Ответы. олимпиада. информатика. 9-11 класс.

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

Республика Алтай

Задания и решения для 9–11 классов

Ограничение по времени работы программы во всех задачах: 1 секунда. Каждая задача оценивается в 100 баллов. Решение этих задач должно быть представлено в виде программы, которая считывает входные данные из текстового файла input.txt, а результат записывает в текстовый файл output.txt. Если решение проходит все тесты из условия, то оно принимается на проверку; если тест не пройден, решение не принимается на проверку и не будет оценено.

Задача 1. Лотерея в цветочном магазине

В цветочном магазине лотерея. Каждому покупателю выдается еще один цветок в подарок. На круглой вращающейся полке стоят N горшков с цветами. Каждый горшок имеет порядковый номер от 1 до N. Покупатель, участвующий в лотерее, называет номер чека M и продавец считает по кругу горшки, начиная с горшка с номером 1. Тот горшок, на котором достигается число M, выдается покупателю. Определите номер цветочного горшка, который достанется покупателю.

Программа получает на вход два целых положительных числа. Первое число N — количество горшков на полке. Второе число M — номер чека покупателя. Гарантировано, что M≥N (это условие проверять не нужно, в тестах к задаче оно учтено). Все числа не превосходят 2∙10⁹.

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

Пример входных и выходных данных

Решение задачи должно быть представлено в виде файла программы для среды программирования. Файл необходимо сохранить в папке с решениями и в названии указать номер задачи

Система оценивания

Задача оценивается максимально в 100 баллов.

При решении задачи возможно использование стандартного потока ввода/вывода без использования текстовых файлов.

Решение

Ответом является остаток от деления числа M на число N, за единственным исключением – если остаток равен нулю, то есть M делится на N, то продавец остановит счет на последнем цветочном горшке с номером N и программа должна вывести значение N, а не 0. Это нужно рассмотреть при помощи одного условия if.

Пример решения задачи на языке Free Pascal:

program z01;

var

N,M:longint;

input,output:text;

begin

assign(input, 'input.txt');

assign(output, 'output.txt');

reset(input);

readln(input, N);

readln(input, M);

close(input);

rewrite(output);

if M mod N = 0 then writeln(output, N) else

writeln(output, M mod N);

close(output);

end.

Задача 2. Конвейер

На конвейере три лотка с деталями. В левом лотке лежат X деталей, в среднем лежат Y деталей, в правом лежат Z деталей. Робот берет одну деталь из левого лотка, затем одну деталь из среднего лотка, затем из правого, среднего, левого, среднего, правого, среднего и т. д. (слева направо, затем справа налево, опять слева направо и т.д.)

Если в каком-нибудь лотке детали кончились, робот останавливает конвейер и подает сигнал. Определите, сколько всего деталей возьмет робот до остановки конвейера.

Программа получает на вход три целых положительных числа X, Y, Z – количество деталей в левом, среднем, правом лотке. Сумма трёх данных чисел не превосходит 2∙10⁹.

Программа должна вывести число деталей, которые возьмет робот до остановки.

Пример входных и выходных данных

Решение задачи должно быть представлено в виде файла программы для среды программирования. Файл необходимо сохранить в папке с решениями и в названии указать номер задачи

Система оценивания

Задача оценивается максимально в 100 баллов.

При решении задачи возможно использование стандартного потока ввода/вывода без использования текстовых файлов.

Решение

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

Для получения более быстрого решения заметим, что процесс взятия конфет содержит цикл «левый лоток, средний лоток, правый лоток, средний лоток», который затем повторяется.

За один проход такого цикла число X уменьшается на 1, число Y уменьшается на 2, число Z уменьшается на 1. Посчитаем, сколько раз будет выполнен цикл — это минимум из чисел X, [Y / 2] и Z (под записью [Y / 2] подразумевается целая часть от деления Y на 2, то есть операция целочисленного деления). Запишем количество проходов цикла в переменную k и уменьшим значение переменных X и Z на k, а значение переменной Y на 2k. За k исполнений цикла суммарно будет взято 4k деталей.

Следующий проход цикла не будет выполнен полностью. Посмотрим на значение переменных X, Y, Z в том порядке, в котором берутся детали из соответствующих лотков. Если X = 0, то нельзя на следующем шаге взять деталь из первого лотка, и ответом будет 4k. Если Y = 0, то будет взята деталь из первого лотка, но во втором лотке детали кончились, поэтому ответ будет 4k + 1. Если же Z = 0, то, аналогично, можно взять еще две детали из левого и среднего лотка, и ответ будет 4k + 2. Наконец, если все эти условия не выполнены, то ответ будет 4k + 3.

