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

alex_kasycky · 2006-12-03 08:57:13

xXx написав:
16 из 20 тестирований

Не поленился

Anna · 2006-12-03 12:04:11

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

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

ppv · 2006-12-03 12:58:37

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

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

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

Dark_Dimius · 2006-12-04 08:00:11

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)

Dark_Dimius · 2006-12-04 08:03:26

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

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

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

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

Dark_Dimius · 2006-12-04 08:09:52

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

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

Dark_Dimius · 2006-12-04 08:14:00

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

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

Dark_Dimius · 2006-12-04 08:15:23

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

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

Dark_Dimius · 2006-12-04 08:16:28

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

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

Dark_Dimius · 2006-12-04 08:17:41

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

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

Dark_Dimius · 2006-12-04 08:19:08

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

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

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

Dark_Dimius · 2006-12-04 08:21:31

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

Junker · 2006-12-04 18:59:09

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

ppv · 2006-12-04 22:13:05

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

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

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

Dark_Dimius · 2006-12-05 13:49:28

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

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

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

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

ppv · 2006-12-05 19:02:11

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

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

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

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

bulpi · 2006-12-06 22:29:33

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

mikolaj · 2006-12-07 09:41:12

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

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

mikolaj · 2006-12-07 11:08:23

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

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

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

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

bulpi · 2006-12-07 14:54:14

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

Dark_Dimius · 2006-12-07 18:21:13

mikolaj написав:
Dark_Dimius написав:
Люди, я тут всем помогаю, мож и кто мне поможет...
Подскажите хороший мануал по параметрам компилятора и препроцессора с++. плз
Поскольку на язык мануала ограничений не наложено, предложу http://gcc.gnu.org/onlinedocs/ :-)

данке.

Савченко О. О. · 2006-12-11 15:26:47

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

Dark_Dimius · 2006-12-14 05:05:51

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

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

Max94 · 2007-01-04 07:38:07

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

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

MItornaDOS · 2007-11-14 21:28:06

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? Там нужно чтобы каждая веревочка связывала ровно два гвоздя и к каждому гвоздю была привязана одна веревочка!

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

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

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

xXx написав:

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

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

xXx написав:

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

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

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

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

ppv написав:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ppv написав:

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

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

Dark_Dimius написав:

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

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

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

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

Dark_Dimius написав:

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

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

bulpi написав:

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

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

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

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

mikolaj написав:

Dark_Dimius написав:

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

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

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

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

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

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

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

Ivan написав:

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

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

mikolaj написав:

bulpi написав:

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