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

necro · 2005-11-19 12:01:36

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

jack_spektor · 2005-11-19 12:14:51

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

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

necro · 2005-11-19 12:25:40

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

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

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

ROBOT · 2005-11-19 12:31:10

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

necro · 2005-11-19 12:34:39

ROBOT написав:
CIRCUIT совсем легко!!!

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

jack_spektor · 2005-11-19 12:37:32

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

jack_spektor · 2005-11-19 12:41:09

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

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

jack_spektor · 2005-11-19 12:43:37

ROBOT написав:
CIRCUIT совсем легко!!!

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

xXx · 2005-11-19 12:53:37

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

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

Vova · 2005-11-19 12:55:33

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

Angry Coder · 2005-11-19 12:59:47

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

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

xXx · 2005-11-19 13:00:33

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)

Angry Coder · 2005-11-19 13:03:06

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

Pavel · 2005-11-19 13:08:02

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

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

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

xXx · 2005-11-19 13:13:22

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

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

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

Angry Coder · 2005-11-19 13:13:51

xXx написав:
Правильный взгляд...

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

Angry Coder · 2005-11-19 13:16:47

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

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

Angry Coder · 2005-11-19 13:19:15

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

- ага

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

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

Pavel · 2005-11-19 13:27:25

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

xXx · 2005-11-19 13:41:37

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

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

Angry Coder · 2005-11-19 13:43:58

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

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

xXx · 2005-11-19 13:45:11

Angry Coder написав:
xXx написав:
Правильный взгляд...
неправильный:(
тест: 1 150 4 140 80 => 1 должно быть.

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

Код:

    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)

Angry Coder · 2005-11-19 13:51:33

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

xXx · 2005-11-19 14:02:49

Angry Coder написав:
тогда: 1 160 4 140 80 => 0 должно быть

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

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

Pavel · 2005-11-19 14:03:23

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

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

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

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

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

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

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

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

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

jack_spektor написав:

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

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

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

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

ROBOT написав:

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

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

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

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

necro написав:

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

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

ROBOT написав:

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

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

jack_spektor написав:

ROBOT написав:

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

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

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

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

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

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

jack_spektor написав:

necro написав:

Код:

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

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

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

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

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

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

Angry Coder написав:

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

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

xXx написав:

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

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

Pavel написав:

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

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

xXx написав:

xXx написав:

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

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

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

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

Angry Coder написав:

xXx написав:

xXx написав:

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

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

Pavel написав:

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

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

Angry Coder написав:

xXx написав:

Код:

Код:

Код:

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

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

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

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

Angry Coder написав:

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

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

Angry Coder написав:

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