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


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

Ви не зайшли.

#1 2006-10-27 23:49:44

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

А всеткаи она глючная

Всетаки со свойей крепкой двойкой по физике так не до чего и не дошел. Жаль конечно сразу знаю что максимум 80 балов - это тупо... И все же как эта физ-задрача решалась?


Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#2 2006-10-28 00:28:31

MAA
Новий користувач
Зареєстрований: 2006-10-27
Повідомлень: 6

Re: А всеткаи она глючная

Для N школ сопротивление между любой парой школ равно 2R/N. Количество пар - N(N-1)/2.

Поза форумом

 

#3 2006-10-28 11:31:52

necro
Олімпієць
Зареєстрований: 2005-11-19
Повідомлень: 134

Re: А всеткаи она глючная

Ну вот б...ха муха. И изза этой х...ни минус 20 баллов. Физикам халява а остальным - нарот...


Да что там "винница" под новый год... Матан - вот в чем сила

Поза форумом

 

#4 2006-10-30 15:45:40

IvanZaremba
Новий користувач
Зареєстрований: 2006-10-17
Повідомлень: 12

Re: А всеткаи она глючная

MAA написав:

Для N школ сопротивление между любой парой школ равно 2R/N. Количество пар - N(N-1)/2.

Н-да... Тепер зрозуміло, чому в мене 12 балів з 20: я вважав, що СПОЧАТКУ ПІДКЛЮЧАЮТЬ НОВУ ШКОЛУ, А ПОТІМ МІРЯЮТЬ ОПОРИ... Якщо журі буде наполягати, що з умови очевидно, що спочатку міряють а потім підключають, я не зможу аргументовано заперечити, що це не так.

Але, на мою суб'єктивну думку, варто було б або в умові написати "перед підключенням", а не "при підключенні", або дати більше прикладів входу/виходу, хоча б один з яких відкидав би таке трактування...

Відредаговано IvanZaremba (2006-10-30 15:48:34)

Поза форумом

 

#5 2006-10-30 15:49:23

Timchenko
Новий користувач
Зареєстрований: 2006-10-22
Повідомлень: 8

Re: А всеткаи она глючная

Согласен, но у каджого была возможность поискать ответы на вопросы в течении довольно длительного промежутка времени, все были в равных условиях. Будет несправедливо, если подобные задачи на знания какого-либо другого предмета будут предложены в 4ом туре.

Вот решение, отправленное мной, и набравшее полный балл:

var r: word;
     i,n,res: LongInt;
begin
  read(r,n);
  res:=0;
  for i:=3 to n do
    if 2*r mod i = 0
      then inc(res,i*(i-1) div 2);
  writeln(res);
end.

Відредаговано Timchenko (2006-10-30 15:51:08)


Не бойтесь делать то, чего никогда не делали, потому - что ковчег строил любитель, а Титаник - профессионалы...

Поза форумом

 

#6 2006-10-30 16:08:14

Yevgeniy
Новий користувач
Зареєстрований: 2006-10-14
Повідомлень: 67

Re: А всеткаи она глючная

smile

Відредаговано Yevgeniy (2006-10-30 17:05:46)


"Математика -- цариця наук, арифметика -- цариця математики."
      Карл Фрідріх Гаусс (1777 - 1855) - КОРОЛЬ МАТЕМАТИКІВ.

Поза форумом

 

#7 2006-10-30 20:49:01

Nicky Nick
Олімпієць
Звідки: Харьков
Зареєстрований: 2005-11-25
Повідомлень: 48
Вебсайт

Re: А всеткаи она глючная

Если кому-то интересно, то вот решение за O(корень из R). Жалко, что простое решение за O(N) также легко справляется с временным ограничением. Но на то это и первый тур...

Код:

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

int r,n;

int rez;

void ReadData()
{
    scanf("%i %i",&r,&n);
}

