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


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

Ви не зайшли.

#1 2012-02-03 17:28:58

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Закінчення олімпіади і розв’язки задач 3 туру

Ось, кому цікаво, загальна таблиця по 3 турам:
Загальний залік
По школярам

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

Спочатку три повнобальні, потім інші.

Like3
Вся ідея розв’язку, в принципі, описується формулами з коду.

Код:

#include <iostream>
#include<cstring>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned ul;
typedef long double ld;

ull fast_pow(ull x,ull power)
{
    ull res=1;
    while(power)
    {
        if(power%2)res*=x;
        x*=x;
        power>>=1;
    }
    return res;
}

int countL3(int n)                              //Рішення для одноцифрових випадків
{
    if(n>=9)return 3;
    if(n>=3)return 2;
    if(n>=1)return 1;
    return 0;
}

ull like3(char* a,int t,bool first=true)       //а - масив цифр числа, t - довжина числа
{
    if(t<=0)return 0;                           
    if(t==1)return countL3(a[0]);
    ull res=(countL3(a[0]-1))*fast_pow(3,t-1);  //Кількість триподібних такої-ж довжини, як і початкове число, у яких старший розряд менший, ніж у даного
    int i=1;
    if(first)while(t-i)res+=fast_pow(3,t-i),i++;//Якщо функція викликана не рекурсивно, то до розв’язку додаємо кількість триподібних, коротших за дане число
    if(9%a[0])return res;                       //Якщо перша цифра числа не 3-подібна, то відповідь уже знайдено
    if(a[1])res+=like3(a+1,t-1,false);          //Інакше до відповіді треба додати рішення для усих цифр числа, крім першої(за умови, що друга цифра - не нуль)
    return res;
}

ull solve(char* a, char *b)                         //Функція, що перетворюе рядок ANSI-символів у масив "звичайних" цифр,            
{                                                   //Вирішує задачу окремо для першого та другого числа, а потім повертає відповідь.
    int a_len=strlen(a),b_len=strlen(b),i=0;
    bool f=true;
    while(a[i])a[i]-='0',f=f&&a[i]!=0&&!(9%a[i]),i++;
    i=0;
    while(b[i])b[i]-='0',i++;
    return like3(b,b_len)-like3(a,a_len)+f;
}

int main()
{
    char a[42],b[42];
    cin>>a>>b;
    cout<<solve(a,b)<<endl;
}

Diiders
Простий перебір степеней перших 16(підібрано експериментально, з невеликим запасом) простих чисел.

Код:

#include <iostream>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned ul;
typedef long double ld;

ull solve(ull n,ull cur_max=1, int start_prime=0)
{
    static const ull primes[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131};
    static const int N_PRIMES=16;
    static const ld EPS=1e-6;
    static ul times_used[N_PRIMES]={0};
    static ull max=0;
    for(int i=start_prime;i<N_PRIMES;++i)
    {
        if((ld)primes[i]*cur_max-(ld)n>EPS)
        {
            ull ts=1;
            for(int i=0;i<N_PRIMES;++i)ts*=times_used[i]+1;
            if(ts>max)max=ts;
        }
        else if(!i||times_used[i-1]>=times_used[i]+1)
        {
            times_used[i]++;
            solve(n,cur_max*primes[i],i);
            times_used[i]--;
        }
    }
    return max;
}

int main()
{
    ull n;
    cin>>n;
    cout<<solve(n)<<endl;
}

Railway
В принципі, рішення - модифікація BFS(але пошук ведеться одночасно з усіх листків, а не з якоїсь однієї вершини). Усе інше, знову ж таки, описується формулами з коду.
По часу роботи - окрема історія. По перше, класи iostream повільніші за scanf(), printf(). Але це, в принципі, не новина.
Найбільше ж на час впливало використання списків std::list. З ними, як уже раніше було з векторами, при компіляції без оптимізацій, програма працює дуже повільно. Хоча з -О2 - цілком нормальний час. Чесно кажучи, не знаю, як з цим на інших олімпіадах, але як на мене, це не дуже правильно - фактично позбавляти учасників частини стандартної бібліотеки, адже очевидно, що це сама бібліотека розраховує на подальшу оптимізацію себе компілятором. Але це все філософія, правила такі, які вони є, і приймаючи участь в олімпіаді ми з ними погоджуємося smile.
Тому для досягнення нормального часу роботи довелося писати свій кривий велосипед, що частково надає інтерфейс std::list(не хотілося сильно переписувати вже працюючий код самого рішення). Зі своєю реалізацією списку програма працює швидко і правильно.
ось код:

Код:

#include <queue>
#include <utility>
#include <cstdio>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned ul;
typedef long double ld;

//bicycles begin
template<typename _Tp>
  inline _Tp*
  __addressof(_Tp& __r)
  {
    return reinterpret_cast<_Tp*>
      (&const_cast<char&>(reinterpret_cast<const volatile char&>(__r)));
  }
template<class T>
struct myList
{
    struct node
    {
        T data;
        node *prev, *next;
        node():prev(0x0),next(0x0){}
    };
    struct iterator
    {
        node *p;
        T& operator *(){return p->data;}
        T* operator ->(){return ::__addressof(p->data);}
        iterator& operator ++(){p=p->next;return *this;}
        iterator& operator --(){p=p->prev;return *this;}
        bool operator ==(iterator const &rhs)const{return p==rhs.p;}
        bool operator !=(iterator const &rhs)const{return !(this->operator ==(rhs));}
        iterator():p(0x0){}
    };
    iterator _beg;
    iterator _end;
    int _sz;
    iterator begin()
    {
        return _beg;
    }
    iterator end()
    {
        return _end;
    }
    int size()
    {
        return _sz;
    }
    void push_back(const T& x)
    {
        if(!_sz)
        {
            _beg.p=new node;
            _end.p=new node;
            _beg.p->prev=0x0;
            _end.p->next=0x0;
            _beg.p->next=_end.p;
            _end.p->prev=_beg.p;
            _end.p=_beg.p;
        }
        *_end=x;
        node* t=_end.p;
        _end.p->next=new node;
        ++_end;
        _end.p->prev=t;
        _end.p->next=0x0;
        _sz++;
    }
    myList():_sz(0){}
    iterator erase(iterator i)
    {
        node* t=i.p;
        if(i.p->prev)i.p->prev->next=i.p->next;
        else ++_beg;
        if(i.p->next)i.p->next->prev=i.p->prev;
        else --_end;
        ++i;
        delete t;
        _sz--;
        if(!_sz)i.p=0x0;
        return i;
    }
};

//bicycles end

struct tree
{
    int id;
    pair<tree*,int> parent;
    myList<pair<tree*,int> > child;
    int max,nMax;
    int neighborsConsidered;
    bool f;
    tree():parent(pair<tree*,int>((tree*)0x0,-1)),max(0),nMax(0),neighborsConsidered(0),f(0){}
};

inline pair<int,int> gen_tree(tree* station,int N)
{
    int max=0, nMax=0;
    tree *root;
    queue<int> q;
    for(int i=0;i<N;++i)
        if(station[i].child.size()==1)q.push(i),station[i].nMax=1;
    while(!q.empty())
    {
        int current=q.front();
        q.pop();
        if(station[current].f)continue;
        if(station[current].neighborsConsidered<(int)station[current].child.size()-1)
        {
            q.push(current);
            continue;
        }
        station[current].f=true;
        myList<pair<tree*,int> >::iterator i;
        for(i=station[current].child.begin();i!=station[current].child.end();++i)
            if(!station[i->first->id].f)break;
        if(i==station[current].child.end())
        {
            root=&station[current];
            station[current].parent.first=0x0;
            station[current].parent.second=-1;
        }
        else
        {
            station[current].parent=*i;
            station[current].child.erase(i);
            station[current].parent.first->neighborsConsidered++;
            q.push(station[current].parent.first->id);
        }
        int tMax=-1,nTMax=0,curMax,nCurMax,nMaxBranches=0;
        for(myList<pair<tree*,int> >::iterator i=station[current].child.begin();i!=station[current].child.end();++i)
        {
            if(i->first->max+i->second>station[current].max)
            {
                tMax=station[current].max;
                nTMax=station[current].nMax;
                station[current].max=i->first->max+i->second;
                station[current].nMax=i->first->nMax;
                nMaxBranches=1;
            }
            else if(i->first->max+i->second==station[current].max)
                station[current].nMax+=i->first->nMax,nMaxBranches++;
            else if(i->first->max+i->second>tMax)
            {
                tMax=i->first->max+i->second;
                nTMax=i->first->nMax;
            }
            else if(i->first->max+i->second==tMax)
                nTMax+=i->first->nMax;
        }
        if(station[current].child.size()==1)continue;
        if(nMaxBranches==1)
        {
            curMax=station[current].max+tMax;
            nCurMax=2*station[current].nMax*nTMax;
        }
        else
        {
            curMax=2*station[current].max;
            nCurMax=0;
            for(myList<pair<tree*,int> >::iterator i=station[current].child.begin();i!=station[current].child.end();++i)
            {
                if(i->first->max+i->second!=station[current].max)continue;
                nCurMax+=(station[current].nMax-i->first->nMax)*(i->first->nMax);
            }
        }
        if(curMax>max)
        {
            max=curMax;
            nMax=nCurMax;
        }
        else if(curMax==max)
            nMax+=nCurMax;
    }
    return pair<int,int>(max,nMax);
}

int main()
{
    srand(time(0));
    int N;
    scanf("%d",&N);
    int src,dst,price;
    static tree station[100000];
    for(int i=0;i<N;i++)
        station[i].id=i;
    if(N==2)
    {
        int res,a;
        scanf("%d%d%d",&a,&a,&res);
        printf("%d 2\n",res);
        return 0;
    }
    for(int i=0;i<N-1;i++)
    {
        scanf("%d%d%d",&temp.src,&temp.dst,&temp.price);
        src--, dst--;
        station[src].child.push_back(pair<tree*,int>(&station[dst],price));
        station[dst].child.push_back(pair<tree*,int>(&station[src],price));
    }
    pair<int,int> res=gen_tree(station,N);
    printf("%d %d\n",res.first,res.second);
}

Тепер Задачі, по яким бал трохи не повний smile

DDR3
Як і у багатьох, у мене по цій задачі 57 балів. Чи не може журі повідомити той злощасний тест, на якому повалилися всі рішення, крім одного? smile

Ідея рішення - бінарний пошук, і куча формул, які треба дуже довго пояснювати. Може коли з’явиться натхнення, і якщо комусь потрібно буде пояснення до цих формул - напишу.

Код:

#include <iostream>
#include <cmath>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned ul;
typedef long double ld;

ull fast_pow(ull n,ull power)
{
    ull res=1;
    while(power)
    {
        if(power&1)
            res*=n;
        n*=n;
        power>>=1;
    }
    return res;
}

ull n_digits_count(ull n)
{
    if(n==1)return 9;
    return 9*fast_pow(10,n-1);
}

ull str_len(ull n)
{
    ull res=0;
    ull t=ceil(log10(n+1));
    for(ull i=1;i<t;++i)
    {
        res+=i*n_digits_count(i);
    }
    res+=t*(n-fast_pow(10,t-1)+1);
    return res;
}

ull get_ith_digit(ull n,ull i,ull t)
{
    return (n/fast_pow(10,t-i))%10;
}

ull consecutive_repeats(ull n,ull t,bool init=1)
{
    if(n<10&&t<2)return 0;
    ull res=0;
    ull threshold=fast_pow(10,t-1);
    ull first,second;
    if(n>=threshold)
    {
        first=get_ith_digit(n,1,t);
        second=get_ith_digit(n,2,t);
    }
    else if(n>=threshold/10)
    {
        first=0;
        second=get_ith_digit(n,1,t-1);
    }
    else first=second=0;
    res+=(first-init)*fast_pow(10,t-2)*(t-1);
    if(second>first)res+=fast_pow(10,t-2);
    else if(second==first)res+=n%fast_pow(10,t-2)+1;
    return res+consecutive_repeats(n%fast_pow(10,t-1),t-1,0);
}

ull repeats_count(ull n)
{
    if(n<10)return 0;
    ull t=ceil(log10(n+1));
    ull first=get_ith_digit(n,1,t),last=get_ith_digit(n,t,t);
    ull res=(first-1)*fast_pow(10,t-2)+(n/10)%fast_pow(10,t-2)+(last>first)+(first==9);
    return res+consecutive_repeats(n,t)+repeats_count(fast_pow(10,t-1)-1);
}

ull solver(ull n)
{
    return str_len(n)-repeats_count(n);
}

ull bin_search(ull l, ull r, ull query, ull(*f)(ull))
{
    for(ull i=0;i<200&&l<r;++i)
    {
        ull mid=l+((r-l)>>1);
        if(f(mid)<query)l=mid;
        else r=mid;
    }
    return query==f(l)?l:r;
}

int main()
{
    ull n;
    cin>>n;
    cout<<bin_search(1,fast_pow(10,19),n,solver)<<endl;
}

Tourist
Завжди недолюблював задачі на геометрію і отримав тут 54 бали smile

Моя ідея була такою:
Будуємо для нашого набору точок опуклу оболонку і перевіряємо, щоб точки з початкового набору йшли в порядку обходу опуклої оболонки, при чому не обходили її більше одного разу.

Але, як це часто буває, після якоїсь правки з’явився баг, на перший погляд, абсолютно з тією правкою не пов’язаний. А помітив я його уже після відправки.

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

Відредаговано Dim_ov (2012-02-03 21:06:29)

Поза форумом

 

#2 2012-02-03 19:58:52

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Закінчення олімпіади і розв’язки задач 3 туру

Все, свої рішення виклав.
Буду вдячний, якщо хтось вкаже на помилку в DDR3, або викладе кращий розв’язок Туриста.

Відредаговано Dim_ov (2012-02-03 21:51:38)

Поза форумом

 

#3 2012-02-03 22:54:29

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Re: Закінчення олімпіади і розв’язки задач 3 туру

Dim_ov написав:

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

Мова точно йде про використання ТІЛЬКИ цієї ідеї??? У мене виходить, начебто тільки її використання дає 26 балів, що теж наче й забагато, але терпимо.

ГАРАНТУЮ, що відповідь НЕ буде використана для того, щоб зменшити бали за відповідний розв"язок. Результати оголошені (нехай лише як попередні, але оголошені), й зміна тестів гіпотетично можлива ЛИШЕ у разі виявлення явної помилки в тестах. А такого поки що нема (і, сподіваюсь, не буде).

- - -

Беручи статистику по всім учасникам, найбільше вердиктів "(Wrong Answer)" по тесту №16. Я не_передивлявся усі розв"язки, і навряд чи це робитиму, але серед тих, які передивився, абсолютно всі не_враховували ситуацію, коли одночасно A[1]==A[2] та A[n-1]==A[n] і при цьому сАме вершина A[n] єдина порушує опуклість.

Друге місце за кількістю вердиктів "(Wrong Answer)" займає тест №21. Він має вигляд 3 4 0 0 3 3 1 1 4 4 3 0 0 3 3 1 1 2 0 0 3 3 (або, якщо відформатувати у більш красивому вигляді, то
3
4   0 0  3 3  1 1  4 4
3   0 0  3 3  1 1
2   0 0  3 3
) і відповідь 0 1 1.

Значну кількість вердиктів "(Wrong Answer)" (6-те місце) має також тест №21, який має вигляд 2 4 -99999998 -99999999 0 0 99999999 100000000 17 42 4 -99999998 -99999999 0 0 99999999 100000000 42 17 (або, якщо відформатувати у більш красивому вигляді, то
2
4     -99999998 -99999999   0 0   99999999 100000000   17 42
4     -99999998 -99999999   0 0   99999999 100000000   42 17
) і відповідь 0 1. Проблема в тому, що при обчисленні напрямку повороту у вершині з координатами 0 0 значна кількість способів дають помилкову відповідь "сусідні з цією вершиною сторони спінапрямлені" (тоді як фактично відбувається дуже малий поворот у від"ємному напрямку (за годинниковою стрілкою)). Аналогічна ситуація у тестах 13, 14 і 30 (але в кожному з них це не єдина проблема).

- - -

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

Поза форумом

 

#4 2012-02-03 23:31:22

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Закінчення олімпіади і розв’язки задач 3 туру

Ilya Porublyov написав:

Мова точно йде про використання ТІЛЬКИ цієї ідеї??? У мене виходить, начебто тільки її використання дає 26 балів, що теж наче й забагато, але терпимо.

Зараз сказати не можу, деталями особливо не цікавився. У понеділок спитаю, чи використовувалось там ще щось і відповім.

Поза форумом

 

#5 2012-02-04 08:15:20

byme8
Новий користувач
Зареєстрований: 2012-01-18
Повідомлень: 6

Re: Закінчення олімпіади і розв’язки задач 3 туру

Я не можу зрозуміти чому моя програма dividers проходе тест на 7 балів.Ще до того тест пише:
FAILED (Wrong Answer)
моя програма просто бере і переділяе всі числа на проміжку.
Ось її код:

Код:

#include <iostream>
using namespace std;

int main()
{
    int i,min=1,ost,k=0,kg=1,max,h=1;
    cin>>max;
    
             for(i=min;i<max;i++)
    {h=1;
                                        for(h;h<=i;h++)
                                  {
                                  ost=i%h;
                                  if (ost==0)
                                  {k++;}
                                  else
                                  {ost=0;}}
                                  if (kg>k)
                                  {k=0;}
                                  else
                                  {kg=k;
                                  k=0;}
                                 
                                  
    }
    cout<<kg;
}

В чому проблема???

Поза форумом

 

#6 2012-02-04 09:05:04

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Закінчення олімпіади і розв’язки задач 3 туру

byme8 написав:

Я не можу зрозуміти чому моя програма dividers проходе тест на 7 балів.Ще до того тест пише:
FAILED (Wrong Answer)
моя програма просто бере і переділяе всі числа на проміжку.
Ось її код:

...

В чому проблема???

Змініть тип int на unsigned long long і умову зовнішнього циклу виправте.
Замість

Код:

i<max

Напишіть

Код:

i<=max

І отримаєте правильне, але неймовірно повільне рішення, яке заслужено бере свої 8 балів.

Відредаговано Dim_ov (2012-02-04 09:22:32)

Поза форумом

 

#7 2012-02-04 09:37:52

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Закінчення олімпіади і розв’язки задач 3 туру

Ilya Porublyov написав:

Також дуже цікавлять всі думки щодо того, як правильно створювати набір тестів по цій задачі.

Вчора не подивився, на яких тестах валиться моя програма, і чому. А сьогодні з подивом помітив, що валиться вона не на ВА, а на ТЛ-ах у 2, 4 і 5 тестах. Тобто мій баг, схоже, виявився не поміченим тестами(хіба-що, потрібні тести, за збігом, були серед ТЛ-них).


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

Код:

1
6
0 0
2 2
4 0
0 0
2 2
4 0

Вона видавала одиницю, тоді як правильна відповідь - 0.

Відредаговано Dim_ov (2012-02-04 16:32:09)

Поза форумом

 

#8 2012-02-04 16:39:35

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Закінчення олімпіади і розв’язки задач 3 туру

Ні, все-таки тестів, подібних до того, що я виклав вище не було.

Ilya Porublyov написав:

Взагалі -- дуже цікавить, які саме ідеї все-таки вдасться довести до повного бала.

Для цього набору тестів я свою довів до 60.
Ось код.
Сильно за нього не бийте - виправлявся він нашвидкоруч, може бути багато зайвих, чи навіть безглуздих, перевірок, і кількаразовий обхід оболонки досі опрацьовується неправильно.

Поза форумом

 

#9 2012-02-06 14:30:20

VIRUS
Новий користувач
Звідки: Днепропетровск
Зареєстрований: 2011-10-29
Повідомлень: 30

Re: Закінчення олімпіади і розв’язки задач 3 туру

Dim_ov в мене до Вас питання. Можете будь ласка дати свій скайп або аську або ще щось якщо є. Дякую...


Чтобы найти баг, ты должен мыслить к как баг.

Поза форумом

 

#10 2012-02-06 16:53:26

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Закінчення олімпіади і розв’язки задач 3 туру

Ilya Porublyov написав:

Мова точно йде про використання ТІЛЬКИ цієї ідеї??? У мене виходить, начебто тільки її використання дає 26 балів, що теж наче й забагато, але терпимо.

Ні, ще виконувалася "звичайна" перевірка фігури на опуклість(Всі повороти мають бути в одну сторону)

Поза форумом

 

#11 2012-02-06 20:31:46

VIRUS
Новий користувач
Звідки: Днепропетровск
Зареєстрований: 2011-10-29
Повідомлень: 30

Re: Закінчення олімпіади і розв’язки задач 3 туру

Є приклад фігури, у якої всі повороти в одну сторону, але вона не опукла.


Чтобы найти баг, ты должен мыслить к как баг.

Поза форумом

 

#12 2012-02-06 20:34:13

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 312
Вебсайт

Re: Закінчення олімпіади і розв’язки задач 3 туру

VIRUS написав:

Є приклад фігури, у якої всі повороти в одну сторону, але вона не опукла.

Подивіться діалог спочатку. Крім перевірки на те, що всі повороти в одну сторону, ще рахувалась кількість змін напрямку руху по вісях Х та У

Поза форумом

 

#13 2012-02-07 07:58:27

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Re: Закінчення олімпіади і розв’язки задач 3 туру

VIRUS написав:

Є приклад фігури, у якої всі повороти в одну сторону, але вона не опукла.

Це твердження ("дійсно, є") чи запитання ("а що, є?")?
Якщо запитання -- то так, є, наприклад, п"ятикутна зірка, якщо її малювати з 1-ї вершини у 3-тю, далі в 5-ту, далі в 2-ту, далі в 4-ту, далі вернутися в 1-шу.

Dim_ov написав:

не завжди працювала для випадків, коли опукла оболонка обходиться кілька разів.

Dim_ov написав:

Ні, все-таки тестів, подібних до того, що я виклав вище не було.

Дійсно, не було.
Дійсно, в даній задачі передбачити у тестах все виявилося досить складно. Ще_складніше, ніж розглянути всі випадки у програмі--розв"язку, а з цим теж ніхто з учасників не_впорався...

Причому, в 23-му тесті таки є маршрут
16
-303 -569
-399 -462
-444 -401
-378 -47
-303 -569
-399 -462
-444 -401
-378 -47
-206 217
106 429
568 465
677 430
1034 196
1186 -34
1288 -276
1092 -732
і ще в 26-му щось подібне. Я чомусь думав що такий тест має виявити ті самі проблеми розв"язків, що й кількакратний обхід оболонки. Як виявилося -- не обов"язково.

Dim_ov написав:

ще виконувалася "звичайна" перевірка фігури на опуклість(Всі повороти мають бути в одну сторону)

Так обидві перевірки ("всі повороти в одну сторону" та "правильна кількість змін напрямку руху по вісях Х та У") разом узяті, якщо їх правильно дошліфувати в усіх дрібницях, дають повний розв'язок! І 56 балів -- не забагато, а, навпаки, 4 бали втрачені, бо погано враховані якісь дрібниці.

Поза форумом

 

#14 2012-02-08 19:28:15

VIRUS
Новий користувач
Звідки: Днепропетровск
Зареєстрований: 2011-10-29
Повідомлень: 30

Re: Закінчення олімпіади і розв’язки задач 3 туру

Ilya Porublyov написав:

Це твердження ("дійсно, є") чи запитання ("а що, є?")?

Там не було знаку запитання!


Чтобы найти баг, ты должен мыслить к как баг.

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt