Ограничения для всех задач
Объем используемой программой памяти: 64 Мб
Время выполнения одного теста: 2 секунды
Ввод: с клавиатуры
Вывод: на экран
A. Цифры
Чтобы привлечь самых маленьких детей в летнюю компьютерную школу «КЭШ», руководством было приобретено очень много красивых пластмассовых цифр. Однажды мимо коробки, где они хранились, проходил ди-джей Евгений. Заметив среди цифр нули он решил, что это сушки, и все их съел. Теперь детям на уроках математики приходится решать задачи без использования нулей. Например, иногда их просят составить любое число с суммой цифр равной N. Мы не спрашиваем, было ли у Евгения расстройство желудка. То, что нас интересует, это сколько разных чисел с суммой разрядов N можно составить из цифр от 1 до 9.
Входные данные
Число N от 1 до 29.
Выходные данные
Единственное число – количество чисел, которые можно составить из цифр, сумма которых равна N.
Пример входных данных
4
Пример выходных данных
8
Примечание
Следующие числа имеют сумму разрядов, равную 4: 1111, 112, 121, 211, 22, 13, 31, 4.
B. Счастливый ноутбук
В компьютерной школе «КЭШ» было очень много ноутбуков. Но мальчик Серёжа соглашался работать только на тех из них, чьи номера он считал «счастливыми». Каждый ноутбук имеет четырёхзначный номер и Серёжа считает его «счастливым» только в том случае, если сумма первых двух цифр этого номера равна сумме двух последних его цифр. Напишите программу, определяющую является ли ноутбук «счастливым».
Входные данные
Четырёхзначный номер ноутбука. Номер не содержит ведущих нулей.
Выходные данные
Выведите «YES» (без кавычек), если Серёжа считает ноутбук «счастливым» и «NO» в противном случае.
Пример входных данных
4563
Пример выходных данных
YES
C. Главное не победа, а обед
Один из отрядов в летней компьютерной школе «КЭШ» решил поучаствовать в соревнованиях, которые состояли из двух этапов. За победу в каждом этапе был объявлен отдельный приз. За первый этап – N конфет, за второй – M сушек. В соревнованиях могут принимать участие команды из любого числа человек. Поэтому ребята решили выставить на соревнования столько человек, чтобы в случае победы любой из призов можно было бы разделить поровну между участниками. Какое максимальное количество участников может быть в команде, чтобы это условие выполнялось?
Входные данные
Два положительных числа – N и M, разделенные пробелом. Каждое из чисел не превышает 2⋅109.
Выходные данные
Одно число – максимально возможное количество человек в команде.
Пример входных данных
24 30
Пример выходных данных
6
D. Вестник «КЭШ»
Однажды отряду №3 в летней компьютерной школе «КЭШ» поручили написать газету о событиях в лагере. Текст им составить удалось, однако на оформление газеты сил не хватило, так как дело было после изнурительной утренней зарядки. К счастью, к ним в руки попала газета отряда №1. Теперь третий отряд хочет вычеркнуть из найденной газеты некоторые символы, чтобы получить свой текст. Помогите им определить, смогут ли они это сделать.
Входные данные
Входные данные состоят из двух строк. В первой строке – текст газеты первого отряда, во второй – текст газеты третьего отряда. Длина обоих текстов не меньше 1 и не превышает 30000 символов. Каждый пробел в любой из строк учитывается как отдельный символ. Заглавные и строчные буквы различаются.
Выходные данные
Выведите «YES» (без кавычек), если третьему отряду удастся оформить газету и «NO» в противном случае.
Пример входных данных
NOT A TEXT FOR THINKING ON
NOTHING
Пример выходных данных
YES
E. Немного математики
В летней компьютерной школе «КЭШ» периодически проходят олимпиады по математике. Мальчик Лёша очень любил такие олимпиады. В одной из них ему предложили решить уравнение: x⋅y⋅z=N для заданного значения N, таким образом, чтобы получились положительные значения x, y и z, удовлетворяющие условию x<y<z. Лёша решил эту задачу, но позже ему захотелось написать программу, решающую её в общем виде (т. е. для произвольного N). Помогите ему.
Входные данные
Положительное число N не превышающее 2147483647.
Выходные данные
Разделенные пробелами значения x, y и z или строка «NO SOLUTION» (без кавычек), если решение не существует. Если решений несколько, выведите любое из них.
Пример входных данных
24
Пример выходных данных
2 3 4
F. Зарница
Между некоторыми жилыми и учебными домиками в летней компьютерной школе «КЭШ» организованы каналы связи для обмена информацией между компьютерами. Во время проведения игры «Зарница» команде диверсантов было поручено установить контроль над всеми каналами связи. Канал связи между домиками u и v считается взятым под контроль, если хотя бы один из этих домиков захвачен диверсантом. Команда диверсантов хочет захватить все каналы связи, взяв под свой контроль как можно меньшее количество домиков (ведь у них есть еще другие важные задания, поэтому нужно оставить в домиках как можно меньше людей). Помогите им определить минимальное количество человек и возможный план захвата.
Входные данные
Первая строка содержит два целых числа: N – число домиков и M – число каналов связи (2 ≤ N ≤ 18, 0 ≤ M). Каждая из последующих M строк описывает один канал связи и содержит по два целых числа U и V (1 ≤ U, V ≤ N, U ≠ V) – номера домиков, соединенные этим каналом связи. Любая пара домиков соединена не более, чем одним каналом связи.
Выходные данные
В первой строке выведите два числа: K и C – соответственно, минимальное количество диверсантов, которое потребуется для установления контроля над всеми каналами связи, и число способов захватить такое количество домиков, чтобы контролировать все каналы связи.
Во второй строке выведите K чисел – номера домиков, соответствующих одному (любому) из способов захвата.
Пример входных данных 1
3 3
1 2
2 3
3 1
Пример выходных данных 1
2 3
1 2
Пример входных данных 2
5 4
1 2
1 3
1 4
1 5
Пример выходных данных 2
1 1
1
Примечание
В первом примере существует три способа захватить два домика так, чтобы контролировать все каналы связи: {1, 2}, {1, 3}, {2, 3}.
G. Крестики-нолики
Однажды в летней компьютерной школе «КЭШ» проходил турнир по игре крестики-нолики по классическим правилам. От каждого из участников требовалось написать программу, которая играет против программы другого участника. Мальчик Миша тоже решил участвовать в этом конкурсе, но у него не хватило времени, чтобы закончить свою программу. В программе осталось лишь реализовать часть, проверяющую является ли позиция, полученная на каком-либо шаге игры, выигрышной для какого-либо игрока. Позиция является выигрышной, если в любой строке, столбце или диагонали расположено одновременно 3 крестика или 3 нолика. Помогите Мише написать программу, которая по заданной игровой позиции проверяет, является ли она выигрышной для какого-либо игрока.
Входные данные
В трех строках записано ровно по 3 символа каждый из которых может быть «0» (ноль), «x» или «.», т. е. «нолик», «крестик» и «пусто» соответственно. Заданная позиция всегда корректна (т. е. могла возникнуть в процессе игры по правилам).
Выходные данные
Выведите «0» (ноль), «x», если победили нолики или крестики и «NONE», если не нашлось трех крестиков или ноликов в ряд.
Пример входных данных
..x
.0x
0.x
Пример выходных данных
x
H. Водные процедуры
В летней компьютерной школе «КЭШ» иногда бывает очень жарко. В такие дни Дмитрий Александрович каждый чётный час (но не раньше 10 и не позже 20 часов) поливает детей из пожарного шланга, чтобы они хоть немного охладились. Мальчик Лёня хочет узнать, когда ещё сегодня будут проводиться водные процедуры. Его не интересуют уже начавшиеся и прошедшие обливания, а также те, что будут проходить завтра. Кроме того, он не очень надеется на свою память, поэтому хочет знать время не более 3 процедур. Помогите ему узнать, когда он сможет охладиться.
Входные данные
Два числа, обозначающие текущее время H (0 ≤ H ≤ 23) и M (0 ≤ M ≤ 59), разделенные пробелом.
Выходные данные
Выведите не более 3 ближайших моментов времени (часы и минуты, разделённые пробелом), когда начинаются водные процедуры после текущего момента времени, в порядке от более ранних к более поздним. Если сегодня водных процедур не предвидится, ничего выводить не нужно.
Пример входных данных
16 00
Пример выходных данных
18 00
20 00
I. Треугольники
Однажды в летней компьютерной школе «КЭШ» мальчик Дима случайно зашёл в класс математики. Его внимание привлекла доска на которой было в беспорядке нарисовано некоторое количество треугольников. Диме очень понравилась идея разрисовывания доски треугольниками, и он принялся изучать ситуацию более внимательно. Он подумал, что наиболее простой и быстрый способ ровно нарисовать такое количество треугольников - вырезать из какого-нибудь материала шаблон и обводить его на доске мелом. Кроме того, Дима предположил, что тот, кто рисовал треугольники, должно быть, очень спешил, и потому перемещал шаблон, не отрывая никакую его часть от доски.
Помогите Диме проверить его гипотезу, если он готов сообщить вам тщательно измеренные координаты вершин треугольников.
Входные данные
В первой строке записано одно целое число - количество треугольников N (2 ≤ N ≤ 100). Последующие N строк описывают треугольники, строка i+1 содержит 3 пары положительных целых чисел, не превосходящих 10000 - координаты вершин треугольника номер i.
Выходные данные
Выведите слово «YES» (без кавычек), если треугольники можно было нарисовать, обводя один шаблон и не отрывая этот шаблон от доски, и «NO» в противном случае.
Пример входных данных 1
3
1 1 1 2 2 1
2 1 2 2 1 2
1 1 2 1 2 2
Пример выходных данных 1
YES
Пример входных данных 2
2
1 1 4 1 2 2
1 1 4 1 3 2
Пример выходных данных 2
NO
J. Прогулка
В лагере «Былина», где проходила смена летней компьютерной школы «КЭШ» очень много тропинок. Тропинки соединяют между собой поляны, квадратные и треугольные домики, столовую и другие интересные места таким образом, что из каждого места существует путь в любое другое. Девочка Лиза очень любит гулять по вечерам и хочет составить круговой маршрут по некоторым из этих тропинок (такой маршрут должен начинаться и заканчиваться в одном и том же месте, при этом ни по одной тропинке не требуется проходить дважды).
Для того, чтобы не пропустить ни одной тропинки, Лиза предварительно пронумеровала все интересные места числами от 1 до N и выписала все тропинки как пары чисел, обозначающих места, которые соединяет данная тропинка. При этом Лиза немного торопилась, и некоторые тропинки оказались выписанными более одного раза.
Помогите Лизе написать программу, определяющую, есть ли в лагере круговой маршрут, удовлетворяющий приведённым ограничениям.
Входные данные
Первая строка содержит два целых числа: N (1 ≤ N ≤ 1000) – количество интересных мест в лагере и M (0 ≤ M ≤ 100000) – количество тропинок в составленном списке.
Последующие M строк описывают тропинки. Каждая тропинка описывается двумя числами: U и V (1 ≤ U, V ≤ N, U ≠ V) – номерами мест, которые она соединяет. Так как тропинки двусторонние, пары чисел (U, V) и (V, U) описывают одну и ту же тропинку.
Выходные данные
Выведите слово «YES», если требуемый круговой маршрут существует и «NO» - в противном случае.
Пример входных данных 1
3 4
1 2
2 3
3 1
3 2
Пример выходных данных 1
YES
Пример входных данных 2
2 3
1 2
2 1
2 1
Пример выходных данных 2
NO
