Подойдет любой online judge.
Спасибо.
Подойдет любой online judge.
Спасибо.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3382 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | heuristica | 3322 |
| 10 | maroonrk | 3312 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 144 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 133 |
| 9 | maroonrk | 132 |
| 10 | Proof_by_QED | 131 |
С прошедшего 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 сложений, сравнений и обращений к памяти.