Задача Рыбаки для C++ Врема 1 секунда

Question

Задача Рыбаки для C++ Врема 1 секунда

Hayk Babayan Ученик (95), открыт 21 час назад

Решите пожалуйста задачу
Однажды N рыбаков отправились на рыбалку, где поймали X рыб. После этого рыбаки легли спать. Утром, просыпаясь друг за другом, каждый из них делил выловленную рыбу на N частей. Каждый раз в остатке оставалось ровно K рыб (0 < K < N). Эти K рыб выбрасывались обратно в море. Рыбак забирал свою часть улова и отбывал домой, не зная ничего о том, поступал ли уже кто-либо из остальных рыбаков таким же образом.

Ваша задача – определите при заданных N и K минимально возможное целое положительное значение X – число рыб, удовлетворяющее условию задачи.

Входные данные
Входной файл INPUT.TXT содержит два целых числа N и K, разделенные пробелом (2 ≤ N ≤ 15, 0 < K < N).

Выходные данные
Выходной файл OUTPUT.TXT должен содержать одно целое положительное число X – наименьшее возможное количество выловленной рыбаками рыбы

Answer 1

Папа Высший разум (150918) 20 часов назад

Если последний рыбак получил ненулевое число рыб, то так:

 #include <iostream>
#include <cstdint>

using namespace std;

int main() {
    uint n, k;
    cin >> n >> k;
    uint64_t x = 1;
    for (uint i = 0; i < n; i++)
        x = x * n + k;
    cout << x << endl;
    return 0;
}

А если допустимо, чтобы последнему досталось 0, то x инициализируй нулём, а не 1.

P.S. Забавно получится, если ввести 15 14. Даже не знаю, физический найдётся ли такое количество рыб на планете (875787780761718749)...

ПапаВысший разум (150918) 19 часов назад

Хотя нет. На самом деле решать надо так, и тогда числа выйдут небольшие:

 #include <iostream> 
#include <cstdint> 
 
using namespace std;

int main() {
    uint n, k;
    cin >> n >> k;
    const uint m = n - 1;
    uint = 1;
    for (uint i = 0; i < n; i++) {
        const uint y = (x + k + m - 1) / m;
        x = y * n + k;
    }
    cout << x << endl;
    return 0;
}

Следующий рыбак же делит N-1 доль, а не 1.

ПапаВысший разум (150918) 19 часов назад

Поправка:

 #include <iostream>
#include <cstdint>

using namespace std;

int main() {
    uint n, k;
    cin >> n >> k;
    const uint m = n - 1;
    uint x = 1;
    for (uint i = 0; i < n; i++) {
        const uint y = (x + k + m - 1) / m;
        x = y * n + k;
    }
    cout << x << endl;
    return 0;
}

ПапаВысший разум (150918) 19 часов назад

Хотя всё равно всё это с ошибкой. Вот так должно быть норм:

 #include <iostream>
#include <cstdint>
#include <numeric>

using namespace std;

int main() {
    uint n, k;
    cin >> n >> k;
    const uint m = n - 1;
    uint x = n - 1;
    for (uint i = 0; i < n; i++) {
        const uint l = lcm(m, x - k) + k;
        x = l * n / m + k;
    }
    cout << x << endl;
    return 0;
}

И для 15 14 выведет 246 млн рыб, столько найдётся, конечно, но ловить придётся долго.

Hayk Babayan Ученик (95) Папа, При вводе переменных 3 и 1, вывод должен получится 25 по примерам самой задачи