Задача A. Уравнение для 5 класса ≡

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Уравнение для пятиклассников представляет собой строку длиной 5 символов. Второй символ строки является либо знаком '+' (плюс) либо '-' (минус), четвёртый символ — знак '=' (равно). Из первого, третьего и пятого символов ровно два являются цифрами из диапазона от 0 до 9, и один — буквой x, обозначающей неизвестное.

Требуется решить данное уравнение относительно x.

Формат входного файла

Входной файл содержит единственную строку — уравнение.

Формат выходного файла

В выходной файл следует вывести единственное целое число — значение x.

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
x+5=7
 
2
2 
3-x=9
 
-6

Задача B. Максимальный перепад ≡

Автор:И. Туфанов, И. Олейников   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:16 Мб
Выходной файл:output.txt  

Условие

Недавно в главном офисе картографической службы Ландшафтии случился пожар. Сгорел архив, хранящий таблицы с перепадами высот в различных регионах страны. Для восстановления этой информации требуется заново посчитать перепады высот по сохранившимся картам.

Карта региона представляет собой матрицу размером N x N клеток, в каждой клетке которой содержится средняя высота определённого района над уровнем моря. Максимальным перепадом высот называется максимальная величина, на которую отличаются средние высоты двух районов, соседних на карте по горизонтали или по вертикали. Требуется по карте региона определить максимальный перепад высот в нем.

Формат входного файла

Входной файл содержит число N, за которым следуют N2 целых чисел — описание карты региона.

Формат выходного файла

Выходной файл должен содержать единственное целое число — максимальный перепад высот в этом регионе.

Ограничения

1 ≤ N ≤ 100. Все высоты — целые числа от 0 до 231−1

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3
1 1 1
1 2 1
1 2 3
 
2

Задача C. Сплошной кафель ≡

Автор:А. Кленин, Н. Кленина   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Плитка кафеля имеет форму квадрата размером 1 × 1, раскрашенного в один из цветов, заданных буквами от "a" до "z".

Если замостить квадратную область размером N × N разноцветными плитками, то могут образоваться горизонтальные или вертикальные одноцветные полосы длиной N плиток.

По описанию области следует определить цвета горизонтальных и вертикальных полос.

Формат входного файла

В первой строке входного файла содержится число N, за которым следуют N строк по N символов в каждой — описание области.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 100

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
4
owww
owow
wwow
oowo
 
NO
2 
3
ibi
ibi
ibi
 
bi

Задача D. Два компьютера ≡

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Имеется два компьютера с одинаковой производительностью и N программ, которые необходимо выполнить. Известно, что i-я программа требует для выполнения на любом из компьютеров Ti секунд. Программы можно выполнять в любом порядке, но прерывать однажды запущенную программу нельзя. Сразу после окончания одной программы можно запускать следующую.

Требуется распределить программы между компьютерами таким образом, чтобы время на их выполнение оказалось наименьшим. Например, программы длительностью 7, 10, 3, 5, 6 можно выполнить за 16 секунд, если на первом компьютере выполнять вторую и четвертую программу, а на втором — остальные три.

Формат входного файла

Входной файл содержит число N, за которым следуют числа T1 … TN. Все числа — целые, разделены пробелами.

Формат выходного файла

Выходной файл должен содержать единственное целое число — минимальное число секунд на выполнение всех программ.

Ограничения

1 ≤ N ≤ 20, 1 ≤ Ti ≤ 1000

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
5 7 10 3 5 6
 
16

Задача E. Hot-keys ≡

Автор:A. Klenin   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

Формат входного файла

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

Формат выходного файла

Выходной файл должен содержать N строк с одинаковыми заголовками, как и во входном файле. В каждом заголовке, которому была назначена какая-то комбинации, перед самым левым вхождением символа из горячей клавиши необходимо добавить символ '&' (ASCII 38).

Ограничения

1 ≤ N ≤ 10, все заголовки имеют длину от 1 до 10 символов и состоят из строчных латинских букв.

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
3
yes
no
cancel
 
&yes
&no
&cancel
2 
4
abc
bca
acb
aaaa
 
&abc
&bca
a&cb
aaaa

Задача F. Судьба математика ≡

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:16 Мб
Выходной файл:output.txt  

Условие

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

В городе, где они живут, телефонные номера состоят из 6 цифр от 0 до 9 в любой комбинации (например, 000999 — правильный телефонный номер).

Между цифрами номера возможны 6 видов отношений: >, <, =, <=, >=, <>. Например, 2>5 означает, что вторая цифра в номере больше, чем пятая.

Формат входного файла

В каждой строке входного файла содержится одно отношение, состоящее из двух различных номеров цифр от 1 до 6, между которыми стоит один из знаков >, <, =, <=, >=, <>. Внутри строки пробелов нет.

Формат выходного файла

В выходном файле должно содержаться единственное число — количество номеров.

Ограничения

Количество отношений находится в диапазоне от 1 до 30.

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
1&lt;2
3=1
3&gt;4
 
12000

Задача G. Новые чемоданы ≡

Автор:И. Бураго   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Недавно Ассоциация Ловцов Шушанчиков известила крокодила Гену о приближающемся ежегодном конкурсе по ловле этих зверьков. Гена сразу же стал собираться в путь к месту соревнований. Первым делом он решил купить новые чемоданы из крокодиловой кожи. Большой опыт Гены говорит о том, что в путешествие следует брать не более K плоских чемоданов квадратной формы.

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

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

Теперь Гену интересует, возможно ли потратить ровно N выданных рублей, купив не менее одного, но и не более K чемоданов.

Формат входного файла

В единственной строке входного файла содержатся целые числа N и K.

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 105, 1 ≤ K ≤ 1000.

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
10 5
 
YES
1 3
2 
842 1
 
NO
3 
98 2
 
YES
7 7

Задача H. Ответы к тесту ≡

Автор:А. Жуплев, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Крокодил Гена решил поступить в университет. Для поступления ему нужно пройти тест, состоящий из Q вопросов. На каждый из них можно ответить либо "Да", либо "Нет". Количество баллов, получаемых абитуриентом за тест, равно количеству данных им правильных ответов. Все абитуриенты проходят тест с одними и теми же вопросами.

Поскольку Гена не подготовился к тесту, он решил схитрить. Для этого он подговорил P шушанчиков, чтобы они прошли тест до него. Каждый шушанчик запомнил, как он отвечал на каждый из вопросов, и сколько баллов получил.

По этим данным Гена должен определить правильные ответы.

Формат входного файла

В первой строке входного файла содержатся числа P Q. Далее следует P описаний шушанчиков, по две строки на описание:

Формат выходного файла

В выходном файле должна содержаться единственная строка, состоящая из Q символов + (ASCII 43) или - (ASCII 45) — правильные ответы к тесту. Если существует несколько вариантов правильных ответов, вывести любой из них. Так, во втором примере допустим также ответ -+++.

Ограничения

1 ≤ P ≤ 1000, 1 ≤ Q ≤ 15

Исходные данные таковы, что существует хотя бы один вариант решения.

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
1 2
+-
0
 
-+
2 
3 4
--++
3
----
1
---+
2
 
+-++

Задача I. Автомобильные номера ≡

Автор:VI Всероссийская командная олимпиада школьников по программированию   Ограничение времени:2 сек
Входной файл:numbers.in   Ограничение памяти:64 Мб
Выходной файл:numbers.out  

Условие

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

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

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

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

В номере могут использоваться следующие буквы: "A", "B", "C", "E", "H", "K", "M", "O", "P", "T", "X", "Y" (эти буквы имеют схожие по написанию аналоги как в русском, так и в латинском алфавите). В этой задаче во входном файле будут использоваться буквы латинского алфавита.

Формат входного файла

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

Формат выходного файла

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

Примеры тестов

№ Входной файл (numbers.in) Выходной файл (numbers.out)
1 
X772KX
 
9
X277XK
X277KX
X727XK
X727KX
X772XK
X772KX
K277XX
K727XX
K772XX

Задача J. Слово из кубиков ≡

Автор:A. Klenin   Ограничение времени:8 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

Имеется N кубиков, на гранях которых написаны буквы. Требуется определить, можно ли из этих кубиков составить данное слово длиной K символов, и если да, то вывести номера использованных кубиков. При этом каждый кубик можно использовать только один раз. Если решений несколько, выдать любое из них.

Формат входного файла

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

Формат выходного файла

Выходной файл должен содержать последовательность из K различных целых чисел от 1 до N, задающих номера кубиков для каждой буквы слова, начиная с первой. Если решения нет, выходной файл должен содержать единственное число 0.

Ограничения

1 ≤ N, K ≤ 12.

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
5
TEST
ABCDAB
TTTTTT
STSTST
CREATE
ERRORS
 
2 5 3 4

Problem K. Very Simple Problem ≡

Author:Far-Eastern Subregional   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

During a preparation of programming contest, its jury is usually faced with many difficult tasks. One of them is to select a problem simple enough to most, if not all, contestants to solve.

The difficulty here lies in diverse meanings of the term "simple" amongst the jury members. So, the jury uses the following procedure to reach a consensus: each member weights each proposed problem with a positive integer "complexity rating" (not necessarily different for different problems). The jury member calls "simplest" those problems that he gave the minimum complexity rating, and "hardest" those problems that he gave the maximum complexity rating.

The ratings received from all jury members are then compared, and a problem is declared as "very simple", if it was called as "simplest" by more than a half of the jury, and was called as "hardest" by nobody.

Input file format

The first line of input file contains integers N and P, the number of jury members and the number of problems. The following N lines contain P integers in range from 0 to 1000 each - the complexity ratings.

Output file format

Output file must contain an ordered list of "very simple" problem numbers, separated by spaces. If there are no such problems, output must contain a single integer 0 (zero).

Constraints

1 ≤ N, P ≤ 100

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
4 4
1 1 1 2
5 900 21 40
10 10 9 10
3 4 3 5

3

Задача L. Числа и музыка ≡

Автор:А. Кленин   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

"Музыкальная" последовательность, состоящая из нулей и единиц, строится следующим образом: на первом шаге последовательность состоит из одной единицы. На каждом следующем шаге к последовательности приписывается ее инверсия, т. е. последовательность, в которой 1 заменены на 0 и наоборот.

Таким образом, на первых 5 шагах последовательность будет выглядеть так:
1
10
1001
10010110
1001011001101001
Требуется по данному числу N определить значение N-го элемента последовательности.

Формат входного файла

Во входном файле содержится целое число N.

Формат выходного файла

В выходном файле должно содержаться число 0 (нуль) либо 1.

Ограничения

1 ≤ N ≤ 1000

Примеры тестов

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
13
 
1
0.690s 0.019s 35