Результати турніру "Динамічний старт"

Зведена таблиця результатів

Учасник\Тест
Matches
Numbers
Rally
Sum
0595_Саша Шевчук 40 24 30 94
0528_Dima Soroka 40 24 9 73
1043_Люба Ярушинська 32 9 30 71
1882_Дмитро Березін 40 0 20 60
1351_Андрій Макаревич 0 24 30 54
0667_Назар Старушок 6 0 30 36
1562_Льоха Антосюк 0 0 30 30
0331_Дмитро Макоївець 0 0 22 22
1124_Олег Юшко 0 0 16 16

 

Результати тестів по задачі "Matches"

Учасник\Тест
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
Sum
0331_Дмитро Макоївець N N N N N N N N N N N N N N N N N N N N 0,0
0528_Dima Soroka + + + + + + + + + + + + + + + + + + + + 40,0
0595_Саша Шевчук + + + + + + + + + + + + + + + + + + + + 40,0
0667_Назар Старушок + - - - - + - - - + - - - - - - - - - - 6,0
1043_Люба Ярушинська + + + + + + + + + + + + + + + + T T T T 32,0
1124_Олег Юшко N N N N N N N N N N N N N N N N N N N N 0,0
1351_Андрій Макаревич W W W W W W W W W W W W W W W W W W W W 0,0
1562_Льоха Антосюк N N N N N N N N N N N N N N N N N N N N 0,0
1882_Дмитро Березін + + + + + + + + + + + + + + + + + + + + 40,0

 

Результати тестів по задачі "Numbers"

Учасник\Тест
01
02
03
04
05
06
07
08
09
10
Sum
0331_Дмитро Макоївець N N N N N N N N N N 0,0
0528_Dima Soroka + + + + + + + + - - 24,0
0595_Саша Шевчук + + + + + + + + - - 24,0
0667_Назар Старушок - - - - - - - - - - 0,0
1043_Люба Ярушинська - + - - - - + + - - 9,0
1124_Олег Юшко N N N N N N N N N N 0,0
1351_Андрій Макаревич + + + + + + + + - - 24,0
1562_Льоха Антосюк N N N N N N N N N N 0,0
1882_Дмитро Березін W W W W W W W W W W 0,0

 

Результати тестів по задачі "Rally"

Учасник\Тест
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
Sum
0331_Дмитро Макоївець + + + + + + + + + + T T T T + 22,0
0528_Dima Soroka P P P P P P - - - - - - - - - 9,0
0595_Саша Шевчук + + + + + + + + + + + + + + + 30,0
0667_Назар Старушок + + + + + + + + + + + + + + + 30,0
1043_Люба Ярушинська + + + + + + + + + + + + + + + 30,0
1124_Олег Юшко + + + + + + + - - - - - - - + 16,0
1351_Андрій Макаревич + + + + + + + + + + + + + + + 30,0
1562_Льоха Антосюк + + + + + + + + + + + + + + + 30,0
1882_Дмитро Березін + + + + + + + + + T T T T T + 20,0

 

Легенда:
T - перевищений ліміт часу
W - помилка вводу-виводу, використання модуля Crt.
R - помилка виконання
N - відсутній розв'язок
P - штраф

Matches (автор - Діма Сорока)

 
	var k,x:longint;
    begin
     read(k);
     x:=3;
     while (k mod x)<>0 do inc(x);
     writeln(x-1);
    end.
	  
	  
	  

 

Numbers (автор - Дмитро Березін :) - виправлено помилку створення вихідного файлу)

 

 
Var fi,fo:text;


 kilt,n,i:longint;

a:array[1..5] of int64;

Begin

Assign(fi,'numbers.in');Reset(fi);
Assign(fo,'numbers.out');Rewrite(fo);

Readln(fi,kilt);

for i:=1 to kilt do Begin

Readln(fi,n);

Case n of

1:a[i]:=10;
2:a[i]:=670;
3:a[i]:=55252;
4:a[i]:=4816030;
5:a[i]:=3486784401;
end;

end;

for i:=1 to kilt do Writeln(fo,a[i]);

Close(fo);end.

		
		

 

Rally (авторский розв"язок)

VAR n,i,r   :longint;
    a       :array[-32769..32768]of boolean;
	fi,fo : text;
BEGIN
  assign(fi,'rally.in');reset(fi);
  assign(fo,'rally.out');rewrite(fo);	
  readln(fi,n);
  for i:=1 to n do begin readln(fi,r); a[r]:=true; end;
  readln(fi,n);
  for i:=1 to n do begin
    readln(fi,r);
    if (10000-r<=32767)and(10000-r>=-32768) then if a[10000-r] then 
			begin writeln(fo,10000-r,' ',r);close(fo); halt end;
  end;
  writeln(fo,'Kaput');close(fo);
END.


	
	 

Ідея розв’язку задачі Numbers

Задача на динамічне програмування. Розглянемо послідовність десяткових цифр парної довжини(номерів у нашому варіанті задачі). Наша задача знайти кількість щасливих номерів довжиною 2N.

Зафіксуємо число K – суму цифр у першій половині номера. Зрозуміло, що 0<=K<=9N. Нехай маємо таку таблицю А, що A[i,j] – кількість номерів довжиною i, сума цифр яких дорівнює j. Для фіксованого К кількість щасливих білетів дорівнює A[N,K]^2. Отже шукане число дорівнює сумі A[N,K]^2 при K від 0 до 9 N, і для розв’язання задачі достатньо побудувати таблицю А.

Зрозуміло, що при j>9*i або при j<0 A[i,j]=0. Значення A[1,i]=1 при 0<=i<=9 – є тільки один номер довжиною 1, що починається на дану цифру – це сама цифра. Отже, нехай ми обчислили значення A[i,j] для всіх i, менших деякого числа а и нам треба обчислити A[a,b]. Нехай T[a,b,c] – кількість номерів довжини а з сумою цифр b і остання цифра яких c. Тоді T[a,b,c]=A[a-1,b-c] тому, що при відкиданні останньої цифри довжина номера зменшиться на 1, а сума його цифр на c. Тепер маємо A[a,b]=T[a,b,0]+T[a,b,1]+...+T[a,b,9], або A[a,b]=A[a-1,b]+A[a-1,b-1]+...+A[a-1,b-9]. Будуємо таблицю А.

Реалізація алгоритму може бути такою:

const
  MaxN = 5;

var
  A : array [1 .. MaxN,0 .. 9*MaxN] of Longint;

function Dyn(N : Integer) : Longint;
var
  I,J,K : Integer;
  Res : Longint;
begin
  fillchar(A,sizeof(A),0);
  for I:=0 to 9 do
    A[1,I]:=1;
  for I:=2 to N do
    for J:=0 to 9*I do
      for K:=0 to 9 do
        if J>=K then
          A[I,J] := A[I,J] + A[I-1,J-K];
  Res := 0;
  for K:=0 to N*9 do
    Res := Res+A[N,K]*A[N,K];
  Dyn := Res;
end;