Question

Задача 1: Костяные войны Марш и Коп — всемирно известная пара враждующих археологов. В стремлении обогнать друг друга они собрали внушительные коллекции костей динозавров, представляющих собой отрезки целочисленной длины. И у Марша, и у Копа имеется ровно две кости длины 1, ровно две кости длины 2 и так до бесконечности (то есть, у каждого есть ровно две кости любой натуральной длины). Однажды археологи решили примириться и в честь этого отдать в Смитсоновский музей прямоугольник периметра P. Для этого и Марш, и Коп хотят пожертвовать на строительство прямоугольника по одной паре одинаковых костей. Каким числом способов они могут это сделать, если ломать кости археологи категорически не согласны? Входные данные Программа получает на вход одно натуральное число P — периметр требуемого прямоугольника (1 ≤ P ≤ 2×109 ). Выходные данные Программа должна вывести одно целое число — количество способов пожертвовать кости, чтобы из них можно было составить прямоугольник периметра P. Система оценки Решение, правильно работающее для P ≤1000, наберёт не менее 60 баллов. Примеры Ввод Вывод Пояснение 10 4 Марш и Коп могут пожертвовать соответственно кости длины 1 и 4; 2 и 3; 3 и 2; 4 и 1 — всего 4 способа. Заметим, что из них сложатся прямоугольники 1×4, 2×3, 3×2 и 4×1 соответственно. 2 0 Несложно понять, что невозможно составить даже один прямоугольник, удовлетворяющий условиям задачи, поэтому ответ ноль

Answer 1

Ответ:

язык pascal abc, 100 баллов

Объяснение:

var P:integer;

begin

 Readln(P);

 if (P mod 2 = 0) and (P>2) then  

 writeln(P/2-1)

 else Writeln (0)

end.

Answer 2

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

Для решения задачи мы можем создать двумерный массив dp, где dp[i][j] будет обозначать количество способов составить прямоугольник периметра j с использованием первых i пар костей. Здесь i может принимать значения от 0 до бесконечности, а j от 0 до P.

Инициализируем массив dp нулями для всех значений. Далее, мы можем использовать рекуррентное соотношение для заполнения массива dp.

Если i = 0, то dp[0][j] = 0 для всех j > 0, так как у нас нет костей для использования.

Если j = 0, то dp[i][0] = 1 для всех i, так как мы всегда можем составить прямоугольник с периметром 0 из нулевых костей.

Для остальных значений i и j мы можем использовать следующее рекуррентное соотношение:

dp[i][j] = dp[i-1][j] + dp[i-1][j-2*i],

где dp[i-1][j] представляет собой количество способов, которыми мы можем составить прямоугольник периметра j без использования текущей пары костей длины 2*i, а dp[i-1][j-2*i] представляет количество способов, которыми мы можем составить прямоугольник периметра j с использованием текущей пары костей длины 2*i.

После заполнения массива dp, значение dp[i][P] будет представлять количество способов, которыми Марш и Коп могут пожертвовать кости, чтобы составить прямоугольник периметра P.

Вот пример кода на языке Python, реализующий описанное решение:

pythonCopy code
def count_rectangles(P):
    dp = [[0] * (P + 1) for _ in range(201)]
    dp[0][0] = 1

    for i in range(1, 201):
        for j in range(P + 1):
            dp[i][j] = dp[i-1][j]
            if j >= 2 * i:
                dp[i][j] += dp[i-1][j-2*i]

    return dp[200][P]

P = int(input())
result = count_rectangles(P)
print(result)

Это решение имеет временную сложность O(P), что позволяет его эффективно работать для P ≤ 2000. Однако, чтобы решить задачу для P ≤ 2×10^9, тр