Предлагаю здесь обсудить сие мероприятие и задачи.
Сслыка на задачи/результаты: http://acm.timus.ru/monitor.aspx?id=100
Предлагаю здесь обсудить сие мероприятие и задачи.
Сслыка на задачи/результаты: http://acm.timus.ru/monitor.aspx?id=100
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3390 |
| 6 | Um_nik | 3387 |
| 7 | tourist | 3384 |
| 8 | heuristica | 3322 |
| 9 | turmax | 3319 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 143 |
| 5 | AmShZ | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | maroonrk | 134 |
| 9 | BledDest | 132 |
| 10 | qwexd | 129 |
кажется можно ввести другие состояния и добавить новый переход - изменение последней буквы (например "a" -> "b", "b"-> "c", из "с" нет перехода).
Не туда
8
0
0.0000000000
1
7
0
2.1600000000
Кто как решал задачу С (Angry birds)?
У меня отличие в том, что когда зафиксировали 2ух обезьян, получаем систему линейных уравнений относительно {p, q2}:
p · xi - q2· xi2 = yi
p · xj - q2· xj2 = yj
Проверяем q2 > = 0, после чего подставляем остальных обезьян в уравнение. Это всё делается в целых числах, чтоб не было проблем с переполнением брал по разным простым модулям.
Почему в G не проходит такое решение?
Нам нужно максимизировать сумму cnt1[i]*cnt2[i], где i=1...100000.
На каждом шаге, пока не останется знаков вопроса, я выбирал такое число, чтобы сумма была максимальной.
В итоге ВА13.
Рассмотрим тест:
7
0 0 1 1 2 2 2
9
0 0 1 1 1 1 2 2 2
30
11
0 0 0 1 2 2 2 3 3 3 3
11
0 0 0 1 1 1 1 2 2 2 3
77
10
0 0 1 2 2 2 3 3 3 3
11
0 0 0 1 1 1 1 2 2 2 3
72
Нули из первой строки ты будет превращать в 1, т.к. это будет максимизировать твою сумму, а нули из второй строки в 3... Но лучше будет все нули превратить в 2.
UPD. Шутканул, после того как ты поставишь 1 в первой строке, во второй ты тоже выберишь 1, сейчас додумаю...У меня тоже ответ 30. Сначала нули из первой строки превращаются в 1, а потом у нас в первой строке уже больше 1 и нули из второй строки тоже превращаются в 1.UPD: Спасибо, я понял
Z[k].FI = -o_O+1
Я подобрал даже до первого сабмита. Правда, все равно +1, потому что сначала выводил вершины в порядке по часовой стрелке =)
P.S. И тогда совершенно непонятно, почему народ ее так грязно насдавал, если в тестах таких случаев не было
не туда
Я выпуклую оболочку написал для первых k точек в порядке сортировки. В конце надо рассмотреть тонкие случаи, когда в оболочке вышло 1 или 2 вершины.
Делали так же, только добавили в выпуклую оболочку точки (-1e9+1, -1e9) и (-1e9,-1e9+1). Все случаи отпадают.
А как нибудь красиво это доказывается?:)
Это же школьный контест. Конечно, доказывается.
Разобьём наш 4-угольник на 2 треугольника диагональю, соединяющей точки примыкания палок к берёзе и к земле. Пусть длины палок - a и b. Зафиксируем какую-то длину этой диагонали L. Тогда максимум площади нижнего треугольника очевидно достигается, когда эта диагональ идёт под углом 45. Тогда эта площадь равна 1/4*L^2.
Пусть теперь угол между палками равен p. Тогда площадь верхнего треугольника равна 1/2*a*b*sin(p). L^2 = a^2+b^2-2*a*b*cos(p). Итого суммарная площадь 1/2*a*b*sin(p) + 1/4*(a^2+b^2-2*a*b*cos(p)) = 1/4*(a^2+b^2) + 1/2*a*b*(sin(p)-cos(p)) = 1/4*(a^2+b^2)+1/sqrt(2)*a*b*sin(p-45). Максимум синуса достигается в 90, т.е. при p=135. Итого ответ 1/4*(a^2+b^2)+1/sqrt(2)*a*b
ну это почти по-человечески
мы просто для каждого слоя искали его нужный сдвиг (перебрав сначала общую картинку)
скидываем цвета, проходясь по кругу, в вектор, и с такими векторами уже все просто
Рассмотрим левый верхний квадрат 2*2. Заметим, что если в нем все цвета одинаковые, то картинка такая, какая нужна. Тогда переберем цвет, который в нем будет. Каждая из четырех клеток квадрата лежит на отдельном слое, а каждый слой представляет из себя зацикленную посл-ть 1, 2, 3, 4. Пусть у нас в некоторой клетке верхнего квадрата стоит число i, а мы хотим получить j. Понятно, что мы можем циклически сдвинуть последовательность 1-2-3-4 вправо или влево. Собственно, перебираем цвет левого верхнего квадрата и банально считаем стоимость сдвига его элементов в нужный цвет.