Даны две последовательности из букв А и Б, в каждой из которых по 100 букв. За одну операцию разрешается вставить в какое-то место последовательности (возможно, в начало или в конец) одну или несколько одинаковых букв или убрать из последовательности одну или несколько подряд идущих одинаковых букв. Докажите, что из первой последовательности можно получить вторую не более чем за 100 операций.

   Решение

В лесном пункте обмена можно обменять
• апельсин — на две груши,
• яблоко и грушу — на апельсин,
• апельсин и грушу — на яблоко.
По случаю праздника в пункте устроили акцию: за каждый обмен в подарок выдают коллекционный фантик. У лисы есть 30 яблок, 30 груш и 30 апельсинов. Какое максимальное количество фантиков она может получить?

   Решение

Темы:    [ Теория алгоритмов (прочее) ] [ Четность и нечетность ]

Сложность: 4 Классы: 9,10,11

Прислать комментарий

Условие

Дано n целых чисел  a₁ = 1,  a₂, a₃, ..., a_n, причём   a_i ≤ a_i+1 ≤ 2a_i  (i = 1, 2,..., n – 1)  и сумма всех чисел чётна. Можно ли эти числа разбить на две группы так, чтобы суммы чисел в этих группах были равны?

Решение

  Отнесём к одной группе число a_n, а к другой – число a_n–1. Затем будем последовательно относить числа a_n–2, a_n–3, ..., a₁ к той группе, в которой сумма чисел меньше (если суммы равные, то число можно относить к любой группе). Пусть  Δ_k ≥ 0  – разность между суммами чисел в группах, полученных после отнесения к ним a_k. Покажем, что  Δ_k ≤ a_k.
  Действительно,  Δ_n–1 = a_n – a_n–1 ≤ 2a_n–1 – a_n–1 = a_n–1.  Ясно также, что если  Δ_k ≤ a_k,  то  Δ_k–1 = |Δ_k–1 – a_k–1|  и  – a_k–1 ≤ Δ_k – a_k–1 ≤ 2a_k–1 – a_k–1 = a_k–1.
  После того как мы распределим по двум группам все числа, получим группы с суммами S₁ и S₂, причём  |S₁ – S₂| ≤ a₁ = 1.  По условию число  S₁ + S₂  чётно, поэтому  S₁ = S₂.

Источники и прецеденты использования