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

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

245 - Uncompress

Post by Revenger »

I have no idea why this program gets WA :-?

[pascal]Program p245;

Const MaxN = 100000;

Var Seq,Dig : String;
Ch : Char;
Voc : Array[1..MaxN]of String;
N : Integer;

Procedure WriteSeq;
Var i,code : Integer;
begin
if Dig='0' then Halt(0);
val(Dig,i,code);
Write(Voc);
Seq:=Voc;
for code:=i downto 2 do Voc

Code: Select all

:=Voc[code-1];
  Voc[1]:=Seq;
  Seq:='';
  Dig:='';
 end;

Procedure AddSeq;
Var i  : Integer;
 begin
  if N=0 then
    Voc[1]:=Seq
   else begin
    for i:=N+1 downto 2 do Voc[i]:=Voc[i-1];
    Voc[1]:=Seq;
   end;
  Write(Seq);
  N:=N+1;
  Seq:='';
 end;

begin
 Seq:='';
 Dig:='';
 N:=0;
 While True Do begin
   Read(Ch);
   Case Ch of
     'A'..'Z' : Seq:=Seq+Ch;
     'a'..'z' : Seq:=Seq+Ch;
     '0'..'9' : Dig:=Dig+Ch;
     else       begin
                 if Seq<>'' then AddSeq;
                 if Dig<>'' then WriteSeq;
                 Write(Ch);
                end;
    end;
  end;
end.[/pascal]

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

Post by xenon »

Your code looks ok to me, although it consumes lots of memory...
One thing that could be wrong is the way you treat line-breaks (combination of read(ch) and write(ch)). As you probably know, the judge translates our Pascal-code to C-code first, and then compiles it. C has a 'funny' way to handle line-breaks, especialy on a unix machine, so things could go wrong here.
I have not verified this, but I have a 'gut-feeling' about it. Try using [pascal]readln(somestring);
handle_all_characters_in_somestring;
writeln;[/pascal]
and it will probably work.

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

yes

Post by Caesum »

they recommend:
Try to NOT read then input in a character-by-character way if possible. We have found problems with the EOLN (end of line, chr(10)) character - GPC does not read it well, and you'll have a lot of problems! If you must read the input in that way, consider this piece of sourcecode:

program PXXX(input, output); { ISO states this line in this way }
{ ... }
begin
{ ... }
while not eof(input) do begin
if eoln(input) then begin{ this should follow the while sentence with nothing between, just like this }
readln(input); { skip rest of line }
writeln(output); { reproduce the eoln character }
continue; { re-test for EOF }
end;
{ here would come 'read(input, ch)' or something like that }
{ ... }
end;
{ ... }
end.
which is from http://acm.uva.es/problemset/pascal.html

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger »

I change my program in proper way. Now it get Runtime Error (Invalid Memory Reference). Why ??!!

[pascal]Program p245;

Const MaxN = 100000;

Var Seq,Dig : String;
Ch : Char;
Voc : Array[1..MaxN]of String;
N : Integer;

Procedure WriteSeq;
Var i,code : Integer;
begin
if Dig='0' then Halt(0);
val(Dig,i,code);
Write(Voc);
Seq:=Voc;
for code:=i downto 2 do Voc

Code: Select all

:=Voc[code-1];
  Voc[1]:=Seq;
  Seq:='';
  Dig:='';
 end;

Procedure AddSeq;
Var i  : Integer;
 begin
  if N=0 then
    Voc[1]:=Seq
   else begin
    for i:=N+1 downto 2 do Voc[i]:=Voc[i-1];
    Voc[1]:=Seq;
   end;
  Write(Seq);
  N:=N+1;
  Seq:='';
 end;

begin
 Seq:='';
 Dig:='';
 N:=0;
 While True Do begin
   if Eoln(InPut) then begin
     Readln;
     Writeln;
    end;
   Read(Ch);
   if Ch in ['A'..'Z','a'..'z'] then Seq:=Seq+Ch else
   if Ch in ['0'..'9'] then Dig:=Dig+Ch else begin
     if Seq<>'' then AddSeq else
     if Dig<>'' then WriteSeq;
     Write(Ch);
    end;
  end;
end.[/pascal]

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

Post by xenon »

see my reply to your topic on 257. S:=S+Ch doesn't work properly.

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger »

I change my program in so way:

[pascal]Program p245;

Const MaxN = 100000;

Var Seq,Dig : String;
Ch : Char;
Voc : Array[1..MaxN]of String;
N : Integer;

Procedure WriteSeq;
Var i,code : Integer;
begin
if Dig='0' then Halt(0);
val(Dig,i,code);
Write(Voc);
Seq:=Voc;
for code:=i downto 2 do Voc

Code: Select all

:=Voc[code-1];
  Voc[1]:=Seq;
  Seq:='';
  Dig:='';
 end;

Procedure AddSeq;
Var i  : Integer;
 begin
  if N=0 then
    Voc[1]:=Seq
   else begin
    for i:=N+1 downto 2 do Voc[i]:=Voc[i-1];
    Voc[1]:=Seq;
   end;
  Write(Seq);
  N:=N+1;
  Seq:='';
 end;

Procedure StringAdd(Var S : String; C : Char); 
 begin
  S:=S+C;
 end; 

begin
 Seq:='';
 Dig:='';
 N:=0;
 While True Do begin
   if Eoln(InPut) then begin
     Readln;
     Writeln;
    end;
   Read(Ch);
   if Ch in ['A'..'Z','a'..'z'] then StringAdd(Seq,Ch) else
   if Ch in ['0'..'9'] then StringAdd(Dig,Ch) else begin
     if Seq<>'' then AddSeq else
     if Dig<>'' then WriteSeq;
     Write(Ch);
    end;
  end;
end.[/pascal]

[b]But It get Runtime Error![/b]

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum »

I had no problem getting your first program to be accepted by just handling the eol properly. You have been very careless in implementing is above. You must use something like

if eoln
... handle eoln
else
... do other stuff
end

and within the first part when you handle the eoln you must deal with anything hanging around in Seq and Dig.

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

Post by xenon »

OK, I was wrong here, the s:=s+ch bug is not an issue here (although it still exists).

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

245 Thanks

Post by Revenger »

Thank you very much! I get Accepted!

pc5971
New poster
Posts: 34
Joined: Mon Aug 05, 2002 11:24 am
Contact:

245 Problem

Post by pc5971 »

I couldn't see where is the problem in my program. I receive the message "Wrong Answer" but I think that it's OK...

Can somebody help me???

Code: Select all

[pascal]
program p254(input,output);
const
zero:string[31]='0000000000000000000000000000000';
unu:string='0000000000000000000000000000001';
x:array[0..100] of string=
('0000000000000000000000000000000',
'0000000000000000000000000000001',
'0000000000000000000000000000003',
'0000000000000000000000000000007',
'0000000000000000000000000000015',
'0000000000000000000000000000031',
'0000000000000000000000000000063',
'0000000000000000000000000000127',
'0000000000000000000000000000255',
'0000000000000000000000000000511',
'0000000000000000000000000001023',
'0000000000000000000000000002047',
'0000000000000000000000000004095',
'0000000000000000000000000008191',
'0000000000000000000000000016383',
'0000000000000000000000000032767',
'0000000000000000000000000065535',
'0000000000000000000000000131071',
'0000000000000000000000000262143',
'0000000000000000000000000524287',
'0000000000000000000000001048575',
'0000000000000000000000002097151',
'0000000000000000000000004194303',
'0000000000000000000000008388607',
'0000000000000000000000016777215',
'0000000000000000000000033554431',
'0000000000000000000000067108863',
'0000000000000000000000134217727',
'0000000000000000000000268435455',
'0000000000000000000000536870911',
'0000000000000000000001073741823',
'0000000000000000000002147483647',
'0000000000000000000004294967295',
'0000000000000000000008589934591',
'0000000000000000000017179869183',
'0000000000000000000034359738367',
'0000000000000000000068719476735',
'0000000000000000000137438953471',
'0000000000000000000274877906943',
'0000000000000000000549755813887',
'0000000000000000001099511627775',
'0000000000000000002199023255551',
'0000000000000000004398046511103',
'0000000000000000008796093022207',
'0000000000000000017592186044415',
'0000000000000000035184372088831',
'0000000000000000070368744177663',
'0000000000000000140737488355327',
'0000000000000000281474976710655',
'0000000000000000562949953421311',
'0000000000000001125899906842623',
'0000000000000002251799813685247',
'0000000000000004503599627370495',
'0000000000000009007199254740991',
'0000000000000018014398509481983',
'0000000000000036028797018963967',
'0000000000000072057594037927935',
'0000000000000144115188075855871',
'0000000000000288230376151711743',
'0000000000000576460752303423487',
'0000000000001152921504606846975',
'0000000000002305843009213693951',
'0000000000004611686018427387903',
'0000000000009223372036854775807',
'0000000000018446744073709551615',
'0000000000036893488147419103231',
'0000000000073786976294838206463',
'0000000000147573952589676412927',
'0000000000295147905179352825855',
'0000000000590295810358705651711',
'0000000001180591620717411303423',
'0000000002361183241434822606847',
'0000000004722366482869645213695',
'0000000009444732965739290427391',
'0000000018889465931478580854783',
'0000000037778931862957161709567',
'0000000075557863725914323419135',
'0000000151115727451828646838271',
'0000000302231454903657293676543',
'0000000604462909807314587353087',
'0000001208925819614629174706175',
'0000002417851639229258349412351',
'0000004835703278458516698824703',
'0000009671406556917033397649407',
'0000019342813113834066795298815',
'0000038685626227668133590597631',
'0000077371252455336267181195263',
'0000154742504910672534362390527',
'0000309485009821345068724781055',
'0000618970019642690137449562111',
'0001237940039285380274899124223',
'0002475880078570760549798248447',
'0004951760157141521099596496895',
'0009903520314283042199192993791',
'0019807040628566084398385987583',
'0039614081257132168796771975167',
'0079228162514264337593543950335',
'0158456325028528675187087900671',
'0316912650057057350374175801343',
'0633825300114114700748351602687',
'1267650600228229401496703205375');


type rec=record n:integer;
                s:string;
         end;

var nrp,n,A,B,C:integer;
    m:string;
    aux,k:integer;
    t:array[1..3] of integer;

function cifra(ch:char):integer;
var c:integer;
begin
  c:=ord(ch)-ord('0');
  cifra:=c;
end;

function caracterul(c:integer):char;
var ch:char;
begin
  ch:=chr(c+ord('0'));
  caracterul:=ch;
end;

function k_max(m:string):integer;
var k:integer;
begin
  k:=1;
  while x[k]<=m do
    k:=k+1;
  k_max:=k-1
end;

procedure citire(var n:integer;var m:string);
begin
  readln(input,n,m);
  delete(m,1,1);
  while length(m)<31 do
    insert('0',m,1);
end;

procedure scad(var s1:string;s2:string);
{ s1:=s1-s2 }
var t,c1,c2,c,j,t1:integer;
begin
  t:=0;
  for j:=31 downto 1 do
    begin
      c1:=cifra(s1[j]);
      c2:=cifra(s2[j]);
      if c1-t<c2 then
        t1:=1
      else
        t1:=0;
      c:=c1-t+t1*10-c2;
      t:=t1;
      s1[j]:=caracterul(c);
    end;
end;

begin
  citire(n,m);
  nrp:=0;
  while not ((n=0) and (m=zero)) do
    begin
      nrp:=nrp+1;
      A:=1; B:=2; C:=3;
      t[A]:=n; t[B]:=0; t[C]:=0;
      repeat
        k:=k_max(m);

        {k discuri de pe A pe C sau
                   de pe A pe B}
        t[A]:=t[A]-k;
        if (n-k) mod 2=1 then
          t[C]:=t[C]+k
        else
          t[B]:=t[B]+k;
        scad(m,x[k]);
        if m<>zero then
            {1 disc de pe A pe B sau
                    de pe A pe C}
          begin
            t[A]:=t[A]-1;
            if (n-k) mod 2=1 then
              t[B]:=t[B]+1
            else
              t[C]:=t[C]+1;
            scad(m,unu);
            if m<>zero then
              begin
                if (n-k) mod 2=1 then
                  begin
                    aux:=A; A:=C; C:=aux;
                    n:=k;
                  end
                else
                  begin
                    n:=k;
                    aux:=A; A:=B; B:=C; C:=aux;
                  end;
              end;
          end;
      until m=zero;
      if nrp>1 then
        writeln(output);
      write(output,t[1],' ',t[2],' ',t[3]);
      citire(n,m);
    end;
end.
[/pascal]

To understand, to the start of the program I calculate (with other program) the 2^k-1 powers. That means that x=s^i-1...

Thank you[/pascal]

mickey_boy
New poster
Posts: 2
Joined: Fri May 23, 2003 1:04 pm
Contact:

can anyone help me 245 uncompres

Post by mickey_boy »

i have a problem with validiation in make the program

haow can i devide it's become 2 words it is, it was, it has
an i'll become i will n i shall


thanx you

mickey_boy
New poster
Posts: 2
Joined: Fri May 23, 2003 1:04 pm
Contact:

Please Help ME Anyone Who has Done IN C for problem set 245

Post by mickey_boy »

Please can you help me Send me source code in C . because i really need this for my study, i have try but Error.


please, please....

thank You

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

please, please ...

Post your code on this board and I think, that someone help you :):)

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

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]
"Everything should be made simple, but not always simpler"

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

245-Problems, don't Know why I get WA

Post by Khriz »

Can someone help me, I don't know why it doesn't work. The source code is a little poor. (I'm a beginner)

#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;
}
//cout << c;
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--;
}
//cout << endl << "Palabra devuelta: " << nodeaux->paraula;
if( pos == 0 && nodeaux != NULL) {
antnodeaux->anterior = nodeaux->anterior;
nodeaux->anterior = node;
return nodeaux;
} else if(nodeaux == NULL) {
return NULL;
}
}
} else {
return NULL;
}
}


Thanks
Khriz

Post Reply

Return to “Volume 2 (200-299)”