Даю много баллов, только с полным объяснением Дана клетчатая фигура в виде лестницы,...

0 голосов
95 просмотров

Даю много баллов, только с полным объяснением
Дана клетчатая фигура в виде лестницы, содержащей n ступенек (на рисунке приведён пример для n=11).Сколько значений n, удовлетворяющих неравенству 300image


Информатика (59 баллов) | 95 просмотров
0

задайте этот вопрос когда закончится актуальная олимпиада фоксфорд

0

Там не перебор 100%

Дан 1 ответ
0 голосов

1) Методом перебора определяем, что на уголки можно разрезать треугольники со стороной 2, 6, 8, 9, и 11. Треугольники со сторонами 3 и 5 разрезать не получится.
2) Замечаем, что из двух уголков можно составить прямоугольник 2*3 (назовем его "универсальный кирпичик"), а из 12 уголков - квадрат 6*6.
3) Теперь мы можем разрезать большую фигуру на квадраты 6*6 и треугольники со стороной 6. В остатке будут "полоски" шириной n и высотой 1, 2, 3, 4, 5.
4) Замечаем, что из универсальных кирпичиков - прямоугольников 2*3 можно составить такие фигуры, как 6*11 (6+3+2), 6*9 (6+3), 6*2 (2 кирпичика, лежащих горизонтально).
5) Итак, чтобы разрезать большую фигуру на уголки, мы разрезаем ее сверху вниз на квадраты и треугольники со стороной 6, пока не порежем всю фигуру, либо получим в остатке полоску высотой 2, 9, или 11 и шириной n.
6) Из шага (1) нам известно, что треугольники размером a = 2, 9 и 11 можно порезать на уголки. После этого останется полоска размером (n - a)*a, но (n - a) делится на 6, поэтому мы можем порезать ее на прямоугольники 2*3, как следует из шага 4.
7) Конечно, фигуру можно разрезать на уголки только тогда, когда число ее клеток кратно 3.

uses math;

var i: integer;
var s: integer;
var y: integer;
var n: integer;

begin
        y := 0;
        n := 0;

        for i := 301 to 699 do begin
                { число клеток (сумма арифметической прогрессии) кратно 3 }
                if i * (i + 1) mod 6 = 0 then begin
                        s := i;
                        while s > 0 do begin
                                if (s = 0) or (s = 2) or (s = 9) or (s = 11) then begin
                                        y := y + 1;
                                        break
                                end else begin
                                        { никогда не выполняется }
                                        if s < 6 then begin
                                                n := n + 1;
                                        end;
                                end;
                                s := s - 6;
                        end;
                end;
        end;

        writeln();
        writeln('yes: ', y);
        writeln('no: ', n);
end.


Ответ: 200.


(9.2k баллов)
0

Кому не понравилось решение? Вот еще более подробное: https://znanija.com/task/27210656