Олимпиадные задачи: Спортивное программирование (олимпиадные задачи на олимпиаде по специальности "Компьютерные системы и сети", апрель - 2014 год).

Олимпиадный тест на тему: "Спортивное программирование" (олимпиадные задачи на олимпиаде по специальности "Компьютерные системы и сети", апрель - 2014 год."

Общие сведения

Входные данные вводятся через стандартный поток ввода, а результаты выводятся без лишних пробелов и переводов строк через стандартный поток вывода.

Входные данные на корректность проверять только тогда, когда это требуется по условию задачи.

Задача A. Робот-прыгун

В некотором институте был разработан одноногий робот-прыгун, который может прыгать на расстояние R1 (режим 1) или R2 (режим 2). После каждого прыжка режим меняется с режима 1 на режим 2, а с режима 2 на режим 1. R1 – любое число из интервала [A;B], R2 – из интервала [C;D]. A, B, C и D – натуральные числа не более 1000 и A не более B, C не более D и В меньше С.

На испытательном полигоне робот должен за минимальное количество прыжков преодолеть полосу препятствий, перемещаясь по некоторым из N свободных площадок, заданных координатами ( x[1];y[1] ), (x[2];y[2]), … , (x[N];y[N]). Начало движение - площадка 1 и режим R1, конец – площадка N. N – не более 10000 и не менее 2, а коордитаты – вещественные числа из интервала [-1000; 1000]. Если достичь N–ю площадку робот не может – ответ равен -1.

Время решения задачи – 3 сек.

Входные данные: первая строка из 4-х чисел, записанных через пробел ( А В С D ),

вторая строка – число N,

затем N строк по два числа, записанных через пробел ( X[i] Y[i] ).

Выходные данные: одно число – минимальное количество прыжков.

Пример

Вход

1 8 11 25

1.5 2

5 6

20 4.5

15.6 15

10 10

Выход

РЕШЕНИЕ

//program A;

//const Eps=0.00001;

var X,Y:array[1..10000] of real;

Stack:array[1..20000] of integer;

R1,R2:array[1..10000] of integer;

K,Ns1,Ns2,N,i:integer;

A,B,C,D:real;

procedure rd;

var i:integer;

begin

readln(A,B,C,D);

readln(N);

A:=A*A; B:=B*B; C:=C*C; D:=D*D;

for i:=1 TO N DO BEGIN

readLN(X[i],Y[i]);

// X[i]:=random(1000); // Y[i]:=random(1000);

end;

//X[N]:=1000;Y[N]:=2000;

R1[1]:=1; Ns1:=1;Ns2:=2;

Stack[1]:=1;

//for i:=1 to N do writeln(X[i]:10:0,Y[i]:10:0);

end;

function len(R,i,j:integer):boolean;

var t:real;

begin

len:=false;

t:=sqr(X[i]-X[j])+sqr(Y[i]-Y[j]);

if R=1 then len:=(A<=t) and (t<=B);

if R=2 then len:=(C<=t) and (t<=D);

end;

procedure stepall();

var i,j,k,R,NN:integer; S:real;

begin

while(Ns1 < Ns2)do begin

i:=Stack[Ns1];

if R1[i]>R2[i] then begin R:=1;NN:=R1[i];end;

if R2[i]>R1[i] then begin R:=2;NN:=R2[i];end;

j:=1;

while j<=N do begin

if (i=j) or ((R=1)and(R2[j]>0)) or

((R=2)and(R1[j]>0)) or(not Len(R,i,j)) then begin inc(j);continue;end;

if R=1 then R2[j]:=NN+1 else R1[j]:=NN+1;

Stack[ns2]:=j; inc(Ns2);

// write(ns2,'+');

if j=N then exit;

inc(j);

end;

inc(Ns1);

// write(Ns1,'=');

end;

begin

rd();

stepall;

//for k:=1 to N do writeln(k:3,r1[k]:5,r2[k]:5);

if R1[N]>R2[N]then K:=R1[N];

if R2[N]>R1[N]then K:=R2[N];

if R1[N]=R2[N]then K:=0;

write(K-1);

// readln;

end.

Тесты

1) Вход

100 110 500 1000

1 1

105 2

150 700

Выход

2) Вход

2 7 11 19

1 7

19 7

Выход

-1

3) Вход

40 60 240 260

0 0

1200 50

50 0

300 0

350 0

600 0

300 250

350 50

650 0

900 0

950 0

1200 0

1450 0

Выход

4) Вход

1 12 13 25

0 -30

0 -20

0 0

10 0

-10 0

