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

n1ce · 2010-01-03 23:51:05

Итак, сдача решений задач второго тура официально завершена. Обсуждаем)

Я решал задачи таким образом:
1. Queen. Поиск в ширину.
2. Beads. Последовательная проверка количества "фенек", которые надо выкинуть и выбор минимума из них. Учитывая, что результат теста 10 1 2 3 4 2 3 4 2 3 1 - 2.
3. Smarand. Разложение на простые множители. Поиск факториалов, которые "содержат" простые множители в соответствующих степенях, выбор максимума из них.
4. Palindrom2. Создаем два палиндрома заменой второй половины числа первой половиной и заменой второй половины числа первой половиной увеличенной на один. Выбор минимального, который превосходит изначальное число.
5. Word2. Динамика (многим известное Расстояние редактирования).

Может не оптимизированные, но коды моих решений:

Queen

Код:

#include <iostream>

using namespace std;

#define INF 10000

int a[30][110];
int h,w,k,ans;
int q[10000];
int head=0;
int tail=0;
int start[2],finish[2];

void incl(int smth)
{
    q[tail]=smth;
    if (tail==9999) tail=0;
    else tail++;
}

int excl()
{
    if (head==tail) return -1;
    int temp=q[head];
    if (head==9999) head=0;
    else head++;
    return temp;
}

int BFS()
{
    int res=excl();
    int w1,h1,stw,sth;
    while (res!=-1)
    {
        w1=res/100;
        h1=res%100;
        stw=w1;
        sth=h1-1;
        while ((sth>0) && (a[stw][sth]!=10000))
        {
            if ((a[stw][sth]==-1) || (a[stw][sth]>(a[w1][h1]+1)))
            {
                a[stw][sth]=a[w1][h1]+1;
                incl(stw*100+sth);
            }
            sth--;
        }
        stw=w1;
        sth=h1+1;
        while ((sth<h+1) && (a[stw][sth]!=10000))
        {
            if ((a[stw][sth]==-1) || (a[stw][sth]>(a[w1][h1]+1)))
            {
                a[stw][sth]=a[w1][h1]+1;
                incl(stw*100+sth);
            }
            sth++;
        }
        stw=w1-1;
        sth=h1;
        while ((stw>0) && (a[stw][sth]!=10000))
        {
            if ((a[stw][sth]==-1) || (a[stw][sth]>(a[w1][h1]+1)))
            {
                a[stw][sth]=a[w1][h1]+1;
                incl(stw*100+sth);
            }
            stw--;
        }
        stw=w1+1;
        sth=h1;
        while ((stw<w+1) && (a[stw][sth]!=10000))
        {
            if ((a[stw][sth]==-1) || (a[stw][sth]>(a[w1][h1]+1)))
            {
                a[stw][sth]=a[w1][h1]+1;
                incl(stw*100+sth);
            }
            stw++;
        }
        stw=w1+1;
        sth=h1+1;
        while (((sth<h+1) && (stw<w+1)) && (a[stw][sth]!=10000))
        {
            if ((a[stw][sth]==-1) || (a[stw][sth]>(a[w1][h1]+1)))
            {
                a[stw][sth]=a[w1][h1]+1;
                incl(stw*100+sth);
            }
            sth++;
            stw++;
        }
        stw=w1-1;
        sth=h1-1;
        while (((sth>0) && (stw>0)) && (a[stw][sth]!=10000))
        {
            if ((a[stw][sth]==-1) || (a[stw][sth]>(a[w1][h1]+1)))
            {
                a[stw][sth]=a[w1][h1]+1;
                incl(stw*100+sth);
            }
            sth--;
            stw--;
        }
        stw=w1+1;
        sth=h1-1;
        while (((sth>0) && (stw<w+1)) && (a[stw][sth]!=10000))
        {
            if ((a[stw][sth]==-1) || (a[stw][sth]>(a[w1][h1]+1)))
            {
                a[stw][sth]=a[w1][h1]+1;
                incl(stw*100+sth);
            }
            sth--;
            stw++;
        }
        stw=w1-1;
        sth=h1+1;
        while (((sth<h+1) && (stw>0)) && (a[stw][sth]!=10000))
        {
            if ((a[stw][sth]==-1) || (a[stw][sth]>(a[w1][h1]+1)))
            {
                a[stw][sth]=a[w1][h1]+1;
                incl(stw*100+sth);
            }
            sth++;
            stw--;
        }
        res=excl();
        if (a[finish[0]][finish[1]]!=-1) return 0;
    }
    return 0;
}

int main()
{
    for (int i=0; i<28; i++)
        for (int j=0; j<100; j++)
            a[i][j]=-1;
    scanf("%d%d%d%d%d%d%d",&w,&h,&start[0],&start[1],&finish[0],&finish[1],&k);
    if (start[0]==finish[0]) if (start[1]==finish[1]) {cout<<0<<endl; return 0;}
    int temp1,temp2;
    for (int i=0; i<k; i++)
    {
        scanf("%d%d",&temp1,&temp2);
        a[temp1][temp2]=INF;
    }
    incl(100*start[0]+start[1]);
    a[start[0]][start[1]]=0;
    BFS();
    cout<<a[finish[0]][finish[1]]<<endl;
    return 0;
}

Smarand

Код:

#include <iostream>

using namespace std;

int primes[500];
int pow[500];
int n,k,ans;

int main()
{
    k=-1;
    scanf("%d",&n);
    if (n==1)
    {
        cout<<0<<endl;
        return 0;
    }
    for (int i=2; (i*i)<(n+1); i++)
    {
        if (n%i==0) primes[++k]=i;
        while (n%i==0)
        {
            pow[k]++;
            n/=i;
        }
    }
    if (n>1) {primes[++k]=n; pow[k]++;}
    ans=-1;
    for (int i=0; i<=k; i++)
    {
        int temp_ans=0, temp=0;
        while (temp<pow[i])
        {
            temp_ans+=primes[i];
            int temp1=temp_ans;
            while (temp1%primes[i]==0)
            {
                temp++;
                temp1/=primes[i];
            }
        }
        ans=ans>temp_ans?ans:temp_ans;
    }
    cout<<ans<<endl;
    return 0;
}

Palindrom2

Код:

#include <iostream>

using namespace std;

long long number,temp,pal;
int nmb[20];
int k;

void do_pal()
{
    pal=nmb[k-1];
    for (int i=k-2; i>=k/2; i--)
    {
        pal*=10;
        pal+=nmb[i];
    }
    for (int i=(k+1)/2; i<k; i++)
    {
        pal*=10;
        pal+=nmb[i];
    }
}

int main()
{
    scanf("%lld",&number);
    temp=number;
    k=0;
    while (temp>0)
    {
        nmb[k]=temp%10;
        temp/=10;
        k++;
    }
    bool f=true;
    for (int i=0; i<k; i++)
    {
        if (nmb[i]!=9) f=false;
    }
    if (f)
    {
        pal=1;
        for (int i=0; i<k; i++)
        {
            pal*=10;
        }
        pal++;
        cout<<pal<<endl;
        return 0;
    }
    do_pal();
    if (pal>number)
    {
        cout<<pal<<endl;
        return 0;
    }
    f=false;
    temp=k/2;
    while (!f)
    {
        nmb[temp]++;
        f=true;
        if (nmb[temp]==10)
        {
            nmb[temp]=0;
            f=false;
            temp++;
        }
    }
    do_pal();
    cout<<pal<<endl;
    return 0;
}

Word2

Код:

#include <iostream>

using namespace std;

int a[10010][2];
char words[10010][2];
int l1,l2;

int main()
{
    char c='w';
    l1=l2=0;
    while (c!='\n')
    {
        scanf("%c",&c);
        words[l1][0]=c;
        l1++;
    }
    c='w';
    while (c!='\n')
    {
        scanf("%c",&c);
        words[l2][1]=c;
        l2++;
    }
    l1--;l2--;
    for (int i=0; i<=l1; i++)
    {
        a[i][0]=i;
    }
    int s1=0; int s2=1;
    for (int i=1; i<=l2; i++)
    {
        for (int j=0; j<=l1; j++)
        {
            if (j==0) a[j][s2]=i;
            else
            {
                int ans=29031993;
                ans=ans<(a[j][s1]+1) ? ans : (a[j][s1]+1);
                ans=ans<(a[j-1][s2]+1) ? ans : (a[j-1][s2]+1);
                ans=ans<(a[j-1][s1]+(words[i-1][1]!=words[j-1][0]?1:0)) ? ans : (a[j-1][s1]+(words[i-1][1]!=words[j-1][0]?1:0));
                a[j][s2]=ans;
            }
        }
        s1=(s1+1)%2; s2=(s2+1)%2;
    }
    cout<<a[l1][s1]<<endl;
    return 0;
}

