Page 1 of 1
373 - Romulan Spelling
Posted: Sun Sep 15, 2002 7:57 pm
by Yarin
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!?
Re: 373 Romulan Spelling
Posted: Mon Sep 16, 2002 12:34 am
by arc16
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 ?).
Re: 373 Romulan Spelling
Posted: Mon Sep 16, 2002 2:16 am
by fds
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
Posted: Mon Sep 16, 2002 2:39 am
by Yarin
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.
Posted: Tue Sep 17, 2002 9:56 pm
by Even
hmm...still WA
g should before p, except epg and pguk ....right?
I don't know what's wrong... :~ please help
and
if pgpuk ... case1 gppuk, case 2 ppguk ...
I think either one is correct ...right ?
if ggpuk ... it should be gpguk or pgguk ?
thanks in advance ...
Posted: Tue Sep 17, 2002 10:01 pm
by Yarin
"pgpuk" -> "gppuk"
"ggpuk" -> "gpguk"
Don't ask me why though...
Posted: Thu Aug 07, 2003 8:30 am
by LittleJohn
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
Posted: Thu Aug 07, 2003 11:48 am
by bobi1978
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.
---------------------------------
Posted: Thu Aug 07, 2003 3:36 pm
by LittleJohn
Hi, bobi:
Thank you for your reply.
But I don't have case sensitive error and keeping WA
p373 TLE ???
Posted: Sun May 01, 2005 12:36 pm
by dootzky
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;
}
}
UNBELIVABLE?!
Posted: Sat May 07, 2005 12:27 pm
by dootzky
nobody answered, for 2 weeks?!
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
