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

Математический кружок

На математический кружок пришли школьники, которые были разбиты на N групп. В i-й группе оказалось X_i школьников. В школе есть M аудиторий, в j-ю аудиторию можно посадить не более, чем Y_j школьников.

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

Формат входных данных

Первая строка входных данных содержит числа N и M, 1<N<M<1000. На второй строчке расположено N чисел X_1, ..., X_N, на третьей строчке расположено M чисел Y_1, ..., Y_M. Числа X_i, Y_j — натуральные, не превосходящие 1000.

Формат выходных данных

В первой строчке программа должна вывести количество групп, которые удастся рассадить по аудиториям. На второй строчке необходимо вывести распределение групп по аудиториям — N чисел, i-е число должно соответствовать номеру аудитории, в которой должна заниматься i-я группа. Нумерация как аудиторий, так и групп ведется с 1. Если i-я группа осталась без аудитории, то i-е число должно быть равно 0. Если допустимых решений несколько, то требуется вывести одно (произвольное) из них.

Пример входных данных

3 4

5 3 4

2 4 2 5

Пример выходных данных

2

0 2 4

 

 

Рифмы

Дан текст (набор слов). Найдите в нем два слова с наилучшей рифмой. Наилучшей будем считать рифму, когда у пары слов совпадает наибольшее число букв с конца.

Формат входных данных

Первая строчка входных данных содержит натуральное число n, 2<=n<=10000. Затем идет n различных строк, каждая из которых содержит одно слово (слова могут состоять из латинских и русских букв в кодировке KOI-8, заглавные и строчные буквы считаются различными).

Формат выходных данных

Программа должна вывести в одной строчке число последних совпадающих букв в наилучшей рифме, затем (через пробел) два слова, образующих эту рифму. Если существует несколько наилучших рифм, то программа должна вывести только одну (любую) пару из них. Если никакие два слова входного текста не рифмуются между собой, программа должна вывести одно число 0.

Примеры Входные данные: 2 олимпиада программирование Выходные данные: 0

Входные данные: 8 зеленый том ученый кругом направо заводит налево говорит Выходные данные: 4 зеленый ученый

 

 

Испорченная сумма

Во время контрольной работы по математике Вася попросил отличника Петю подсказать ему решение задачи, и тот прошептал ему подсказку, представляющую собой арифметическое выражение вида A+B=C, где A, B, C – натуральные числа. При этом Вася не расслышал все цифры чисел, поэтому некоторые цифры этого выражения остались Васе неизвестны. Помогите Васе восстановить это арифметическое выражение.

Формат входных данных

Входные данные представляют собой текстовую строку вида A+B=C, где A, B, C – последовательности, состоящие из цифр и знаков вопроса. Длина входной строки не превосходит 1000 символов.

Формат выходных данных

Программа должна вывести решение – верное равенство, получаемое из исходного уравнения заменой знаков вопроса на цифры. Если таких решений несколько – программа должна вывести одно (любое) из них. Если решений нет, программа должна напечатать строку "impossible".

Примеры

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

?0?+?01=1??

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

009+101=110

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

2+?=1

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

impossible

 

Игра в спички

На столе лежит N спичек. Двое играющих по очереди берут со стола 1, 2 или 5 спичек. Выигрывает тот, кто возьмет последнюю спичку. Определите, какой игрок выигрывает при правильной игре.

Формат входных данных

Программа получает на вход единственное число N, 0<N≤1000.

Формат выходных данных

Программа должна вывести единственное число 1 или 2 – номер игрока, у которого есть выигрышная стратегия.

Пример

Вход     Выход

6         2

 

Даты

Программа получает на вход две строки, содержащие даты, записанные в формате dd.mm.yyyy, где dd – день месяца от 01 до 31, mm – номер месяца от 01 до 12, yyyy – номер года от 0001 до 2999. Программа должна вычислить разность между этими датами (количество дней между ними) и вывести ответ в виде натурального числа. Обе даты корректные, вторая позже первой.

Учтите, что года, чьи номера делятся на 4 и не делятся на 100, а также все года, чьи номера делятся на 400 являются високосными.

Пример Вход             Выход 01.01.0001 1 02.01.0001

Вход             Выход 29.02.2004 366 01.03.2005

 

    

    

Табличный редактор

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

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

Текст внутри ячеек таблицы может располагаться на нескольких строках. Текст состоит только из латинских заглавных и строчных букв, цифр и знаков препинания (за исключением знака -).

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

В отформатированной таблице текст в каждой строке каждой ячейки должен быть отделен от вертикальных разделителей ровно одним пробелом слева и не менее чем одним пробелом справа. Все пробелы между словами являются значимыми. При форматировании разрешается только:

1. изменять количество ведущих и хвостовых пробелов в строках ячеек;

2. добавлять и удалять символы - в горизонтальных разделителях таблицы.

Таблица не содержит пустых столбцов, т.е. в каждом столбце есть по крайней мере одна ячейка с непустым текстом.

Требуется отформатировать заданную таблицу так, чтобы ее ширина (длина строки таблицы) оказалась минимальной.

Исходные данные

Входные данные содержат отредактированную таблицу. Таблица состоит не более чем из 100 строк, длина строки таблицы не превышает 255 символов. Строки не содержат ведущих и хвостовых пробелов. Файл не содержит пустых строк. Последняя строка таблицы завершается символом перехода на новую строку.

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

Требуется вывести в выходной файл отформатированную таблицу. Строки вывода не должны содержать ведущих и хвостовых пробелов. Вывод не должен содержать пустых строк. Исходные данные таковы, что ширина отформатированной таблицы не превысит 255 символов. Последняя строка таблицы должна завершаться символом перехода на новую строку.

Пример входных данных +-----------+-------+---+ |Anatoliy  |Ivanov|179| +-----------+-------+---+ |Sergey| Petrov|57 | +-----------+-------+---+ |Aleksey| Sidorov-| | |  | Vasechkin|| +-----------+-------+---+

Пример выходных данных +----------+-----------+-----+ | Anatoliy | Ivanov | 179 | +----------+-----------+-----+ | Sergey | Petrov | 57 | +----------+-----------+-----+ | Aleksey | Sidorov- | | |     | Vasechkin | | +----------+-----------+-----+

 

Городские кварталы

План города представляет собой прямоугольник, разбитый двумя рядами параллельных улиц на N×M квадратных кварталов. Вертолет вылетает из одного угла города и летит по прямой в противоположный угол города. Определите количество кварталов, над которыми пролетит вертолет. Границы кварталов не относятся к кварталу, то есть считается, что вертолет пролетает над кварталом, если он пролетает над его внутренней точкой.

Формат входных данных

Входные данные содержат два натуральных числа, не превосходящих 10⁹ – количество кварталов в сторонах прямоугольного города.

Формат выходных даных

Программа должна вывести единственное целое число – количество кварталов, над которыми пролетит вертолет.

Пример

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

3               4

2