Форум Всеукраїнської інтернет-олімпіади NetOI


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#26 2008-12-23 20:37:56

astor
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 48

Re: Разбор решений задач.

это не понятно...

А ЧО тут неясного? о_О
якшо 2 числа однакові, то чисел, що знаходяться між ними немає, тому їх сума 0.

Відредаговано astor (2008-12-23 20:38:53)

Поза форумом

 

#27 2008-12-23 21:17:12

V@ny@
Новий користувач
Зареєстрований: 2007-12-17
Повідомлень: 13

Re: Разбор решений задач.

Ну почнемо!
Почнемо із Winner. Все знання щоб розвязати задачу - сума арифметичної прогресії і знаходження похідної та екстр. точок.

Код:

var
   F1, F2, Z, N1, N2, T : int64;

begin
     read(Z,T);
     N1:=trunc((2*Z-T)/(2*T));
     N2:=N1+1;
     F1:=round(Z*N1-(N1*(N1+1)/2-1)*T);
     F2:=round(Z*N2-(N2*(N2+1)/2-1)*T);
     if F2>F1 then writeln(N2,' ',F2)
              else writeln(N1,' ',F1);
end.

Далі - Cavalery. Задача на знання пошука у ширину. Починаємо з клітинки в яку потрібно попасти і робимо ходи конем. Маскимальне чисто із тих клітинок, в які ми хочемо потрапити і буде розвязком smile.

Код:

type
    arr2 = array[1..100,1..100] of integer;
const
    d1 : array[1..8] of integer=(2,1,-1,-2,-2,-1,1,2);
    d2 : array[1..8] of integer=(-1,-2,-2,-1,1,2,2,1);

var
   m, n, s1, nn, i, x0, y0, s, t : integer;
   s2 : int64;
   d : arr2;
   count : array[1..10000] of integer;

procedure poshuk(x0,y0 : integer; var d : arr2);
var ax, ay : array[1..10000] of integer;
    i, j, k, l : integer;

function xod(p, q : integer) : boolean;
begin
     if (p>0) and (p<=n) then
     if (q>0) and (q<=m) then
     if d[p,q]=-1 then begin xod:=true; exit; end;
     xod:=false;
end;

begin
     for i:=1 to n do
     for j:=1 to m do d[i,j]:=-1;
     ax[1]:=x0; ay[1]:=y0; d[x0,y0]:=0; k:=0; l:=1;
     repeat
           inc(k);
           for i:=1 to 8 do
           if xod(ax[k]+d1[i],ay[k]+d2[i]) then begin
              inc(l); ax[l]:=ax[k]+d1[i]; ay[l]:=ay[k]+d2[i];
              d[ax[l],ay[l]]:=d[ax[k],ay[k]]+1;
           end;
     until (k=l);
end;

begin
     read(n,m);
     read(s,t);
     poshuk(s,t,d);
     read(nn);
     s1:=0; s2:=0;
     for i:=1 to nn do
     begin
          read(x0,y0);
          if d[x0,y0]=-1 then inc(s1)
          else s2:=s2+d[x0,y0];
     end;
     if s1>0 then writeln(s1)
             else writeln(s2);
end.

Device.
Задачу можно написати за хвилину динамічним програмуванням.

Код:

program device;
var a:array[1..100000000] of int64;
    i,n:int64;
begin
 read(n);
 i:=6;
 a[1]:=0;
 a[2]:=0;
 a[3]:=1;
 a[4]:=0;
 a[5]:=1;
 while i<=n do
 begin
  if i mod 2 =0 then a[i]:=2*a[i div 2]
  else a[i]:= a[i div 2]+a[(i div 2) +1];

  inc(i);
 end;
 writeln(a[n]);
end.

Але тут О(2*N). На макс значеннях хвилину працюе, і тому будемо знаходити тільки ті значення, що нам потрібні.

Код:

var
   N : int64;
   a, b : array[1..1000] of int64;
   t : integer;

function F(N : int64) : int64;
var k, p1, p2 : int64;
    i : integer;
begin
     k:=N div 2;
     if N<3 then begin F:=0; exit end
            else if N=3 then begin F:=1; exit; end;
     for i:=1 to t do
     if a[i]=N then begin F:=b[i]; exit; end;
     if odd(N) then begin
        p1:=F(N-k); inc(t); a[t]:=N-k; b[t]:=p1;
        p2:=F(k); inc(t); a[t]:=k; b[t]:=p2;
        F:=p1+p2;
     end
     else begin
        p2:=F(k); inc(t); a[t]:=k; b[t]:=p2;
        F:=2*p2;
     end;
end;

begin
     t:=0;
     read(N);
     writeln(F(N));
end.

На цьому алгоритмі для 10^18 за декілька мілісекунд.


Summa. задачу можно написати "втупу") Але від цього толку - 5 балів.
Довго парився, дійшов до задічі скільки раз зустрічаєтьзя цифра х у проміжку (а,b). Проходим усі цифри і маємо відповідь.

Код:

var
   N1, N2 : longint;

function F(N : longint) : int64;
var st1, st2, st3, st : string;
    i, k, x, code : integer;
    S : int64;
    p, p1 : longint;
begin
     str(N,St); St3:=St[length(St)];
     St2:=copy(St,1,length(St)-1); val(St2,p,code);
     S:=0;
     for x:=1 to 9 do
     begin
          str(x,St1);
          if St1<=St3 then S:=S+(p+1)*x
                      else S:=S+p*x;
     end;

     for i:=2 to length(St)-1 do
     begin
          St2:=copy(St,1,i-1); val(St2,p,code);
          k:=length(St)-i;
          St3:=copy(St,i+1,k); val(St3,p1,code);
          k:=round(exp(ln(10)*k));
          for x:=1 to 9 do
          begin
               str(x,St1);
               if St1>St[i] then S:=S+p*k*x
               else if St1=St[i] then S:=S+(p*k+p1+1)*x
               else S:=S+(p+1)*k*x;
          end;
     end;

     St3:=St[1];
     St2:=copy(St,2,length(St)-1); val(St2,p,code);
     k:=length(St)-1; k:=round(exp(ln(10)*k));
     for x:=1 to 9 do
     begin
          str(x,St1);
          if St1=St3 then S:=S+(p+1)*x
          else if St1<St3 then S:=S+k*x;
     end;

     F:=S;
end;

begin
     read(N1,N2);
     writeln(F(N2)-F(N1-1));
end.

Market. Цікава задача, зводиться до такої: яке найменше число не можна представити у вигляді суми чисел масиву, а ця вже досить відома.

Код:

type
   list = array[1..20000] of longint;
var
   A, B, D : list;
   C, S : int64;
   N, M, j, i : integer;

procedure Qsort(var a: list; Lo,Hi: integer);

procedure sort(l,r: integer);
var
  i,j: integer;
  x,y: longint;
begin
  i:=l; j:=r; x:=a[(l+r) DIV 2];
  repeat
    while a[i]<x do i:=i+1;
    while x<a[j] do j:=j-1;
    if i<=j then
    begin
      y:=a[i]; a[i]:=a[j]; a[j]:=y;
      i:=i+1; j:=j-1;
    end;
  until i>j;
  if l<j then sort(l,j);
  if i<r then sort(i,r);
end;

begin 
  sort(Lo,Hi);
end;

begin
     read(N); for i:=1 to N do read(A[i]);
     read(M); for i:=1 to M do read(B[i]);

     for i:=1 to N do C:=C+A[i];

     for i:=1 to N do D[i]:=A[i];
     for i:=N+1 to N+M do D[i]:=B[i-N];
     QSort(D,1,M+N);

     S:=1;
     for i:=1 to M+N do
         if S>=D[i] then S:=S+D[i]
                    else break;

     writeln(C-S);
end.

Скільки набрало потім скажу)

Поза форумом

 

#28 2008-12-23 21:30:22

kadr
Новий користувач
Зареєстрований: 2007-11-29
Повідомлень: 75

Re: Разбор решений задач.

Device:

Код:

#include <map>
#include <iostream>
#include <cstdio>
using namespace std;
#define mp make_pair
int a,b,c,d,i,j,n,m,k;
map <int,int> p;
int rec(int a)
{
    if (a<3) return 0; else
    if (a==3) return 1; else
    if (p.count(a)!=0) return p[a];
    if (a&1)
    {
        int b=rec(a>>1),c=rec((a>>1)+1);
        p.insert(mp(a,b+c));
        return b+c;
    } else
    {
        int b=rec(a>>1);
        b<<=1;
        p.insert(mp(a,b));
        return b;
    }
}
int main()
{
    p.clear();
    scanf("%d",&n);
    a=rec(n);
    printf("%d\n",a);
}

Winner:

Код:

#include <iostream>
#include <cstdio>
using namespace std;
#define ll long long
int a,b,i,j,n,m,k,z,t;
ll c,d;
inline ll f(ll a)
{
    ll rr=-(ll)t*a*a+(ll)a*(2LL*(ll)z-(ll)t)+2LL*(ll)t;
    rr>>=1;
    return rr;
}
int main()
{
    scanf("%d%d",&z,&t);
    a=(2*z+1)/(2*t);
    if (a<2) a=2;
    b=a+1;
    c=f((ll)a);
    d=f((ll)b);
    if (c>=d) { d=c; b=a; }
    while (b>2 && f(b-1)==d) --b;
    cout<<b<<" "<<d<<endl;
}

Cavalery:

Код:

#include <iostream>
#include <cstdio>
using namespace std;
#define mp make_pair
#define x first
#define y second
#define INF 1000000000
const int dx[]={1, 1,-1,-1,2, 2,-2,-2};
const int dy[]={2,-2, 2,-2,1,-1, 1,-1};
int ci,cj,bi,bj,a,b,c,d,i,j,n,m,k;
int mas[102][102];
pair <int,int> st[10003];
inline bool norm(int ci,int cj)
{
    return (ci>=1 && cj>=1 && ci<=n && cj<=m);
}
int main()
{
    memset(mas,63,sizeof(mas));
    scanf("%d%d",&n,&m);
    scanf("%d%d",&bi,&bj);
    a=0; b=0;
    st[0]=mp(bi,bj);
    mas[bi][bj]=0;
    while (a<=b)
    {
        ci=st[a].x,cj=st[a++].y;
        for (int i=0;i<8;i++)
        {
            int fi=ci+dx[i],fj=cj+dy[i];
            if (norm(fi,fj) && mas[fi][fj]>=INF)
            {
                st[++b]=mp(fi,fj);
                mas[fi][fj]=mas[ci][cj]+1;
            }
        }
    }
    scanf("%d",&k);
    c=0; d=0;
    for (int i=0;i<k;i++)
    {
        scanf("%d%d",&a,&b);
        c=min(c+mas[a][b],INF);
        if (mas[a][b]>=INF) d++;
    }
    if (d) printf("%d\n",d); else printf("%d\n",c);
}

Поза форумом

 

#29 2008-12-23 21:41:26

guest1
Новий користувач
Зареєстрований: 2006-12-19
Повідомлень: 309
Вебсайт

Re: Разбор решений задач.

Более 80% баллов. В принципе, неплохо big_smile И вроде прохожу. (можно и поспать smile )

Поза форумом

 

#30 2008-12-23 21:50:59

kadr
Новий користувач
Зареєстрований: 2007-11-29
Повідомлень: 75

Re: Разбор решений задач.

Может и не в тему, но думаю будет полезно:
http://www2.olymp.vinnica.ua/cgi-bin/v_ … nguage=ukr


Линк на общие резы за первые 2 тура.

Поза форумом

 

#31 2008-12-23 21:57:57

astor
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 48

Re: Разбор решений задач.

офтоп: скільке треба балів, щоб пройти в 4 тур?

Поза форумом

 

#32 2008-12-23 22:38:43

redman17
Новий користувач
Звідки: Винница
Зареєстрований: 2008-09-04
Повідомлень: 82

Re: Разбор решений задач.

astor написав:

это не понятно...

А ЧО тут неясного? о_О
якшо 2 числа однакові, то чисел, що знаходяться між ними немає, тому їх сума 0.

я бы написал if m=n then write(сума_цифр(m))


WE DIE HARD!!!

Поза форумом

 

#33 2008-12-23 22:41:02

redman17
Новий користувач
Звідки: Винница
Зареєстрований: 2008-09-04
Повідомлень: 82

Re: Разбор решений задач.

V@ny@ написав:

Маскимальне чисто із тих клітинок, в які ми хочемо потрапити і буде розвязком .

не ври нам - сумма чисел из клеток, в которые надо попасть


WE DIE HARD!!!

Поза форумом

 

#34 2008-12-23 22:42:48

redman17
Новий користувач
Звідки: Винница
Зареєстрований: 2008-09-04
Повідомлень: 82

Re: Разбор решений задач.

astor написав:

офтоп: скільке треба балів, щоб пройти в 4 тур?

определяется жури по окончанию 3 тура


WE DIE HARD!!!

Поза форумом

 

#35 2008-12-24 13:20:02

V@ny@
Новий користувач
Зареєстрований: 2007-12-17
Повідомлень: 13

Re: Разбор решений задач.

redman17 написав:

V@ny@ написав:

Маскимальне чисто із тих клітинок, в які ми хочемо потрапити і буде розвязком .

не ври нам - сумма чисел из клеток, в которые надо попасть

це глупость, починаємо всіма ходити одночасно, коли останній прийде(якщо прийде) тоді й буде кінець, за неї в мене 40)
Всьго 165, за суму половина - важка задача. маркет і вінер мабуть макс не пройшло, зараз протестую

Поза форумом

 

#36 2008-12-24 16:19:46

redman17
Новий користувач
Звідки: Винница
Зареєстрований: 2008-09-04
Повідомлень: 82

Re: Разбор решений задач.

Давайте не превращать тему "Разбор задач второго тура" в тему "Мои коды".

Пускай каждый кто оставляет свое решение следит, что бы оно не повторяло уже размещенное тут, или существенно улучшало размещенную уже идею.

+ Очень важно чтобы это был не просто код, а и поянение своего решения хотя бы в общих словах.

Насколько я понимаю предназначение такой темы - помощь тем, кто не смог решить что-то + обсуждение наилучшего возможного решения (преимуществ разных решений)

Відредаговано redman17 (2008-12-24 16:20:06)


WE DIE HARD!!!

Поза форумом

 

#37 2008-12-24 16:56:31

astor
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 48

Re: Разбор решений задач.

я бы написал if m=n then write(сума_цифр(m))

ну ненаю... в мене пройшло 39/40, можливо, на цьому і залагало...

Поза форумом

 

#38 2008-12-24 20:49:38

redman17
Новий користувач
Звідки: Винница
Зареєстрований: 2008-09-04
Повідомлень: 82

Re: Разбор решений задач.

V@ny@ написав:

Далі - Cavalery. Задача на знання пошука у ширину. Починаємо з клітинки в яку потрібно попасти і робимо ходи конем. Маскимальне чисто із тих клітинок, в які ми хочемо потрапити і буде розвязком smile.

type
    arr2 = array[1..100,1..100] of integer;
const
    d1 : array[1..8] of integer=(2,1,-1,-2,-2,-1,1,2);
    d2 : array[1..8] of integer=(-1,-2,-2,-1,1,2,2,1);

var
   m, n, s1, nn, i, x0, y0, s, t : integer;
   s2 : int64;
   d : arr2;
   count : array[1..10000] of integer;

procedure poshuk(x0,y0 : integer; var d : arr2);
var ax, ay : array[1..10000] of integer;
    i, j, k, l : integer;

function xod(p, q : integer) : boolean;
begin
     if (p>0) and (p<=n) then
     if (q>0) and (q<=m) then
     if d[p,q]=-1 then begin xod:=true; exit; end;
     xod:=false;
end;

begin
     for i:=1 to n do
     for j:=1 to m do d[i,j]:=-1;
     ax[1]:=x0; ay[1]:=y0; d[x0,y0]:=0; k:=0; l:=1;
     repeat
           inc(k);
           for i:=1 to 8 do
           if xod(ax[k]+d1[i],ay[k]+d2[i]) then begin
              inc(l); ax[l]:=ax[k]+d1[i]; ay[l]:=ay[k]+d2[i];
              d[ax[l],ay[l]]:=d[ax[k],ay[k]]+1;
           end;
     until (k=l);
end;

begin
     read(n,m);
     read(s,t);
     poshuk(s,t,d);
     read(nn);
     s1:=0; s2:=0;
     for i:=1 to nn do
     begin
          read(x0,y0);
          if d[x0,y0]=-1 then inc(s1)
          else s2:=s2+d[x0,y0];
     end;
     if s1>0 then writeln(s1)
             else writeln(s2);
end.

возможно я что-то не понимаю, возтожно - ты...
s2:=s2+d[x0,y0];

Відредаговано redman17 (2008-12-24 20:50:14)


WE DIE HARD!!!

Поза форумом

 

#39 2008-12-28 16:20:16

floppy
Новий користувач
Зареєстрований: 2008-12-28
Повідомлень: 2

Re: Разбор решений задач.

А когда будут задания 3 тура?

Поза форумом

 

#40 2008-12-28 23:50:04

pro
Новий користувач
Звідки: Черкаси
Зареєстрований: 2007-11-14
Повідомлень: 33

Re: Разбор решений задач.

Ну я сомневаюсь что задания будут до нового года)


"Никакие украшения не являются постоянными, будь то картина или цветы в нише. Перемены — да. Но суть всегда остается неизменной." Перл Бак.

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt