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

Редактор - C++

Восстановить пароль Регистрация
 
Rakaddar
0 / 0 / 0
Регистрация: 23.03.2009
Сообщений: 14
11.03.2010, 12:40     Редактор #1
Помогите, пожалуйста, решить задачу на структуры данных. Вроде легкая, но у меня 16 тест не проходит, где то зацикливается походу.

Редактор
(Время: 1 сек. Память: 16 Мб Сложность: 39%)

Немногие знают, что первые версии текстового редактора из предыдущей задачи были написаны в России программистом Колей. Для этого он несколько месяцев почти не выходил из подвала, где стояли только диван и компьютер.

Вот одна из проблем, с которыми столкнулся Коля в те времена. Во время работы пользователь набирает какой-то текст, а так же может его редактировать. При этом, даже если итоговый результат полностью помещается на экран, в процессе работы отдельные строки могут иметь слишком большую длину. Мы не будем просить вас повторить Колин подвиг и заново написать редактор. Определите, какой максимальной длины строка получалась в течение набора текста, если вам известно, какие клавиши и в каком порядке нажимал пользователь.
Входные данные

Во входном файле INPUT.TXT записана строка из различных символов - последовательность кнопок на клавиатуре, которые нажимал пользователь. Переводы строк заменены на символ '\'. Первые версии редактора поддерживали три управляющие команды, которые закодированы следующим образом:
'<' - удаление предыдущего символа (если курсор находится в начале строки, и эта строка не первая, то удаляется предшествующий перевод строки);
'^' - перемещение в конец предыдущей строки (игнорируется, если курсор находится на первой строке);
'|' - перемещение в конец следующей строки (игнорируется, если курсор находится на последней строке).

Все остальные символы, содержащиеся в файле, имеют коды от 32 (пробел) и выше и должны пониматься как есть. Число нажатий клавиш не превосходит 105.
Выходные данные

В выходной файл OUTPUT.TXT выведите одно целое число - максимальную длину строки, которая была достигнута в течение работы редактора.
Примеры
№ INPUT.TXT OUTPUT.TXT
1 Hello, World???<<<! 15
2 Hello, World?\This is^<!!!| a sample. 17

мой код :

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
#include <iostream>
 
using namespace std;
 
int a[1000009] = {0},pre[1000009],next[1000009], n = 1, i, c = 0, m = 0;
char s[1000009];
 
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    gets(s);
 
    pre[0] = 0;
    next[0] = 0;
 
    for(i = 0; i < strlen(s); i++)
    {
        if( s[i] == '\\' )
        {
            if(next[c] == c)next[n] = n;
            else
            {
                next[n] = next[c];
                pre[next[c]] = n;
            }
            next[c] = n;
            pre[n] = c;
            c = next[c];
            n++;
        }
        else if( s[i] == '<' )
        {
            if(a[c])a[c]--;
            else if(pre[c] != c)
            {
                next[pre[c]] = next[c];
                if(next[c]!=c)pre[next[c]] = pre[c];
                c = pre[c];
            }
        }
        else if( s[i] == '^' )
            c = pre[c];
 
        else if( s[i] == '|' )
            c = next[c];
 
        else a[c]++;
        m = max(m,a[c]);
    }
    cout << m;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.03.2010, 12:40     Редактор
Посмотрите здесь:

Hex редактор C++
Визуальный редактор С++ C++
C++ редактор текста
C++ Графический редактор
Текстовый редактор C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Yurii_74
paladin
 Аватар для Yurii_74
279 / 179 / 3
Регистрация: 25.02.2009
Сообщений: 592
11.03.2010, 13:17     Редактор #2
Зачем такие жуткие массивы? Всяко разно больше 105 символов не выйдет.
kuroiryuu
 Аватар для kuroiryuu
311 / 295 / 23
Регистрация: 05.11.2009
Сообщений: 698
Завершенные тесты: 2
11.03.2010, 13:24     Редактор #3

Не по теме:

вот что олимпиадные задачи с людьми делают...



Цитата Сообщение от Rakaddar Посмотреть сообщение
Hello, World???<<<! 15
а как тут 15 получилось???
"Hello" - 5
"World" - 5
", " - 2
"???" - 3
"!" - 1
удалили 3 "?" и как 15 получилось?
5+2+5+1 = 15 так что ли?
Rakaddar
0 / 0 / 0
Регистрация: 23.03.2009
Сообщений: 14
11.03.2010, 14:38  [ТС]     Редактор #4
Yurii_74, это 10^5 вообще то

kuroiryuu, максимальное из вообще когда либо присустствующего чила символов,
не просто в конце

Добавлено через 25 секунд
kuroiryuu, пробелы считаются
kuroiryuu
 Аватар для kuroiryuu
311 / 295 / 23
Регистрация: 05.11.2009
Сообщений: 698
Завершенные тесты: 2
12.03.2010, 10:29     Редактор #5
Цитата Сообщение от Rakaddar Посмотреть сообщение
kuroiryuu, максимальное из вообще когда либо присустствующего чила символов,
не просто в конце
По условию определите, какой максимальной длины строка получалась в течение набора текста, если вам известно, какие клавиши и в каком порядке нажимал пользователь.
Так строка тут только теста (без учёта спецсимволов) нужна, а не просто что нажимал пользователь...

Цитата Сообщение от Rakaddar Посмотреть сообщение
Добавлено через 25 секунд
kuroiryuu, пробелы считаются
так я считал пробелы, и где для первого задания ещё два пробела потерялось?
во втором сразу видно что 17, ибо длинная строки "This is a sample." 17

Добавлено через 58 минут
и еще в этой строке Hello, World?\This is^<!!!| a sample. одинарный слэш не пройдёт, ибо Си не воспринимает '\', может быть из-за этого у вас не проходили ваши тесты

Добавлено через 33 минуты
в принципе, вот что у меня получилось...
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
56
int main()
{
    char * input = "Hello, World???<<<!\\Hello, World?\\This is^<!!!| a sample.";
 
    int max = 0;
    int* count_str = 0;
    int count = 1;
    for (int i = 0; i < (int)strlen(input); i++)
    {
        if(input[i] == '\\')
            count++;
    }
 
    count_str = new int[count];
    
    for(int i = 0; i < count; i++)
        count_str[i] = 0;
 
    int j = 0;
    int i = 0;
    while(i < (int)strlen(input))
    {
        switch(input[i])
        {
            case '<':
                if (i > 0 && input[i - 1] == '\\')
                {
                    count_str[j - 1] = count_str[j - 1] + count_str[j];
                    count--;
                }
                if (i > 0 && input[i - 1] != '\\')
                    count_str[j]--;
                break;  
            case '^':
                j = (j > 0) ? j - 1: j;
                break;
            case '|':
                j = (j < count) ? j + 1: j;
                break;
            case '\\':
                j++;
                break;
            default:
                
                count_str[j]++;
                break;
        }
        i++;
    }
    max = count_str[0];
    for (int i = 0; i < count; i++)
        if (max < count_str[i])
            max = count_str[i];
    cout << "Max = " << max << endl;
    delete[] count_str;
}
Yandex
Объявления
12.03.2010, 10:29     Редактор
Ответ Создать тему
Опции темы

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