Автор |
LNU FAMI TJU Contest 22 |
Ostap
Користувач
Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06 |
Опубліковано 27-06-2007 18:19 |
|
|
Якщо в когось є питання по задачах або по контесту в загальному - пишіть сюди.
Не помиляється той, хто нічого не робить! |
|
Автор |
RE: LNU FAMI TJU Contest 22 |
ibm
Користувач

Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07 |
Опубліковано 27-06-2007 23:26 |
|
|
Як ти робив (сам алгоритм) задачку з CD? В мене чомусь дало неправильну в-дь, хоча я, я здається все врахував... Задача нагадує якусь, звідси, яку я вже давно здав і Забобонного Гриця з обласної... 
Pascal not dead! |
|
Автор |
RE: LNU FAMI TJU Contest 22 |
vlad89
Користувач
Повідомлень: 8
Звідки: Kiev National University
Зареєстрований: 13.03.06 |
Опубліковано 27-06-2007 23:33 |
|
|
ibm написав:
Як ти робив (сам алгоритм) задачку з CD? В мене чомусь дало неправильну в-дь, хоча я, я здається все врахував... Задача нагадує якусь, звідси, яку я вже давно здав і Забобонного Гриця з обласної...  
Розбиваєш на макс. за кількістю кучі (K == 13, тоді по 12). В тебе може залишитися одна купа. Якщо в ній не 13, то це відповідь. Якщо ж 13, то ти можеш перекласти один диск з якоїсь лівої групи, де максимум до неї, так щоб вийшло 14, але лише в тому випадку, якщо 1) така взагалі є 2) інші купи не по 14 дисків.
Brain is the organ that thinks that it thinks.
Змінив(ла) vlad89, 27-06-2007 23:34 |
|
Автор |
RE: LNU FAMI TJU Contest 22 |
Romko
Користувач
Повідомлень: 113
Звідки: mdegree
Зареєстрований: 07.11.06 |
Опубліковано 27-06-2007 23:50 |
|
|
Я тільки не врахував умови про 14
 |
|
Автор |
RE: LNU FAMI TJU Contest 22 |
Romko
Користувач
Повідомлень: 113
Звідки: mdegree
Зареєстрований: 07.11.06 |
Опубліковано 27-06-2007 23:50 |
|
|
Доречі, задача D робилась динамікою, жадним?
 |
|
Автор |
RE: LNU FAMI TJU Contest 22 |
Ostap
Користувач
Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06 |
Опубліковано 28-06-2007 00:21 |
|
|
Доречі, задача D робилась динамікою, жадним?
Динаміка.
Не помиляється той, хто нічого не робить! |
|
Автор |
RE: LNU FAMI TJU Contest 22 |
ibm
Користувач

Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07 |
Опубліковано 28-06-2007 00:24 |
|
|
Vladislav_Simonenko написав:
Розбиваєш на макс. за кількістю кучі (K == 13, тоді по 12). В тебе може залишитися одна купа. Якщо в ній не 13, то це відповідь. Якщо ж 13, то ти можеш перекласти один диск з якоїсь лівої групи, де максимум до неї, так щоб вийшло 14, але лише в тому випадку, якщо 1) така взагалі є 2) інші купи не по 14 дисків.
Блін! Я так і робив! А воно - не канало!
Pascal not dead! |
|
Автор |
RE: LNU FAMI TJU Contest 22 |
Torax
Користувач