Результаты проверки:
1. Queen. 38
2. Beads. 40
3. Smarand. 40
4. Palindrom2. 40
5. Word2. 40

Відредаговано n1ce (2010-01-04 01:05:00)

DEzzL · 2010-01-04 00:18:01

в 3-м немного не так.
найдя max(p^a)
после надо найти такое min(L)? что
a<=L+[L/p]+[L/(p^2)]+[L/(p^3)]......
ну и ответ соответсвенно L*p

n1ce · 2010-01-04 00:22:34

DEzzL написав:
в 3-м немного не так.
найдя max(p^a)
после надо найти такое min(L)? что
a<=L+[L/p]+[L/(p^2)]+[L/(p^3)]......
ну и ответ соответсвенно L*p

Согласен, это более оптимально, но на суть решения не очень влияет. У меня, к счастью, 40 баллов.

Відредаговано n1ce (2010-01-04 00:35:38)

Ilya Porublyov · 2010-01-04 07:24:05

У 3-ій задачі розкладення на прості множники і т. д. взагалі-то хороший і ефективний спосіб, але є інший, зовсім трошки менш ефективний і при цьому набагато коротший і красивший: для всіх підряд чисел (2,3,... ... ...) шукаємо алгоритмом Евкліда НСД вхідного числа й поточного, щоразу ділячи вхідне число на знайдений НСД. Правда, доводиться трохи хитро забезпечувати, щоб одночасно і у випадку простого числа не крутило оті 2,3,... аж до самого числа (тоді як можна лише до кореня), і разом з тим не помилялось у випадках, коли на вході заданий, наприклад, квадрат простого числа.

Код:

int nsd(int a,int b)
{
    while (a!=0 && b!=0)
    {
        if (a>b)
            a%=b;
        else
            b%=a;
    }
    return (a+b);
}
int main()
{
    int k;
    cin >> k;
    int i=1;
    int nnn, last_used=0;
    while (k!=1)
    {
          if((nnn=nsd(k,i))>1)
          {
             last_used=i;
             k/=nnn;
          }
          else
              if(i<k &&  (i-last_used)*(i-last_used)>k)
              {
                 i=k-1;
              }
      i++;
    }
    cout << i-1 << endl;
    return 0;
}

Автор ідеї прикрутити сюди НСД -- учень Черкаського фіз-мат ліцею Поліщук Євгеній.
Патч алгоритму, що стосується обривання циклу при перевищенні кореня з k -- мій.

DEzzL · 2010-01-04 08:07:37

ребята, огромная просьба человека с 40-ка расказать поподробней 5-ую,а не только общий подход, заранее благодарен.

pilya · 2010-01-04 09:50:25

Уважаемое жюри возможно ли узнать входные данные для 23 теста задачи queen?
Мое решение почему то только на этом тесте дает "bad data". И что обозначате bad data?

Я проверял на любых задачах вплоть до простого считывания входных данных и ввывода постоянного результата а 23 тест всегда дает bad data. Может что то с входными данными.
У кого эта задача набрала 40 балов поделитесь решением.

Відредаговано pilya (2010-01-04 10:03:51)

pilya · 2010-01-04 10:29:42

Жюри обратите пожалуйста внимание!!!

Вот код который всеравно выдает в 23 тесте bad data а не Wrong Answer.
На сколько я понимаю bad data это не правильный прием входных данных хотя я не понимаю что вэтом коде приема неправильно?

#include <iostream>
using namespace std;

int w,h,bx,by,ex,ey,k;

int main(void)
{
int i,j,x,y;

cin>>w>>h>>bx>>by>>ex>>ey>>k;
bx--;
by--;
ex--;
ey--;
if(bx==ex && by==ey)
{
cout<<0<<endl;
return 0;
}
for(i=0;i<k;i++)
{
cin>>x>>y;
}
cout<<5<<endl;
return 0;
}

если в цикле измениеть i<k на i<k+1 то 23 тест проходит что говорит о том что в тесте некорректные входные данные
что противоречит правилам олимпиады

Відредаговано pilya (2010-01-04 12:35:37)

erebus · 2010-01-04 12:13:26

Можно ли выложить тесты к задачам?
Хотелось бы найти свои ошибки.

LeonID · 2010-01-04 12:14:46

На онлайн проверке мое решение задачи Смаранд набирает полный бал. А в финальном отчете 39, почему?

alexkasycky · 2010-01-04 12:18:17

LeonID написав:
На онлайн проверке мое решение задачи Смаранд набирает полный бал. А в финальном отчете 39, почему?

обычно это ТЛ. у тебя с большим запасом проходит?

Silicious Man · 2010-01-04 12:40:23

Ilya Porublyov написав:
У 3-ій задачі розкладення на прості множники і т. д. взагалі-то хороший і ефективний спосіб, але є інший, зовсім трошки менш ефективний і при цьому набагато коротший і красивший: для всіх підряд чисел (2,3,... ... ...) шукаємо алгоритмом Евкліда НСД вхідного числа й поточного, щоразу ділячи вхідне число на знайдений НСД. Правда, доводиться трохи хитро забезпечувати, щоб одночасно і у випадку простого числа не крутило оті 2,3,... аж до самого числа (тоді як можна лише до кореня), і разом з тим не помилялось у випадках, коли на вході заданий, наприклад, квадрат простого числа.
…
Автор ідеї прикрутити сюди НСД -- учень Черкаського фіз-мат ліцею Поліщук Євгеній.
Патч алгоритму, що стосується обривання циклу при перевищенні кореня з k -- мій.

Ему респект.

Тем не менее, мое решение работает гораздо быстрее (я не голословен, только что измерял). Автор идеи - Кемпнер (1918). Метод описан здесь http://mathworld.wolfram.com/SmarandacheFunction.html (первая ссылка, выдаваемая гуглом на запрос "Smarandache function"). За название функции, указанное в условии задачи, авторам задач отдельное спасибо. (Только не думайте сейчас, что я при решении задач моментально лезу в интернет; между прочим метод с простыми множителями я сам придумал еще до того). Код моего решения:

Код:

#include <stdio.h>
#include <math.h>

int a (int p, int n){
    if (n == 1) return 1;
    return ((pow ((double) p, (double) n) - 1) / (p - 1));
}

int mu (int p, int alpha){    // mu (p^alpha)
    if (alpha == 1) return p;
    int k0 = alpha * (p - 1);
    int i, nu;
    i = nu = floor (log (1 + k0) / log (p));
    int k_i = alpha / a (p, nu);
    int r_i = alpha - k_i * a (p, nu);
    int summ = k0 + k_i;
    while (r_i > 0){
        int k_im1 = r_i / a (p, i - 1);
        int r_im1 = r_i - k_im1 * a (p, i - 1);
        k_i = k_im1;
        r_i = r_im1;
        i--;
        summ += k_i;
    }
    return summ;
}

int mu (int n){  // mu (p)
    if (n == 1) return 0;
    int max = 0;
    int s = sqrt (n) + 2;
    for (int p = 2; p <= s; p++){
        int alpha = 0;
        while (n % p == 0){
            n /= p;
            alpha++;
        }
        if (alpha){
            int mu1 =  mu (p, alpha);
            if (mu1 > max) max = mu1;
        }
    }
    return (n > max) ? n : max;
}

int main () {
    int n;
    scanf ("%d", &n);
    printf("%d\n", mu (n));
    return 0;
}

Silicious Man · 2010-01-04 12:45:33

1. 40 (поиск в ширину)
2. 40 (линейный проход, поиск максимального расстояния между одинаковыми бусинками)
3. 40 (см. мой предыдущий пост)
4. 40 (долго рассказывать, реализовано увеличение того, что в середине)
5. 14!!! (я написал крутой алгоритм за O(nd) где d - искомое расстояние, но почему-то тайм-ауты; еще буду разбираться)

LeonID · 2010-01-04 12:47:36

DEzzL написав:
ребята, огромная просьба человека с 40-ка расказать поподробней 5-ую,а не только общий подход, заранее благодарен.

Поподробней и коротко не получится, лучше поищи в google "алгоритм Левенштейна", и подумай как его реализовать с помощью двух линейных массивов.

alexkasycky · 2010-01-04 13:52:54

pilya написав:
Жюри обратите пожалуйста внимание!!!

Вот код который всеравно выдает в 23 тесте bad data а не Wrong Answer.
На сколько я понимаю bad data это не правильный прием входных данных хотя я не понимаю что вэтом коде приема неправильно?
#include <iostream>
using namespace std;

int w,h,bx,by,ex,ey,k;

int main(void)
{
int i,j,x,y;

cin>>w>>h>>bx>>by>>ex>>ey>>k;
bx--;
by--;
ex--;
ey--;
if(bx==ex && by==ey)
{
cout<<0<<endl;
return 0;
}
for(i=0;i<k;i++)
{
cin>>x>>y;
}
cout<<5<<endl;
return 0;
}
если в цикле измениеть i<k на i<k+1 то 23 тест проходит что говорит о том что в тесте некорректные входные данные
что противоречит правилам олимпиады

почему Бэд Дэйта - вполне понятно, ты не все входные данные считываешь если bx==ex && by==ey(можешь поставить этот иф после цикла и убедиться). другое дело, что изменение к на к+1 действительно меняет ситуацию, что совершенно не логично... две причины которые я вижу(обе маловероятные) это:
1) баг компилятора
2) у всех тестов один общий поток ввода, и если считать лишнего в пред идущем - "нужно будет" читать меньше в этом.

pilya · 2010-01-04 14:03:40

Огромное спасибо за указание ошибки.
За такую ошибку надо не два бала а 20 балов снимать
Извините за зря потраченное время.

Відредаговано pilya (2010-01-04 14:08:14)

Silicious Man · 2010-01-04 14:04:26

pilya написав:
У кого эта задача набрала 40 балов поделитесь решением.

Задача Queen, 40 баллов

Код:

#include <iostream>

int main (void) {
    int w, h, k;
    int xs, ys, xe, ye;
    std::cin >> w >> h >> xs >> ys >> xe >> ye >> k;
    int a[100][100];
    for (int i = 0; i < w; i++)
        for (int j = 0; j < h; j++)
            a[i][j] = -1;
    for (int i = 0; i < k; i++){
        int x, y;
        std::cin >> x >> y;
        a[x - 1][y - 1] = -2;
    }
    a[xs - 1][ys - 1] = 0;
    int Q[10000][3];
    Q[0][0] = xs - 1;
    Q[0][1] = ys - 1;
    Q[0][2] = 0;
    int ql = 1;
    int qi = 0;
    while (qi < ql){
        if (Q[qi][0] == xe - 1 && Q[qi][1] == ye - 1){
            std::cout << Q[qi][2] << "\n";
            return 0;
        }
        for (int incr_x = -1; incr_x <= 1; incr_x++){
            for (int incr_y = -1; incr_y <= 1; incr_y++){
                if (incr_x == 0 && incr_y == 0) continue;
                int x = Q[qi][0];
                int y = Q[qi][1];
                while (1){
                    if (x < 0 || x >= w || y < 0 || y >= h) break;
                    if (a[x][y] == -2) break;
                    if (a[x][y] == -1){
                        a[x][y] = 0;
                        Q[ql][0] = x;
                        Q[ql][1] = y;
                        Q[ql][2] = Q[qi][2] + 1;
                        ql++;
                    }
                    x += incr_x;
                    y += incr_y;
                }
            }}
        qi++;
    }
    std::cout << "-1\n";
    return 0;
}

LeonID · 2010-01-04 14:10:21

Задача Queen

Код:

var wertikales,horizontas,quinx,quiny,kilkvraga,i,j,x,y:longint;
endx,endy,k,p,xod:longint;
doska,vidmitka:array[-1..100,-1..200]of integer;
bx,by:array[1..8]of integer;
zmina:boolean;
begin
read(wertikales);
read(horizontas);
read(quinx,quiny);
read(endx,endy);
read(kilkvraga);
bx[1]:=0;by[1]:=1;
bx[2]:=0;by[2]:=-1;
bx[3]:=1;by[3]:=0;
bx[4]:=1;by[4]:=-1;
bx[5]:=1;by[5]:=1;
bx[6]:=-1;by[6]:=1;
bx[7]:=-1;by[7]:=0;
bx[8]:=-1;by[8]:=-1;
for i:=1 to wertikales do
      for j:=1 to horizontas do begin
          doska[i,j]:=0;{formuu dosku}
          vidmitka[i,j]:=0;{vsi nevidmicheni}
          end;
doska[quinx,quiny]:=1;
for i:=1 to kilkvraga do begin
    read(x,y);
    doska[x,y]:=-1;
    end;
for i:=0 to wertikales+1 do begin
    doska[i,0]:=-1;
    doska[i,horizontas+1]:=-1;
    end;
for i:=0 to horizontas+1 do begin
    doska[0,i]:=-1;
    doska[wertikales+1,i]:=-1;
    end;
xod:=0;
repeat
zmina:=false;
xod:=xod+1;
for i:=1 to wertikales do
    for j:=1 to horizontas do begin
    if (doska[i,j]=xod)and (vidmitka[i,j]<>1) then begin
    vidmitka[i,j]:=1;{vzali koord prosrela}
    for k:=1 to 8 do
                if not((k=0) and (p=0)) then begin
                x:=i;y:=j;
                while doska[x,y]<>-1 do begin
                if doska[x,y]=0 then doska[x,y]:=xod+1;
                x:=x+bx[k];
                y:=y+by[k];
                zmina:=true;
      end;
     x:=i;y:=j;
     end;
   end;
   end;
until (zmina=false) or (doska[endx,endy]<>0);
if doska[endx,endy]=0 then write(-1)else
write(doska[endx,endy]-1);
end.

pilya · 2010-01-04 14:17:49

А вот мое решение queen правда с ошибкой описанной ранее.
Если кому интерестно.

Код:

#include <iostream>
using namespace std;
struct myNapr
{
    int x;
    int y;    
};
struct myStack
{
    int x;
    int y;
    myStack *p;
};
struct myPole
{
    int s;
    unsigned char b;
};

myPole pole[26][99];
myNapr p[8];
int w,h,bx,by,ex,ey,k;
myStack *bSt, *eSt;

void AddStack(int x,int y)
{
    if(bSt==NULL)
    {
        bSt=new myStack;
        eSt=bSt;
        eSt->x=x;
        eSt->y=y;
        eSt->p=NULL;
    }else
    {
        eSt->p=new myStack;
        eSt=eSt->p;
        eSt->x=x;
        eSt->y=y;
        eSt->p=NULL;
    }
}

int NextStep(int x,int y)
{
    int i,j,step,tx,ty;
    unsigned char v,f;
    j=0;
    step=pole[x][y].s+1;
    f=pole[x][y].b;
    while(f)
    {
        j++;
        v=1;
        for(i=0;i<8;i++)
        {
            if(v&f)
            {
                tx=x+p[i].x*j;
                ty=y+p[i].y*j;
                if(tx==ex && ty==ey) return step;
                if(tx<0||tx>=w||ty<0||ty>=h||pole[tx][ty].s==-1)
                {
                    f&=(~v);
                }
                else
                {
                    pole[tx][ty].b&=~v;
                    if(i>3)pole[tx][ty].b&=~(v>>4); else pole[tx][ty].b&=~(v<<4);
                    if(pole[tx][ty].s==0) 
                    {
                        pole[tx][ty].s=step;
                        AddStack(tx,ty);
                    }
                }
            }
            v<<=1;
        }
    }
    pole[x][y].b=0;
    return 0;
}


int main(void)
{
    int i,j,x,y;
    myStack *tSt;
    bSt=eSt=NULL;
    //Инициализация допустимых направлений ферзя
    p[0].x=0; p[0].y=1;
    p[1].x=1; p[1].y=1; 
    p[2].x=1; p[2].y=0; 
    p[3].x=1; p[3].y=-1; 
    p[4].x=0; p[4].y=-1; 
    p[5].x=-1; p[5].y=-1; 
    p[6].x=-1; p[6].y=0; 
    p[7].x=-1; p[7].y=1; 

    cin>>w>>h>>bx>>by>>ex>>ey>>k;
    bx--;
    by--;
    ex--;
    ey--;
    if(bx==ex && by==ey)
    {
        cout<<0<<endl;
        return 0;
    }
    //Заполнение игрового поля
    for(i=0;i<w;i++)
        for(j=0;j<h;j++) 
        {
            pole[i][j].s=0;
            pole[i][j].b=0xFF;
        }
    for(i=0;i<k;i++)
    {
        cin>>x>>y;
        pole[x-1][y-1].s=-1;
    }
    //Решение
    int rez;
    rez=NextStep(bx,by);
    while(bSt!=NULL && rez==0)
    {
        tSt=bSt;
        bSt=bSt->p;
        rez=NextStep(tSt->x,tSt->y);
        delete tSt;
    }

    cout<<((rez)?rez:-1)<<endl;

    while(bSt!=NULL)
    {
        tSt=bSt;
        bSt=bSt->p;
        delete tSt;
    }
    return 0;
}

Відредаговано pilya (2010-01-04 14:23:48)

Зевс · 2010-01-04 15:12:52

Да, у меня тоже Queen набрала 38 из-за того, что я проверяю равенство клеток и выхожу до того, как считал все входные данные. Странно, так как на других олимпиадах это всегда работало: естественно, потому, что обычно ввод из файла, но... Я перечитал правила и кроме фразы
"Щоб пройти тест, програма повинна отримати правильний результат у відведений на тест час." ничего не нашел. Моя программа выдает правильный результат в указанное время...
Думаю, это недоработка жюри.

PS: только не подумайте, что мне так важны эти 2 балла - просто в следующий раз, это может оказаться очень важно. Я думаю, что это должно быть огворено в правилах, так как в информатике просто из-за мелочи можно круто пролететь .

Жюри_Пасихов · 2010-01-04 16:48:45

pilya написав:
Огромное спасибо за указание ошибки.
За такую ошибку надо не два бала а 20 балов снимать
Извините за зря потраченное время.

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

Уважаемый ЗЕВС!

А ввод-вывод следует организовывать согласно техническим условиям, приведенним в задаче. А там всегда сказано "Программа читает (и далее аккуратненько перечисляется), ЧЕГО И СКОЛЬКО должна читать программа... А если она по каким-то (возможно, гениальным) причинам не пожелала все прочитать, то эта программа не соответствует техническим условиям.... с вытекающими оттуда последствиями.
А в правилах сказано, что программа должна соответствовать техническим условиям. Так что Ваша критика слегка необоснованна.

А то что, на других олимпиадах "катит"....это проблема других олимпиад. Может, по ихним ТУ можна получать ответ вообще не читая входные данные...Олимпиад нынче много разных...

LeonID · 2010-01-04 20:27:49

Суммарные результаты по двум турам, для учасников которые набрали больше 200 баллов.

Код:

1;               ?рифа Серг?й ;300
2;               Norris Chuck ;300
3;             Пол?щук Дмитро ;300
4;             Пупкин Василий ;300
5;            Башук Олександр ;300
6;            Вышневый Андрей ;300
7;            Лавриненко Марк ;300
8;        Миринский Александр ;300
9;               PandA Andrey ;298
10;              Гр?нчук Олег ;298
11;              Наг?н Серг?й ;298
12;           Рубаненко Роман ;298
13;        Бережной Владислав ;298
14;      Кожевнiков Олександр ;298
15;           Мостовий Андр?й ;297
16;          Кушн?ренко Роман ;297
17;           Савенко Натал?я ;296
18;            Вареник Андр?й ;295
19;               Igor Drobot ;294
20;              Черник Роман ;294
21;           Андр?й Пилипчук ;294
22;           Т?машов Михайло ;294
23;               Глова Павло ;292
24;              Тимашов Миша ;292
25;         Руденко Александр ;292
26;              Гр?нчук Олег ;291
27;          Гелева Олександр ;290
28;              Шевчук ?вген ;289
29;             Адабрин Абрак ;288
30;              Прядко Антон ;286
31;               Бойков ?ван ;285
32;        Челноков Володимир ;284
33;            ?вген?я Крищик ;283
34;            Reader Acrobat ;282
35;           Тодер Святослав ;282
36;       Big Boss -псевдон?м ;282
37;             Побойко Игорь ;281
38;              Андр?й Кулян ;278
39;            Opara Alexandr ;274
40;          Гранковский Вова ;274
41;          Владислав Бабкин ;269
42;             Егоров Виктор ;267
43;           Шаравара Виктор ;267
44;               Фурко Роман ;265
45;            Баленко Даниил ;264
46;           Шевченко Серг?й ;264
47;          Касицкий Алексей ;264
48;         Лукянець Валентин ;262
49;        Микитянский Максим ;262
50;           Слободян Сергей ;260
51;                 Зайцев Ян ;259
52;             Оришич Серг?й ;259
53;             Швець Михайло ;257
54;            Vasyliv Yevgen ;257
55;              Фуйор Кирило ;256
56;             Васил?в ?вген ;255
57;             Жернов Андрей ;255
58;               Руснак ?гор ;254
59;            Михайлюта Влад ;252
60;       Дмитренко Анастас?я ;252
61;              Zdomsky Ivan ;251
62;               Курас Игорь ;250
63;            П?дкуйко Антон ;250
64;         Резунов Олександр ;250
65;       Будиченко Владислав ;250
66;             Сагач Ярослав ;248
67;         Резунов Александр ;248
68;        Майстренко Алексей ;246
69; Light_keeper_2 Псевдон?м  ;244
70;           Оглобля Ярослав ;241
71;              М?на?в Борис ;240
72;          Дем'янюк В?тал?й ;240
73;                Пронь Олег ;239
74;         Mostovenko mykola ;238
75;         Мостовенко Микола ;238
76;             Чудов Алексей ;236
77;         Сн?тко Олександр  ;236
78;          Богдан Прищенко  ;235
79;            Яковл?в Максим ;232
80;                   Stdio h ;227
81;               Pascal Blez ;227
82;             Яковл?в Артем ;227
83;           Циммерман Елена ;226
84;                Орлов Юрий ;224
85;              Кашин Андрей ;224
86;             absent sonner ;219
87;          Макаревич Андр?й ;219
88;           Комиссарова Ася ;217
89;            Мизюк Валентин ;215
90;         Сорочан Александр ;215
91;      Кожевников Олександр ;215
92;       Присяжнюк Олександр ;212
93;              Сливка Тарас ;208
94;            Здомський ?ван ;204

reiten · 2010-01-04 20:53:35

LeonID написав:
Суммарные результаты по двум турам, для учасников которые набрали больше 200 баллов.
Код:
2;               Norris Chuck ;300
4;             Пупкин Василий ;300

Грядет сражение титанов

pilya · 2010-01-05 18:35:56

reiten написав:
LeonID написав:
Суммарные результаты по двум турам, для учасников которые набрали больше 200 баллов.
Код:
2;               Norris Chuck ;300
4;             Пупкин Василий ;300
Грядет сражение титанов

Но у Пупкина есть волосатая лапа
Это единственный человек который не сдав задачу полиндром получил за нее полный бал

zasqzasq · 2010-01-05 20:23:52

можете викласти на сайті тести до задачі BEADS?

LeonID · 2010-01-05 20:32:55

zasqzasq написав:
можете викласти на сайті тести до задачі BEADS?

Якщо твій розвязок на паскалі, то виклади його, а я покажу тести які він не проходить.

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

#1 2010-01-03 23:51:05

Обсуждаем решения и результаты проверки

Код:

Код:

Код:

Код:

#2 2010-01-04 00:18:01

Re: Обсуждаем решения и результаты проверки

#3 2010-01-04 00:22:34

Re: Обсуждаем решения и результаты проверки

DEzzL написав:

#4 2010-01-04 07:24:05

Re: Обсуждаем решения и результаты проверки

Код:

#5 2010-01-04 08:07:37

Re: Обсуждаем решения и результаты проверки

#6 2010-01-04 09:50:25

Re: Обсуждаем решения и результаты проверки

#7 2010-01-04 10:29:42

Re: Обсуждаем решения и результаты проверки

#8 2010-01-04 12:13:26

Re: Обсуждаем решения и результаты проверки

#9 2010-01-04 12:14:46

Re: Обсуждаем решения и результаты проверки

#10 2010-01-04 12:18:17

Re: Обсуждаем решения и результаты проверки

LeonID написав:

#11 2010-01-04 12:40:23

Re: Обсуждаем решения и результаты проверки

Ilya Porublyov написав:

Код:

#12 2010-01-04 12:45:33

Re: Обсуждаем решения и результаты проверки

#13 2010-01-04 12:47:36

Re: Обсуждаем решения и результаты проверки

DEzzL написав:

#14 2010-01-04 13:52:54

Re: Обсуждаем решения и результаты проверки

pilya написав:

#15 2010-01-04 14:03:40

Re: Обсуждаем решения и результаты проверки

#16 2010-01-04 14:04:26

Re: Обсуждаем решения и результаты проверки

pilya написав:

Код:

#17 2010-01-04 14:10:21

Re: Обсуждаем решения и результаты проверки

Код:

#18 2010-01-04 14:17:49

Re: Обсуждаем решения и результаты проверки

Код:

#19 2010-01-04 15:12:52

Re: Обсуждаем решения и результаты проверки

#20 2010-01-04 16:48:45

Re: Обсуждаем решения и результаты проверки

pilya написав:

#21 2010-01-04 20:27:49

Re: Обсуждаем решения и результаты проверки

Код:

#22 2010-01-04 20:53:35

Re: Обсуждаем решения и результаты проверки

LeonID написав:

Код:

#23 2010-01-05 18:35:56

Re: Обсуждаем решения и результаты проверки

reiten написав:

LeonID написав:

Код:

#24 2010-01-05 20:23:52

Re: Обсуждаем решения и результаты проверки

#25 2010-01-05 20:32:55

Re: Обсуждаем решения и результаты проверки

zasqzasq написав:

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