Ускова О.Ф., Горбенко О.Д. Олимпиадные задачи по программированию. Лучшие решения. Часть 3
Подождите немного. Документ загружается.
51
Запись +0300 означает, что время в данном
часовом поясе отличается от времени по
Гринвичу на +03 часа 00 минут.
формат входных данных:
файл input.txt:
SUN, 03 DEC 1996 09:10:35 +0100
формат выходных даных:
файл output.txt:
SUN, 03 DEC 1996 11:10:35 +0300
Program Moscow;
Const DayMonth:array[1..12] of
integer=(31,28,31,30,31,30,31,31,30,31,30,31);
{сколько дней в каком месяце}
var day,date,month,year,hour,min,sec:integer;
{считанные день, число, месяц, год, час,
минуты, секунды}
inch,incmin:integer;
{указывает считанный часовой пояс}
f:text;
{указатель на файл для чтения и записи}
Procedure GetNext(s:string;var i:integer;var
r:string);
{выделяет слово из строки}
begin
r:='';
52
while (i<=length(s)) and (s[i] in [' ', ','
, ':' ]) do inc(i);
while (i<=length(s)) and not (s[i] in [' ',
',' , ':' ]) do
begin
r:=r+s[i];
inc(i);
end;
end;
Procedure ReadF;
{считывает файл input.txt}
var s,r:string; {переменные для хранения
всей строки и 1 слова}
i:integer; {указатель на тек. позицию}
err:integer; {признак ошибки при
распознавании чисел(не проверяется)}
begin
Assign(f,'input.txt');
Reset(f);
i:=1;
Read(f,s);
GetNext(s,i,r);
if r='MON' THEN DAY:=1;
if r='TUE' THEN DAY:=2;
if r='WED' THEN DAY:=3;
if r='THU' THEN DAY:=4;
if r='FRI' THEN DAY:=5;
if r='SAT' THEN DAY:=6;
if r='SUN' THEN DAY:=7;
GetNext(s,i,r);
Val(r,date,err);
53
GetNext(s,i,r);
if r='JAN' THEN MONTH:=1;
if r='FEB' THEN MONTH:=2;
if r='MAR' THEN MONTH:=3;
if r='APR' THEN MONTH:=4;
if r='MAY' THEN MONTH:=5;
if r='JUN' THEN MONTH:=6;
if r='JUL' THEN MONTH:=7;
if r='AUG' THEN MONTH:=8;
if r='SEP' THEN MONTH:=9;
if r='OCT' THEN MONTH:=10;
if r='NOV' THEN MONTH:=11;
if r='DEC' THEN MONTH:=12;
GetNext(s,i,r);
Val(r,year,err);
if length(r)=2 then year:=year+1900;
GetNext(s,i,r);
Val(r,hour,err);
GetNext(s,i,r);
Val(r,min,err);
GetNext(s,i,r);
Val(r,sec,err);
GetNext(s,i,r);
if length(r)=5 then begin
Val(Copy(r,2,2),inch,err);
54
Val(Copy(r,4,2),incmin,err);
if s[1]='-' then
begin
inch:=-inch;
incmin:=-incmin;
end;
end
else
begin
if r='UT' then begin inch:=00;
incmin:=00; end;
if r='GMT' then begin inch:=00;
incmin:=00; end;
if r='EDT' then begin inch:=-4;
incmin:=00; end;
if r='CDT' then begin inch:=-5;
incmin:=00; end;
if r='MDT' then begin inch:=-6;
incmin:=00; end;
if r='PDT' then begin inch:=-7;
incmin:=00; end;
end;
INCH:=3-INCH;
INCMIN:=-INCMIN;
Close(f);
end;
Function IntToStr(x:integer):string;
{перевод из числа в строу}
var r:string; {временная переменная }
begin
55
Str(x,r);
IntToStr:=r;
end;
Function IntToStr2(x:integer):string;
{перевод из числа в строку длиной 2}
var r:string;
begin
Str(x,r);
if length(r)=1 then r:='0'+r;
IntToStr2:=r;
end;
Procedure WriteF;
{запись файла}
var s,r:string; {временные переменные для
хранения строки и 1 слова}
begin
Assign(f,'output.txt');
ReWrite(f);
s:='';
if DAY=1 THEN r:='MON';
if DAY=2 THEN r:='TUE';
if DAY=3 THEN r:='WEN';
if DAY=4 THEN r:='THU';
if DAY=5 THEN r:='FRI';
if DAY=6 THEN r:='SAT';
if DAY=7 THEN r:='SUN';
s:=s+r+', '+IntToStr2(date);
Case month of
1:r:='JAN';
56
2:r:='FEB';
3:r:='MAR';
4:r:='APR';
5:r:='MAY';
6:r:='JUN';
7:r:='JUL';
8:r:='AUG';
9:r:='SEP';
10:r:='OCT';
11:r:='NOV';
12:r:='DEC';
end;
s:=s+' '+r+' '+INtToStr(year)+'
'+IntToStr2(hour)+':'+INtToStr2(min)+':'+INtTo
Str2(sec)+' +0300';
Writeln(f,s);
Close(f);
end;
Function LeapYear(x:integer):boolean;
{проверка на високосный год}
begin
LeapYear:=((x mod 4 =0) and (x mod 100<>0)) or
(x mod 400=0)
end;
Procedure Incr;
{изменение даты}
var month1:integer; {используется для
вычилсения даты}
begin
inc(min,incmin);
57
if min>=60 then begin inc(hour); min:=min-60
end;
if min<0 then begin dec(hour); min:=min+60
end;
inc(hour,inch);
if hour>=24 then begin inc(day); inc(date);
hour:=hour-24 end;
if hour<0 then begin hour:=hour+24;
dec(day); dec(date) end;
{день недели}
if day<=0 then day:=day+7;
if day>7 then day:=day-7;
{день месяца}
if (month<>2) or not LeapYear(year) then
begin
if date>daymonth[month] then begin
date:=1; Inc(month) end;
if date<=0 then
begin
{сдвинуть месяц на 1 назад}
dec(month);
if leapyear(year) and (month=2)
then day:=29
else begin
month1:=month;
if month1<=0 then
inc(month1,12);
if month1>12 then
dec(month1,12);
58
day:=Daymonth[month1];
end;
end;
end
else
begin
if date>29 then begin date:=1;
Inc(month) end;
if date<=0 then
begin
{сдвинуть месяц на 1 назад}
dec(month);
day:=31;
end;
end;
{проверить месяц}
if month<=0 then begin Dec(year);
month:=12; end;
if month>12 then begin Inc(year);
month:=1; end;
end;
BEGIN
ReadF;
Incr;
WriteF;
END.
Задача 7. " Дороги "
Эта задача предлагалась на межвузовской
олимпиаде по информатике в 1998 году. Ниже
приводится решение призёра олимпиады
59
Колбешкина Дмитрия Михайловича – в настоящее
время аспиранта факультета ПММ.
Имеется N (N<=50) городов и система дорог,
соединяющая эти города. Любые два города может
соединять не более одной дороги. По любой
дороге, соединяющей два города можно проехать
в обе стороны.
Создать программу для определения ,
существуют ли города, из которых можно выехать
по одной дороге, а вернуться в них по другой.
Технические требования:
Входной файл: INPUТ.ТХТ
Выходной файл: ОUTPUТ.ТХТ
Ограничение времени: 10 секунд.
Формат входных данных:
В первой строке входного файла содержится
целое положительное число N. Далее каждая
строка файла содержит два целых положительных
числа I и J, означающих , что есть дорога,
соединяющая I-ый и J-ый города.
Формат выходных данных:
В выходном файле указываются целые числа -
номера городов, из которых можно выехать по
одной дороге, а вернуться в них по другой.
Пример файлов входных и выходных данных:
INPUT.TXT
60
5
1 2
2 3
3 4
1 3
5 4
OUTPUT.TXT
1 2 3
Алгоритм решения
1. Выберем один город из списка. Этот город
объявляем началом пути.
(Если городов больше нет - то переходим к
пункту 5.)
Выберём одну из дорог, соединяющую этот
город с другим.
(Если дорог больше нет - то переходим к
пункту 1.)
Идём по выбранной дороге в следующий
город.
Закрываем дорогу. Это делаем для того, что
бы не пройти по ней ещё раз.
2. Проверяем, не вернулись ли мы к началу?
(Тогда все города на нашем пути удовлетворяют
условию задачи и мы их запоминаем!!!)
(Переходим к пункту 4.)
3. Выберем одну из дорог, соединяющую этот
город с другим, в котором ещё нет флага. (Если
дорог больше нет - то переходим к пункту 4.)