Лягушки и их счастливые номера

110

21 января 2021, 02:00

Немножко про условие задачи : Дано N лягушек и бесконечное поле, в каждой лягушки есть свой счастливый порядковый номер. Лягушки приходят по очереди (1..N) они смотрят на клетку с номером 0, если она не занята то занимают ее, иначе перескакивают в клетку 0 + A[i], где A[i] - счастливый порядковый номер i-той лягушки, и повторяют этот процесс пока клетка не будет свободной.

Необходимо определить для каждой лягушки ее номер на бесконечном поле.

Пример:

6
2 3 2 4 4 6

Ответ:

0 3 2 4 8 6

Объяснение:

1-я лягушка посмотрела на клетку с номером 0, она не занята, она ее заняла.
2-я лягушка посмотрела на клетку с номером 0, она занята, перескочила на номер 3, не занята, она ее заняла.
3-я лягушка заняла клетку с номером 2 по аналогии с 2-й лягушкой.
4-я лягушка посмотрела на клетку номером 0, она занята, перескочила в клетку с номером 4, и заняла там своё место.
5-я лягушка посмотрела на клетку номером 0, она занята, перескочила в клетку с номером 4, она занята, перескочила в клетку с номером 8 и заняла ее.
6-я лягушка посмотрела на клетку номером 0, она занята, перескочила в клетку с номером 6, и заняла там своё место.

Какбы простая-то загадка, но ограничения большие:

1 <= N <= 3 * 10^5
1 <= A[i] <= 10^9
Ограничение по времени: 3 секунды
Ограничение по памяти: 256 МБ

Моя попытка была следующей:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ll n;
    cin >> n;
    set <ll> a;
    ll x;
    for (ll i = 0;i < n;i++) 
    {
        cin >> x;
        ll c = 0;
        if (a.size() == 0) {
            a.insert(0);
            cout << 0 << " ";
            continue;
        }
        while (a.find(c) != a.end()) c += x;
        a.insert(c);
        cout << c << " ";
    }
    return 0;
}

Но увы это решение не прошло по времени :(

Answer 1

Увидел тег любой-язык и поленился писать на плюсах...

40мс - когда у всех 300 000 лягушек одинаковое счастливое число
130мс - когда у 300 000 лягушек случайные счастливые числа от 1 до 10^9

Алгоритм на C#:

int[] Frogs(int[] frogs)
{
    // Тут храним минимальное число шагов, которые придется сделать очередной лягушке
    var steps = new Dictionary<int, int>(frogs.Length);
    // Все, кроме нулевой лягушки сделают как минимум 1 шаг
    for (int i = 1; i < frogs.Length; i++)
        steps[frogs[i]] = 1;
    // Нулевая лягушка всегда будет в нулевой клетке => ноль шагов
    steps[frogs[0]] = 0;
    // Это клетки нашего поля
    var field = new HashSet<int>(frogs.Length);
    for (int i = 0; i < frogs.Length; i++)
    {
        // Вычисляем вероятно доступную ячейку
        var cell = steps[frogs[i]] * frogs[i];
        // Если она все же недоступна
        while (field.Contains(cell))
        {
            // Прыгаем дальше
            cell += frogs[i];
            // Увеличиваем счетчик шагов для данного счастливого номера
            steps[frogs[i]]++;
        }
        // Занимаем ячейку
        field.Add(cell);
        // Увеличиваем счетчик шагов для следующей лягушки
        // с таким же счастливым числом
        steps[frogs[i]]++;
    }
    // Если бы можно было вернуть IEnumerable, а не int[],
    // то можно было бы еще выиграть немного времени
    return field.ToArray();
}

Answer 2

Кардинально другого алгоритма не придумал, но улучшил ваш:

int main()
{
     using large = long long;
     long count = 0;
     std::cin >> count;
     std::vector<large> cells;   // используем вектор заместо множества
     cells.reserve(count);       // зарезвируем память заранее
     if(count)
     {
         large n = 0;
         std::cin >> n;
         std::count << 0;
         cells.push_back(0); // первая лягушка всегда занимает клетку 0,
         --count;            // продолжим со второй
     }
     large number = 0;
     while(count--)
     {
         std::cin >> number;
         const auto end = std::end(cells);
         auto place = number;
         // вначале ищем по всему вектору от начала до конца
         auto cell  = std::lower_bound(std::begin(cells), end, place);
         while(cell != end && *cell == place)
         {
              place += number;
              // последующие ищем от текущего до конца, то есть
              // область поиска каждый раз сужается
              cell = std::lower_bound(cell, end, place);
         }
         // вставка без выделения памяти, ее сразу зарезервировали,
         // по стоимости как memmove будет
         cells.insert(cell, place); 
         std::cout << place;
     }
}