Олимпиадная задача. Монетки

349

12 мая 2022, 12:10

Ограничение времени 1 секунда

Ограничение памяти 512Mb

Условие:

Как всем хорошо известно, дядюшка Скрудж очень богат. Все свое свободное время он проводит со своими золотыми монетам. Сегодня он решил сложить их в столбики, используя следующий алгоритм: первый столбик имеет высоту А, а второй - В. Высота каждого нового столбца должна равняться сумме высот двух последних построенных. Если высота столбика превышает С, то он убирает из нее С монет.

Определите, какой высоты будет К-ый столбик.

Формат ввода Заданы четыре целых числа A, B, C, K

(0 ≤ A, B ≤ 1000000000; 1 ≤ C, K ≤ 1000000000; A < C; B < C).

Формат вывода Выведите одно число - количество монет в K-ом столбике.

Пример 1

Ввод

1 1 10 2

Вывод

Пример 2

Ввод:

2 5 13 5

Вывод:

Моя попытка решения:

#include <iostream>
using namespace std;
long long a, b, c, k, n, l1, l2;
int main() {
    cin >> a >> b >> c >> k;
    if (k == 1) {
        cout << a;
    }
    else if (k == 2) {
        cout << b;
    }
    else {
        l1 = a;
        l2 = b;
        for (long long i = 3; i <= k; i++) {
            n = l1 + l2;
            if (n > c)
                n -= c;
            l1 = l2;
            l2 = n;
        }
        cout << n;
    }
    return 0;
}

Хотел просто перебрать, но не проходит по времени на 6 тестах. Подскажите пожалуйста, как решить эту задачу?

Answer 1

#include <iostream>
using namespace std;
pair<unsigned long long, unsigned long long> fib(unsigned long long N,
                                                 unsigned long long A,
                                                 unsigned long long B,
                                                 unsigned long long C)
{
    unsigned long long a[2][2] = {{1,1},{1,0}};
    unsigned long long r[2][2] = {{1,0},{0,1}};
    while(N)
    {
        unsigned long long b[2][2];
        if (N&1) {
            b[0][0] = a[0][0]*r[0][0] + a[0][1]*r[1][0];
            b[0][1] = a[0][0]*r[0][1] + a[0][1]*r[1][1];
            b[1][0] = a[1][0]*r[0][0] + a[1][1]*r[1][0];
            b[1][1] = a[1][0]*r[0][1] + a[1][1]*r[1][1];
            r[0][0] = b[0][0]%C;
            r[0][1] = b[0][1]%C;
            r[1][0] = b[1][0]%C;
            r[1][1] = b[1][1]%C;
        }
        N >>= 1;
        b[0][0] = a[0][0]*a[0][0] + a[0][1]*a[1][0];
        b[0][1] = a[0][0]*a[0][1] + a[0][1]*a[1][1];
        b[1][0] = a[1][0]*a[0][0] + a[1][1]*a[1][0];
        b[1][1] = a[1][0]*a[0][1] + a[1][1]*a[1][1];
        a[0][0] = b[0][0]%C;
        a[0][1] = b[0][1]%C;
        a[1][0] = b[1][0]%C;
        a[1][1] = b[1][1]%C;
    }
    return make_pair(r[0][0]*B + r[0][1]*A,r[1][0]*B+r[1][1]*A);
}
int main()
{
    unsigned long long A, B, C, K;
    cin >> A >> B >> C >> K;
    if (K == 1) cout << A << "\n";
    else if (K == 2) cout << B << "\n";
    else if (A == 0 && B == 0) cout << B << "\n";
    else
    {
        auto p = fib(K-2,A,B,C);
        A = p.first%C;
        if (A == 0) A = C;
        cout << A << endl;
    }
}

ПОСЛЕДНИЕ ВОПРОСЫ

Все вопросы

ТОП-10

Все популярные вопросы

Как возможно ускорить алгоритм?

Написал программу, которaя в маcсиве из n целых чиcел наимeньший элeмент поставит на первое место, наименьший из оcтавшихся - на пoследнее, следующий...

267

c++

Преобразить цикл в рекурсию С++

Всем доброго времени сутокЯ студентка 1 курса, преподаватель по программированию дал интересное задание: создать калькулятор комплексных...

251

c++

Как найти проекцию точки на окружность?

324

c++

Как вычислить сумму бесконечного ряда?

Пусть дан бесконечный ряд,найти его суммуВот что я написал сам:

287