Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 11.03.2010, 07:20
Slava

 
Сообщений: n/a

Редактор
Помогите, пожалуйста, решить задачу на структуры данных. Вроде легкая, но у меня 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

мой код :
#include <iostream>
using namespace std;

long long n = 1,a[1000009],pre[1000009],next[1000009],i,c = 0,m = 0;
char s[1000009];
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

gets(s);
pre[0]=next[0]=0;
for(i=0;i<strlen(s);i++)
{

if(s[i] == '\\'){
if(next[c]==c)next[n]=n;
else {
pre[next[c]]=n;
next[n]=next[c];
}
next[c]=n;
pre[n]=c;
c=next[c];n++;
}
else if(s[i]=='<'){
if(a[c]>0)a[c]--;
else if(pre[c]!=c)
{
next[pre[c]]=next[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;
}
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Помогите написать задачку "Текстовый редактор" на С++ redpage Задачи 4 23.10.2009 00:45
Редактор блок схем гость Реализация, исходники, языки 3 18.04.2009 16:27
Помогите создать текстовый редактор на С++ Лёлик Задачи 2 05.11.2008 21:45
Редактор графа на С++ Builder Irensik Реализация, исходники, языки 1 06.04.2008 22:28