Подойдет любой online judge.
Спасибо.
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
3 дня
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
3 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | djm03178 | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 27.11.2024 13:42:38 (i2).
Десктопная версия, переключиться на мобильную.
При поддержке
С прошедшего CodeChef June 2012 Long Round была задача CLOSEST, в которой нужно было для набора точек P и набора точек-запросов Q для каждой точки-запроса q найти ближайшую к ней в наборе P. Это немного не Closest Pair problem, но смежная задача.
http://codeforces.me/contest/120/problem/J
Спасибо за советы. На самом деле мне стоило сразу заглянуть на http://e-maxx.ru/algo/nearest_points. Там конце есть список задач.
Да, хороший список. Нужно бы мне чаще заглядывать на e-maxx)) Я этого еще не видел, а он развивается...
В поддержку отечественного производителя: на e-maxx дана ссылка на задачу про треугольник минимального периметра за NlogN CodeJam Finals 2009. Есть ровно такая же задача на тимусе (2006 год).
Ещё есть, в абсолютно прямолинейной и очевидной постановке, на http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=3779 (Если там вдруг что не так — буду благодарен за bug report, но вроде должно быть всё нормально...)
А вообще с этой задачей довольно весело, что есть несложная эвристика тупейшего алгоритма, которую весьма сложно завалить ограниченным набором заранее заданных тестов. Подробнее http://codeforces.me/blog/entry/3879
Мне все хотелось у кого-то спросить: для какой цели нужны задачи такого рода: написал алгоритм, ПРЯМО предназначенный для решения именно этой задачи и получил АС?
Ну, окромя олимпиад бывают ещё и курсы (предметы), предназначенные тупо для всех подряд студентов соответствующей специальности... Там большинство задач (но не факт, все ли) и должны быть именно такими.
UPD: видимо, надо успокоить человека, что именно в нашем случае именно это рассматривалось как сложная задача для студентов соответствующей специальности... И тот (пока что единственный) курс (год обучения), коему она давалась, оказался слабоват и именно её никто не решил. И всё же остаюсь в твёрдой уверенности, что для всеобще-образовательных целей должны быть главным образом именно такие (до ужаса прозрачные) задачи.
Да, теперь понял. А мне только что вспомнилось, как нескольким группам по специальности "Информационные системы" в нашем универе подкинули задачу "посчитать, сколько существует чисел на промежутке [l; r] (10^7 <= l, r < 10^8), таких, что сумма первых четырех цифр равна сумме последних четырех цифр, ТЛ = 2 секунды". Задачу не решил никто.
P.S. Очевидно, я учусь на другой специальности :).
...Может, компы медленные были?:)
Может, на дворе был 2011 год, а студенты во время вычисления суммы цифр выполняли восемь делений вместо в худшем случае двух? :).
UPD. Я гоню: не восемь делений, конечно, а шестнадцать.
Ну, на кодшефе даже такое бы стопудово не прошло;)
На кодшефе лично я бы написал meet-in-the-middle за O(sqrt(r) * log(r)) и не парился.
Задача "сколько чисел на отрезке таких, что сумма первых четырех = сумме последних четырех" решается динамикой. Если зафиксировать длину числа, состояние = [сумма1, сумма2, сколько цифр уже выписано]. Выписывать цифры нужно со старших разрядов. Чтобы удобнее писалось, как обычно, можно сказать, что [l..r] = [1..r] — [1..l-1].
В универе скорее всего хотели, чтобы вы написали перебор, который работает за 10^8 сложений, сравнений и обращений к памяти.