Муниципальный этап всероссийской олимпиады школьников по информатике

Регион

Ханты-Мансийский автономный округ – Югра

Учебный год

2012-2013

Параллель

7-8 классы

Разработчик

Алексеев А.В., к.п.н., доцент

 

A. Строки в книге

(Время - 1 сек., память - 16 Мб)

В книге на одной странице помещается k строк. Таким образом, на 1-й странице печатаются строки с 1-й по k-ю, на второй — с (k+1)-й по (2∙k)-ю и т.д. Напишите программу, которая по номеру строки в тексте определяет номер страницы, на которой будет напечатана эта строка, и порядковый номер этой строки на странице.

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

В единственной строке входного файла input.txt записаны два числа: k — количество строк, которое печатается на странице, и  n — номер строки (1≤ ≤ 200, 1≤ n ≤ 20000).

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

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

Примеры

input.txt

output.txt

1

50 1

1 1

2

20 25

2 5

3

14 41

3 13

B. Фибоначчиева последовательность

(Время - 1 сек., память - 16 Мб)

Последовательность чисел a1, a2, …, ai,… называется фибоначчиевой, если для всех ≥ 3 верно, что ai=ai–1+ai–2, то есть каждый член последовательности (начиная с третьего) равен сумме двух предыдущих.

Ясно, что задавая различные числа a1 и a2 мы можем получать различные такие последовательности, и любая фибоначчиева последовательность однозначно задается двумя своими первыми членами.

Будем решать обратную задачу. Вам будет дано число n и два члена последовательности: an и an+1. Вам нужно написать программу, которая по их значениям найдет a1 и a2.

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

В единственной строке входного файла input.txt записаны: число n и значения двух членов последователности: an и an+1 (1  ≤ 30, члены последовательности — целые числа, по модулю не превышающие 2×109).

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

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

Пример

input.txt

output.txt

1

4 3 5

1 1

C. Сжатие бинарных последовательностей

(Время - 1 сек., память - 16 Мб)

Последовательность из символов ‘0’ и ‘1’ называется бинарной. Они широко применяются в информатике и других науках. Одно из неудобств бинарных последовательностей – их трудно запоминать. Для решения этой проблемы были предложены разные способы их сжатия. Программист Слава использует следующий способ: просматривая последовательность слева направо, он заменяет ‘1’ на ‘a’, ‘01’ на ‘b’, ‘001’ на ‘c’, …, ‘00000000000000000000000001’ на ‘z’. Напишите программу, которая поможет Славе автоматизировать этот способ сжатия.

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

В единственной строке входного файла input.txt записана одна бинарная последовательность – строка из 0 и 1, длиной не более 255 символов. Гарантируется, что к ней применим указанный способ сжатия.

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

В единственную строку выходного файла output.txt нужно вывести одну строку из латинских строчных букв от ‘a’ до ‘z’ – сжатие заданной бинарной последовательности.

Пример

input.txt

output.txt

1

101

ab

2

101001

abc

3

0000000000000000000000001

y

D. Вирусы

(Время - 2 сек., память - 16 Мб)

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

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

В первой строке входного файла input.txt записаны два натуральных числа n и m - размеры таблицы (количество строк и столбцов соответственно). Известно, что 1 £ n, m £ 3000. Во второй строке вначале записано одно число k – количество проникших вирусов, а далее записаны 2k чисел – номера строк и столбцов первых заражённых ячеек xi, yi (1 £ k £ 10, 1 £ xi £ n, 1 £ yi £ m).

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

В единственную строку выходного файла output.txt нужно вывести одно число – время заражения всей области.

Пример

input.txt

output.txt

1

4 5

2 2 1 4 5

4

Пояснения

В приведённом примере таблица имеет размер 4*5, в ней символом ‘V’ помечены проникшие вирусы. Легко посчитать, что за четыре единицы времени произойдёт заражение всей области.

 

 

 

 

 

V

 

 

 

 

 

 

 

 

 

 

 

 

 

V