Олимпиада школьников

по информатике
2010–2011 учебный год
9–11 класс
Дорогой друг! Желаем успеха!
Решением каждой задачи должен являться исходный текст программы на любом из допустимых языков программирования. В начале решения в комментариях должны быть указаны: фамилия, имя участника, школа, класс, название задачи.

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

Если вы не умеете вводить информацию из файла и выводить в файл, вводите с клавиатуры, выводите на экран, соблюдая формат ввода-вывода. В этом случае (если вы пишете на паскале) ваша программа не должна использовать модуль crt.

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

Выходные данные также должны быть выведены в полном соответствии с описанным форматом выходных данных. Выводить дополнительную информацию не нужно.

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

Не забывайте время от времени сохранять свои решения!

Задача A. Алгоритм Евклида

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Максимальное время работы на одном тесте:	2 секунды
Максимальный объем используемой памяти:	64 мегабайта

Андрей недавно начал изучать информатику. Одним из первых алгоритмов, который он изучил, был алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух чисел. Напомним, что наибольшим общим делителем двух чисел a и b называется наибольшее натуральное число x, такое, что и число a, и число b делится на него без остатка.

Алгоритм Евклида заключается в следующем:

1. 
   Пусть a, b — числа, НОД которых надо найти.
   
2. 
   Если b = 0, то число a — искомый НОД.
   
3. 
   Если b > a, то необходимо поменять местами числа a и b.
   
4. 
   Присвоить числу a значение a – b.
   
5. 
   Вернуться к шагу 2.
   

Андрей достаточно быстро освоил алгоритм Евклида и вычислил с его помощью много наибольших общих делителей. Поняв, что надо дальше совершенствоваться, ему пришла идея решить новую задачу. Пусть заданы числа a, b, c и d. Требуется узнать, наступит ли в процессе реализации алгоритма Евклида для заданной пары чисел (a, b) такой момент, когда перед исполнением шага 2 число a будет равно c, а число b будет равно d.

Требуется написать программу, которая решает эту задачу

Формат входных данных

Первая строка входного файла содержит количество наборов входных данных K (1 ≤ K ≤ 100). Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа: a, b (1 ≤ a, b ≤ 10¹⁸). Вторая строка – два целых числа: c, d (1 ≤ c, d ≤ 10¹⁸).

Все числа в строках разделены пробелом

Формат выходных данных

Для каждого набора входных данных выведите в выходной файл слово «YES», если в процессе применения алгоритма Евклида к паре чисел (a, b) в какой-то момент получается пара (c, d). В противном случае выведите слово «NO».

Примеры:

input.txt	output.txt
2 20 10 10 10 10 7 2 4	YES NO

Задача B. Электропоезд

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Максимальное время работы на одном тесте:	1 секунда
Максимальный объем используемой памяти:	64 мегабайта

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

Формат входных данных

В первой строке задано время отправления поезда с начальной станции. Время задается в следующем формате: сначала идут две цифры, задающие часы (от 00 до 23), далее идет двоеточие, затем идут две цифры, задающие минуты (от 00 до 59). Пробелы внутри строки, задающей время, не допускаются.

Во второй строке входного файла записано натуральное число N (2≤N≤1000) — количество станций в маршруте электропоезда (включая начальную и конечную станции). В третьей строке записано N–1 число — первое из этих чисел задает время следования в минутах от начальной станции до второй станции, второе — время от второй станции до третьей и т.д. Каждое из этих чисел натуральное и не превышает 1000.

Формат выходных данных

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

Примеры

input.txt	output.txt
07:00 4 10 5 3	07:00 07:10 07:15 07:18
22:58 5 2 60 43 20	22:58 23:00 00:00 00:43 01:03

Задача C. Такси

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Максимальное время работы на одном тесте:	1 секунды
Максимальный объем используемой памяти:	64 мегабайта

После затянувшегося совещания директор фирмы решил заказать такси, чтобы развезти сотрудников по домам. Он заказал N машин – ровно столько, сколь у него сотрудников. Однако когда они подъехали, оказалось, что у каждого водителя такси свой тариф за 1 километр.

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

Формат входных данных

Сначала вводится натуральное число N (1≤N≤1000) – количество сотрудников компании (совпадающее с количеством вызванных машин такси). Далее вводится N чисел, задающих расстояния в километрах от работы до домов сотрудников компании (первое число – для первого сотрудника, второе – для второго и т.д.). Все расстояния – положительные целые числа, не превышающие 1000. Далее вводится еще N чисел – тарифы за проезд одного километра в такси (первое число – в первой машине такси, второе – во второй и т.д.). Тарифы выражаются положительными целыми числами, не превышающими 10000.

Формат выходных данных

В выходной файл выведите N чисел. Первое число – номер такси, в которое должен сесть первый сотрудник, второе число – номер такси, в которое должен сесть второй и т.д., чтобы суммарные затраты на такси были минимальны. Если вариантов рассадки сотрудников, при которых затраты минимальны, несколько, выведите любой из них.

Примеры:

input.txt	output.txt
3 10 20 30 50 20 30	1 3 2
5 10 20 1 30 30 3 3 3 2 3	1 2 3 5 4

Задача D. Симметричная последовательность

Имя входного файла:	input.txt
Имя выходного файла:	output.txt
Максимальное время работы на одном тесте:	3 секунды
Максимальный объем используемой памяти:	64 мегабайта

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

1 2 3 4 5 4 3 2 1

1 2 1 2 2 1 2 1

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

Формат входных данных

Во входном файле записано сначала число N – количество элементов исходной последовательности. Далее записано N чисел – элементы этой последовательности. 1≤N≤100, элементы последовательности – натуральные числа от 1 до 9.

Формат выходных данных

В выходной файл выведите сначала число M — минимальное количество элементов, которое надо дописать к последовательности, а потом M чисел (каждое – от 1 до 9) – числа, которые надо дописать к последовательности.

Примеры:

input.txt	output.txt
9 1 2 3 4 5 4 3 2 1	0
5 1 2 1 2 2	3 1 2 1
5 1 2 3 4 5	4 4 3 2 1

9–11 класс
Ответы и решения

Задача А. Алгоритм Евклида

При решении данной задачи следует учитывать следующее. Поскольку ограничения на числа a, b ,c, d в этой задаче достаточно большие, простая симуляция описанного в условии алгоритма не будет укладываться в ограничения по времени.

Однако правильная реализация простой симуляции алгоритма проходит не все тесты.

Более быстрый алгоритм таков. Разобьем процесс применения алгоритма Евклида к паре чисел (а, b) на фазы.

Началом фазы будем считать обмен на шаге 3, а окончанием — момент перед следующим таким обменом (или окончание работы алгоритма — для последней фазы). Нетрудно видеть, что если в начале фазы а=а0, b=b0, то в ее конце a=а0 mod b0,b=bo. В то же время на каждом шаге внутри фазы из а вычиталось bo, т.е. а последовательно было равно a0, a0 – b0, a0-2b0, … , a0 mod b0.

Для того чтобы проверить, встречалась ли пара (с, d) во время фазы, надо проверить следующие условия:

1. d=b0

2. с - (а0 mod b0) делится на b0

3. с≤ c0

Приведем пример реализации:

var

a,b,c,d,n : int64;

procedure swap(var a,b:int64);

var

t:integer;

begin

t:=a;a:=b;b:=t;

end;
procedure solve;

begin

while (b<>0) do begin

// проверка интервала (a,b) и (a mod b,b)

if (b = d) and (c < a)

and ((c - a mod b) mod b = 0) then begin

writeln('YES');

exit;

end;

// переход к следующему интервалу.

a := a mod b;

swap(a,b);

end;

writeln('NO');

end;
procedure init;

var

i: integer;

begin

assign(input, 'euclid.in');reset(input);

assign(output, 'euclid.out');rewrite(output);

readln(n);

for i := 1 to n do begin

read(a,b,c,d);

solve;

end;

end;

begin

init;

close(output);

end.
Задача B. Электропоезд

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

1) реализовать прибавление ко времени одной минуты и получать нужное время путём прибавления по минуте в цикле;

2) реализовать прибавление произвольного количества минут, удовлетворяющих условию задачи, ко времени.

Остаётся не забыть про переход через 24 часа.

Теперь рассмотрим, как можно было это всё реализовать на Delphi. Положим, что в переменной H хранятся текущие часы, а в переменной M – текущие минуты.

Для считывания времени понадобятся две дополнительные переменные: S типа String[2] и Tmp типа Char.
Read(S,Tmp); {Считываем первые два символа - часы, а затем двоеточие}

H:=StrToInt(S);

Read(S); {Считываем минуты}

M:=StrToInt(S);

Теперь рассмотрим прибавление DM минут к времени, хранящемуся в переменных H и M:

H:=(H + (DM+M) Div 60) Mod 24;

M:=(DM+M) Mod 60;
Для вывода времени в формате ЧЧ:ММ понадобится два условных оператора:
If H<10 Then Write(‘0’); {Выводим часы и двоеточие}

Write(H,’:’);

If M<10 Then Write(‘0’); {Выводим минуты}

WriteLn(M);

Задача C. Такси

Тише едешь – дальше будешь.

Заметим, что минимум затрат на такси достигается при такой рассадке сотрудников по такси, что 1-й по величине длины поездки сотрудник (1-й тот, чей путь до дома максимален) сидит в 1-м  по стоимости такси (1-е такси – такси, тариф в котором минимален). Таким образом, для того, чтобы вывести номер такси, в котором при такой рассадке окажется 1-й сотрудник, требуется отсортировать расстояния и тарифы в порядке убывания и возрастания соответственно.

Задача D. Симметричная последовательность

Начнем с функции, которая будет проверять, является ли последовательность a[1], a[2], …, a[k] палиндромной. Для этого нужно сравнить числа a[1] и a[k], a[2] и a[k-1], и т. д. до a[k div 2] и a[k+1-(k div 2)].

a[1]

a[2]

…

a[k div 2]

a[k+1-(k div 2)]

…

a[k-1]

a[k]

Если в какой-то из пар числа окажутся неравными, то последовательность палиндромной не является. Напишем соответствующий код:
function palindrom (k : integer) : boolean;

var

i : integer;

begin

palindrom:=TRUE;

for i:=1 to k div 2 do

if a[i]<>a[k+1-i] then begin

palindrom := false;

break;

end;

end.

Теперь вернемся к исходной задаче. Заметим, что в худшем случае нам придется дописать N-1 чисел. Например, если дана последовательность 1 2 3 … N-1 N, то кратчайшая палиндромная последовательность будет выглядеть так: 1 2 3 … N-1 N N-1 … 3 2 1. В самом лучшем случае наша последовательность уже является палиндромной и дописывать ничего не нужно. Таким образом, ответом в задаче является число от 0 до N-1.

Опишем один из алгоритмов, решающих нашу задачу. Для начала проверим, является ли данная нам последовательность палиндромной, используя вызов функции palindrom(N). Если нет, то проверим, достаточно ли добавить одно число. Ясно, что для того, чтобы получилась палиндромная последовательность, необходимо в конец дописать число a[1] :

a[N+1]:=a[1];

После этого опять проверим, получился ли палиндром, вызывая функцию palindrom(N+1). Если нас вновь не постиг успех, допишем в конец исходной последовательности два числа:

a[N+2]:=a[1]; a[N+1]:=a[2]

и т. д. до тех пор, пока функция palindrom на очередном шаге не вернет результат TRUE.
Покажем, как организовать этот процесс, используя цикл for:
[1] for i:=0 to N-1 do begin

[2] for j:=1 to i do

[3] a[N+j]:=a[i+1-j]; {Добавляем в конец i чисел}

[4] if palindrom(N+i) then begin

[5] writeln(i); {Печатаем количество добавленных чисел}

[6] for j:=1 to i do

[7] write(a[N+j],’ ’); {Печатаем добавленные числа}

[8] exit;

[9] end;

[10] end.

Обратим внимание, что мы принудительно завершаем работу программы оператором exit, если при очередной итерации цикла получается палиндромная последовательность. Можно было обойтись без этого, используя цикл while.
Теперь попробуем несколько модифицировать приведенный алгоритм. Дело в том, что мы выполняем лишние операции, дописывая в конец те же числа, что стоят в начале последовательности и затем сравнивая эти числа в функции palindrom. Ясно, что достаточно проверять лишь числа, которые входят в исходную последовательность.
Для этого в цикле внутри функции palindrom нужно начинать проверять числа не с a[1], а с числа, которое сравнивается с числом a[N], то есть с числа a[k+1-N]:
for i:=k+1-N to k div 2 do ...
Тогда и в основной программе нет нужды дополнять массив новыми числами: строки [2] и [3] можно удалить, а строку [7] заменить такой: write(a[i+1-j],’ ’);
Отметим, что максимальная возможная длина палиндрома – 199. Это нужно учитывать при объявлении массива a.

Пример полного решения на языке Pascal:

var

N,i,j : integer;

a : array [1..1000] of integer;

function palindrom (k : integer) : boolean;

var

i : integer;

begin

for i:=1 to k div 2 do

if a[i]<>a[k+1-i] then begin

palindrom := false;

break;

end;

end;
begin

assign(INPUT,' input.txt ');reset(INPUT);

assign(OUTPUT,' output.txt');rewrite(OUTPUT);

read(N);

for i:=1 to N do

read(a[i]);

for i:=0 to N-1 do begin

for j:=1 to i do

a[N+j]:=a[i+1-j]; {Добавляем в конец i чисел}

if palindrom(N+i) then begin

writeln(i); {Печатаем количество добавленных чисел}

for j:=1 to i do

write(a[N+j],' '); {Печатаем добавленные числа}

close(output);

exit;

end;

end;

close(INPUT);

close(OUTPUT);

end.

Баллы за задачи

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

Во всех задачах ответ однозначен.

К задачам B, C и D прилагаются наборы тестов. Тестировать задачи можно с использованием автоматической системы для самотестирования olympiads.ru, которую можно скачать по адресу https://olympiads.ru/school/system/download/olympiads/download.shtml.

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