373 - Romulan Spelling

Moderator: Board moderators

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

373 - Romulan Spelling

This problem description is just awful. I tried the following simple algorithm:

For each line: (ignoring case)
1. Replace every occurence of "pg" with "gp"
2. Replace every occurence of "egp" with "epg"
3. Replace every occurence of "gpuk" with "pguk"

But I realize this will not work too well if the strange rule is supposed to be applied recursively as well. Could someone tell me what the output for
pppgegppp ppvpgegpvpvp
pggggguk eggppuk
is supposed to be. Also, why is there a special correction judge for this problem!?

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

Re: 373 Romulan Spelling

Yarin wrote:For each line: (ignoring case)
1. Replace every occurence of "pg" with "gp"
2. Replace every occurence of "egp" with "epg"
3. Replace every occurence of "gpuk" with "pguk"

But I realize this will not work too well if the strange rule is supposed to be applied recursively as well. Could someone tell me what the output for
pppgegppp ppvpgegpvpvp
pggggguk eggppuk
is supposed to be. Also, why is there a special correction judge for this problem!?
working on this too, still WA though...
i think the output should be:

Code: Select all

``````gpppegppp ppvgpegpvpvp
pggggguk eggppuk
``````
i don't know whether this should be case sensitive or not (e = E ?).

fds
New poster
Posts: 4
Joined: Fri Aug 30, 2002 4:10 pm

Re: 373 Romulan Spelling

Yarin, give a try to the following input:

Code: Select all

``````pg ppppppppppg  gppppppp
ppppppg  epgppgpguk epgpppguk
gpppppppg dds tpg tgp
gpxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx pppg
xxepgxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx ppgp
xxxxxegpxx xxxxxxpguk xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx pegp
xxxxxxxxxx xxxxxxgpuk xxepgpgukx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx pepg
xxxxxxxxxx xxxxxxgpuk xxepgpgukx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxgp
xxxxxxxxxx xxxxxxgpuk xxepgpgukx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxpg
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppg
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeegp
pggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggp
ggpuk gpguk  eggpuk
``````
you should get:

Code: Select all

``````gp gpppppppppp  gppppppp
gpppppp  epggpppguk epgpppguk
ggppppppp dds tgp tgp
gpxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx gppp
xxepgxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx gppp
xxxxxepgxx xxxxxxpguk xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx pepg
xxxxxxxxxx xxxxxxpguk xxepgpgukx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx pepg
xxxxxxxxxx xxxxxxpguk xxepgpgukx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxgp
xxxxxxxxxx xxxxxxpguk xxepgpgukx xxxxxxxxxx xxxxxxxxxx xxxxxxxxxx xxgp
gppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeepg
ggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggpp
gpguk gpguk  epgguk
``````
I believe this includes the main tests you need in this problem. Hope it helps,

Cheers

Fernando

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
Thanks a lot! Got AC now. It's really not obvious from the problem description that the last word, "eggpuk", should be "epgguk". It might as well be "egpguk" imho.

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
hmm...still WA

g should before p, except epg and pguk ....right?

and

if pgpuk ... case1 gppuk, case 2 ppguk ...
I think either one is correct ...right ?

if ggpuk ... it should be gpguk or pgguk ?

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
"pgpuk" -> "gppuk"
"ggpuk" -> "gpguk"

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
It looks like the "epg"'s priority is higher than "pguk",
I have the same method as Yarin's, but the order is not the same:
1) replace each "pg" with "gp", except "epg" or "pguk"
2) replace each "gpuk" with "pguk"
3) replace each "egp" with "epg"
The procedure above can pass the i/o posted here, but WA.
Any hint? thx

bobi1978
New poster
Posts: 13
Joined: Tue Jul 22, 2003 1:57 pm
Contact:
To Little John:
I think that your algorithm is ok.
I don't think that there are HIGH and LOW PRIORITIES.
Maybe you have CASE SENSITIVE ERROR (when replacing "G" and "P").

Here is my algorithm (ACC).
---------------------------------
"XPGX" -> "XGPX"
"EGPX" or "XGPUK" or "EGPUK" -> "EPGX" or "XPGUK" or "EPGUK"
REPEAT THIS UNTILL THERE ARE NO MORE CHANGES.
---------------------------------

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
Hi, bobi:
But I don't have case sensitive error and keeping WA

dootzky
New poster
Posts: 36
Joined: Tue Apr 12, 2005 12:20 am
Contact:

p373 TLE ???

i saw only one more post about p373, but it was all about algo.
i belive my algo is good (works for all input/output in that post),
but now i'm getting TLE??

why?

here's my code:

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream.h>

int a,b,i;
char line[200],temp;

int ninja () {

if  ( ((line[i-1]=='p')||(line[i-1]=='P')) && (line[i-2]!='e') && (line[i-2]!='E')
&& (line[i+1]!='u')&& (line[i+1]!='U') && (line[i+2]!='k')&& (line[i+2]!='K') )
{
//cout << "i-1=" << line[i-1] << ", i+1=" << line[i+1];
//cout << ", i+2=" << line[i+2] << endl;
temp=line[i]; line[i]=line[i-1]; line[i-1]=temp; i++; return 2;}
i++;
return 1;
}

int ninja2 () {

if   ( ((line[i-1]=='e')||(line[i-1]=='E')) && ((line[i+1]=='p')||(line[i+1]=='P')) )
{temp=line[i]; line[i]=line[i+1]; line[i+1]=temp; i++; return 3;}
i++;
return 1;
}

int ninja3 () {

if ( ((line[i+1]=='p')||(line[i+1]=='P')) &&
((line[i+2]=='u')||(line[i+2]=='U')) &&
((line[i+3]=='k')||(line[i+3]=='K')) )
{temp=line[i]; line[i]=line[i+1]; line[i+1]=temp; i++; return 4;}

i++;
return 1;
}

void main () {

while (gets(line)) {

a=0; b=0;
// pg switch
do {
a=1;
for (i=0;i<(signed)strlen(line);)
if ((line[i]=='g') || (line[i]=='G')) { a=ninja(); }
else i++;

if (a==1) {b++; a=0;}

} while (b<100);

a=0; b=0;
// gpuk switch
do {
a=1;
for (i=0;i<(signed)strlen(line);)
if ((line[i]=='g') || (line[i]=='G')) { a=ninja3(); }
else i++;

if (a==1) {b++; a=0;}

} while (b<100);

a=0; b=0;
// Egp switch
do {
a=1;
for (i=0;i<(signed)strlen(line);)
if ((line[i]=='g') || (line[i]=='G')) { a=ninja2(); }
else i++;

if (a==1) {b++; a=0;}

} while (b<100);

cout << line << endl;

}
}
``````

dootzky
New poster
Posts: 36
Joined: Tue Apr 12, 2005 12:20 am
Contact:

UNBELIVABLE?!

nevermind, the problem is sucky, anywayz.

it wasn't clear enough that it should switch ALL p's and g's,
and even now - i'm not sure what EXACTLY i should do.

i saw on one of the posts, that one dude said his algo was:

- switch letters until no more changes... (omg!)
that didn't work for me. i did that. and it was fine. but the algo was killing it self, always chaning from pg to gp, and when E (or e) was found in front, it reversed the process - p infront of g. and back again.
so the changes never ended.

i really don't get this one...

well, greetzs,
dootzky