2020-08-05
421
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
Мэр города Берлянска решил построить перед своим домом забор из N деревянных досок и нанять лучшего маляра города для его покраски. Поскольку забор должен стать главной достопримечательностью города, лучший дизайнер города для каждой доски назначил тщательно выбранный цвет, в который она должна быть покрашена.
Для покраски главный маляр решил применить новейшую технологию, специально разработанную им для выполнения этого задания. Покраской забора будет заниматься специальный робот, который за один час может покрасить произвольный отрезок забора (набор соседних досок) в некоторый цвет. Поскольку задание должно быть выполнено как можно быстрее, требуется составить программу для робота, которая позволит достичь требуемой раскраски за минимальное время.
Оставить какую-то из досок непокрашенной, естественно, запрещается.
Входные данные
В первой строке входного файла записано число N (1 <= N <= 300), где N количество досок в заборе. Вторая строка содержит строку из N символов, описывающую требуемую покраску забора. Цвета обозначаются заглавными латинскими буквами.
|
|
|
Выходные данные
В первой строке выходного файла выведите M - наименьшее возможное время покраски забора в часах. Следующие M строк должны содержать программу покраски для робота. Каждая строка должна содержать два числа Li и Ri, а также заглавную букву латинского алфавита, задающую цвет Ci и означает, что робот должен покрасить участок забора с Li по Ri доску в цвет Ci (если длина забора N, должно выполняться 1 <= Li <= Ri <= N).
Пример
Ввод
5
ABBCA
Вывод
3
1 5 A
2 3 B
4 4 C
Полоски
ограничение времени на тест: 0.75 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
Картина представляет собой прямоугольник, состоящий из MxN клеток (M строк и N столбцов, 1 <= M, N <= 50). Согласно художественному замыслу, каждая клетка этого прямоугольника должна быть покрашена в один из 26 цветов. Цвета обозначаются соответствующими строчными буквами латинского алфавита.
Работу по созданию этого шедевра постмодернизма поручили интеллектуальному маляру. К сожалению, тот весьма ленив, поэтому ему не хочется раскрашивать одну клетку за другой. Вместо этого маляр приучен рисовать полоски. Полоска бывает горизонтальной или вертикальной и имеет ширину в одну клетку. Когда маляр легким движением руки рисует на картине полоску некоторого цвета, это означает, что все клетки этой полоски окрашиваются в указанный цвет.
Изначально прямоугольник картины бесцветный, поэтому наносимые маляром полоски должны покрыть его весь. Во избежание смешения красок маляру запрещается перекрашивать клетки картины, поэтому полоски могут пересекаться только в случае, когда они имеют одинаковый цвет.
Ваша задача - помочь маляру и определить, как ему выполнить свою нелегкую работу, нарисовав при этом минимальное возможное число полосок.
|
|
|
Входные данные
В первой строке входного файла записаны целые числа M и N - размеры картины. В последующих M строках приводится описание требуемой раскраски. Каждая такая строка состоит из N символов, представляющих собой строчные латинские буквы, обозначающие цвета соответствующих клеток.
Выходные данные
В первой строке выходного файла должно располагаться целое число K - минимальное возможное число полосок, которое придется нарисовать маляру. В последующих K строках должны содержаться указания по рисованию этих полосок - каждая полоска на отдельной строке. Для горизонтальных полосок используется такой формат:
<H начальная_строка начальный_столбец длина цвет>
Здесь начальная_строка и начальный_столбец представляют собой координаты самой левой клетки полоски, цвет - цвет полосы, а длина - число клеток в ней.
Соответственно, запись вида
<V начальная_строка начальный_столбец длина цвет>
обозначает вертикальную полоску заданной длины и цвета, начальная_строка и начальный_столбец представляют собой координаты самой верхней клетки полоски.
Нумерация строк и столбцов начинается с единицы, левая верхняя клетка картины находится в столбце 1, строке 1. Элементы строк выходного файлы, описывающих полоски, должны разделяться пробелами.
Пример
Ввод
3 4
aaaa
abbb
aaac
Вывод
5
V 3 4 1 c
H 3 1 3 a
H 2 2 3 b
H 1 1 4 a
V 2 1 1 a
Винни-путешественник
ограничение времени на тест: 2.5 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
Поговорив с Пятачком о жизни, Винни-Пух опять уснул. Благодаря Вам Винни узнал, что он сможет подарить подарки так, что ни один ослик не обидится. И теперь Пух хочет раздать подарки своим друзьям. Дом Винни находится в точке с координатами (X, Y). (На плоскости введена такая декартова система координат, что ось OX направлена с севера на юг, а ось OY c запада на восток). Когда Винни-Пух выбирал место для своего дома, он даже не рассматривал точки с нецелыми координатами. Свои деревни ослики тоже строили только в точках с целочисленными координатами. К огромному разочарованию Винни, солнце светило с северо-запада так ярко, что Пух не мог идти ни на север, ни на запад, иначе ему слепило глаза. Таким образом, он мог ходить на юг и на восток, а также в любом из промежуточных направлений.
По карте Пух выяснил, где находятся все N деревень Чудесного Леса, в которых живут ослики (1 <= N <= 200). Винни очень щедрый, поэтому, зайдя в i-ую деревню, он дарит каждому из Ai (1 <= Ai <= 10) ее жителей по подарку. Если у Винни не хватит подарков на всех осликов из какой-либо деревни, то он не пойдёт в неё, чтобы никого не обидеть. У Пуха есть всего K подарков, и он хочет обрадовать как можно больше осликов. Он не хочет нести слишком много груза, и просит Вас определить максимальное количество подарков, которое он сможет подарить.
Входные данные
В первой строке записаны числа N, K (K <= 1000000), X, Y, разделенные пробелами. В следующих N строках описаны деревни: в i+1 - ой строке записана тройка чисел (Xi, Yi, Ai), где Xi, Yi - координаты i-ой деревни. Все координаты по модулю не превосходят 100000.
Выходные данные
Выведите единственное число -- ответ на поставленную задачу.
Пример
Ввод
1 1 1 1
2 2 2
Вывод
0
Забор
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
Двое рабочих красят длинный забор. Забор представляет собой последовательность вертикальных досок, пронумерованных числами 1, 2 и т.д. Первый рабочий покрасил доски с A1 по A2 включительно, а второй - с B1 по B2 включительно. Требуется узнать, сколько всего досок покрасили оба рабочих. Возможно, что некоторое количество досок покрашено двумя рабочими.
|
|
|
Входные данные
Во входном файле содержатся натуральные числа A1, A2, B1 и B2 (1 <= A1, A2, B1, B2 <= 1000), записанные через пробел.
Выходные данные
В выходной файл выведите количество досок, покрашенных рабочими.
Пример
Ввод
Пример 1
1 3 4 2
Пример 2
6 4 1 2
Вывод
Пример 1
4
Пример 2
5
Вычеркивания
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
На доске записаны все натуральные числа от 1 до N. Далее M раз повторяется следующая последовательность действий:
* на доске ищется такое число K, которое имеет наибольшее количество натуральных делителей (если таких чисел несколько, то из них выбирается наименьшее);
* найденное число K стирается с доски.
Найдите сумму стертых с доски чисел.
Входные данные
Во входном файле записаны два целых числа N, M (1 <= N <= 1000; 0 <= M <= N) через пробел.
Выходные данные
В выходной файл выведите сумму стертых с доски чисел.
Пример
Ввод
6 3
Вывод
12
Пояснение
В первый раз вычеркивается число 6 (четыре делителя), во второй - число 4 (три делителя), а в третий - число 2 (два делителя)
Анализ строки
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
Найдите количество различных подстрок строки S, которые, будучи перевернутыми, встречаются в строке ровно один раз. Подстрокой называется некоторая идущая подряд последовательность символов данной строки. Две строки называются одинаковыми, если они совпадают (независимо от их местоположения в строке S). При сравнении регистр букв необходимо учитывать.
Входные данные
Во входном файле записана строка S, длина которой не меньше 1 и не превосходит 63 символов. В строке S встречаются только строчные и прописные латинские буквы.
Выходные данные
|
|
|
В выходной файл выведите количество искомых подстрок строки S.
Пример
Ввод
ABCABA
Вывод
3
Банкет
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
После прошедших в Берляндии президентских выборов новый президент Берляндии решил устроить банкет. Решено было пригласить N гостей. Про некоторые пары гостей известно, что они настолько не дружат, что не могут находиться во время банкета в одном зале. Решено провести банкет в двух залах. Ваша задача найти количество распределений гостей между залами (каждого гостя надо определить либо в зал 1, либо в зал 2) с учетом того, что некоторые пары гостей не могут находиться в одном зале.
Входные данные
В первой строке входного файла записаны два целых числа N и M (1 <= N <= 100; 1 <= M <= 1000), где N количество гостей, а M количество пар гостей, которые не могут находиться в одной комнате. Далее в M строках описаны пары гостей двумя числами (их номерами). Все числа в каждой строке разделяются пробелами.
Выходные данные
В выходной файл выведите искомое количество способов без лидирующих нулей.
Пример
Ввод
4 3
1 2
1 3
3 4
Вывод
2
Пояснение
Существует два разных способа рассадить гостей: 1) в первый зал первого и четвертого гостя, а во второй - второго и третьего; 2) в первый зал второго и третьего гостя, а во второй - первого и четвертого.
Взрыватель
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
В некотором лабиринте размером N _ M клеток стоит Взрыватель. Ему известно, где лежит клад, и он хочет до него добраться. За один ход Взрыватель может либо переместиться на соседнюю клетку (т.е. имеющую с текущей общую сторону), если она свободна, либо заложить бомбу на ту клетку, где он находится, либо пропустить ход. Заложенная бомба взрывается через три хода, т.е. после того как Взрыватель сделает еще 3 действия, но не успеет сделать четвертого (под действием понимается и пропуск хода тоже). При взрыве уничтожаются препятствия во всех клетках, имеющих с данной клеткой хотя бы одну общую точку. Взрыв не должен задевать клад или самого Взрывателя. Взрыватель не должен покидать лабиринт. Выведите такую последовательность действий Взрывателя, в соответствии с которой он достигает клада. Если решений несколько, то выведите любое.
Входные данные
В первой строке записаны натуральные числа N и M (1 <= N, M <= 100) через пробел. Далее идет N строк по M символов. Символ '.' означает свободную клетку, 'E' - взрывателя, 'T' - клад, 'X' - препятствие.
Выходные данные
В выходной файл выведите действия взрывателя, при которых он достигает клада ('M' - заложить бомбу, 'T' - пропустить ход, 'S' - пойти вниз, 'W' - пойти влево, 'N' - пойти вверх, 'E' - пойти вправо). Размер выходной последовательности не должен превышать 100000 символов. Если Взрыватель не может дойти до клада, то надо вывести "No solution".
Пример
Ввод
3 5
XEX.X
X.XXT
X.X.X
Вывод
MSSTNENMSWSNEEE
Жизнь насекомых II
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
В комнате, имеющей форму куба со стороной 200 см, находится N мух. Каждая муха заявила, что ей принадлежит та часть комнаты, которая ближе к ней, чем к какой-либо другой мухе. Мудрый Паук, сидящий в углу, заметил, что первой мухе принадлежит A1 см^3, второй - A2 см^3,:, N-ой - AN см^3. Какие числа назвал Мудрый Паук?
Входные данные
В первой строке входного файла записано натуральное число N (1 <= N <= 6) - количество мух в комнате. Далее в N строках содержатся описания их положений на момент сделанного заявления. Каждое положение описывается тройкой целых чисел xi, yi, zi (0 <= xi, yi, zi <= 200) - координатами мухи в пространстве. Никакие две мухи не находятся в одной точке. Система координат введена таким образом, что один угол комнаты имеет координаты (0, 0, 0), а противоположный - (200, 200, 200).
Выходные данные
Выведите N действительных чисел A1, A2,..., AN с двумя знаками после запятой по одному числу в строке.
Пример
Ввод
Пример 1
3
0 100 100
150 100 100
200 100 100
Пример 2
2
0 0 0
100 100 100
Вывод
Пример 1
3000000.00
4000000.00
1000000.00
Пример 2
562500.00
7437500.00
Числа в отрезке
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
Найдите количество целых чисел в заданном отрезке [A, B], которые делятся на сумму своих цифр.
Входные данные
Во входном файле содержатся натуральные числа A и B (1 <= A <= B <= 1000), записанные через пробел.
Выходные данные
В выходной файл выведите единственное число - ответ на поставленную задачу.
Пример
Ввод
Пример 1
5 15
Пример 2
10 20
Вывод
Пример 1
7
Пример 2
4
Заполнение таблицы
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
На карточке нарисовано в строку N клеток (таблица размера 1xN). Таблица последовательно заполняется числами от 1 до N в соответствии со следующим алгоритмом:
* ищется самая длинная последовательность идущих подряд пустых клеток, если таких несколько, то выбирается самая левая последовательность;
* если длина последовательности - нечетное число, то в среднюю клетку последовательности ставится очередное число, иначе число ставится в последнюю клетку первой половины последовательности.
Ваша задача вывести результат после полного заполнения таблицы.
Входные данные
В первой строке входного файла содержится натуральное число (1 <= N <= 100).
Выходные данные
В выходной файл выведите N чисел - последовательность чисел, записанных в таблице после ее полного заполнения через пробел.
Пример
Ввод
9
Вывод
6 2 4 7 1 8 3 5 9
Выборы в Берляндии
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
В Берляндии снова выборы. На пост президента страны претендуют N кандидатов. Выборы будут проводиться по новой, разработанной берляндскими специалистами системе. Каждый из M избирателей предоставляет бюллетень, на котором он расставляет всех N кандидатов в некотором порядке в соответствии со своими предпочтениями. Определение результатов производится по следующей схеме:
1) если некоторый кандидат стоит первым более чем в половине бюллетеней, то он выигрывает выборы;
2) если такого кандидата нет, то ищутся все такие кандидаты, которые стоят первыми в наименьшем количестве бюллетеней (возможно, что таких кандидатов несколько);
3) все найденные кандидаты одновременно вычеркиваются из всех бюллетеней;
4) если в бюллетенях вычеркнуты все кандидаты, то выборы признаются несостоявшимися, иначе переходим к пункту 1.
Ваша задача указать номер победителя на выборах или вывести 0, если выборы не состоялись.
Входные данные
Входной файл содержит несколько наборов входных данных. В первой строке файла записано целое число P (1 <= P <= 20) - количество наборов входных данных во входном файле. Каждый набор начинается строкой, в которой записана пара чисел N, M (1 <= N, M <= 100) через пробел. Далее в M строках записаны перестановки из номеров кандидатов (от 1 до N) через пробел, каждая строка соответствует одному бюллетеню.
Выходные данные
Выведите P строк в выходной файл. В каждой строке выведите ответ для соответствующего набора входных данных - номер победившего кандидата или 0, если выборы не состоялись.
Пример
Ввод
2
3 3
1 3 2
2 3 1
2 3 1
5 5
1 3 2 4 5
3 2 4 1 5
1 4 2 3 5
5 2 3 4 1
3 2 1 5 4
Вывод
2
3
Пояснение
удаляются одновременно кандидаты 2, 4; затем кандидат 5; после чего кандидат 3 становится первым в трех бюллетенях и побеждает на выборах.
Принтер
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
В некотором рекламном агентстве (далее РА) хотят иметь программу, которая по дневному списку заявок на работу принтера выдает S - максимальную прибыль, которую может дать принтер в этот день. Каждая заявка описывается четырьмя целыми числами: B - время поступления заказа (0 <= B <= 10, все времена в задаче отсчитываются в часах с открытия РА), L - необходимое время работы принтера для выполнения заказа (1 <= L <= 10), F - время, к которому заказ должен быть готов (0 <= F <= 10) и C - прибыль, которую РА получит в случае выполнения заказа (0 <= C <= 10000). В каждый момент времени принтер может работать над выполнением только одной заявки. Если принтер начал работать над заявкой, он не останавливается, пока ее не выполнит. Напишите для РА такую программу.
Входные данные
В первой строке входного файла содержится целое число N - количество заявок (1 <= N <= 1000). Далее идут N строк c описаниями заявок - числами B, L, F и C, записанными через пробел.
Выходные данные
В выходной файл выведите число S - максимальную прибыль, которую может дать принтер.
Пример
Ввод
Пример 1
3
0 1 1 10
2 1 3 10
0 2 3 5
Пример 2
3
0 1 1 10
2 1 5 10
0 2 3 5
Вывод
Пример 1
20
Пример 2
25
Счастливые номера
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
Номер из N цифр называется счастливым, если между его цифрами можно расставить знаки '+' и '-' так, что полученное выражение будет равно 0. Не ставить никакого знака между цифрами нельзя. Лидирующие нули в номере допускаются. Сосчитайте S - количество счастливых номеров из N цифр, если можно использовать цифры, большие или равные 0 и меньшие P.
Входные данные
В первой строке записаны целые числа N и P (1 <= N <= 10; 2 <= P <= 10) через пробел.
Выходные данные
В выходной файл выведите число S.
Пример
Ввод
2 10
Вывод
10
Кубики
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
На шахматной доске размера NxN лежит N^2 кубиков так, что нижняя грань каждого кубика совпадает с одной из клеток доски. Шахматная доска расположена таким образом, что термины "север", "юг", "запад", "восток" соответствуют направлениям общепринятым для изображения карт. Каждая грань всех кубиков покрашена в черный или белый цвет. За один ход разрешается выбрать какой-то ряд кубиков (вертикальный или горизонтальный) и провернуть его по часовой стрелке на 90 градусов (ось поворота проходит через центры кубиков выбранного ряда и совпадает с его направлением, т.е. тоже вертикальна или горизонтальна в соответствии с выбранным рядом). Термин "по часовой" обозначает направление поворота, если наблюдать поворот с севера для вертикального ряда и с запада для горизонтального.
Ваша задача вывести последовательность ходов, которая приведет к тому, что все верхние грани кубиков будут черные.
Входные данные
В первой строке входного файла записано натуральное число N (1 <= N <= 30) - размер доски. Далее в N^2 строках описаны квадраты строками из 6 символов. Символ "0" обозначает черный цвет грани, а символ "1" - белый. Строка s1 s2 s3 s4 s5 s6 обозначает, что нижняя грань кубика цвета s1, верхняя - s2, западная - s3, северная - s4, восточная - s5, южная - s6. Кубики перечисляются в порядке с севера на юг, с запада на восток, т.е. сначала перечисляется самый северный ряд в порядке с запада на восток и т.д. вплоть до самого южного ряда.
Выходные данные
В первой строке выходного файла выведите слово YES, если существует искомая последовательность ходов, иначе выведите NO. В случае положительного ответа во второй строке выведите количество ходов Q, а затем в Q строках описания самих ходов. Каждое описание имеет вид: сначала идет символ "H" или "V" в зависимости от того горизонтальный это ряд или вертикальный. Далее в описании через пробел идет число, обозначающее номер ряда. Ряды нумеруются числами от 1 до N в порядке с севера на юг для горизонтальных рядов и с запада на восток для вертикальных. Величина Q не должна превышать 50000. Если решений несколько, выведите любое.
Пример
Ввод
Пример 1
2
101101
001011
110000
000011
Пример 2
2
101101
010011
110000
000011
Вывод
Пример 1
YES
1
H 2
Пример 2
YES
4
H 2
V 2
V 2
V 2
Решаем уравнение
ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.
ввод: input.txt
вывод: output.txt
Даны три числа A, B и M (0<=A,B<M). Найдите такое X (0<=X<M), что A*X имеет остаток B при делении на M.
Входные данные
Даны целые A, B и M (1<=M<=10^9).
Выходные данные
Выведите любое Х удовлетворяющее условию задачи. Если такого не существует -- выведите -1.
Пример
Ввод
3 2 10
Вывод
4
Волшебная игра
ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.
ввод: input.txt
вывод: output.txt
Вася в казино играет в интересную игру.
Сначала он платит вступительный взнос за игру и в обмен на деньги получает право играть. Более того, за уплаченные деньги он сразу получает X очков.
На автомате, в который он играет, есть три кнопки. Когда он нажимает первую, к его очкам добавляется A очков. Когда нажимает вторую - добавляется B. Когда нажимает третью - добавляется C очков.
Ему разрешается сначала несколько раз (или ни разу) нажать третью кнопку, и затем несколько раз (или ни разу) - первую. Нажимать вторую кнопку Васе запрещено.
Если после этого он набрал ровно Y очков, то Вася считается выигравшим, и ему выплачивается премия. Если же Y очков набрать не удается, Вася считается проигравшим, и ничего не получает.
Если Вася выиграл, то считается, что он разгадал одну из волшебных последовательностей нажатий, которые приводят к выигрышу. Он имеет право и дальше играть в эту игру, и искать другие такие последовательности, которые X очков превращают в Y, но ему категорически запрещено использовать одну и ту же выигрышную последовательность более одного раза.
Напишите программу, которая посчитает, сколько различных выигрышных последовательностей существует, то есть сколько раз Вася может выиграть в эту замечательную игру.
Входные данные
Во входном файле записаны числа X, A, B, C, Y. Каждое из этих чисел - целое из диапазона [-10^9, 10^9].
Выходные данные
В выходной файл выведите одно число - количество различный выигрышных последовательностей. Если таких последовательностей бесконечно много, выведите -1.
Пример
Ввод
Test #1
1 1 0 -1 10
Test #2
1 2 4 -2 -20
Test #3
1 1 2 3 10
Вывод
Test #1
-1
Test #2
0
Test #3
4
Сессия все ближе
ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.
ввод: input.txt
вывод: output.txt
Профессор и ассистент собираются принимать экзамен по курсу комбинаторных алгоритмов в группе из n студентов.
Процедура сдачи экзамена такова: сначала студент j (возможно, без подготовки) беседует с ассистентом a_j минут (время беседы зависит от количества пропусков занятий и известно).
Ассистент дает ему заранее подготовленную сложную задачу, для решения которой этому студенту будет предоставлено не менее b_j минут, затем несчастный студент отправляется на расправу к профессору, разговор с которым зависит от предшествующих оценок студента и продлится c_j минут.
Каждый из экзаменаторов в любой момент времени работает только с одним студентом.
Посоветуйте, в какой очередности бригаде экзаменаторов следует принимать студентов, чтобы как можно быстрее закончить экзамен и со спокойной совестью отправиться пить "Кока-Колу"?
Входные данные
Исходные данные задачи - число студентов группы n (1 <= n <= 1000) (первая строка исходного файла) и последующие n строк, содержащих по три целых числа a_i, b_i, c_i (для i = 1..n, все числа от 0 до 60).
Выходные данные
Результат вычислений - минимальная продолжительность экзамена в минутах.
Пример
Ввод
4
5 2 7
4 4 3
7 3 2
5 1 6
Вывод
26
Суперсреднее
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
На уроке информатики преподаватель Дисководов С.Д. дал задание школьнику Андрею написать программу для вычисления среднего геометрического двух действительных чисел. В лекционных записях по математике он обнаружил, что среднее арифметическое F1 двух чисел A, B вычисляется по формуле (A+B)/2, а среднее геометрическое F2 вычисляется по формуле sqrt(A*B).
Так как Андрей одинаково хорошо знает и Pascal, и С++, то он написал решение на обоих языках программирования:
{текст решения на Pascal}
var a, b: real;
ans: real;
begin
assign(input, 'input.txt');
reset(input);
read(a, b);
close(input);
ans:= sqrt(a * b);
assign(output, 'output.txt');
rewrite(output);
writeln(ans: 0: 2);
close(output);
end.
/* решение на C++ */
#include <stdio.h>
#include <math.h>
int main()
{ float a, b, ans;
freopen("input.txt", "rt", stdin);
scanf("%f %f", &a, &b);
ans = sqrt(a * b);
freopen("output.txt", "wt", stdout);
printf("%.2f", ans);
return 0;
}
Андрей настолько быстро справился с заданием, что Дисководов С.Д. решил усложнить задачу. Теперь Андрею для двух действительных чисел A, B надо найти среднее геометрическое чисел F1 и F2, где F1 - среднее арифметическое чисел A и B, а F2 - их среднее геометрическое. Помогите Андрею справиться с новой задачей. Помните, что Андрею достаточно представить решение на одном языке программирования.
Входные данные
Во входном файле в первой строке содержатся два действительных числа A, B (1 <= A, B <= 100), записанные через пробел.
Выходные данные
В выходной файл выведите среднее геометрическое чисел F1 и F2, где F1 - среднее арифметическое чисел A и B, а F2 - их среднее геометрическое. Ответ выведите с двумя знаками после запятой (так же, как в приведенных решениях Андрея).
Пример
Ввод
4 9
Вывод
6.24
Калькулятор
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
Дано выражение вида:
<число><операция><число>=
где <операция> - это одна из операций +, -, *, / (здесь деление понимается как целая часть от деления), <число> - любое натуральное число. Требуется вычислить значение данного выражения.
Входные данные
Во входном файле содержится одна строка вида <число><операция><число>=. Оба числа в строке - натуральные от 1 до 150. Гарантируется, что не менее, чем в половине тестов жюри оба числа будут от 1 до 9.
Выходные данные
Выходной файл должен содержать одно целое число - значение выражения без ведущих нулей.
Пример
Ввод
Пример 1
3-4=
Пример 2
124/25=
Вывод
Пример 1
-1
Пример 2
4
Прибавлятель
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
Некоторое устройство, называемое "Прибавлятель", осуществляет сложение двух неотрицательных целых чисел А и В, одно из которых, число А, хранится на ленте, а второе число В - в специальном буфере. В процессе сложения Прибавлятель анализирует содержимое ленты и буфера и вместо числа А формирует на ленте сумму чисел А и В. В каждый момент времени Прибавлятель работает только с одной из цифр числа на ленте (говорят, что он находится над этой цифрой), выполняя одну из двух команд: "move" - передвинуться на одну цифру (позицию на ленте) влево, и "+" - изменить цифру, над которой он находится в данный момент: 1 изменяется на 2; 2 - на 3; 3 - на 4; 4 - на 5; 5 - на 6; 6 - на 7; 7 - на 8; 8 - на 9; 9 - на 0; 0 - на 1. Если Прибавлятель выполняет команду "move", находясь над самой левой цифрой числа на ленте, то к этому числу слева приписывается цифра 0, и Прибавлятель оказывается над ней. В исходном состоянии на ленте Прибавлятеля записано число А, а сам Прибавлятель находится над некоторой заданной его цифрой. Цифры числа на ленте нумеруются справа, начиная с 1.
Требуется написать программу, формирующую такую кратчайшую последовательность команд Прибавлятеля, после выполнения которой на ленте окажется число А+В.
Входные данные
В первой строке входного файла содержится число, написанное на ленте (не более 250 знаков). Вторая строка содержит число (не более 250 знаков), которое нужно прибавлять к нему, третья строка - позиция Прибавлятеля над числом, считая справа. Отрицательную и нулевую позицию Прибавлятель иметь не может.
Выходные данные
В выходной файл записывается последовательность команд исполнителя. Каждая команда должна располагаться на отдельной строке. Если последовательность команд написать невозможно, нужно вывести сообщение "No solution".
Пример
Ввод
123456712
12
1
Вывод
+
+
move
+
Функция
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
В языке программирования ОГОЛ вызывать функции можно лишь из функций, которые описаны после описания той функции, которая вызывается. В частности, функция не может вызывать себя.
Программист Петя спроектировал программу, которая должна быть написана на этом языке. В частности, в проекте указано, какие функции вызываются из какой функции. Для удобства Петя пронумеровал все функции числами от 1 до N.
Требуется написать программу, которая определяет, в каком порядке функции должны быть описаны в программе на языке ОГОЛ.
Входные данные
В первой строке входного файла содержится число N (1 <= N <= 100) - количество функций, которые должны быть в программе. Далее идут N строк, причем i-я строка содержит описание функций, которые должны вызываться из i-й функции. Это описание сначала содержит число - количество функций, которые вызываются из данной функции, а затем номера вызываемых функций (одна и та же функция может вызываться из одной функции несколько раз).
Выходные данные
Необходимо вывести в строку через пробел номера функций в том порядке, в каком они должны быть описаны в программе. Если написать такую программу на языке ОГОЛ невозможно, в выходной файл нужно поместить одно число 0. Если решений несколько, то выведите любое.
Пример
Ввод
Пример 1
3
0
4 1 1 3 1
1 1
Пример 2
2
1 2
1 1
Вывод
Пример 1
1 3 2
Пример 2
0
Кладотолкатель
ограничение времени на тест: 0.75 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
Некий лабиринт представляет собой матрицу M x N, некоторые ячейки которой пустые, а остальные заполнены камнями. В одной из пустых клеток находится клад, а в другой - кладоискатель. Кладоискатель и клад не могут находиться в ячейках, заполненных камнями, за пределами лабиринта, а также одновременно в одной и той же ячейке. Кладоискатель может передвигаться в соседнюю ячейку (соседними считаются ячейки, граничащие по стороне), а также передвигать клад следующим образом: нужно встать в соседнюю к кладу ячейку и толкнуть его. При этом клад передвинется на соседнюю ячейку в направлении, заданном толчком, а кладоискатель переместится в ячейку, где только что находился клад.
Требуется написать программу, которая определяет последовательность толчков и передвижений кладоискателя, с помощью которой клад можно передвинуть к выходу (выход находится в пустой ячейке). Так как клад очень тяжелый, количество толчков должно быть минимальным. При наличии нескольких решений программа должна выводить то из них, которое требует наименьшего количества перемещений.
Входные данные
В первой строке входного файла записаны числа M и N (2 <= M, N <= 40) через пробел. Последующие M строк содержат описание лабиринта. Каждая строка состоит из N символов, описывающих ячейки лабиринта: заполненная камнями ячейка обозначается латинской буквой 'X', пустая ячейка обозначается символом '.' (ASCII код 46), начальная позиция кладоискателя - буквой 'Y', начальная позиция клада - латинской буквой 'B', выход - латинской буквой 'T'.
Выходные данные
Если решения не существует, то файл должен содержать слово 'NO'. Иначе в первой строке выходного файла должно содержаться слово 'YES', а во второй строке - последовательность символов, определяющая действия кладоискателя, в частности, символы 'w', 'e', 'n', 's' обозначают передвижения кладоискателя на запад, восток, север и юг соответственно, а символы 'W', 'E', 'N', 'S' обозначают толчки кладоискателя в соответствующих направлениях. Если решений несколько, то выведите любое.
Пример
Ввод
3 3
..Y
.B.
TXX
Вывод
YES
sWnwS
Прямоугольники
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
На плоскости нарисовали красный прямоугольник. Затем нарисовали N (0<N<100) зеленых прямоугольников (зеленые прямоугольники могут пересекаться между собой, а также с красным прямоугольником). Стороны всех прямоугольников (как красного, так и зеленых) параллельны осям координат.
Требуется написать программу, определяющую набор прямоугольников со сторонами, параллельными осям координат, и удовлетворяющих следующим условиям:
прямоугольники полностью покрывают часть красного прямоугольника, которая не покрыта зелеными прямоугольниками;
прямоугольники не пересекаются между собой и с зелеными прямоугольниками (касаться сторонами они при этом могут);
прямоугольники лежат внутри красного прямоугольника;
количество прямоугольников в наборе не превышает величины (2N+1)^2.
Входные данные
В первой строке входного файла содержатся 4 числа - координаты левого нижнего и правого верхнего углов красного прямоугольника. Во второй строке задано число N. В каждой из последующих N строк располагаются четверки чисел, задающих соответственно координаты левых нижних и правых верхних углов зеленых прямоугольников. Все координаты в строках целые, разделены пробелом и не превосходят по абсолютному значению 2000.
Выходные данные
Выходной файл должен содержать в первой строке число M - количество прямоугольников в искомом наборе. В каждой из последующих М строк должны располагаться четверки чисел, задающих соответственно координаты левых нижних и правых верхних углов прямоугольников набора. Все координаты в строках разделены пробелом. Если решений несколько, то выведите любое.
Пример
Ввод
5 5 10 10
2
2 2 3 10
2 7 20 8
Вывод
3
5 5 10 7
5 8 9 10
9 8 10 10
267. О, счастливчик!
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
В круге стоят N человек. Все люди пронумерованы по часовой стрелке числами от 1 до N. С помощью считалки, в которой P слов, они хотят выбрать счастливчика. Считалка начинается с человека, стоящего в позиции 1, счет ведется по часовой стрелке, счастливчиком объявляется тот, на ком она закончится, т.е. произнесется P-ое слово. В какую позицию Вам следует встать, чтобы счастливчиком оказались Вы?
Входные данные
Во входном файле содержатся два натуральных числа N, P (1 <= N <= 100, 1 <= P <= 1000), разделенных пробелом.
Выходные данные
Выведите в выходной файл номер позиции, в которую Вам следует встать, чтобы Вы оказались счастливчиком.
Пример
Ввод
5 15
Вывод
5
