160922 recipes — различия между версиями
(Новая страница: «* swap Представьте, что числа были бы 10^6. Тогда бы задача решалась просто массивом, верно? Н…») |
м |
||
| Строка 9: | Строка 9: | ||
Помните, что табличка должна быть больше, чем число элементов в ней, но помните и то, что чем больше съедено памяти, тем медленнее программа. | Помните, что табличка должна быть больше, чем число элементов в ней, но помните и то, что чем больше съедено памяти, тем медленнее программа. | ||
| + | |||
| + | Попробуйте сначала написать решение с массивом, | ||
| + | для маленьких чисел, убедитесь, что оно проходит сколько-то тестов, затем приступайте к решению для больших чисел. | ||
* mice | * mice | ||
| Строка 27: | Строка 30: | ||
* painter | * painter | ||
Обратите внимание на размер входных данных!! | Обратите внимание на размер входных данных!! | ||
| + | |||
| + | Есть как минимум три разных разумных способа решить эту задачу. | ||
* fastadd | * fastadd | ||
Разобрана на практике последней (4a). Очень короткий и простой код, он почти весь в разборе практики приведен. | Разобрана на практике последней (4a). Очень короткий и простой код, он почти весь в разборе практики приведен. | ||
| − | Кстати, можно не бояться создавать массив размера 2^{24}. | + | Кстати, можно не бояться создавать и честно заполнять нужными данными массив размера 2^{24}. |
А еще вы теперь умеете брать по модулю :) | А еще вы теперь умеете брать по модулю :) | ||
Версия 04:37, 28 сентября 2016
- swap
Представьте, что числа были бы 10^6. Тогда бы задача решалась просто массивом, верно?
Но числа 10^9, нельзя массив с такими большими индексами. И вот тут на помощь приходит хеш-таблица.
В конспекте есть по сути готовый код.
Без readInt/writeInt вряд ли зайдет.
Помните, что табличка должна быть больше, чем число элементов в ней, но помните и то, что чем больше съедено памяти, тем медленнее программа.
Попробуйте сначала написать решение с массивом, для маленьких чисел, убедитесь, что оно проходит сколько-то тестов, затем приступайте к решению для больших чисел.
- mice
Похожа на meeting с прошлой недели, решение которой выложено.
Вообще выложены все решения всех старых задач. Туда можно и полезно смотреть.
- evalpm, evalhard
Есть набросок кода в конспетке. Можно заглянуть еще в прошлогодний конспект (стр. 26), он тоже есть на страничке вики (уже).
Не ленитесь тестировать.
- isgood
Решается за O(n).
Может помочь разбор доп4a практики. Но определить, есть ли у подстроки хороший циклический сдвиг, может быть даже проще, чем хороша ли сама подстрока.
- painter
Обратите внимание на размер входных данных!!
Есть как минимум три разных разумных способа решить эту задачу.
- fastadd
Разобрана на практике последней (4a). Очень короткий и простой код, он почти весь в разборе практики приведен.
Кстати, можно не бояться создавать и честно заполнять нужными данными массив размера 2^{24}.
А еще вы теперь умеете брать по модулю :)
