10027 - Language Cardinality

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

Moderator: Board moderators

ahanys
New poster
Posts: 24
Joined: Mon Nov 19, 2001 2:00 am
Location: N/A
Contact:

10027 - Language Cardinality

Post by ahanys » Tue Mar 19, 2002 12:32 pm

I repetely testing if there is any other derivation of any frase.

Code: Select all

/* @JUDGE_ID: 9072XC 10027 C++ */
#include <stdio.h>
#include <string.h>

char r[1001][2][11];
char s[1050][10000];

int main() {
    char l[10000];
    char *u;
    int i = 0;
    int poc = 1;

    gets(l);
    u = strtok(l, """);
    sprintf(s[0],"%s",u);

    while (gets(l) != NULL) {
        u = strtok(l, """);
        if (u == NULL) continue;
        sprintf(r[i][0],"%s",u);
        u = strtok(NULL, """);
        u = strtok(NULL, """);
        sprintf(r[i++][1],"%s",u);
    }
    int change = 1;
    int stare = poc;
    while (1) {
        char *is = NULL;
        if (!change) {
            break;
        } else {
            change = 0;
        }
        for (int a=0; a<i; a++)                 // for each rule
        for (int b=0; b<poc; b++)               // for each word
        while ((is = strstr(s[b], r[a][0])) != NULL)      // for each
        {
            char tmp[10002] = "";
            if (poc > 1000) {printf("Too many.n"); exit(0);}
            {
                for (int w=0; w<=is-s[b]; w++) {
                    if (w == is-s[b]) {
                        tmp[w] = '';
                    } else {
                        tmp[w] = s[b][w];
                    }
                }
                strcat(tmp, r[a][1]);
                strcat(tmp, &s[b][(is-s[b])+strlen(r[a][0])]);

                for (int t=0; t<=poc; t++) {
                    if (t == poc) {
                        strcpy(s[poc++], tmp);
                        change = 1;
                        break;
                    }
                    if (strcmp(s[t], tmp) == 0) break;
                }
            }
            is = NULL;
            if (stare == poc) {
                break;
            } else {
                stare = poc;
            }
        }
    }
    printf("%in",poc);
}


It looks much better for read. :smile:

I GET WRONG ANSWER! :roll:



<font size=-1>[ This Message was edited by: ahanys on 2002-03-26 10:38 ]</font>

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Tue Mar 19, 2002 12:38 pm

HEY, THERE'S NO REASON TO SCREAM... :wink:

Could you tell us what reply you get? Btw, you can nicely indent your code (see FAQ). That way it's easier for us to read... If you want to, you can even do it afterwards by editing your posting. I like the new forum :smile:

<font size=-1>[ This Message was edited by: Stefan Pochmann on 2002-03-19 11:40 ]</font>

arnsfelt
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:

Post by arnsfelt » Tue Mar 19, 2002 3:32 pm

Some questions:

Are your string buffers large enough ?
Is poc always <= 1000 before the last line ?

ahanys
New poster
Posts: 24
Joined: Mon Nov 19, 2001 2:00 am
Location: N/A
Contact:

Post by ahanys » Tue Mar 19, 2002 4:30 pm

If number of words exceeds 1000 I print Too many. or somethink like this. See problem description.:smile:

arnsfelt
New poster
Posts: 44
Joined: Wed Oct 17, 2001 2:00 am
Location: Denmark
Contact:

Post by arnsfelt » Tue Mar 19, 2002 10:21 pm

Good for you.

Here is another question:

Does your program work for the input
"SSS"
"SS"->"b"
?

btw, ofcourse I've read the problem description - I solved the problem 8 month ago :smile:

ahanys
New poster
Posts: 24
Joined: Mon Nov 19, 2001 2:00 am
Location: N/A
Contact:

Post by ahanys » Tue Mar 26, 2002 11:40 am

Your last qustion my program solve correctly.

Please test my program on your input. :smile:

<font size=-1>[ This Message was edited by: ahanys on 2002-03-26 10:40 ]</font>

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

Post by Dominik Michniewski » Tue May 13, 2003 8:33 am

I've got the same problem like ahanys...
My program runs (I think OK) with rules, which have empty sides (before or after a production sign), I consider also that empty string belongs to words generated by G (I try with case, that empty string doesn't belong but WA too).
Could anyone tell me, what should be wrong? Or send me some IO or maybe I can send (s)he my code ? It's similar to code ahanys ...

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)

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Jul 14, 2003 7:33 pm

Try this input (when I had all of them handled correctly I got AC):

Code: Select all

9

"aaa"
"a"->"a"

"aaa"
""->""

"@@@"
"@"->"#"
"#"->"{"
"{"->"%/\=?"
"%/\=?"->"&!+-"
"&!+-"->"$"
"$"->",:-.;_"
",:-.;_"->"abcdefghij"
"abcdefghij"->"qwertyuiop"
"qwertyuiop"->"0123456789"

"@@@"
"@"->"#"
"#"->"{"
"{"->"%%%%%%%%%%"
"%%%%%%%%%%"->"&&&"
"&&&"->"$$$$$"

"abc"
"a"->"b"
"b"->"c"
"a"->"dddddddd"
"d"->"e"

"aaa"
"a"->"b"
"b"->"c"
"c"->"d"
"d"->"e"
"e"->"f"
"f"->"g"
"g"->"h"
"g"->""

"abcdefgh"
"a"->"b"
"b"->"c"
"c"->"d"
"d"->"e"
"e"->"f"
"f"->"g"
"g"->"h"
"g"->""

"aaaaaaaaaa"
""->"aaaaaaaaaa"

"aaa"
"a"->"bbbbbbbbbb"
"b"->"aaaaaaaaaa"
Output:

Code: Select all

1

1

1000

657

518

585

Too many.

Too many.

Too many.

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

Post by Dominik Michniewski » Tue Jul 15, 2003 9:37 am

Per: Could you help me ? I've got correct results for your inputs, but judge says TLE. I don't know what can I do wrong ... Can I send you my code via PM ?

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)

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Tue Jul 15, 2003 1:12 pm

Yeah, sure. I'm not very good at reading code (sometimes not even my own :)) but I could give it a try.

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

Post by Dominik Michniewski » Tue Jul 15, 2003 2:46 pm

Thanks Per again. I didn't think about such kind of productions before ...

For every, who has problems with this question:
think about productions like "a"->"aaa" :)

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)

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

10027 Language Cardinality

Post by liulike » Sat Jan 10, 2004 8:31 am

How to slove the problem?
Plz give me some hints.
Thx!!

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Thu Jan 22, 2004 8:06 pm

I get accepted by trying to generate all possible string, if the number of string > 1000 I just stop and output "Too many"

This is not the fastest or smartest method, but it is straight forward to code :wink:
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

User avatar
habibiamin
New poster
Posts: 8
Joined: Tue Oct 12, 2004 1:54 pm
Location: Iran-Tehran
Contact:

10027 Why TLE ??? HELP PLZ

Post by habibiamin » Wed Nov 10, 2004 12:51 pm

Please help me... I don't know why TLE ??? in 10027
:oops:
[pascal]
//http://acm.uva.es/problemset/v100/10027.html
program Q10027;

type
Grammer=record
Src,Des:String;
end;

var
GRAMS:array [1..100] of Grammer;
LWords:Array [1..1000] of string;
lines,GRAMSCNT:integer;
Language:string;
WCnt:integer;

function IsValid(Word:string):boolean;
var
r:boolean;
i:integer;
begin
r:=true;
for i:=1 to WCnt do
begin
if LWords=Word then r:=false;
end;
IsValid:=r;
end;

procedure Words(st:integer;var lang:string;var Count:integer);
var
TLang:string;
i,j:integer;
begin
if Count<=1000 then
begin
for j:=st to length(lang) do
begin
for i:=1 to GRAMSCNT do
begin
if(copy(lang,j,length(GRAMS.Src))=GRAMS.Src) then
begin
TLang:=lang;
lang:=copy(lang,1,j-1)+GRAMS.Des +copy(lang,j+length(GRAMS.Src),length(lang));
if (IsValid(lang)) then
begin
Count:=Count+1;
LWords[Count]:=lang;
Words(i+length(GRAMS.Src),lang,Count);
end;
lang:=Tlang;
if Count>1000 then Break;
end;
end;
if Count>1000 then Break;
end;
end;
end;

procedure READGRAMS();
var
TMPSTR:string;
i,pre,state:integer;
begin
readln(TMPSTR);
while(TMPSTR<>'') do
begin
pre:=-1;
state:=1;
for i:=1 to length(TMPSTR) do
if TMPSTR='"' then
if pre<>-1 then
begin
if state=1 then
begin
GRAMSCNT:=GRAMSCNT+1;
GRAMS[GRAMSCNT].Src:=copy(TMPSTR,pre,i-pre);
GRAMS[GRAMSCNT].Des:='';
state:=2;
end
else
GRAMS[GRAMSCNT].Des:=copy(TMPSTR,pre,i-pre);

if GRAMS[GRAMSCNT].Des=GRAMS[GRAMSCNT].Src then
begin
GRAMSCNT:=GRAMSCNT-1;
end;

pre:=-1;
end
else
pre:=i+1;
readln(TMPSTR);
end;

end;
begin
readln(lines);
readln;
while(lines>0) do
begin
readln(Language);
if Language ='' then Break;
Language:=copy(Language,2,length(Language)-2);
GRAMSCNT:=0;
READGRAMS();
WCnt:=1;
LWords[WCnt]:=Language ;
Words(1,Language,WCnt);
if(WCnt>1000) then
writeln('Too many.')
else
writeln(WCnt);

lines:=lines-1;
end;



end.
[/pascal]

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Sat Aug 19, 2006 6:28 am

I am getting TLE. i used STL string, string.find(),string.erase(), string.insert() these options. are these slow? do i have to do it manually?

One more question:

Say initial string = Asb

rule = A->tA

will it mean resultant set contains infinite number of words or only tAsb. coz tAsb contains A again. so can i replace it again or not?
Self judging is the best judging!

Post Reply

Return to “Volume 100 (10000-10099)”