Вітаю Вас, Гость
[ Нові повідомлення · Учасники · Правила форуму · Пошук · RSS ]
Сторінка 1 з 11
Форум » Інтернет-олімпіада 2014 » Другий тур » Обговорення задач
Обговорення задач
KulAlexДата: Вівторок, 14.10.2014, 19:03 | Повідомлення # 1
Сержант
Група: Администраторы
Повідомлень: 28
Статус: Offline
Після закінчення туру можна всім бажаючим обговорити задачі і публікувати свої розв'язки.
 
KulAlexДата: Вівторок, 14.10.2014, 19:14 | Повідомлення # 2
Сержант
Група: Администраторы
Повідомлень: 28
Статус: Offline
Оскільки тільки 15 учасників повністю розв’язали задачу А, даю пояснення.
Один з варіантів розв'язку задачі: кожного дня шукаємо першу найменшу квітку і з неї починаємо поливати (буває варіант коли перша найменша квітка знаходиться в межах [n-k+1; n ], то поливаємо останні k ктіток).

 
touristДата: Вівторок, 14.10.2014, 21:11 | Повідомлення # 3
Рядовой
Група: Учасник
Повідомлень: 10
Репутація: 1
Статус: Offline
Для розв’язку першої задачі можна було використати такі структури даних, типу дерева відрізків чи кореневої-декомпозиції. Я опишу розв’язок із використанням дерева відрізків з лінивим пропихуванням. Ідея аналогічна вижче описаній. Тільки пошук мінімального елементу забезбечується деревом. Апдейт на відрізку, який ми підливаємо в певний день, будемо робити за допомогою лінивого пропихування.Отже, нам всього потрібно написати функцію побудови дерева, пошуку мін. елементу і лінивого апдейту.  Ця ідея буде працювати і для більшої кількості днів. Хоча є і рішення, яке буде працювати трошки швидше описаного мною. Це використання бінарного пошуку по відповіді. Але його я залишу на обговорення. Можливо хтось інший знає це рішення і зможе поділитися з іншими учасниками).

Повідомлення відредагував tourist - Вівторок, 14.10.2014, 21:15
 
perunandrejДата: Вівторок, 14.10.2014, 22:25 | Повідомлення # 4
Рядовой
Група: Учасник
Повідомлень: 7
Репутація: 2
Статус: Offline
Цитата KulAlex ()
задачу А, даю пояснення
Цитата tourist ()
типу дерева відрізків чи кореневої-декомпозиції
Раз пішла така гулянка...

Цитата tourist ()
Можливо хтось інший знає це рішення і зможе поділитися з іншими учасниками
Чому б і ні ?
_______________________________________________________________________________________________
Помітимо, що максимальна відповідь 10^9 + 2^8.
Створимо функцію, для перевірки запитуваної відповіді ans. Проходячи по масиву a зліва на право,перевіряємо, за скільки  днів всі квіти виростуть до висоти ans. Звісно , якщо ai>ans ,то така відповідь не правильна.
Звісно це не повний розв'язок задачі, оскільки , за умовою, дівчинка поливає за один день k квіток , які розташовані підряд.
Заведемо масив h , у якому будемо зберігати дану різницю (ans-ai) - мінімальну кількість разів полиття квітки i.
Зрозуміло, що якщо на кроці i , ans-ai>=0 ,то hj=hj-(ans-ai) (для i+1 <= j < min(i+k+1,n)  ).Введемо зміну sc - кількість днів у запасі  ,які є у Софії на кроці i , після пройдених кроків.
Продовження у спойлері...


Повідомлення відредагував perunandrej - Вівторок, 14.10.2014, 23:29
 
fhntv24Дата: Середа, 15.10.2014, 16:44 | Повідомлення # 5
Рядовой
Група: Учасник
Повідомлень: 6
Репутація: 0
Статус: Offline
Цитата perunandrej ()
for(int i=0;i<n;i++) h=0;
Для C++: НЕ ЗАМЕНЯЙТЕ НА MEMSET. Почему же? А потомучто получите 0 балов ... уже понял по своему опыту... Отправлял в понедельник , когда входные тесты не проходили , хотя у себя на компе все окай.
 
Форум » Інтернет-олімпіада 2014 » Другий тур » Обговорення задач
Сторінка 1 з 11
Пошук: