Темы --> Информатика --> Алгоритмы --> Игры и выигрышные стратегии
    Простые игры(20 задач)
    Функция Гранди(6 задач)
---> 7 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: 1 2 >> Отображать по:
#13
Сетевая игра
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Петя и Вася нашли на чердаке остатки рыболовной сети своего деда. Часть веревок давно сгнила, и сеть распалась на большое число кусков, каждый из которых состоит не более чем из 50 веревочек единичной длины.

Так как использовать по назначению остатки данной сети было уже нельзя, братья разложили один из найденных кусков на прямоугольном столе так, что веревочки оказались параллельны сторонам стола, и стали играть в следующую игру.

Братья делают ходы по очереди, Петя ходит первым. Своим ходом игрок находит веревочку, являющуюся стороной некоторой целой единичной квадратной ячейки сети (все

четыре образующие ее веревочки целы), и перерезает выбранную веревочку. Проигрывает тот из братьев, который не может сделать очередной ход.Требуется написать программу, которая по описанию куска сети на столе определяет, может ли Петя выиграть при любой игре Васи, и если да, то какой первый ход он должен для этого сделать.

Входные данные

В первой строке входных данных задается число N (1 ≤ N ≤ 50) — количество веревочек единичной длины, из которых состоит кусок сети. Следующие N строк содержат по две пары целых чисел — координаты концов веревочек. Каждая четверка чисел описывает отрезок единичной длины, параллельный одной из осей координат.

Координаты всех точек неотрицательны и не превосходят 50.

Выходные данные

Первая строка выходных данных должна содержать число 1, если Петя может выиграть при любой игре Васи, и число 2, если нет. В случае выигрыша Пети вторая строка должна содержать номер веревочки, которую он должен перерезать первым ходом. Если возможных выигрышных ходов несколько, выведите любой. Веревочки пронумерованы, начиная с 1, в том порядке, в котором они заданы во входных данных.

Примечание

В примере во второй строке выведено два числа. Это сделано для иллюстрации того, какие именно веревочки можно разрезать. Вам требуется вывести любую одну из них.

Максимальная оценка за решение задачи при N ≤ 13 равна 40 баллам.

Примеры
Входные данные
10
2 1 2 0
1 2 2 2
2 2 2 1
0 2 1 2
1 1 2 1
2 0 1 0
1 1 0 1
1 1 1 2
1 0 1 1
0 1 0 2
Выходные данные
1
2 3
#991
Раскраска плиток
  
Плитки поля N*N покрашены в K цветов. Необходимо перекрасить все клетки в один цвет (в т.ч. клетки, которые уже были покрашены в этот цвет). Красить в цвет C можно строку или столбец целиком, если эта строка или столбец содержит хотя бы две клетки цвета C. Необходимо подсчитать минимальное количество перекрашиваний и цвет, в который будет окрашено поле.

После того, как к удивлению тётушки Полли, её забор был покрашен, она поручила Тому Сойеру обновить краску на плитках, которыми был вымощен их квадратный двор. Двор был покрыт NN одинаковыми квадратными плитками, каждая из которых когда-то давно была покрашена в один из K цветов (K<N). Краска на плитках потускнела и Тому Сойеру поручили их покрасить, на этот раз в один любой цвет (из тех же К цветов). Покрасить нужно все плитки, в том числе и те, которые уже были покрашены в этот цвет раньше.

Окунув кисть в ведро с краской один раз, можно перекрасить один горизонтальный или вертикальный ряд плиток. Чтобы разнообразить свою работу, Том придумал, что ряд плиток можно красить только цветом, которым на данный момент уже покрашены (старой или новой краской) по крайней мере две плитки выбранного ряда (вертикального или горизонтального). За один раз Том собирается красить допустимым цветом весь ряд целиком, независимо от того, были ли уже перекрашены какие-либо его плитки ранее. Помогите Тому определить, какое минимальное число раз ему придется обмакнуть кисть, чтобы перекрасить все плитки, следуя придуманным правилам, и в какой цвет окажутся окрашены все плитки.

Входные данные

В первой строке входного файла записаны через пробел два числа: N — количество плиток в одном ряду (1<N≤200) и K (1≤K<N). В каждой из следующих N строк записаны N натуральных чисел, обозначающих номера цветов красок, в которые когда-то были выкрашены соответствующие плитки данного горизонтального ряда. Номера цветов — натуральные числа в диапазоне от 1 до K.

Выходные данные

В выходной файл выведите два числа: L — какое минимальное число раз придется окунать кисть в ведро с краской, и номер краски С, в которую в результате окажутся перекрашены все плитки двора. Если таких красок может быть несколько, то выведите номер любой из них.

Если перекрасить все плитки, следуя придуманным Томом правилам, нельзя, выведите два раза число 0.

Примеры
Входные данные
3 2
1 2 1
2 1 1
1 2 2
Выходные данные
4 1
Входные данные
2 1
1 1
1 1
Выходные данные
2 1
#1014
Великая сеча
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Алеша Попович и Добрыня Никитич сражаются со стаей двух- и трехголовых драконов. Они по очереди взмахивают мечами, и одним махом могут отрубить любое (по своему желанию) число голов, но только у одного дракона. Отрубивший последнюю голову у последнего дракона получает в жены прекрасную принцессу.

Кто из богатырей (начинающий или второй) может получить в жены принцессу независимо от действий другого?

Входные данные

Во входном файле записано два числа N и M — количество двух- и трехголовых драконов соответственно (оба числа целые из диапазона от 0 до 100).

Выходные данные

В выходной файл выведите сначала число 1 или 2 определяющее, кто из богатырей имеет все шансы получить в жены принцессу (1 — тот, кто начинает, 2 — второй). В случае 1 выведите также все варианты его первого хода, которые к этому приводят: сначала выведите количество различных выигрышных ходов (при этом отрубание одинакового количества голов у разных двухголовых драконов считается одним и тем же ходом, так же и для трехголовых), а затем сами ходы. Каждый ход задается парой чисел: первое число определяет у сколькиголового дракона нужно отрубать головы, а второе — сколько голов нужно отрубать.

Примеры
Входные данные
2 0
Выходные данные
2
Входные данные
3 2
Выходные данные
1
2
2 2
3 2
#1029
Разноцветные треугольники
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Выпуклый N-угольник разбит непересекающимися диагоналями на треугольники. (Многоугольник называется выпуклым, если любая его диагональ лежит внутри него.) Требуется покрасить каждую сторону и каждую проведенную диагональ в красный или синий цвет так, чтобы у каждого треугольника были стороны как красного, так и синего цвета.

Требуется привести любую из допустимых раскрасок.

Входные данные

В первой строке записано одно число N (4N100) - количество вершин многоугольника.

Далее следуют N–3 строки, в каждой из которых записана пара натуральных чисел — номера вершин, которые соединяет диагональ. Считается, что все вершины занумерованы последовательно натуральными числами от 1 до N.

Выходные данные

В выходном файле должны быть 2N–3 строки. Каждая строка содержит 3 числа: номера вершин, которые соединяет данная сторона или диагональ и цвет (1 - синий, 2 - красный), в который Вы красите данную сторону или диагональ.

Примечание

Возможный ответ на перый тест:

3 4 1

2 3 2

1 2 1

1 3 2

1 4 1

Возможный ответ на второй тест:

5 6 1

4 5 2

3 4 1

3 5 2

2 3 1

1 2 2

1 3 1

1 5 2

1 6 1

Примеры
Входные данные
4
1 3
Выходные данные
Входные данные
6
1 3
3 5
5 1

Выходные данные

                            
                                


                        

                    

                    

                        

                            

                                #1039
                            

                            

                                Магия Копперфильда
                            

                              
                
                            

                                
                                
                            


                        

                        

                                

                                

                                    

                                        
ограничение по времени на тест

                                        2.0 second;
                                    
                                        
ограничение по памяти на тест

                                        64 megabytes
                                    

                                

                            
                                Дана прямоугольная таблица. Фишка в таблице может перемещаться в любое место на K ходов. Требуется последовательно убрать все ячейки таблицы, кроме одной, задавая количество ходов, на которые должна сходить фишка, и координаты удаляемых клеток. Фишка должна оказаться в единственной оставшейся клетке.

                            

   

 	

 
Всемирно известный маг Дэвид Копперфильд любит показывать следующий трюк. Квадрат из N столбцов и N строк, в каждой клетке которого находится какая-нибудь картинка, появляется на экране телевизора. Пусть все картинки пронумерованы следующим образом:


 
 	 	 	 	 	
 		 			
1
 				 		 			
2
 				 		 			
…
 				 		 			
N
 				 	
 	
 		 			
N+1
 				 		 			
N+2
 				 		 			
…
 				 		 			
2*N
 				 	
 	
 		 			
:
 				 		 			
:
 				 		 			
…
 				 		 			
:
 				 	
 	
 		 			
N*(N–1)+1
 				 		 			
N*(N–1)+2
 				 		 			
…
 				 		 			
N*N
 				 	
 
 




Дэвид просит каждого зрителя поставить палец на левую верхнюю картинку (то есть в клетку номер 1), и Магия начинается: маг просит зрителей сдвинуть свой палец K1 раз в произвольном направлении (сдвигать палец разрешается только на соседнюю картинку по горизонтали или по вертикали, оставлять палец на месте запрещено, при этом если, допустим, Дэвид попросил сдвинуть палец 3 раза, то можно, например, сдвинуть палец на одну клетку вправо, затем — на одну клетку вниз, затем — на одну вверх). Затем со словами "Ваш палец не здесь" Дэвид убирает некоторые картинки, и — что удивительно, пальцы телезрителей действительно не указывают на те картинки, которые убирает Дэвид. Затем он просит сделать K2 ходов, и так далее (если Дэвид уже убрал какую-то картинку, то ходить через эту клетку нельзя). В конце, Дэвид убирает все картинки, кроме одной, и, улыбаясь, говорит: "Вы здесь" (аплодисменты).


 
Дэвиду приходится довольно часто повторять этот трюк, и, чтобы не ошибиться, он попросил написать программу, которая будет ему сообщать, сколько ходов должны делать телезрители, и какие картинки нужно убирать. Напишите такую программу.
 

   


   

    

     Входные данные
    




Во входном файле записано одно число N — размер квадрата (2N100).
 


   


   

    

     Выходные данные
    




В выходной файл ваша программа должна печатать следующие строки чисел:


 
K1 X1,1 X1,2 … X1,m1


 
K2 X2,1 X2,2 … X2,m2
 


 …



 
Ke Xe,1 Xe,2 … Xe,me


 
где Ki — это число ходов, которые должны сделать телезрители, а Xi,1 … Xi,mi — номера картинок, которые Дэвид должен убрать с экрана после этого. При этом все Ki должны удовлетворять условию 2NKi10000 и все Ki должны быть различны. Каждая картинка (кроме той, которая останется) должна убираться ровно один раз. После каждой просьбы зрителей сделать Ki ходов, Дэвид должен убирать хотя бы одну картинку. Каждое Ki должно печататься в начале новой строки. Ситуаций, когда телезритель остался на клетке, у которой нет соседних, а его просят куда-нибудь ходить, возникать не должно.
 

    

    


                            
Примеры
Входные данные
3

Выходные данные
7 1 3 7 9
9 2 4 6 8


                            
                                


                        

                    

                

                
        

            Страница: 
                    1
                    2
                >>
            Отображать по:
            
        

    
            

        

        
    
    

    

        

            
Выбрано
:
            
Отменить
|
            
Добавить в контест