TransWikia.com

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

Stack Overflow на русском Asked by asdfjsldfksjdsdjklas on February 2, 2021

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

One Answer

#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;
    }
}

Answered by Harry on February 2, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP