#1091

Трехмерные ладьи

Темы: [Битовые операции]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2006, Задача I ]

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

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

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

В первой строке входного файла записано натуральное число N (1≤N≤1000), задающее размеры игрового куба, и количество ладей K (0≤K≤10⁶). Далее записано K троек чисел, задающих координаты ладей (координата по каждому измерению — натуральное число от 1 до N).

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

Выведите в выходной файл слово YES, если эти ладьи бьют весь куб, и слово NO в противном случае. В случае NO выведите во второй строке координаты какой-нибудь клетки, которая не бьется ни одной из ладей.

Примеры

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

2 2
1 1 1
2 2 2

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

YES

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

2 2
1 1 1
1 1 2

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

NO
2 2 1

#1094

Переливания

Темы: [Битовые операции] [Целые числа]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2006, Задача L ]

Есть три сосуда с водой. В одном из них A миллилитров воды, в другом — B миллилитров, в третьем — C. Разрешается следующая операция. Можно перелить воду из одного сосуда в другой так, чтобы в том сосуде, в который мы переливаем, количество воды после переливания было в два раза больше, чем до переливания. То есть, если до переливания в сосудах было A, B и C миллилитров соответственно, и мы переливаем, например, из второго сосуда в третий, то после переливания в сосудах должно оказаться A, B–C, 2С миллилитров соответственно (такое переливание можно делать только при условии, когда B≥C). Эту операцию можно повторять не более 10000 раз.

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

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

Во входном файле записаны неотрицательные целые числа A, B, C — количество воды в каждом из сосудов изначально. Числа A, B, C не превышают 10¹⁸.

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

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

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

Примеры

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

1 2 10

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

2
3 1
2 1

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

0 1 0

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

#1096

Дробное число

Темы: [Вещественные числа]

Источники: [ Личные олимпиады, Олимпиады сайта, 2009, Задача Q ]

Дана обыкновенная дробь N/M. Представьте ее в виде десятичной дроби и выведите первую цифру после запятой.

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

Вводятся два натуральных числа N и M, не превосходящие 1000.

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

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

Примеры

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

1 2

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

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

4 4

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

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

1000 3

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

#1124

Максимальный подпалиндром

Темы: [Динамическое программирование по подстрокам] [Строки]

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 1999, Задача B ]

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

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

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

Во входном файле находится строка длиной не более 100 символов, состоящая из заглавных букв латинского алфавита.

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

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

Примеры

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

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

1
N

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

ABCDEF

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

1
A

#1140

HTHL

Темы: [Строки]

Источники: [ Командные олимпиады, Командные чемпионаты школьников Санкт-Петербурга по программированию, 2000, Задача E ]

Клуб Юных Хакеров разработал новый язык для web-страниц. В этом языке у тегов нет атрибутов, и запрещается использовать пробелы в написании тега. А именно: назовем открывающим тегом языка HTHL (Hyper Text Hackers' Language) следующую последовательность:

"<", имя тега, ">"

а закрывающим тегом последовательность

"</", имя тега, ">"

где имя тега – любая последовательность латинских букв и цифр, не длиннее 100 символов. Рассмотрим примеры тегов языка HTHL:

 <par> <hthl> <hacker2> <super>

 </hthl> </hyper> </down>

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

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

На первой строке входного файла находится число K (0 ≤ K ≤ 100) — количество имен тегов, которые не разрывают слово. Следующие K строк содержат имена этих тегов.

На следующей строке находится N — количество строк в странице HTHL, в которой следует осуществлять поиск (1 ≤ N ≤ 100). Следующие N строк содержат текст страницы, все строки не длиннее 250 символов.

Следующая строка содержит число M — количество запросов (1 ≤ M ≤ 100). Затем следует M строк — слова, поиск которых следует осуществить в документе. Словом является любая последовательность латинских букв и цифр не длиннее 250 символов.

Гарантируется, что страница HTHL является корректной, т.е. все символы "<", "/" и ">" используются только в тегах, все теги записаны корректно.

Различие между большими и маленькими буквами следует игнорировать.

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

Выведите в выходной файл M строк — для каждого слова выведите номер строки в странице, на которой оно впервые встречается, либо 0, если число не встречается на странице (Нумерация строк идет с 1).

Примеры

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

0
1
this page is very simple
5
this
page
is
very
simple

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