Головна Обговорення Лінки Пошук Prykladna СС Прикладна _КОЛЕДЖ 29.03.2024 12:43:56 (EEST=GMT+2)
ACM -
Навігація -
Теми форуму +
Чи знали ви, що... ? (beta) -
Число 4 в Японії нещасливе, оскільки звучить так само, як слово «смерть».
Події
ПнВтСрЧтПтСбНд
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):
AVATARbbodio
AVATARklichuk
AVATARGrudik
AVATARKiraSvetlova

Перегляд теми
ACM Контестер | Змагання | Google Code Jam 2008
Автор Round 2
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 02-08-2008 22:33
Pакінчився Round 2 Google Code Jam.
Висловлюємо свої думки.
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Round 2
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 02-08-2008 22:40
B-large здало тільки 163 людини. Серед них і IBM, щкода що це йому не допомогло пройти у раунд3.
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Round 2
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 03-08-2008 22:46
Розв'язок задачі В

Вася запропонував гарний (ідеальний) розв'язок задачі В.
Ідея:
1) якщо A<=N*M, тоді розв'язок існує
2) інкаше (А>N*M) - не існує
3) якщо існує, ставимо першу точкі з координатами (0,0)
4) другу точку - (N,1)
5) а третю підбараємо таким чином, щоб площа трикутника була потрібною
6) така точка завжди буде.

Доведення:
Координати третої точки належать множині - [0..N-1]x[1..M], отже кількість цих точок є рівно N*M.
Потрібно довести, що площі трикутників побудовані на точках A(0,0), B(N,1), C(x,y), де xє[0..N-1] yє[1..M], є різними для різних x та y.

Запишемо площу через векторний добуток:
(Bx-Ax)*(Cy-Ay)-(Cx-Ax)*(By-Ay)
підставимо наші координати отрмаємо
(N-0)*(y-0)-(x-0)*(1-0)
=> N*y-x
враховуючи те, що xє[0..N-1] легко помітити, що для різних x та y результати будуть різні, що і потрібно було довести.
Змінив(ла) webmaster, 03-08-2008 22:49
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Round 2
Torax
Користувач

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

Повідомлень: 75
Звідки: ЛНУ
Зареєстрований: 03.03.06
Опубліковано 08-08-2008 22:00
хто розкаже як робити четверту задачу?
Torax 275476769 Torax[Lviv NU] Надіслати приватне повідомлення
Автор RE: Round 2
webmaster
Головний Адміністратор

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

Повідомлень: 1135
Зареєстрований: 17.03.07
Опубліковано 08-08-2008 23:14
Коротко:
1) ми можемо порахувати скільки нам буде коштувати поставити на наступну позицію j-ий символ, якщо ми перед тим поставили i-ий
2) ми можемо порахувати скільки буде коштувати поставити j-ий символ на останню позицію, якщо ми перед тим поставили i-ий, і якщо першим ми поставили k-ий.
P.S. це все по блокам, тому і потрібно 2-ий пункт.
3) якщо ми вже маємо пораховані ваги, то ми зможемо легко запустити динаміку по 4-ьом параметрам (маска, k, i, j).

Ось так, якщо коротко.
brus07 brus07 (Lviv NU) http://acm.lviv.ua Надіслати приватне повідомлення
Автор RE: Round 2
Torax
Користувач

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

Повідомлень: 75
Звідки: ЛНУ
Зареєстрований: 03.03.06
Опубліковано 09-08-2008 17:54
ясно, дякую, дійсно доволі просто ))
Torax 275476769 Torax[Lviv NU] Надіслати приватне повідомлення
Перейти на форум:
Голосування
Що Ви б хотіли отримати в якості подарунку на змаганні з програмування?

Медалі

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

торт

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

квитки в кіно

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

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

книги

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

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

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