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


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

Ви не зайшли.

#51 2010-12-30 20:25:54

Иванов
Новий користувач
Зареєстрований: 2010-12-09
Повідомлень: 21

Re: Лучшие решения задач второго тура

пишу кодом, чтобы пробелы сохранились

Код:

вот заполненный массив

 8   24   12    6    7    1 
32   36   18   13    8 
36   36   18   13 
42   36   18 
42   36 
42 

буду обозначать G(a b c) - время на исследование отрезка a b c

если пробурить 8 и нефть там есть (худший случай), придется потратить дополнительно G(24   12    6    7    1)=34. 8+36=44.
если пробурить первой 24, тогда либо 8, либо G(12    6    7    1 )=18. худший случай 24+18=42.
вывод: начинать бурение МОЖНО с точки 24, потому что в этом случае НАВЕРНЯКА уложимся в оптимальное время 42.

итак G(8   24   12    6    7    1 ) = 24 + G(12    6    7    1 )

рассмотрим теперь 12    6    7    1 
если начать в 12: 12+G(6    7    1 )=12+13=25>18 - не то
если начать в 6: 6+max(12,G(7    1))=6+12=18 - значит следующей бурить МОЖНО точку 6

осталась только точка 12.

значит G(8   24   12    6    7    1 ) = 24 + 6 + 12 = 42

вот вам план бурения, который определит где заканчивается нефть за время не большее 42 как нефть ни изворачивайся (худший случай)

Відредаговано Иванов (2010-12-30 20:31:40)

Поза форумом

 

#52 2010-12-30 22:31:35

LVV
Олімпієць
Звідки: Цюрупинськ
Зареєстрований: 2010-11-19
Повідомлень: 294
Вебсайт

Re: Лучшие решения задач второго тура

Разобрался. smile Большое спасибо всем за терпение и помощь. С наступающим Новым 2011 годом. Удачи и всяческих успехов.

Поза форумом

 

#53 2011-01-06 08:42:11

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Re: Лучшие решения задач второго тура

Н-да, як виявилося, реалізація в першому пості даної теми не настільки схожа на мою і не настільки зрозуміла, як мені здалося на перший погляд... Прошу пробачення, що так настійливо відсилав саме до неї -- вона правильна, але навряд чи може вважатися зразком простоти та зрозумілості. Просто пробував відповісти щось по суті, будучи сильно завалений текучкою в універі.

Поза форумом

 

#54 2011-01-19 15:53:31

jurij
Новий користувач
Зареєстрований: 2009-01-23
Повідомлень: 32

Re: Лучшие решения задач второго тура

MItornaDOS написав:

А-а-а, це як елемент підрахунку кількості можливих сум для невеликих M smile
От що мене більше цікавить – це те, від чого і як залежить кількість витягань Mmin після яких для даних номіналів з'являється властивість описана вище:

Якщо A[i] - це кількість можливих сум після i витягань, то для всіх i > 50
A[i+1] - A[i] = const

Для случая, когда присутствуют монеты 1 коп и 100 коп данная закономерность возникает только после 100 вытягиваний.

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt