Page **1** of **2**

### 10625 - GNU = GNU'sNotUnix

Posted: **Thu May 20, 2004 2:05 pm**

by **liux0229**

I've been working on problem 10625, GNU's Not Unix.

I have tried my best to let my program passed by the judge, but always it says I've got the wrong answer. (Also put a 64 bit structure in cos the problem states that the output data will be contained in a 64-bit int). I wonder if there is some special case that I have not yet considered of. So can anyone set up some test data that can cover all aspects of the problem and the answers to them so I can find out where is wrong.

Thank you very much!

Liux

Posted: **Mon May 24, 2004 7:44 am**

by **neno_uci**

Hi liux!

I solved this problem using unsigned long long type for the result, after getting several WA just because of problems printing the result.

Hope it helps...!!!

Posted: **Fri Jul 02, 2004 7:59 pm**

by **anupam**

Hello,

will you please describe the algorithm you have used to solve the porblem??

getting WA 5 times.

Posted: **Sat Jul 03, 2004 2:56 am**

by **Larry**

If you're getting WA, maybe you should explain your algorithm..

Posted: **Sat Jul 03, 2004 8:19 am**

by **anupam**

I have applied simulation to solve it. But, I think, there is a mathemetical solution(purely) to the problem. Would you please explain the mathematical way please??

Anupam

Posted: **Sat Jul 03, 2004 9:40 am**

by **Larry**

It depends on what you mean by simulation. I consider my method a simulation.

The important note is that it doesn't matter what the actual string is, but the number of times a character appear in the input (and each time a rule is applied..).

### I get WA yet, but I know the Math

Posted: **Mon Jul 12, 2004 3:36 pm**

by **medv**

Hi!

I built a matrix m[33..126,33..126] where m[i,j] = amount of letters with ASCII code j in a rule, beginning with a letter with ASCII code i.

For example , if I had only 3 letters (A,B,C) and rules

A->ABC

B->BAAC

C->CB

then I would get matrix ((1 1 1)(2 1 1)(0 1 1)).

In each query I have a Word, a Letter and Number (of iterations).

I evaluate matr = m^Number (^ - power) in O(log Number) time, then I have matr[i,j] = amount of letters with ASCII code j that will be generated

if I would begin with letter ASCII i.

For example, input query is: ABC A 3

matr = m^3 = ((9 9 9)(12 12 12)(6 6 6))

Input string is ABC, Letter is A.

So the answer is matr[1,1] +matr[2,1]+matr[3,1] = 27.

By the way, I wrote in Pascal, and I used extended.

Is there in pascal some integer 64-bit type?

### 10625 - Why WA?

Posted: **Mon Jul 12, 2004 8:02 pm**

by **medv**

program p10625;

const

MIN = 33;MAX = 126;

type

row = array[MIN..MAX] of extended;

var

TempM,m,m1:array[MIN..MAX] of row;

inp,i,j,k,tests,rules:integer;

number,Left,Right:integer;

ch,letter:char;

s:array[MIN..MAX] of integer;

res:extended;

procedure copy(var a,b:array of row);

var

i,j:integer;

begin

for i:=0 to MAX-MIN do

for j:=MIN to MAX do

b[i,j] := a[i,j];

end;

procedure mult(a,b:array of row; var res:array of row);

var

i,j,k:integer;

s:extended;

begin

for i:=0 to MAX-MIN do

for j:=MIN to MAX do

begin

s := 0;

for k:=MIN to MAX do

s := s + a[i,k]*b[k-MIN,j];

res[i,j] := s;

end;

end;

procedure MakeOne(var m:array of row);

var

i:integer;

begin

FillChar(m,sizeof(m),0);

for i:=0 to MAX - MIN do

m[i,i+MIN] := 1;

end;

function IsZeroRow(m:array of row;RowNumber:integer):boolean;

var

i:integer;

begin

IsZeroRow := True;

for i:=MIN to MAX do

if m[RowNumber,i] > 0.0 then

begin

IsZeroRow := True; Exit;

end;

end;

begin

readln(tests);

for i:=1 to tests do

begin

FillChar(TempM,sizeof(TempM),0);

readln(rules);

for j:=1 to rules do

begin

read(ch); Left := Ord(ch);read(ch);read(ch);

while not eoln do

begin

read(ch);

Right := Ord(ch); TempM[Left,Right] := TempM[Left,Right] + 1;

end;

readln;

end;

readln(inp);

for j:=1 to inp do

begin

copy(TempM,m);

for k:=MIN to MAX do

if IsZeroRow(m,k) then m[k,k] := 1;

FillChar(s,sizeof(s),0);

read(ch);

while ch <> ' ' do

begin

Inc(s[Ord(ch)]);

read(ch);

end;

read(letter);read(ch);

readln(number);

MakeOne(m1);

while number > 0 do

begin

if number mod 2 = 1 then mult(m,m1,m1);

number := number div 2;

mult(m,m,m);

end;

res := 0;

for k := MIN to MAX do

res := res + s[k]*m1[k,Ord(letter)];

writeln(res:0:0);

end;

end;

end.

Posted: **Mon Jul 12, 2004 11:38 pm**

by **gawry**

I think it was rather runtime error than a real wrong answer.

Code: Select all

```
program p10625;
const
MIN = 33;MAX = 126;
type
row = array[MIN..MAX] of int64;
matrix = array[MIN..MAX] of row;
var
TempM,m,m1:matrix;
inp,i,j,k,tests,rules:integer;
number,Left,Right:integer;
ch,letter:char;
s:array[MIN..MAX] of integer;
res:int64;
procedure copy(var a,b:matrix);
var
i,j:integer;
begin
for i:=MIN to MAX do
for j:=MIN to MAX do
b[i,j] := a[i,j];
end;
procedure mult(a,b:matrix; var res:matrix);
var
i,j,k:integer;
s:int64;
begin
for i:=MIN to MAX do
for j:=MIN to MAX do
begin
s := 0;
for k:=MIN to MAX do
s := s + a[i,k]*b[k,j];
res[i,j] := s;
end;
end;
procedure MakeOne(var m:matrix);
var
i:integer;
begin
FillChar(m,sizeof(m),0);
for i:=MIN to MAX do
m[i,i] := 1;
end;
function IsZeroRow(m:matrix;RowNumber:integer):boolean;
var
i:integer;
begin
IsZeroRow := True;
for i:=MIN to MAX do
if m[RowNumber,i] > 0 then
IsZeroRow := False;
end;
begin
readln(tests);
for i:=1 to tests do
begin
FillChar(TempM,sizeof(TempM),0);
readln(rules);
for j:=1 to rules do
begin
read(ch); Left := Ord(ch);read(ch);read(ch);
while not eoln do
begin
read(ch);
Right := Ord(ch); TempM[Left,Right] := TempM[Left,Right] + 1;
end;
readln;
end;
for k:=MIN to MAX do
if IsZeroRow(TempM,k) then TempM[k,k] := 1;
readln(inp);
for j:=1 to inp do
begin
copy(TempM,m);
FillChar(s,sizeof(s),0);
read(ch);
while ch <> ' ' do
begin
Inc(s[Ord(ch)]);
read(ch);
end;
read(letter);read(ch);
readln(number);
MakeOne(m1);
while number > 0 do
begin
if number mod 2 = 1 then mult(m,m1,m1);
number := number div 2;
mult(m,m,m);
end;
res := 0;
for k := MIN to MAX do
res := res + m1[k,Ord(letter)]*s[k];
writeln(res);
end;
end;
end.
```

Now it should work but it will be also a little bit too slow, mostly because I have changed extended to int64 - extended give wrong answer for this test case:

So maybe you should think about another method (hint - n<=10000 so it may be a really simple one).

### Re: I get WA yet, but I know the Math

Posted: **Wed Jul 14, 2004 1:51 pm**

by **misof**

medv wrote:By the way, I wrote in Pascal, and I used extended.

Is there in pascal some integer 64-bit type?

Freepascal compiler supports the types int64 (64-bit signed int) and qword (64-bit unsigned), if I recall correctly.

Posted: **Sun Jul 18, 2004 10:21 am**

by **liux0229**

OK...Now I get passed. Thank all of you for your advices

I used simulation and it's much quicker than the math way metioned above, which involves too many wasted multiplications with 0

### 10625 GNU = GNU'sNotUnix

Posted: **Thu Jul 29, 2004 9:11 pm**

by **Hedge**

Hello. I am trying to solve problem 10625 but i got wa a couple of times and cant figure out why. I use a simulating approach. I store the current number of each printable char and in every recursion step i add for every rule the number of the the char which i substitute to the number of the chars who take the place of it. I took care that i substitute all rules at one time and i use unsigned long long int.

Is there anything i havent took care or any tricky input, especialy in the input format?

Anyone have some tricky test cases?

Thank you in advance,

Hedge

Posted: **Thu Jul 29, 2004 10:56 pm**

by **Larry**

Posted: **Fri Jul 30, 2004 10:12 am**

by **Hedge**

I read this thread already, but it wasnt realy useful for me, because the discussion went in some other directions. So i started a new thread.

Posted: **Mon Aug 02, 2004 12:02 am**

by **Hedge**

Hello. I am trying to solve problem 10625 but i got wa a couple of times and cant figure out why. I use a simulating approach. I store the current number of each printable char and in every recursion step i add for every rule the number of the the char which i substitute to the number of the chars who take the place of it. I took care that i substitute all rules at one time and i use unsigned long long int.

Is there anything i havent took care or any tricky input, especialy in the input format?

Anyone have some tricky test cases?