Пример решения задачи на языке Free Pascal:

program z02;

var

X,Y,Z,k: longint;

input,output:text;

begin

assign(input, 'input.txt');

assign(output, 'output.txt');

reset(input);

readln(input, X);

readln(input, Y);

readln(input, Z);

close(input);

rewrite(output);

if X

if kZ then k:=Z;

writeln(k);

X:=X-k;

Y:=Y-2*k;

Z:=Z-k;

if X=0 then writeln(output, 4*k) else

if Y=0 then writeln(output, 4*k+1) else

if Z=0 then writeln(output, 4*k+2) else

writeln(output, 4*k+3);

close(output);

end.

Задача 3. Счастливая неделя.

В году племени Доджиков N месяцев, ровно по 30 дней каждый, неделя состоит из 7 дней. Если в понедельник выпадает первое число месяца, у племени Доджиков наступает счастливая неделя праздников.

Этот год у племени начался в k-й по счету день недели (1-й день недели — понедельник, 2-й — вторник, 3-й — среда, … , 7-й — воскресенье). Определите, сколько в этом году у племени Доджиков будет счастливых недель.

Программа получает на вход в первой строке целое положительное число N — количество месяцев в календаре племени Доджиков, не превосходящее 10⁹. Во второй строке число k — номер дня недели, на который приходится первое число первого месяца нового года (1≤k≤7).

Программа должна вывести единственное целое число — количество счастливых недель в этом году.

Пример входных и выходных данных

Решение задачи должно быть представлено в виде файла программы для среды программирования. Файл необходимо сохранить в папке с решениями и в названии указать номер задачи

Система оценивания

Задача оценивается максимально в 100 баллов.

При решении задачи возможно использование стандартного потока ввода/вывода без использования текстовых файлов.

Решение

Сначала посчитаем, на какой день недели приходится 1-е число первого месяца, затем будем считать, на какой день недели приходится 1-е число каждого следующего месяца. Если пронумеровать дни недели от 1 до 6, а воскресенье считать днём недели номер 0, то для получения дня недели 1-го числа следующего месяца нужно к текущему номеру дня недели прибавить 30 и взять остаток от деления на 7. Повторяем это в цикле N раз и при получении числа 1 увеличиваем ответ на 1.

Пример решения на языке Free Pascal:

program z03_0;

var

N,k,ans,i: longint;

input,output:text;

begin

assign(input, 'input.txt');

assign(output, 'output.txt');

reset(input);

readln(input, N);

readln(input, k);

close(input);

rewrite(output);

k:=k mod 7;

ans:=0;

for i:=1 to N do begin

if k=1 then ans:=ans+1;

k:=(k+30) mod 7;

end;

writeln(output, ans);

close(output);

end.

Такое решение затратное по времени при больших значениях N.

Чтобы построить более быстрое решение заметим, что поскольку числа 7 и 30 — взаимно простые, то в последовательности дней недели, на которые выпадают 1-е числа месяца будет цикл длины 7: понедельник, среда, пятница, воскресенье, вторник, четверг, суббота. Поэтому для нахождения ответа достаточно найти первый месяц года, в котором будет понедельник 1-е, и к ответу добавить количество оставшихся месяцев в году, деленное на 7 нацело. Пример такого решения:

program z03;

var

N,k,i: longint;

input,output:text;

begin

assign(input, 'input.txt');

assign(output, 'output.txt');

reset(input);

readln(input, N);

readln(input, k);

close(input);

rewrite(output);

k:=k mod 7;

i:=1;

while (i1) do begin

i:=i+1;

k:=(k+30) mod 7;

end;

if iN then writeln(output, 0) else

writeln(output, 1+(N-i) div 7);

close(output);

end.

Задача 4. Лыжные гонки.

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

На входе программа получает в первой строчке целое положительное число N. Далее в N строках записаны номер участника K (1≤K≤100 000) и через пробел его результат в формате mm:ss, где mm минуты (10≤mm≤59), ss секунды (0≤ss≤59).

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

Пример входных и выходных данных

Решение задачи должно быть представлено в виде файла программы для среды программирования. Файл необходимо сохранить в папке с решениями и в названии указать номер задачи

Система оценивания

Задача оценивается максимально в 100 баллов.

При решении задачи для ввода и вывода обязательно необходимо использовать текстовые файлы.

Решение

Заполним два массива: num, где будем хранить номера спортсменов, и t, где будем хранить результаты спортсменов в секундах. Далее будем частично сортировать по возрастанию массив t, одновременно делая такие же изменения в массиве num. При сортировке учитываем то, что результаты могут быть одинаковыми. Пример решения на языке Free Pascal:

program z04;

var

N,min,sek,i,j,code,minT,minN,k: longint;

tstr:string;

num, t:array[1..100000] of longint;

input,output:text;

begin

assign(input, 'input.txt');

assign(output, 'output.txt');

reset(input);

readln(input, N);

for i:=1 to N do begin

readln(input,num[i],tstr);

j:=pos(':',tstr);

val(copy(tstr,j-2,2),min,code);

val(copy(tstr,j+1,2),sek,code);

t[i]:=min*60+sek;

end;

close(input); rewrite(output);

k:=1; j:=1;

for i:=2 to N do begin

if t[i]

minN:=num[i]; num[i]:=num[j]; num[j]:=minN;

minT:=t[i];

t[i]:=t[j];

t[j]:=minT;

end;

end;

write(output,num[j]);

while k

j:=j+1;

for i:=j+1 to N do begin

if t[i]

minN:=num[i]; num[i]:=num[j]; num[j]:=minN;

minT:=t[i];

t[i]:=t[j];

t[j]:=minT;

end;

end;

if t[j-1]

k:=k+1;

writeln(output,'');

write(output,num[j]);

end else write(output,' ',num[j]);

end;

close(output);

end.

Задача 5. Автомобильные номера

В нашей стране принят автомобильный номер следующего формата: буква, три цифры, две буквы, без учета кода региона. Например, A123BC. Петя недавно узнал, что такое палиндром. Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Петя вышел на улицу и стал разглядывать номера на автомобилях. Он заметил, что буквы номера без цифр могут быть палиндромами (например, А123BA), а могут и цифры без букв образовывать палиндром (например, A121BC). Ну и в редком случае встречаются номера, в которых и буквы и цифры образуют два палиндрома (например, A121BA). Петя решил подсчитать, сколько встречается номеров, где нет ни одного палиндрома, палиндромы только буквы, только цифры, и буквы и цифры. Помогите Пете составить программу подсчета количества таких номеров.

Программа получает на вход N строк текста (1≤N≤100 000), каждая строка содержит один образец автомобильного номера. Каждый образец содержит 3 любые цифры и 3 любые заглавные латинские буквы (других символов во входных данных быть не может). Среди номеров может быть некорректный номер, у которого не соблюдается порядок цифр и букв, например, AB1B22.

Программа должна вывести:

• в первой строке количество номеров, в которых ни буквы, ни цифры не образуют палиндрома,

• во второй — количество номеров, в которых только буквы образуют палиндром,

• в третьей — количество номеров, в которых только цифры образуют палиндром,

• в четвертой — количество номеров, в которых и буквы и цифры образуют палиндром.

Пример входных и выходных данных

Решение задачи должно быть представлено в виде файла программы для среды программирования. Файл необходимо сохранить в папке с решениями и в названии указать номер задачи

Система оценивания

Задача оценивается максимально в 100 баллов.

При решении задачи для ввода и вывода обязательно необходимо использовать текстовые файлы.

Решение

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

program z05;

var

a,b,c,d:integer;

anum:string[6];

alpha,num:string[3];

input,output:text;

begin

assign(input, 'input.txt');

assign(output, 'output.txt');

reset(input);

a:=0;b:=0;c:=0;d:=0;

while not eof(input) do begin

readln(input,anum);

alpha:=anum[1]+anum[5]+anum[6];

num:=copy(anum,2,3);

if (alpha='AAA') and (alpha='001')and(num

if (alpha[1]=alpha[3])and(num[1]=num[3]) then a:=a+1 else

if num[1]=num[3] then b:=b+1 else

if alpha[1]=alpha[3] then c:=c+1 else d:=d+1;

end;

close(input); rewrite(output);

writeln(output,d);

writeln(output,c);

writeln(output,b);

writeln(output,a);

close(output);

end.