а кто Рика от халявы остановит? доедет до пункта y, не остановится и пойдёт дальше по кругу лимонад фармить, пока не надоест

вроде ж нет условия что надо в 2 остановиться?

итерируем квадрат k+3*1e9 раз, потом не более чем за 3 доходим до цели - получаем не более -k для произвольного k

А, ок

все та же задача с риком
реализовала сначала через обычный алгоритм Дейкстеры, пишет,что времени много,через контейнер на каком-то тесте валится...
помогите,пожалуйста,в чем ошибка?

Можно ссылку на задачу?
Я бы написал не через set, а через приоритетную очередь. Раза в 2 должно ускорить

там нужно заходить через почту института

а что нужно уточнить?

Внизу, заголовок priority_queue
https://e-maxx.ru/algo/dijkstra_sparse
Сет, из которого можно удалять только самый первый элемент, что нам и нужно. Только он по убыванию  хранит, поэтому расстояния поддерживаем перевернутые

а что через контейнер не так? он на нем валится не из-за времени

А, извини

Кстати, ты тут в коде умножаешь два int < 1e6, происходит переполнение
Замени на ll

Можно через 2 очереди, одна для последнего действия a, другая для последнего действия b

Работать будет линейно

Я так понял у нее не TL. У нее в коде перемножается в интах i*i, i < 1000000, 10^12 не помещаются, получаются отрицательные числа, происходит выход за границы массива

А

Привет!

Есть задача по поиску Z-функции строки, выполняю её на моей любимой джаве:

 private static int[] zFucntion(String s) {
        int n = s.length();
        int z[] = new int[n];

        for (int i = 1, l = 0, r = 0; i < n; ++i) {
            if (i <= r) {
                z[i] = Math.min(r - i + 1, z[i - l]);
            }

            while (i + z[i] < n && s.split("")[z[i]].equals(s.split("")[i + z[i]])) {
                ++z[i];
            }

            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }

        return z;
    }

Для считывания и записи используется два файла, применяю буферизованны IO API:

 private static final File inputFile = new File("input.txt");
    private static final File outputFile = new File("output.txt");

    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new FileReader(inputFile));
        BufferedWriter writer = new BufferedWriter(new FileWriter(outputFile));

        String data;

        try {
            while ((data = input.readLine()) != null) {
                int[] prefixes = zFucntion(data);
                StringBuilder outputData = new StringBuilder();

                for (int i = 1; i < prefixes.length; i++) {
                    outputData.append(prefixes[i]).append(" ");
                }

                writer.write(outputData.toString().trim() + "\n");
            }
        } finally {
            input.close();
            writer.close();
        }
    }

Но вот если попробовать в input передать рандомную строку размеров 92670 символов, но алгоритм не проходит ограничение по времени. Может ли быть беда в алгоритме?

В телеграмме можно так скидывать код? Это как?