Открытая олимпиада школьников по информатике (на задачах районного тура)

Решения и тесты

1. Светодиоды
Тесты

Ввод	Правильный ответ	Оценка за тест
0	6	1
733999	31	1
421244	24	1
668885	38	1
123456780	43	1

Полный балл (10 баллов) получает программа, выдавшая правильные ответы на все тесты

Решение
Тема: простая задача

const ks:array['0'..'9'] of integer=(6,2,5,5,4,5,6,3,7,6);
var s:string;
  i,k:integer;
begin
  readln(s);
  k:=0;
  for i:=1 to length(s) do
    k:=k+ks[s[i]];
  writeln(k);
end.

2. Окно
Тесты

Ввод	Правильный ответ	Оценка за тест
a	1 1	2,1
aaa bb ccc dd eee	3 5	2,1
1 2 3 4 5 6 7 8 9 0	1 10	2,1
123456789 1234567890	20 1	2,1
12345 123 12 12345678 1234567 1234 1 1234 123456 123 12345 12 123 123456789 123 1 123456	29 3	2,1
1 123 12 12 1234 12 1 123 1 1 123 12 12 1234 1 12	5 9	2,1

Полный балл (25 баллов) получает программа, выдавшая правильные ответы на все тесты

Решение
Тема: перебор

var s:string;
  i,j,k,w,h,mh,mw:integer;
begin
  readln(s);
  mh:=1;
  mw:=length(s);
  for w:=1 to length(s) do
  begin
    h:=0;
    k:=0;
    while k<=length(s) do
    begin
      inc(h);
      if k+w+1>length(s) then
        break;
      i:=k+w+1;
      while i>k do
      begin
        if s[i]=' ' then
          break;
        dec(i);
      end;
      if i=k then
      begin
        h:=1000;
        break;
      end;
      k:=i;
    end;
    if (h*w<mh*mw) or (h*w=mh*mw) and (w>mw) then
    begin
      mh:=h;
      mw:=w;
    end;
  end;  
  writeln(mw,' ',mh);
end.

3. Мышь
Тесты

Ввод	Правильный ответ	Оценка за тест
1 1 1000 1000 30 40	50.000 0.000	2,5
1 9 100 100 1 100	900.045 900.045	2,5
4 2 100 100 100 0 0 100 -100 0 0 –100	800.000 800.000	2,5
3 1 100 100 30 –10 30 90 -66 –88	236.491 141.421	2,5
5 7 101 201 -93 47 77 41 73 –62 23 –83 -19 99	3319.032 3084.601	2,5
5 1 100 100 70 10 40 20 10 70 20 40 60 60	315.717 274.372	2,5

Полный балл (30 баллов) получает программа, выдавшая правильные ответы на все тесты
Решение
Тема: моделирование

const eps=1e-10;
const inf=1e100;
var 
  x,y,t,dx,dy:extended;
  i,n,k,w,h:integer;
  r1,r2:extended;
procedure solve(a,d:extended;z:integer;var t:extended);
var r:extended;
begin
  r:=z-a;
  if abs(d)<=eps then exit;
  r:=r/d;
  if r<eps then exit;
  if r>1+eps then exit;
  if t=inf then
    t:=r
  else if t>r then
      t:=r;
end;
begin
  read(n,k,w,h);
  x:=w/2;
  y:=h/2;
  r1:=0;
  r2:=0;
  for i:=1 to n do
  begin
    read(dx,dy);
    dx:=dx*k;
    dy:=dy*k;
    r1:=r1+sqrt(sqr(dx)+sqr(dy));
    while true do
    begin
      t:=inf;
      solve(x,dx,0,t);
      solve(x,dx,w,t);
      solve(y,dy,0,t);
      solve(y,dy,h,t);
      if t=inf then
        break;
      r2:=r2+sqrt(sqr(x+t*dx-w/2)+sqr(y+t*dy-h/2));
      dx:=dx*(1-t);
      dy:=dy*(1-t);
      x:=w/2;
      y:=h/2;
      if (abs(dx)<eps) and (abs(dy)<eps) then
        break;
    end;
    x:=x+dx;
    y:=y+dy;
  end;
  writeln(r1:1:3,' ',r2:1:3);
end.

4. Монумент
Тесты

Ввод	Правильный ответ	Оценка за тест
1 12 5	1 12	3,0
5 2 3	3 14	3,0
1001 1 1	31 61	3,0
1000 25 7	34 1639	3,0
1000 3 5	38 361	3,0
5000 2 5	88 800	3,0

Полный балл (35 баллов) получает программа, выдавшая правильные ответы на все тесты

Решение
Тема: динамическое программирование

const maxh=250;
      maxn=5000;
var n,w,h,t,i,j,k,l,m:integer;
  a:array[1..maxn,1..maxh] of integer;
function max(x,y:integer):integer;
begin
  if x>y then max:=x else max:=y;
end;
begin
  read(n,w,h);
  if w>h then
  begin
    t:=w;
    w:=h;
    h:=t;
  end;
  for j:=1 to maxh do
  begin
    k:=0;
    for i:=1 to n do
    begin
      if (i-j>0) and (a[i-j,j-1]>0) then
        a[i,j]:=a[i-j,j-1]+h;
      if (j=1) and (i=1) then
        a[i,j]:=h;
      if (j mod w=0) and (i-j div w>0) and (a[i-j div w,j-1]>0) then
        a[i,j]:=max(a[i-j div w,j-1]+h,a[i,j]);
      if (j mod h=0) and (i-j div h>0) and (a[i-j div h,j-1]>0) then
        a[i,j]:=max(a[i-j div h,j-1]+w,a[i,j]);
      if a[i,j]>0 then
        k:=1;
    end;
    if k=0 then break;
  end;
  m:=0;
  j:=maxh;  
  while j>=1 do
  begin
    for i:=1 to n do
      if a[i,j]>0 then
      begin
        if j=1 then
          m:=max(m,a[i,j])
        else
        begin
          for k:=n-i downto 1 do
            if a[k,j-1]>0 then
              m:=max(m,a[i,j]+a[k,j-1]);
        end;
      end;
    if m>0 then break;  
    dec(j);
  end;
  writeln(j,' ',m);
end.