Подразделы

Другие разделы

Дата и время

29/03/2024 03:25:29

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printРазбор задачи I. Гири

Тема: математика, задача на построение
Сложность: средняя

1. Гири можно разделить на три набора равного веса, если сумма весов гирь делится на 3, т.е. `(sum_{i=1}^n\ i)\ mod\ 3\ =\ {n*(n+1)}/2\ mod\ 3\ =\ 0`. Легко убедиться, что сумма делится на 3 для `n` равных `3*k` или `3*k+2` и не делится для `n` равных `3*k+1`.
2. Нельзя разделить на три набора менее 4 гирь.
3. Любую группу из 6 последовательных чисел `i+1,\ i+2,\ …,\ i+6` можно разделить на три набора равного веса `{i+1,i+6},{i+2,i+5},{i+3,i+4}`. Поэтому можно выделять из гирь подгруппы по 6 гирь, пока число гирь не станет равно 9 и меньше.
4. Набор из гирь 1,2,3,4,5 можно разделить так {1,4},{2,3},{5}. Набор из гирь 1,2,3,4,5,6 можно разделить так {1,6},{2,5},{3,4}. Набор из гирь 1,2,3,4,5,6,7,8 можно разделить так {4,8},{5,7},{1,2,3,6}. Набор из гирь 1,2,3,4,5,6,7,8,9 можно разделить так {7,8},{6,9},{1,2,3,4,5}.
loading