void Solve()
{
    r *= 2;
    rez = 0;

    int to = int(sqrt(r));
    int i1,i2;
    for (i1=3; i1<to; i1++)
    {
        if (r % i1 == 0)
        {
            i2 = r / i1;
            if (i1 <= n)
                rez += i1*(i1-1)/2;
            if (i2 <= n)
                rez += i2*(i2-1)/2;
        }
    }

    if (r <= n)
        rez += r*(r-1)/2;

    if (r % 2 == 0)
    {
        i2 = r/2;
        if (i2 <= n)
            rez += i2*(i2-1)/2;
    }

    if (to*to == r)
    {
        if (r % to == 0)
        {
            if (to <= n)
                rez += to*(to-1)/2;
        }
    }
    else
    {
        if (r % to == 0)
        {
            i1 = to;
            i2 = r / i1;
            if (i1 <= n)
                rez += i1*(i1-1)/2;
            if (i2 <= n)
                rez += i2*(i2-1)/2;
        }
    }
}

void WriteData()
{
    printf("%i\n",rez);
}

int main()
{
    ReadData();
    Solve();
    WriteData();

    return 0;
}

Поза форумом

 

#8 2006-10-31 13:57:17

FireTiger
Новий користувач
Звідки: Донецк
Зареєстрований: 2006-09-27
Повідомлень: 86

Re: А всеткаи она глючная

Nicky Nick написав:

Если кому-то интересно, то вот решение за O(корень из R). Жалко, что простое решение за O(N) также легко справляется с временным ограничением. Но на то это и первый тур...

Код:

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

int r,n;

int rez;

void ReadData()
{
    scanf("%i %i",&r,&n);
}

void Solve()
{
    r *= 2;
    rez = 0;

    int to = int(sqrt(r));
    int i1,i2;
    for (i1=3; i1<to; i1++)
    {
        if (r % i1 == 0)
        {
            i2 = r / i1;
            if (i1 <= n)
                rez += i1*(i1-1)/2;
            if (i2 <= n)
                rez += i2*(i2-1)/2;
        }
    }

    if (r <= n)
        rez += r*(r-1)/2;

    if (r % 2 == 0)
    {
        i2 = r/2;
        if (i2 <= n)
            rez += i2*(i2-1)/2;
    }

    if (to*to == r)
    {
        if (r % to == 0)
        {
            if (to <= n)
                rez += to*(to-1)/2;
        }
    }
    else
    {
        if (r % to == 0)
        {
            i1 = to;
            i2 = r / i1;
            if (i1 <= n)
                rez += i1*(i1-1)/2;
            if (i2 <= n)
                rez += i2*(i2-1)/2;
        }
    }
}

void WriteData()
{
    printf("%i\n",rez);
}

int main()
{
    ReadData();
    Solve();
    WriteData();

    return 0;
}

ЗАЧЕМ???? yikes Если проходит за О(н)? Да и линейное решение очень простое и естественное...


ICQ 339203772  - Если что-нибудь срочно необходимо - стучитесь, я отвечу! smile
----------------
Основная проблема с программистами заключается в том, что вы никогда не можете сказать, чем они занимаются, до тех пор, пока не будет слишком поздно.

Поза форумом

 

#9 2006-11-01 00:07:26

Nicky Nick
Олімпієць
Звідки: Харьков
Зареєстрований: 2005-11-25
Повідомлень: 48
Вебсайт

Re: А всеткаи она глючная

FireTiger написав:

Nicky Nick написав:

Если кому-то интересно, то вот решение за O(корень из R). Жалко, что простое решение за O(N) также легко справляется с временным ограничением. Но на то это и первый тур...

Код:

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

int r,n;

int rez;

void ReadData()
{
    scanf("%i %i",&r,&n);
}

void Solve()
{
    r *= 2;
    rez = 0;

    int to = int(sqrt(r));
    int i1,i2;
    for (i1=3; i1<to; i1++)
    {
        if (r % i1 == 0)
        {
            i2 = r / i1;
            if (i1 <= n)
                rez += i1*(i1-1)/2;
            if (i2 <= n)
                rez += i2*(i2-1)/2;
        }
    }

    if (r <= n)
        rez += r*(r-1)/2;

    if (r % 2 == 0)
    {
        i2 = r/2;
        if (i2 <= n)
            rez += i2*(i2-1)/2;
    }

    if (to*to == r)
    {
        if (r % to == 0)
        {
            if (to <= n)
                rez += to*(to-1)/2;
        }
    }
    else
    {
        if (r % to == 0)
        {
            i1 = to;
            i2 = r / i1;
            if (i1 <= n)
                rez += i1*(i1-1)/2;
            if (i2 <= n)
                rez += i2*(i2-1)/2;
        }
    }
}

void WriteData()
{
    printf("%i\n",rez);
}

int main()
{
    ReadData();
    Solve();
    WriteData();

    return 0;
}

ЗАЧЕМ???? yikes Если проходит за О(н)? Да и линейное решение очень простое и естественное...

Вот и затем, что решение за O(N) у тебя на олимпиаде более высокого уровня благополучно обломится по времени... Как по мне (ИМХО!), естественным является то решение, которое имеет более широкие рамки применимости... Короче говоря, более оптимизированное...

Поза форумом

 

#10 2006-11-01 09:11:46

IvanZaremba
Новий користувач
Зареєстрований: 2006-10-17
Повідомлень: 12

Re: А всеткаи она глючная

Шановні панове!

Мені ДУЖЕ ЦІКАВО знати думку решти учасників щодо того, чи достатньо чітко з умови випливало, що СПОЧАТКУ міряють _О_пори, а ПОТІМ підключають нову школу, а не навпаки (див. також мій попередній пост, четвертий у даній темі).



Тепер щодо O(n) versus O(sqrt(n)). Насправді зауваження мудре (якщо, звісно, ідея O(sqrt(n))-алгоритму  правильна... я не маю особливих підстав для сумнівів, просто детально ще не дивився). На останніх Всеукрах ("основних", тобто УОІ) на деяких задачах ставлять тайм-ліміти по 50 мілісекунд, тобто 0,05с !!! Щоправда, "чистого" процесорного часу, а на НетОІ, наскільки мені відомо, час міряється не настільки чисто.
Крім того, я заради фіззарядки спробував написати всі розв'язки першого туру на Пітоні, так в окремих тестах таки отримав тайм-оверфлоу. Звісно, у значній мірі це проблема Пітона; я це розумію, і писав на ньому виключно заради тренування... але, водночас, це і проблема алгоритма!!!

Поза форумом

 

#11 2006-11-01 13:05:03

Fizteh
Новий користувач
Зареєстрований: 2006-09-17
Повідомлень: 99

Re: А всеткаи она глючная

IvanZaremba написав:

Шановні панове!

Мені ДУЖЕ ЦІКАВО знати думку решти учасників щодо того, чи достатньо чітко з умови випливало, що СПОЧАТКУ міряють _О_пори, а ПОТІМ підключають нову школу, а не навпаки (див. також мій попередній пост, четвертий у даній темі).



Тепер щодо O(n) versus O(sqrt(n)). Насправді зауваження мудре (якщо, звісно, ідея O(sqrt(n))-алгоритму  правильна... я не маю особливих підстав для сумнівів, просто детально ще не дивився). На останніх Всеукрах ("основних", тобто УОІ) на деяких задачах ставлять тайм-ліміти по 50 мілісекунд, тобто 0,05с !!! Щоправда, "чистого" процесорного часу, а на НетОІ, наскільки мені відомо, час міряється не настільки чисто.
Крім того, я заради фіззарядки спробував написати всі розв'язки першого туру на Пітоні, так в окремих тестах таки отримав тайм-оверфлоу. Звісно, у значній мірі це проблема Пітона; я це розумію, і писав на ньому виключно заради тренування... але, водночас, це і проблема алгоритма!!!

