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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Hardcore
4 / 4 / 0
Регистрация: 24.10.2010
Сообщений: 200
#1

Запаковка - C++

25.10.2010, 19:26. Просмотров 779. Ответов 4
Метки нет (Все метки)

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Сложность Гамма

Билл пытается компактно представить последовательность заглавных латинских букв от 'A' до 'Z', с учетом повторяющихся последовательностей в ней. Например, возможный способ представить последовательность AAAAAAAAAABABABCCD - есть 10(A)2(BA)B2(C)D. Билл ввел формальное понятие упакованной последовательности так:
• Последовательность, содержащая один символ из диапазона 'A'..'Z' считается упакованной последовательностью. Ее распаковка возвращает тот же символ.
• Если S и Q - упакованные последовательности, то SQ - также упакованная последовательность. Причем, если результатом распаковки S является S', а Q - Q', то SQ распаковывается в S'Q'.
• Если S - упакованная последовательность, то X(S) - также упакованная последовательность, где X - десятичное целое число, большее 1. Если S распаковывается в S', то X(S) распаковывается в S', повторенную X раз.

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

Ввод
Одна строка, состоящая не менее, чем из одного и не более чем из 100 символов в диапазоне 'A'..'Z'.
Вывод
Число - длину кратчайшего из вариантов запаковки исходной последовательности.

Ввод 1 Ввод 2
AAAAAAAAAABABABCCD NEERCYESYESYESNEERCYESYESYES
Вывод 1 Вывод 2
12 14
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.10.2010, 19:26
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Запаковка (C++):

Zip запаковка\распаковка данных со смещением - C++
Воспользовавшись программой Offset file unzipper 0.3.6a узнал что у файла смещение(hex offset) = 3, windowBits=15. Теперь нужно как то...

Запаковка файлов в .exe - Программы архиваторы
столкнулся с такой проблемой и не могу решить её. Вообщем скачал файл он в формате .exe и распаковал его с помощью 7z и у меня на рабочем...

Распаковка и запаковка псевдоархива - Delphi
В общем есть псевдоархив, всю структуру я наметил в hex редакторе. Сначала идет хедер архива, размер архива. Дальше весь архив идет...

Запаковка программы в .msi - C#
Здравствуйте. Скажите, у меня есть 3 файла моей программы. Как её запаковать в один установочный файл .msi? И есть ли альтернативные...

Распаковка и запаковка .sr формата. - Графика и игры
Не знал, для какого раздела это лучше подходит, написал сюда. Натолкнулся на проблему с редактированием .sr файлов в одной ире. В нужном...

Запаковка файлов с данными - C#
Здравствуйте! У меня есть проект, он подгружает некоторые текстовики, картинки и прочее. Следовательно рядом с экзешником программы в...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
25.10.2010, 21:15 #2
Цитата Сообщение от Hardcore Посмотреть сообщение
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб. Сложность Гамма
а что это значит?
0
Hardcore
4 / 4 / 0
Регистрация: 24.10.2010
Сообщений: 200
26.10.2010, 12:23  [ТС] #3
Это лимит времени на компиляцию и объем экзэшника.
0
easybudda
26.10.2010, 12:33
  #4

Не по теме:

Цитата Сообщение от Hardcore Посмотреть сообщение
Это лимит времени на компиляцию и объем экзэшника.
0.00000003125 миллисекунды и 0,000000000023669 килобайт, да ещё и с гамма-сложностью? Это чё за марсианский девайс такой?

0
Хохол
Эксперт C++
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
26.10.2010, 13:50 #5
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <fstream>
#include <string>
 
using namespace std;
 
ofstream cout("output.txt");
ifstream cin("input.txt");
 
int dp[200][200]; // [start][len]
string s;
 
const int inf = 987654321;
 
int numberLen(int n)
{
    if(n <= 9)
        return 1;
    else
        return 2;
}
 
bool good(int start, int L, int len)
{
    for(int i = L; i < len; i++)
        if(s[start+i] != s[start+i%L])
            return false;
    return true;
}
 
int f(int start, int len)
{
    if(dp[start][len] == 0)
    {
        if(len == 1)
            dp[start][len] = 1;
        else
        {
            dp[start][len] = inf;
            for(int L = 1; L <= len-1; L++)
                dp[start][len] = min(dp[start][len],f(start,L)+f(start+L,len-L));
 
            for(int L = 1; L <= len/2; L++)
                if(len % L == 0)
                    if(good(start,L,len))
                            dp[start][len] = min(dp[start][len], numberLen(len/L) + 2 + f(start,L));
        }
    }
    return dp[start][len];
}
 
int main()
{
    cin >> s;
    cout << f(0,s.size());
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.10.2010, 13:50
Привет! Вот еще темы с ответами:

Запаковка папки в архив программно - C++ Builder
Можно ли как-либо папку находящююся на диске С запаковать в архив рар или зип, вместе со всеми файлами?

.NET 4.x Запаковка и распаковка архива + ProgressBar - C#
К слову мне нужна информация как запаковать и распаковать zip архив + используя криптографию zip архива + показывать процесс на...

Запаковка файлов в один пакет - Visual Basic
Доброго дня всем! Прошу прощения за возможно ламерский вопрос Дело такое. Я запаковую некоторое количество файлов в один пакет. Вот...

Запаковка файлов в архив с расширением pack - Графика и игры
Есть игровой архив pack и скрипт для его распаковки в проге quickbms. Распаковав его и отредактировав файлы, необходимо запаковать файлы...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
26.10.2010, 13:50
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru