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


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

Ви не зайшли.

#1 2005-11-19 12:01:36

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

Обсудим решения

Давайте например бламблам кто как делал : я лично бинарным от диагонали но сто процентов все не пройдет. Какие задачи считаете халявными кроме Беар - я лично Циркуит считаю легким с точки зрения программирования


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

Поза форумом

 

#2 2005-11-19 12:14:51

jack_spektor
Олімпієць
Звідки: Украина Одесса
Зареєстрований: 2005-11-12
Повідомлень: 116
Вебсайт

Re: Обсудим решения

Я лично Блям сдалал с помощью уравнения:
Нарисовал,подумал и высчитал корни.Но помойму решение у меня глючное.
Наверное неправильное.

Если интересно посмотри решение на:
http://www.TheJack.narod.ru/olymp.rar


Delphi IT!!!
Мой сайт:http:\\mr-kody.blogspot.com

Поза форумом

 

#3 2005-11-19 12:25:40

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

Re: Обсудим решения

jack_spektor написав:

Я лично Блям сдалал с помощью уравнения:
Нарисовал,подумал и высчитал корни.Но помойму решение у меня глючное.
Наверное неправильное.

Если интересно посмотри решение на:
http://www.TheJack.narod.ru/olymp.rar

Имееш ввиду по диагонали тогда я тож так пробовал но глюк нашел в решении и переделал на бинарный поиск


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

Поза форумом

 

#4 2005-11-19 12:31:10

ROBOT
Олімпієць
Звідки: Ялта
Зареєстрований: 2005-10-26
Повідомлень: 158

Re: Обсудим решения

CIRCUIT совсем легко!!!


I have Delphi 7, BP 7.0, FP 1.0.4, Windows XP
Мои решения олимпиад на  Паскале: http://h0h0l.narod.ru/
Моя проверялка: http://www.proveryalka.narod.ru/
ICQ: 266367671

Поза форумом

 

#5 2005-11-19 12:34:39

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

Re: Обсудим решения

ROBOT написав:

CIRCUIT совсем легко!!!

Согласен. Ладно задам самый интересующий щас вопрос : кто как нюпатиенс делал?


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

Поза форумом

 

#6 2005-11-19 12:37:32

jack_spektor
Олімпієць
Звідки: Украина Одесса
Зареєстрований: 2005-11-12
Повідомлень: 116
Вебсайт

Re: Обсудим решения

Я делал,по мойму правильно...


Delphi IT!!!
Мой сайт:http:\\mr-kody.blogspot.com

Поза форумом

 

#7 2005-11-19 12:41:09

jack_spektor
Олімпієць
Звідки: Украина Одесса
Зареєстрований: 2005-11-12
Повідомлень: 116
Вебсайт

Re: Обсудим решения

necro написав:

Имееш ввиду по диагонали тогда я тож так пробовал но глюк нашел в решении и переделал на бинарный поиск

Я думал,насчёт поиска...
На мой взгляд данная задача чисто геометрическая...
Но тест нас рассудит...


Delphi IT!!!
Мой сайт:http:\\mr-kody.blogspot.com

Поза форумом

 

#8 2005-11-19 12:43:37

jack_spektor
Олімпієць
Звідки: Украина Одесса
Зареєстрований: 2005-11-12
Повідомлень: 116
Вебсайт

Re: Обсудим решения

ROBOT написав:

CIRCUIT совсем легко!!!

Не сказал бы...
У тебя когда-нибудь получалось больше двух разрезов?
Мне чего-то кажеться, что там больше двух не может быть...


Delphi IT!!!
Мой сайт:http:\\mr-kody.blogspot.com

Поза форумом

 

#9 2005-11-19 12:53:37

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: Обсудим решения

jack_spektor написав:

ROBOT написав:

CIRCUIT совсем легко!!!

Не сказал бы...
У тебя когда-нибудь получалось больше двух разрезов?
Мне чего-то кажеться, что там больше двух не может быть...

Совсем не легко!!!
На эту задачу я больше всего времени потратил...(пока не доказал, что больше 2-ух разрезов быть не может)
А если так легко, то может кто-нибудь объяснит как доказать(кроме полного перебора), что 2 разреза - этом максимум...


icq - 402174

Поза форумом

 

#10 2005-11-19 12:55:33

Vova
Олімпієць
Звідки: г. Мариуполь
Зареєстрований: 2005-11-19
Повідомлень: 27

Re: Обсудим решения

А больше 2 и не надо

Поза форумом

 

#11 2005-11-19 12:59:47

Angry Coder
Олімпієць
Зареєстрований: 2005-11-03
Повідомлень: 42

Re: Обсудим решения

доказательство:
для наглядности заменим 0 на -1 тогда
заиндексируем элементы с 0.
сумма по i от 0 до n-1(  сумма по j от и i до i+n\2-1 (А[i] mod n) ) = 0 (очевидно каждая 1 и -1 войдет в сумму n раз)

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

Поза форумом

 

#12 2005-11-19 13:00:33

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: Обсудим решения

jack_spektor написав:

necro написав:

Имееш ввиду по диагонали тогда я тож так пробовал но глюк нашел в решении и переделал на бинарный поиск

Я думал,насчёт поиска...
На мой взгляд данная задача чисто геометрическая...
Но тест нас рассудит...

Правильный взгляд...

Код:

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

#define swap(a,b)    a=(a^=b)^(b^=a)
#define sort(a,b)    if(a>b)swap(a,b)

short Test()
{
    int X,Y,A,B;
    scanf("%d%d%d%d",&X,&Y,&A,&B);
    sort(X,Y);
    sort(A,B);
    if(X<=A && Y<=B)return 1;
    else if(X>A && Y>B)return 0;
    else if(Y>B){
        swap(X,Y);
        swap(A,B);
    }
    X*=X;Y*=Y;
    A*=A,B*=B;
    A-=X+Y-B;
    B+=A+B;
    if(A<0 || B<0 || A+B<Y)return 0;
    return 1;
}

int main()
{
    int N;
    for(scanf("%d",&N);N;N--)
        printf("%d",Test());
    return 0;
}

Відредаговано xXx (2005-11-19 13:47:15)


icq - 402174

Поза форумом

 

#13 2005-11-19 13:03:06

Angry Coder
Олімпієць
Зареєстрований: 2005-11-03
Повідомлень: 42

Re: Обсудим решения

бламблам чисто геометрическая и решается на интах:)
но бинарный поиск должен взять все тесты

Поза форумом

 

#14 2005-11-19 13:08:02

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

Re: Обсудим решения

Нафлудили уже. Не буду разбираться.

Мое мнение:
Bear - без комментариев.
Piece - чистая вычислительная геометрия. Сложность в том, чтобы сделать как можно меньше операций с вещественными числами. В 3-4 можно уложиться.
Blamblam - Опять же вычислительная геометрия. Случай с диагональным размещением просто прописывается (тут кто-то писал про круг описываемый картой - так и надо!). Корни все что здесь нужно.
Newpatience - Ужас, а не задача. Пасьянс всегда сходится (доказывается). Есть короткое и относительно простое решение за n^2. Но можно сложно и геморойно пробить за n*log(n). У меня получилось уложиться в 5кб (с++). Но послал все-таки короткое решение. Ибо геморойное не вписывается в формат первого тура.
Circuit - задача-шутка. За счет дискретной непрерывности ответ либо 1 (пополам) либо 2. Отсюда же и следует решение.

Нынче первый гораздо сложнее прошлого.

Поза форумом

 

#15 2005-11-19 13:13:22

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: Обсудим решения

Angry Coder написав:

доказательство:
для наглядности заменим 0 на -1 тогда
заиндексируем элементы с 0.
сумма по i от 0 до n-1(  сумма по j от и i до i+n\2-1 (А[i] mod n) ) = 0 (очевидно каждая 1 и -1 войдет в сумму n раз)

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

Генерил в реалтайме? (грузонуто получилось)
Это доказательство - доказательство не простоты задачи!!!


icq - 402174

Поза форумом

 

#16 2005-11-19 13:13:51

Angry Coder
Олімпієць
Зареєстрований: 2005-11-03
Повідомлень: 42

Re: Обсудим решения

xXx написав:

Правильный взгляд...

неправильный:(
тест: 1 150 4 140 80 => 1 должно быть.

Поза форумом

 

#17 2005-11-19 13:16:47

Angry Coder
Олімпієць
Зареєстрований: 2005-11-03
Повідомлень: 42

Re: Обсудим решения

Pavel написав:

Newpatience - Ужас, а не задача. Пасьянс всегда сходится (доказывается). Есть короткое и относительно простое решение за n^2. Но можно сложно и геморойно пробить за n*log(n). У меня получилось уложиться в 5кб (с++). Но послал все-таки короткое решение. Ибо геморойное не вписывается в формат первого тура.

Newpatience o(n) и к тому же простое для написания;)

Поза форумом

 

#18 2005-11-19 13:19:15

Angry Coder
Олімпієць
Зареєстрований: 2005-11-03
Повідомлень: 42

Re: Обсудим решения

xXx написав:

Генерил в реалтайме? (грузонуто получилось)

- ага

xXx написав:

Это доказательство - доказательство не простоты задачи!!!

да оно ж простое! словами - рассмотрим суммы цифр на всех отрезках длины n/2 и докажем, что там есть отрезок с нулевой суммой (если числа -1 и 1).

Поза форумом

 

#19 2005-11-19 13:27:25

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

Re: Обсудим решения

2Angry.
за линейное? Ты не прав: попробуй 3 1 1 2 3 2 3 (если я правильно предположил твое решение)
насчет цепи согласен (рамка длиной n/2).

Поза форумом

 

#20 2005-11-19 13:41:37

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: Обсудим решения

Angry Coder написав:

xXx написав:

Генерил в реалтайме? (грузонуто получилось)

- ага

xXx написав:

Это доказательство - доказательство не простоты задачи!!!

да оно ж простое! словами - рассмотрим суммы цифр на всех отрезках длины n/2 и докажем, что там есть отрезок с нулевой суммой (если числа -1 и 1).

Не я то понял, но оно не очевидно...


icq - 402174

Поза форумом

 

#21 2005-11-19 13:43:58

Angry Coder
Олімпієць
Зареєстрований: 2005-11-03
Повідомлень: 42

Re: Обсудим решения

Pavel написав:

2Angry.
за линейное? Ты не прав: попробуй 3 1 1 2 3 2 3 (если я правильно предположил твое решение)
насчет цепи согласен (рамка длиной n/2).

рамка n/2 это к Circuit доказательство.
В пасьянсе решение такое: рассмотрим одну карточку. она в оптимальном решении может лежать либо так, как лежит, либо должна перевернутся. попробуем оставить так. ее фиксированое положение однозначно задает положение карточки, с такой же цифрой, как на ней. та в свою очередь задает положение еще одной. и так далее пока цикл не замкнется. теперь попробуем другой вариант. то же самое. далее перейдем к следующей карточке не из этого цикла, если такая еще есть. итого если мы умеем искать положение карточки с заданым числом за О(1) (а это легко) то алгоритм сработает за О(n).

Поза форумом

 

#22 2005-11-19 13:45:11

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: Обсудим решения

Angry Coder написав:

xXx написав:

Правильный взгляд...

неправильный:(
тест: 1 150 4 140 80 => 1 должно быть.

Нет, правильный!!!
Просто я из-за мысли о простоте задачи допустил грубую ошибку и не протестил!!! sad

Код:

    A-=X+Y-B; //вот здесь я изменил A и не учёл в следующей строке
    B-=X+Y-A; //а вот и та ошибка!!!

А вот это работает:

Код:

         int T=A;
    A-=X+Y-B;
    B-=X+Y-T;

или так:

Код:

     A-=X+Y-B;
    B+=A+B;

Відредаговано xXx (2005-11-19 13:50:10)


icq - 402174

Поза форумом

 

#23 2005-11-19 13:51:33

Angry Coder
Олімпієць
Зареєстрований: 2005-11-03
Повідомлень: 42

Re: Обсудим решения

тогда: 1 160 4 140 80 => 0 должно быть

Поза форумом

 

#24 2005-11-19 14:02:49

xXx
Олімпієць
Звідки: Kirovsk-city
Зареєстрований: 2005-11-16
Повідомлень: 123
Вебсайт

Re: Обсудим решения

Angry Coder написав:

тогда: 1 160 4 140 80 => 0 должно быть

должно быть 1!

Відредаговано xXx (2005-11-19 14:03:54)


icq - 402174

Поза форумом

 

#25 2005-11-19 14:03:23

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

Re: Обсудим решения

Angry Coder написав:

итого если мы умеем искать положение карточки с заданым числом за О(1) (а это легко)

Вот к этому и вопрос КАК?

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt