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


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

Ви не зайшли.

#26 2006-12-03 08:57:13

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

Re: Обсуждаем идеи решений

xXx написав:

sad 16 из 20 тестирований

Не поленился lol


Этот аккаунт не работает... мой новый аккаунт - alexkasycky

Поза форумом

 

#27 2006-12-03 12:04:11

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

Re: Обсуждаем идеи решений

xXx написав:

sad 16 из 20 тестирований на 40 б. на остальных Тайм аут на 17ом тесте.

Бедняга.. Но кажется есть правило,что засчитать могут худший результат. Так что... Учись,студент, профессором будешь!smile


Хорошо смеется тот, кто смеется последним...

Поза форумом

 

#28 2006-12-03 12:58:37

ppv
Новий користувач
Зареєстрований: 2006-11-30
Повідомлень: 9

Re: Обсуждаем идеи решений

Просьба к набравшим 40 на майоре и решавшим её динамикой:
Предисловие: у меня 12 состояний (различные очертания края) и около 55 (чуть оптимизировал и стало 40) операций над длинными числами за шаг. TL гарантирован.
По представленным решениям видно, что у решивших этих самых операций значительно меньше.

Собственно просьба: Будьте любезны, опишите словами ваши состояния. По коду, к сожалению, очень трудно их понять.

Відредаговано ppv (2006-12-03 13:00:44)

Поза форумом

 

#29 2006-12-04 08:00:11

Dark_Dimius
Новий користувач
Звідки: /dev/null
Зареєстрований: 2005-11-17
Повідомлень: 136

Re: Обсуждаем идеи решений

ppv написав:

Просьба к набравшим 40 на майоре и решавшим её динамикой:
Предисловие: у меня 12 состояний (различные очертания края) и около 55 (чуть оптимизировал и стало 40) операций над длинными числами за шаг. TL гарантирован.
По представленным решениям видно, что у решивших этих самых операций значительно меньше.

Собственно просьба: Будьте любезны, опишите словами ваши состояния. По коду, к сожалению, очень трудно их понять.

Делаем динамику по краю переход из и-го шага в и+1
\ - чистый край
=  - разрыв
---------------------------------------------------------------------------------------------
в \\\ можна перейти из \\\ 3 методами
из =\\ двумя
из \=\ одним
из \\= двумя
из ==\одним
из\== одним
из =\= одним
из === одним

a[j][1]=a[k][1]*3+a[k][2]*2+a[k][3]+a[k][4]*2+a[k][5]+a[k][7]+a[k][6]+a[k][8];

Відредаговано Dark_Dimius (2006-12-04 08:05:54)


/*Hа C я могy пpосто делать ошибки, на C++ я могy их наследовать!
Некоторые люди на пальцах считают до 10, я же до 1023*/
Если надо помощь - стучитесь в асю, постараюсь помочь 99996414http://www.icq.com/scripts/online.dll?icq=99996414&img=5

Поза форумом

 

#30 2006-12-04 08:03:26

Dark_Dimius
Новий користувач
Звідки: /dev/null
Зареєстрований: 2005-11-17
Повідомлень: 136

Re: Обсуждаем идеи решений

в =\\ можна перейти из

\\\ двумя методами
\=\ одним
\\= одним
\== одним

a[j][2]=a[k][1]*2+a[k][3]+a[k][4]+a[k][7];

Відредаговано Dark_Dimius (2006-12-04 08:07:54)


/*Hа C я могy пpосто делать ошибки, на C++ я могy их наследовать!
Некоторые люди на пальцах считают до 10, я же до 1023*/
Если надо помощь - стучитесь в асю, постараюсь помочь 99996414http://www.icq.com/scripts/online.dll?icq=99996414&img=5

Поза форумом

 

#31 2006-12-04 08:09:52

Dark_Dimius
Новий користувач
Звідки: /dev/null
Зареєстрований: 2005-11-17
Повідомлень: 136

Re: Обсуждаем идеи решений

в \=\ можна перейти из
\\\ одним способом
=\\ одним
\\= одним
=\= одним

a[j][3]=a[k][1]+a[k][2]+a[k][4]+a[k][6];


/*Hа C я могy пpосто делать ошибки, на C++ я могy их наследовать!
Некоторые люди на пальцах считают до 10, я же до 1023*/
Если надо помощь - стучитесь в асю, постараюсь помочь 99996414http://www.icq.com/scripts/online.dll?icq=99996414&img=5

Поза форумом

 

#32 2006-12-04 08:14:00

Dark_Dimius
Новий користувач
Звідки: /dev/null
Зареєстрований: 2005-11-17
Повідомлень: 136

Re: Обсуждаем идеи решений

в \\= перейти из
\\\ двемя методами
=\\ одним методом
\=\ одним
==\ одним

//a[j][4]=a[k][1]*2+a[k][2]+a[k][3]+a[k][5];


/*Hа C я могy пpосто делать ошибки, на C++ я могy их наследовать!
Некоторые люди на пальцах считают до 10, я же до 1023*/
Если надо помощь - стучитесь в асю, постараюсь помочь 99996414http://www.icq.com/scripts/online.dll?icq=99996414&img=5

Поза форумом

 

#33 2006-12-04 08:15:23

Dark_Dimius
Новий користувач
Звідки: /dev/null
Зареєстрований: 2005-11-17
Повідомлень: 136

Re: Обсуждаем идеи решений

в ==\ перейти из
\\\ одним
\\= одним

a[j][5]=a[k][1]+a[k][4];


/*Hа C я могy пpосто делать ошибки, на C++ я могy их наследовать!
Некоторые люди на пальцах считают до 10, я же до 1023*/
Если надо помощь - стучитесь в асю, постараюсь помочь 99996414http://www.icq.com/scripts/online.dll?icq=99996414&img=5

Поза форумом

 

#34 2006-12-04 08:16:28

Dark_Dimius
Новий користувач
Звідки: /dev/null
Зареєстрований: 2005-11-17
Повідомлень: 136

Re: Обсуждаем идеи решений

в =\= перейти из
\\\ одним
\=\ одним

a[j][6]=a[k][1]+a[k][3];


/*Hа C я могy пpосто делать ошибки, на C++ я могy их наследовать!
Некоторые люди на пальцах считают до 10, я же до 1023*/
Если надо помощь - стучитесь в асю, постараюсь помочь 99996414http://www.icq.com/scripts/online.dll?icq=99996414&img=5

Поза форумом

 

#35 2006-12-04 08:17:41

Dark_Dimius
Новий користувач
Звідки: /dev/null
Зареєстрований: 2005-11-17
Повідомлень: 136

Re: Обсуждаем идеи решений

в \== из
\\\  одним
=\\ одним

//a[j][7]=a[k][1]+a[k][2];


/*Hа C я могy пpосто делать ошибки, на C++ я могy их наследовать!
Некоторые люди на пальцах считают до 10, я же до 1023*/
Если надо помощь - стучитесь в асю, постараюсь помочь 99996414http://www.icq.com/scripts/online.dll?icq=99996414&img=5

Поза форумом

 

#36 2006-12-04 08:19:08

Dark_Dimius
Новий користувач
Звідки: /dev/null
Зареєстрований: 2005-11-17
Повідомлень: 136

Re: Обсуждаем идеи решений

а в === только из \\\ smile

a[j][8]=a[k][1];

Если еще не понял - стучи в асю


/*Hа C я могy пpосто делать ошибки, на C++ я могy их наследовать!
Некоторые люди на пальцах считают до 10, я же до 1023*/
Если надо помощь - стучитесь в асю, постараюсь помочь 99996414http://www.icq.com/scripts/online.dll?icq=99996414&img=5

Поза форумом

 

#37 2006-12-04 08:21:31

Dark_Dimius
Новий користувач
Звідки: /dev/null
Зареєстрований: 2005-11-17
Повідомлень: 136

Re: Обсуждаем идеи решений

Люди, я тут всем помогаю, мож и кто мне поможет...
Подскажите хороший мануал по параметрам компилятора и препроцессора с++. плз


/*Hа C я могy пpосто делать ошибки, на C++ я могy их наследовать!
Некоторые люди на пальцах считают до 10, я же до 1023*/
Если надо помощь - стучитесь в асю, постараюсь помочь 99996414http://www.icq.com/scripts/online.dll?icq=99996414&img=5

Поза форумом

 

#38 2006-12-04 18:59:09

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

Re: Обсуждаем идеи решений

Объясните мне Ferry: тест 4 1 1 8 8 ответ: 12 почему? Ведь: (1,1)+(1,8)+(1,8) = 1+1+8+1+8 = 19?


Главное не участие, а победа!

Поза форумом

 

#39 2006-12-04 22:13:05

ppv
Новий користувач
Зареєстрований: 2006-11-30
Повідомлень: 9

Re: Обсуждаем идеи решений

Спасибо, Dark_Dimius!
разобрался, прочуствовал-доказал, реализовал.
Изящно, обход кратных подсчетов. За счет симметричности кол-во состояний снижается до 6.
Интересно, это можно придумать? Или знать надо?

К сожалению, проблема осталась. Хотя на моей машинке время выполнения снизилось в 3 раза.... на online-проверке в TL не влезаю. sad(((

2Junker: 4 1 1 8 8
1 1 >>
1 <<
8 8 >>
1 <<
1 1>>
итого 12.

Поза форумом

 

#40 2006-12-05 13:49:28

Dark_Dimius
Новий користувач
Звідки: /dev/null
Зареєстрований: 2005-11-17
Повідомлень: 136

Re: Обсуждаем идеи решений

ppv написав:

Спасибо, Dark_Dimius!
разобрался, прочуствовал-доказал, реализовал.
Изящно, обход кратных подсчетов. За счет симметричности кол-во состояний снижается до 6.
Интересно, это можно придумать? Или знать надо?

К сожалению, проблема осталась. Хотя на моей машинке время выполнения снизилось в 3 раза.... на online-проверке в TL не влезаю. sad(((

2Junker: 4 1 1 8 8
1 1 >>
1 <<
8 8 >>
1 <<
1 1>>
итого 12.

если ты пишеш чисто сумирование - может накрытся ды добавляй уже умноженое на коефициент.
Ты пишеш на си или пасе?


/*Hа C я могy пpосто делать ошибки, на C++ я могy их наследовать!
Некоторые люди на пальцах считают до 10, я же до 1023*/
Если надо помощь - стучитесь в асю, постараюсь помочь 99996414http://www.icq.com/scripts/online.dll?icq=99996414&amp;img=5

Поза форумом

 

#41 2006-12-05 19:02:11

ppv
Новий користувач
Зареєстрований: 2006-11-30
Повідомлень: 9

Re: Обсуждаем идеи решений

Dark_Dimius написав:

если ты пишеш чисто сумирование - может накрытся ды добавляй уже умноженое на коефициент.
Ты пишеш на си или пасе?

пишу на си
коеффициент я реализовал сразу, а вот нормальную длинную ярифметику не стал smile (делал 1эл массива -- одна цифра)
сделал нормальную длинную арифметику (на 8 цифр сразу) и все прошло. 0.08с макс.

сделал зарубку: надо оптимизировать задачи по максимуму. smile

Відредаговано ppv (2006-12-05 19:02:29)

Поза форумом

 

#42 2006-12-06 22:29:33

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

Re: Обсуждаем идеи решений

Добрые люди! Подскажите мне, плиз, АЛГОРИТМ решения Mayor. Очень меня зацепило, что не решил. Програмки мне без надобности, алгоритм по ним не понять. На bulpi@narod.ru

Поза форумом

 

#43 2006-12-07 09:41:12

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

Re: Обсуждаем идеи решений

Dark_Dimius написав:

Люди, я тут всем помогаю, мож и кто мне поможет...
Подскажите хороший мануал по параметрам компилятора и препроцессора с++. плз

Поскольку на язык мануала ограничений не наложено, предложу http://gcc.gnu.org/onlinedocs/ :-)

Поза форумом

 

#44 2006-12-07 11:08:23

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

Re: Обсуждаем идеи решений

bulpi написав:

Добрые люди! Подскажите мне, плиз, АЛГОРИТМ решения Mayor. Очень меня зацепило, что не решил. Програмки мне без надобности, алгоритм по ним не понять. На bulpi@narod.ru

Думаю, лень будет людям цитировать учебники по программированию. Введи в поисковик "динамическое программирование плитки" и выбирай. Вот здесь вроде неплохо описано:

http://ips.ifmo.ru/courses/course1/chG/l7/index.html

хотя для состояния 7 сдается мне ошибочка у них вышла...

Поза форумом

 

#45 2006-12-07 14:54:14

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

Re: Обсуждаем идеи решений

2 mikolaj
Большое спасибо тебе, добрый человек!

Поза форумом

 

#46 2006-12-07 18:21:13

Dark_Dimius
Новий користувач
Звідки: /dev/null
Зареєстрований: 2005-11-17
Повідомлень: 136

Re: Обсуждаем идеи решений

mikolaj написав:

Dark_Dimius написав:

Люди, я тут всем помогаю, мож и кто мне поможет...
Подскажите хороший мануал по параметрам компилятора и препроцессора с++. плз

Поскольку на язык мануала ограничений не наложено, предложу http://gcc.gnu.org/onlinedocs/ :-)

данке.


/*Hа C я могy пpосто делать ошибки, на C++ я могy их наследовать!
Некоторые люди на пальцах считают до 10, я же до 1023*/
Если надо помощь - стучитесь в асю, постараюсь помочь 99996414http://www.icq.com/scripts/online.dll?icq=99996414&amp;img=5

Поза форумом

 

#47 2006-12-11 15:26:47

Савченко О. О.
Новий користувач
Звідки: Суми, Укрина
Зареєстрований: 2006-10-18
Повідомлень: 11

Re: Обсуждаем идеи решений

А когда приблизительно начнется третий тур?


if you haven't anything to do, don't do it here! smile

Поза форумом

 

#48 2006-12-14 05:05:51

Dark_Dimius
Новий користувач
Звідки: /dev/null
Зареєстрований: 2005-11-17
Повідомлень: 136

Re: Обсуждаем идеи решений

Савченко О. О. написав:

А когда приблизительно начнется третий тур?

в прошлом году прошло 10 дней - 3 тур начасля в новый год.
Скорее всего через неделю-две


/*Hа C я могy пpосто делать ошибки, на C++ я могy их наследовать!
Некоторые люди на пальцах считают до 10, я же до 1023*/
Если надо помощь - стучитесь в асю, постараюсь помочь 99996414http://www.icq.com/scripts/online.dll?icq=99996414&amp;img=5

Поза форумом

 

#49 2007-01-04 07:38:07

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

Re: Обсуждаем идеи решений

Ivan написав:

А если первый равен второму?

Большое спасибо, исправил, 40 из 40.

Поза форумом

 

#50 2007-11-14 21:28:06

MItornaDOS
Новий користувач
Звідки: Вінницька область
Зареєстрований: 2007-11-08
Повідомлень: 74

Re: Обсуждаем идеи решений

mikolaj написав:

bulpi написав:

Добрые люди! Подскажите мне, плиз, АЛГОРИТМ решения Mayor. Очень меня зацепило, что не решил. Програмки мне без надобности, алгоритм по ним не понять. На bulpi@narod.ru

Думаю, лень будет людям цитировать учебники по программированию. Введи в поисковик "динамическое программирование плитки" и выбирай. Вот здесь вроде неплохо описано:

http://ips.ifmo.ru/courses/course1/chG/l7/index.html

хотя для состояния 7 сдается мне ошибочка у них вышла...

эх, начал я читать и тут чё-то непонятное:

Вот цитата из учебника от 1 до 2 примера:

Пример #1.    

Пусть имеется деревянная планка, параллельная оси Ох, в которую вбито N (N≤100) гвоздей. Известны координаты этих гвоздей X[i], i=1,...N, причем X[i]<X[i+1]. К гвоздям требуется привязать веревочки таким образом, чтобы

    *      каждая веревочка связывала ровно два гвоздя;
    *      к каждому гвоздю была привязана одна веревочка;
    *      суммарная длина веревочек была минимальна.

Для каждого номера i гвоздя определим две функции. Функция F0(i) будет означать минимально возможную длину веревочек, требуемых для соединения первых i гвоздей, причем только к последнему гвоздю с номером i веревочка еще не привязана. Функция F1(i) будет означать минимально возможную длину веревочек, требуемых для соединения первых i гвоздей, причем к гвоздю с номером i веревочка уже привязана. Тогда можно записать следующие рекуррентные соотношения.
F0(i+1)=F1(i);   
F1(i+1)=min{F1(i)+X[i+1]-X[i];, F0(i)+X[i+1]-X[i]}.   

Первое соотношение показывает, что для получения требуемой конструкции достаточно просто добавить к конструкции F1(i) свободный гвоздь с номеров i+1. Для получения же конструкции F1(i+1) нужно воспользоваться лучшим из результатов F0(i), F1(i), соединив гвоздь с номером i+1 с i-м. При этом к каждому гвоздю, даже если мы воспользовались конструкцией F0(i), будет привязана хотя бы одна веревочка.

А если N=1,3,5,7...97,99? Там нужно чтобы каждая веревочка связывала ровно два гвоздя и к каждому гвоздю была привязана одна веревочка!

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt