Бесконечная последовательность

@iama · Регистрация: 30.07.2010

Студворк — интернет-сервис помощи студентам

Задача

Моё решение на плюсах

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <map>
 
using namespace std;
 
long long p, q, x, y;
map <long long, long long> pc;
 
long long f(long long n)
{
    if (n < 1)
        return 1;
    else
    {
        long long a = n / p - x, b = n / q - y;
 
        if (!pc[a])
            pc[a] = f(a);
 
        if (!pc[b])
            pc[b] = f(b);
 
        pc[n] = pc[a] + pc[b];
 
        return pc[n];
    }
}
 
int main()
{
    long long n;
 
    cin >> n >> p >> q >> x >> y;
 
    cout << f(n) << endl;
 
    return 0;
}

Есть подозрения, что при каком-то наборе данных алгоритм зацикливается (но не должно же - чем глубже рекурсия, тем меньший элемент последовательности ищется, вроде всегда так), пробовал крайние значения - работает в доли секунды.

Помогите, люди добрые!

Или хоть контрпример подскажите...

@grizlik78 · 03.08.2011, 14:01

Сообщение от BAIZOR

То на ТопКодере она может пройти, а на Кодфорсесе нет?

Вполне. Поэтому тайм-лимиты на этих серверах могут быть разными.

@BAIZOR · 03.08.2011, 14:02

Сообщение от grizlik78

Вполне. Поэтому тайм-лимиты на этих серверах могут быть разными.

ну ладно, я не люблю спорить. И на 100% я не знаю, но я очень сомневаюсь в Вашей правоте.

@iama · 03.08.2011, 14:03 **[ТС]**

Сообщение от Хохол

Думаю вы уже поняли что оценка неверна.

Она верна только для x = y = 0

Сообщение от BAIZOR

Или если на одном сервере стоит процессор более мощьный чем на другом, то на мощьном сервере решение пройдет, а на слабом нет?

Могу выложить исходник, который проходит тут и не проходит тут. При одинаковых тестах и условии.

Сообщение от grizlik78

Если внимательно посмотреть, то на всех таких серверах тестовые задания выстраиваются в очередь.

Пруф

Сообщение от Хохол

И хватит гнать на хешмапу, она классная, прочитайте сначала литературу.

Но она только в C++0x. А жаль. Прийдется сохранять значения только для значений, меньших какого-то предела, сколько памяти хватит

@BAIZOR · 03.08.2011, 14:10

Сообщение от iama

Могу выложить исходник, который проходит тут и не проходит тут. При одинаковых тестах и условии.

почти убедили

А вдруг это какието старые версии контестных серверов?)
Мне уже аж интересно стало, пойду в гугл копать...

@Хохол · 03.08.2011, 14:18

Если проблема в количестве вызовов порядка 5 млн, хешмапа может помочь.
Напишите уже её руками.
Кстати если у них vs 2008, хешмапа находится в namespace stdext.

@iama · 03.08.2011, 14:23 **[ТС]**

Я сдал!
На пределе, между прочим.

Мое решение (страшный быдлокод)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h>
 
#define MAX_N 14000000
 
long long p, q, x, y;
int ar[MAX_N];
 
long long f(long long n)
{
    if (n < 1)
        return 1;
    else
    {
      if (n < MAX_N && ar[n])
      return ar[n];
 
    long long a = n / p - x, b = n / q - y, ax, bx;
 
    if (a < 1)
      ax = 1;
    else if (a < MAX_N && ar[a])
      ax = ar[a];
    else
    {
      ax = f(a);
      if (a < MAX_N)
        ar[a] = ax;
    }
 
    if (b < 1)
      bx = 1;
    else if (b < MAX_N && ar[b])
      bx = ar[b];
    else
    {
      bx = f(b);
      if (b < MAX_N)
        ar[b] = bx;
    }
 
    return ax + bx;
    }
}
 
int main()
{
    long long n;
 
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
 
    scanf("%I64d %I64d %I64d %I64d %I64d", &n, &p, &q, &x, &y);
    printf("%I64d\n", f(n));
 
    return 0;
}

Еле-еле вписался. Сделал статический массив, хранил значения только для таких i, что меньше определенного значения, в мапе на примере от grizlik78 хранились соответствия для всех чисел от 1 до 1000, вот и решил сделать тупо через статический массив.

Смущает другое - на этом же сайте люди с 5 мб памяти сдают... Но это ладно...

Огромное всем человеческое спасибо!

Добавлено через 2 минуты

Сообщение от BAIZOR

А вдруг это какието старые версии контестных серверов?)

Не, там просто сервер трухлявый, маломощный

Сообщение от Хохол

Кстати если у них vs 2008, хешмапа находится в namespace stdext.

Дак не компилило у них на серве с ней, представляете? Я ж сам в шоке, вроде должна быть. Вы же hash_map имеете в виду?

@grizlik78 · 03.08.2011, 14:54

У меня была похожая идея, только я решил честно вычислять первые значения.
Меняя параметр THRESHOLD можно обменивать время начальной инициализации и размер вектора на количество вставок в мапу и, соответственно, время вычисления самой функции.
Собственно

код

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <map>
#include <vector>
#include <cstdlib>
 
using namespace std;
 
long long p, q, x, y;
map <long long, long long> pc;
vector<int> first_nums;
int const THRESHOLD = 5000000;
 
void finit()
{
    first_nums.resize(THRESHOLD);
    first_nums[0] = 1;
    for (int num = 1; num < THRESHOLD; ++num)
    {
        int a = max<long long>(0, num / p - x), b = max<long long>(0, num / q - y);
        first_nums[num] = first_nums[a] + first_nums[b];
    }
}
 
long long f(long long n)
{
    if (n < 0)
        return 1;
    long long res = 1;
    if (n < THRESHOLD)
        res = first_nums[n];
    else if (!(res = pc[n]))
    {
        long long a = max<long long>(0, n / p - x), b = max<long long>(0, n / q - y), fa = 1, fb = 1;
 
        if (a < THRESHOLD)
            fa = first_nums[a];
        else if (!(fa = pc[a]))
            fa = pc[a] = f(a);
 
        if (b < THRESHOLD)
            fb = first_nums[b];
        else if (!(fb = pc[b]))
            fb = pc[b] = f(b);
 
        res = pc[n] = fa + fb;
    }
    return res;
}
 
int main()
{
        long long n;
 
        cin >> n >> p >> q >> x >> y;
        
        finit();
 
        cout << f(n) << endl;
 
        return 0;
}

.

@Mr.X · 07.08.2011, 15:12

А если так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
/////////////////////////////////////////////////////////////////////////////////////////
typedef long long  T_num;
/////////////////////////////////////////////////////////////////////////////////////////
T_num  res  = 0;
 
T_num  p    = 0;
T_num  q    = 0;
T_num  x    = 0;
T_num  y    = 0;
/////////////////////////////////////////////////////////////////////////////////////////
void  A(T_num  i)
{    
    if(i <= 0)
    {
        ++res;
    }
    else
    {
        A(i / p - x);
        A(i / q - y);        
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::cout << "n = "; 
    T_num  n = 0;
    std::cin >> n;
 
    std::cout << "p = ";
    std::cin >> p;
 
    std::cout << "q = ";
    std::cin >> q;
 
    std::cout << "x = ";
    std::cin >> x;
 
    std::cout << "y = ";
    std::cin >> y;
    
    A(n);
 
    std::cout << "res = "
              << res
              << std::endl;
}

@iama · 07.08.2011, 17:39 **[ТС]**

Mr.X, мы уже пробовали простой рекурсией, при больших N и малых P и Q не проходит

@Mr.X · 07.08.2011, 19:40

Сообщение от iama

Mr.X, мы уже пробовали простой рекурсией, при больших N и малых P и Q не проходит

Ну дак здесь же не надо ждать возвращаемых значений, поэтому должно работать быстрее.

@grizlik78 · 07.08.2011, 20:05

Сообщение от Mr.X

Ну дак здесь же не надо ждать возвращаемых значений, поэтому должно работать быстрее.

Да, но вызовов функции при этом будет недопустимо много, из-за того, что будут вычисляться давно уже посчитанные значения, которые, в свою очередь, для вычисления сами требуют многократного вызова функции.
Даже для значений
1000000000 2 2 0 0
результата ждать придётся очень долго, хотя реально надо вычислить всего 3 десятка значений.

Добавлено через 10 минут
Сравните:
Ваш вариант

$ echo 1000000000 2 2 0 0 | /usr/bin/time ./a.out
n = p = q = x = y = res = 1073741824
160.84user 0.02system 2:40.98elapsed 99%CPU (0avgtext+0avgdata 3696maxresident)k
0inputs+0outputs (0major+289minor)pagefaults 0swaps

Вариант из первого поста

$ echo 1000000000 2 2 0 0 | /usr/bin/time ./a.out
1073741824
0.00user 0.00system 0:00.00elapsed 0%CPU (0avgtext+0avgdata 3920maxresident)k
0inputs+0outputs (0major+303minor)pagefaults 0swaps

Почти 3 минуты против 0 секунд

Это на нетбуке. На десктопе побыстрее будет, конечно, но всё же.

Новые блоги и статьи Все статьи Все блоги /
Асинхронный приём данных из COM-порта Argus19 01.05.2026 Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .	попытка написать игровой сервер на C++ pyirrlicht 29.04.2026 попытка написать игровой сервер на плюсах с открытым бесконечным миром. возможно получится прикрутить интерпретатор питон для кастомизации игровой логики. что есть на текущий момент:. . .	Контроль уникальности выбранного документа-основания при изменении реквизита Maks 28.04.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРемонтСпецтехники", разработанного в КА2. Задача: уведомлять пользователя, если указанная заявка (документ-основание). . .	Благородство как наказание Maks 24.04.2026 У хорошего человека отношения с женщинами всегда складываются трудно. А я человек хороший. Заявляю без тени смущения, потому что гордиться тут нечем. От хорошего человека ждут соответствующего. . .
Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	03.08.2011, 14:18
	Если проблема в количестве вызовов порядка 5 млн, хешмапа может помочь. Напишите уже её руками. Кстати если у них vs 2008, хешмапа находится в namespace stdext. 1

@iama 1360 / 988 / 119 Регистрация: 30.07.2010 Сообщений: 5,297
	07.08.2011, 17:39 [ТС]
	Mr.X, мы уже пробовали простой рекурсией, при больших N и малых P и Q не проходит 0