VI Всероссийская командная олимпиада школьников по программированию
Ограничение времени:
2 сек
Входной файл:
numbers.in
Ограничение памяти:
64 Мб
Выходной файл:
numbers.out
Условие
При расследовании дорожно-транспортных происшествий
часто возникают проблемы с розыском автомобилей, водители
которых покинули место происшествия.
Получение свидетельских показаний — непростая работа.
Ситуация осложняется тем, что очень часто свидетели могут
только приблизительно вспомнить номер автомобиля.
При этом с большой вероятностью опрашиваемый может
перепутать порядок цифр или букв в номере.
По полученному от свидетеля происшествия номеру, подсчитайте,
сколько различных номеров может получиться из него перестановкой
букв и/или цифр, а также выведите все такие номера.
Напомним, что автомобильные номера в России состоят из трех
букв и трех цифр, упорядоченных следующим образом: буква,
три цифры, затем две буквы. Фрагмент номера, который идентифицирует
регион, в котором зарегистрирован автомобиль, мы будем игнорировать.
В номере могут использоваться следующие буквы:
"A",
"B",
"C",
"E",
"H",
"K",
"M",
"O",
"P",
"T",
"X",
"Y"
(эти буквы имеют схожие по написанию аналоги как в русском, так и в латинском
алфавите). В этой задаче во входном файле будут использоваться
буквы латинского алфавита.
Формат входного файла
Входной файл содержит одну строку, которая представляет собой корректный
автомобильный номер.
Формат выходного файла
В первой строке выходного файла выведите число k — количество номеров,
которые могут получиться из заданного перестановкой букв и/или цифр.
В последующих k строках выведите все такие номера в произвольном порядке.
Имеется два компьютера с одинаковой производительностью и
N программ, которые необходимо выполнить. Известно, что i-я
программа требует для выполнения на любом из компьютеров Ti секунд.
Программы можно выполнять в любом порядке, но прерывать
однажды запущенную программу нельзя.
Сразу после окончания одной программы можно запускать следующую.
Требуется распределить программы между компьютерами таким
образом, чтобы время на их выполнение оказалось наименьшим.
Например, программы длительностью 7, 10, 3, 5, 6 можно выполнить
за 16 секунд, если на первом компьютере выполнять вторую и четвертую
программу, а на втором — остальные три.
Формат входного файла
Входной файл содержит число N, за которым следуют
числа T1 … TN.
Все числа — целые, разделены пробелами.
Формат выходного файла
Выходной файл должен содержать единственное целое
число — минимальное число секунд на выполнение всех программ.
В 3000 году при раскопках развалин вычислительного центра археологи обнаружили древнюю базу данных,
в которой содержатся даты начала и окончания каких-то исторических событий.
Работу по расшифровке осложняет тот факт,
что древние программисты не могли договориться между собой, в каком порядке
сохранять компоненты даты — день, месяц и год.
Программисту будущего было поручено написать программу, определяющую порядок компонент.
По данным двум датам, состоящим из трёх чисел каждая, требуется найти порядок, в котором следует
записать компоненты обеих дат, чтобы выполнялись следующие условия:
Даты соответствуют правилам календаря:
в году 12 месяцев, количество дней в месяцах равно 31,28,31,30,31,30,31,31,30,31,30,31.
Годы, номера которых делятся на 4, но не делятся на 100, являются високосными. Годы с номерами,
делящимися на 400, также високосные. В високосный год в феврале 29 дней.
Дата начала события должна предшествовать дате окончания. Даты НЕ должны совпадать.
Формат входного файла
Во входном файле содержится шесть чисел.
Первая тройка описывает дату начала события, вторая — дату окончания.
Компоненты обеих дат записаны в одном и том же порядке.
Формат выходного файла
Выведите три числа — номера компонент описывающих день, месяц и год.
Если существует несколько решений, выведите любое из них.
Если решения не существует, выведите -1.
В первом примере даты расшифровываются как: 5 ноября 2005 и 4 октября 2006.
Дана последовательность различных целых чисел A1, A2, …, AN.
Требуется подсчитать количество таких троек (Ai, Aj, Ak), что i ≠ j, i ≠ k, j < k
и Ai нацело делится как на Aj, так и на Ak. Например, в последовательности
1 3 2 4 6 таких троек четыре:
6 3 2, 6 1 3, 6 1 2, 4 1 2.
Рекомендуется рассмотреть частичные решения для следующих случаев
N = 3
4 ≤ N ≤ 100
Формат входного файла
Входной файл содержит число N, за которым следуют N чисел A1A2… AN.
Формат выходного файла
Выходной файл должен соджержать единственное число — количество троек.
Крокодил Гена решил поступить в университет.
Для поступления ему нужно пройти тест, состоящий из Q вопросов.
На каждый из них можно ответить либо "Да", либо "Нет".
Количество баллов, получаемых абитуриентом за тест,
равно количеству данных им правильных ответов.
Все абитуриенты проходят тест с одними и теми же вопросами.
Поскольку Гена не подготовился к тесту, он решил схитрить.
Для этого он подговорил P шушанчиков, чтобы они прошли тест до него.
Каждый шушанчик запомнил, как он отвечал на каждый из вопросов,
и сколько баллов получил.
По этим данным Гена должен определить правильные ответы.
Формат входного файла
В первой строке входного файла содержатся числа PQ.
Далее следует P описаний шушанчиков, по две строки на описание:
В первой строке описываются ответы, данные шушанчиком.
Они задаются строкой длинной Q, состоящей из символов
+ (ASCII 43) или - (ASCII 45)
для ответов "Да" или "Нет" соответственно.
На i-ой позиции строки находится ответ на i-ый вопрос.
Во второй строке содержится целое число — количество баллов.
Формат выходного файла
В выходном файле должна содержаться единственная строка,
состоящая из Q символов + (ASCII 43) или - (ASCII 45) —
правильные ответы к тесту.
Если существует несколько вариантов правильных ответов, вывести любой из них.
Так, во втором примере допустим также ответ -+++.
Ограничения
1 ≤ P ≤ 1000, 1 ≤ Q ≤ 15
Исходные данные таковы, что существует хотя бы один вариант решения.
Даны восемь символов из диапазона от "A" до "Z".
Некоторые из них могут совпадать.
Требуется определить, можно ли расположить эти символы
в вершинах куба таким образом, чтобы на соседних
(т. е. соединенных ребром) вершинах оказались разные символы.
Формат входного файла
Во входном файле находится строка из восьми заглавных латинских букв.
Формат выходного файла
Выходной файл должен содержать целое число 1, если расположение возможно, и 0 (нуль) в противном случае.
Уравнение для пятиклассников представляет собой строку длиной 5 символов.
Второй символ строки является либо знаком '+' (плюс) либо '-' (минус),
четвёртый символ — знак '=' (равно).
Из первого, третьего и пятого символов ровно два являются цифрами из диапазона от
0 до 9, и один — буквой x, обозначающей неизвестное.
Требуется решить данное уравнение относительно x.
Формат входного файла
Входной файл содержит единственную строку — уравнение.
Формат выходного файла
В выходной файл следует вывести единственное целое число — значение x.
Костяшка домино описывается парой цифр от 0 до 6,
например 06 или 33.
Цепочка - это последовательность костяшек, скложенных таким образом,
чтобы соседние цифры на них совпадали. При этом костяшки можно
переворачивать. Например, 15-54-44-46-60 — цепочка.
Дана строка из 2N символов (цифр), задающая N костяшек домино.
Требуется переставить все эти костяшки таким образом,
чтобы они образовали цепочку, либо определить, что это невозможно.
Если существует несколько способов, вывести любой из них.
Формат входного файла
Входной файл содержит строку, задающую костяшки.
Формат выходного файла
В выходном файле должна содержаться единственная строка вида
d1-d2-...-dN, где
d1, d2, …, dN — костяшки из исходного набора,
или NO, если сложить цепочку невозможно.
Любимая девушка одного математика сообщила ему номер своего телефона.
Как истинный представитель своей профессии, он тут же забыл этот номер,
однако успел заметить и запомнить целый ряд соотношений между цифрами.
Дальнейшая судьба математика зависит от того, сможет ли он по этим соотношениям
определить достаточно узкое множество подходящих номеров,
чтобы успеть обзвонить их за приемлемое время.
В городе, где они живут, телефонные номера состоят из 6 цифр
от 0 до 9 в любой комбинации (например, 000999 — правильный телефонный номер).
Между цифрами номера возможны 6 видов отношений:
>, <, =, <=, >=, <>.
Например, 2>5 означает, что вторая цифра в номере больше, чем пятая.
Формат входного файла
В каждой строке входного файла содержится одно отношение,
состоящее из двух различных номеров цифр от 1 до 6,
между которыми стоит один из знаков
>, <, =, <=, >=, <>.
Внутри строки пробелов нет.
Формат выходного файла
В выходном файле должно содержаться единственное число — количество номеров.
Ограничения
Количество отношений находится в диапазоне от 1 до 30.
На шашечной доске размером N × N клеток расположены несколько белых и несколько черных шашек.
Горизонтали доски обозначены числами 1, 2, 3, … снизу вверх. (То есть первая строка входных данных описывает горизонталь доски с номером N, вторая N − 1 и т.д.)
Вертикали обозначены буквами a, b, c, … слева направо.
Клетка, таким образом, задается комбинацией из буквы и числа, например d12.
Ход шашки задается перечислением всех клеток, которые она посетила за этот ход,
включая начальную и конечную.
Обозначения клеток при этом разделяются знаком - (минус). Например: a1-c3-e1.
Шашка может побить (взять) шашку противоположного цвета,
"перепрыгнув" через нее по диагонали в любом направлении.
Если после этого имеется возможность взять еще одну шашку, то это можно сделать на том же ходу.
Требуется определить ход черных, соответствующий наиболее длинному взятию.
Если имеется несколько вариантов хода, выдать любой из них.
Формат входного файла
В первой строке входного файла содержится число N.
В следующих N строках — описание позиции, состоящее из символов '.' (точка),
'O' (заглавная латинская О),'X' (заглавная латинская X).
Они определяют пустую клетку, белую шашку и черную шашку соответственно.
Формат выходного файла
В выходном файле должна содержаться единственная строка вида
L1N1 − L2N2 − … − LKNK, где K ≥ 1,
или Impossible если взятие невозможно.
При выводе на экран буква "А" выглядит следующим образом:
..#..
.#.#.
#...#
#...#
#####
#...#
#...#
Символом '#' (ASCII 35) обозначены чёрные пиксели,
а символом '.' (ASCII 46) — пиксели, не изменяющие цвет при выводе буквы.
Экран размером X × Y заполнен белым цветом.
В различные позиции экрана вывели N букв "А".
Требуется написать программу, которая по изображению на экране
восстановит количество букв и координаты, в которые они выводились.
Левый верхний пиксель экрана имеет координаты (0, 0). Никакая буква не выходит
за границы экрана.
Формат входного файла
Первая строка входного файла содержит числа XY.
Следующие Y строк по X каждая описывают изображение на экране,
причём символом '#' обозначены чёрные пиксели,
а символом '.' — белые.
Формат выходного файла
В выходном файле должно содержаться число букв N, за которым
следует N пар чисел xiyi — координаты верхнего левого угла каждой буквы.
Если существует несколько решений, вывести любое из них.
Марсианские кассовые аппараты распечатывают коды товаров на чеках в виде
строки, состоящей из цифр от '0' до '9' и заглавных латинских букв
от 'A' до 'F'. Все коды имеют длину N символов.
Каждый символ выводится в виде матрицы размером 5 × 7 позиций,
некоторые из которых закрашиваются при печати.
Символы отделяются друг от друга вертикальным рядом неокрашенных позиций.
Матрицы для всех используемых символов приведены ниже
('.' (точка) обозначает неокрашенную, а '#' — закрашенную позицию):
0
.###.
#...#
#..##
#.#.#
##..#
#...#
.###.
1
...##
..#.#
.#..#
#...#
....#
....#
....#
2
.###.
#...#
....#
...#.
..#..
.#...
#####
3
.###.
#...#
....#
.###.
....#
#...#
.###.
4
#...#
#...#
#...#
#...#
.####
....#
....#
5
#####
#....
#....
####.
....#
#...#
.###.
6
.###.
#...#
#....
####.
#...#
#...#
.###.
7
#####
....#
....#
...#.
..#..
.#...
#....
8
.###.
#...#
#...#
.###.
#...#
#...#
.###.
9
.###.
#...#
#...#
.####
....#
#...#
.###.
A
..#..
.#.#.
#...#
#...#
#####
#...#
#...#
B
####.
#...#
#...#
####.
#...#
#...#
####.
C
.###.
#...#
#....
#....
#....
#...#
.###.
D
###..
#..#.
#...#
#...#
#...#
#..#.
###..
E
#####
#....
#....
####.
#....
#....
#####
F
#####
#....
#....
####.
#....
#....
#....
Однажды марсианский кассовый аппарат сломался,
и распечатал один из чеков поверх другого.
В результате изображения товарных кодов перекрылись, так что
в каждом выведенном символе оказались закрашены точки,
соответствующие символам как первого, так и второго кода.
Ваша программа должна восстановить по полученному изображению
две исходные строки товарного кода или определить, что это
изображение не могло быть получено перекрытием двух товарных кодов.
Рекомендуется рассмотреть частичные решения
N = 1
Формат входного файла
Входной файл состоит из 7 строк по 6 × N − 1 символов каждая —
изображение перекрывающихся товарных кодов.
Формат выходного файла
Выходной файл должен содержать две строки длиной по N символов —
восстановленные коды товаров.
Если решения не существует, вывести единственную строку IMPOSSIBLE.
Если решений несколько, вывести любое из них.
Недавно Ассоциация Ловцов Шушанчиков известила крокодила Гену о
приближающемся ежегодном конкурсе по ловле этих зверьков. Гена сразу же стал
собираться в путь к месту соревнований. Первым делом он решил купить новые
чемоданы из крокодиловой кожи. Большой опыт Гены говорит о том, что в
путешествие следует брать не более K плоских чемоданов квадратной формы.
В ассортименте чемоданного магазина имеется неограниченное количество
плоских квадратных чемоданов с любой целочисленной длиной стороны. Стоимость
каждого чемодана в рублях равняется квадрату длины его стороны —
пропорционально площади, обтянутой дорогостоящей кожей.
Ассоциация выдала Гене N рублей на затраты, связанные с поездкой. Однако
бухгалтерия Ассоциации требует, чтобы каждый участник конкурса полностью
потратил выделенные ему средства. Лишних денег у Гены тоже нет, так что ему
необходимо купить чемоданы на сумму ровно N рублей.
Теперь Гену интересует, возможно ли потратить ровно N выданных рублей,
купив не менее одного, но и не более K чемоданов.
Формат входного файла
В единственной строке входного файла содержатся целые числа N и K.
Формат выходного файла
Если интересующая Гену покупка невозможна, то в выходном файле должна
содержаться строка NO. В противном случае в первой строке выходного
файла должно содержаться YES, а во второй строке — длины сторон
чемоданов, которые следует приобрести, записанные через пробел в
произвольном порядке. Если существует несколько решений, вывести любое из
них.
Имеется N кубиков, на гранях которых написаны буквы.
Требуется определить, можно ли из этих кубиков составить данное слово длиной K символов,
и если да, то вывести номера использованных кубиков.
При этом каждый кубик можно использовать только один раз.
Если решений несколько, выдать любое из них.
Формат входного файла
В первой строке входного файла содержится количество кубиков N.
Во второй строке — слово, в следующих N строках — по шесть символов без разделителей,
определяющих буквы на гранях кубиков. (Порядок букв не имеет значения).
Формат выходного файла
Выходной файл должен содержать последовательность из K различных целых чисел от 1 до N,
задающих номера кубиков для каждой буквы слова, начиная с первой.
Если решения нет, выходной файл должен содержать единственное число 0.
В данном двумерном целочисленном массиве a размером N × N
требуется найти три элемента, сумма которых максимальна.
При этом первый элемент должен быть соседним по горизонтали или вертикали со вторым, а второй — с третьим.
Формат входного файла
Входной файл содержит число N, за которым следует N2 чисел
a1,1a1,2
…
a1,N
a2,1a2,2
…
a2,N
…
aN,1aN,2
…
aN,N
— элементы массива.
Формат выходного файла
Выходной файл должен содержать единственное число — максимальную сумму.
При N = 1 следует вывести единственный элемент матрицы.
Недавно в главном офисе картографической службы Ландшафтии случился пожар.
Сгорел архив, хранящий таблицы с перепадами высот в различных регионах страны.
Для восстановления этой информации требуется заново
посчитать перепады высот по сохранившимся картам.
Карта региона представляет собой матрицу размером N x N клеток,
в каждой клетке которой содержится
средняя высота определённого района над уровнем моря.
Максимальным перепадом высот называется
максимальная величина, на которую отличаются средние высоты двух районов,
соседних на карте по горизонтали или по вертикали.
Требуется по карте региона определить максимальный перепад высот в нем.
Формат входного файла
Входной файл содержит число N,
за которым следуют N2 целых чисел — описание карты региона.
Формат выходного файла
Выходной файл должен содержать единственное целое число —
максимальный перепад высот в этом регионе.
Ограничения
1 ≤ N ≤ 100.
Все высоты — целые числа от 0 до 231−1
Московская городская олимпиада по информатике 2003/04 г.
Ограничение времени:
3 сек
Входной файл:
e.in
Ограничение памяти:
200 Мб
Выходной файл:
e.out
Условие
Для игры в "Поле чудес" используется круглый барабан, разделенный на сектора, и стрелка.
В каждом секторе записано некоторое число. В различных секторах может быть записано одно и то же число.
Однажды ведущий решил изменить правила игры.
Он сам стал вращать барабан и называть игроку (который барабана не видел) все числа подряд в том порядке,
в котором на них указывала стрелка в процессе вращения барабана.
Получилось так, что барабан сделал целое число оборотов, то есть последний сектор совпал с первым.
После этого ведущий задал участнику вопрос: какое наименьшее число секторов может быть на барабане?
Напишите программу, отвечающую на этот вопрос.
Формат входного файла
Во входном файле записано сначала число N — количество чисел, которое назвал ведущий.
Затем записано N чисел, на которые указывала стрелка в процессе вращения барабана.
Первое число всегда совпадает с последним (в конце стрелка указывает на тот же сектор, что и в начале).
Формат выходного файла
Выведите минимальное число секторов, которое может быть на барабане.
Ограничения
2 ≤ N ≤ 30000
Числа, записанные в секторах барабана, — натуральные, не превышающие 32000.
Плитка кафеля имеет форму квадрата размером 1 × 1, раскрашенного
в один из цветов, заданных буквами от "a" до "z".
Если замостить квадратную область размером N × N разноцветными плитками,
то могут образоваться горизонтальные или вертикальные одноцветные полосы
длиной N плиток.
По описанию области следует определить цвета горизонтальных и вертикальных полос.
Формат входного файла
В первой строке входного файла содержится число N,
за которым следуют N строк по N символов в каждой — описание области.
Формат выходного файла
Выходной файл должен содержать строку из букв, соответствующих цветам полос, в алфавитном порядке.
Если не образуется ни одной полосы, слеудет вывести строку NO
