Сегодня прошел первый тур вышеописанной олимпиады. Предлогаю обсудить здесь задачи.
Сегодня прошел первый тур вышеописанной олимпиады. Предлогаю обсудить здесь задачи.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | adamant | 152 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
А-шку бинпоиском по ответу решал
А как вы осуществляете проверку на то, что
k! % n = 0Лично я разбил n на простые множители, а затем для каждого простого множителя находил k! и из них брал максимальный(если было несколько одинаковых простых множителей, то считал что то навроде ans=max(ans,минимальный к, чтобы k!/x+k!/x*x+k!/x*x*x была >= количеству одинаковых простых множителей)).
И сколько в итоге получили баллов?
Незнаю скоро выйдут резы(поидее я как то убито объяснил свое решение)
По А 100
ошибка( написал неправильный алгоритм
Ммм что!?
Для каждого простого делителя N сравниваем степень этого простого в N со степенью этого простого в K!.
А степень простого в K! находится так:
B примерно за O(8*N) (тама 8 различных случаев и каждый перебираем за n).
C — находил для каждой X-axis точки максимальный рост(который равняеться h+0.5 или же если пересекаются то h+0.75) и суммировал их.Где то за O(N*H+X).
C. Тоже самое. Решение работает в худшем случаи за 2 * 10^8 при TL 2 секунды :(.
я добавил break; когда он хоть раз пересекаеться(надеюсь затащит:D)
У меня макстест работал у себя за 1.7. Но прошло не на full (86), пока не знаю почему.
UPD. WA оказывается. Тупая ошибка. Проверял до 10^6 надо до 10^6+10^4. :(
в С можно по точкам ходить, отсортировав(для треугольника p[i], l[i], r[i]).
Надо не забыть только убрать все внутренние треугольники за N^2(я забыл)
Надо еще с -10^4
Это я не забыл, потому что в сэмпле есть :)
А можно сканлайном вот так:
Добавим в вектор для каждой верхней вершины треугольника (x, y) данный (x — 1, 1) и (x + 1, 1). Проходим по всем высотам i сверху вниз, и по вектору слева направо, поддерживая сканлайн и несколько случаев, когда мы добавляем sqrt(2), 3sqrt(2) / 2 или 2. Сложность O(2NH), и че-то все задачи решаются за 10^8, может это нормально для ваших серверов?
У нас в каждом регионе по-другому и еще нету feedback-а.
У вас в области тоже катают? Не знаю как других, но меня раздражает как другие пытаются скатать (непонятно откуда) и хотят порвать тех кто чалил с 7 класса олимпиаду.
UPD: Они катают отсюда походу
Чалил?
"Чалил"
çalıştı
dASdasdasda asdf MInus give
лол :)
Вы Б — шку как написали(не квадрат)
У нас есть 8 случаев
насчет х(x1>=x2 или же x1<x2), y(y1>=y2 и y1<y2), z(аналогично).
2 случая * 2 * 2 = 8 случаев.
Каждый случай за O(N) находим максимум и минимум и его разницу берем. И из всех разниц берем максимальный.
Итоговая асимптотика O(8*n).
блин) я так подумал но не смог доказать) завтра сюда резы скинте
Скорее всего завтра будет игра, граф и строки. Всем удачи!
игра и граф не будут отвечаю) геометрия,динамика и строки будут отвечаю) ну все равно удачи всем)
Как на счет прошлой области???
Ахах, ни игры, ни строк, ни динамики и ни графов не было
зато геометрия была и F — ку можно двухмерной динамикой решить:D
Не знаю как вы, а я прочитав условия, увидел первые 2 задачи как: напишите бинпоиск по ответу.
А геома халява по идее
Увидел в B: решите это уравнение и там всё будет :)
Задачи второго тура как решать?
F можно за N, я написал за NlogN что то вроде этого:
Вроде должно проходить.
В D я написал жадное решение, сортируя девушек по росту, ищу для них минимальную пару.
Можно диницу было пустить за N*sqrt(N) :)
Сколько баллов по второму кстати?
Еще не проверили. Но не фулл. Я перебирал (p-a) тоже.)
Прошел 2-тур, может кто-то сделать разбор задач?
D) Отсортим оба массива по невозрастанию, пустим два указателя, рассмотрим случаи, когда они родственники. То есть, если они не родственники, просто присваиваем i-тому мальчику j-тую девочку. В другом случае, пытаемся i + 1 -ому мальчику присвоить j-тую девочку, а для i — того двигаем второй указатель.
Е) Предпосчитаем все делители S до его корня четвертой и корня третьей степени(2 массива). Пройдемся по ним двумя циклами. Первым итератором будет p — c, вторым p — b. p — c + p — b = 2a -> найдем а. Нужно не забыть проверить чтобы все делилось на 2.
Решаем квадратное уравнение p^2 — ap — S/(p — b)/(p — c) = 0.
F) Для каждого i посчитаем ближайший справа и слева элементы, меньшие его. Ответом будет максимум среди всех (r[i] — l[i] — 1) * a[i](не забудьте отнять k — 1)
Капец я Е не смог до норм решения додуматься
Я вообще на контесте думал, что ответы в Е только 0 и 1. :)
Может кто-нибудь скинуть условия 2-ого тура
Вот
У нас кто-то взял задачи до контеста (вчера) можете сказать откуда?
Утечка была
Откуда?
Эти задачи были на Другой олимпиаде
Задачу F можно решить используя этот алгоритм. Проходит на 100% !!!
Не скажете как?
В статье описывается алгоритм за O(NM) Хотя в задаче maxN = 105 и maxa[i] = 109. Или я что-то не понимаю?
Я за O(N*N — ?) решил на 100 ))
Можно поподробнее?
А можно где-нибудь посмотреть результаты?