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

Question

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

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

Условие:

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

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

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

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

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

Пример 1

Ввод

1 1 10 2

Вывод

1

Пример 2

Ввод:

2 5 13 5

Вывод:

6

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

#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 тестах. Подскажите пожалуйста, как решить эту задачу?

c++олимпиада числа фибоначчи

Harry · Answer

#include using namespace std; pair 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; } }

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

One Answer

Add your own answers!

Ask a Question