Олимпиадная задача про числа, состоящие из 2 и 5

Question

Может кто-то пожалуйста решить данное условие задачи?

Федя совсем недавно поступил в лучший вуз страны. В особенности ему стала интересна кафедра изучения счастливых чисел, то есть тех чисел, которые состоят только из цифр 2 и 5. Научные сотрудники этой кафедры исследуют их распределение. Они поняли, что существует последовательность всех счастливых чисел в порядке возрастания (2 - первое число, 5 - второе, 22 - третье и т.д.). Они хотят найти порядковый номер счастливого числа N в данной последовательности. Федю очень заинтересовала эта задача. Он думал над ней целый день, но так ни к чему и не пришел. Можете ли вы помочь Феде и кафедре счастливых чисел найти ответ?

Формат входных данных В данную задачу вам нужно отправить только ответ на этот тест:

Тест №1: N = 25;

Формат результата Для каждого теста требуется ввести в тестирующую систему одно целое число –- порядковый номер счастливого числа N в последовательности счастливых чисел.

Примечания Т.к. счастливое число 2 является первым числом последовательности счастливых чисел, то ответ на задачу при N = 2 равен 1. При N = 22, ответ равен 3. А например, т.к. число 255 является 10-ым членом последовательности, то при N = 255 ответ будет равен 10.

Мой текущий код

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <numeric>

using namespace std;

bool isValid (int number) {
    bool ans = true;
    for (const char& letter : to_string(number)) {
        if (!(letter == '5' || letter == '2')) {
            ans = false;
            break;
        }
    }
    return ans;
} 

// int skip_values (int number) {
//     string x = to_string(number);
//     if (x.at(0) == '2') {
//         x[0] = '5';
//     } else if (x.at(0) == '5') {
//         x = string(x.size() + 1, '2');
//     }
//     return stoi(x);
// }

int main () {
    int n;
    cin >> n;
    int ans = 0;

    int num = 0;

    bool stop = false;

    while (!stop) {
        ++num;
        if (isValid(num)) {
            ++ans; 
            cout << num << endl;
            if (num == n) {
                stop = true;
                break;
            }
        }
    }
    return 0;
}

Проблема в том, что код должен принимать очень большие значения, такие как 552222552555225252222555555522522555225255525252552222525255 . Заранее спасибо

Answer 1

Ладно, держите — для длин чисел до 63 цифр...

#include <string>
#include <iostream>
#include <iomanip>

using namespace std;

int main(int argc, char * argv[])
{
    string s;
    cin >> s;
    unsigned long long N = s.size();
    unsigned long long p = (1ull << N) - 2;
    unsigned long long L = (1ull << N);
    for(char c: s)
    {
        if (c == '5') p += L/2;
        L /= 2;
    }
    cout << p+1 << endl;
}

Answer 2

Не надо перебирать числа и считать среди них счастливые. По виду счастливого числа (строке, которая его изображает) можно вычислить его номер.

Например, все счастливые числа до 52:

Счастливое число 52 идёт под номером 5. Под каким номером идёт число 525? Чур, не считать!

Номер будет 12. К каждому числу в предыдущей таблице припишите справа двойку и пятерку:

1:  2 ->  22  25
2:  5 ->  52  55
3: 22 -> 222 225
4: 25 -> 252 255
5: 52 -> 522 525

Чисел справа от стрелочек в два раза больше чем слева. Это все счастливые числа до 525 кроме 2 и 5. Добавим их 12 = 2 * 5 + 2.

Если какое-то счастливое число X...X имеет номер N, то число X...X5 будет иметь номер 2N + 2.

Соответственно число X...X2 получит номер на единицу меньше: 2N + 1.

Пустому счастливому числу припишем номер 0. Читаем цифры числа по одной, предыдущий номер умножаем на два и добавляем 1 или 2 в зависимости от новой цифры.

Номер накапливается в переменной 64 бита, этого хватит на самый длинный из примеров.

#include <iostream>
#include <string>

int main() {
    std::string s;
    std::cin >> s;
    unsigned long long n = 0;
    for (const auto &c : s) {
        n = 2 * n + ((c == '5') ? 2 : 1);
    }
    std::cout << n << '\n';
}

$ g++ -std=c++17 -pedantic -Wall -Wextra -Werror happy-numbers.cpp

$ echo 2 | ./a.out 
1

$ echo 22 | ./a.out 
3

$ echo 255 | ./a.out 
10

$ echo 552222552555225252222555555522522555225255525252552222525255 | ./a.out
2033138283364396074

БЛОГ НА HUSL

Олимпиадная задача про числа, состоящие из 2 и 5

Ответы (2 шт):