Более 100 человек решили эту задачу на полный балл, потому нечего даже и говорить о неоднозначности условия.

Поза форумом

 

#12 2006-11-01 15:36:41

IvanZaremba
Новий користувач
Зареєстрований: 2006-10-17
Повідомлень: 12

Re: А всеткаи она глючная

Fizteh написав:

... нечего даже и говорить о неоднозначности условия ...

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

Fizteh написав:

Более 100 человек решили эту задачу на полный балл ...

А скільки людей отримали за неї 12 балів? Дещо менше, але теж багато. І серед них окремі потенційні лідери. (Наприклад, мій добрий знайомий, котрий у 2005 мав перший диплом Всеукра з фізики; його результата на Всеукрі з фізики--2006 я не пам'ятаю, але точно пам'ятаю, що він же у 2006 був дрУгим з інформатики всерЕдині своєї паралелі в УФМЛ і не поїхав на УОІ лише тому що у 2006 Всеукри проходили одночасно.)

Із тим, що правильна з точки зору журі трактовка природніша, ніж моя, я в приниці погоджуюся.
Але ж я і не говорю про НЕПРАВИЛЬНІСТЬ формулювання. Я говорю про НЕОДНОЗНАЧНІСТЬ!

Так що, шановний Фізтех, __ВАШУ__ думку я вже зрозумів. А тепер, будь ласка,  дайте можливість сказати іншим.

До речі, навіщо виділяти увесь мій пост (включно з частиною про O(sqrt(n)), щоб дати на нього таку відповідь???

Відредаговано IvanZaremba (2006-11-01 15:40:12)

Поза форумом

 

#13 2006-11-01 19:45:15

Юрко Савеленко
Новий користувач
Зареєстрований: 2006-10-12
Повідомлень: 9

Re: А всеткаи она глючная

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

Поза форумом

 

#14 2006-11-01 21:51:08

Fizteh
Новий користувач
Зареєстрований: 2006-09-17
Повідомлень: 99

Re: А всеткаи она глючная

Ivan Zaremba, на комплимент нарываешься. По поводу задачи - сначала подключают школу, потом меряют сопротивления. Я считал так, получил 20 баллов. А друзей своих оставь, за себя отвечай.

Поза форумом

 

#15 2006-11-02 10:13:28

reiten
журі
Звідки: Киев
Зареєстрований: 2005-10-16
Повідомлень: 196

Re: А всеткаи она глючная

IvanZaremba написав:

Шановні панове!

На останніх Всеукрах ("основних", тобто УОІ) на деяких задачах ставлять тайм-ліміти по 50 мілісекунд, тобто 0,05с !!! Щоправда, "чистого" процесорного часу, а на НетОІ, наскільки мені відомо, час міряється не настільки чисто.

На NetOI2005 тоже были ТЛ в 0.05с.


"...Существуют два подхода к проектированию программ. В одном архитектура делается настолько простой, что в ней явно нет дефектов; в другом - настолько сложной, что в ней нет явных дефектов".
С. А. Хоар

Поза форумом

 

#16 2006-11-02 13:13:11

FireTiger
Новий користувач
Звідки: Донецк
Зареєстрований: 2006-09-27
Повідомлень: 86

Re: А всеткаи она глючная

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

Гм... И действительно не совсем однозначно... Хотя при решении задачи у меня подобных сомнений не возникало smile


ICQ 339203772  - Если что-нибудь срочно необходимо - стучитесь, я отвечу! smile
----------------
Основная проблема с программистами заключается в том, что вы никогда не можете сказать, чем они занимаются, до тех пор, пока не будет слишком поздно.

Поза форумом

 

#17 2006-11-02 13:27:22

Sharp
Олімпієць
Зареєстрований: 2005-10-17
Повідомлень: 34

Re: А всеткаи она глючная

Интересная тут мысль прозвучала: если у меня правильно, значит, в условии все сказано предельно четко. Здесь лотерея или олимпиада?

Поза форумом

 

#18 2006-11-02 14:55:35

Fizteh
Новий користувач
Зареєстрований: 2006-09-17
Повідомлень: 99

Re: А всеткаи она глючная

Sharp написав:

Интересная тут мысль прозвучала: если у меня правильно, значит, в условии все сказано предельно четко. Здесь лотерея или олимпиада?

Больше 100 человек решило правильно!!! Тем более заочная олимпиада - можно было спросить.

Поза форумом

 

#19 2006-11-02 15:20:35

FireTiger
Новий користувач
Звідки: Донецк
Зареєстрований: 2006-09-27
Повідомлень: 86

Re: А всеткаи она глючная

Fizteh написав:

Sharp написав:

Интересная тут мысль прозвучала: если у меня правильно, значит, в условии все сказано предельно четко. Здесь лотерея или олимпиада?

Больше 100 человек решило правильно!!! Тем более заочная олимпиада - можно было спросить.

Гиблое дело этот спор... Те кто решил на полный бал будут настаивать на том что условие корректно, однозначно и т.п, а те которые запороли эту задачу будут настаивать на обратном...
Голодный сытому не товарищ.... smile


ICQ 339203772  - Если что-нибудь срочно необходимо - стучитесь, я отвечу! smile
----------------
Основная проблема с программистами заключается в том, что вы никогда не можете сказать, чем они занимаются, до тех пор, пока не будет слишком поздно.

Поза форумом

 

#20 2006-11-02 16:30:40

IvanZaremba
Новий користувач
Зареєстрований: 2006-10-17
Повідомлень: 12

Re: А всеткаи она глючная

Fizteh написав:

А друзей своих оставь, за себя отвечай.

Fizteh написав:

Больше 100 человек решило правильно!!!

Фізтех, ти сам собі суперечиш! Або факт наявності інших людей, які думають так само, як учасник спору, __Є__ аргументом, або __НЕ_ __Є__.  Не залежно від того, чи до цього апелює одна сторона спору, чи інша!


Fizteh написав:

По поводу задачи - сначала подключают школу, потом меряют сопротивления. Я считал так, получил 20 баллов.

Так формула получається інша:

if (2*R) mod (i+1) = 0 then
  res := res + i*(i+1) div 2

замість

if (2*R) mod i = 0 then
  res := res + i*(i-1) div 2

Як же може получитися той самий результат (крім як за рахунок неправильних меж циклів)?..

Відредаговано IvanZaremba (2006-11-02 16:33:48)

Поза форумом

 

#21 2006-11-02 17:11:49

Fizteh
Новий користувач
Зареєстрований: 2006-09-17
Повідомлень: 99

Re: А всеткаи она глючная

Код:

 for i:=3 to n
     do
          if (2*r) mod i = 0
             then begin
                   q:=(i-1)*i div 2;
                   s:=s+q;
                  end;

i - количество школ, которые подключили на данном этапе. Логично(по условию), что сначала i=3, в конце i=n. Дальше все очевидно. Я плохо понимаю, как ты рассуждал.

Поза форумом

 

#22 2006-11-06 18:24:24

hommiak
Новий користувач
Зареєстрований: 2006-10-25
Повідомлень: 6

Re: А всеткаи она глючная

Так же, как и моё решение,решение следующего вида(Fizteh, у тебя такая программа?)

program supernet;

var
i,r,n,s,q:integer;

begin
read(r,n); 
s:=0;
for i:=3 to n
     do
          if (2*r) mod i = 0
             then begin
                   q:= (i-1)*i div 2;
                   s:=s+q;
                  end;

write(s);
end.

получает следущие баллы 

01 PASSED (+1) 0.01 сек.
02 PASSED (+1) 0.01 сек.
03 PASSED (+1) 0.01 сек.
04 PASSED (+1) 0.01 сек.
05 PASSED (+1) 0.00 сек.
06 PASSED (+1) 0.00 сек.
07 PASSED (+1) 0.00 сек.
08 PASSED (+1) 0.00 сек.
09 PASSED (+1) 0.00 сек.
10 FAILED (Wrong Answer) 0.00 сек.
11 FAILED (Wrong Answer) 0.00 сек.
12 PASSED (+1) 0.00 сек.
13 FAILED (Wrong Answer) 0.00 сек.
14 FAILED (Wrong Answer) 0.00 сек.
15 FAILED (Wrong Answer) 0.00 сек.
16 PASSED (+1) 0.00 сек.
17 PASSED (+1) 0.00 сек.
18 FAILED (Wrong Answer) 0.00 сек.
19 FAILED (Wrong Answer) 0.00 сек.
20 FAILED (Wrong Answer) 0.00 сек.
Прошло тестов: 12 из 20.

Набрано баллов: 12 из 20.

Поза форумом

 

#23 2006-11-06 18:49:30

partisan
Олімпієць
Звідки: Киев
Зареєстрований: 2005-11-04
Повідомлень: 180

Re: А всеткаи она глючная

hommiak написав:

Так же, как и моё решение,решение следующего вида(Fizteh, у тебя такая программа?)

program supernet;

var
i,r,n,s,q:integer;

begin
read(r,n); 
s:=0;
for i:=3 to n
     do
          if (2*r) mod i = 0
             then begin
                   q:= (i-1)*i div 2;
                   s:=s+q;
                  end;

write(s);
end.

получает следущие баллы 

01 PASSED (+1) 0.01 сек.
02 PASSED (+1) 0.01 сек.
03 PASSED (+1) 0.01 сек.
04 PASSED (+1) 0.01 сек.
05 PASSED (+1) 0.00 сек.
06 PASSED (+1) 0.00 сек.
07 PASSED (+1) 0.00 сек.
08 PASSED (+1) 0.00 сек.
09 PASSED (+1) 0.00 сек.
10 FAILED (Wrong Answer) 0.00 сек.
11 FAILED (Wrong Answer) 0.00 сек.
12 PASSED (+1) 0.00 сек.
13 FAILED (Wrong Answer) 0.00 сек.
14 FAILED (Wrong Answer) 0.00 сек.
15 FAILED (Wrong Answer) 0.00 сек.
16 PASSED (+1) 0.00 сек.
17 PASSED (+1) 0.00 сек.
18 FAILED (Wrong Answer) 0.00 сек.
19 FAILED (Wrong Answer) 0.00 сек.
20 FAILED (Wrong Answer) 0.00 сек.
Прошло тестов: 12 из 20.

Набрано баллов: 12 из 20.

Во Фри-Паскале:
  integer=smallint=2 bytes
  longint=4 bytes
В Делфи:
  smallint=2 bytes
  integer=longint=4 bytes

Поза форумом

 

#24 2006-11-06 19:03:35

hommiak
Новий користувач
Зареєстрований: 2006-10-25
Повідомлень: 6

Re: А всеткаи она глючная

partisan написав:

Во Фри-Паскале:
  integer=smallint=2 bytes
  longint=4 bytes
В Делфи:
  smallint=2 bytes
  integer=longint=4 bytes

Уже нашел. Если integer заменить  на longint, программа набирает 20 баллов.
абыдна sad
подумал, раз числа до 10000, хватит integer, а подставить не догадался.И из-за этого потерять 8баллов...

Поза форумом

 

#25 2006-11-06 20:05:57

Ivan
Олімпієць
Зареєстрований: 2005-10-09
Повідомлень: 218

Re: А всеткаи она глючная

Маленькая ошибка - мало потерянных баллов wink


ICQ 233-416-344

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt