Олимпиадные задачи с решениями по программированию

Каникулы!

До начала учебного года 3 дня

Всього новин: 724
Всього уроків: 37
Всього класів: 20
Переглядів: 733096
Онлайн: 5

Олимпиадные задачи по программированию с решением

Дата добавления: 2011-06-27
Автор: Будина Н. В.

Линейные программы.

Кубики. Кубик с ребром N см покрасили и разрезали на кубики с ребром 1 см. При этом появились такие, у которых окрашено разное количество граней. Например, если N = 3, то после разрезания будет 8 кубиков, у которых окрашено три грани, 12 с двумя гранями, 6 с одной, а один кубик будет совсем неокрашенный. Составьте программу, которая бы определяла, сколько кубиков с каждой возможным количеством окрашенных граней.

С клавиатуры вводится целое число N (от 1 до 1292)

На экран или форму выводятся различные варианты окрасок и их количества в формате: количество_окрашеных_граней/количество_кубиков в порядке возрастания первого параметра

Решение на языке Паскаль:
program cubes;
uses crt;
var x, x1,x2,x3,x0,y, z,k, n:integer;
s:string; f, g:text;
begin
assign(f,’cubes. dat’);
reset(f);
readln(f, y);
close(f) ;
x3:=8;
x1:=sqr(y-2)*6;
x0:=(sqr(y-2))*(y-2);
x2:=(y-2)*4*2+(y-2)*4;
assign(g,’cubes. sol’);
rewrite(g);
writeln(g,’0/’,x0,’ 1/’,x1,’ 2/’,x2,’ 3/’,x3);
close(g);
end.

Ветвление

Отрезок. Отрезок на плоскости задается двумя несовпадающие конечными точками A (x1; y1) и B (x2; y2). С точки С (х3; у3) к прямой, содержащей отрезок АВ, проводится перпендикуляр г. Определить, попадает перпендикуляр на отрезок АВ или на его продолжение.
Во входном файле содержится три пары чисел, являющихся координатами точек А, В, С. В файле содержится ответ «На отрезок» или «На продолжение».
Пример входного и выходного файлов

Решение на языке Паскаль:
program z3;
var x1,x2,x3,y1,y2,y3,ac, ab, bc, a1,b1:real;f, f1:text;
begin
assign (f, ‘z1.dat’);
rewrite(f);
readln(x1,y1);
readln(x2,y2);
readln(x3,y3);
writeln(f, x1,y1);
writeln(f, x2,y2);
writeln(f, x3,y3);
close(f);
ac:=sqr(x1-x3)+sqr(y1-y3);
ab:=sqr(x2-x1)+sqr(y2-y1);
bc:=sqr(x3-x2)+sqr(y3-y2);
b1:=(ab+bc-ac)/(2*sqrt(ab*bc));
a1:=(ac+ab-bc)/(2*sqrt(ac*ab));
if (a1 2 и действительные числа a1, b1, . an, bn. (ai, bi). Рассматривая пары чисел ai и bi, как левые и правые концы отрезков на одной и той же прямой, определить концы отрезка, являющегося пересечением всех этих отрезков. Если такого числа нет, то сообщить об этом. Во входном файле в первой строке задается число N, в следующих N строках — координаты концов отрезков; в файле выводятся координаты концов отрезка, являющегося пересечением всех этих отрезков, или сообщение «Нет пересечения».

Решение на языке Паскаль:
program Dlina;
var a, a1,a2,a3,b1,b2,b3,z, n,g, d:integer; f, f1:text; x:string;
begin
assign (f,’dlina. dat’);
writeln(‘vvedite kolvo otrezkov’); readln(a);
writeln(‘vvedite konci pervogo otrezka’); readln(a1,b1);
writeln(‘vvedite konci vtorogo otrezka’); readln(a2,b2);
writeln(‘vvedite konci tretego otrezka’); readln(a3,b3);
rewrite(f);
writeln(f, a);
writeln(f, a1,’ ‘,b1);
writeln(f, a2,’ ‘,b2);
writeln(f, a3,’ ‘,b3);
close(f);
assign (f1,’dlina. sol’);
rewrite(f1);
close(f1);
if a2>a3 then z:=a2 else z:=a3;
if a1>z then n:=a1 else n:=z;
writeln(‘bolshee iz trex’,n);
if b2 d then g:=b1 else g:=d;
writeln(‘menshee iz trex’,g);
x:=’peresechenia net’;
if n b) and (b = 9) and (a = 1) and (b 0) and (y 0) and (y 36) and (y 2 then begin
a:=8;
b:=12*n-24;
c:=6*n*n-3*a-2*b;
d:=n*n*n-a-b-c;
write(f,’0/’,d,’ ‘,’1/’,c,’ ‘,’2/’,b,’ ‘,’3/’,a);
end;
close(f);
end.

Второй вариант
uses crt;
var n, i,j, k,m, k0,k1,k2,k3 : longint; f, f1 : text;
begin
clrscr;
assign(f,’CUBES. dat’);
reset(f);
assign(f1,’CUBES. sol’);
rewrite(f1);
readln(f, n);
k:=n*n*n;
if n=1 then writeln(f1,’6/1′) else
if n=2 then writeln(f1,’3/8′) else
begin
k2:=12*(n-2);
k3:=8;
k1:=6*(n*n-4-4*(n-2));
k0:=k-k1-k2-k3;
writeln(f1,’0/’,k0,’ ‘,’1/’,k1,’ ‘,’2/’,k2,’ ‘,’3/’,k3)
end;
close(f); close(f1);
end.

Еще один вариант
program cubes;
var x1, x2: integer; x3, x4, n : integer; f1, f2 : text;
begin
assign(f1, ‘cubes. dat’);
assign(f2, ‘cubes. sol’);
reset(f1);
read(f1, n);
rewrite(f2);
if (n >= 1) and (n 1)
then writeln(f2, ‘0/’, x1,’ 1/’, x2,’ 2/’,x3,’ 3/’, x4);
if (n = 1) then writeln(f2, ‘4/1’);
close(f1);
close(f2);
end.

Цикли

Задача 1 На интервале [m; n] найти количество натуральных чисел вида 3d5p (d, p — положительные целые числа).
Пример входного и выходного файлов

Решение на языке Паскаль:
program z1;
var a1,b1,c1,d1,a2,b2,c2,d2,m, n,k, s,x, i:integer;
f, f1:text;
begin
assign (f, ‘z1.dat’);
rewrite(f);
readln(m, n);
writeln(f, m,n);
close(f);
a1:=m div 1000; b1:=m mod 1000 div 100;
c1:=m mod 100 div 10; d1:=m mod 10;
a2:= n div 1000; b2:=n mod 1000 div 100;
c2:=n mod 100 div 10; d2:=n mod 10;
for i:=1 to 10 do
begin
if b1 0 then
begin
assign(f1, ‘z1.rez’);
rewrite(f1);
writeln(‘s=’,s);
writeln(f1,s);
close(f1)
end
end.

REBUS.Составить программу REBUS, которая определяет все 4-значные числа на интервале [M, N], удовлетворяющие условиям:
a) abcd — 4-цифровое число;
b) a, b, c, d — разные цифры;
c) ad — cd = a + b + c + d;
и подсчитывает общее количество этих чисел.
Во входном файле REBUS. DAT в 1-м и 2-й строчках находятся два числа M и N. В файле REBUS. SOL выводятся числа, удовлетворяющие условиям а)-с), и их количество.

Решение на языке Паскаль:
program REBUS;
var a, b,c, d,m, n,k, x,i:integer; f, f1,f2:text;
begin
assign (f,’rebus. dat’);
readln(m, n);
rewrite(f);
writeln(f, m);
writeln(f, n);
close(f);
for i:=m to n do
begin
a:=i div 1000; b:=i mod 1000 div 100;
c:=i mod 100 div 10; d:=i mod 10;
if (a <> b) and (a <> c) and (a <> d) and (b <> c) and (b <> d) and (c <> d) and (a*d-c*d=a+b+c+d) then
begin k:=k+1;
assign(f1,’rebus. sol’);
append(f1);
writeln(f1,i);
close(f1);
end;
end;
assign(f1,’rebus. sol’);
rewrite(f1);
writeln(k);
writeln(f1,k);
close(f1) end.

DATES. Даны две календарные даты. Вычислите количество дней между ними.
Данные вводятся в файл в формате «ДД. ММ. ГГГГ», де ДД – день, ММ – месяц, ГГГГ – год.

Решение на языке Паскаль:
program RUN;
Uses CRT;
Const M:array[0..11] of byte=(31,29,31,30,31,30,31,30,30,31,30,31);
var chiclo1,chiclo2,i, w1,w2,god1,god2, S, S1,S2:integer; f, f1:text;
begin
assign (f,’dates. dat’);
writeln(‘ vvedite pervy daty’);
readln(chiclo1,w1,god1);
writeln(‘ vvedite vtorogy daty’);
readln(chiclo2,w2,god2);
rewrite(f);
if (chiclo1 10) and (w1 10) and (w1 MIN1 do
begin
CHAS1:=CHAS1+0.5;
MIN1:=MIN1+6;
i:=i+1;
end;
assign(f1, ‘DATES. SOL’);
rewrite(f1);
writeln(‘ proshlo ‘,i,’ minyt ‘);
writeln(f1,i);
close(f1)
end.

Lift. Чтобы поднять на N-й этаж M-этажного дома новый холодильник, Витя вызвал бригаду грузчиков. Оплата работы грузчиков рассчитывается так: за подъем холодильника на один этаж требуется заплатить 200 гривен, за спуск на один этаж — 100 гривен. За подъем и спуск на лифте плата не взимается. Несмотря на то, что в доме есть лифт, Вите возможно все же придется заплатить грузчикам, поскольку лифт останавливается только на каждом K-м этаже, начиная с первого (то есть на этажах с номерами 1, K +1, 2K +1, 3K +1, . ). Нужно вычислить, какой минимальной суммы денег достаточно, чтобы грузчики доставили холодильник с первого этажа на N-й.
Во входном файле записаны три числа: M (2 M ; < c - chetchik ostanovok);>
For i:=1 to c do begin
if (W[i] B then begin
assign(f1, ‘Lift. sol’);
rewrite(f1);
writeln(‘ opyckaemca B=’,B);
writeln(f1,B);
close(f1)
end
else begin
assign(f1, ‘Lift. sol’);
rewrite(f1);
writeln(‘ podnimaemca A=’,A);
writeln(f1,A);
close(f1)
end;
end;
if W[i]=N then begin
assign(f1, ‘Lift. sol’);
rewrite(f1);
writeln(‘nichego ne platim’);
writeln(f1,’nichego ne platim’);
close(f1)
end;
end;
end.

«Несчастливые пиковые» числа. Трехзначное число назовем «пиковым», если его цифра десятков будет больше цифры единиц и сотен (напр., число 276 — «пиковое», а 954 и 277 — нет). Составьте программу, которая подсчитывает, сколько «пиковых» чисел находится на отрезке [A, B] и сколько из них делятся без остатка на 13.

два целых числа 100 n) and (k>m) then c:=c+1;
if x mod 13=0 then t:=t+1;
end;
assign(f1, ‘PICK. SOL’);
rewrite(f1);
writeln(f1,c,’ ‘,t);
close(f1);
writeln(‘ a=’,a,’ b=’,b,’ c=’,c,’ t=’,t);
end.

Второй вариант
Program PICK;
var f1,f2 : text; a, b,c, d,i, j,k, l,n, x,y, z : integer;
begin
assign(f1,’pick. dat’);
reset(f1);
assign(f2,’pick. sol’);
rewrite(f2);
readln(f1,l);
for d:= 1 to l do begin
read(f1,a, b);
k:=0;
J:=0;
for i:= a to b do begin
z:=i mod 10;
y:=i div 10 mod 10;
x:=i div 100;
if (y>x) and (y>z) then k:=k+1 ;
if (y>x) and (y>z) and (i mod 13 =0)
then j:=j+1 ;
end;
write(f2,k,’ ‘,j);
end;
close(f1);
close(f2);
end.

Добавление. Число, которое одинаково читается слева направо и наоборот, называется палиндромом, напр., 3773. Возьмем произвольное число N (от 10 до 10000). Если оно не палиндром, добавим к нему число, состоящее из тех же цифр, но записанных в обратном порядке. Будем повторять эту операцию, пока не получим палиндром (если это возможно). Например, N = 49, 49 +94 = 143, 143 +341 = 484. Напишите программу, которая бы определяла, можно из заданного числа N получить палиндром, и если возможно, то за какое минимальное количество добавлений. Если меньше, чем за 100 добавлений это сделать невозможно, вывести на экран -1.

С клавиатуры вводится целое число N (від 10 до 10000)

На экран или форму выводится минимальное количество добавлений для получения палиндрома или -1, если за 100 добавлений это сделать невозможно

Олимпиадные задачи с решениями по программированию

Параллелограмм и прямоугольник имеют одинаковые(попарно) стороны. Найдите острый угол параллелограмма, если его площадь равна половине площади прямоугольника. Ответ дайте в градусах. Реклама. Попроси больше объяснений; Следить ? Отметить нарушение ? Neylovima 12.04.2015.

Олимпиадные задачи с решениями по программированию

Олимпиады по программированию

Несколько вводных слов

Представленные здесь задачи — это продолжение курса программирования, который опубликован здесь. Тем самым, этот курс рассчитан на школьников 9-го математического класса, которые до этого уже полгода изучали программирование. Курс годовой, в режиме 2 часа в неделю. Мне бы хотелось выразить признательность школьникам 9 класса «В» Московской гимназии 1543 (2004-2005 учебный год) за нашу с ними совместную работу по «обкатке» этих задач 🙂 .

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

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

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

Все представленные задачи представлены в формате, принятом на сайте www. olympiads. ru. Внутри архива содержатся условие, тесты, проверяющие программы. Там, где используются дополнительные программы, они также есть внутри архивов. Обратите внимание, в html-версии присутствуют некоторые комментарии для преподавателей, которых нет внутри архивов!

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

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

Во всех задачах входные данные (если не указано иное) вводятся из файла INPUT. TXT, выходные данные выводятся в файл OUTPUT. TXT.

Комментарии. Цель первых занятий — вспомнить материал прошлого года на достаточно простых задачах.

Комментарии. Задачи 204-206 — это задачи окружной олимпиады прошлого учебного года, в которой школьники не участвовали. Им были предложены эти задачи с двумя целями: во-первых, попробовать свои силы в области олимпиад по информатике, а во-вторых, продолжить вспоминать материал прошлого учебного года.

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

Комментарии. Далее идет серия задач на тему «строки».

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

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

Комментарии. Задача 249 — довольно необычна. Существует огромное количество подходов к ее решению (можно придумать правила генерации предложений и «зашить» довольно большой словарь, а можно немножко подумать и придумать способы, как обойтись очень небольшим количеством слов). В результате решения этой задачи порой получаются довольно забавные тексты, эта задача очень непохожа на большинство олимпиадных задач, предоставляет школьникам очень большой размах для творчества (не только программисткого), и этим мне эта задача очень нравится. Эта задача автоматически проверяется лишь частично — проверяющая программа проверяет соблюдение формальных правил, дальше требуется вручную посмотреть, что тексты все-таки отвечают правилам русского языка. К сожалению, в задаче используются русские буквы, и это неминуемо приводит к проблемам с кодировками — предложенная проверяющая программа проверяет решение, считая что генерируется текст в DOS-кодировке.

Комментарии. Следующие несколько задач — на алгоритм Дейкстры. Задачи на алгоритм Дейкстры (равно как и дальше задачи на какие-либо стандартные алгоритмы) подобраны по следующему принципу: сначала идет задача, которая встречается как этап в алгоритме, потом — задача просто на то, чтобы написать рассказанный алгоритм, а дальше — набор задач на использование этого алгоритма (при этом решение этих задач для слабых школьников уже не обязательно, а вот того, чтобы каждый мог написать рассказанный алгоритм, стоит добиваться). Задача 251 — это лишь подэтап в алгоритме Дейкстры, однако написав ее, дальше уже несложно написать и весь алгоритм Дейкстры целиком (хотя написание алгоритма «с нуля» вызывает у слабых школьников ступор). Естественно, что алгоритм Дейкстры школьникам рассказывается (хотя, безусловно, бывают школьники, которые могут его придумать сами, но такое встречается все-таки нечасто).

Комментарии. Описание алгоритма Дейкстры — это часть задачи (оно входит в условие задачи) для того, чтобы когда школьники его пишут он был у них перед глазами. При этом перед этим мы с ними подробно разбираем его у доски.

Комментарии. Следующая серия задач — на алгоритм Флойда.

Комментарии. Научившись считать длины кратчайших путей, стоит обратить внимание на то, как по этим значениям восстановить сам путь. Задача 261 — про это. Каким алгоритмом ищутся длины кратчайших путей здесь — не существенно.

Комментарии. Следующая задача — на алгоритм Форда-Белмана.

Комментарии. Следующая серия задач посвящена остовным деревьям и алгоритмам их поиска — алгоритму Прима и Краскала. Начинается все с задач на понимание школьниками что такое дерево. Дальше идут две очень простых задачи, одна из которых соответствует шагу алгоритма Краскала, вторая — шагу алгоритма Прима.

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

Хочется обратить внимание вот на что: рекурсия изучается достаточно поздно. Изучение рекурсии начинается на задачах, которые уже не раз разбирались, и которые должны быть понятны школьникам, правда, добавляется довольно искусственный запрет на использование циклов. Этот запрет объясняется тем, что «сейчас мы с вами на простых задачах изучим некоторый инструмент, который реально в этих задачах и не нужен. Но дальше нам этот инструмент понадобится на других (уже не столь простых) задачах, которые без него решать будет еще сложнее.»

Комментарии. Также, без автоматической проверки, давалась и тема рекурсивной генерации объектов.

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

Комментарии. Задачи 278, 279 (или вариант 279-й задачи — задача 280) — это задачи контрольной работы по теме рекурсия. Первая задача этой работы решалась на листочке:

Комментарии. Последние три задачи — на тему «обход в глубину». Обратите внимание, что в задаче 282 требуется дополнительный модуль, которому для работы нужны дополнительные файлы. Исходный текст этого модуля можно найти в архиве решения.

Олимпиадные задачи с решениями по программированию

Олимпиадные задачи с решениями по программированию

Ограничение по времени на тест: 4 секунды

Ограничение по памяти на тест: 256 мегабайт

Ввод: standard input

Вывод: standard output

В городе N. очень плохо с дорогами, общепитом и IT-инфраструктурой. Всего в городе n перекрестков, некоторые пары которых соединены двусторонними дорогами. Дорожная сеть состоит из n — 1 дороги, по дорогам можно добраться с любого перекрестка на любой другой. Да, вы правы — дорожная сеть образует неориентированное дерево.

    в каждом перекрестке должен находится не более чем один ресторан; каждый ресторан принадлежит либо «iMac D0naldz», либо «Burger Bing»; каждая сеть должна построить не менее одного ресторана; не существует пары перекрестков, которые соединены дорогой и на которых стоят рестораны разных сетей.

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

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

В первой строке входных данных содержится целое число n (3 ≤ n ≤ 5000) — количество перекрестков в городе. Далее в n — 1 строке перечислены все дороги, по одной дороге в строке. Каждая дорога задана парой чисел xi, yi (1 ≤ xi, yi ≤ n) — номерами соединяемых перекрестков. Считайте, что перекрестки пронумерованы от 1 до n.

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

В первую строку выведите целое число z — количество искомых пар. Далее выведите все искомые пары (a, b) в порядке увеличения первой компоненты a.

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

Решением олимпиадной задачи является программа, написанная на одном из языков программирования. Самыми популярными языками являются: C++, C#, Java, Pascal. Возможно, вы скажете, что Pascal уже давно устарел. Однако не стоит его недооценивать! Опытные спортивные программисты способны писать на Pascal’е стандартные алгоритмы, которые уже есть в C++, быстрее, чем обычный человек прочтет условие задачи 🙂 Кстати, из-за того, что участники выбирают язык программирования самостоятельно, есть риск, что они делают неоптимальный выбор. Во-первых, решения существуют не на всех языках, а во-вторых, решения, написанные на некоторых языках, могут работать менее эффективно, чем на других.

    строгий формат ввода\вывода, иногда даже с точностью до пробелов и переводов строк; условия, как правило, имеют строгую однозначную трактовку. Вот уж где можно поучиться заказчикам в написании ТЗ! строгие ограничения по времени выполнения и используемой памяти. В реальной разработке вам скорее скажут что-то в стиле «Хотим, чтобы работало на таком-то железе и на такой-то ОС» или «Слушай, твоя программа ест слишком много памяти». Куда реже можно услышать фразы типа «Твоя программа должна работать не более 1,5 секунд» или «Не смей использовать более 64 мегабайт памяти»; все исходные величины строго ограничены.

    задача считается решенной, если решение участника правильно сработало на всех тестах. Такая система оценки используется на ACM-соревнованиях. за решение начисляются баллы, которые зависят от количества тестов, успешно пройденных программой. Такой подход часто используется на школьных олимпиадах: никто не уйдет обиженным с соревнования и получит хотя бы свои 0,5 балла. тесты объединены в группы, за каждую из которых начисляется определенное количество баллов. Нужно заметить, что баллы за группу начисляются, только если решение правильно сработало на всех тестах из группы. Это разумный компромисс между справедливостью и удовлетворением участников. ABBYY Cup исповедует именно такую форму оценки решений; иногда число баллов, полученных участником, зависит от времени, которое было затрачено на решение задачи. Например, такая система используется на Codeforces и Topcoder.

Оценки решений «эвристических» задач в каждом случае разрабатывается индивидуально. В эвристической задаче, которую предлагалось решить финалистам ABBYY Cup 2.0, нужно было разработать программу для классификации документов по тематикам. Решение проверялось на группе тестов, каждая из которых содержала некоторый набор текстов на разные темы. Всего было три тематики, и каждая из них была представлена в каждой группе в разном количестве. Выигрывал тот, чье решение прошло наибольшее количество групп тестов. При установке «эвристической» задачи на тестирующую платформу иногда приходиться ее дорабатывать, поскольку большинство тестирующих платформ «заточено» на оценку классических задач.

Рузана Миниахметова, группа образовательных проектов.

Олимпиадные задачи с решениями по программированию

Программирование на C, C# и Java

Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы

Олимпиадная задача по программированию с решением – #4

Разберем решение олимпиадной задачи по программированию про парикмахерскую. В статье представлен алгоритм решения в текстовом виде и исходной код программы на языке C# с комментариями.

Условие задачи

В парикмахерской работает один мастер. Он тратит на одного клиента ровно 20 минут, а затем сразу переходит к следующему, если в очереди кто-то есть, либо ожидает, когда придет следующий клиент.

Даны времена прихода клиентов в парикмахерскую (в том порядке, в котором они при-ходили).

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

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

Формат входного файла

В первой строке вводится натуральное число N, не превышающее 100 — количество клиентов.

В следующих N строках вводятся времена прихода клиентов — по два числа, обозначающие часы и минуты (часы — от 0 до 23, минуты — от 0 до 59) и степень его нетерпения (неотрицательное целое число не большее 100) — максимальное количество человек, которое он готов ждать впереди себя в очереди. Времена указаны в порядке возрастания (все времена различны).

Гарантируется, что всех клиентов успеют обслужить до полуночи.

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

Формат выходного файла

В выходной файл выведите N пар чисел: времена выхода из парикмахерской 1-го, 2-го, …, N-гo клиента (часы и минуты). Если на момент прихода клиента человек в очереди больше, чем степень его нетерпения, то можно считать, что время его ухода равно времени прихода.

Алгоритм решения

Примем, что нумерация элементов в массиве начинается с нуля.

Прочитать из входного файла первую строку (это число N). Создать массив длиной N для хранения времени входа клиентов в парикмахерскую (массив элементов типа Time, DateTime или что-то в этом роде). Назовем его input. Создать массив целых чисел длиной N для хранения степени нетерпения каждого клиента. Назовем его impatience. Прочитать из входного файла N строк и заполнить прочитанными данными массивы input и impatience. Создать массив длиной N для хранения времени выхода клиентов из парикмахерской (массив элементов типа Time, DateTime или что-то в этом роде). Назовем его output. В ЦИКЛЕ for от 0 до N – 1 (по i):

1. Объявим переменную целого типа k = 0. Это количество людей в очереди перед i-м клиентом.

2. Объявим переменную целого типа kN = 0. Это расстояние в рамках массива от i-го клиента до первого в очереди перед ним.

3. Найдем эти значения путем перебора элементов массива output от i – 1 до 0 (переменная цикла j) и сравнивая значения времени с input[i]. (ЕСЛИ output[j] > input[i], ТО k = k + 1 и kN = i – j).

4. ЕСЛИ степень нетерпения i-го клиента меньше k, ТО output[i] = input[i] (значит он не будет ждать и уходит); ИНАЧЕ output[i] = input[i] + 20 минут (в начале примем, что ему возможно не нужно будет ждать очереди), далее в цикле от i – 1 до i – kN по j: ЕСЛИ output[j] > input[i] (значит i-й клиент сразу после j-го), ТО output[i] = output[j] + 20 минут и выходим из цикла по j. Вывести значения массива output в выходной файл.

Программирование на C, C# и Java

Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы

Олимпиадная задача по программированию с решением – #4

Разберем решение олимпиадной задачи по программированию про парикмахерскую. В статье представлен алгоритм решения в текстовом виде и исходной код программы на языке C# с комментариями.

Условие задачи

В парикмахерской работает один мастер. Он тратит на одного клиента ровно 20 минут, а затем сразу переходит к следующему, если в очереди кто-то есть, либо ожидает, когда придет следующий клиент.

Даны времена прихода клиентов в парикмахерскую (в том порядке, в котором они при-ходили).

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

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

Формат входного файла

В первой строке вводится натуральное число N, не превышающее 100 — количество клиентов.

В следующих N строках вводятся времена прихода клиентов — по два числа, обозначающие часы и минуты (часы — от 0 до 23, минуты — от 0 до 59) и степень его нетерпения (неотрицательное целое число не большее 100) — максимальное количество человек, которое он готов ждать впереди себя в очереди. Времена указаны в порядке возрастания (все времена различны).

Гарантируется, что всех клиентов успеют обслужить до полуночи.

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

Формат выходного файла

В выходной файл выведите N пар чисел: времена выхода из парикмахерской 1-го, 2-го, …, N-гo клиента (часы и минуты). Если на момент прихода клиента человек в очереди больше, чем степень его нетерпения, то можно считать, что время его ухода равно времени прихода.

Алгоритм решения

Примем, что нумерация элементов в массиве начинается с нуля.