160922 recipes — различия между версиями

Текущая версия на 04:38, 28 сентября 2016

• swap

Представьте, что числа были бы 10^6. Тогда бы задача решалась просто массивом, верно?

Но числа 10^9, нельзя массив с такими большими индексами. И вот тут на помощь приходит хеш-таблица.

В конспекте есть по сути готовый код.

Без readInt/writeInt вряд ли зайдет.

Помните, что табличка должна быть больше, чем число элементов в ней, но помните и то, что чем больше съедено памяти, тем медленнее программа.

Попробуйте сначала написать решение с массивом, для маленьких чисел, убедитесь, что оно проходит сколько-то тестов, затем приступайте к решению для больших чисел.

• mice

Похожа на meeting с прошлой недели, решение которой выложено.

Вообще выложены все решения всех старых задач. Туда можно и полезно смотреть.

• evalpm, evalhard

Есть набросок кода в конспетке. Можно заглянуть еще в прошлогодний конспект (стр. 26), он тоже есть на страничке вики (уже).

Не ленитесь тестировать.

• isgood

Решается за O(n).

Может помочь разбор доп4a практики. Но определить, есть ли у подстроки хороший циклический сдвиг, может быть даже проще, чем хороша ли сама подстрока.

• painter

Обратите внимание на размер входных данных!!

Есть как минимум три разных разумных способа решить эту задачу.

• fastadd

Разобрана на практике последней (4a). Очень короткий и простой код, он почти весь в разборе практики приведен.

Кстати, можно не бояться создавать и честно заполнять нужными данными массив размера ${\displaystyle 2^{24}}$.

А еще вы теперь умеете брать по модулю :)