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

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

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

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

25.10.2010, 19:26. Просмотров 740. Ответов 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
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.10.2010, 19:26     Запаковка
Посмотрите здесь:

C# Запаковка файлов с данными
Распаковка и запаковка .sr формата.
Visual Basic Запаковка файлов в один пакет
Запаковка файлов в архив с расширением pack
C++ Builder Запаковка папки в архив программно
Запаковка dll и exe в один исполняемый файл C#
Delphi Запаковка\Распаковка массива байт (Zlib)
Запаковка файлов в .exe
Visual Basic Распаковка и запаковка файлов в архивы - нужен графический вид
Zip запаковка\распаковка данных со смещением C++
Запаковка программы в .msi C#
7z: запаковка содержимого папки, а не папки с содержимым BAT

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

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

Не по теме:

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

Хохол
Эксперт 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());
}
Yandex
Объявления
26.10.2010, 13:50     Запаковка
Ответ Создать тему
Опции темы

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