Задача A. Домой на электричках
Имя входного файла: | a. in |
Имя выходного файла: | a. out |
Максимальное время работы на каждом тесте: | 2 секунды |
Максимальный доступный объем памяти: | 8 мегабайт |
Одна из команд-участниц олимпиады решила вернуться домой на электричках. При этом ребята хотят попасть домой как можно раньше. К сожалению, не все электрички идут от города, где проводится олимпиада, до станции, на которой живут ребята. И, что еще более обидно, не все электрички, которые идут мимо их станции, останавливаются на ней (равно как вообще, электрички останавливаются далеко не на всех станциях, мимо которых они идут).
Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E.
Напишите программу, которая по данному расписанию движения электричек вычисляет минимальное время, за которое ребятам удастся добраться домой.
Формат входных данных
Во входном файле записаны сначала числа N (2 ≤ N ≤ 100) и E (2 ≤ E ≤ N). Затем записано число M (2 ≤ M ≤ 50), обозначающее число рейсов электричек. Далее идет описание M рейсов электрички. Описание каждого рейса электрички начинается с числа Ki (2 ≤ Ki ≤ N) - количества станций, на которых она останавливается, а далее следует Ki пар чисел, первое число каждой пары задает номер станции, второе - время (время выражается целым числом из диапазона от 0 до 109). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении - либо от города, либо к городу.
Формат выходных данных
В выходной файл выведите одно число - минимальное время, когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они добраться не смогут, выведите -1.
Пример
a. in | a. out |
5 3 4 2 35 | 20 |
Задача B. Рамка
Имя входного файла: | b. in |
Имя выходного файла: | b. out |
Максимальное время работы на каждом тесте: | 2 секунды |
Максимальный доступный объем памяти: | 8 мегабайт |
Рассмотрим прямоугольник размером X × Y, из середины которого вырезали прямоугольник размером (X - 2) × (Y - 2). Назовем такую геометрическую фигуру рамкой размера X × Y. На рисунке 1 изображена рамка размера 5 × 6.
Предположим, что у нас имеется неограниченный запас плиток размера A × 1. Рассмотрим следующую задачу: можно ли полностью замостить рамку размера X × Y такими плитками (плитки разрешается поворачивать на 90 градусов). Например, рамку 5 × 6 можно полностью замостить плитками размера 3 × 1 (например, как это сделано на рисунке 2), а плитками размера 4 × 1 - нельзя.
Формат входных данных
Первая строка входного файла содержит два целых числа - X и Y (3 ≤ X, Y, ≤ 106). Вторая строка содержит число N - количество видов плиток, которые следует проанализировать (1 ≤ N ≤ 1000). Третья строка содержит N натуральных чисел, не превышающих 106. Обозначим i-ое число третьей строки входного файла за Ai.
Формат выходных данных
Выведите в выходной файл N строк, i-ая строка должна содержать слово yes, если можно замостить рамку размера X × Y плитками размера Ai × 1 и no в противном случае.
Пример
b. in | b. out |
5 6 2 3 4 | yes no |
Задача C. Умный чертежник
Имя входного файла: | c. in |
Имя выходного файла: | c. out |
Максимальное время работы на каждом тесте: | 2 секунды |
Максимальный доступный объем памяти: | 8 мегабайт |
Фирма Macrohard изобрела новое устройство с целью облегчить труд людей, кому по долгу службы приходится чертить много чертежей, а также школьников, изучающих черчение. Это устройство представляет собой крошечного робота, который умеет ползать по клетчатому листу бумаги. При этом в начале он обязательно должен быть расположен на пересечении линий сетки.
Этот робот умеет выполнять программу, которая может состоять из команд E, W, N, S - переместиться по листу в соседнюю вершину сетки вправо, влево, вперед, назад соответственно. Перемещаясь в соседний узел сетки, робот оставляет за собой ровную линию. При этом по правилам техники безопасности ему категорически запрещается проводить дважды одну и ту же линию, так как при попытке провести линию второй раз, он очень сильно пачкается в своих же собственных чернилах (они очень долго сохнут), и выходит из строя.
При этом, правда, через одну и ту же вершину сетки робот может проходить дважды. Возможно два случая (более толстой линией показано, как мы проезжаем через вершину в первый раз, более тонкой - во второй).
В первом случае мы оба раза проезжаем через вершину "прямо" (будем называть это самопересечением маршрута), а во втором случае - оба раза "поворачиваем" (это будем называть самокасанием).
Разработчики также установили, что в случае самопересечения маршрута робот пачкается в своих чернилах сильнее, чем в случае самокасания, и, если самопересечения встречаются часто, быстро выходит из строя. Поэтому они решили написать для него внутренний оптимизатор программы.
Вам дается программа для робота. Требуется изменить ее так, чтобы узор, получающийся в конце ее работы, был таким же, но при этом при работе робота не возникало самопересечений маршрута.
Формат входных данных
В первой строке входного файла содержится программа для робота. Таким образом, в первой строке входного файла могут встречаться только символы E, W, N, S, а также пробельные символы, которые должны игнорироваться. Общая длина строки (включая пробельные символы) не превышает 200 символов.
Формат выходных данных
В выходной файл вы должны вывести одну строку с оптимизированной программой. Эта строка должна удовлетворять тем же условиям, что и входная строка.
Пример
c. in | c. out |
EENWSSWNN | ENESWSWNN |
Задача D. Три из четырех
Имя входного файла: | d. in |
Имя выходного файла: | d. out |
Максимальное время работы на каждом тесте: | 2 секунды |
Максимальный доступный объем памяти: | 8 мегабайт |
Дано множество точек на плоскости, которое обладает следующим свойством: среди любых четырех из заданных точек три лежат на одной прямой.
Требуется найти ломаную, которая имеет минимальную длину и проходит через все заданные точки.
Формат входных данных
Первая строка входного файла содержит число N - количество точек (3 ≤ N ≤ 100). Следующие N строк содержат координаты точек - пары целых чисел, не превышающих 10000 по абсолютной величине. Никакие две точки не совпадают.
Формат выходных данных
Выведите в выходной файл длину исходной ломаной с точностью не менее 10-3.
Пример
d. in | d. out |
4 0 0 1 0 2 0 1 1 | 3. |
Задача E. Трубочист
Имя входного файла: | e. in |
Имя выходного файла: | e. out |
Максимальное время работы на каждом тесте: | 2 секунды |
Максимальный доступный объем памяти: | 8 мегабайт |
После пожара 1812 года на одной из главных улиц Москвы уцелел лишь один дом. Вернувшиеся после победы жители решили вновь поселиться на этой улице. При этом каждый решил построить себе дом такой же высоты, каким он был у него до пожара.
Дома будут строиться вплотную друг другу, а крыши соседних домов будут соединяться лестницами (длина лестницы равна разнице высот домов), чтобы трубочист мог путешествовать по крышам и чистить трубы.
Когда план постройки домов был уже почти утвержден, свое веское слово сказал Главный Трубочист. Он попросил построить дома так, чтобы суммарная длина лестниц была минимальной. Помогите ему составить такой план постройки домов.
Формат входных данных
Во входном файле записано сначала число N (1 ≤ N ≤ 10000), затем N чисел - высоты домов до пожара (это натуральные числа от 1 до 109), и затем K - номер уцелевшего дома.
Формат выходных данных
В выходной файл выведите высоты домов в таком порядке, чтобы выполнялось требование Главного Трубочиста. Обратите внимание, что K-ый дом (уцелевший) перестраивать не нужно (и следовательно его высота должна остаться прежней).
Пример
e. in | e. out |
5 2 |
Задача F. Квадраты
Имя входного файла: | f. in |
Имя выходного файла: | f. out |
Максимальное время работы на каждом тесте: | 2 секунды |
Максимальный доступный объем памяти: | 8 мегабайт |
Рассмотрим целочисленную решетку размера N × N. Пусть некоторые ее узлы покрашены в белый, а некоторые - в черный цвет. Требуется определить количество квадратов на заданной решетке, то есть квадтаров, вершины которых совпадают с узлами заданной решетки и покрашены в одинаковый цвет.
Например, на решетке размера 4 × 4, изображенной на рисунке 1 такой квадрат один, он показан на рисунке 2.
Формат входных данных
Первая строка входного файла содержит число N - размер решетки (2 × N × 50). Следующие N строк содержат по N символов из множества {"0", "1"} и задают решетку. Если точка с координатами (i, j) покрашена в белый цвет, то j-ый символ i-ой строки есть "0", а если в черный, то "1".
Формат выходных данных
Выведите в выходной файл количество квадратов на решетке из входного файла.
Пример
f. in | f. out |
4 0100 0011 1000 0111 | 1 |
Задача G. Таймер
Имя входного файла: | g. in |
Имя выходного файла: | g. out |
Максимальное время работы на каждом тесте: | 2 секунды |
Максимальный доступный объем памяти: | 8 мегабайт |
Таймер - это часы, которые умеют подавать звуковой сигнал по прошествии некоторого периода времени. Напишите программу, которая определяет, когда должен быть подан звуковой сигнал.
Формат входных данных
В первой строке входного файла записано текущее время в формате ЧЧ:ММ:СС (с ведущими нулями). При этом оно удовлетворяет ограничениям: ЧЧ - от 00 до 23, ММ и СС - от 00 до 60.
Во второй строке записан интервал времени, который должен быть измерян. Интервал записывается в формате Ч:М:С (где Ч, М и С - от 0 до 109, без ведущих нулей). Дополнительно если Ч=0 (или Ч=0 и М=0), то они могут быть опущены. Например, 100:60 на самом деле означает 100 минут 60 секунд, что то же самое, что 101:0 или 1:41:0. А 42 обозначает 42 секунды. 100:100:часов, 100 минут, 100 секунд, что то же самое, что 101:41:40.
Формат выходных данных
В выходной файл выведите в формате ЧЧ:ММ:СС время, во сколько прозвучит звуковой сигнал. При этом если сигнал прозвучит не в текущие сутки, то дальше должна следовать запись +<кол-во> days. Например, если сигнал прозвучит на следующий день - то +1 days.
Примеры
g. in | g. out |
01:01:01 48:0:0 | 01:01:01+2 days |
01:01:01 58:119 | 02:01:00 |
23:59:59 1 | 00:00:00+1 days |
Задача H. Репортаж
Имя входного файла: | h. in |
Имя выходного файла: | h. out |
Максимальное время работы на каждом тесте: | 2 секунды |
Максимальный доступный объем памяти: | 8 мегабайт |
родной город. Одна из местных газет решила написать статью об их походе. Как выяснилось, в процессе похода альпинисты N раз останавливались на ночлег на той или иной высоте hi. Поскольку главный редактор газеты настаивает, чтобы название статьи было "Восхождение и спуск", решено было не упоминать о некоторых днях похода, рассказав лишь о 2k+1 дне, причем если статья будет рассказывать о x1-ом, x2-ом, ..., x2k+1-ом дне (x1 < x2 < ... < x2k+1), то должно выполняться условие h1 < h2 < ... < hk > ... > h2k > h2k+1. Найдите максимальное k, для которого можно соответствующим образом выбрать 2k+1 день.
Формат входных данных
Первая строка входного файла содержит число N - количество дней в походе (1 ≤ N ≤ 100). Следующая строка содержит N целых чисел - h1, h2, ..., h2k+1 (0 ≤ hi ≤ 104).
Формат выходных данных
В первой строке выходного файла выведите число k. Затем выведите 2k+1 число - номера дней, репортаж о которых следует включить в статью, в возрастающем порядке. Если возможных ответов несколько, выведите любой.
Примеры
h. in | h. out |
7 | 2 |
4 | 0 1 |
Задача A. Монстры
Имя входного файла: | monsters. in |
Имя выходного файла: | monsters. out |
Максимальное время работы на каждом тесте: | 2 секунды |
Максимальный объем доступной памяти: | 8 мегабайт |
В одной секретной лаборатории вывели новый вид маленьких монстров, размером чуть больше суслика. В ходе исследований ученые решили поставить следующий эксперимент. В центре комнаты устанавливается прямоугольный стол, поверхность которого разбита на N × M клеток размера 1 × 1. В начальный момент времени на некоторых его клетках располагаются монстры, смотрящие параллельно сторонам стола. По команде экспериментатора монстры начинают двигаться по прямой в ту сторону, в которую они смотрят, доходят до края стола и спрыгивают на пол. Там их собирает лаборант Петя и относит в клетку.
Рисунок 1. Монстры на столе для экспериментов
Поскольку у монстров очень грязные лапки, они оставляют следы на тех клетках, на которых они побывали. Так как отмывать стол придется лаборанту Пете, его заинтересовал вопрос - в каком количестве клеток побывают монстры. Помогите ему решить эту сложную задачу.
Формат входных данных
Первая строка входного файла содержит числа M и N - размеры лабораторного стола (1 ≤ M, N ≤ 106). Следующая строка содержит число K - количество монстров (0 ≤ K ≤ 103). Следующие K строк содержат описания монстров - два целых числа и один символ из множества {N, E, S, W} - начальные координаты и направление соответствующего монстра (соответствие направлений и координат приведено на рисунке 1). Символ отделен от чисел ровно одним пробелом.
Формат выходных данных
В выходной файл выведите единственное число - количество клеток стола, на которых побывают монстры.
Пример
monsters. in | monsters. out |
8 5 4 4 4 S 6 2 W 6 3 N 6 4 S | 13 |
Задача B. Форум
Имя входного файла: | forum. in |
Имя выходного файла: | forum. out |
Максимальное время работы на каждом тесте: | 2 секунды |
Максимальный объем доступной памяти: | 8 мегабайт |
Клуб Юных Хакеров организовал на своем сайте форум. Форум имеет следующую структуру: каждое сообщение либо начинает новую тему, либо является ответом на какое-либо предыдущее сообщение и принадлежит той же теме.
После нескольких месяцев использования своего форума юных хакеров заинтересовал вопрос - какая тема на их форуме наиболее популярна. Помогите им выяснить это.
Формат входных данных
Первая строка входного файла содержит целое число N - количество сообщений в форуме (1 ≤ N ≤ 1000). Следующие строки содержат описание сообщений в хронологическом порядке.
Описание сообщения, которое представляет собой начало новой темы, состоит из трех строк. Первая строка содержит число 0. Вторая строка содержит название темы. Длина названия не превышает 30 символов. Третья строка содержит текст сообщения.
Описание сообщения, которое является ответом на другое сообщение, состоит из двух строк. Первая строка содержит целое число - номер сообщения, ответом на которое оно является. Сообщения нумеруются, начиная с единицы. Ответ всегда появляется позже, чем сообщение, ответом на которое он является. Вторая строка содержит текст сообщения.
Длина всех сообщений не превышает 100 символов.
Формат выходных данных
Выведите в выходной файл название темы, к которой относится наибольшее количество сообщений. Если таких тем несколько, то выведите первую в хронологическом порядке.
Пример
forum. in | forum. out |
7 0 Олимпиада по информатике Скоро третья командная олимпиада? 0 Новая компьютерная игра Вышла новая крутая игра! 1 Она пройдет 24 ноября 1 В Санкт-Петербурге и Барнауле 2 Где найти? 4 Примет участие более 50 команд 6 Интересно, какие будут задачи | Олимпиада по информатике |
Задача C. Три города
Имя входного файла: | three. in |
Имя выходного файла: | three. out |
Максимальное время работы на каждом тесте: | 2 секунды |
Максимальный объем доступной памяти: | 8 мегабайт |
В одном государстве имеется N городов. Некоторые города соединены дорогами, причем для любых двух городов A и B выполняется следующее свойство: существует ровно один способ попасть из города A в город B если можно перемещаться только по дорогам и не разрешается проезжать по одной и той же дороге более одного раза.
Недавно президента этой страны заинтересовал вопрос: какие три города являются наиболее удаленными друг от друга. А именно, назовем взаимной удаленностью друг от друга трех городов A, B и C минимальное количество дорог, которое необходимо использовать, чтобы доехать от A до B, затем от B до C и затем от C до A (при этом разрешается использовать одну и ту же дорогу в различных путешествиях).
Требуется найти три города, для которых взаимная удаленность друг от друга будет максимальной.
Например, для пяти городов, соединенных дорогами так, как это показано на рисунке 1, три наиболее удаленных друг от друга города - это города 1, 2 и 5 (взаимная удаленность равна 2 + 3 + 3 = 8), а для городов на рисунке 2 - это любые три города, выбранные из множества {1, 2, 4, 5} (удаленность 2 + 2 + 2 = 6).
|
|
Рисунок 1. Пример городов, соединенных дорогами, решение - 1, 2, 5. | Рисунок 2. Пример городов, соединенных дорогами, решение неоднозначно. |
Формат входных данных
Первая строка входного файла содержит число N - количество городов (3 ≤ N ≤ 1000). Следующие N строк содержат описания городов. Описание i-го города сначала содержит Ki - количество городов, с которыми он соединен дорогами (1 ≤ Ki < N), а затем Ki чисел - номера городов, с которыми он соединен.
Гарантируется, что входные данные корректны - то есть если есть дорога из города A в город B, то есть и дорога из города B в город A, причем для всех пар городов выполняется свойство, указанное в условии задачи.
Формат выходных данных
Выведите в выходной файл три различных числа - номера трех наиболее удаленных друг от друга городов в произвольном порядке. Если решений несколько, выведите любое из них.
Примеры
three. in | three. out |
5 1 3 1 3 2 3 5 1 4 | 1 2 5 |
5 1 3 1 3 1 3 1 3 | 1 2 4 |
Задача D. Половинное деление
Имя входного файла: | half. in |
Имя выходного файла: | half. out |
Максимальное время работы на каждом тесте: | 2 секунды |
Максимальный объем доступной памяти: | 8 мегабайт |
Рассмотрим выпуклый многоугольник, вершины которого лежат в точках плоскости с целыми координатами. Требуется разбить его на треугольники с вершинами в точках с целыми координатами, каждый из которых имел бы площадь 1/2, либо выяснить, что это сделать невозможно.
Рисунок 1. Разбиение многоугольника на треугольники с площадью 1/2.
Формат входных данных
Первая строка входного файла содержит число N - количество вершин многоугольника (1 ≤ N ≤ 10). Следующие N строк содержат координаты вершин многоугольника в порядке обхода их по часовой стрелке. Все координаты - целые неотрицательные числа, не превышающие 10. Никакие три последовательные вершины многоугольника не лежат на одной прямой.
Формат выходных данных
Если выполнить разбиение указанным образом невозможно, выведите в выходной файл единственное число - 0.
В противном случае выведите несколько строк, содержащих по 6 чисел каждая. Количество строк должно быть равно количеству треугольников в найденном разбиении. Числа в каждой строке должны представлять собой координаты вершин соответствующего треугольника - x1, y1, x2, y2, x3, y3. Площадь каждого треугольника должна быть 1/2. Порядок перечисления треугольников и вершин в каждом из треугольников может быть произвольным. Если допустимых разбиений несколько, выведите любое.
Пример
half. in | half. out |
4 0 0 0 2 2 2 1 0 |
Задача A. Антенна
В связи с развитием сотовой связи в тридесятом царстве компания Змей Горыныч Телеком решила установить антенну, которая бы обеспечивала связью все деревни. Про каждую деревню известны ее координаты (xi, yi). Чтобы качество связи было максимальным, требуется расположить вышку таким образом, чтобы сумма квадратов расстояний от вышки до деревень была минимальна.
Определите координаты точки, в которой следует построить вышку. Например, если имеется три деревни, координаты которых (0, 0), (3, 0) и (3, 6) соответственно, то вышку следует установить в точке (2, 2).
Задача B. Налоговая реформа
После введения в тридесятом царстве новой системы налогового учета, каждый его житель платит налоги по следующей схеме. Определено ] N критических сумм - L1 < L2 < ... < LN и N + 1 процентная ставка P1, P2, ..., PN, PN+1.
Если сумма годового дохода жителя царства не превышает L1 золотых монет, то он платит в казну P1 процентов своего дохода. Если сумма его годового дохода находится в пределах от L1 до L2 золотых монет, то он платит в казну P1 процентов от суммы в L1 монет и затем P2 процентов от суммы L2 - L1.
Вообще, если сумма его дохода X монет удовлетворяет неравенству Li < X < Li+1, то сумма налога, который ему следует уплатить складывается из следующих слагаемых:
- Pi+1 процентов от X - Li Pi процентов от Li - Li-1 ... P1 процентов от L1
Соответственно, если доход превышает LN, то применяется это правило с i = N.
Однако одному князю не понравилось, что жители его автономного княжества уплачивают такой большой налог, и он ввел следующую поправку к закону на территории своего княжества: каждому гражданину возвращается K процентов уплаченной им суммы налога. Правда затем с этой суммы также взымается налог (по той же схеме, независимо от основного налога), который уже не компенсируется подобным образом.
Сумма исходного налога, компенсации и дополнительного налога округляются до целых чисел по стандартным правилам округления.
Например, если N = 3, L1 = 100, L2 = 200, L3 = 300, P1 = 10%, P2 = 20%, P3 = 30%, P4 = 40%, K = 20%, то житель тридесятого царства с доходом в 250 золотых монет сначала уплатит 50 × 0.3 + 100 × 0.2 + 100 × 0.1 = 45 монет налога. Затем ему будет возвращено 45 × 0.2 = 9 монет, с которых должен будет уплатить налог в размере 9 × 0.1 = 0.9 монет, что будет округлено до 1 монеты. Итого будет уплачено+ 1 = 37 монет налога и у жителя останется = 213 монет.
заинтересовалась, сколько зарабатывает ее муж Емеля. Она знает, что после уплаты налогов на домашнее хозяйство остается Y монет. Выясните, каким мог быть доход Емели до уплаты налогов.
Задача C. Найти и заменить
По заказу Ивана Царевича команда программистов под руководством Василисы Премудрой разрабатывает новый пакет программ Яга Офис, основой которого будет новый мощный текстовый редактор.
Одной из важнейших функций редактора является поиск-замена. Задан текст, набор слов, которые требуется найти в тексте и слова, на которые их следует заменить. Ваша задача - помочь разработчикам редактора реализовать эту сложную функцию.
Например, если исходно был задан текст
Жили были дед и баба, и было у них три сына.
и набор замен
дед --> Иван
и --> да
баба --> Марья
сына --> гуся
то результатом замен будет
Жили были Иван да Марья, да было у них три гуся.
Задача D. Странная математика
В связи с реформой образования в тридесятом царстве был введен новый предмет, на котором изучаются различные альтернативные науки. Одной из таких наук является странная математика. Ее основное отличие от обычной математики в том, что числа в ней упорядочены не по возрастанию, а лексикографически, то есть как в словаре (сначала по первой цифре, затем, при равной первой цифре - по второй, и так далее). Кроме того, рассматривается не бесконечное множество натуральных чисел, а лишь первые N чисел. Так, например, если N = 11, то числа в странной математике оказываются упорядочены следующим образом: 1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9.
Помогите ученикам в изучении этой науки - напишите программу, которая по заданному N находит место заданного числа X в порядке, определенном в странной математике. Например, если N = 11 и X = 2, то Ваша программа должна выдать в качестве ответа 4.
Задача E. Пополам
В результате ограбления центрального банка тридесятого царства Кащею Бессмертному и Соловью Разбойнику на двоих досталось N мешков с деньгами весом W1, W2, ..., WN соответственно. Чтобы побыстрее разделить добычу, решено было не открывать мешки, а поделить их таким образом, чтобы каждому досталось одно и то же количество мешков, а также, чтобы общий вес денег у обоих был одинаковым.
Помогите им разделить деньги таким образом или выясните, что это невозможно. Например, если N = 4, W1 = 6, W2 = 4, W3 = 3 и W4 = 1, то возможное поделить мешки следующим образом: одному - первый и четвертый, другому - второй и третий. Если же N = 4, W1 = 6, W2 = 3, W3 = 2 и W4 = 1, то поделить добычу указанным способом невозможно.
Задача A. Треугольник и круг
На плоскости заданы треугольник и круг. Определите, имеется ли у них хотя бы одна общая точка. И треугольник, и круг считаются включающими свою внутренность, то есть если одна фигура целиком лежит внутри другой, то общая точка есть.
Решение этой задачи в Вашей работе должно содержать:
Алгоритм определения наличия общей точки на русском языке. Программу, реализующую описанный алгоритм.Задача B. Суперчемпион
В детском шахматном лагере прошел турнир. В турнире каждый игрок сыграл с каждым ровно одну партию. Каждая партия закончилась либо победой одного из участников, либо вничью.
Петя, приехавший в лагерь уже после турнира, заинтересовался, есть ли в лагере суперчемпион, то есть шахматист, который выиграл все свои партии. Для этого он решил опросить участников турнира. Петя решил задавать им вопросы вида "Как закончилась твоя партия с другим участником?", где вместо слов "другим участником" следует подставить имя одного из участников турнира. Петя хочет задать наименьшее количество вопросов, и выяснить, есть ли в лагере суперчемпион, и если есть, то кто это.
Например, если в лагере три шахматиста, то вне зависимости от ответов достаточно задать три вопроса, если четыре, то может потребоваться четыре вопроса, а если пять, то шесть вопросов.
Разработайте алгоритм, позволяющий Пете найти суперчемпиона, если он есть, задав наименьшее количество вопросов в худшем случае. Напишите программу, эмулирующую поведение Пети. Считайте, что игроки занумерованы числами от 1 до N, и Ваш язык программирования расширен тремя функциями:
function getn: integer; | Возвращает количество участников турнира. Эту функцию следует вызвать один раз в начале программы. |
function gameres(i, j: integer): integer; | Возвращает результат партии между i-ым и j-ым участником. Значение равно 1, если i-ый участник выиграл партию с j-ым, -1, если i-ый участник ее проиграл и 0, если партия закончилась вничью. Следует минимизировать количество вызовов этой функции в худшем случае. |
procedure answer(i: integer); | Эту функцию следует вызвать в конце программы. В качестве параметра следует передать номер игрока, который является суперчемпионом, либо 0, если суперчемпиона нет. |
Решение этой задачи в Вашей работе должно содержать:
При оценке этой задачи основным критерием жюри будет количество заданных вопросов.
Задача C. Странная игра
Определив, кто является суперчемпионом в шахматном турнире, Петя решил предложить ему сыграть в следующую игру. На каждую клетку доски M × N кладется карточка с записанным на ней целым числом. Игроки по очереди берут с доски карточки. Можно брать карточку с клетки только если она является свободной. Карточка называется свободной, если для нее одновременно выполняется два условия:
- сверху от нее нет карточки, то есть клетка, на которой она лежит, принадлежит верхнему ряду или на клетке сверху от нее уже нет карточки; слева от нее нет карточки, то есть клетка, на которой она лежит, принадлежит левому ряду или на клетке слева от нее уже нет карточки.
Игра заканчивается когда на доске не осталось карточек.
После окончания игры каждый игрок подсчитывает сумму чисел на карточках, которые он взял с доски. Выигрывает тот, у кого сумма больше. Петя ходит первым. Выясните, сможет ли он выиграть при любой игре своего противника.
Например, если карточки на поле имеют значения, показанные на рисунке 1, то Петя может выиграть при любой игре противника, а если значения, показанные на рисунке 2, то нет.
Решение этой задачи в Вашей работе должно содержать:
Алгоритм определения победителя в игре на русском языке. Доказательство корректности работы алгоритма. Оценку времени работы Вашего алгоритма и количества необходимой памяти. Программу, реализующую описанный алгоритм.Задача D. Преобразователь
Недавно наши ученые изобрели новый специальный компьютер - преобразователь. Преобразователь работает по программе, представляющей собой конечное множество правил. Каждое правило имеет вид
<левая часть> → <правая часть>
Здесь <левая часть> представляет собой произвольную последовательность больших букв латинского алфавита, а <правая часть> - произвольную последовательность больших и маленьких букв латинского алфавита. Пример правила:
ABC → AbC
Также преобразователь имеет специальный регистр, в котором в каждый момент времени может быть записана произвольная последовательность больших и маленьких букв латинского алфавита. Изначально в регистре записана строка, состоящая из одной буквы "S". Будем называть строку, записанную в этом регистре текущей строкой.
Работа преобразователя осуществляется следующим образом: он произвольным образом выбирает одно из правил, левая часть которого содержится в качестве подстроки в текущей строке, и заменяет некоторое произвольным образом выбранное вхождение левой части этого правила на его правую часть. Отметим, что преобразователь не всегда выбирает первое возможное правило и не всегда заменяет первое вхождение в текущую строку его левой части.
Работа преобразователя заканчивается успешно когда текущая строка состоит только из маленьких букв латинского алфавита. Говорят, что в заданном наборе правил выводится получившаяся при этом текущая строка.
Если текущая строка содержит не только маленькие буквы латинского алфавита, но при этом нельзя применить ни одного правила, то работа преобразователя заканчивается с ошибкой. Также преобразователь может зациклиться.
Программа для преобразователя вместе с алфавитом и начальным символом называется формальной грамматикой, а множество строк, которое выводится из правил этой грамматики называется языком, задаваемым этой грамматикой.
Например, грамматика
S → Aa
A → AA
A → a
A → b
задает язык, состоящий из всех слов, состоящих из букв "a" и "b" и заканчивающихся буквой "a". Например, слово "abba" может быть выведено преобразователем следующим образом:
S => Aa => AAa => Aba => AAba => aAba => abba
Существуют и другие выводы этого слова, например:
S => Aa => AAa => AAAa => aAAa => abAa => abba
Рассмотрим другой пример: грамматика
S → AB
AB → C
A → a
задает пустой язык, то есть язык, в котором не содержится ни одного слова, поскольку применением указанных правил невозможно превратить строку "S" в строку, состоящую только из маленьких букв латинского алфавита.
Интересный случай представляют собой грамматики, в которых в каждом правиле левая часть состоит из одного символа. Такие грамматики называются контекстно-свободными. Так, первая из рассмотренных нами грамматки контекстно-свободная, а вторая - нет.
Рассмотрим теперь следующую грамматику:
S → aSb
S → ab
Эта грамматика задает язык, состоящий из всех слов, в которых сначала идет некоторое количество букв "a", а затем такое же количество букв "b", и только их. Так, слова "ab", "aabb", "aaabbb", и т. д. принадлежат этому языку, а, например, слова "abb" и "aaa" - нет. Этот язык также обозначают {anbn | n ≥ 1}.
Ваше задание в этой задаче - построить грамматику, которая будет задавать язык, состоящий из всех слов, в которых сначала идет некоторое количество букв "a", затем такое же количество букв "b" и затем такое же количество букв "с". Так, слова "abc", "aabbcc", "aaabbbccc", и т. д. должны принадлежать этому языку, а, например, слова "bc", "abbc", "aaccbb", "aabbbccc" - нет. Также этот язык можно обозначить как {anbncn | n ≥ 1}.
Подсказка: грамматика, задающая этот язык не может быть контекстно-свободной, то есть должна содержать правила, в левая часть которых содержит более одного символа. Также помните, что преобразователь может останавливаться с ошибкой (если нет ни одного правила, которое можно применить, и в текущей строке имеются большие буквы) или зацикливаться, в этом случае содержимое регистра не имеет значения и может быть произвольным. Это не влияет на язык, который задает грамматика.
Решение этой задачи в Вашей работе должно содержать:
Дополнительно будет оцениваться грамматика, содержащая только неукорачивающие правила, то есть правила, в которых левая часть не длинее правой.
Также будут поощряться участники, в работах которых будет содержаться формальное доказательство, что все слова описанного языка могут быть выведены из приведенных правил, и никакое другое слово не может быть из них выведено.
Задача E. Кубики
Имя входного файла: | cubes. in |
Имя выходного файла: | cubes. out |
Максимальное время работы на каждом тесте: | 2 секунды |
Максимальный объем используемой памяти: | 8 мегабайт |
Максимальная оценка: | 60 баллов |
Привидение Петя любит играть со своими кубиками. Он любит выкладывать их в ряд и разглядывать свое творение. Однако недавно друзья решили подшутить над Петей и поставили в его игровой комнате зеркало. Ведь всем известно, что привидения не отражаются в зеркале! А кубики отражаются.
Теперь Петя видит перед собой N цветных кубиков, но не знает, какие из этих кубиков нестоящие, а какие - всего лишь отражение в зеркале.
Помогите Пете! Выясните, сколько кубиков может быть у Пети. Петя видит отражение всех кубиков в зеркале и часть кубиков, которая находится перед ним. Часть кубиков может быть позади Пети, их он не видит.
Формат входных данных
Первая строка входного файла содержит число N (1 ≤ N ≤ 100000) и количество различных цветов, в которые могут быть раскрашены кубики - M (1 ≤ M ≤ 100000). Следующая строка содержит N целых чисел от 1 до M - цвета кубиков.
Формат выходных данных
Выведите в выходной файл все такие K, что у Пети может быть K кубиков.
Пример
cubes. in | cubes. out |
6 2 | 3 5 6 |
Возможные в приведенном примере взаимные расположения Пети, кубиков и зеркала приведены на рисунке. Петя смотрит вправо, затененные на рисунке кубики находятся позади Пети и поэтому он их не видит.
Примечание
Решения, работающие только при небольших значениях N и/или M, также будут оцениваться.
Задача F. Квадратики
Имя входного файла: | squares. in |
Имя выходного файла: | squares. out |
Максимальное время работы на каждом тесте: | 2 секунды |
Максимальный объем используемой памяти: | 8 мегабайт |
Максимальная оценка: | 40 баллов |
Недавно ученые Флатландии изобрели новое полезное устройство - машинку по раскрашиванию квадратиков. Эта машина передвигается по плоскости, на которой расположена Флатландия и раскрашивает квадратики размера 1 × 1 с вершинами в точках с целыми координатами в черный цвет.
Скажем, что два квадратика являются соседними, если они имеют общую сторону. Изначально машина находится в центре квадратика с координатами левого нижнего угла (0, 0). Каждую секунду машина раскрашивает квадратик, на котором она находится в черный цвет и перемещается на один из соседних квадратиков. При этом машина никогда повторно не перемещается на квадратик, который она уже закрасила.
Запаса топлива и краски машине хватает на раскраску ровно N квадратиков. После того, как N квадратиков будет закрашено, машина останавливается. Остановить машину до того, как она закрасила ровно N квадратиков невозможно. Несложно видеть, что после закраски в черный цвет некоторых квадратиков некоторые белые квадратики оказываются полностью окружены черными. Скажем, что белый квадратик окружен, если из него нельзя уйти сколь угодно далеко, перемещаясь только по белым квадратикам и каждый раз переходя на соседний квадратик.
Ученые заинтересовались - а можно ли составить такой маршрут для машины по раскрашиванию квадратиков, чтобы ровно K белых квадратиков оказались окружены. При этом они хотят, чтобы в конце своего пути машина оказалась на квадратике, соседнем с тем, с которого она начала движение. Помогите ученым решить эту сложную проблему!
Формат входных данных
Входной файл содержит два целых числа — N и K (1 ≤ N 1 ≤ K ≤ 100000).
Формат выходных данных
Если решение существует, выведите на первой строке выходного файла слово YES. В противном случае выведите NO. Если решение существует, то затем выведите в выходной файл N пар целых чисел - координаты левых нижних углов квадратиков, которые посетит машина по раскрашиванию квадратиков, в порядке из посещения. Разделяйте числа пробелами и/или переводами строки.
Пример
squares. in | squares. out |
16 3 | YES |
Примечание
Решение получит баллы за тесты с ответом NO только, если оно пройдет хотя бы один тест с ответом YES.
Задача G. Путешествие отважного таракана
Имя входного файла: | travel. in |
Имя выходного файла: | travel. out |
Максимальное время работы на каждом тесте: | 2 секунды |
Максимальный объем используемой памяти: | 8 мегабайт |
Максимальная оценка: | 100 баллов |
Петя любит делать из проволоки различные фигурки. Недавно он сделал из проволоки N треугольников и разложил их на столе.
Таракан Вася очень любит путешествовать. Он начинает свое путешествие из некоторой точки внутри некоторого треугольника и затем последовательно перебирается из одного треугольника в другой. При этом он путешествует таким образом, что любые три последовательных треугольника, в которых он побывал, образуют елочку. Три треугольника образуют елочку, если можно сопоставить их вершинам буквы: A, B, C - вершинам первого треугольника, D, E, F - вершинам второго и G, H, I - вершинам третьего, так, что выполняются следующие условия:
- D лежит внутри треугольника ABC; E и F лежат вне треугольника ABC; DE и DF пересекают сторону BC; G лежит внутри треугольника DEF; H и I лежат вне треугольника DEF; GH и GI пересекают сторону EF.
При этом Вася всегда ползет от "вершины" елочки к "основанию", то есть сначала посещает треугольник ABC, затем DEF и затем GHI.
Известно, что Вася будет бегать по треугольникам до тех пор, пока не попадет в треугольник, из которого не может выбраться по своим правилам.
Петя хочет узнать, какое наибольшее количество раз Вася сможет перебежать из треугольника в треугольник, прежде закончит свое путешествие. Помогите ему! Вася может посещать один треугольник несколько раз.
Формат входных данных
Первая строка входного файла содержит число N - количество треугольников (1 ≤ N ≤ 100). Следующие N строк содержат по три пары целых чисел - координаты вершин треугольников (координаты не превышают 105 по абсолютной величине). Никакая вершина треугольника не лежит на стороне другого треугольника (в частности, никакие вершины различных треугольников не совпадают). Все треугольники невырождены.
Формат выходных данных
Выведите в выходной файл максимальное количество перемещений из треугольника в треугольник, которое сможет совершить Вася. Если Васино путешествие может продолжаться бесконечно долго, выведите в выходной файл число -1.
Пример
travel. in | travel. out |
5 2 | 3 |
Задача 1. Песочница
Имя входного файла: | sandbox. in |
Имя выходного файла: | sandbox. out |
Максимальное время работы на каждом тесте: | 2 секунды |
Максимальный объем используемой памяти: | 32 мегабайта |
Максимальная оценка: | 100 баллов |
Прямоугольная детская площадка полностью замощена N плитками. Все плитки прямоугольные, возможно разного размера. Плитки не перекрываются.
На этой площадке решили построить песочницу. Чтобы подготовить место для песочницы, необходимо вынуть не более K плиток таким образом, чтобы песочница занимала все освободившееся пространство, была прямоугольной и имела максимально возможную площадь.
Напишите программу, которая определяет расположение песочницы, удовлетворяющей перечисленным выше требованиям.
Формат входных данных
Введем систему координат так, чтобы начало координат совпадало с одним из углов площадки, а оси координат шли вдоль сторон площадки. В этом случае противоположный угол площадки окажется в точке (X, Y).
Первая строка входного файла содержит два числа X и Y (натуральные числа, не превышающие 10000). Во второй строке заданы числа N и K (1 ≤ K ≤ N ≤ 2000). Следующие N строк файла содержат по четыре целых числа Xi,1, Yi,1, Xi,2, Yi,2, задающих координаты двух противоположных углов плитки (0 ≤ Xi,1 < Xi,2 ≤ X, 0 ≤ Yi,1 < Yi,2 ≤ Y).
Формат выходных данных
В выходной файл выведите координаты двух противоположных углов найденного прямоугольника. Если решений несколько, выведите любое из них.
Пример
Пример входного и выходного файлов для приведенного рисунка.
sandbox. in | sandbox. out |
7 5 8 3 |
Задача 2. Юбилейная
Максимальная оценка: | 100 баллов |
Каждый из расположенных вдоль Н-ского проспекта N фонарных столбов покрашен в один из трех цветов: серый, бурый или малиновый. Главный архитектор хочет, чтобы к юбилею города все столбы имели одинаковый цвет. Он решил составить план перекраски, но знакомиться с имеющейся раскраской у него нет времени. Поэтому план должен быть универсальным, то есть приводить к нужному результату при любой начальной раскраске. План состоит из списка пар столбов. Этот список просматривается последовательно. Если оба столба очередной пары списка имеют одинаковый цвет, то их не трогают, иначе они перекрашиваются в третий цвет (не совпадающий с их цветами).
Помогите главному архитектору составить такой план, по возможности меньшей длины.
Система оценки
В каждом тесте за правильный план вы получаете от половины до полного балла, в зависимости от длины плана. За самый короткий план среди полученных для данного теста вы получите полный балл.
Входные данные
Вам предлагается решить эту задачу для следующих входных данных:
Тест 1 | N = 5 |
Тест 2 | N = 7 |
Тест 3 | N = 8 |
Тест 4 | N = 12 |
Тест 5 | N = 25 |
Тест 6 | N = 32 |
Тест 7 | N = 34 |
Тест 8 | N = 128 |
Тест 9 | N = 253 |
Тест 10 | N = 511 |
Тест 11 | N = 999 |
Тест 12 | N = 1000 |
Формат выходных данных
Решением задачи являются выходные файлы. Первая строка выходного файла должна содержать число N для данного теста. Если задачу решить невозможно, вторая строка должна содержать число 0. В противном случае вторая строка должна содержать число M - количество пар в плане, каждая из следующих M строк должна содержать пару чисел - номера столбов.
Размер выходного файла не должен превышать 100 килобайт.
Примеры
N | выходной файл |
3 | 3 0 |
4 | 4 4 1 2 3 4 1 3 2 4 |
Задача 3. Поезд "Россия"
Имя входного файла: | russia. in |
Имя выходного файла: | russia. out |
Максимальное время работы на каждом тесте: | 2 секунды |
Максимальный объем используемой памяти: | 32 мегабайта |
Максимальная оценка: | 70+30+30 баллов |
Поезд "Москва - Владивосток" следует практически через всю Россию, и потому получил название "Россия". Станции пронумерованы от 1 (Москва) до N (Владивосток). Поезд проезжает станции в порядке возрастания номеров. Во время пути поезда вагоны могут отцепляться и прицепляться. Прицепить вагон можно только в начало или в конец поезда. Отцепить вагон также можно только из начала или конца поезда. Для каждого вагона известна станция, на которой его должны прицепить к составу, и станция, на которой его нужно отцепить.
Требуется составить расписание, определяющее с какой стороны и в каком порядке нужно прицеплять к поезду в процессе следования каждый из вагонов, чтобы всегда иметь возможность их отцепить на нужной станции. Путь поезда начинается на станции номер 1 без вагонов и должен закончиться на станции N без вагонов.
При этом рассмотрите следующие случаи:
Известно, что в составе поезда есть вагон, следующий от начальной станции до конечной. На каждой станции к составу прицепляется не более одного вагона. В поезде может не быть вагона, следующего от первой станции до последней, но при этом на каждой станции прицепляется не более одного вагона. В поезде может не быть вагона, следующего от первой станции до последней, и на каждой станции может быть прицеплено любое число вагонов.Система оценки
Решение задачи для случая 1 оценивается из 70 баллов.
Решение задачи для случая 2 оценивается из + 30) баллов.
Решение задачи для случая 3 оценивается из + 30 + 30) баллов.
Формат входных данных
В первой строке входного файла находится число N - количество станций на маршруте поезда, затем число M - общее число вагонов. Далее идет M пар чисел, i-ая пара задает номера станций, между которыми следует вагон номер i (второе число всегда больше первого). 2 ≤ N ≤ 200, 1 ≤ M ≤ 200.
Формат выходных данных
В выходной файл выведите команды на прицепление и отцепление вагонов в том порядке, в котором они должны выполняться в процессе следования поезда. Каждый вагон должен быть прицеплен к составу ровно один раз и ровно один раз от него отцеплен. Команды задаются в следующем виде:
1 X | Прицепить вагон номер X в начало состава |
2 X | Прицепить вагон номер X в конец состава |
3 X | Отцепить вагон номер X |
Если условиям задачи удовлетворить нельзя, выведите одно число 0.
Примеры
Для первого случая:
russia. in | russia. out |
10 5 2 9 4 9 1 10 3 8 5 8 | 1 3 1 1 1 4 2 2 1 5 3 5 3 4 3 2 3 1 3 3 |
Для второго случая:
russia. in | russia. out |
10 4 1 7 2 8 3 9 4 10 | 1 1 2 2 2 3 2 4 3 1 3 2 3 3 3 4 |
Для третьего случая:
russia. in | russia. out |
5 7 1 3 1 2 2 3 2 4 4 5 3 5 3 5 | 1 1 1 2 3 2 2 4 1 3 3 3 3 1 1 7 1 6 3 4 1 5 3 7 3 6 3 5 |
Примечания
- Если есть вагон, следующий от станции 1, то должна быть команда его прицепления, если есть вагон, следующий до станции N, должна быть команда его отцепления. В случаях 2 и 3 возможны участки, на которых поезд следует вообще без вагонов. Задача будет считаться принятой на проверку, если она прошла тест для первого случая.
Задача 4. Фишки
Имя входного файла: | fishes. in |
Имя выходного файла: | fishes. out |
Максимальное время работы на каждом тесте: | 2 секунды |
Максимальный объем используемой памяти: | 32 мегабайта |
Максимальная оценка: | 100 баллов |
Последовательность клеток занумерована числами от 1 до N. В каждой клетке стоит либо черная, либо белая фишка. Группой назовем набор подряд стоящих фишек одного цвета, ограниченный с обеих сторон фишками другого цвета или концами последовательности. Следует переместить фишки так, чтобы они образовали не более двух групп.
Перемещение фишек описывается с помощью плана обмена, в котором используются понятия операция обмена и шаг. Операция обмена меняет местами две соседние группы фишек. Шаг состоит не более чем из K одновременно выполняемых обменов. Обмены можно совершать одновременно только тогда, когда в них участвуют разные группы. После каждого шага группы одного цвета, оказавшиеся рядом, объединяются. План обменов содержит описания шагов, выполняемых последовательно.
Напишите программу, определяющую план обменов, с помощью которого за наименьшее число шагов получается последовательность, состоящая не более чем из двух групп.
Формат входных данных
В первой строке входного файла записаны числа N и K (1 ≤ N ≤ 100000 и 1 ≤ K ≤ 10000). Исходная расстановка фишек задается в последующих строках, содержащих N чисел (0 или 1), разделенных пробелами или переводами строк. При этом 0 соответствует черной фишке, 1 - белой.
Формат выходных данных
Выходной файл должен содержать описание шагов плана, по одному шагу на строке. Описание шага начинается с числа L - количества обменов на этом шаге. Затем для каждого обмена указывается минимальный номер клетки, в которой стоит фишка, участвующая в этом обмене. Последняя строка плана должна содержать одно число 0.
Примеры
fishes. in | fishes. out |
9 3 | 2 1 6 1 1 0 |
3 1 1 1 0 | 0 |
Примечание
Требуется найти план, содержащий наименьшее число шагов, при этом общее число обменов может быть не минимальным.
Задача 5. Стекло
Имя входного файла: | glass. in |
Имя выходного файла: | glass. out |
Максимальное время работы на каждом тесте: | 2 секунды |
Максимальный объем используемой памяти: | 32 мегабайта |
Максимальная оценка: | 100 баллов |
На столе расположено несколько треугольных осколков стекла. Были выдвинуты следующие предположения:
- все эти осколки принадлежали одному прямоугольному стеклу, которое исходно лежало так, что его стороны были параллельны краям стола; осколки получены в результате удара в некоторую точку стекла, не лежащую на его границе; в момент удара одна из вершин каждого осколка находилась в точке удара; некоторые осколки, возможно, были сдвинуты; стекло может быть восстановлено параллельным переносом осколков, то есть ни один из осколков не был повернут.
Напишите программу, помогающую при этих предположениях полностью восстановить прямоугольное стекло из всех имеющихся осколков или определяющую, что это сделать невозможно.
Формат входных данных
В первой строке входного файла записано число N - количество осколков (1 ≤ N ≤ 2000).
Введем систему координат таким образом, чтобы оси координат были параллельны сторонам стола. В каждой из следующих N строк записано по три пары чисел, задающих текущие координаты вершин осколков. Все координаты - целые числа, по модулю не превосходящие 10000. Все осколки имеют ненулевую площадь.
Формат выходных данных
Если стекло возможно восстановить при указанных предположениях, то в N строках выходного файла выведите координаты вершин осколков после восстановления стекла. Стекло должно быть восстановлено таким образом, чтобы координаты всех его углов были неотрицательны, и один из его углов располагался в начале координат. Перечисление осколков и их вершин должно соответствовать их порядку следования во входном файле.
В случае нескольких решений выведите любое из них.
В случае невозможности восстановить стекло в выходной файл выведите сообщение NO.
Примеры
glass. in | glass. out |
5 | |
4 20 -20 | NO |
Задача 6. Чайнворд
Имя входного файла: | chain. in |
Имя выходного файла: | chain. out |
Максимальное время работы на каждом тесте: | 2 секунды |
Максимальный объем используемой памяти: | 32 мегабайта |
Максимальная оценка: | 100 баллов |
Журналисты газеты The Run Times к каждому номеру готовят чайнворд. Чайнворд - это последовательность клеток, в которые читатель вписывает угаданные слова. При этом каждое следующее слово последовательности должно начинаться с той же буквы, которой заканчивается предыдущее, и эта буква записывается в одной клетке. Одно и то же слово в чайнворде может встречаться несколько раз. Количество клеток в чайнворде называется его длиной. Например, в чайнворд длины 9 можно вписать слова "set", "too" и "olymp" следующим образом: "setoolymp".
Из имеющегося списка слов журналисты должны составить чайнворд, а затем выделить в нем некоторые клетки так, чтобы из прочитанных последовательно слева направо букв в выделенных клетках образовывался лозунг спонсора газеты. Так, в приведенном выше примере чайнворд был составлен специально для лозунга "soly", который можно прочитать, если, например, выделить в чайнворде первую, четвертую, шестую и седьмую клетки.
Для экономии места в газете журналисты хотят составить чайнворд минимальной длины.
Напишите программу, которая по заданному списку английских слов и лозунгу составит такой чайнворд.
Формат входных данных
В первой строке входного файла записан лозунг спонсора, содержащий от одной до 250 букв. Во второй строке записано число N - количество слов, которые можно использовать при составлении чайнворда (1 ≤ N ≤ 1000). В последующих N строках перечисляются различных слова, каждое из которых содержит от двух до 10 букв.
Лозунг и все слова состоят только из строчных латинских букв. Ни одна из строк входного файла не содержит пробелов.
Формат выходных данных
В выходной файл выведите слова, из которых будет составлен чайнворд. Каждое слово должно быть выведено в отдельной строке. Порядок слов определяется порядком их расположения в чайнворде. Если решений несколько, выведите любое из них.
Если из заданных слов требуемый чайнворд составить невозможно, то выходной файл должен содержать только один символ - знак вопроса.
Примеры
chain. in | chain. out |
soly 4 set olymp lye too | set too olymp |
solve 4 set owe evil too | ? |
solve 7 olymp set too pink knot parliament tvs | set too olymp pink knot tvs set |
Тест №9. Олимпиада 2005.
Выберите один правильный ответ. После ответа на все вопросы нажмите кнопку «Готово». |
воспринимаемые человеком или специальными устройствами сведения об окружающем мире и протекающих в нем процессах;
часть знаний, использующихся для ориентирования, активного действия, управления;
сообщения, передающиеся в форме знаков или сигналов;
все, что фиксируется в форме документов.
Примером текстовой информации может служить:музыкальная заставка;
таблица умножения;
иллюстрация в книге;
реплика актеров на спектакле.
Под носителем информации понимают:линии связи для передачи информации;
устройства для хранения данных в персональном компьютере;
среду для записи и хранения информации;
аналого-цифровой преобразователь.
Какой из следующих сигналов является аналоговым:сигнал маяка;
сигнал SOS;
кардиограмма;
сигнал светофора.
Внутреннее представление информации в компьютере:непрерывно;
дискретно;
частично дискретно, частично непрерывно;
и дискретно, и непрерывно одновременно.
В процессе управления "водитель-автомобиль" передачу управляющих воздействий обеспечивает:автомобиль;
двигатель;
багажник;
зеркало заднего вида.
Простейший алфавит, с помощью которого возможно описание множества натуральных чисел, может состоять:из 16 символов;
из двух цифр 0, 1;
ровно из одного символа;
из трех цифр 1, 2, 3.
Абсолютный адрес ячейки в электронных таблицах - это:расстояние от ячейки, содержащей формулу, до ячейки, на которую в ней имеется ссылка;
диапазон ячеек, содержащийся в функции;
адрес, в котором не перенастраиваются номера строк и столбцов;
полный адрес, указывающий номера строки и столбца ячейки.
Принцип программного управления работой компьютера предполагает:возможность выполнения без внешнего вмешательства целой серии команд;
моделирование информационной деятельности человека при правлении компьютером;
необходимость использования операционной системы для синхронной работы аппаратных средств;
использование формул исчисления высказываний для реализации команд в компьютере.
С использованием архиватора Arj лучше всего сжимаются:рисунки;
тексты;
фотографии;
видеофильмы.
