10027 - Language Cardinality

[ahanys]

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.

I GET WRONG ANSWER!



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

[Stefan Pochmann]

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

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

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

[arnsfelt]

Some questions:

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

[ahanys]

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

[arnsfelt]

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

[ahanys]

Your last qustion my program solve correctly.

Please test my program on your input.

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

[Dominik Michniewski]

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

[Per]

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]

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

[Per]

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

[Dominik Michniewski]

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

[liulike]

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

[..]

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

[habibiamin]

Please help me... I don't know why TLE ??? in 10027

[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]

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?