Головна Обговорення Лінки Пошук Prykladna СС Прикладна _КОЛЕДЖ 18.01.2020 05:29:38 (EEST=GMT+2)
ACM -
Навігація -
Теми форуму +
Чи знали ви, що... ? (beta) -
Найбільша середня тривалість життя в світі в Андоррі-83 роки, найменша в Ботсвані-35 років. Для порівняння: в Україні цей показник-68 років.
Події
ПнВтСрЧтПтСбНд
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31

Birthday(s):
AVATARMisha
AVATARZdebyman
AVATARPrototype
AVATARsuhanov
AVATARArtem Halushko
AVATARAntonrom00

Перегляд теми
ACM Контестер | Online Judge System | acm.tju.edu.cn
Автор DP Problems Marathon
Torax
Адміністратор

Аватар користувача

Повідомлень: 75
Звідки: ЛНУ
Зареєстрований: 03.03.06
Опубліковано 22-07-2007 13:19
Слухайте, як робити там задачу A?
І ще питання до тих, хто здав задачу B - як ви її робили?? Теж через long double чи якось правильніше??
Torax 275476769 Torax[Lviv NU] Надіслати приватне повідомлення
Автор RE: DP Problems Marathon
Mace Windu
Користувач

Повідомлень: 141
Звідки: НУ "ЛП"
Зареєстрований: 13.04.06
Опубліковано 22-07-2007 15:04
Як вам ідея зробити дві групи вершин для правої частини графу - одну для перемог, другу для нічиїх? Витоків також два. Спочатку знаходимо максимальний потік в перемоги, а потім все що лишилося пробуємо запхнути в нічиї. Виходить граф на 3n+3 вершини.
Mace_Windu 248-855-941 Mace(Lviv Polytechniс NU) Надіслати приватне повідомлення
Автор RE: DP Problems Marathon
webmaster
Головний Адміністратор

Аватар користувача

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 22-07-2007 23:09
то Mace Windu: якщо ти то писав про задачу А, то там потік не вийде, бо вершин 1000 і більше.

"Слухайте, як робити там задачу A?"

Вася казав так:
Vasya (22:58:18 22/07/2007)
ну тут якщо ти їх посортуєш
Vasya (22:59:17 22/07/2007)
і для кожного (починаючи з найбільшого) будеш підбирати мах з тих, що менші за нього, або мах взагалі якщо 1 зробити не можна
Vasya (22:59:30 22/07/2007)
то отримаєш простеньку жадну динаміку



І ще питання до тих, хто здав задачу B - як ви її робили?? Теж через long double чи якось правильніше??

Я також лонг даубл. Ну там просто дуже швидко виходить відповідь 0.00000
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: DP Problems Marathon
Torax
Адміністратор

Аватар користувача

Повідомлень: 75
Звідки: ЛНУ
Зареєстрований: 03.03.06
Опубліковано 23-07-2007 00:01
я щось схоже робив, не проканує... та й не динаміка тоді вже це..
а на рахунок потоку - там вся соль тої задачі якраз в тому, що вершин задофіга для чесного потоку.
На рахунок задачі B: можна було зразу рахувати відсотки, так робив Ігор Євчинець
Torax 275476769 Torax[Lviv NU] Надіслати приватне повідомлення
Автор RE: DP Problems Marathon
Mace Windu
Користувач

Повідомлень: 141
Звідки: НУ "ЛП"
Зареєстрований: 13.04.06
Опубліковано 25-07-2007 13:46
Ну це паросполучення, а не чистий потік. Його можна легко оптимізувати.
Mace_Windu 248-855-941 Mace(Lviv Polytechniс NU) Надіслати приватне повідомлення
Перейти на форум:
Банери
Голосування
Що Ви б хотіли отримати в якості подарунку на змаганні з програмування?

Медалі

настільні ігри

торт

клавіатура, навушники, флешки і т.д.

квитки в кіно

квитки в аквапарк

квитки на пейнтбол

книги

футболки з логотипом змагання

Для участі в голосуваннях Ви повинні залогуватись.
Міні-чат +
Зараз на сайті -
Гостей: 3
На сайті немає зареєстрованних користувачів

Користувачів: 4,408
новачок: Lord_Voldemort
Powered by PHP-Fusion © 2003-2006
LNU ACMania © 2004-2011 e-mail: webmaster@acm.lviv.ua
21,943,196 унікальних відвідувачів
Our projects: ACM Contester, _College.
  пїЅпїЅпїЅпїЅпїЅпїЅпїЅ Orphus     bigmir)net TOP 100