245 - Uncompress

[Khriz]

sorry for the tabs
[cpp]
#include <string>
#include <ctype.h>
#include <iostream>

using namespace std;

struct nodecua {
char paraula[51];
nodecua * anterior;
};

nodecua* buscarParaula(int, nodecua*);

int main() {
char c, paraula[51];
int i, pos;
nodecua * actual;
nodecua * anterior;

anterior = NULL;
i = -1;
pos = -1;

while( (c = cin.get()) != EOF ) {

if( isalpha(c) ) {

if( i == -1 ) {
i = 0;
actual = (nodecua*)malloc(sizeof(nodecua));
actual->anterior = anterior;
}
paraula = c;
i++;

} else if ( isdigit(c) ) {
if(pos == -1) {
pos = atoi(&c);
} else {
pos = (pos*10)+atoi(&c);
}

} else {

if(i != -1) {
paraula = '\0';
i = -1;
strcpy(actual->paraula, paraula);
cout << actual->paraula << c;
anterior = actual;

} else if(pos != -1) {
if (pos != 1) {
actual = buscarParaula(pos - 1, anterior);
if( actual != NULL) {
actual->anterior = anterior;
cout << actual->paraula << c;
anterior = actual;
} else {
cout << c;
}
} else if(pos == 1) {
if( anterior != NULL) {
cout << anterior->paraula << c;
} else {
cout << c;
}
} else if(pos == 0) {
if( i != 0) {
paraula = '\0';
i = -1;
strcpy(actual->paraula, paraula);
cout << actual->paraula << endl;
exit(0);
} else {
exit(0);
}

}
pos = -1;

} else {
cout << c;
}
paraula[0] = '\0';
}
}
}

nodecua* buscarParaula(int pos, nodecua * node) {

nodecua * nodeaux = node;
nodecua * antnodeaux;

if( node != NULL) {
if (pos != 0) {
while( pos > 0 && nodeaux != NULL){
antnodeaux = nodeaux;
nodeaux = nodeaux->anterior;
pos--;
}

if( pos == 0 && nodeaux != NULL) {
antnodeaux->anterior = nodeaux->anterior;
nodeaux->anterior = node;
return nodeaux;
} else if(nodeaux == NULL) {
return NULL;
}
}
} else {
return NULL;
}
}
[/cpp]

[Khriz]

Hi,

I receive WA in the problem 245 and I don't know why, all my results go ok, can someone help me. I've used a tail to go back to search the word indicated by the number.

[cpp]
#include <string>
#include <ctype.h>
#include <iostream>

using namespace std;

struct nodecua {
char paraula[51];
nodecua * anterior;
};

nodecua* buscarParaula(int, nodecua*);

int main() {
char c, paraula[51];
int i, pos;
nodecua * actual;
nodecua * anterior;

anterior = NULL;
i = -1;
pos = -1;

while( (c = cin.get()) != EOF ) {

if( isalpha(c) ) {

if( i == -1 ) {
i = 0;
actual = (nodecua*)malloc(sizeof(nodecua));
actual->anterior = anterior;
}

paraula = c;
i++;

} else if ( isdigit(c) ) {
if(pos == -1) {
pos = atoi(&c);
} else {
pos = (pos*10)+atoi(&c);
}

} else {

if(i != -1) {
paraula = '\0';
i = -1;
strcpy(actual->paraula, paraula);
cout << actual->paraula << c;
anterior = actual;

} else if(pos != -1) {
if (pos != 1) {
actual = buscarParaula(pos - 1, anterior);
if( actual != NULL) {
actual->anterior = anterior;
cout << actual->paraula << c;
anterior = actual;
} else {
cout << c;
}
} else if(pos == 1) {
if( anterior != NULL) {
cout << anterior->paraula << c;
} else {
cout << c;
}
} else if(pos == 0) {
if( i != 0) {
paraula = '\0';
i = -1;
strcpy(actual->paraula, paraula);
cout << actual->paraula << endl;
exit(0);
} else {
exit(0);
}

}
pos = -1;

} else {
cout << c;
}
paraula[0] = '\0';
}
}
}

nodecua* buscarParaula(int pos, nodecua * node) {

nodecua * nodeaux = node;
nodecua * antnodeaux;

if( node != NULL) {
if (pos != 0) {
while( pos > 0 && nodeaux != NULL){
antnodeaux = nodeaux;
nodeaux = nodeaux->anterior;
pos--;
}

if( pos == 0 && nodeaux != NULL) {
antnodeaux->anterior = nodeaux->anterior;
nodeaux->anterior = node;
return nodeaux;
} else if(nodeaux == NULL) {
return NULL;
}
}
} else {
return NULL;
}
}
[/cpp]

[Raiyan Kamal]

Hello there,

did you take care of this? I could not understand from you code.

If it is not the first occurrence, the word is not copied to the compressed file. Instead, its position in the list is copied into the compressed file and the word is moved to the front of the list.

i.e. after you use a word from the list (after getting a number) you have to put it on top of the list.

I used a bi-directional linked list to store all the words. I assumed that there might be 10000 or less different words.

[liulike]

hello gyes, can any 1 tell me what the problem is in my src code.
I have tried all critical cases i have found. but still wa.
please help and post test cases

---
here is the code,...

Code: Select all

[c]
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#define N 10200
char a[N][60],d[60],q[60],tmp[60],an[60];
int i,l,s,t,n,num,j;
main()
{
	while(gets(q))
	{
		sscanf(q,"%s",&an);
		if(an[1]==0 && an[0]=='0') break;
		l=strlen(q);
		if(l==0) {printf("\n");continue;}
		for(i=0;i<l;i++) if(isalnum(q[i])) d[i]=q[i]; else d[i]=' ';d[i]=0;
		s=-1;
		for(i=0;i<=l;i++)
		{
			if(i==l) {q[i]='\n';goto end;}
			if(isalpha(d[i]))
			{
				if(s!=1) a[t][n++]=d[i],s=0;
				else
				{
					strcpy(tmp,a[t-num-1]);
					printf("%s",a[t-num-1]);
					for(i=t-num+1;i>0;i--) strcpy(a[i],a[i-1]);
					strcpy(a[t],tmp);
					s=0;n=1;a[t][0]=d[i];num=0;
				}
			}
			else if(isdigit(d[i]))
			{
				if(s!=0) num=num*10+(d[i]-'0'),s=1;
				else
				{
					a[t][n]=0;s=1;num=d[i]-'0';t++;n=0;
					printf("%s",a[t-1]);
				}
			}
			else
			{
				end:
				if(s==1)
				{
					strcpy(tmp,a[t-num]);
					printf("%s",a[t-num]);
					for(j=t-num;j<t-1;j++) strcpy(a[j],a[j+1]);
					strcpy(a[t-1],tmp);
				}
				else if(s==0)
				{
					a[t][n]=0;
					t++;
					printf("%s",a[t-1]);
				}
				s=-1;num=0;n=0;
				printf("%c",q[i]);
			}
		}
	}
	fflush(stdout);
	return 0;
}[/c]

any help is welcome.
thank you all.
--
anupam [/i][/b]

You should use getchar() to read data instead of gets()
If you still get WA, I would send you my code

[Experimenter]

Hi, guys!
I just wonder, why I get this TLE. Here is the code. (I don't care, actually, how much memory it consumes - it should just be working).
I would be very greatful for your help.
[cpp]
#include <string>
#include <list>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <stdio.h>

using namespace std;

#ifndef ONLINE_JUDGE
ifstream fin ("input.txt");
ofstream fout("output.txt");
#else
#define fin std::cin
#define fout std::cout
#endif


list <string > dict;
int i = 0;
void Init(string& in);
enum eLexType {Word, Number,Other,End};
eLexType getlex(string& s,const string& in);

list <string >::iterator Exists (const string& s);
bool IsAlpha(char c);
bool IsDigit(char c);
void DeCompress(const string& in,string& out);

int main()
{
string in,out;
Init(in);
DeCompress(in,out);
for(int i = 0; i < out.length();i++)
fout<<out;
return 0;
}

void Init(string& in)
{ i =0; dict.resize(0);
in = "";
string s;
while(true)
{
getline(fin,s,'\n');
if(s == "0" || fin.eof())
break;
in += s;
in += '\n';
}
}

void DeCompress(const string& in,string& out)
{ eLexType type;
string s,t;
list <string >::iterator iter,t_iter;
while((type = getlex(s,in)) != End)
{
switch(type)
{
case Word:
{
iter = Exists(s);
if(iter == dict.end())
dict.push_back(s);
else
{
for(;iter != --dict.end();iter++)
{
t_iter = iter;
t_iter++;
std::iter_swap(t_iter,iter);
}
}
out += s;
break;
}
case Number:
{
int nIndex;
sscanf(s.c_str(),"%d",&nIndex);
for(iter = dict.end();nIndex > 0; nIndex--)
iter--;

out += *iter;
for(;iter != --dict.end();iter++)
{
t_iter = iter;
t_iter++;
std::iter_swap(t_iter,iter);
}
break;
}
case Other:
out += s;
break;
}
}
}
eLexType getlex(string& s,const string& in)
{
s = "";
int n = in.length();

if(i >= n)
return End;
if(IsAlpha(in))
{ s += in;
for(i++;i < n && IsAlpha(in); i++)
s += in;
return Word;
}

if(IsDigit(in))
{ s += in;
for(i++;i < n && IsDigit(in); i++)
s += in;
return Number;
}

s = in[i++];
return Other;
}
list <string >::iterator Exists (const string& s)
{ for(list <string >::iterator i = dict.begin(); i != dict.end();i++)
if(*i == s)
return i;
return dict.end();
}

bool IsAlpha(char c)
{ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
}
bool IsDigit(char c)
{ return (c >= '0' && c <= '9');
}

[/cpp]

[Experimenter]

guys, have a mercy on me. help me, please!

[Experimenter]

i really cannot understand what's going on.
it should be working now, as it exchanges only pointers not data as I use list not an array. I might messed up with input somewhere. have a look, somebody,please. you might see what I am not seeing.
[cpp]
#include <string>
#include <list>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <set>
#include <stdio.h>

using namespace std;

#ifndef ONLINE_JUDGE
ifstream fin ("input.txt");
ofstream fout("output.txt");
#else
#define fin std::cin
#define fout std::cout
#endif


list <string > dict;
set <string > words;
enum eLexType {Word, Number,Other,End};
eLexType getlex(string& s);
string in("");
unsigned long i = 0;

list <string >::iterator Exists (const string& s);
void DeCompress();

int main()
{
DeCompress();
return 0;
}

void DeCompress()
{
eLexType type;
string s;

getline(fin,in,'\n');
i = 0;

list <string >::iterator iter;
while((type = getlex(s)) != End)
{
switch(type)
{
case Word:
{
iter = Exists(s);
if(iter == dict.end())
{
dict.push_back(s);
words.insert(s);
}
else
dict.splice(dict.end(),dict,iter);
fout<<s;
break;
}
case Number:
{
int nIndex;
sscanf(s.c_str(),"%d",&nIndex);
for(iter = dict.end();nIndex > 0; nIndex--)
iter--;
fout<<*iter;
dict.splice(dict.end(),dict,iter);
break;
}
case Other:
fout<<s;
break;
}
}
}
eLexType getlex(string& s)
{

if(i >= in.length())
{
if(fin.eof())
return End;
getline(fin,in,'\n');
i = 0;

s = "\n";
return Other;
}

if(in == "0")
return End;
if((in >= 'a' && in <= 'z') || (in >= 'A' && in <= 'Z'))
{ s = in;
for(i++;i < in.length() && ((in >= 'a' && in <= 'z') || (in >= 'A' && in <= 'Z')); i++)
s += in;
return Word;
}

if((in[i] >= '0' && in[i] <= '9'))
{ s = in[i];
for(i++;i < in.length() && (in[i] >= '0' && in[i] <= '9'); i++)
s += in[i];
return Number;
}

s = in[i++];
return Other;
}
list <string >::iterator Exists (const string& s)
{
if(words.find(s) != words.end())
{
for(list <string >::iterator iter = dict.begin(); iter != dict.end();iter++)
if(*iter == s)
return iter;
}
else
return dict.end();
}
[/cpp]

[Experimenter]

guys, I really don't know what is going on. I even did this thing but still I get time limit exceeded. what could possibly cause it?
[cpp]
#include <string>
#include <list>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <set>
#include <stdio.h>

using namespace std;

#ifndef ONLINE_JUDGE
ifstream fin ("input.txt");
ofstream fout("output.txt");
#else
#define fin std::cin
#define fout std::cout
#endif


list <string > dict;
set <string > words;
enum eLexType {Word, Number,Other,End};
eLexType getlex(string& s);
string in("");
unsigned long i = 0;

list <string >::iterator Exists (const string& s);
bool IsAlpha(char c);
bool IsDigit(char c);
void DeCompress();

int main()
{
DeCompress();
return 0;
}

void DeCompress()
{
eLexType type;
string s;

getline(fin,in,'\n');
i = 0;

list <string >::iterator iter;
while((type = getlex(s)) != End)
{
switch(type)
{
case Word:
{
iter = Exists(s);
if(iter == dict.end())
{
dict.push_back(s);
words.insert(s);
}
else
dict.splice(dict.end(),dict,iter);
fout<<s;
break;
}
case Number:
{
int nIndex;
sscanf(s.c_str(),"%d",&nIndex);
for(iter = dict.end();nIndex > 0; nIndex--)
iter--;
fout<<*iter;
dict.splice(dict.end(),dict,iter);
break;
}
case Other:
fout<<s;
break;
}
}
}
eLexType getlex(string& s)
{

if(i >= in.length())
{
if(fin.eof())
return End;
getline(fin,in,'\n');
i = 0;

s = "\n";
return Other;
}

if(in == "0")
return End;
if(IsAlpha(in))
{ s = in;
for(i++;i < in.length() && IsAlpha(in); i++)
s += in;
return Word;
}

if(IsDigit(in))
{ s = in;
for(i++;i < in.length() && IsDigit(in); i++)
s += in;
return Number;
}

s = in[i++];
return Other;
}
list <string >::iterator Exists (const string& s)
{
if(words.find(s) != words.end())
{
for(list <string >::iterator iter = dict.begin(); iter != dict.end();iter++)
if(*iter == s)
return iter;
}
else
return dict.end();
}

bool IsAlpha(char c)
{ return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
}
bool IsDigit(char c)
{ return (c >= '0' && c <= '9');
}
[/cpp]

[Experimenter]

fucken hell! the last one got accepted. the problem was in function exists. it took quite a long time to search for it, so a fast way of answering had to be found. for this purpose I use a set.

[abhijit]

Change the subject of your post, or if thats not possible, try reposting. You seem to want the answer to 254 and not 245.

[abhijit]

Maybe you are asking about words like :
i'm
etc.

Consider a word to be a sequence ONLY of upper and lowercase letters.
You leave the "m" as "m" and don't change it to "am".

[Wei]

Well~I don't know where the wrong is~~
Could someone help me???

Code: Select all

Cut after AC!!!^^

[ibrahim]

Hi,
I don't know, why can't understand this problem. Will you please help me.

[Abednego]

Seams like a simple simulation with a list, but I get WA. liulike said to use getchar() instead of gets(). Is there any reason for it? Can anyone make a test case that doesn't work with gets()? It sounds very strange.

Code: Select all

#include <stdio.h>
#include <map>
#include <string>
#include <list>
#include <ctype.h>
using namespace std;

char buf[1024 * 1024];

int main()
{
    list< string > li;
    map< string, list< string >::iterator > s2it;
    while( gets( buf ) && ( buf[0] - '0' || buf[1] ) )
    {
        string token;
        int num = 0, i = 0;
        do
        {
            if( isalpha( buf[i] ) ) token += buf[i];
            else if( isdigit( buf[i] ) )
            {
                num *= 10;
                num += buf[i] - '0';
            }
            else 
            {
                if( token.size() )
                {
                    if( s2it.count( token ) ) li.erase( s2it[token] );
                    li.push_front( token );
                    s2it[token] = li.begin();
                    cout << token;
                    token = "";
                }
                else if( num )
                {
                    __typeof( li.begin() ) it = li.begin();
                    while( --num ) ++it;
                    token = *it;
                    cout << token;
                    li.erase( it );
                    li.push_front( token );
                    s2it[token] = li.begin();
                    token = "";
                }
                putchar( buf[i] );
            }
        }
        while( buf[i++] );
        putchar( '\n' );
    }
    return 0;
}

[stubbscroll]

Seams like a simple simulation with a list, but I get WA. liulike said to use getchar() instead of gets(). Is there any reason for it? Can anyone make a test case that doesn't work with gets()? It sounds very strange.

I don't think there is a test case that doesn't work with gets(). I use gets() in my accepted code.