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

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

MAA написав:

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

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

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

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

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

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;
}

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

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

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



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

Fizteh написав:

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

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

Fizteh написав:

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

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

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

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

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

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

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

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

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

Sharp написав:

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

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

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)

Так же, как и моё решение,решение следующего вида(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.

partisan написав:

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

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