Лектор університету встановив новий світовий рекорд по катанню на американських гірках. Він провів на цьому атракціоні дев’ять днів і дванадцять годин й усе ще почував себе досить добре для того, щоб продовжувати кататися.
Вася запропонував гарний (ідеальний) розв'язок задачі В.
Ідея:
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
Коротко:
1) ми можемо порахувати скільки нам буде коштувати поставити на наступну позицію j-ий символ, якщо ми перед тим поставили i-ий
2) ми можемо порахувати скільки буде коштувати поставити j-ий символ на останню позицію, якщо ми перед тим поставили i-ий, і якщо першим ми поставили k-ий.
P.S. це все по блокам, тому і потрібно 2-ий пункт.
3) якщо ми вже маємо пораховані ваги, то ми зможемо легко запустити динаміку по 4-ьом параметрам (маска, k, i, j).
Birthday(s):
