Задачи олимпиады "Муниципальный этап ВсОШ Псковской области по информатике, 9-11 классы"

Задача A. Число

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

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

Входной файл INPUT.TXT содержит натуральное число, не превосходящее 10¹⁰⁰.

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

В выходной файл OUTPUT.TXT выведите то же число, разделяя тройки цифр запятыми.

Примеры

Задача B. Ограбление в парке

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

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

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

В первой строке входного файла INPUT.TXT записаны два числа: L – длина лавочки и K – количество гранитных блоков-ножек. Оба числа натуральные и не превышают 10 000.

Во второй строке записано K различных целых неотрицательных чисел, задающих положение каждой ножки. Положение ножки определяется расстоянием от левого края плиты до левого края ножки (ножка – это куб размером 1×1×1). Ножки перечислены слева направо (то есть начиная с ножки с меньшим расстоянием до левого края)

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

В выходной файл OUTPUT.TXT требуется вывести координаты ножек, которые грабителям нужно оставить. Для каждой ножки нужно выдать ее положение. Ножки следует перечислять слева направо, как они встречаются во входных данных.

Примеры

Примечание

Второй пример соответствует лавочке на рисунке.

Задача C. Пробежка

Хомячок Хома наконец-то получил в подарок долгожданный тренажёр – колесо для бега. Колесо представляет из себя два круга, соединённых N спицами. Спицы пронумерованы числами от 1 до N по часовой стрелке. Соседние спицы расположены на равном расстоянии друг от друга.

Хома начинает пробежку так, что его передние лапки стоят на первой спице. Далее он делает K шагов таким образом, что на переход к следующей спице он тратит одну секунду. Сделав K шагов, он смотрит на какой спице он остановился: если это первая спица, то он завершает пробежку и слазит с колеса, а иначе отдыхает R секунд и повторяет процедуру снова.

Хозяйка Хомы интересуется, сколько времени будет занимать одна такая пробежка?

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

Входной файл INPUT.TXT содержит три целых числа N, K и R по одному в отдельной строке (1 ≤ N, K, R ≤ 2×10⁹).

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

В выходной файл OUTPUT.TXT выведите единственное число – сколько секунд потратит Хома на пробежку.

Пример

Задача D. Прямоугольник

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

Напишите программу, которая поможет Маше определить длины сторон прямоугольника.

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

Во входном файле INPUT.TXT записаны два целых неотрицательных числа K и L – количество узлов и единичных отрезков сетки соответственно. Оба числа не превосходят 10⁹.

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

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

Примеры

№	INPUT.TXT	OUTPUT.TXT	Пояснение
1	2 7	2 3
2	1 4	2 2

Система оценки

Решения, работающие только для K,L ≤ 10³, будут оцениваться в 50 баллов.

Решения, работающие только для K,L ≤ 10⁶, будут оцениваться в 75 баллов.

Задача E. Шахматобокс

Шахматобокс - командная игра, объединяющая два известных вида спорта: шахматы и бокс. В результате соревнований каждая команда получает рейтинговые баллы, которые вычисляются на основании составленного протокола соревнований для данной команды. Протокол представляет собой таблицу из N строк и M столбцов, заполненную символами "+", "-" или "?". Здесь "+" означает число +1, "-" означает число -1, а "?" говорит о том, что данный результат пока не определен в связи с тем, что соревнования еще не закончились. Таким образом, в начале соревнований таблица состоит только из знаков "?", а по мере проведения соревнований знаки "?" заменяются либо на "+", либо на "-". По окончанию соревнований в таблице нет знаков неопределенности "?". После чего рейтинговый балл команды равен разности суммы в строке с наибольшей суммой и суммы в столбце с наименьшей суммой.

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

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

В первой строке входного файла INPUT.TXT записаны целые числа N и M (1 ≤ N, M ≤ 1000) – количество строк и столбцов в протоколе команды соответственно. Далее идут N строк по M символов, содержащие символы "+", "-" и "?".

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

В выходной файл OUTPUT.TXT выведите наибольший возможный рейтинговый балл, который может получить команда, после некоторой замены символов "?" на "+" или "-" в протоколе.

Пример

Пояснение

В примере максимальный рейтинговый балл может быть равен 5 после следующей замены знаков "?":

+-+
+--
--+
+++

Действительно, после такой замены в четвертой строке сумма равна 3, а во втором столбце она равна -2, таким образом получаем рейтинговый балл: 3 - (-2) = 5.

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

Система оценки

Решения, работающие только для 1 ≤ N, M ≤ 100, будут оцениваться в 50 баллов.