СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости




Задания
Версия для печати и копирования в MS Word
Задание 27 № 7420

На вход программе подаются сведения о посетителях, желающих попасть в популярное кафе. В первой строке сообщается число желающих N, которое не меньше 10, но не превосходит 1000, и количество столиков, которое не меньше 10, но не превосходит 1000. Каждая из следующих N строк имеет следующий формат:

 

<Фамилия> <время прихода> < время ухода>,

 

где <Фамилия> — строка, состоящая не более чем из 20 символов; <время прихода> — через двоеточие два целых числа, соответствующие часам (от 00 до 23 — ровно 2 символа) и минутам (от 00 до 59 — ровно 2 символа); <время ухода> имеет тот же формат. <Фамилия> и <время прихода>, а также <время прихода> и <время ухода> разделены одним пробелом.

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

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

 

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

3 10

Иванов 09:45 12:00

Петров 10:00 11:00

Сидоров 12:00 13:12

 

Результат работы программы на этих входных данных:

Иванов 1

Петров 2

Сидоров 1

Решение.

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

 

Пример правильной и эффективной программы на языке Паскаль:

 

var p:array[1..1000] of integer;

c,c1:char;

i,j,N,K:integer;

name:string;

time1,time2:integer;

begin

readln(N,K);

for i:=1 to K do

p[i]:=0;

for i:=1 to N do

begin

name:='';

repeat

read(c);

name:=name+c

until c=' '; {cчитана фамилия}

read(c,c1); {cчитаны чаcы первого времени}

time1:=60*((ord(c)-ord('0'))*10+ ord(c1)-ord('0'));

read(c,c,c1); {пропущено двоеточие, и cчитаны минуты}

time1:=time1+(ord(c)-ord('0'))*10+ord(c1)-ord('0');

read(c,c,c1); {cчитаны чаcы второго времени}

time2:=60*((ord(c)-ord('0'))*10+ ord(c1)-ord('0'));

readln(c,c,c1); {пропущено двоеточие, и cчитаны минуты}

time2:=time2+(ord(c)-ord('0'))*10+ord(c1)-ord('0');

for j:=1 to K do

if p[j]<=time1 then

begin

p[j]:=time2;

writeln(name,' ',j);

break;

end

end;

end.

 

 

Пример правильной и эффективной программы на языке Бейсик:

 

DIM p(1000) AS INTEGER

DIM s AS STRING

DIM nm AS STRING

INPUT n

INPUT k

FOR i = 1 TO k

p(i) = 0

NEXT i

FOR j = 1 TO n

LINE INPUT s

c$ = MID$(s, 1, 1)

i = 1

WHILE NOT (c$ = " ")

i = i + 1

c$ = MID$(s, i, 1)

WEND

nm = MID$(s, 1, i)

time1 = (ASC(MID$(s, i + 1, 1)) - ASC("0")) * 60 * 10

time1 = time1 + (ASC(MID$(s, i + 2, 1)) - ASC("0")) * 60

time1 = time1 + (ASC(MID$(s, i + 4, 1)) - ASC("0")) * 10

time1 = time1 + (ASC(MID$(s, i + 5, 1)) - ASC("0"))

time2 = (ASC(MID$(s, i + 7, 1)) - ASC("0")) * 60 * 10

time2 = time2 + (ASC(MID$(s, i + 8, 1)) - ASC("0")) * 60

time2 = time2 + (ASC(MID$(s, i + 10, 1)) - ASC("0")) * 10

time2 = time2 + (ASC(MID$(s, i + 11, 1)) - ASC("0"))

FOR i = 1 TO k

IF time1 >= p(i) THEN

p(i) = time2

PRINT nm, i

GOTO 10

ENDIF

NEXT i

10 NEXT j

END

Источник: ЕГЭ по ин­фор­ма­ти­ке 08.05.2014. До­сроч­ная волна, ре­зерв­ный день. Ва­ри­ант 201.