0 20

Выход

Остальные тесты по задаче "A" Вы можете скачать по следующей ссылке: Скачать тесты

Задача В. Сумма

Найти сумму двух целых N-ричных чисел. N принимает значение от 2-х до 10. Разрядность чисел не более 255.

Время решения задачи – 0.5 сек.

Входные данные: первая строка – основание системы счисления N,

вторая строка – первое слагаемое,

третья строка – второе слагаемое.

Выходные данные: значение суммы.

Пример

Вход

12201

2210

Выход

22111

РЕШЕНИЕ

program B;

//{$APPTYPE CONSOLE}

//uses SysUtils;

var s,s1,s2:string;

c,a,a1,a2,i,k,p,k1,k2:integer;

begin

readln(p); readln(s1); readln(s2);

s1:='0'+s1; s2:='0'+s2;

k1:=length(s1); k2:=length(s2);

if k1 < k2 then

for i:=1 to k2-k1 do s1:='0'+s1;

if k1>k2 then

for i:=1 to k1-k2 do s2:='0'+s2;

k:=k1; if k1 < k2 then k:=k2;

c:=0;

s:='000000000000000000000000000000';

s:=s+s+s+s+s+s+s+s;

delete(s,k+1,300);

for i:=k downto 1 do begin

a1:=ord(s1[i])-48;

a2:=ord(s2[i])-48;

a:=a1+a2+c;

c:=a div p; a:=a mod p;

s[i]:=chr(a+48);

end;

if s[1]='0' then delete(s,1,1);

write(s);

// readln;

end.

Тесты:

1) Вход

12201

2210

Выход

22111

2) Вход

Выход

3) Вход

777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777

Выход

1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

4) Вход

888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

Выход

1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

5) Вход

100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Выход

1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

6) Вход

73629971648982648500032927950908372387697444444444444444444444444444444444444430807478748787327648273648273648848484848484844848484844949494949494949494949494949494949403030303030303030303030303003300

13333333333333333333333777777777777777777777777774444444444444444444444444999999999999999999955555555555555555555555555550000000000000000000000000000000000000555559999999999999999999999999494949493488

Выход

86963304982315981833366705728686150165475222222218888888888888888888888889444430807478748787283203829203829204404040404034844848484844949494949494949494949495505054949403030303030303030302525252496788

Задача С. Отрезки

На числовой оси задано N отрезков своей левой и правой границей. Найти такую точку на числовой оси, для которой сумма длин и частей длин отрезков слева от нее была бы равна сумме длин и частей длин отрезков справа. Часть длины отрезка учитывается, если искомая точка делит отрезок на две части – левую и правую. N – натуральное число не превышающее 10000. Координаты левой границы каждого отрезка меньше координаты правой границы. Координаты границ – целые числа, не превышающие 10000 по модулю. Если решений несколько, то результатом считать самую левую точку из них.

Время решения задачи - 1 сек.

Входные данные: первая строка содержит число N. Каждая из N последующих строк содержит по 2 числа, записанных через пробел ( координаты левой и правой границ отрезка).

Выходные данные: единственное число – найденная координата точки с точностью до 0.01.

Пример

Вход

-15 15

0 20

0 3

Выход

4.25

РЕШЕНИЕ

program C;

const Eps=0.000001;

var X,Y:array[1..15000] of real;

N,i:integer;

S,K,R,KK,RL,RR:real;

procedure sort;

var i,j:integer; r:real;

begin

for i:=1 to N-1 do begin

r:=-1;

for j:=1 to N-i do begin

if(X[j]>X[j+1])then begin

r:=X[j];X[j]:=X[j+1];X[j+1]:=r;

r:=Y[j];Y[j]:=Y[j+1];Y[j+1]:=r;

end;

if(r < 0) then break;

end

end;

procedure rd;

var i:integer;

begin

readln(N);

for i:=1 TO N DO BEGIN

READLN(X[i],Y[i]);

// X[i]:=random(1000);

// Y[i]:=X[i]+random(1000);

K:=K+Y[i]-X[i];

if(RL>X[i])then RL:=X[i];

if(RR < Y[i])then RR:=Y[i];

end;

KK:=K/2.0;

//writeln(RL:0:2,RR:10:2,KK:10:2);

//for i:=1 to N do writeln(X[i]:10:2,Y[i]:10:2);

end;

function step(R:real):real;

var i:integer; S:real;

begin

i:=1; S:=0;

while(i<=N) and (X[i] < R) do begin

if(Y[i]<=R) then S:=S+Y[i]-X[i] else S:=S+R-X[i];

