Задача A. Котенок Гав и сосиски

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

Условие

В распоряжение котенка Гава и щенка Шарика поступила лента из N сосисок. Они договорились есть ее с разных концов до тех пор, пока не встретятся. Гав съедает VGav сосисок в секунду, а Шарик — VSharik сосисок в секунду.

Напишите программу, которая вычислит количество сосисок, целиком съеденных каждым зверем.

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

Входной файл содержит три целых числа: N — количество сосисок, VGav — скорость Гава, VSharik — скорость Шарика.

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

Выходной файл должен содержать два числа: сначала количество сосисок, целиком съеденных Гавом, а затем количество сосисок, целиком съеденных Шариком.

Ограничения

1 ≤ N ≤ 108; 1 ≤ VGav, VSharik ≤ 10

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

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

Задача B. Настройка гитары

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

Условие

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

Первая струна настраивается по камертону. Каждая следующая струна настраивается по предыдущей, а именно:

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

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

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

i-ый символ входной строки показывает как звучит (i+1)-ая струна относительно i-ой, а именно:

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

В выходном файле должна содержаться строка из 5 символов, описывающая действия, которые требуется произвести для настройки гитары. В i-ой позиции строке должен содержаться символ, описывающий действие над (i+1)-ой струной:

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

Входной файл (input.txt) Выходной файл (output.txt)
1
=====
*****
2
=<=<=
*++++
3
>==<=
---??

Задача C. Древнее сложение

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

Условие

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

Каждая цифра представлялась с помощью трёх символов, имевших значения:

Комбинация этих символов являлась корректной записью цифры, если: Например, цифра три записывалась как ..., а цифра двенадцать — как ..||.

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

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

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

Символ «ракушка» обозначается '*' (ASCII 42), «точка» — '.' (ASCII 46), «черта» — '|' (ASCII 124). Разряды отделяются друг от друга пробелом (ASCII 32).

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

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

Ограничения

Оба числа не превосходят 109.

Строки во входном файле содержат от 1 до 255 символов.

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

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

Задача D. Индикатор загрузки

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

Условие

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

Индикатор загрузки представляет собой поле n × m пикселей, отражающее состояние загрузки некоторого файла размером n ⋅ m байт. Все пиксели индикатора нумеруются от 1 до n ⋅ m слева направо сверху вниз, при этом пиксель c номером i окрашен в чёрный цвет, если i-й по счёту байт файла уже загружен, и в белый цвет — в противном случае.

Для ускорения загрузки файл был разделён на равные фрагменты по b байт, каждый из которых загружается одновременно. Байты внутри одного фрагмента загружаются последовательно от начала к концу.

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

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

В первой строке входного файла находятся целые числа n m b. Вторая строка содержит четыре числа r1 c1 r2 c2 — координаты видимой части индикатора. Следующие r2 − r1 + 1 строк по c2 − c1 + 1 символов каждая описывают видимую часть изображения: строки с r1-й по r2-ю, столбцы с c1-го по c2-й. Символ '=' (ASCII 61) обозначает чёрный пиксель, символ '.' (ASCII 46) — белый.

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

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

Ограничения

1 ≤ n, m ≤ 104, 1 ≤ b ≤ n ⋅ m, n ⋅ m делится на b нацело.

1 ≤ r1 ≤ r2 ≤ n, 1 ≤ c1 ≤ c2 ≤ m, r2 − r1 ≤ 100, c2 − c1 ≤ 100.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5 7 5
2 3 2 3
.
0 28
2
5 7 5
1 5 3 7
.==
==.
..=
21 21

Задача E. Нарезка фантиков

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

Условие

Для производства конфетных фантиков изготовлена длинная узкая лента с напечатанными на ней картинками. Длина каждой картинки — L мм, расстояние между двумя соседними картинками — d мм, расстояние от начала ленты до первой картинки — a мм.

Нужно получить N фантиков длиной W мм каждый. Аппарат по производству фантиков работает так: сперва от начала ленты отрезается и выбрасывается кусок длиной x мм. Затем от начала ленты один за другим отрезаются фантики длиной W мм каждый.

Каким должно быть x, чтобы на каждом фантике была целиком расположена ровно одна картинка? Картинки, попадающие на фантик только частично, не считаются.

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

Входной файл содержит целые числа L d a N W.

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

Выходной файл должен содержать целое число x.

Число x должно удовлетворять неравенству 0 ≤ x < L + d.

Если существует несколько решений, выведите любое из них.

Ограничения

1 ≤ N, L, W, d ≤ 1000.

0 ≤ a < L+d.

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

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

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

Задача F. Золотая середина

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

Условие

Центральным элементом набора из k чисел называется такой элемент, который после сортировки набора будет занимать в нём центральную позицию (то есть позицию номер k / 2, считая с единицы).

Числа добавляются в изначально пустой набор в заданном порядке. Требуется определить значения центрального элемента после добавления каждого числа.

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

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

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

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

Ограничения

1 ≤ n ≤ 106,  − 109 ≤ ai ≤ 109.

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

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

Задача G. Оригами

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

Условие

Складывание фигуры начинается с квадратного листа бумаги, лежащего на специальной (также квадратной) учебной доске для оригами. Доска размечена на n × n клеток, стороны которых параллельны её краям. Через все клетки доски проведены диагонали двух типов: пересекающие клетки сверху вниз слева направо (\) и справа налево (/). Две диагонали, соединяющие противоположные углы доски, называются главными.

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

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

Ниже показан процесс складывания фигуры по схеме, приведённой в примере 2.

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

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

Каждый сгиб задаётся положением диагонали, вдоль которой он должен быть произведён, и состоит из трёх компонент.

  1. Тип диагонали — символ '/' (ASCII 47) или '\' (ASCII 92).
  2. Направление сгиба листа — символ 'u' (ASCII 117) для сгиба вниз или 'l' (ASCII 108) для сгиба вверх; однозначно определяет положение относительно главной диагонали.
  3. Номер диагонали — целое число от 1 до n. Диагонали каждого типа, расположенные по одну сторону от главной, нумеруются по возрастанию от угла доски к главной диагонали.

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

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

Ограничения

1 ≤ n ≤ 100, 0 ≤ m ≤ 4 n − 2.

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2
\u1/u3
~~^
~,#
,##
2
4 3
/l3\u2/u3
~~^~
~,#&gt;
,##~
#'~~

Задача H. Модель Изинга

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

Условие

Модель Изинга используется в физике для описания твердого тела. Она использует представление кристаллической решетки, в узлах которой находятся атомы.

Рассмотрим плоскую прямоугольную решетку с N узлами по вертикали и M узлами по горизонтали (всего NM узлов). Каждый узел характеризуется своим спином, который может принимать значения +1 или 1.

Соседними считаются узлы решётки, смежные по горизонтали или вертикали. Назовём энергией решетки количество пар соседних узлов с различными спинами.

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

Энергия решетки, приведенной в примере, равна 13. После изменения спина левого верхнего узла и третьего узла во второй строке получим решетку с энергией 15.

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

В первой строке входного файла содержатся числа N и M. Далее следует N строк по M символов в каждой. Строки состоят из символов '+' и '-'. Символ '+' соответствует положительному спину, а '-'  — отрицательному.

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

В выходной файл выведите четыре числа: r1 c1 r2 c2  — координаты двух узлов, изменение спина в которых максимально увеличит энергию. ri  — номер строки узла, ci  — номер узла в его строке. Нумерация начинается с 1.

Ограничения

1 ≤ N, M ≤ 1000; N+M > 2;

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

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

Задача I. Беговые дорожки

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

Условие

Между n спортсменами организуется соревнование по бегу. К сожалению, в распоряжении организаторов имеется стадион лишь с n − 1 беговой дорожкой, поэтому одновременно могут состязаться только n − 1 из n участников. По этой причине соревнования разбиваются на несколько забегов.

Правила соревнований требуют, чтобы каждый из бегунов:

Кроме того, некоторые пары спортсменов во избежание конфликтов нельзя выставлять на соседние дорожки в забеге. При этом у каждого из участников есть не более одного «неприятного» ему конкурента, и чувство антипатии является взаимным.

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

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

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

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

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

Ограничения

2 ≤ n ≤ 100.

1 ≤ r ≤ 1000.

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

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

0.351s 0.020s 37