XVIII олимпиада школьников Красноярского края по информатике
2004-2005 учебный год
(II этап – районный)
ЗАДАЧИ
Максимальное время выполнения заданий: 240 мин.
Максимальное количество набранных баллов: 200
Задача 1.
Максимальная оценка:	30 баллов
Группа программистов собралась в понедельник и на все свои деньги купила «Sprite» в бутылках емкостью по 0.25 л., не забыв взять сдачу.
Во вторник они сдали пустую посуду, добавили оставшуюся сдачу и вновь купили столько таких же бутылок «Sprite», сколько могли.
Так они действовали до пятницы. В пятницу, сдав посуду и добавив сдачу с четверга, они смогли купить только одну бутылку напитка. При этом денег у них уже не осталось.
Требуется написать программу, определяющую минимальную сумму, которой располагали программисты в понедельник.
Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: 2 секунды на каждый тест
Формат входных данных:
Входной файл INPUT.TXT состоит из единственной строки, содержащей два целых числа F (стоимость одной бутылки «Sprite») и P (стоимость одной пустой бутылки из под «Sprite») разделенных пробелом.
Ограничения на входные данные
1)	Стоимости бутылки «Sprite» и пустой бутылки выражаются целыми положительными числами и не превосходят 1 000 000 коп каждая
2)	Пустая бутылка дешевле полной бутылки
3)	Начальная сумма не превосходит 2 000 000 000 коп
Формат выходных данных:
В выходной файл OUTPUT.TXT выводится число, определяющее вычисленное количество денег в копейках.
Примеры входных и выходных файлов:
INPUT.TXT	OUTPUT.TXT	
7 3	83	
Задача 2.
Оценка:	20 баллов
Найти неизвестные десятичные цифры А, Б, В за минимум кратких, точных рассуждений – утвердительных высказываний о цифре разряда, если АВВ5 + ВВАА = ББ922.

Задача 3.
Максимальная оценка:	50 баллов
Имеется список учащихся школы.
Требуется написать программу, распределяющую какое имя самое редкое.
Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: 1 секунда на каждый тест
Формат входных данных:
Входной файл INPUT.TXT содержит список учеников. В каждой строке через пробел заданы Фамилия Имя и Отчество ученика.
Ограничения на входные данные
1)	Число учеников в школе <= 10000
Формат выходных данных:
Файл OUTPUT.TXT содержит одну строку с искомым именем.
Примеры входных и выходных файлов:
INPUT.TXT	OUTPUT.TXT	
Пушкин Александр Сергеевич
Луканов Александр Сергеевич
Соколова Любава Викторовна
Иванов Иван Иванович
Сидоров Иван Петрович	Любава	
Задача 4.
Максимальная оценка:	40 баллов
Требуется написать программу, которая находит цифру, на которую оканчивается число a^b.
Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: 1 секунды на каждый тест
Формат входных данных:
В первой строке входного файла INPUT.TXT записаны числа a и b, разделенные пробелом.
Ограничения на входные данные
1)	 1<= a, b <= 10000.
Формат выходных данных:
В выходной файл OUTPUT.TXT следует записать одну цифру - ту, на которую оканчивается число a^b.
Примеры входных и выходных файлов:
INPUT.TXT	OUTPUT.TXT	
2 2	4	
Задача 5. 
(Задача XVII краевой олимпиады школьников Красноярского края)
Максимальная оценка:	60 баллов
Найти закопанный пиратами клад просто: всё, что для этого нужно – это карта. Как известно, пираты обычно рисуют карты от руки и описывают алгоритм нахождения клада так: «Встаньте около одинокой пальмы. Пройдите тридцать шагов в сторону леса, потом семнадцать шагов в сторону озера, …, наконец десять шагов в сторону большого булыжника. Клад находится под ним». Большая часть таких указаний просто сводится к прохождению какого-то количества шагов в одном из восьми направлений (1 – север, 2 – северо-восток, 3 – восток, 4 – юго-восток, 5 – юг, 6 – юго-запад, 7 – запад, 8 – северо-запад) (см. рис). Длина шага в любом направлении равна 1.
Путешествие по такому пути обычно является прекрасным способом посмотреть окрестности, однако в наше время постоянной спешки ни у кого нет времени на это. Поэтому кладоискатели хотят идти напрямую в точку, где зарыт клад. Например, вместо того, чтобы проходить три шага на север, один шаг на восток, один шаг на север, три шага на восток, два шага на юг и один шаг на запад, можно пройти напрямую, использовав около 3.6 шага (см. рис).

Требуется написать программу, которая по указаниям пиратов определяет точку, где зарыт клад.
Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Максимальное время работы на одном тесте: 2 секунды
Максимальный объем используемой памяти: 32 мегабайта
Формат входных данных:
Первая строка входного файла содержит число N – число указаний (1≤N≤40). Последующие N строк содержат сами указания – номер направления (целое число от 1 до 8) и количество шагов (целое число от 1 до 1000). Числа разделены пробелами.
Формат выходных данных:
В выходной файл выведите координаты X и Y точки (два вещественных числа, разделённые пробелом), где зарыт клад, считая, что ось Ox направлена на восток, а ось Oy  на север. В начале кладоискатель должен стоять в начале координат. Координаты необходимо вывести с погрешностью не более 10-3.
Примеры входных и выходных файлов:
INPUT.TXT	OUTPUT.TXT	
6
1 3
3 1
1 1
3 3
5 2
7 1	3.000 2.000	
1
8 10	-7.071 7.071	
XVII олимпиада школьников Красноярского края по информатике
2004-2005 учебный год
(II этап – районный)
ЛИСТ ТЕСТИРОВАНИЯ
Задача 1. (30 баллов)
№ теста	Входные данные	Правильный ответ	Баллы	Ответ участника	Баллы участника	
1	7 3	83	5			
2	2 1	17	5			
3	12 2	2602	5			
4	100 1	100000099	5			
5	1000 20	125000980	5			
дополнительные баллы за все пройденные тесты	5			
Всего за задачу		баллов	
Задача 3. (50 баллов)
(тестовые файлы прилагаются)
№ теста	Входные данные	Правильный ответ	Баллы	Ответ участника	Баллы участника	
1	input0.txt	output0.txt	7			
2	input1.txt	output1.txt	7			
3	input2.txt	output2.txt	14			
4	input3.txt	output3.txt	14			
дополнительные баллы за все пройденные тесты	8			
Всего за задачу		баллов	
Задача 4. (40 баллов)
№ теста	Входные данные	Правильный ответ	Баллы	Ответ участника	Баллы участника	
1	2  2	4	6			
2	1  7777	1	6			
3	78  44	6	6			
4	3  10000	1	6			
5	37836  377	6	6			
6	9999  9999	9	6			
дополнительные баллы за все пройденные тесты	4			
						
Всего за задачу		баллов	
Задача 5. (60 балла)
(тестовые файлы прилагаются)
№ теста	Входные данные	Правильный ответ	Баллы	Ответ участника	Баллы участника	
1	input01.txt	output01.txt	4			
2	input02.txt	output02.txt	4			
3	input03.txt	output03.txt	4			
4	input04.txt	output04.txt	4			
5	input05.txt	output05.txt	4			
6	input06.txt	output06.txt	4			
7	input07.txt	output07.txt	4			
8	input08.txt	output08.txt	4			
9	input09.txt	output09.txt	4			
10	input10.txt	output10.txt	4			
11	input11.txt	output11.txt	4			
12	input12.txt	output12.txt	4			
13	input13.txt	output13.txt	4			
14	input14.txt	output14.txt	4			
дополнительные баллы за все пройденные тесты	4			
Всего за задачу		баллов	

XVII олимпиада школьников Красноярского края по информатике
2004-2005 учебный год
(II этап – районный)
РЕШЕНИЯ
Задача 2.
1.	Так как переносится в следующий разряд при сложении двух десятичных цифр А и В может лишь 1, то Б=1.
2.	Так как при сложении 5 и А получаем в младшем разряде 2, то А=7 и в следующий разряд переносится 1.
3.	Следовательно, В + А + 1 оканчивается на 2, или В+7+1=12, или В=4. 
Решение найдено за 3 рассуждения (хотя разрядов было больше).
Задача 3.
У этой задачи есть несколько решений, вот одно из них. Воспользуемся хэш-функцией - функцией, которая по входной строке возвращает ее контрольную сумму, т.е. сумму кодов всех символов этой строки. Для начала создадим массив из элементов word размер около 10000 элементов (хэш-функция от самого длинного русского имени наверняка в него поместится). Для ускорения работы заведем еще один массив такого же размера (о его предназначении позже). После преобразования ФИО -> Имя -> Контрольная сумма мы увеличиваем значение элемента с номером, равным контрольной суммы, на 1 (мы используем позиционную хэш-функцию). Если до этого он был 0, то в другой массив заносим номер строки, где он встретился, чтобы в случае необходимости быстро найти его. После того как мы прочитали весь файл, ищем в нашем массиве минимальный ненулевой элемент, в другом массиве находим номер строки, в которой впервые встретилось это имя, читаем из нее ФИО и преобразовываем его в имя. Затем выводим его.
Задача 4.
Надо найти последнюю цифру a^b. На последнюю цифру не влияет никакая цифра, кроме последней цифры числа a^(n-1). Это упрощает задачу. Каждый раз следует возводить в степень только последнюю цифру и при получении числа большего 9 получать только последнюю цифру. Проиллюстрируем на примере:
last :=a
  if b <> 1 then
    for c := 2 to b do 
     begin
      last := last * a;
      last := last mod 10;
     end;
Задача 5.
Для решения этой задачи достаточно было завести две переменные для хранения текущих координат кладоискателя и изменять их в соответствии с входными данными. Например, можно было для каждого указания разбирать 8 случаев — в зависимости от направления — и в каждом из них соответствующим образом передвигать кладоискателя. Однако при таком решении довольно легко ошибиться. Более рациональным было бы использование того факта, что 8 направлений пронумерованы подряд по часовой стрелке. Это могло привести, например, вот к такому короткому решению:
Var I,N,Dir,Len:LongInt;
  X,Y:Real;
Begin
  Assign(Input,'Input.txt');
  Reset(Input);
  Read(N); X := 0; Y := 0;
  for I := 1 to N do 
   begin
    read(Dir,Len);
    X := X + Sin(Pi/4*(Dir–1))*Len;
    Y := Y + Cos(Pi/4*(Dir–1))*Len
  end;
  assign(Output,'Output.txt);
  rewrite(Output);
  writeln(X:0:3,' ',Y:0:3);
  close(Output)
End.

С уважением Н.В. Лалетин
р.т. 8 (231) 2-02-02