Повідомлень: 75
Звідки: ЛНУ
Зареєстрований: 03.03.06 |
Опубліковано 28-06-2007 00:48 |
|
|
розкажіть як конкретно динамікою там робити задачу D? |
|
Автор |
RE: LNU FAMI TJU Contest 22 |
Ostap
Користувач
Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06 |
Опубліковано 28-06-2007 02:07 |
|
|
розкажіть як конкретно динамікою там робити задачу D?
Ідея така:
нехай маємо наше число М (потреба пального). Представимо його в двійковому вигляді, наприклад:
0010110
пробігаємося від старших бітів і шукаємо не нульовий елемент (4-тий біт на прикладі). Ми тепер маємо два варіанти: купити ємкість розміру 2^4 або не купувати, а перенести "борг" в молодші розряди - тобто купити цей об'єм меншими ємкостями. При переносі отримаємо таке представлення (вже не двійкове):
0002110
(одна ємкість об'єму 2^k перетворюється в дві 2^(k-1))
з такого стану ми маємо 3 переходи: купити 0, 1 або 2 ємкості об'єму 2^3 і перейти ми можемо у стани такі:
0000510
0000310
0000110
відповідно.
Отже охарактеризуємо стан динамічної системи:
1) k - позиція (біт) яку ми розглядаємо - від 31 до 0
2) величина "боргу" - скільки потрібно ще купити об'єму пального крім того, що описане бітами починаючи з k (поточної позиції) в напрямку молодших бітів. Борг може бути від 0 до S, де S - кількість ємкостей об'єму меншого за 2^k, оскільки більший борг ми заповнити точно не зможемо.
Отже маємо максимум 32х100000 = 3.2М різних можливих динамічних позицій.
З кожної позиції ми можемо побудувати такі переходи:
- купувати від 0 до min(борг(+1 якщо поточний біт виставлений), C[k]) ємкостей об'єму 2^k (тут C[k] - к-сть ємкостей об'єму 2^k) а решту боргу переносити на наступний розряд - в наступну динамічну позицію.
Крім цього інтуїтивно зрозуміло, що коли ми на певному кроці купуємо кілька ємкостей об'єму 2^k, то нам потрібно вибрати ті, які мають найменшу ціну. Тобто перш за все потрібно посортувати ємкості по цінах в кожній групі з однаковими об'ємами.
Весь цей алгоритм дуже просто реалізувати за допомогою рекурсії з мемоізацією.
Не помиляється той, хто нічого не робить! |
|
Автор |
RE: LNU FAMI TJU Contest 22 |
ibm
Користувач

Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07 |
Опубліковано 28-06-2007 10:45 |
|
|
Romko написав:
Я тільки не врахував умови про 14
А що за умова ще така? там, походу те саме, що й при < 13. Походу умови треба тільки на 15 і я так зробив...
Ось мій непроканавший атсорс
begin
readln(n);
for n:=n downto 1 do
begin
readln(k,cd);
if (cd=13) then cd:=12;
cds:=k div cd;
if ((k mod cd)=13) and (cd<15) then cds:=cds+2 else
if ((k mod cd)>0) then cds:=cds+1;
if cds=0 then cds:=1;
writeln(cds);
end;
end.
І що тут поганого?
Pascal not dead! |
|
Автор |
RE: LNU FAMI TJU Contest 22 |
ibm
Користувач

Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07 |
Опубліковано 28-06-2007 10:48 |
|
|
Кул! mMasters рулить не менше Остапа! 45 хвилин і 4 задачі!
Pascal not dead! |
|
Автор |
RE: LNU FAMI TJU Contest 22 |
ibm
Користувач

Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07 |
Опубліковано 28-06-2007 11:09 |
|
|
Доречі як робилась задачка з матрицею (simple game):
http://acm.tju.edu.cn/toj/vcontest/showp251_A.html
Я за неї вже взявся в кінці, написав щось нашвидкоруч (за 15хв., бо наробив троха багів) і попробував здати за 2хв. до кінця. Звичайно я не здивувався, коли в мене видало Time Limit - в цьому задача й полягала... ...
Pascal not dead!
Змінив(ла) ibm, 28-06-2007 11:11 |
|
Автор |
RE: LNU FAMI TJU Contest 22 |
webmaster
Головний Адміністратор

Повідомлень: 1135
Зареєстрований: 17.03.07 |
Опубліковано 28-06-2007 12:17 |
|
|
ibm написав:
Кул! mMasters рулить не менше Остапа! 45 хвилин і 4 задачі! 
Та він (або вони) підглянули вчорашні задачі  |
|
Автор |
RE: LNU FAMI TJU Contest 22 |
Ostap
Користувач
Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06 |
Опубліковано 28-06-2007 13:48 |
|
|
2 ibm:
І що тут поганого?
Спробуй тест
1
13 20
Відповідь, зрозуміло:
2
твоя прога дає 1...
Не помиляється той, хто нічого не робить! |
|
Автор |
RE: LNU FAMI TJU Contest 22 |
DixonD
Користувач
Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06 |
Опубліковано 28-06-2007 13:53 |
|
|
В задачі А потрібно було знайти к-ість пар взаємо простих чисел? |
|
Автор |
RE: LNU FAMI TJU Contest 22 |
Mace Windu
Користувач
Повідомлень: 141
Звідки: НУ "ЛП"
Зареєстрований: 13.04.06 |
Опубліковано 28-06-2007 15:06 |
|
|
Та він (або вони) підглянули вчорашні задачі Нічого ми не підглядали =) Годину думали, потім почали тупити =) |
|
Автор |
RE: LNU FAMI TJU Contest 22 |
Mace Windu
Користувач
Повідомлень: 141
Звідки: НУ "ЛП"
Зареєстрований: 13.04.06 |
Опубліковано 28-06-2007 15:19 |
|
|
Було б цікаво почитати, як робиться G? Ми писали динаміку, але вона не пройшла... |
|
Автор |
RE: LNU FAMI TJU Contest 22 |
GeKa
Користувач
Повідомлень: 3
Звідки: NU"LP"
Зареєстрований: 11.03.06 |
Опубліковано 28-06-2007 16:15 |
|
|
Ostap написав:
розкажіть як конкретно динамікою там робити задачу D?
Ідея така:
нехай маємо наше число М (потреба пального). Представимо його в двійковому вигляді, наприклад:
0010110
пробігаємося від старших бітів і шукаємо не нульовий елемент (4-тий біт на прикладі). Ми тепер маємо два варіанти: купити ємкість розміру 2^4 або не купувати, а перенести "борг" в молодші розряди - тобто купити цей об'єм меншими ємкостями. При переносі отримаємо таке представлення (вже не двійкове):
0002110
(одна ємкість об'єму 2^k перетворюється в дві 2^(k-1))
з такого стану ми маємо 3 переходи: купити 0, 1 або 2 ємкості об'єму 2^3 і перейти ми можемо у стани такі:
0000510
0000310
0000110
відповідно.
Отже охарактеризуємо стан динамічної системи:
1) k - позиція (біт) яку ми розглядаємо - від 31 до 0
2) величина "боргу" - скільки потрібно ще купити об'єму пального крім того, що описане бітами починаючи з k (поточної позиції) в напрямку молодших бітів. Борг може бути від 0 до S, де S - кількість ємкостей об'єму меншого за 2^k, оскільки більший борг ми заповнити точно не зможемо.
Отже маємо максимум 32х100000 = 3.2М різних можливих динамічних позицій.
З кожної позиції ми можемо побудувати такі переходи:
- купувати від 0 до min(борг(+1 якщо поточний біт виставлений), C[k]) ємкостей об'єму 2^k (тут C[k] - к-сть ємкостей об'єму 2^k) а решту боргу переносити на наступний розряд - в наступну динамічну позицію.
Крім цього інтуїтивно зрозуміло, що коли ми на певному кроці купуємо кілька ємкостей об'єму 2^k, то нам потрібно вибрати ті, які мають найменшу ціну. Тобто перш за все потрібно посортувати ємкості по цінах в кожній групі з однаковими об'ємами.
Весь цей алгоритм дуже просто реалізувати за допомогою рекурсії з мемоізацією.
прікольно, але є альтернатива...як на мене - простіша
for (i = 0 to 30)
{
i-й біт є в М -> вибрали надешевший і додали до результату (якшо такого не існує - розв'язку нема)
всі цестерни розміром і, що залишилися, посортували по ціні і попарно позєднували, утворивши цестерни розміром 2і.
} |
|
Автор |
RE: LNU FAMI TJU Contest 22 |
DixonD
Користувач
Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06 |
Опубліковано 28-06-2007 16:36 |
|
|
to Geka: класно! 8-) |
|
Автор |
RE: LNU FAMI TJU Contest 22 |
Ostap
Користувач
Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06 |
Опубліковано 28-06-2007 16:40 |
|
|
прікольно, але є альтернатива...як на мене - простіша
for (i = 0 to 30)
{
i-й біт є в М -> вибрали надешевший і додали до результату (якшо такого не існує - розв'язку нема)
всі цестерни розміром і, що залишилися, посортували по ціні і попарно позєднували, утворивши цестерни розміром 2і.
}
Справді, твій розв'язок значно кращий ніж мій.
*THUMBS UP*
Не помиляється той, хто нічого не робить! |
|