Ограничение времени 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 тестах. Подскажите пожалуйста, как решить эту задачу?
#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;
}
}
Написал программу, которaя в маcсиве из n целых чиcел наимeньший элeмент поставит на первое место, наименьший из оcтавшихся - на пoследнее, следующий...
Всем доброго времени сутокЯ студентка 1 курса, преподаватель по программированию дал интересное задание: создать калькулятор комплексных...
Пусть дан бесконечный ряд,найти его суммуВот что я написал сам: