Форум программистов, компьютерный форум CyberForum.ru

Что мне нужно сделать? - C++

Восстановить пароль Регистрация
 
newyork7776
 Аватар для newyork7776
346 / 339 / 79
Регистрация: 21.05.2013
Сообщений: 1,305
Завершенные тесты: 1
11.12.2013, 19:21     Что мне нужно сделать? #1
Есть сообщение, записанное в алфавите из 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. Конкретные значения K1, K2, ..., KM - 1 не задаются — их, наоборот, нужно подобрать.

Напишите программу, которая будет искать минимальное необходимое количество нажатий на клавиши для набора указанного сообщения на указанной клавиатуре.

Входные данные
В первой строке содержатся два числа N и M, во второй — N чисел f1, f2, ..., fN — количества вхождений соответствующего символа. Числа внутри строк разделены одинарными пробелами. 2 ≤ M ≤ 50, 3 ≤ N ≤ 70, M < N, 1 ≤ fi ≤ 1000.

Выходные данные
Необходимо вывести единственное число — найденное минимальное количество нажатий на клавиши.

Примеры тестов
входные данные
5 3
3 2 5 7 1
выходные данные
21
Примечание
Значение 21 достигается при K1 = 2, K2 = 3 (1-й и 2-й символы сопоставить 1-й клавише, 3-й символ 2-й клавише, 4-й и 5-й символы 3-й клавише). Тогда количество нажатий будет

(3 × 1 + 2 × 2) + (5 × 1) + (7 × 1 + 1 × 2) = 21.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.12.2013, 19:21     Что мне нужно сделать?
Посмотрите здесь:

Подскажите пожалуйста,что нужно сделать,что бы отображался русский язык?? C++
C++ Я не прошу писать мне код, я прошу подсказать мне, что за структура требуется в задании
C++ Объясните человеческим языком мне чайнику что такое singleton, статический класс. Зачем они нужны. Что рекомендуете прочитать мне для начала
C++ Что нужно сделать, чтобы это скомпилировалось?
Не могу отладить программу, не понимаю, что нужно сделать C++
C++ Нужно сделать что бы давало рандомно числа и нужно написать ответ
C++ Что мне нужно дописать
Всё компилируется, выводится, но не то что мне нужно C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 04:44. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru