Головна Обговорення Лінки Пошук Prykladna СС Прикладна _КОЛЕДЖ 18.01.2020 05:39:42 (EEST=GMT+2)
ACM -
Навігація -
Теми форуму +
Чи знали ви, що... ? (beta) -
В Англії спочатку швидкість автомобіля була обмежена законом до швидкості пішохода. Їх вважали настільки небезпечними, що попереду повинна була йти людина з червоним прапорцем, яка повідомляла пішоходів та кучерів про небезпеку. Закон відмінили у 1896 році.
Події
ПнВтСрЧтПтСбНд
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
Сторінка 1 з 2 1 2 >
Автор LNU FAMI TJU Contest 22
Ostap
Адміністратор

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


Не помиляється той, хто нічого не робить!
Ostap 200-738-699 Ostap Korkuna (Lviv NU) Надіслати приватне повідомлення
Автор RE: LNU FAMI TJU Contest 22
ibm
Користувач

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

Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07
Опубліковано 27-06-2007 23:26
Як ти робив (сам алгоритм) задачку з CD? В мене чомусь дало неправильну в-дь, хоча я, я здається все врахував... Задача нагадує якусь, звідси, яку я вже давно здав і Забобонного Гриця з обласної...B);)


Pascal not dead!
ibmua 353747640 ibm http://code.knopok.net/ Надіслати приватне повідомлення
Автор RE: LNU FAMI TJU Contest 22
vlad89
Користувач

Повідомлень: 8
Звідки: Kiev National University
Зареєстрований: 13.03.06
Опубліковано 27-06-2007 23:33
ibm написав:
Як ти робив (сам алгоритм) задачку з CD? В мене чомусь дало неправильну в-дь, хоча я, я здається все врахував... Задача нагадує якусь, звідси, яку я вже давно здав і Забобонного Гриця з обласної...B);)


Розбиваєш на макс. за кількістю кучі (K == 13, тоді по 12). В тебе може залишитися одна купа. Якщо в ній не 13, то це відповідь. Якщо ж 13, то ти можеш перекласти один диск з якоїсь лівої групи, де максимум до неї, так щоб вийшло 14, але лише в тому випадку, якщо 1) така взагалі є 2) інші купи не по 14 дисків.


Brain is the organ that thinks that it thinks.
Змінив(ла) vlad89, 27-06-2007 23:34
vlad89 288869492 Vladyslav Simonenko Надіслати приватне повідомлення
Автор RE: LNU FAMI TJU Contest 22
Romko
Користувач

Повідомлень: 113
Звідки: mdegree
Зареєстрований: 07.11.06
Опубліковано 27-06-2007 23:50
Я тільки не врахував умови про 14


Treizzz 7715843 Romko [Lviv NU] Надіслати приватне повідомлення
Автор RE: LNU FAMI TJU Contest 22
Romko
Користувач

Повідомлень: 113
Звідки: mdegree
Зареєстрований: 07.11.06
Опубліковано 27-06-2007 23:50
Доречі, задача D робилась динамікою, жадним?


Treizzz 7715843 Romko [Lviv NU] Надіслати приватне повідомлення
Автор RE: LNU FAMI TJU Contest 22
Ostap
Адміністратор

Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06
Опубліковано 28-06-2007 00:21
Доречі, задача D робилась динамікою, жадним?


Динаміка.


Не помиляється той, хто нічого не робить!
Ostap 200-738-699 Ostap Korkuna (Lviv NU) Надіслати приватне повідомлення
Автор 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!
ibmua 353747640 ibm http://code.knopok.net/ Надіслати приватне повідомлення
Автор RE: LNU FAMI TJU Contest 22
Torax
Адміністратор

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

Повідомлень: 75
Звідки: ЛНУ
Зареєстрований: 03.03.06
Опубліковано 28-06-2007 00:48
розкажіть як конкретно динамікою там робити задачу D?
Torax 275476769 Torax[Lviv NU] Надіслати приватне повідомлення
Автор 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, то нам потрібно вибрати ті, які мають найменшу ціну. Тобто перш за все потрібно посортувати ємкості по цінах в кожній групі з однаковими об'ємами.

Весь цей алгоритм дуже просто реалізувати за допомогою рекурсії з мемоізацією.



Не помиляється той, хто нічого не робить!
Ostap 200-738-699 Ostap Korkuna (Lviv NU) Надіслати приватне повідомлення
Автор RE: LNU FAMI TJU Contest 22
ibm
Користувач

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

Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07
Опубліковано 28-06-2007 10:45
Romko написав:
Я тільки не врахував умови про 14

А що за умова ще така? там, походу те саме, що й при < 13. Походу умови треба тільки на 15 і я так зробив...
Ось мій непроканавший атсорс:D
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!
ibmua 353747640 ibm http://code.knopok.net/ Надіслати приватне повідомлення
Автор RE: LNU FAMI TJU Contest 22
ibm
Користувач

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

Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07
Опубліковано 28-06-2007 10:48
Кул! mMasters рулить не менше Остапа! 45 хвилин і 4 задачі!B)


Pascal not dead!
ibmua 353747640 ibm http://code.knopok.net/ Надіслати приватне повідомлення
Автор 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хв. до кінця. Звичайно я не здивувався,:o коли в мене видало Time Limit - в цьому задача й полягала...:(B)...


Pascal not dead!
Змінив(ла) ibm, 28-06-2007 11:11
ibmua 353747640 ibm http://code.knopok.net/ Надіслати приватне повідомлення
Автор RE: LNU FAMI TJU Contest 22
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 28-06-2007 12:17
ibm написав:
Кул! mMasters рулить не менше Остапа! 45 хвилин і 4 задачі!B)


Та він (або вони) підглянули вчорашні задачі ;)
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: LNU FAMI TJU Contest 22
Ostap
Адміністратор

Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06
Опубліковано 28-06-2007 13:48
2 ibm:
І що тут поганого?


Спробуй тест
1
13 20

Відповідь, зрозуміло:
2

твоя прога дає 1...


Не помиляється той, хто нічого не робить!
Ostap 200-738-699 Ostap Korkuna (Lviv NU) Надіслати приватне повідомлення
Автор RE: LNU FAMI TJU Contest 22
DixonD
Адміністратор

Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06
Опубліковано 28-06-2007 13:53
В задачі А потрібно було знайти к-ість пар взаємо простих чисел?
DixonD 427265719 dixond[злий_пес]acm[на]lviv[на]ua DixonD (Lviv NU) http://dixond.blogspot.com/ Надіслати приватне повідомлення
Автор RE: LNU FAMI TJU Contest 22
Mace Windu
Користувач

Повідомлень: 141
Звідки: НУ "ЛП"
Зареєстрований: 13.04.06
Опубліковано 28-06-2007 15:06
Та він (або вони) підглянули вчорашні задачі
Нічого ми не підглядали =) Годину думали, потім почали тупити =)
Mace_Windu 248-855-941 Mace(Lviv Polytechniс NU) Надіслати приватне повідомлення
Автор RE: LNU FAMI TJU Contest 22
Mace Windu
Користувач

Повідомлень: 141
Звідки: НУ "ЛП"
Зареєстрований: 13.04.06
Опубліковано 28-06-2007 15:19
Було б цікаво почитати, як робиться G? Ми писали динаміку, але вона не пройшла...
Mace_Windu 248-855-941 Mace(Lviv Polytechniс NU) Надіслати приватне повідомлення
Автор 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-)
DixonD 427265719 dixond[злий_пес]acm[на]lviv[на]ua DixonD (Lviv NU) http://dixond.blogspot.com/ Надіслати приватне повідомлення
Автор 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*



Не помиляється той, хто нічого не робить!
Ostap 200-738-699 Ostap Korkuna (Lviv NU) Надіслати приватне повідомлення
Сторінка 1 з 2 1 2 >
Перейти на форум:
Банери
Голосування
Що Ви б хотіли отримати в якості подарунку на змаганні з програмування?

Медалі

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

торт

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

квитки в кіно

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

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

книги

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

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

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