Страница: << 17 18 19 20 21 22 23 >> Отображать по:
#1020
Левый лабиринт
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

В спортзале размером NxM метров построили современный аттракцион под названием "Левый лабиринт". Для этого на полу спортзала с интервалом в 1 метр начертили линии, параллельные стенам спортзала. Таким образом, спортзал разбили на NxM клеток. Дальше некоторые из этих клеток покрасили в черный цвет.

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

  • Участнику запрещено ходить по черным клеткам.
  • Придя в какую-то клетку, участник может пойти либо прямо, либо налево, либо направо (если в соответствующем направлении клетка не покрашена в черный цвет): ходить назад, а также ходить по диагонали запрещается.
  • За все время пути участнику разрешается повернуть направо (то есть пойти из текущей клетки направо относительно того, откуда он пришел в данную клетку) не более K раз.
  • В начальной клетке участник может встать лицом в ту сторону, в какую ему захочется. С какой стороны участник прибежит в конечную клетку также не важно.

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

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

Во входном файле сначала записано число K — количество разрешенных поворотов направо (целое число из диапазона от 0 до 5), затем записаны числа N и M, задающие размеры спортзала — натуральные числа, не превышающие 20. Далее записано N строк по M чисел в каждой. Число 0 обозначает непокрашенную клетку, число 1 — покрашенную, число 2 — клетку, откуда стартует участник и число 3 — клетку, куда нужно добежать (клетки, помеченные 2 и 3 являются непокрашенными). В лабиринте всегда есть ровно одна начальная клетка и ровно одна клетка, в которую нужно попасть.

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

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

Примеры
Входные данные
1 3 4
0 0 2 0
0 1 1 0
0 0 3 0
Выходные данные
6
Входные данные
0 5 5
0 1 0 0 0
0 1 0 1 0
0 0 3 1 0
1 0 1 1 0
2 0 0 0 0
Выходные данные
12
#1022
Анаграммер
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Анаграммер — специальное устройство для получения из слова его анаграмм (то есть слов, записанных теми же буквами, но в другом порядке). Это устройство умеет выполнять 2 операции:

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

Стек — это хранилище данных, которое работает по принципу "первый пришел — последний ушел". Стек можно представить себе в виде пирамидки. Когда мы добавляем букву в стек, это соответствует тому, что на стержень пирамидки сверху мы надеваем кольцо, на котором написана соответствующая буква. Когда берем букву из стека, то это соответствует тому, что мы снимаем со стержня верхнее кольцо, и смотрим, какая буква на нем написана.

Например, слово TROT в слово TORT может быть преобразовано анаграммером двумя различными последовательностями операций: 11112222 или 12112212.

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

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

Первая строка входного файла содержит исходное слово, а вторая — слово, которое необходимо получить. Слова состоят только из заглавных латинских букв и имеют длину не более 50 символов. Оба слова имеют одинаковую длину. В этих строках не содержится пробелов.

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

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

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

Примеры
Входные данные
TORT
TROT
Выходные данные
2
11112222
12112212
Входные данные
MOSCOW
OMCOWS
Выходные данные
1
112211212122
#1028
Поиск прямоугольников
  

0

2

2

2

2

0

2

2

2

2

1

1

2

2

2

1

1

0

0

0

На поле NxM клеток (N строк и M столбцов) положили K прямоугольников один поверх другого в случайном порядке. Длины сторон прямоугольников выражаются целым числом клеток. Прямоугольники не выходят за границы поля. Границы прямоугольников совпадают с границами клеток поля.

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

По содержимому таблицы требуется определить положение и размеры прямоугольников.

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

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

В первой строке входного файла записаны целые числа N, M, K (1N200, 1M200, 1K255). Далее следует N строк по M чисел в каждой — содержимое таблицы. Все числа в таблице целые, находятся в диапазоне от 0 до K включительно.

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

В выходной файл необходимо выдать K строк. Каждая строка должна описывать соответствующий ее номеру прямоугольник четырьмя числами R C H W (R и C должны описывать координаты левого нижнего угла прямоугольника, а H и W — координаты правого верхнего угла). Числа должны разделяться пробелом.

Оси координат устроены следующим образом: начало координат находится в нижнем левом углу поля, а оси координат направлены вдоль сторон поля (ось Ox — вдоль нижней стороны, а ось Oy — вдоль левой стороны). Клетки поля имеют размер 1x1. Таким образом, координаты левого нижнего угла поля — (0,0), правого верхнего — (M,N). Заметьте, что вы должны вывести координаты углов прямоугольников (как точек) в этой системе координат, а не координаты угловых клеток, покрытых прямоугольниками.

Примеры
Входные данные
4 5 2
0 2 2 2 2
0 2 2 2 2
1 1 2 2 2
1 1 0 0 0
Выходные данные
0 0 2 2
1 1 5 4
#1032
Узор
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

В комнате решили сделать паркетный пол. Причем есть задумка выложить на полу некоторый узор.

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

Существует несколько форм паркетных плиток:

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

Изначально, какая-то часть пола может уже быть выложена плиткой.

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

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

В первой строке входного файла записаны три числа: N, M (размеры комнаты) и K (количество доступных видов плитки). 1≤N≤8, 1≤M≤8, 1≤K≤10. Далее идет описание желаемой раскраски пола. Описание представляет собой N строчек по M чисел в каждой, где 0 обозначает белый цвет, 1 — черный, 2 — то, что квадрат уже выложен плиткой. В последних K строчках находятся описания доступных типов плитки в следующем формате:

<форма> <стоимость> <окраска>

<Форма> — это число от 1 до 4, описывающее форму плитки (см. рисунок выше)

<Стоимость> — это натуральное число, не превосходящее 10000, задающее стоимость одной плитки такого типа

<Окраска> — это от одного до трех чисел 0 или 1. Количество чисел совпадает с количеством квадратиков, из которых состоит плитка. Числа задают цвета квадратиков плитки в том порядке, в каком квадратики пронумерованы на рисунке.

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

В выходной файл выведите единственное число — минимальную стоимость укладки или –1, если требуемым образом уложить плитку невозможно.

Примеры
Входные данные
4 3 3
2 2 2
2 0 0
2 1 2
2 2 2
2 10 0 0
1 5 1
4 6 0 0 1
Выходные данные
15
#1044
Лотерея
  

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

В некоторый момент прием ставок на текущий розыгрыш завершается, и после этого ведущий в телеэфире называет выигравшее число (это также \(M\)-значное число в \(K\)-ичной системе счисления). После этого те телезрители, у кого первая цифра их числа совпала с первой цифрой числа, названного ведущим, получают выигрыш в размере \(A_1\) рублей. Те, у кого совпали первые две цифры числа — получают \(A_2\) рублей (при этом если у игрока совпала вторая цифра, но не совпала первая, он не получает ничего). Аналогично угадавшие первые три цифры получают \(A_3\) рублей. И так далее. Угадавшие все число полностью получают \(A_m\) рублей. При этом если игрок угадал \(t\) первых цифр, то он получает \(A_t\) рублей, но не получает призы за угадывание \(t-1\), \(t-2\) и т.д. цифр. Если игрок не угадал первую цифру, он не получает ничего.

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

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

В первой строке задаются числа \(N\) (количество телезрителей, сделавших свои ставки, \(1\le N\le 100000\)), \(M\) (длина чисел \(1\le M\le 10\)) \(K\) (основание системы счисления \(2\le K\le 10\)). В следующей строке записаны \(M\) чисел \(A_1\), \(A_2\), ..., \(A_M\), задающих выигрыши в случае совпадения только первой, первых двух,... , всех цифр (\(1\le A_1\le A_2\le ... \le A_M\le 100000\)). В каждой из следующих \(N\) строк записано по одному \(M\)-значному \(K\)-ичному числу. Числа идут в порядке неубывания.

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

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

Примеры
Входные данные
10 3 2
1 3 100
000
000
001
010
100
100
100
100
110
111
Выходные данные
011
6
Входные данные
1 1 10
100
0
Выходные данные
1
0
Страница: << 17 18 19 20 21 22 23 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест