Башня Петя в очередной раз купил себе набор из кубиков. На этот раз он выстроил из них настоящую крепость — последовательность из N столбиков, высота каждого столбика составляет Ai кубиков. Вскоре ему стало интересно, насколько его крепость защищена от жуликов и воров. Для этого он ввел понятие башни. Башней называется любая последовательность из K столбиков подряд (где K — любимое число Пети Защищенность башни определяется как суммарная высота всех столбиков этой башни (чем она больше, тем громаднее и ужаснее она кажется), умноженная на минимум высоты столбиков башни (т.к. враги, очевидно, будут пытаться проникнуть через самое слабое место башни). Неприступность крепости определяется как сумма защищенностей каждой из башен. Петя решил как можно скорее посчитать, какова же неприступность его крепости. Однако вскоре он понял, что недостаточно знать высоту каждого из столбиков. В зависимости от того, как сгруппировать столбики в башни, получится разный результат. В различных вариантах группировки часть столбиков могут не принадлежать ни одной из башен. Разумеется, Петя выберет то разбиение на башни, при котором неприступность будет максимальна. Петя успешно справился со своей задачей, но теперь Правительство Флатландии решило защитить свой горный курорт. Правительство уже построило крепость из кубиков (просто кубики были побольше). Теперь вы должны Правительству посчитать неприступность этой крепости. Единственная трудность состоит в том, что у Правительства было очень много денег, и поэтому крепость была построена очень длинная. Входные данные В первой строке содержатся число N — количество столбиков в крепости и число K — любимое число Пети (1 ≤ K ≤ N ≤ 100 000). Далее в следующей строке содержатся N целых чисел, обозначающих Ai (1 ≤ Ai ≤ 106). Выходные данные В первой строке выведите число Q — количество башен в оптимальном разбиении. Далее выведите Q чисел — номера первых столбиков каждой башни. Примеры Ввод Вывод 8 3 1 2 3 4 1 6 7 8 2 2 6 1 1 1 1 1 2 1 1 1000000 2 1 2 Решите на с++ или Python
Ответы
Program Strok;
uses crt;
const number=['0','1','2','3','4','5','6','7','8','9'];
var A:array[1..10] of string;
i,j,k:integer;
s:string;
begin
{Ввод элементов массива}
for i:=1 to 10 do
begin
write('Введите ',i,' элемент массива: ');
readln(a[i])
end;
{проверка условий}
for i:=1 to 10 do {перебираем элементы массива}
begin
k:=0; {задаем триггер}
s:=a[i];
for j:=length(s) div 2+1 to length(s) do
if s[j] in number then k:=1; {Pascal позволяет обращаться со строковыми переменными, как с массивами символов, проверяем строку со второй половины на "вшивость", и, если встретилась цифра, вызываем срабатывание тригера}
if k=0 then writeln(s)
end;
readln end.
uses crt;
const number=['0','1','2','3','4','5','6','7','8','9'];
var A:array[1..10] of string;
i,j,k:integer;
s:string;
begin
{Ввод элементов массива}
for i:=1 to 10 do
begin
write('Введите ',i,' элемент массива: ');
readln(a[i])
end;
{проверка условий}
for i:=1 to 10 do {перебираем элементы массива}
begin
k:=0; {задаем триггер}
s:=a[i];
for j:=length(s) div 2+1 to length(s) do
if s[j] in number then k:=1; {Pascal позволяет обращаться со строковыми переменными, как с массивами символов, проверяем строку со второй половины на "вшивость", и, если встретилась цифра, вызываем срабатывание тригера}
if k=0 then writeln(s)
end;
readln end.
Ответить на вопрос
Поделитесь своими знаниями, ответьте на вопрос:
Популярные вопросы в разделе
Интернет хорошо или плохо напиши ответ и обоснуй его?
Автор: Emasterova77
Переведите число 243 из восьмеричной системы в десятичную и обратно С решением
Автор: kovalenko262
Переведем 11110100 из 2-ой в 10-ую = 2^7 + 2^6 + 2^5 + 2^4 + 2^2 = 128 + 64 + 32 + 16 + 4 = 244.
185 + 244 = 429. В 16: 429/16 = 26 (ост: 13 = D); 26 / 16 = 1 (ост 10 = A).
ответ: 1AD.
2. 19 из 10-ой переведём в 6-ую = 31. Также переведём 33 из 10-ой в 6-ую = 53.
Перечислим все наборы:
33 34 35 40 41 42 43 44 45 50 51 52 53.
Считаем тройки и получаем их количество - 6.
3. 49[10cc] = 100[x cc]. Распишем 100 и получим = 1*x^2 + 0*x^1 + 0*x^0 = x^2. => 49 = x^2; x = 7.
ответ: 7.
4. Переведём число 30 из 10-ой в 4-ую СС и получим: 132. Нам надо найти числа, которые оканчиваются на 31. Значит все последующие разряды будут x. x31 < 132. Если x = 0, то будет следующее число 031, оно меньше 132 и значит подходит. Если x = 1, то будет число 131 и оно также подходит. Все последующие число не подходят, поэтому ответ только два числа.
5. Долго делать это, чем смог