Ускова О.Ф., Горбенко О.Д. и др. Олимпиадные задачи по программированию. Лучшие решения: Учебное издание. Часть 2
Подождите немного. Документ загружается.
3:r:='*';
4:r:='@';
else Writeln('Error!!!!!')
end;
s:=r+s;
end;
To5:=s;
end;
Procedure ReadFile;
{чтение исходных данных из файла Input.txt:
N - число слов на странице
a - первое слово
b - второе слово }
var s:string;
f:text;
begin
Assign(f,'input.txt');
Reset(f);
Readln(f,n);
Readln(f,a);
Readln(f,b);
Close(f);
end;
Function To10(x:string):integer;
{перевод слова языка TURBU в число от 0 до 3124
каждый символ в языке TURBU представляет собой цифру
пятеричной системы счисления от 0 до 4}
var i,pos,st,r:integer;
begin
pos:=0; st:=1;
for i:=length(x) downto 1 do
begin
case x[i] of
'#':r:=0;
'$':r:=1;
'&':r:=2;
'*':r:=3;
'@':r:=4;
else Writeln('Error!!!!!')
end;
pos:=pos+r*st;
st:=st*5;
end;
To10:=pos;
end;
Procedure DoLen5(var s:string);
{дополнение полученного слова до принятого в языке TURBU
(необходимо когда в начале слова стоит один(или несколько)
нулевой символ `#`, в этом случае код слова в десятичной
системе счисления будет меньше 625)}
begin
While length(s)<5 do s:='#'+s;
end;
Procedure WriteToFile;
{запись в файл Output.txt и расчет выходных данных }
var ttt,q,p:integer;
s1,s2:num5;
f:text;
begin
Assign(f,'output.txt');
Rewrite(f);
{расчет необходимого количества страниц}
p:=Trunc(3125/n+0.999999);
Writeln(f,p);
{расчет номера страницы, на которой находиться слово a}
q:=To10(a) div n + 1;
Writeln(f,q);
{получение первого слова на странице, на которой находиться
слово b}
ttt:=(To10(b) div n)*n;
s1:=To5(ttt);
{добавление в начало полученного слова нулевых символов языка TURBU}
DoLen5(s1);
Writeln(f,s1);
{получение последнего слова на странице, на которой находиться
слово b}
ttt:=(To10(b) div n)*n+n-1;
if ttt>3124 then ttt:=3124;
s2:=To5(ttt);
{добавление в начало полученного слова нулевых символов языка
TURBU}
DoLen5(s2);
Writeln(f,s2);
Close(f);
end;
{основная программа}
BEGIN
ReadFile;
WriteToFile;
END.
Задача 7. " Московское время "
Задача была предложена на всемирной студенческой олимпиаде по
программированию (ACM) в 1999 году. Автор решения – один из
участников четвертьфинального тура олимпиады, неоднократный
победитель межвузовских олимпиад, ныне магистрант 1 года обучения
факультета ПММ ВГУ Якубенко Андрей Павлович.
Задано время в определенном часовом поясе. Требуется определить
время, которое сейчас в Москве(GMT +0300).
Запись +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:='';
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);
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);
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
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';
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)+':'+INtToStr2(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);
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);
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 году. Ниже приводится решение призёра олимпиады Колбешкина
Дмитрия Михайловича, в настоящее время студента 5 курса факультета
ПММ.
Имеется N предприятий (N<=50) и задана матрица A размером N на N.
Каждый элемент матрицы A[I,J] показывает какую сумму денежных
средств предприятие I должно предприятию J. (Диагональные элементы
матрицы A равны нулю.)
Создать программу для устранения в матрице A всех ситуаций, когда
предприятие I должно предприятию J, а предприятие J должно
предприятию K.
При этом не имеет значения, какое предприятие какому будет должно -
важно, чтобы баланс предприятия (сумма долга или, наоборот, сумма
которую должны предприятию) не изменился.
Технические требования:
Входной файл: INPUТ.ТХТ
Выходной файл: ОUTPUТ.ТХТ
Ограничение времени: 5 секунд
Формат входных данных:
В первой строке входного файла содержится целое положительное число
N. Далее в каждой строке файла содержатся строки матрицы A. Каждая
строка содержит N положительных вещественных чисел - значений
элементов соответствующей строки матрицы A.
Формат выходных данных :
В каждой строке файла содержатся строки полученной матрицы A. Каждая
строка содержит N положительных вещественных чисел - значений
элементов соответствующей строки матрицы A.
Пример файлов входных и выходных данных:
INPUT.TXT
3
0 13.5 0
2.5 0 20
10 10 0
OUTPUT.TXT
0 1 0
0 0 0
0 0 0
Алгоритм решения
1. Подсчитаем баланс всех предприятий в отдельном массиве. Возможны
варианты:
а) предприятие никому ничего не должно (баланс = 0)
б) предприятие кому-то что-то должно (баланс < 0)
в) предприятию кто-то что-то должен (баланс > 0)
2. Находим 2 предприятия с балансами разных знаков.
3. Вычисляем сумму долга одного предприятия другому и запоминаем в
матрице.
Долг равен минимальному из двух чисел (балансов, взятых с
положительным знаком).
4. Изменяем баланс этих предприятий, предполагая что долг был
уплачен. Баланс у одного (или двух) предприятия стал = 0.
5. Если ещё остались предприятия с балансом <> 0 то возвращаемся к
пункту 2.
Program Plz1;
{Автор Колбешкин Д.М.}
Const MaxN = 50;
Var fin,fout:text;
i,j,N :integer;
t :real;
A : array[1..MaxN,1..MaxN] of real; {Матрица A}
B : array[1..MaxN] of real; {Баланс предприятий}
Begin
writeln (' Задача о неплатежах');
assign(fin,'input.txt');
assign(fout,'output.txt');
reset(fin);
rewrite(fout);
read(fin,N); {Кол-во предприятий}
for i:=1 to n do
for j:=1 to n do
read(fin,A[i,j]); {Заполняем матрицу A}
for i:=1 to N do
begin
t:=0;
for j:=1 to N do
t:=t+A[i,j]-A[j,i]; {Считаем баланс}
B[i]:=t;
end;
for i:=1 to N do
for j:=1 to N do
A[i,j]:=0; {Здесь будет ответ}
for i:=1 to N do
if B[i]>0 then {Ищем баланс>0}
begin
j:=1;
while B[i]>0 do
begin
if B[j]<0 then {Ищем баланс<0}
if B[i]<(-B[j]) then {"Считаем долг"}
begin
A[i,j]:=B[i]; {"платим" долг}
B[j]:=B[j]+B[i]; {Изменяем баланс}
B[i]:=0; {Изменяем баланс}
end else begin
A[i,j]:=-B[j]; {"платим " долг}
B[i]:=B[j]+B[i]; {Изменяем баланс}
B[j]:=0; {Изменяем баланс}
end;
j:=j+1;
end;
end;
for i:=1 to N do { Вывод ответа в файл }
begin
for j:=1 to N do
if A[i,j]=trunc(A[i,j])
then
write(fout,trunc(A[i,j]),' ')
else
write(fout,A[i,j],' ');
writeln(fout);
end;
close(fin);
close(fout);
End.
Задача 8. " О дорогах "
Эта задача предлагалась на межвузовской олимпиаде по информатике
в 1998 году. Ниже приводится решение призёра олимпиады Колбешкина
Дмитрия Михайловича – в настоящее время студента 5 курса факультета
ПММ.
Имеется N (N<=50) городов и система дорог, соединяющая эти
города. Любые два города может соединять не более одной дороги. По
любой дороге, соединяющей два города можно проехать в обе стороны.
Создать программу для определения, существуют ли города, из
которых можно выехать по одной дороге, а вернуться в них по другой.
Технические требования:
Входной файл: INPUТ.ТХТ
Выходной файл: ОUTPUТ.ТХТ
Ограничение времени: 10 секунд.
Формат входных данных:
В первой строке входного файла содержится целое положительное число
N. Далее каждая строка файла содержит два целых положительных числа
I и J, означающих, что есть дорога, соединяющая I-ый и J-ый города.
Формат выходных данных:
В выходном файле указываются целые числа - номера городов , из
которых можно выехать по одной дороге, а вернуться в них по другой.
Пример файлов входных и выходных данных:
INPUT.TXT
5
1 2
2 3
3 4
1 3
5 4
OUTPUT.TXT
1 2 3
Алгоритм решения
1. Выберем один город из списка. Этот город объявляем началом пути.
(Если городов больше нет - то переходим к пункту 5.)
Выберём одну из дорог, соединяющую этот город с другим.
(Если дорог больше нет - то переходим к пункту 1.)
Идём по выбранной дороге в следующий город.
Закрываем дорогу. Это делаем для того, что бы не пройти по ней
ещё раз.
2. Проверяем, не вернулись ли мы к началу? (Тогда все города на
нашем пути удовлетворяют условию задачи и мы их запоминаем!!!)
(Переходим к пункту 4.)
3. Выберем одну из дорог, соединяющую этот город с другим, в котором
ещё нет флага. (Если дорог больше нет - то переходим к пункту 4.)
Перед уходом ставим флаг. Он означает что город уже БЫЛ у нас на
пути.
Идём по выбранной дороге в следующий город. (Переходим к пункту
2.)
4. По своим следам возвращаемся в предыдущий город.
Если мы вернулись НЕ к началу пути то:
Убираем флаг. (Переходим к пункту 3.)
Если мы вернулись к началу пути то:
Открываем дорогу по которой вернулись. (Переходим к пункту 1.)
5. Все нужные города найдены...
*)
Program Plz2;
{Автор Колбешкин Д.М.}
Const MaxN = 50;
Var i,j,N,t : byte;
fin,fout : text;
a : array [1..MaxN,1..MaxN] of byte; {Матрица дорог}
b : array [1..MaxN] of byte; {Запоминаем путь}
c : array [1..MaxN] of byte; {Формируем ответ}
Procedure Rekurs(k:byte); {k - город, в котором мы сейчас}
var l:byte; {l - город, в который думаем
сходить}
begin {i - начало пути}
if k=i then {Мы вернулись к началу?}
begin
c[i]:=1;
for t:=1 to N do
if b[t]=1 then c[t]:=1
end
else
for l:=1 to N do {Смотрим - есть ли дорога к
новому городу?}
if (a[k,l]<>0) and (b[l]=0) and (c[i]=0) then
begin
b[k]:=1; {Ставим влаг перед уходом}
Rekurs(l); {Идём в следующий город}
b[k]:=0; {Убираем флаг при обратном пути}
end;
end;
Begin
writeln (' Задача о дорогах ');
assign(fin,'input.txt');
assign(fout,'output.txt');
reset(fin);
rewrite(fout);
read(fin,n);
for i:=1 to N do
for j:=1 to N do
a[i,j]:=0;
for i:=1 to N do
b[i]:=0;
for i:=1 to N do
c[i]:=0;
while not Eof(fin) do {Составляем карту дорог}
begin
readln(fin,i,j);
a[i,j] := 1;
a[j,i] := 1;
end;
for i:=1 to N do
for j:=1 to N do
if (c[i]=0)and(a[i,j]=1) then
begin
a[i,j]:=0; {Закрываем дорогу}
a[j,i]:=0; {Закрываем дорогу}
Rekurs(j); {Идём в следующий город}
a[i,j]:=1; {Открываем дорогу}
a[j,i]:=1; {Открываем дорогу}
end;
for i:=1 to N do
if c[i]=1 then write(fout,i,' ');
close(fin);
close(fout);
End.
Задача 9. " ДЕНЬГИ "
Эта задача предлагалась на факультетской олимпиаде по информатике
в 1999 году. Ниже приводится решение призёра олимпиады Колбешкина
Дмитрия Михайловича – в настоящее время студента 5 курса факультета
ПММ.
Имеется денежная сумма в N единиц. Требуется написать программу
для определения, можно ли представить данную сумму денег купюрами