Задача Abcdefg
Є повідомлення, записане в алфавіті з N символів. Відомо, що
1-й, 2-й, , N-й
символи алфавіту використані в повідомленні
f1, f2, ,
fN разів. Його потрібно
набрати на M-клавішній клавіатурі, застосувавши спосіб набору, аналогічний тому,
що використовується в мобільних телефонах.
На телефоні, клавіші 2 співставлені літери
abc, клавіші
3 def і т.д. Для набору тексту телефон переводиться в спеціальний режим,
у котрому одне натискання на клавішу 2 породжує символ a, 2 підряд натискання
на 2 символ b, 3 підряд символ c; аналогічно, одне натискання
3 породжує
d, 2 підряд e і т.д. Якщо ж потрібно набрати 2 підряд літери
a, то натискають
клавішу 2, трохи чекають і знов натискають клавішу 2.
В нашому ж випадку, символи з 1-ого по якийсь
K1-ий мають відповідати 1-ій клавіші, з
(K1+1)-ого по якийсь K2-ий
2-ій клавіші і т.д., до
KM=N.
Напишіть програму, що шукатиме мінімальну необхідну кількість натискань на клавіші
для набору вказаного повідомлення на вказаній клавіатурі, якщо дозволяється будь-який
розподіл символів алфавіту між клавішами.
Технічні
умови.Ви вводите з клавіатури спочатку два числа
N і M, потім N чисел
f1, f2, , fN кількості входжень відповідного символа. Всі числа розділені пропусками.
2 £ M
£100,
3£ N
£250, M < N. Потрібно вивести на екран єдине число знайдену мінімальну кількість натискань на клавіші.
Приклад:
Введення:
5 3 3 2 5 7 1
Виведення:
21
Примітка до
прикладу.
Значення 21 досягається, якщо 1-й та 2-й символи співставити
1-й клавіші, 3-й символ 2-й клавіші,
4-й та 5-й символи 3-й клавіші. Тоді кількість
натискань буде (3×1 +
2×2) +
(5×1) +
(7×1+1×2) =
21.
Задача
Abcdefg
Есть
сообщение, записанное в алфавите из N
символов. Известно, что 1-й, 2-й, , N-й символы
алфавита использованы в сообщении f1,
f2, , fN раз. Его необходимо
набрать на M-клавишной клавиатуре,
используя способ набора, аналогичный
используемому в мобильных телефонах.
На телефоне, клавише 2 сопоставлены
буквы abc, клавише 3 def и т.д.
Для набора текста телефон переводится в
специальный режим, в котором одно нажатие
на клавишу 2 порождает символ a, 2 подряд
нажатия на 2 символ b, 3 подряд
символ c; аналогично, одно нажатие
3 порождает d, 2 подряд
e и т.д.
Если же необходимо набрать 2 подряд буквы
a, то нажимают клавишу 2, немного
ждут и снова нажимают клавишу 2.
В нашем же случае, символы с 1-ого по
некоторый K1-ый должны
соответствовать 1-ой клавише, с (K1+1)-ого
по некоторый K2-ой 2-ой клавише и т.д.,
до KM=N.
Напишите программу, которая будет искать
минимальное необходимое количество
нажатий на клавиши для набора указанного
сообщения на указанной клавиатуре, если
разрешается какое угодно распределение
символов алфавита между клавишами.
Технические условия. Вы
вводите с клавиатуры сначала два числа N и
M,
потом N чисел f1, f2, , fN
количества вхождений соответствующего
символа. Все числа разделены пробелами. 2 £
M £100,
3£
N £250,
M < N. Необходимо вывести на экран единственное
число найденное минимальное количество
нажатий на клавиши.
Пример:
Ввод: 5 3 3 2 5 7 1
Вывод: 21
Примечание к примеру. Значение 21
достигается, если 1-й и 2-й символы
сопоставить 1-й клавише, 3-й символ 2-й
клавише, 4-й и 5-й символы 3-й клавише. Тогда
количество нажатий будет (3×1
+ 2×2)
+ (5×1)
+ (7×1+1×2)
= 21.
Кравець Г.П,
Непомнящий Г.І., Пасіхов Ю.Я., Порубльов І.М. |
