245 - Uncompress

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Khriz
New poster
Posts: 3
Joined: Thu Mar 04, 2004 9:00 pm

Post by 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
New poster
Posts: 3
Joined: Thu Mar 04, 2004 9:00 pm

245 WA

Post by 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
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by 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
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

Post by liulike »

anupam wrote: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 :oops: :oops: [/i][/b]
You should use getchar() to read data instead of gets()
If you still get WA, I would send you my code :D

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

245 Time Limit Exceeded

Post by 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). :D
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]
it would be great if you replied this post. really.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

Post by Experimenter »

guys, have a mercy on me. help me, please! :cry:
it would be great if you replied this post. really.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

Post by 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]
Last edited by Experimenter on Wed Nov 03, 2004 1:59 pm, edited 2 times in total.
it would be great if you replied this post. really.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

Post by 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]
it would be great if you replied this post. really.

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

Post by 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. :lol:
it would be great if you replied this post. really.

abhijit
New poster
Posts: 12
Joined: Mon May 24, 2004 2:13 pm

Post by 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
New poster
Posts: 12
Joined: Mon May 24, 2004 2:13 pm

Post by 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
New poster
Posts: 23
Joined: Sat Jul 24, 2004 5:37 pm
Contact:

245 with lots of WA~

Post by Wei »

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

Code: Select all

Cut after AC!!!^^

ibrahim
Experienced poster
Posts: 149
Joined: Mon Feb 07, 2005 10:28 pm
Location: Northern University, Bangladesh
Contact:

Problem with 245

Post by ibrahim »

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

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by 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;
}
If only I had as much free time as I did in college...

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll »

Abednego wrote: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.

Post Reply

Return to “Volume 2 (200-299)”