Question

У Саши есть красивая веревочка длины 1006 см, завязанная в кольцо. Для новогодних поделок ему нужно много обрезков этой веревочки. Поэтому он взял ножницы и стал веревочку резать. Саша хочет сделать как можно меньше разрезов и получить части только длины 1, 2 или 3 см, при этом, чтобы была хотя бы одна часть длины 1 см, хотя бы одна часть длины 2 см и хотя бы одна часть длины 3 см. Какое наименьшее количество разрезов ему нужно сделать? Комментарий. Для веревочки с длиной 6 наименьшее количество разрезов равно трем.

Answer 1

5 разрезов ну почему обязательно 20 символов? ну с начала отрезаешь и конец вот те 1 см потом так же вот те 2 см и 3 см тоже так


                                                                          

 

Answer 2

Для начала, заметим, что если мы имеем части длины $a$ и $b$, то мы можем получить часть длины $a+b$ и часть длины $|a-b|$.

Давайте теперь разделим веревочку на три части: $x$, $y$ и $z$, такие что $x+y+z=1006$. Мы хотим минимизировать количество разрезов, чтобы получить обрезки длины 1, 2 или 3 см. Для этого мы должны сделать как можно больше обрезков длины 3 см и как можно меньше обрезков длины 1 см и длины 2 см. Заметим, что если у нас есть часть длины 2 см, мы можем разрезать ее на две части длины 1 см.

Поэтому, мы можем разделить веревочку на три части таким образом:

• $z$ должна быть равна 1 или 2 см.
• Если $z=1$, то $y$ должна быть равна 1 или 2 см, и $x$ должна быть равна 1003 или 1004 см.
• Если $z=2$, то $y$ должна быть равна 1 см, и $x$ должна быть равна 1003 или 1004 см.

Таким образом, мы можем получить наименьшее количество обрезков следующим образом:

• Если $z=1$ и $y=1$, то нам нужно разрезать $x$ на обрезки длины 3 см, пока не останется часть длиной 1 или 2 см, что потребует $\left\lceil\frac{x-1}{3}\right\rceil$ разрезов.
• Если $z=1$ и $y=2$, то нам нужно разрезать $x$ на обрезки длины 3 см, пока не останется часть длиной 1 см, что потребует $\left\lceil\frac{x-2}{3}\right\rceil$ разрезов.
• Если $z=2$, то нам нужно разрезать $x$ на обрезки длины 3 см, пока не останется часть длиной 2 см, что потребует $\left\lceil\frac{x-2}{3}\right\rceil$ разрезов.

Таким образом, наименьшее количество разрезов будет равно $\min{\left\lceil\frac{x-1}{3}\right\rceil+\left\lceil\frac{y}{3}\right\rceil+\left\lceil\frac{z-1}{3}\right\rceil, \left\lceil\frac{x-2}{3}\right\rceil+\left\lceil\frac{y-1}{3}\right\rceil+\left\lceil\frac{z}{3}\right\rceil}$.

Тепер