Задача "Сожми меня если сможешь"

@Legoshi · Регистрация: 13.05.2022

Студворк — интернет-сервис помощи студентам

Секретный агент Джеймс Бонд с кнопкой должен передать послание правительству своего государства. Так как канал передачи совершенно секретен и максимально безопасен, его пропускная способность очень низка, поэтому исходное сообщение должно быть сжато согласно существующему правилу:

Для любой строки s cтрока str= s...s (конкатенация n строк s) может быть представлена, как str = s^n, т.е. строка str может быть закодирована в виде строки s со следующей за ней десятичной записью числа n таким образом, что суммарная длина закодированной строки составляет len(s)+digits10(n), где len(s) - длина строки s, а digits10(n) - число цифр в десятичной записи положительного числа n (примеры в примечаниях).

Необходимо найти минимальную длину сжатой строки. Скобки при сжатии не нужны, маги-дешифровальщики могут восстановить исходное сообщение и без них (смотреть примеры и примечание).

Формат ввода

В первой строке одно целое число (1≤n≤500)(1≤n≤500) - длина исходной строки.

В следующей строке дана исходная строка, состоящая из букв латинского алфавита в нижнем регистре (от 'a' до 'z' включительно).

Формат вывода

Выведите минимальную длину сжатой строки.

Примеры:
5
aaabb

4
--------
10
aaaaaaaaaa

3
-------
22
aaabaaabccdaaabaaabccd

8

Примечание:
Строка aaabaaabccdaaabaaabccd может быть представлена в виде a3b2c2d2. ~~Длинна~~ длина 8

Заранее спасибо всем, кто поможет!

@Catstail · 14.05.2022, 07:36

Сообщение от Legoshi

Строка aaabaaabccdaaabaaabccdможет быть представлена в виде a3b2c2d2. Длина 8

- неужели? А по-моему, после сжатия длина будет 18...

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def press(stri):
    res=""
    count=1
    prev=stri[0]
    for curr in stri[1:]:
        if prev==curr:
            count+=1
        else:
            if count>1:
                res=res+prev+str(count)
            else:
                res=res+prev
            count=1
            prev=curr
    if count>1:
        res=res+prev+str(count)
    else:
        res=res+prev
    return res
 
_=input()
print(len(press(input())))

@QueryMonkey · 14.05.2022, 07:45

Предложенный формат где позволяются вложенные циклы, но скобки отбрасываются, приводит к потере данных при сжатии. Это хорошо видно в примере 3 от ТС.

Более простой пример: а2б2 может быть получен из аабб, или из аабааб
Если (а2б)2

@Catstail · 14.05.2022, 09:58

QueryMonkey, задача не вполне корректна

@eaa · 14.05.2022, 10:00

двумерное дп

Новые блоги и статьи Все статьи Все блоги /
Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .	Контроль уникальности заводского номера - вариант №2 Maks 24.03.2026 В отличие от предыдущего варианта добавлено прерывание циклов, также добавлены новые переменные для сохранения контекста ошибки перед прерыванием цикла: Процедура ПередЗаписью(Отказ, РежимЗаписи,. . .	SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++ 8Observer8 24.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip	Жизнь в неопределённости kumehtar 23.03.2026 Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .
Модель здравоСохранения: работники работают быстрее после её введения. anaschu 23.03.2026 geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .	Контроль уникальности заводского номера - вариант №1 Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере документа выдачи шин для спецтехники с табличной частью. Данные берутся из регистра сведений, по которому настроено. . .	Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения anaschu 22.03.2026 e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git	Программный отбор элементов справочника по группе Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .

@Legoshi 0 / 0 / 0 Регистрация: 13.05.2022 Сообщений: 1

	Задача "Сожми меня если сможешь" 13.05.2022, 19:53. Показов 528. Ответов 4 Метки нет (Все метки) Секретный агент Джеймс Бонд с кнопкой должен передать послание правительству своего государства. Так как канал передачи совершенно секретен и максимально безопасен, его пропускная способность очень низка, поэтому исходное сообщение должно быть сжато согласно существующему правилу: Для любой строки s cтрока str= s...s (конкатенация n строк s) может быть представлена, как str = s^n, т.е. строка str может быть закодирована в виде строки s со следующей за ней десятичной записью числа n таким образом, что суммарная длина закодированной строки составляет len(s)+digits10(n), где len(s) - длина строки s, а digits10(n) - число цифр в десятичной записи положительного числа n (примеры в примечаниях). Необходимо найти минимальную длину сжатой строки. Скобки при сжатии не нужны, маги-дешифровальщики могут восстановить исходное сообщение и без них (смотреть примеры и примечание). Формат ввода В первой строке одно целое число (1≤n≤500)(1≤n≤500) - длина исходной строки. В следующей строке дана исходная строка, состоящая из букв латинского алфавита в нижнем регистре (от 'a' до 'z' включительно). Формат вывода Выведите минимальную длину сжатой строки. Примеры: 5 aaabb 4 -------- 10 aaaaaaaaaa 3 ------- 22 aaabaaabccdaaabaaabccd 8 Примечание: Строка aaabaaabccdaaabaaabccd может быть представлена в виде a3b2c2d2. ~~Длинна~~ длина 8 Заранее спасибо всем, кто поможет! 0

@QueryMonkey Нарушающий 417 / 305 / 46 Регистрация: 13.04.2022 Сообщений: 1,759
	14.05.2022, 07:45
	Предложенный формат где позволяются вложенные циклы, но скобки отбрасываются, приводит к потере данных при сжатии. Это хорошо видно в примере 3 от ТС. Более простой пример: а2б2 может быть получен из аабб, или из аабааб Если (а2б)2 0

@Catstail Супер-модератор 38194 / 21127 / 4309 Регистрация: 12.02.2012 Сообщений: 34,732 Записей в блоге: 14
	14.05.2022, 09:58
	QueryMonkey, задача не вполне корректна 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	14.05.2022, 10:00
	двумерное дп 0