373 - Romulan Spelling

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

Moderator: Board moderators

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

373 - Romulan Spelling

Post 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!?

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

Re: 373 Romulan Spelling

Post 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 ?).

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

Re: 373 Romulan Spelling

Post 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

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

Post 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.

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

Post 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 ...

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

Post by Yarin »

"pgpuk" -> "gppuk"
"ggpuk" -> "gpguk"

Don't ask me why though...

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post 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

bobi1978
New poster
Posts: 13
Joined: Tue Jul 22, 2003 1:57 pm
Location: Kavadarci, Macedonia
Contact:

Post 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.
---------------------------------

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn »

Hi, bobi:
Thank you for your reply.
But I don't have case sensitive error and keeping WA :cry:

dootzky
New poster
Posts: 36
Joined: Tue Apr 12, 2005 12:20 am
Location: belgrade, serbia (ex yugoslavia)
Contact:

p373 TLE ???

Post 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;

	}
}

dootzky
New poster
Posts: 36
Joined: Tue Apr 12, 2005 12:20 am
Location: belgrade, serbia (ex yugoslavia)
Contact:

UNBELIVABLE?!

Post by dootzky »

nobody answered, for 2 weeks?! :o

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 :(

Post Reply

Return to “Volume 3 (300-399)”