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


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

Ви не зайшли.

#76 2009-01-22 23:15:24

TheEvilOfTheDay
Новий користувач
Звідки: Подалі від Київського Лідеру..
Зареєстрований: 2008-11-29
Повідомлень: 12
Вебсайт

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

redman17 написав:

еще раз абсолютно однозначное мое ЛИЧНОЕ мнение после МНОГОКРАТНОГО прочтение диалога (в трезвом уме и ясной памяти smile ):

- еще раз представьте аналогию с обыкновенными предметными олимпиадами - аналогичная ситуация с вопросами к жури, трактовками условий и "уходом" с олимпиады за 3 часа до конца

- Ваши расчеты видятся мне весьма приблизительными, если вообще точными - условия на машине, на которой Вы замеряли время, наверняка отличны от условий проверки решений на олимпиаде

- "реальней замерять время" - еще раз перечитайте предложение со словами "наиболее эффективное решение" и "неправдоподобные подсчеты"

- последнее предложение:
а) совершенно отбивает охоту продолжать дискуссию
б) является по меньшей мере некорректным и не вписывающимся в рамки правил форума
в) по-моему ваше первое сообщение - призыв к дискуссии с другими участниками и жури, последнее предложение - что-то типо "пошел вон" (МОЕ ЛИЧНОЕ МНЕНИЕ)

В мене дійсно немає бажання продовжувати цю дискусію, оскілки ви читаєте мій пост частково і опускаєте можливі фактори, і навіть деякі частини, ось наприклад як зараз ("наиболее эффективное решение" и "неправдоподобные подсчеты", про це я написав трохи нижче ніж "реальней замерять время".)

Останнє речення несе характер "досит викручувати мої слова і недочитувати до кінця".

Вибачте звісно, якщо я вас чимось образив...

Мій перший пост є чисто моїми підрахунками, поріняннями, в кінці, якого прохання журі трохи подумати над написаним.

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

ЩЕ РАЗ ВИБАЧТЕ КОГО ОБРАЗИВ.

Поза форумом

 

#77 2009-01-23 09:11:37

Журі_Пасіхов
Гість

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

TheEvilOfTheDay написав:

От мені хотілось би дізнатись від журі декілька відповідей (але я розумію, що я їх не отримаю).

Мені от цікаво який в них стоїть проц? Pentium 1, чи що?
В мене перша задача максимальний тест проходить на проці 2.4Ггц, за 0.07с, а тут ТЛ на 0.34, тобто по співвдношенню це виходить приблизно 0.5Ггц на тестуючій машині.

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

Чому неможна вимкнути сервер від мережі буквально на 80 * 6 * 1 * 30 сек = 14400 сек = 4 год (це вже якщо на кожну задачу по 30 тестів і ТЛ по 1 секунді), щоб протестувати рішення.
Чи серверу так краще думати, коли одночасно надсилають на онлайн перевірку?
При онлайн перевірці іноді різниця виходить в 5+ балів, чому тоді не ставиться найвища?

Якщо ж тестується розвязок на машині в 0.5Ггц, то можете пояснити, будь-ласка, яка в цьому мета? Привчити олімпіадників (у майбутньому розробників та кібернетиків) програмувати на ЕВМ? Навіть на всеукрі тестували на 2х ядерному проці.

Я просто не можу зрозуміти цих пунктів....

І чесно кажучи на одній з найкращих олімпіад, на мій погляд, ТопКодері на одних і тих самих тестах, программа працює приблизно в 5 разів швидше ніж на Core-2-Quad 2.5Ghz, 4.00GB RAM, тому можливо журі треба зробити якісь логічні висновки звідси?

Чому ж, отримаєте...
1. Для перевірки використовується потужна програмно-апаратна платформа, але спроектована таким чином, щоб відділяти повільні розв'язки від швидких. Ваше намагання знайти пропорційність між часом проходження РІЗНИХ тестів і частотою різних процесорів, ще й без врахування умов переврки недолуге.

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

3. Мережу вимкнути можна. Але тоді журі не зможе відлагодити тести. Воно в сервері не сидить. :-)

4. Різниця при жорстких тайм-лімітах вивнкає в випадку часу проходження теста "на грані". Але якщо врахувати, що час проходження теста виставлено в 2 ( а інколи і в 3) рази більший, ніж час кращого розв'язку, що його має журі то однозначно, тестований розв'язок повинен мати меншу кількість балів.

5. Мета одна. Навчити  учасників гарно думати, а не швидко топтатися по кнопках  на клавах швидких машин. Для майбутніх розоробників, як ви слушно відмітили, це ДУЖЕ корисна навичка.  ОСЬ ЧОМУ В НАШІЙ ОЛІМПІАДІ ТРИВАЛІ ТУРИ І ЖОРСТКІ ТАЙМ-ЛІМІТИ.
Те, що хтось робить не так... як уміють і розуміють, так і роблять. Там, найчастіше, головна мета - знайти чемпіона-самородка, який переможе на міжнародній оліпміаді, і це оправдано. У нас мета інша- створити умови, за яких цей самородок зможе навчитися бути самородком.

 

#78 2009-01-23 12:00:13

Cris
Новий користувач
Звідки: Сумы
Зареєстрований: 2007-10-02
Повідомлень: 140

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

Журі_Пасіхов написав:

уважаемое жури а когда обьявят пропускной бал на 4-й тур?

Поза форумом

 

#79 2009-01-23 14:30:35

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

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

В этой теме про лампочки ничего толкового не сказано, потому расскажу свое решение(60/60).
Пусть f(i,j) это количество способов получить за i операций j включеных лампочек, если всего их N. Получим:
f(i,j)=f(i-1,j-1)*(n-j+1)+f(i-1,j+1)*(j+1)
Это верно, потому что мы можем либо зажечь одну лампочку, т.е. из f(i-1,j-1) перейти в f(i,j), но сделать это мы можем (n-j+1) способами, т.к. ровно столько лампочек не горело на предыдущем шагу, либо мы можем потушить одну лампочку, т.е. перейти из f(i-1,j+1) в f(i,j) ровно (j+1) способами.
Первым числом из ответа будет f(k,n).
Для второго числа следует заметить, что N переключений должны быть сделаны в первой половине, остальные же могут быть сделаны как в первой, так и во второй половине. Следовательно, k-n переключений могут быть сделаны как в левой, так и в правой половине. Не трудно убедиться, что второе число из ответа равно f(k,n)*2^(k-n), где операция ^ это возведение в степень.

Вот код:

Код:

#define _CRT_SECURE_NO_DEPRECATE
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <iostream>
#include <iterator>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <sstream>
#include <fstream>
#include <ctime>
#pragma comment(linker, "/STACK:16777216")
using namespace std;
#define pb push_back
#define ppb pop_back
#define pi 2*acos(0.0)
#define mp make_pair
#define x first
#define y second
#define sqr(a) (a)*(a)
#define D(a,b) sqrt(((a).x-(b).x)*((a).x-(b).x)+((a).y-(b).y)*((a).y-(b).y))
#define pii pair<int,int>
#define pdd pair<double,double>
#define sz(x) int((x).size())
#define INF 1000000000
#define FOR(i,a,b) for (int _n(b), i(a); i <= _n; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;i--)
#define all(c) (c).begin(), (c).end()
#define SORT(c) sort(all(c))
#define rep(i,n) FOR(i,1,(n))
#define rept(i,n) FOR(i,0,(n)-1)
#define L(s) (int)((s).end()-(s).begin())
#define C(a) memset((a),0,sizeof(a))
#define val(ch) (int)(ch)-(int)('0')
#define toch(a) (char)((int)(a)+(int)('0'))
#define VI vector <int>
#define ll long long
const int LN=50;
class lng
{
public:
    int n[LN+1];
    inline void tol(int a)
    {
        C(n); n[0]=1; n[LN]=a;
    }
    inline void toc(int a)
    {
        n[0]=1; n[LN]=a;
    }
};
inline lng operator +(const lng &a,const lng &b)
{
    lng res; C(res.n);
    int len=max(a.n[0],b.n[0]);
    FORD(i,LN,LN-len+1)
    {
        int m=res.n[i]+a.n[i]+b.n[i];
        res.n[i]=m%10000; res.n[i-1]=m/10000;
    }
    (res.n[LN-len]!=0)?res.n[0]=len+1:res.n[0]=len;
    return res;
}
inline lng operator *(const lng &a,const lng &b)
{
    lng res; C(res.n);
    if (a.n[0]==0 || b.n[0]==0) return res;
    int p=0;
    int npos=INF;
    FORD(i,LN,LN-b.n[0]+1)
    {
        FORD(j,LN,LN-a.n[0]+1)
        {
            int m=res.n[j-p]+a.n[j]*b.n[i];
            res.n[j-p]=m%10000;
            if (m%10000) npos=min(npos,j-p);
            res.n[j-p-1]+=m/10000;
            if (m/10000) npos=min(npos,j-p-1);
        }
        p++;
    }
    while (npos<=LN && res.n[npos]==0) npos++;
    while (npos>1 && npos<=LN && res.n[npos-1]!=0) npos--;
    res.n[0]=LN-npos+1;
    return res;
}
inline void out(const lng &a)
{
    FOR(i,LN-a.n[0]+1,LN)
    {
        if (i==LN-a.n[0]+1) printf("%d",a.n[i]); else
        if (a.n[i]<10) printf("000%d",a.n[i]); else
        if (a.n[i]<100) printf("00%d",a.n[i]); else
        if (a.n[i]<1000) printf("0%d",a.n[i]); else
        printf("%d",a.n[i]);
    }
}
int a,b,c,d,i,j,n,m,k,now,last;
lng mas[52][2],tmp;
int main()
{
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    scanf("%d%d",&n,&k);
    if (n>k) 
    {
        printf("0 0\n");
        exit(0);
    }
    now=0; 
    mas[0][0].tol(1);
    tmp.tol(0);
    rep(i,k)
    {
        last=now; now^=1;
        rept(j,n+1)
        {
            mas[j][now].tol(0);
            tmp.toc(j+1);
            if (j!=n) mas[j][now]=mas[j+1][last]*tmp;
            tmp.toc(n-j+1);
            if (j!=0) mas[j][now]=mas[j][now]+mas[j-1][last]*tmp;
        }
    }
    out(mas[n][now]);
    printf(" ");
    if (mas[n][now].n[0]==0 || (mas[n][now].n[0]==1 && mas[n][now].n[LN]==0)) 
    {
        printf("0\n");
        exit(0);
    }
    tmp.tol(1);
    lng tmp1;
    tmp1.tol(2);
    rep(i,k-n)
    {
        tmp=tmp*tmp1;
    }
    tmp=tmp*mas[n][now];
    out(tmp);
    printf("\n");
}

Поза форумом

 

#80 2009-01-23 18:40:11

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

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

Вельмишановний Пасіхов, чи не могли б ви пояснити яким чином в мене вийшов таймаут в задачі стрімер (1.8 сек), в якій ВЗАГАЛІ немає циклів та ріделенів??? (задачі 1, 7, 12, 16 та 17)
вибачте, що пишу в темі, бо пм на форумі немає, а на мило писати впадлу.

Поза форумом

 

#81 2009-01-23 19:04:13

Seyaua
Новий користувач
Звідки: Харьков
Зареєстрований: 2009-01-07
Повідомлень: 12

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

astor

Во-первых у тебя немного некорекктный тон по отношению к жюри.
Во-вторых тайм-лимит может быть связан с делением на 0 (runtime error, но программa не обрывалась). То есть возможно у тебя какие то случаи в этой задаче прописаны неправильно. Проверь свое решение на тесте: 5 5 0 5.

Відредаговано Seyaua (2009-01-23 19:13:22)

Поза форумом

 

#82 2009-01-23 19:19:01

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

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

astor

Во-первых у тебя немного некорекктный тон по отношению к жюри.
Во-вторых тайм-лимит может быть связан с делением на 0 (runtime error, но программa не обрывалась). То есть возможно у тебя какие то случаи в этой задаче прописаны неправильно. Проверь свое решение на тесте: 5 5 0 5.

я пишу тому, що перший раз мене проігнорували. І ДЕ в мене некоректний тон, не скажеш, ні???
тест твій пройшов відразу. відповідь: 1.25000000000Е+001

Поза форумом

 

#83 2009-01-23 19:24:05

Seyaua
Новий користувач
Звідки: Харьков
Зареєстрований: 2009-01-07
Повідомлень: 12

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

А когда ты считаешь пересечение отрезков, ты учитываешь то что они могут быть параллельными?

Поза форумом

 

#84 2009-01-23 19:29:50

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

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

А когда ты считаешь пересечение отрезков, ты учитываешь то что они могут быть параллельными?

не сильно зрозумів. дай тест.

Поза форумом

 

#85 2009-01-23 19:36:52

Seyaua
Новий користувач
Звідки: Харьков
Зареєстрований: 2009-01-07
Повідомлень: 12

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

тесты:

#1: 5 5 0 0
#2: 8 3 2 5

Поза форумом

 

#86 2009-01-23 19:47:03

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

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

відповіді
№1 2.5000000000000Е+001
№2 1.6500000000000Е+001

Поза форумом

 

#87 2009-01-23 19:50:43

Seyaua
Новий користувач
Звідки: Харьков
Зареєстрований: 2009-01-07
Повідомлень: 12

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

Значит не знаю где ошибка (трудно её искать не зная даже алгоритма).
Но все равно думаю, что скорее всего где-то возникает RE.

Поза форумом

 

#88 2009-01-23 19:51:15

Журі_Пасіхов
Гість

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

astor написав:

Вельмишановний Пасіхов, чи не могли б ви пояснити яким чином в мене вийшов таймаут в задачі стрімер (1.8 сек), в якій ВЗАГАЛІ немає циклів та ріделенів??? (задачі 1, 7, 12, 16 та 17)
вибачте, що пишу в темі, бо пм на форумі немає, а на мило писати впадлу.

1. Дякую  за "вельмишановного". Відповісти взаємністю мені, схоже, важкувато.
2. Це ви повинні пояснити собі, чому у вас вийшов таймаут. Я ж цього зробити не можу, тому що не знаю, хто ви. Якби ви  написали, як годиться, листа з темою АПЕЛЛЯЦІЯ на адресу олімпіади, вказали свій код і суть проблеми, то обов'язково отримали б вичерпну відповідь, а якщо є наша помилка, то й вибачення. Але помилок в тестах до цієї задачі, схоже, немає. До того ж працює он-лайн перевірка ... А шукати в протоколі офіційної  перевірки кількох сотень розв'язків той, в якого не пройшли  "задачі" (очевидно, мова йде про тести  №№1,7,12,17) мені (sorry) "впадлу", та й де гарантія, що ви один такий кмітливий?

 

#89 2009-01-23 19:55:41

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

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

1. Дякую  за "вельмишановного". Відповісти взаємністю мені, схоже, важкувато.
2. Це ви повинні пояснити собі, чому у вас вийшов таймаут. Я ж цього зробити не можу, тому що не знаю, хто ви. Якби ви  написали, як годиться, листа з темою АПЕЛЛЯЦІЯ на адресу олімпіади, вказали свій код і суть проблеми, то обов'язково отримали б вичерпну відповідь, а якщо є наша помилка, то й вибачення. Але помилок в тестах до цієї задачі, схоже, немає. До того ж працює он-лайн перевірка ... А шукати в протоколі офіційної  перевірки кількох сотень розв'язків той, в якого не пройшли  "задачі" (очевидно, мова йде про тести  №№1,7,12,17) мені (sorry) "впадлу", та й де гарантія, що ви один такий кмітливий?

ну ок. але на сайті я не знайшов інформації про апеляцію. чекайте мого листа.
+ 16 пропустили.

Відредаговано astor (2009-01-23 20:05:05)

Поза форумом

 

#90 2009-01-24 16:11:13

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

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

redman17 написав:

кстати насчет размещенных тут мною решений:
NEWCALC  - 60/60
TETRIS      - 60/60
STREAMER - 57/60 (одна BAD DATA - будем разбираться)
TREASURE - 58/60 (один WRONG ANSWER - аналогично)

мой LAMPSPLUS - 24/60, а потому об идее распространяться и не стоит

кстати насчет размещенных тут мною решений:
NEWCALC  - 60/60
TETRIS      - 60/60
STREAMER - 57/60 (одна BAD DATA - будем разбираться)
TREASURE - 52/60 (три WRONG ANSWER - уже ясно почему)

мой LAMPSPLUS - 24/60, а потому об идее распространяться и не стоит


WE DIE HARD!!!

Поза форумом

 

#91 2009-01-24 20:45:27

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

Re: Разбор задач третьего тура интернет-олимпиады Net-OI-2008

Мне больше сняли smile

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt