Сегодня папа познакомил Тимофея с шахматными фигурами. Больше всего сыну понравился слон. Он ему понравился настолько, что Тимофей все остальные фигуры тоже объявил слонами (с соответствующими правилами перемещения) и теперь старается разместить на шахматной доске как можно больше не угрожающих друг другу слонов. А папа задумался - какое наибольшее количество не угрожающих друг другу слонов можно разместить на доске размером n × n?
Формат входных данных
В единственной строке входного файла записано одно натуральное число: n – размер шахматной доски.
Формат выходных данных
Выведите одно натуральное число - ответ на задачу.
Тимофею подарили набор цифр. Он быстро научился составлять из них различные числа. Помогите Тимофею составить из всего набора цифр минимально возможное число.
Формат входных данных
В единственной строке входного файла записано одно натуральное число: n — набор цифр, подаренных Тимофею. (1 ≤ n ≤ 1000000000).
Формат выходных данных
Выведите одно натуральное число — минимально возможное число, составленное из того же набора цифр.
На чердаке у бабушки Антон нашел пару старых счёт. Первые счёты
изначально имели n1 спиц, на каждой из которых располагалось по m1
костяшек, вторые — соответственно n2 спиц по m2 костяшек.
Время не пощадило вычислительные приспособления, и часть спиц и костяшек оказалось утрачено.
Антон хочет знать, возможно ли починить какие-нибудь счёты, воспользовавшись
спицами и костяшками других счёт (все костяшки и спицы — одинаковые).
Во втором примере первые счёты имели 2 спицы по 2
костяшки на каждой, на первой спице осталась одна костяшка, вторая спица со
всеми костяшками исчезла. Вторые счёты имели три спицы по три костяшки,
на первой спице костяшек не осталось (но сама спица уцелела), на второй
сохранилось две костяшки, на третьей — все три. Первые счёты можно
починить, забрав одну спицу и три костяшки из вторых счёт.
Формат входного файла
Входной файл содержит целые числа n1m1n2m2,
за которыми следует n1 чисел pi — количество оставшихся костяшек
на i − й спице первых счёт,
затем n2 чисел qi — количество оставшихся костяшек
на i − й спице первых счёт.
Если спица отсутствует, вместо соответствующего количества указывается число − 1.
Формат выходного файла
Выходной файл должен содержать единственное целое число:
0, если ни одни счёты починить нельзя;
1, если возможно починить только первые счёты;
2, если возможно починить только вторые счёты;
12, если можно починить либо те, либо другие (не обязательно одновременно).
У Фрэнка Стоктона есть сказка, которая называется «Принцесса или тигр?» В этой сказке один узник должен угадать, в какой из трех комнат находится принцесса, а в какой — тигр. Если он угадает, в какой комнате находится принцесса, то женится на ней, если не угадает, то его (вполне возможно) растерзает тигр.
В некотором царстве правил король. Однажды он тоже прочитал эту сказку.
— В самый раз для моих заключенных! — сказал он своему министру. — Только я не хочу полагаться на случайности. Пусть на дверях каждой комнаты повесят номера, а заключенному будет кое-что сказано о них. Если узник не дурак и способен рассуждать логически, он сумеет сохранить себе жизнь и в придачу заполучить прелестную невесту.
Настал день первого испытания. Потирающий руки король, объявил узнику, что в одной комнате находится принцесса, в другой - тигр, третья комната пуста. После этого стражник произнес два высказывания, в которых говорилось о наличии или отсутствии принцессы или тигра в комнате с некоторым номером.
Поскольку в королевстве принцесс на выданье очень много, а содержание узников обходится недешево, король потихоньку дал указание министру решить две проблемы разом и составить программу для выбора нужной комнаты. Ну а поскольку придворным программистом сейчас являетесь именно вы - кому решать эту проблему?
Поговорив с узником, вы выяснили его приоритеты предпочтений:
1. Если комната с принцессой определяется однозначно - выбираем номер этой комнаты (ура, свадьба).
2. Иначе, если комната с принцессой определяется неоднозначно, а комната с тигром однозначно - выбираем номер комнаты, в которой возможно есть принцесса и точно нет тигра (вдруг повезет).
3. Иначе, если комнаты с принцессой и тигром определяются неоднозначно, а пустая комната однозначно - выбираем номер пустой комнаты (жизнь дороже).
Осталось составить программу...
Формат входного файла
В первой строке входного файла записано первое высказывание - одно из четырех возможных предложений:
Princess is in room
Princess is not in room
Tiger is in room
Tiger is not in room
В конце предложения через пробел указан номер комнаты.
Во второй строке в том же формате записано второе высказывание. Гарантируется, что высказывания истинны, не совпадают и не противоречат друг другу.
Формат выходного файла
Выведите номер комнаты, который следует выбрать узнику в соответствии с приоритетом предпочтений. Если однозначный выбор сделать нельзя - выведите номера всех подходящих комнат через пробел в порядке возрастания.
Ограничения
Номер комнаты - целое число 1, 2 или 3.
Система оценки и описание подзадач
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Подзадача 1: В высказываниях речь идет только о принцессах, баллы: 30.
Подзадача 2: Нет ограничений, баллы: 70.
Пояснения к примерам
В первом примере принцесса в комнате 2 - выбираем эту комнату.
Во втором примере принцессы нет в комнатах 1 и 3, значит она в комнате 2.
В третьем примере принцессы нет в комнате 2, значит она может быть в комнатах 1 и 3, но в первой комнате тигр, поэтому выбираем комнату 3.
Примеры тестов
№
Входной файл (input.txt)
Выходной файл (output.txt)
1
Princess is not in room 3
Princess is in room 2
2
2
Princess is not in room 3
Princess is not in room 1
Сегодня на уроке математики ребята выбирали задания на лето - проекты, которые они будут реализовывать в свободное время. Тимофей опоздал на урок и ему досталась отвергнутая всеми и совершенно на первый взгляд скучная тема "числа-палиндромы".
Анализируя числа, Тимофей заметил, что некоторые из них сохраняют свою "палиндромность" и в двоичной системе счисления. Теперь он хочет совершить настоящий переворот в математике и вывести формулу, связывающую порядковый номер такого числа и само число.
Мы не требуем от вас такого же подвига, просто решите эту задачу!
Напомним, что число является палиндромом, если оно одинаково читается в обоих направлениях. Например, в десятичной системе счисления числа 1, 33, 1001 - палиндромы, а 13, 20 или 1024 - нет. Аналогично, в двоичной системе счисления, числа 1, 100001, 10111101 - палиндромы, а 110, 1010 - нет.
Формат входных данных
В единственной строке записано одно натуральное число n - порядковый номер числа, которое является палиндромом и в десятичной, и в двоичной системах счисления.
Формат выходных данных
Выведете одно натуральное число - соответствующий палиндром (в десятичной системе счисления).
Ограничения
1 ≤ n ≤ 40
Система оценки и описание подзадач
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.
Подзадача 1: 0 ≤ n ≤ 20, баллы: 30. Гарантируется, что ответ не превысит 105
Подзадача 2: нет дополнительных ограничений, баллы: 70. Гарантируется, что ответ не превысит 1013
Пояснения к примерам
Комментарий к первому примеру: Первое натуральное число, запись которого является палиндромом и в десятичной, и в двоичной системах счисления, равно 1. Приведем ряд из семи первых чисел, обладающих таким же свойством: 1 (12), 3 (112), 5 (1012), 7 (1112), 9 (10012), 33 (1000012), 99 (101111012).
