Буквально несколько часов назад на Хабре была опубликована очень интересная статья.
Конечно, сейчас задачи кажутся совсем простыми. Неужели через четверть века про нынешние гробы скажут то же самое?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3856 |
| 2 | jiangly | 3747 |
| 3 | orzdevinwang | 3706 |
| 4 | jqdai0815 | 3682 |
| 5 | ksun48 | 3591 |
| 6 | gamegame | 3477 |
| 7 | Benq | 3468 |
| 8 | Radewoosh | 3462 |
| 9 | ecnerwala | 3451 |
| 10 | heuristica | 3431 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | -is-this-fft- | 162 |
| 3 | Dominater069 | 160 |
| 4 | Um_nik | 158 |
| 5 | atcoder_official | 156 |
| 6 | djm03178 | 153 |
| 7 | adamant | 152 |
| 8 | luogu_official | 149 |
| 9 | awoo | 147 |
| 10 | TheScrasse | 146 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2025 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 20.02.2025 04:41:20 (l3).
Десктопная версия, переключиться на мобильную.
При поддержке
Вы можете сходу решить Т4?
Нет, мне все-таки пришлось подумать над ней минут 10-15.
Но я же не вхожу в топ-200, мне такое тугодумие позволительно...
Круто! Мне эту задачу уже пару раз за последнее время рассказывали, и я до сих пор не имею представления, как её решать.
Совершенно непривычно думать в терминах магнитных лент, тем более что random access на этих устройствах выполняется за линейное время от позиции ячейки.
Идея решения под спойлером.
Не зависит ли это от процента компьютеризации населения?
В 1989 году из нашего класса, из 30 человек (ну я в той школе во 2-4 классе учился) только один человек имел дома Spectrum (48кб оперативки и один мееедленный магнитофон, хуже чем в задаче T4). В 1995 когда я в 8й класс поступил в свою третью школу, помнится, IBM-ы различные процентов у 40 были, а через год у двоих появились первые пентиумы. У меня бушная 386 появилась ещё через год :)
Да и новые языки меняют жизнь — на факультативе по алгоритмам мы обсуждали разворот и вращение строки (современным новичкам на питоне трудно понять в чём задача этой задачи) а графы представлять чем-либо кроме матрицы смежности казалось слишком насосным, поскольку мэпы в паскале отсутствовали а с массивами динамического размера возиться было неудобно. Сейчас это вспоминается как-то... с недоверием к себе самому. Массив больше 64кб не влезал в сегмент — я помню с каким удивлением пересел на Watcom C с 4-разрядными интами... :D
В 2000-м помню задачки которые нам показывали с разных уровней ACM... Они не выглядели так непонятно (для меня) как нынешние D и E из Div1 здесь — хотя допускаю что это субъективно, но можно поднять что-нибудь для сравнения... :)
Сейчас ситуация уже не та — м.б. передовые страны вышли на насыщение в смысле компьютеризации. Ну а остальные подтягиваются. Исходя из этого вероятно некоторым гробам действительно предстоит изменить категорию, но какие-то вероятно гробами и останутся.
Ну это если не фантазировать на тему что будет решена P=NP и квантовые компьютеры подешевеют. Хотя если я правильно понимаю по поводу второго предположения фантазировать уже пора. Вот это, имхо, действительно может новые качественные задачи внести, даже если по первости участники будут сдавать первый тур на бумажке, а к машинному допускать будут только 20 топовых участников.
По поводу квантовых компьютеров — у меня есть опасения, что прежде чем подешеветь, им следует хотя бы появиться. В их полноценном виде. Потому что, AFAIK, львиная часть ныне существующих КК имеют определенные проблемы, реализованы не полноценно и на сенсацию-революцию в мире инженеров пока не тянут. И перспективы весьма смутны, ибо что-то там в микро-мире кубитов работает хорошо в количестве N штук, и неясным образом начинает "глючить" в количестве N+1. Экспертом не являюсь, и хотелось бы, конечно, ошибаться.
Может, СF не самое то место для данных обсуждений, но если у кого-то есть что сказать по теме — wellcome! Или хотя бы ссылочек. Думаю, многим интересно.