Сайт Льва Волкова
  
· Река Коси (Индия) ежегодно прокладывает себе новое русло. Общий объем наносов - 116 млн м3/г, можно наполнить 8 млн. вагонов.
 
      На главную  
 Личное
  Статьи
  Задачи 
 Ссылки
 АТ-531
www.levvol.ru    
 

Муниципальный этап Всероссийской олимпиады по информатике. Московская область. 29 ноября 2009 г.

Задача № 3. Ресторан

Оценка 25 баллов.

В популярном ресторане быстрого питания «Вилы» есть 10 столиков. Все столики пронумерованы (от 1 до 10) и за каждым столиком может сидеть до четырех человек. В ресторан в определенное время Xi приходит компания из Рi человек (от 1 до 4). При этом известно время ухода данной компании Fi.

Компания выбирает себе столик, за которым сидит минимально возможное количество человек (возможно, 0). Если таких столиков несколько, то из всех таких столиков они выбирают столик с минимальным номером. Если же столика, куда бы они поместились, найти не удается, то компания разворачивается и уходит в конкурирующий ресторан «Бе-бе».

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

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

В первой строке входного файла input.txt содержится целое число N (1≤N≤1000) — количество компаний, которые приходят в ресторан. В следующих N строках задаются по три числа через пробел — количество человек в компании Рi (1≤Р≤4), время прихода копании Xi и время ухода компании Yi(0≤XiYi≤30000). Время задается целым числом. Компании вводятся в порядке возрастания времени прихода. Все компании приходят в разное время.

В последней строке файла задается число К — номер посетителя, столик для которого требуется определить.

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

На экран вывести одно число — номер столика, за которым окажется К-ый человек. Если столик для компании, куда входит данный человек, подобрать не удастся, то выведите 0.

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

Ввод Вывод
3
2 1 5
1 2 4
4 3 6
5
3
3
2 1 3
1 2 3
4 3 6
5
1

Ршение



Program Olimp3(input);
Uses CRT;
Type r_type=record
num, tb, te, table:integer;
end;
Label 1;
Var x:array [1..1000] of r_type;
i,j,k,m,n,p,bt,et,tab :integer;
b :boolean;
Begin
ClrScr;
{Файловые операции. Открытие файла}
Assign(input,'input.txt'); Reset(input);
{Вввод данных}
readln(n); {Число компаний}
m:=1; tab:=0; x[1].table:=tab;
for k:=1 to n do begin
{количество людей в компании,
время прихода, время ухода}

readln(p,bt,et);
if (tab>10) or (p>4) then begin
writeln('нет мест');
goto 1;
end;
i:=1; b:=true; tab:=tab+1;
{поиск освободтвшихся столиков}
while (i<=m-1) and (b) do begin
if x[i].te<=bt then begin
tab:=x[i].table;
b:=false;
end;
i:=i+1;
end;
{усаживание компании за столик}
for i:=1 to p do begin
with x[m] do begin
num:=m;
tb:=bt;
te:=et;
table:=tab;
end;
m:=m+1;
end;
1: end;
{ввод числа к - номера посетителя}
readln(k);
{вывод результата}

writeln('----------------------------');
writeln(x[k].table);
Close(input);
End.

Скачать эту программу

<<<Задача 2 | Назад |  Задача 4 >>>