и cin.tie(0)

оптимум суммы (N+1)^(-c_ij) даст минимизацию, нет?

Математик который заваривает полный чайник?

Интересно почитать про лучшую стратегию для игр типо куки кликер

точно не умею, приближенно просто перебираем перестановками по 7 локальный оптимум стратегии

Лучшая стратегия: взлом протокола или кидание пачек купюр в монитор.

А так, если возьмём упрощённую модель: есть генераторы печенек g_i. Стоимость апгрейда генератора gi с уровня j на j+1 обозначим как l_ij.
Генератор gi на уровне j выдаёт c_ij печенек в единицу времени.

Дальше можно формулировать разные задачи с разными решениями.
Например, получить максимальный CPS (cookies per second) за T единиц времени.
Или за минимальное время получить для некоего gi* уровень j*.


У реальных куки кликеров усложняется то, параметры lij, cij не всегда известны на старте. И часто имеют какие-то разные отклонения от экспоненциальных схем.

простая эвристика - считать цену апгрейда на +1 печеньку

+1 за 10 лучше чем (10)
+10 за 200 (20)

Получается классическая задача оптимального управления в условиях полной / неполной информации

за минимальное время заработать S печенек суммарно (доходом, не прибылью), потому что асценды считаются от этого параметра
тут фигня, что сортировка особенная задача и все её соседи плохие

дейкстру на гиперкубе такое себе

вообще в самом кукикликере была багофича, что асценды работают по c' = sqrt(c) то есть решение c ~ t^3/2, а сама игра по c' = ln c, то есть решение c ~ t * ln t, так что надо было асцендить как не в себя с точностью до экспоненциального участка до предела золотой печеньки

А если +1 за 10 или +10 за 99

Всем привет) Как решать по нормальному следующую таску: есть текст из T символов и N (N порядка 10) строк, в каждой из которых указано 2 слова: X и Y. Нужно заменить в тексте каждый X на Y. Пока умею за O(T N): рассматриваем символ i и пытаемся приложить все паттерны. Можно ли как-то лучше и менее запарно?

а есть ли какой-то пример неразрешимого унарного языка?

мне нужен пример неразрешимого языка, который лежит в DTIME(n)/1, но там лежат все унарные языки, значит какой-то неразрешимый унарный тоже должен лежать

Что означает /1?

Подсказка имеет длину 1

Например язык номеров останавливающихся машин тьюринга. Тогда в качестве подсказки будет 1 на нужных нам номерах, на остальных 0.

а почему он неразрешимый?

Короче, если выберем простую нумерацию МТ (например, по возрастанию длины + лексикографическую сортировку среди одинаковых длин), то по записи МТ мы сможем легко находить ее номер, а значит разрешимость номеров будет эквивалентна разрешимости записей МТ. А последнее неразрешимо, читайте про Halting Problem.