Задача 4 - Ноги, стулья, табуретки (100 баллов)
Задача 1 - Ход ладьей (100 баллов)
| Полный балл: | 100 |
| Ограничение времени: | 1 с |
| Ограничение памяти: | 128M |
Петя и Вася играют в следующую игру. У них есть шахматная доска (не обязательно квадратная) размера N x M клеток. Они по очереди ставят на доску шахматные ладьи так, чтобы они не били друг друга. Проигрывает тот, кто не может сделать очередной ход, так как его ладья окажется под боем, на какую бы свободную клетку он ее не поставил. Петя ходит первым. Напишите программу, которая определит, кто победит, Петя или Вася, если оба играют оптимально.
Формат входных данных
В первой строке входных данных содержится натуральное число T (1 ≤ T ≤ 100) количество раз, которое Петя и Вася сыграли в описанную выше игру.
Каждая из последующих T строк содержит два натуральных числа N и M, разделенные пробелом - размеры доски, на которой Петя и Вася играли очередную игру (1 ≤ N, M ≤ 109).
Формат результата
Вывод должен содержать ровно N строк.
Для каждой доски из входных данных выведите в отдельную строку одно слово. Если при оптимальной игре обоих игроков победит Петя, выведите слово First, а если Вася, то выведите слово Second.
Примеры
Входные данные
2
3 4
8 8
Результат работы
First
Second
Примечания
Шахматная ладья бьет все клетки, расположенные с ней на одной горизонтали и вертикали. На рисунке ниже крестиками показаны все поля, которые оказываются под боем, если поставить ладью, например, в клетку d4. Соответственно, в этом случае в отмеченные крестиком поля ставить следующую ладью уже нельзя.
|
|
|
Задача 2 - Паром (100 баллов)
| Полный балл: | 100 |
| Ограничение времени: | 1 с |
| Ограничение памяти: | 128M |
Грузоподъемность парома, который перевозит автомобили через пролив, составляет M тонн. На берегу выстроилась очередь из N автомобилей. Известен вес Ai каждого автомобиля в очереди. Капитан парома хочет взять на борт как можно больше автомобилей, поэтому он решил взять из очереди (не обязательно от начала) максимально возможное количество подряд стоящих автомобилей, суммарный вес которых не превышает грузоподъемность парома. Напишите программу, которая поможет ему это сделать.
Формат входных данных
В первой строке заданы два целых положительных числа - грузоподъемность парома M (1 ≤ M ≤ 100000) и количество автомобилей в очереди N (1 ≤ N ≤ 100000).
В следующей строке записаны через пробел N целых положительных чисел Ai (1 ≤ Ai ≤ 1000)- веса автомобилей в очереди. Первое число A1 - вес первого автомобиля в очереди, второе число A2 - вес следующего за ним автомобиля и т.д.
Формат результата
Выведите единственное число - максимально возможное количество подряд стоящих в очереди автомобилей (не обязательно от начала очереди) суммарный вес которых не превосходит грузоподъемность парома.
|
|
|
Примеры
Входные данные
10 12
3 5 4 3 2 1 2 1 3 5 7 1
Результат работы
5
Задача 3 - Криптография (100 баллов)
| Полный балл: | 100 |
| Ограничение времени: | 500 мс |
| Ограничение памяти: | 128M |
Петя увлекся криптографией и, для начала, придумал очень простой способ шифрования. Каждой маленькой букве латинского алфавита он поставил в соответствие ее порядковый номер в алфавите, начиная с 0. Теперь вместо последовательности букв в слове Петя будет писать последовательность номеров этих букв.
Для простоты он решил ограничиться словами, которые состоят только из первых десяти букв латинского алфавита. Тогда вместо букв {a,b,c,d,e,f,g,h,i,j} Петя будет использовать цифры {0,1,2,3,4,5,6,7,8,9}. Например, слово abba после шифрования превратится в 0110, слово bee - в 144, слово hi - в 78.
Пете так понравился его новый шифр, что он решил сделать о нем доклад на сессии Малой академии наук школьников Крыма "Искатель". Для демонстрации шифра слушателям, Петя заготовил N листочков, на каждом из которых он написал маленькими латинскими буквами некоторое слово. Затем он взял еще N листочков и для каждого записанного ранее слова записал на новый листочек его шифр. Выполнив шифрование, Петя аккуратно разложил все листочки на столе парами слово-шифр и пошел за компьютер заниматься программированием.
|
|
|
Вернувшись через некоторое время к столу, он увидел, что все его листочки со словами и шифрами разложены на две стопки - в одной стопке были слова, в другой шифры - это мама Пети навела порядок на его рабочем столе. Причем и слова, и шифры были расположены с своих стопках в произвольном порядке, а не в том, в котором их писал Петя. Кроме того, в стопке с шифрами оказалось листочков меньше, чем с стопке со словами, то есть некоторые шифры оказались потерянными.
Но Петя не расстроился. Он же программист! Петя сел к компьютеру и написал программу, которая помогла ему найти для каждого слова соответствующий ему шифр или выяснить, что шифр был потерян. А вы сможете написать такую программу?
Формат входных данных
В первой строке задано натуральное число N - количество слов, которое зашифровал Петя (1 ≤ N ≤ 20000). Далее следуют N строк, каждая из которых содержит одно слово, записанное маленькими буквами латинского алфавита. Все слова различны, имеют одинаковую длину не более 9 символов и состоят из первых 10 букв латинского алфавита {a,b,c,d,e,f,g,h,i,j}.
|
|
|
В следующей строке записано число M - количество оставшихся шифров (0 ≤ M < N). В следующих M строках записаны шифры некоторых слов из первых N строк. Слова зашифрованы в соответствии с придуманным Петей правилом. Буква a заменяется цифрой 0, буква b цифрой 1, буква c цифрой 2, и так далее до буквы j, которая заменяется цифрой 9. Шифры могут идти не в том порядке, в котором расположены слова.
Формат результата
Для каждого из N заданных слов необходимо вывести в отельной строке слово YES, если для этого слова шифр есть среди оставшихся M шифров, и слово NO, если шифр был утерян.
Примеры
Входные данные
4
abcd
aaee
jihg
daba
3
9876
0123
3010
Результат работы
YES
NO
YES
YES
Задача 4 - Ноги, стулья, табуретки (100 баллов)
| Полный балл: | 100 |
| Ограничение времени: | 500 мс |
| Ограничение памяти: | 128M |
В школьной столовой стоят табуретки и стулья, на каждой табуретке и на каждом стуле сидит школьник. У табуретки три ноги, у стула четыре ноги, у школьника, конечно же, две. Таракан Митя увлечен математикой. Он подсчитывает все, что попадается на его пути. Пробегая очередной раз по столовой он насчитал N ног. Вам предстоит написать программу, которая вычислит, сколько же было стульев и табуреток в школьной столовой.
Формат входных данных
Ввод содержит единственное целое число N - количество всех ног (y людей, стульев и табуреток вместе взятых), которое насчитал Митя (5 ≤ N ≤ 231-1).
Формат результата
Выведите единственную строку, содержащую два числа, разделенные одним пробелом. Первое число - количество стульев, второе число - количество табуреток.
Так как различных подходящих вариантов для количества стульев и табуреток может быть много, выведите тот, для которого количество стульев отличается от количества табуреток как можно меньше, то есть для которого модуль разности количества стульев и количества табуреток минимален. Входное число N таково, что ответ всегда существует.
Примеры
Входные данные
39
Результат работы
4 3
Входные данные
100
Результат работы
10 8
Примечания
В первом примере ответ единственный - 4 стула и 3 табуретки.
Во втором примере существует 4 различных варианта для количества стульев и табуреток:
Стулья Табуретки Модуль разности
0 20 20
5 14 9
10 8 2
15 2 13
Так как наименьший модуль разности количества стульев и табуреток получается для варианта 10 стульев и 8 табуреток, его и надо выводить в качестве ответа.
Дата добавления: 2018-11-24; просмотров: 360; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!