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

reiten · 2008-01-10 16:33:22

Dark_Dimius написав:
БОООООООЛЬШАЯ благодарность авторам задач.... задачи ОЧЕНЬ понравились

Спасибо!

Oracle · 2008-01-10 17:12:47

Робив так само як Руслан, але відстань між відрізками знаходив бінарним пошуком, але нажаль, 6 ВА і 4 ТЛ, хоча ВА, підозрюю, через те, що не врахував, що час має бути строго більший 0. Доречі, на тесті Руслана моя прога дає 0.000491 0.007910.

MAXXX · 2008-01-10 18:25:01

тесты нв все кроме нави в онлайн проверке!
провенрил свои...
ньюгарден 60
нави ?? - ладно, много и не будет:))
лого 60
сайтсиинг 60
патрол 56 - обиииидно то как:(
но больше всего мне понравилось это:
(тест к сайтсиинг, последний)
10 PASSED (+6) 5.75 сек.
Какой же был таймлимит???!

и еще интерестно - почему код со сложностью N*M*K работает тааааак долго? (пусть даже с даблами). кстати, вот он:

Код:

#include <cstdlib>
#include <iostream>
#include <cstdio>
using namespace std;
double l[102][102],r[102][102],u[102][102],d[102][102],s[102][102],a[102][102],c[2][102][102];
int k,n,m,i,j,x,y,cnt,cur,last;
int main()
{
    cin>>n>>m>>k>>x>>y;k/=5;
    for(i=0;i<=n+1;i++)for(j=0;j<=m+1;j++)
    {l[i][j]=0;r[i][j]=0;u[i][j]=0;d[i][j]=0;
     s[i][j]=0;c[0][i][j]=0;c[1][i][j]=0;}
    for(i=1;i<=n;i++)for(j=1;j<=m;j++)
    {cin>>u[i][j]>>l[i][j]>>d[i][j]>>r[i][j]>>s[i][j];
    u[i][j]/=100;d[i][j]/=100;l[i][j]/=100;
    r[i][j]/=100;s[i][j]/=100;}
    c[0][x][y]=100;cur=0;last=1;
    for(cnt=0;cnt<k;cnt++){cur=last;last=1-cur;
    for(i=1;i<=n;i++)for(j=1;j<=m;j++)
    c[cur][i][j]=c[last][i][j]*s[i][j]+c[last][i-1][j]*d[i-1][j]+c[last][i+1][j]*
    u[i+1][j]+c[last][i][j-1]*r[i][j-1]+c[last][i][j+1]*l[i][j+1];}
    x=1;y=1;for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(c[cur][i][j]>c[cur][1][1])
    {c[cur][1][1]=c[cur][i][j];x=i;y=j;}printf("%d %d %0.7f\n",x,y,c[cur][x][y]);
    return EXIT_SUCCESS;
}

Відредаговано MAXXX (2008-01-10 18:31:02)

spiker · 2008-01-10 18:43:44

Дайте ссилку на он-ліне провірку ....

Skiminok · 2008-01-10 18:47:05

Ссылка вот. Но она тебе не поможет. Ибо онлайн-проверка лежиииит....

MAXXX · 2008-01-10 18:54:46

Цікаво..На тест Руслана у мене видає таку ж відстань, проте час 0.00008. Руслан, ти можешь якось перевірити чи довести правильність своєї відповіді? Прошу всіх тестувати свої програми ні цьому тесті. Цікаво дізнатись, яка відповідь правильна...
ЗІ. Точніше 0.00007875594

Відредаговано MAXXX (2008-01-10 18:59:12)

Skiminok · 2008-01-10 18:59:56

Задача patrol. Вышеуказанный тест
1000 20 3
2 0
-5 2
-2 -4

Мой ответ:
9.82258403563613E-0004 7.91038704773199E-0003

Расстояние идентично, время не равно ни результату Руслана, ни Андрея, ни Oracle...

З.Ы. Жестокий тест. Интересно, сколько в нём есть вариантов ответа?

Відредаговано Skiminok (2008-01-10 19:03:01)

simonenko · 2008-01-10 19:04:47

Skiminok написав:
Задача patrol. Вышеуказанный тест
1000 20 3
2 0
-5 2
-2 -4

Мой ответ:
9.82258403563613E-0004 7.91038704773199E-0003

Расстояние идентично, время не равно ни результату Руслана, ни Андрея, ни Oracle...

З.Ы. Жестокий тест. Интересно, сколько в нём есть вариантов ответа?

Это правильный ответ:
0.0000787559 0.0079103870

MAXXX · 2008-01-10 19:10:37

Я радий і не ставлю під сумнів твій професіоналізм, проте як саме ти визачив що ця відповідь правильна?

simonenko · 2008-01-10 19:22:14

MAXXX написав:
Я радий і не ставлю під сумнів твій професіоналізм, проте як саме ти визачив що ця відповідь правильна?

У Руслана точно не правильно находит первое число. У остальных не знаю, но выходит что тоже не правильно (или не совсем точно, ведь не взирая на несовпадение с нашим ответом, ответ то надо находить с точностью до третьего знака). А вообще у меня решение правильное, в он-лайн проверке проходило все 16 тестов, а насчет точности, то замена double на long double абсолютно не меняет ответ, так что я уверен, что этот ответ достаточно точный.

RuslanSM · 2008-01-10 19:54:17

Влад а ти вважаєш, що машина може зробити пару циклів, і береш відповідь по модулю???
Бо інакше правильність твоєї відповіді під великим сумнівом для мене і мого ПП .

Відредаговано RuslanSM (2008-01-10 19:55:29)

partisan · 2008-01-10 19:59:31

To Ruslan: Отловил глюк: при расстановке машин на отрезках нужен не 1 иф, а целый вайл. Однако все равно 2 вронга.

На твой тест выдало 0.000078

Відредаговано partisan (2008-01-10 20:00:19)

RuslanSM · 2008-01-10 20:02:28

Все знайшов помилку у ПП. Вибачення Владу

partisan · 2008-01-10 20:03:21

RuslanSM написав:
Влад а ти вважаєш, що машина може зробити пару циклів, і береш відповідь по модулю???
Бо інакше правильність твоєї відповіді під великим сумнівом для мене і мого ПП .

Пару циклів не треба (хоча це може залежати від алгоритму). У мене кожна машина їде до місця наступної і цього досить (дивись пост вище).

Phoenix_Ukraine · 2008-01-10 20:06:01

Фух... По Патрулю 60!
А по Sightseeing останній тест 5.14.. Теж 60. Після 25 сек на тест минулого року я вже нічому не дивуюся!

Skiminok · 2008-01-10 20:07:24

Итак, проверка поднялась.
Могу выдать только одно слово: "Оба-на..."

Patrol: 60
Sightseeing: 60
Logo: 60
NewGarden: 24!!!

BD в 9 тестах - это весело, ничего не скажешь... )
Буду разбираться.

simonenko · 2008-01-10 20:09:17

RuslanSM написав:
Влад а ти вважаєш, що машина може зробити пару циклів, і береш відповідь по модулю???
Бо інакше правильність твоєї відповіді під великим сумнівом для мене і мого ПП .

неосилил ....

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

MAXXX · 2008-01-10 20:11:10

Phoenix_Ukraine написав:
Фух... По Патрулю 60!
А по Sightseeing останній тест 5.14.. Теж 60. Після 25 сек на тест минулого року я вже нічому не дивуюся!

єєє.... на яку задачу???

Відредаговано MAXXX (2008-01-10 20:12:10)

Phoenix_Ukraine · 2008-01-10 20:11:17

А посиланнячко-то працює!

Правда, із Неві яісь глюки, тому і перевірки нема на нього...

partisan · 2008-01-10 20:11:22

To simonenko: а как ты делал проверку на расстояние, когда сравниваешь текущее с найденым ранее? А то с этим приколы. После понимания, что это надо, написал if( (cur<=mindist-eps) or ( (abs(cur-mindist)<eps) and (curtime<mintime) ) ).

Відредаговано partisan (2008-01-10 20:17:07)

RuslanSM · 2008-01-10 20:15:00

2partisan: Так само як і ми

partisan · 2008-01-10 20:17:49

RuslanSM написав:
2partisan: Так само як і ми

Просто < ? хіба? Чи ти про написане пізніше з eps?

Відредаговано partisan (2008-01-10 20:18:11)

RuslanSM · 2008-01-10 20:19:58

З перевірками (з eps) 99 відсотків.

Відредаговано RuslanSM (2008-01-10 20:20:21)

simonenko · 2008-01-10 20:21:19

partisan написав:
To simonenko: а как ты делал проверку на расстояние, когда сравниваешь текущее с найденым ранее? А то с этим приколы. После понимания, что это надо, написал if( (cur<=mindist-eps) or ( (abs(cur-mindist)<eps) and (curtime<mintime) ) ).

typedef double cfloat;

const cfloat eps = 1e-9;

inline int cmp (cfloat q, cfloat w) {
return q < w - eps ? -1 : q > w + eps ? 1 : 0;
}

if (cmp (res, R) > 0 || (cmp (res, R) == 0 && cmp (when, dist + hypot (x * t, y * t)) > 0)) {
res = R;
when = dist + hypot (x*t, y*t);
}

partisan · 2008-01-10 20:25:37

To simonenko: спасибо!

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

#51 2008-01-10 16:33:22

Re: Барабанная дробь...

Dark_Dimius написав:

#52 2008-01-10 17:12:47

Re: Барабанная дробь...

#53 2008-01-10 18:25:01

Re: Барабанная дробь...

Код:

#54 2008-01-10 18:43:44

Re: Барабанная дробь...

#55 2008-01-10 18:47:05

Re: Барабанная дробь...

#56 2008-01-10 18:54:46

Re: Барабанная дробь...

#57 2008-01-10 18:59:56

Re: Барабанная дробь...

#58 2008-01-10 19:04:47

Re: Барабанная дробь...

Skiminok написав:

#59 2008-01-10 19:10:37

Re: Барабанная дробь...

#60 2008-01-10 19:22:14

Re: Барабанная дробь...

MAXXX написав:

#61 2008-01-10 19:54:17

Re: Барабанная дробь...

#62 2008-01-10 19:59:31

Re: Барабанная дробь...

#63 2008-01-10 20:02:28

Re: Барабанная дробь...

#64 2008-01-10 20:03:21

Re: Барабанная дробь...

RuslanSM написав:

#65 2008-01-10 20:06:01

Re: Барабанная дробь...

#66 2008-01-10 20:07:24

Re: Барабанная дробь...

#67 2008-01-10 20:09:17

Re: Барабанная дробь...

RuslanSM написав:

#68 2008-01-10 20:11:10

Re: Барабанная дробь...

Phoenix_Ukraine написав:

#69 2008-01-10 20:11:17

Re: Барабанная дробь...

#70 2008-01-10 20:11:22

Re: Барабанная дробь...

#71 2008-01-10 20:15:00

Re: Барабанная дробь...

#72 2008-01-10 20:17:49

Re: Барабанная дробь...

RuslanSM написав:

#73 2008-01-10 20:19:58

Re: Барабанная дробь...

#74 2008-01-10 20:21:19

Re: Барабанная дробь...

partisan написав:

#75 2008-01-10 20:25:37

Re: Барабанная дробь...

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