II (муниципальный) этап Всероссийской олимпиады школьников по информатике в Башкортостане

3 декабря в Башкортостане прошел 2 муниципальный этап олимпиады школьников по информатике. 

Привожу тексты задач.  Интересно, какими были задачки в других регионах?


 
Задача А.  Два плюс – три. (100 балов)
Входной файл:a.in
Выходной файл:a.out
Ограничение по времени: 1 сек.
Ограничение по памяти: 16 Мб
Вася, скучая на уроке математики, писал в тетради различные числа. Наугад выбирая три числа, он проверял, можно ли, суммируя первые два числа, получить третье. Сосед по парте отличник Иванов, усложнив задачу, написал программу, которая позволяет проверить можно ли перестановкой цифр в числах a и b, записанных Васей, получить их сумму равную c.
Входные данные
Входной файл содержит три целых числа: a, b, c (0 < a, b, c < 109). Числа разделены пробелом.
Выходные данные
Если искомая перестановка цифр невозможна, вывести в выходной файл число 0. При положительном ответе необходимо вывести число x, получаемое перестановкой цифр числа a, и число y, получаемое перестановкой цифр числа b, сумма которых равна c. Числа x и y не должны содержать ведущих нулей и разделяются пробелом. Если вариантов чисел несколько, то вывести любой.
Пример

a.in
a. out
12 31 25
12 13
12 31 26
0
101 2 13
11 2

 
Задача B. Различные числа (80 балов)
Входной файл:b.in
Выходной файл:b.out
Ограничение по времени: 1 сек.
Ограничение по памяти: 32 Мб
Дан массив (достаточно большой), содержащий целые числа из диапазона -15000..15000. Сосчитать сколько различных чисел в этом массиве. Гарантируется, что количество чисел в файле не превышает 106.
Формат входных данных:
Во входном файле b.in содержатся элементы массива. Файл может содержать несколько строк. Все числа в строке разделены пробелом. Каждая строка заканчивается «Enter».
Формат выходных данных:
В первой строке выходного файла b.out содержится число – количество различных чисел. Далее следуют сами эти числа, записанные по 10 в строке в порядке возрастания.
Пример

b.in
b. out
5 7 -47 6 -193 5
7 9 14 5485 -193
8
-193 -47 5 6 7 9 14 5485
1 1 1 1 1 1 2 2 2 2
2
1 2
1
2
3
1
2
3
3
1 2 3

 
Задача С. Театр (80 баллов)
Входной файл:                             с.in
Выходной файл:                          c.out.
Ограничение по времени тестирования: 1 сек.
Ограничение по памяти: 32 Мб
В театре N мест, пронумерованных целыми числами от 1 до N. Некоторые зрители опоздали на спектакль, поэтому после третьего звонка те зрители, которые имели билеты на неудобные места, пересели на более удобные. Опоздавшие зрители, которые пришли уже после третьего звонка, садились на первое попавшееся свободное место.
В антракте один из опоздавших решил сесть на свое место. Если его место до этого было занято, то сидевший там пересаживался на свое место. Если и там кто-то уже сидел, то и этот зритель также вынужден был вернуться на свое место, и так далее. Поскольку в театр попали только зрители с билетами, то начавшийся в антракте процесс пересаживания зрителей обязательно заканчивался.
Требуется составить программу для подсчета количества зрителей, которые были вынуждены пересесть на свои места.
Формат входных данных:
Входной файл c.inсостоит из трех строк. В первой строке содержится целое число N (1 £ N £ 15 000) — количество мест в театре. Вторая строка содержит последовательность из N целых чисел, разделенных пробелами. Первое число определяет номер места в билете у зрителя, занявшего первое место, второе число — номер места в билете у зрителя, занявшего второе место, и так далее. Если место свободно, то соответствующее число равно 0. Третья строка содержит одно целое число K (1 £ K £ 15 000) — номер места в билете опоздавшего зрителя, который решил пересесть в антракте на свое место.
Формат выходных данных:
Выходной файл c.outсодержит одно целое число — количество зрителей, поменявших свои места в антракте, включая опоздавшего зрителя.

c.in
c.out
8
0 1 3 5 2 0 0 0
5
3
10
0 2 5 3 4 0 0 0 0 0
2
0
2
2 1
1
2

 
Задача D. Змейка (80 балов)
Входной файл:d.in
Выходной файл:d.out
Ограничение по времени: 1 сек.
Ограничение по памяти: 32 Мб
Мальчик Вася на уроке математики, вместо того, чтобы слушать учителя, рисовал числа в тетрадке в клеточку. Да не просто так рисовал, а определенным образом. Сначала он поставил в клетку число 1. Затем справа от нее нарисовал число 2. Затем снизу от числа 2 написал число 3. Затем перешёл на клетку правее и продолжил увлекательное занятие, двигаясь по столбцу вверх, пока число в этом столбце не стало выше самого верхнего числа в предыдущем столбце. Затем он перешёл на клетку правее и опять таки продолжил рисование чисел, начиная с 7, но только уже сверху вниз, пока не нарисовал число, которое оказалось на одну клетку ниже самого нижнего числа в предыдущем столбце. И так далее. Вася не любил числа, заканчивающиеся нулем, и пропускал их при рисовании змейки. Первые его шесть заполненных столбцов мы скопировали из его тетрадки и привели здесь на рисунке. Так как Вася очень любопытный, то он очень хочет узнать, какое же число будет у него стоять в N-ом столбце в той строке, где стоит число 1. Первые 6 таких чисел в этой строке видны на рисунке: 1, 2, 5, 8, 14, 19. Напишите программу, которая поможет Васе.
Формат входных данных:
Вводится одно число N (1 ≤ N ≤ 106) – номер столбца.
Формат выходных данных:
Вывести N-ое число в строке, где стоит число 1.

d.in
d.out
5
14

 
 
 
 
 
 
 
Задача E. Склад (60 балов)
Входной файл:e.in
Выходной файл:e.out
Ограничение по времени: 2 сек.
Ограничение по памяти: 32 Мб
Банки с красками нумеруются числами от 0 до 999999. Краски на склад поступают наборами, в каждом наборе содержится по одной банке для каждого номера краски от a до b включительно. Время от времени на склад приходит покупатель и забирает все банки с номерами большими или равными k. В начале дня склад пустой.
Напишите программу для кладовщика, которая вычисляет количество банок, взятых покупателями.
Формат входных данных:
Во входном файле журнал действий кладовщика. Строка "ADDab", где a и b – целые числа (0 ≤ ab ≤ 999999), означает, что на склад поступил набор с номерами банок от a до b. Строка "DELk", где k – целое число (0 ≤ k ≤ 999999), означает, что пришёл покупатель и забрал все банки с номерами большими или равными k. Строка ''END'' является последней строкой в файле и означает конец рабочего дня кладовщика. Количество записей в файле не превышает 2000.
Формат выходных данных:
В выходной файл для каждой записи "DELk" в порядке их следования во входном файле вывести строку, содержащую одно число – количество банок, взятых этим покупателем.
Пример

e.in
e.out
ADD 10 20
ADD 5 15
DEL 7
ADD 3 7
DEL 4
DEL 5
END
20
6
0
 

 

 

ВложениеРазмер
inf09.doc80 КБ
у нас было тоже самое

а подскажите, как решить задачу Е - склад