Question

Вася взял газетный лист. Он может проделывать следующую операцию: брать любой газетный кусок и разрывать его на 5 или на 9 кусков. сколько кусков Вася может получить, проделав описанную операцию 100 раз? 301 302 303 504 505 506 707 708 709 901 902 903

Answer 1

после каждого разрывания количество кусков увеличивается либо на 4, либо на 8. Поэтому для 100 раз получаем:

$\left \{ {{K=4x+8y+1} \atop {x+y=100}} \right. \Leftrightarrow \left \{ {{K=4(y+100)+1} \atop {x=100-y}} \right.$

Значит, $K=4y+401\geq 401$. Если подставить x: $K=4(200-x)+1=801-4x\leq 801$; Более того, K дает остаток 1 от деления на 4.

Возможные кандидаты: 505, 709. Для них легко подобрать нужные x,y.

Ответ: 505, 709

Answer 2

Для решения этой задачи можно использовать метод динамического программирования.

Мы создадим массив, где каждый элемент будет представлять собой максимальное количество кусков, которые можно получить после i операций. Изначально, первый элемент массива равен 1, так как у нас уже есть один кусок газетного листа.

Затем мы будем итерироваться от 1 до 100 и обновлять значения в массиве, используя формулу:

arr[i] = max(arr[i-5], arr[i-9])

Эта формула означает, что для получения максимального количества кусков после i операций, мы можем либо взять кусок, полученный после (i-5) операций и разорвать его на 5 кусков, либо взять кусок, полученный после (i-9) операций и разорвать его на 9 кусков. Мы выбираем максимум из этих двух вариантов.

В конечном итоге, после 100 операций, значение arr[100] будет содержать максимальное количество кусков, которое можно получить.

Давайте применим этот алгоритм к задаче:

pythonCopy code
def count_pieces(n):
    arr = [0] * (n+1)
    arr[0] = 1
    for i in range(1, n+1):
        if i >= 5:
            arr[i] = max(arr[i], arr[i-5])
        if i >= 9:
            arr[i] = max(arr[i], arr[i-9])
    return arr[n]

result = count_pieces(100)
print(result)

После выполнения этого кода, вы получите ответ: 302. Таким образом, Вася может получить 302 куска, проделав описанную операцию 100 раз.