Страница: << 1 2 3 4 5 6 7 >> Отображать по:
#78
Прямоугольники
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дан прямоугольник N x M, состоящий из квадратиков 1 x 1. Некоторые квадратики вырезали. Надо найти наименьшее количество прямоугольников, на которое можно разрезать оставшуюся фигуру.

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

В первой строке входных данных заданы числа N и M, (1 ≤  N, M ≤ 10). Далее следует N строк. В (i+1)-ой содержится M чисел; j-е число равно 1, если клетку на i-й строке и в j-м столбце вырезали из доски, 0 – если оставили.

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

Выведите единственное число – минимальное количество прямоугольников, на которое можно разрезать полученную фигуру.

Примеры
Входные данные
2 2 
0 0
1 0
Выходные данные
2
#79
Арбузная грядка
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

Ограничение по времени:        3 секунды
Ограничение по памяти:         64 мегабайта

На этот раз Вася увлекся выращиванием арбузов. Его огород имеет форму прямоугольника \(N \times M\) метров, разделенного на одинаковые ячейки размером \(1 \times 1\) метр, в каждой из которых растет по арбузу. Как-то раз он решил  осмотреть некоторые из них, начав в левом верхнем углу, пройдясь по огороду и вернувшись обратно. Ячейки, оказавшиеся внутри цикла, считаются осмотренными, остальные – не осмотренными. По некоторым банальным соображениям Вася не ходит по грядкам, а только лишь по специальным дорожкам, расположенным на границах ячеек с арбузами. Вдобавок, он хочет, чтобы его путь получился без самопересечений. К счастью, дорожки достаточно широкие для того, чтобы гулять по ним много раз, не считая это за самопересечение (см. рисунки к примерам).

Ваша задача – узнать, за какое минимальное время Васе удастся обойти ровно i арбузов. Можно считать, что он двигается равномерно со скоростью 1 метр в секунду.

Формат входных данных 

В первой строке входных данных содержатся два числа \(N, M (1 \le N, M \le 50)\). В следующих N строках идет описание огорода. В (i + 1)-й строке содержатся M символов. Символ "I" на j-й позиции означает, что Вася хочет осмотреть арбуз, расположенный в i-й строке и j-м столбце огорода; символ " ." означает, что ему не важно, что происходит в соответствующей ячейке; символ "X" означает, что он не хочет осматривать это растение. Других символов в строке нет.

Гарантируется, что  суммарное количество символов "I" и "X" не превосходит 10, и присутствует хотя бы один символ "I".

Формат выходных данных 

Выведите ровно K чисел, разделенных пробелами, где K – количество арбузов, которые Вася хочет осмотреть (количество символов "I" во входном файле). Число номер i должно быть равно минимальному времени, за которое он успеет осмотреть ровно i арбузов, соответствующих символам "I".

Не забудьте учесть, что арбузы, помеченные ".", могут быть осмотрены или нет, но арбузы "X" Вася осматривать не хочет ни в коем случае.

Примеры

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

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

1 1
I             

4

2 2
XX
XI

8
Рис. 1

3 3
III
IXI
III

4 6 8 10 12 14 16 18
Рис. 2

3 3
X. I
.I.
I..

8 10 14

1 10
IIXIIXIXII

4 6 12 14 20 26 28

#191
Шахматный детектив
  
Источники: [ Командные олимпиады, ВКОШП, 2006, Задача A ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes
Дано изображение состоящее из черных, белых и серых клеток. Необходимо определить, может ли изображение быть шахматной доской (клетки доски могут состоять из нескольких маленьких клеток). 

Известный частный сыщик поставил чашку с чаем на специальную подогревающую подставку, питающуюся от USB-порта его компьютера, и приступил к обдумыванию очередного запутанного преступления. Через пару часов раздумий он понял, что для разгадки этого дела достаточно определить, была ли на месте преступления шахматная доска.

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

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

 

includegraphics{pics/chess.1} includegraphics{pics/chess.2}

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

Шахматная доска – это квадрат, разбитый на x2 (для некоторого x) равных квадратов – полей. Стороны полей параллельны сторонам изображения. Длина стороны каждого поля шахматной доски выражается целым числом пикселей. Все пиксели, принадлежащие одному полю, покрашены в один и тот же цвет – черный или белый. При этом соседние поля (поля, имеющие общую сторону) покрашены в различные цвета.

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

В первой строке вводятся два целых числа: m и n – размеры фрагмента фотографии в пикселях ( 1\( le\)m, n\( le\)250).

Следующие m строк содержат по n символов каждая, j-й символ i-й строки соответствует пикселю с координатами (i, j). Символ «.» (точка) означает белый пиксель, символ «*» – черный, символ «?» – серый.

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

Если заданный фрагмент фотографии может быть изображением части шахматной доски, выведите  слово «YES». После этого выведите m строк по n символов в каждой – изображение соответствующей части шахматной доски в том же формате, что и во входных данных, только серые пиксели должны быть заменены на белые или черные. Если решений несколько, выведите любое.

В противном случае программа должна вывести слово «NO».

Примеры
Входные данные
4 5
*.?.?
.***.
.*?*.
.*?*.
Выходные данные
YES
*...*
.***.
.***.
.***.
Входные данные
4 5
..?..
.***.
.*?*.
.*?*.
Выходные данные
NO
#201
Числа Фибоначи
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
F1 = F2 = 1, Fn = Fn-1 + Fn-2, при n > 2

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

В единственной строке входных данных записано натуральное число n (1≤n≤45).

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

Вывести одно число Fn

Примеры
Входные данные
2
Выходные данные
1
Входные данные
5
Выходные данные
5
#202
Игра со спичками
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На столе лежит кучка из N спичек. Двое играют в такую игру. За один ход разрешается взять из кучки одну, две или три спички, так чтобы оставшееся количество спичек не было простым числом (Например, можно оставить в кучке 1 или 4 спички, но нельзя оставить 2 или 3). Выигрывает тот, кто забирает последнюю спичку. Требуется определить, кто из игроков имеет выигрышную стратегию.

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

Вводится одно число N (1<=N<=10000).

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

Выведите число 1, если выигрышую стратегию имеет начинающий игрок, или число 2, если выигрышную стратегию имеет второй игрок.

Примеры
Входные данные
1
Выходные данные
1
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест