Олимпиада по
программированию (2003-2004 учебный год, районно-городской тур)
1. Разложение (15 баллов, 10 сек на тест)
Альберт хочет
представить некоторое целое положительное число N в виде сумме квадратов двух целых
положительных чисел P и
Q (0<P<=Q). Это не всегда возможно. Если точного
разложения не существует, Альберту нужно подобрать такие P и Q, чтобы значение выражения |N–P2–Q2| было
минимальным. Если существует несколько вариантов разложения, минимизирующих
значение указанного выражения, то вывести вариант с меньшим Q.
Напишите
программу, которая вводит с клавиатуры целое число N (1<=N<=106) и выводит на экран
целые значения P и Q.
Пример ввода:
14
Пример вывода:
2 3
Решение:
Требуется
выполнить двойной цикл по P
и Q и выбрать числа P и Q, минимизирующие указанное выражение, а
для одинакового значения выражения – с меньшим Q. Так как N<=106, то нужно
рассматривать P и Q, не превышающие тысячи,
т.е. внутренняя часть цикла выполняется около 500 000 раз. Рекомендуется для P и Q использовать тип longint, чтобы не происходило
переполнение при возведении в квадрат.
Программа:
var
z,p,q,mind,minp,minq,maxp,d:longint;
begin
read(z);
mind:=1000000;
maxp:=trunc(sqrt(z));
for p:=1
to maxp do
for q:=p to maxp do
begin
d:=abs(z-p*p-q*q);
if (d<mind) or ((d=mind) and
(minq>q)) then
begin
mind:=d;
minp:=p;
minq:=q;
end;
end;
writeln(minp,' ',minq);
end.
Тесты жюри:
|
Ввод
|
Правильный
ответ
|
Оценка
за правильный ответ
|
|
25
|
3 4
|
3
|
|
2581
|
30 41
|
3
|
|
9
|
2 2
|
3
|
|
9999
|
60 80
|
3
|
|
888888
|
534 777
|
3
|
2. Игра (20 баллов, 5 сек на тест)
Двое играют в
следующую игру. Сначала с помощью компьютера генерируется случайное целое число
N0,
состоящее из двух или более цифр. Затем игроки ходят по очереди, соблюдая
следующие правила. Игрок, делающий i-ый ход, должен назвать новое число Ni, строго меньшее числа Ni-1,
но большее или равное сумме цифр числа Ni-1. Если игрок не может сделать ход по
правилам, то он проигрывает. Например, пусть N0=98. Первый игрок должен назвать число от 17 до 97.
Если он назовет 17, то второй игрок назовет 8 и выиграет. Если он назовет 19,
то второй игрок должен будет выбрать число от 10 до 18, и какое бы число второй
игрок не назвал, первый игрок сможет назвать 9 и выиграть.
Напишите
программу, которая вводит с клавиатуры натуральное число N0 (10<=N<10101) и выводит на
экран число N1
– ход, который позволит выиграть первому игроку при безошибочной игре
противников. Если выигрышный ход не существует, то программа должна вывести 0.
Пример ввода:
98
Пример вывода:
19
Решение:
Решение задачи
требует математических рассуждений. В указанном диапазоне существуют три числа N, а именно 19 (минимальное
число с суммой цифр 10), 299 (минимальное число с суммой цифр 20) и
3999999999999999999999999999999999 (минимальное число с суммой цифр 300),
которые являются проигрышными для игрока, делающего первый ход. Принцип
рассуждения показан в задаче. Например, для числа 299 следующее число нужно
выбирать в диапазоне от 20 до 298. Независимо от выбора следующий игрок может назвать
число 19. Если начальное число N
отличается от указанных чисел, то в качестве выигрышного хода нужно выбрать
одно из этих чисел в зависимости от суммы цифр числа N.
Программа:
var s:string;
ns,i:integer;
begin
readln(s);
ns:=0;
for i:=1 to
length(s) do
ns:=ns+(ord(s[i])-ord('0'));
if (s='19')
or (s='299') or
(s='3999999999999999999999999999999999') then
writeln('0')
else if
ns<=9 then
writeln('9')
else if
ns<=19 then
writeln('19')
else if
ns<=299 then
writeln('299')
else
writeln('3999999999999999999999999999999999');
end.
Тесты жюри:
|
Ввод
|
Правильный
ответ
|
Оценка
за правильный ответ
|
|
18
|
9
|
3
|
|
399
|
299
|
3
|
|
398
|
299
|
3
|
|
298
|
19
|
2
|
|
2999999999999999999999999999999999
|
299
|
3
|
|
12999999999999999999999999999999999
|
3999999999999999999999999999999999
|
4
|
|
3999999999999999999999999999999999
|
0
|
2
|
3. Сортировка (25 баллов, 5 сек на тест)
Напишите
программу, которая вводит с клавиатуры строку длиной от 1 до 25 символов,
состоящую из прописных латинских букв, и выводит на экран минимальное
количество обменов, которые необходимо сделать в этой строке, чтобы
отсортировать буквы строки в алфавитном порядке. Обмен – это перестановка двух
букв. Например, чтобы отсортировать буквы строки BAZAR, нужно сделать 3 обмена. Сначала
можно поменять местами 3 и 5 букву (BARAZ), затем 3 и 4 буквы (BAARZ), и, наконец, 1 и 3 буквы (AABRZ).
Пример ввода:
BAZAR
Пример вывода:
3
Решение:
Выполняем рекурсивный
перебор всех вариантов обмена с оптимизацией. Жадный алгоритм, который выбирает
любой подходящий обмен не приводит к успеху.
Программа: другие варианты
var st:string;
ss:string;
n:integer;
procedure sortstr(var s:string);
{ сортировка строки методом
вставок }
var i,j:integer;
c:char;
begin
for i:=1 to
length(s) do
begin
j:=i-1;
while
j>=1 do
begin
if
s[j+1]<s[j] then
begin
c:=s[j+1];
s[j+1]:=s[j];
s[j]:=c;
end
else
break;
dec(j);
end;
end;
end;
function nobmen(from:integer):integer;
{ минимальное количество
обменов }
var i,j,o,om:integer;
ch:char;
lc:set of
'A'..'Z';
begin
{ символы от 1 до from уже стоят на своих местах }
nobmen:=0;
for i:=from+1
to n do
if (st[i]<>ss[i])
then
begin
om:=100;
lc:=[];
for j:=i+1 to n do
{ подбираем символ, который должен
стоять в позиции i
нужно рассмотреть все варианты,
не рассматриваем варианты, эквивалентные
предыдущим }
if (st[j]=ss[i]) and
(st[j]<>ss[j]) and not (ss[j] in lc) then
begin
include(lc,ss[j]);
ch:=st[i]; { обмен }
st[i]:=st[j];
st[j]:=ch;
o:=1+nobmen(i);
ch:=st[i]; { обратный
обмен }
st[i]:=st[j];
st[j]:=ch;
if om>o then om:=o; { если лучше, то запомним }
end;
nobmen:=om;
exit;
end;
end;
begin
readln(st);
ss:=st;
sortstr(ss);
n:=length(st);
writeln(nobmen(0));
end.
Тесты жюри:
|
Ввод
|
Правильный
ответ
|
Оценка
за правильный ответ
|
|
А
|
0
|
2
|
|
ACDC
|
1
|
2
|
|
ZABCDEFGHIJKLMNOPQRSTUVWX
|
24
|
3
|
|
DDAABBCC
|
6
|
4
|
|
EEEECBDA
|
4
|
4
|
|
CFBEDAAAAA
|
5
|
4
|
|
TILITILITRALIVALIPARAMPAM
|
12
|
6
|
4. Дерево (30 баллов, 5 сек на тест)
Напишите программу,
которая с клавиатуры вводит строку длиной от 1 до 80 символов, содержащую
арифметическое выражение, и выводит его структуру “графически” в виде дерева.
Арифметическое
выражение состоит из переменных (обозначаемых одной прописной латинской
буквой), знаков арифметических действий (+, –, *, /), и круглых скобок.
Приоритет операций * и / выше, чем у операций + и –. Все операции являются
левоассоциативными, т.е. выражение A+B+C интерпретируется как (A+B)+C, а не A+(B+C). Скобки изменяют порядок вычислений.
Операция смены знака не используется. Арифметическое выражение корректно и не
содержит никаких других символов, кроме указанных, в том числе пробелов. При
выводе структуры выражения используется схема на рисунке. Для изображения
вертикальных линий используется символ ‘|’ (вертикальная черта), а для
горизонтальных – символ ‘_’ (подчеркивание).
Пример ввода:
A+B-C*D
Пример вывода:
-
|_+
| |_A
| |_B
|_*
|_C
|_D
Решение:
Для получения
структуры выражения используется рекурсивный синтаксический разбор. После этого
выражение печатается достаточно простой подпрограммой.
Программа:
type pitem=^item;
item=record
fl:boolean; {переменная или выражение}
op:char; {имя переменной или знак операции}
left:pitem;
right:pitem;
end;
var s:string;
i:integer;
e:pitem;
function loadexpr(var i:integer):pitem; forward;
function loadfactor(var i:integer):pitem; { множитель }
var rz:pitem;
begin
if s[i]='('
then
begin
inc(i); { пропускаем ‘(‘ }
rz:=loadexpr(i);
inc(i); { пропускаем ‘(‘ }
end
else
begin { имя переменной }
new(rz);
rz^.fl:=false;
rz^.op:=s[i];
rz^.left:=nil;
rz^.right:=nil;
inc(i);
end;
loadfactor:=rz;
end;
function loadterm(var i:integer):pitem; { слагаемое }
var lt,rt,rz:pitem;
op:char;
begin
rz:=loadfactor(i);
while
(i<=length(s)) and ((s[i]='*') or (s[i]='/')) do
begin
op:=s[i];
inc(i);
rt:=loadfactor(i);
lt:=rz;
new(rz);
rz^.fl:=true;
rz^.op:=op;
rz^.left:=lt;
rz^.right:=rt;
end;
loadterm:=rz;
end;
function loadexpr(var i:integer):pitem; { выражение }
var lt,rt,rz:pitem;
op:char;
begin
rz:=loadterm(i);
while
(i<=length(s)) and ((s[i]='+') or (s[i]='-')) do
begin
op:=s[i];
inc(i);
rt:=loadterm(i);
lt:=rz;
new(rz);
rz^.fl:=true;
rz^.op:=op;
rz^.left:=lt;
rz^.right:=rt;
end;
loadexpr:=rz;
end;
procedure printitem(e:pitem;p,a:string); { печать выражения e
p
и a – это префиксы, которые
нужно выводить перед операцией и
ее аргументами }
begin
write(p);
writeln(e^.op);
if e^.fl then
begin
printitem(e^.left,a+'|_',a+'| ');
printitem(e^.right,a+'|_',a+'
');
end;
end;
begin
readln(s);
i:=1;
e:=loadexpr(i);
printitem(e,'','');
end.
Тесты жюри:
|
Ввод
|
Правильный
ответ
|
Оценка
за правильный ответ
|
|
Z
|
Z
|
5
|
|
A*B
|
*
|_A
|_B
|
5
|
|
T+B*С
|
+
|_T
|_*
|_B
|_C
|
5
|
|
(A+B)*F
|
*
|_+
| |_A
| |_B
|_F
|
5
|
|
(X+Z)*(U-V)-(A+B*T)*С/D*K+(H-G)
|
+
|_-
| |_*
| | |_+
| | | |_X
| | | |_Z
| | |_-
| | |_U
| | |_V
| |_*
| |_/
| | |_*
| | | |_+
| | | | |_A
| | | | |_*
| | |
| |_B
| | |
| |_T
| | | |_С
| | |_D
| |_K
|_-
|_H
|_G
|
10
|