Проблемы с типом данных, слишком маленький

Question

Проблемы с типом данных, слишком маленький

Рейтинг: -3Ответов: 1Опубликовано: 21.02.2023

Имеется калькулятор, который выполняет три операции:

Прибавить к числу X единицу. Умножить число X на 2. Умножить число X на 3. Определите кратчайшую последовательность операций, необходимую для получения из числа 1 заданное число N.

Входные данные Программа получает на вход одно число N, не превосходящее 106.

Выходные данные Выведите строку, состоящую из цифр "1", "2" или "3", обозначающих одну из трех указанных операций, которая получает из числа 1 число N за минимальное число операций. Если возможных минимальных решений несколько, выведите любое из них.

Ввод: 562340

вывод: 3333312222122213312

На этом тесте он ломается

Ввод: 1

вывод:

Ввод: 5

вывод: 121

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main()
{
    string s;

    vector <unsigned long long int> vec = { 1000000000000000000, 0, 1, 1 };
    vector <unsigned long long int> a = { 1000000000000000000, 0, 1, 1 };
    unsigned long long int p = 0;
    unsigned long long int  v = 0;
    unsigned long long int  t = 0;
    unsigned long long int  n = 0;
    unsigned long long int  c = 0;
    unsigned long long int  u = 0;
    cin >> n;


    for (int i = 4; i <= n; ++i) {
        p = 0;
        v = 0;
        t = 0;
        if (i % 3 == 0) { p = i / 3; }
        if (i % 2 == 0) { v = i / 2; }
        t = (i - 1);

        c = min(min(vec[p], vec[v]), vec[t]);
        //ищем что в с
        if (c == vec[p]) { u = p; }
        else if (c == vec[v]) { u = v; }
        else { u = t; }

        s += to_string(a[u]);

        //понимаем какую операцию сделали
        if ((i / 3) == u) { s += '3'; }
        if ((i / 2) == u) { s += '2'; }
        if ((i - 1) == u) { s += '1'; }

        c++;
        vec.push_back(c);
        a.push_back(stoll(s));
        s.clear();

    }
    cout << vec[n] << endl;
    cout << a[n];

    return 0;
}

c# алгоритм олимпиада

Источник: Stack Overflow на русском

Answer 1

▲ 2Принят

А ведь вашу задачу очень просто решить методом поиска в ширину, надо только идти от N к 1. Так даже удобнее: не надо потом путь строить с использованием стека.

#include <vector>
#include <iostream>
#include <iomanip>
#include <queue>
#include <stack>
#include <set>

using namespace std;

struct Node
{
    Node(int i, int p = -1):idx(i),prev(p){}
    int idx;   // Индекс
    int prev;  // Предыдущий узел - для восстановления пути
    bool operator <(const Node& n) const { return idx < n.idx; }
};

int main()
{
    int start = 1, stop = 1;

    cin >> start;

    queue<Node> Q;   // Очередь BFS
    set<Node> S;     // Множество уже обработанных узлов

    Q.push(Node(start));
    while(!Q.empty())
    {
        S.insert(Q.front());        // Внесли в обработанные
        int index = Q.front().idx;  // Индекс
        if (index == stop) break;   // Найден!
        Q.pop();                    // Убираем из очереди
        vector<int> next;           // Возможные варианты
        if (index%3 == 0) next.push_back(index/3);
        if (index%2 == 0) next.push_back(index/2);
        if (index > 1) next.push_back(index-1);
        for(int i: next)            // Обработка возможных вариантов
        {
            Node n(i,index);
            if (S.find(n) != S.end()) continue;  // Уже отработан
            Q.push(n);              // Внесение в очередь еще не рассмотренных
        }
    }

    // Вывод цепочки - так как в обратном порядке, используем стек

    int last = Q.front().idx;
    auto i = S.find(Node(last));

    for(int index = i->prev; index != -1; )
    {
        if (index == last * 3) cout << 3; else
        if (index == last * 2) cout << 2; else cout << 1;
        last = index;
        i = S.find(Node(index));    // Поиск предыдущего
        if (i == S.end()) break;         // Береженого Бог бережет :)
        index = i->prev;                 // Предыдущий в цепочке
    }
}

Заметим, что хоть ответ и отличается от указанного, он имеет ту же длину и дает то же число. Просто к одной цели могут вести разные пути...

P.S. И зачем тут unsigned long long?...

Проблемы с типом данных, слишком маленький

Ответы