inc(i);

end ;

result:=S;

end;

function stepend(R:real):real;

var i:integer; S:real;

begin

i:=1; S:=Y[1];

while(i<=N) and (X[i] < R) and (S < R)do begin

if (Y[i]>S) then S:=Y[i];

inc(i);

end ;

result:=S;

end;

begin

S:=0; RL:=10000; RR:=-10000; R:=0;

rd();

sort();

//for i:=1 to N do writeln(X[i]:10:2,Y[i]:10:2);

while(abs(S-KK)>Eps) do begin

R:=(RL+RR)/2.0;

S:=step(R);

//writeln(S:0:2,R:10:2,RL:10:2,RR:10:2);

if(S < KK)then RL:=R else RR:=R;

end;

RL:=stepend(R);

if RL < R then R:=RL;

if KK>0 then write(R:0:2) else write('0.00');

// readln;

end.

Тесты:

1) Вход

-15 15

0 20

0 3

Выход

4.25

2) Вход

-100 100

Выход

0.00

3) Вход

-13 -3

15 25

15 35

Выход

-3.00

Остальные тесты по задаче "C" Вы можете скачать по следующей ссылке: Скачать тесты

Задача D. Степень

Для двух натуральных чисел Х и К вычислить и вывести последние (младшие) 6 разрядов степени Х^К (Х в К-й степени ).

Если значение Х^K меньше 1000000, то вывести это значение, т.е. вывести все число. Х и К не больше 2000;

Время решения задачи – 0.5 сек.

Входные данные: два числа, записанных через пробел ( Х К ).

Выходные данные: последние 6 разрядов или значение Х^K.

Пример

Вход

1001 5

Выход

005001

РЕШЕНИЕ:

program D;

var p:extended;

n,r,i:integer;

function Null(p:extended):string;

var s,ss:string;

i,k:integer;

begin

str(p:0:0,s);

k:=length(s);

if k < 6 then begin ss:='000000' ;delete(ss,1,k);s:=ss+s;end;

result:=s;

end;

begin

readln(r,n);

if (r=0) or (r=1) then begin write(r);exit; end;

p:=r;

for i:=2 to n do begin

p:=p*r;

if p>=1000000 then break;

end;

if p < 1000000 then begin

write(p:0:0);readln; exit;

end;

r:=round(r) mod 1000000;

if r=0 then r:=1000000;

p:=r;

for i:=2 to n do begin

p:=p*r;

p:=round(p) mod 1000000;

if p=0 then p:=1000000;

end;

if p < 1000000 then write(Null(p))

else begin

p:=round(p) mod 1000000;

write(Null(p));

end;

// readln;

end.

Тесты:

1) Вход

1001 5

Выход

005001

2) Вход

1 1000

Выход

3) Вход

999 999

Выход

998999

4) Вход

1001 1001

Выход

001001

5) Вход

100 100

Выход

000000

6) Вход

13 5

Выход

371293

Задача E. Частное

Дано 3 натуральных числа : А, В и Р. Значения А и В не более 1000000, а Р не более 255.

Вычислить частное А/В с точностью до Р знаков после десятичной запятой.

Время решения задачи – 0.5 сек.

Входные данные: строка содержит значения 3-х чисел, записанных через пробел (А В Р).

Выходные данные: найденное значение частного .

Пример

Вход

17 3 10

Выход

5.6666666667

РЕШЕНИЕ:

program E;

var i,n,a,b,t,m:longint;

s:string;

begin

readln(a,b,m); t:=a div b; a:=a mod b;

n:=1;

str(t,s); s:=' '+s+'.';

while n<=m+1 do begin

a:=a*10;

if a < b then s:=s+'0'else begin

t:=a div b; a:=a mod b; s:=s+chr(t+48);

end;

inc(n);

end;

t:=length(s);

if s[t]>'4' then begin

for i:=t-1 downto 1 do begin

// writeln(s);

if s[i]='.' then continue;

if s[i]=' ' then begin s[i]:='1'; continue end;

if s[i]<'9' then begin s[i]:=chr(ord(s[i])+1);break; end;

s[i]:='0';

end;

delete(s,t,1);

if s[1]=' ' then delete(s,1,1);

write(s);

readln;

end.

Тесты:

1) Вход

17 3 10

Выход

5.6666666667

2) Вход

3 5 8

Выход

0.60000000

3) Вход

999999 888888 20

Выход

1.12500000000000000000

4) Вход

1 989898 4

Выход

0.0000

5) Вход

2 978767 100

Выход

0.0000020433872412944040818703532097015939442175716999040629690212277283561869168045101643189850086895

6) Вход

878787 1 100

Выход

878787.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

7) Вход

1966 8547 20

Выход

0.2300222300

Задача F. Строки

Дано 2 строки одинаковой длины S1 и S2. Строки состоят из символов 0 и 1. Над второй строкой S2 можно выполнять следующие действия: удалить последний символ, вставить перед первым символом 0, вставить перед первым символом 1. За какое минимальное количество действий можно вторую строку сделать равной первой.

Длина входных строк не более 255 символов.

Время решения задачи – 0.5 сек.

Входные данные: первая входная строка – S1, затем вторая – S2.

Выходные данные: минимальное количество действий.

Пример

Вход

10011

00111

Выход

РЕШЕНИЕ:

program F;

var s1,s2:string;

k,mk,d1,d2:integer;

function xod(s2:string;k:integer):integer;

begin

if s1=s2 then begin

if mk > k then mk: =k;

exit;

end;

if k=d1 then exit;

delete(s2,d2,1);

s2:='1'+s2; xod(s2,k+1);

s2[1]:='0'; xod(s2,k+1);

end;

function find:integer;

var i,k:integer;

begin

i:=1;

while i<=d1 do begin

if copy(s1,i,d1)=copy(s2,1,d1-i+1) then break;

inc(i);

end;

result:=i-1;

end;

begin

readln(s1); readln(s2); d1:=length(s1); d2:=d1;

// xod(s2,0); writeln(2*mk);

mk: =find; write(2*mk);

// readln;

end.

Тесты:

1) Вход

10011

00111

Выход

2) Вход

10101010100010101110111010101000000000100101010101010010101011111111111111111111111111111000000000000000000000000000000000111111111111111110101010101010100001111111111111111111111111000000000000000011

10101010000111111111111111111111111100000000000000001110101010101010101010101010101010101010100000000000000000000000000000000000000000001111111111111111111111111111111111111100000101000000000000000000

Выход

292

3) Вход

1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Выход

380

4) Вход

00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Выход

5) Вход

Выход

6) Вход

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

Выход

Задача G. Кубики

На предприятии изготавливаются игральные кости (кубики с цифрами на гранях: 1, 2, 3, 4, 5 и 6). Каждый кубик описывается последовательностью цифр: цифра передней грани, задней, левой, правой, верхней и нижней. Таким образом, один и тот же кубик может быть описан различными последовательностями цифр в зависимости от его положения в устройстве чтения. Написать программу, которая по 2-м последовательностям определяет, являются ли они описаниями одного кубика ( ответ 1) или двух различных (ответ 2).

Время решения задачи – 0.5 сек.

Входные данные: первая строка – первая последовательность,

вторая строка – вторая последовательность.

Выходные данные: 1 или 2.

Пример

Вход

123456

124365

Выход

РЕШЕНИЕ:

program G;

type ss=string[2];

const N=12;

R:array[1..N] of integer=( 0, -1, 2, -3,

-20, 21, -22, 23,

30, -31, 32, -33);

var s:string;

s1,s2:array[1..3] of ss;

z,i,k,j:integer;

function cmp:integer;

var a1,a2:ss;

i1,i2:integer;

p:boolean;

a:char;

begin

k:=0;

for i1:=1 to 3 do begin

a1:=s1[i1]; p:=true;

for i2:=1 to 3 do begin

a2:=s2[i2];

if a1=a2 then begin

if i1<>i2 then k:=k+10;

p:=false;

break;

end else begin

a:=a2[1]; a2[1]:=a2[2]; a2[2]:=a;

if a1=a2 then begin

if i1<>i2 then k:=k+10;

k:=k+1;p:=false;

break;

end;

if p then begin cmp:=0;exit; end;

end;

cmp:=1;

end;

begin

readln(s);

for i:=1 to 3 do s1[i]:=copy(s,i+i-1,2);

readln(s);

for i:=1 to 3 do s2[i]:=copy(s,i+i-1,2);

if cmp=0 then begin write(2);exit; end;

for i:=1 to N do if abs(R[i])=k then break;

if R[i] < 0 then write(2) else write(1);

//readln;

end.

Тесты:

1) Вход

123456

124365

Выход

2) Вход

351426

Выход

3) Вход

654321

326541

Выход

4) Вход

234561

234516

Выход

5) Вход

253416

615243

Выход

6) Вход

342615

624315

Выход

7) Вход

236154

326145

Выход

8) Вход

654321

654231

Выход

Следующее олимпиадное задание >>