### P177

Posted:

**Tue Jun 18, 2002 4:00 am**Is there any trap in it?

I've checkmy output carefully for over 100 times, why i still got WA?

I've checkmy output carefully for over 100 times, why i still got WA?

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

Posted: **Tue Jun 18, 2002 4:00 am**

Is there any trap in it?

I've checkmy output carefully for over 100 times, why i still got WA?

I've checkmy output carefully for over 100 times, why i still got WA?

Posted: **Thu Jun 20, 2002 2:02 am**

Can someone check my output?

Though my program looks stupid, but it works well on my computer!

I can't find why i got WA.

[pascal]

program acm177;

const

b2:array[1..13]of longint=(2,4,8,16,32,64,128,256,512,1024,2048,4096,8192);

var

opc:array[1..9000]of char;

n:byte;

fig:array[0..200]of string;

mhu,mhd,mwl,mwr:longint;

fh,fw:longint;

procedure readdata;

begin

readln(n);

end;

procedure makeopc;

var

i:byte;

j:longint;

tc:char;

h,w:longint;

begin

fillchar(opc,sizeof(opc),0);

opc[1]:='R';

opc[2]:='U';

if n>1 then

begin

for i:=2 to n do

begin

for j:=b2[i-1]+1 to b2* do*

begin

case opc[b2*+1-j] of*

'U':begin

opc[j]:='L';

end;

'D':begin

opc[j]:='R';

end;

'L':begin

opc[j]:='D';

end;

'R':begin

opc[j]:='U';

end;

end;

end;

end;

for j:=1 to b2[n-1] do

begin

tc:=opc[j];

case opc[b2[n]+1-j] of

'U':opc[j]:='D';

'D':opc[j]:='U';

'L':opc[j]:='R';

'R':opc[j]:='L';

end;

case tc of

'U':opc[b2[n]+1-j]:='D';

'D':opc[b2[n]+1-j]:='U';

'L':opc[b2[n]+1-j]:='R';

'R':opc[b2[n]+1-j]:='L';

end;

end;

end;

h:=0;mhu:=0;mhd:=0;

w:=0;mwl:=0;mwr:=0;

for j:=1 to b2[n] do

begin

case opc[j] of

'U':dec(h);

'D':inc(h);

'L':dec(w);

'R':inc(w);

end;

if h<mhu then mhu:=h;

if h>mhd then mhd:=h;

if w<mwl then mwl:=w;

if w>mwr then mwr:=w;

end;

end;

procedure buildfig;

var

px,py:longint;

i,j:longint;

begin

if n=1 then

begin

fh:=0;

fillchar(fig,sizeof(fig),0);

fig[0]:='_|';

end else

begin

fh:=-mhu+mhd+1;

fw:=(-mwl+mwr)*2+1;

px:=-mwl*2+1;

py:=-mhu;

fillchar(fig,sizeof(fig),0);

for i:=0 to fh do

for j:=1 to fw do

begin

fig*:=fig**+' ';*

end;

for j:=1 to b2[n] do

begin

case opc[j] of

'U':begin

fig[py][px]:='|';

dec(py);

end;

'D':begin

inc(py);

fig[py][px]:='|';

end;

'L':begin

dec(px);

fig[py][px]:='_';

dec(px);

end;

'R':begin

inc(px);

fig[py][px]:='_';

inc(px);

end;

end;

end;

end;

end;

procedure out;

var

b:boolean;

l:byte;

i:longint;

begin

for i:=0 to fh do

begin

repeat

l:=length(fig*);*

if fig*[l]=' ' then fig**:=copy(fig**,1,l-1);*

until fig*[l]<>' ';*

end;

for i:=0 to fh do

begin

b:=false;

for l:=1 to length(fig*) do*

if fig[i][l]<>' ' then

begin

b:=true;

break;

end;

if b then writeln(fig[i]);

end;

writeln('^');

end;

procedure run;

begin

repeat

readdata;

if n<>0 then

begin

makeopc;

buildfig;

out;

end;

until n=0;

end;

begin

run;

end.

[/pascal]

Though my program looks stupid, but it works well on my computer!

I can't find why i got WA.

[pascal]

program acm177;

const

b2:array[1..13]of longint=(2,4,8,16,32,64,128,256,512,1024,2048,4096,8192);

var

opc:array[1..9000]of char;

n:byte;

fig:array[0..200]of string;

mhu,mhd,mwl,mwr:longint;

fh,fw:longint;

procedure readdata;

begin

readln(n);

end;

procedure makeopc;

var

i:byte;

j:longint;

tc:char;

h,w:longint;

begin

fillchar(opc,sizeof(opc),0);

opc[1]:='R';

opc[2]:='U';

if n>1 then

begin

for i:=2 to n do

begin

for j:=b2[i-1]+1 to b2

begin

case opc[b2

'U':begin

opc[j]:='L';

end;

'D':begin

opc[j]:='R';

end;

'L':begin

opc[j]:='D';

end;

'R':begin

opc[j]:='U';

end;

end;

end;

end;

for j:=1 to b2[n-1] do

begin

tc:=opc[j];

case opc[b2[n]+1-j] of

'U':opc[j]:='D';

'D':opc[j]:='U';

'L':opc[j]:='R';

'R':opc[j]:='L';

end;

case tc of

'U':opc[b2[n]+1-j]:='D';

'D':opc[b2[n]+1-j]:='U';

'L':opc[b2[n]+1-j]:='R';

'R':opc[b2[n]+1-j]:='L';

end;

end;

end;

h:=0;mhu:=0;mhd:=0;

w:=0;mwl:=0;mwr:=0;

for j:=1 to b2[n] do

begin

case opc[j] of

'U':dec(h);

'D':inc(h);

'L':dec(w);

'R':inc(w);

end;

if h<mhu then mhu:=h;

if h>mhd then mhd:=h;

if w<mwl then mwl:=w;

if w>mwr then mwr:=w;

end;

end;

procedure buildfig;

var

px,py:longint;

i,j:longint;

begin

if n=1 then

begin

fh:=0;

fillchar(fig,sizeof(fig),0);

fig[0]:='_|';

end else

begin

fh:=-mhu+mhd+1;

fw:=(-mwl+mwr)*2+1;

px:=-mwl*2+1;

py:=-mhu;

fillchar(fig,sizeof(fig),0);

for i:=0 to fh do

for j:=1 to fw do

begin

fig

end;

for j:=1 to b2[n] do

begin

case opc[j] of

'U':begin

fig[py][px]:='|';

dec(py);

end;

'D':begin

inc(py);

fig[py][px]:='|';

end;

'L':begin

dec(px);

fig[py][px]:='_';

dec(px);

end;

'R':begin

inc(px);

fig[py][px]:='_';

inc(px);

end;

end;

end;

end;

end;

procedure out;

var

b:boolean;

l:byte;

i:longint;

begin

for i:=0 to fh do

begin

repeat

l:=length(fig

if fig

until fig

end;

for i:=0 to fh do

begin

b:=false;

for l:=1 to length(fig

if fig[i][l]<>' ' then

begin

b:=true;

break;

end;

if b then writeln(fig[i]);

end;

writeln('^');

end;

procedure run;

begin

repeat

readdata;

if n<>0 then

begin

makeopc;

buildfig;

out;

end;

until n=0;

end;

begin

run;

end.

[/pascal]

Posted: **Mon Jun 24, 2002 4:56 pm**

Hi!

You have wrong output for this input:

And you have..

Try to change this and resubmit...

If you got WA again then send me your corrected code...

Good Luck

You have wrong output for this input:

I have:1

0

b --> blankb_|

^

And you have..

For the next inputs I think your program is correct..._|

^

Try to change this and resubmit...

If you got WA again then send me your corrected code...

Good Luck

Posted: **Tue Jun 25, 2002 8:38 am**

Thank you. I got Accepted.

Posted: **Mon Jul 14, 2003 2:45 pm**

you are not right

Posted: **Tue Jul 15, 2003 2:58 pm**

Would you check my output.

I think it works well, but i got WA. -_-;;;

[cpp]#include <iostream>

#include <string>

using namespace std;

int input;

string output;

char screen[1000][500];

void toscreen(string str)

{

int x, y, c1;

int xx, yy;

int maxx=0;

int maxy=0;

int minx=10000;

int miny=10000;

x=800;

y=250;

for(c1=0; c1<str.length(); c1++)

{

if(maxx<x) maxx=x;

if(maxy<y) maxy=y;

if(minx>x) minx=x;

if(miny>y) miny=y;

switch(str[c1])

{

case '1':

screen[y][x]='_';

screen[y][x+1]='|';

if(x+1>maxx) maxx=x+1;

y--;

break;

case '2':

screen[y][x+2]='_';

screen[y+1][x+3]='|';

if(y+1>maxy) maxy=y+1;

if(x+4>maxx) maxx=x+4;

x+=4;

y++;

break;

case '3':

screen[y][x]='_';

screen[y][x-1]='|';

if(x-1<minx) minx=x-1;

y--;

break;

case '4':

screen[y][x-2]='_';

screen[y+1][x-3]='|';

if(x-4<minx) minx=x-4;

if(y+1>maxy) maxy=y+1;

y++;

x-=4;

break;

}

}

if(input==5) minx++;

if(input==6) minx++;

if(input==7) minx++;

if(input==8) minx++;

if(input==9) minx++;

if(input==13) minx++;

for(yy=miny; yy<=maxy; yy++)

{

for(xx=minx; xx<=maxx; xx++)

{

cout << screen[yy][xx];

screen[yy][xx]=0;

}

cout << endl;

}

cout << "^" << endl;

}

void dragon(int level, string now)

{

int c1;

string t1=now;

if(level==input)

{

output=now;

return;

}

for(c1=now.length()-1; c1>=0; c1--)

{

switch(now[c1])

{

case '1':

t1+='3';

break;

case '2':

t1+='1';

break;

case '3':

t1+='4';

break;

case '4':

t1+='2';

break;

}

}

dragon(level+1, t1);

}

void main(void)

{

while(1)

{

cin >> input;

if(input==0) break;

output="";

dragon(1, "1");

toscreen(output);

}

}[/cpp]

I think it works well, but i got WA. -_-;;;

[cpp]#include <iostream>

#include <string>

using namespace std;

int input;

string output;

char screen[1000][500];

void toscreen(string str)

{

int x, y, c1;

int xx, yy;

int maxx=0;

int maxy=0;

int minx=10000;

int miny=10000;

x=800;

y=250;

for(c1=0; c1<str.length(); c1++)

{

if(maxx<x) maxx=x;

if(maxy<y) maxy=y;

if(minx>x) minx=x;

if(miny>y) miny=y;

switch(str[c1])

{

case '1':

screen[y][x]='_';

screen[y][x+1]='|';

if(x+1>maxx) maxx=x+1;

y--;

break;

case '2':

screen[y][x+2]='_';

screen[y+1][x+3]='|';

if(y+1>maxy) maxy=y+1;

if(x+4>maxx) maxx=x+4;

x+=4;

y++;

break;

case '3':

screen[y][x]='_';

screen[y][x-1]='|';

if(x-1<minx) minx=x-1;

y--;

break;

case '4':

screen[y][x-2]='_';

screen[y+1][x-3]='|';

if(x-4<minx) minx=x-4;

if(y+1>maxy) maxy=y+1;

y++;

x-=4;

break;

}

}

if(input==5) minx++;

if(input==6) minx++;

if(input==7) minx++;

if(input==8) minx++;

if(input==9) minx++;

if(input==13) minx++;

for(yy=miny; yy<=maxy; yy++)

{

for(xx=minx; xx<=maxx; xx++)

{

cout << screen[yy][xx];

screen[yy][xx]=0;

}

cout << endl;

}

cout << "^" << endl;

}

void dragon(int level, string now)

{

int c1;

string t1=now;

if(level==input)

{

output=now;

return;

}

for(c1=now.length()-1; c1>=0; c1--)

{

switch(now[c1])

{

case '1':

t1+='3';

break;

case '2':

t1+='1';

break;

case '3':

t1+='4';

break;

case '4':

t1+='2';

break;

}

}

dragon(level+1, t1);

}

void main(void)

{

while(1)

{

cin >> input;

if(input==0) break;

output="";

dragon(1, "1");

toscreen(output);

}

}[/cpp]

Posted: **Tue Nov 16, 2004 7:07 am**

Are you sure you clearly understand what problem 177 asked for?

Posted: **Sun Jan 09, 2005 12:20 pm**

Try to check your output with a hex editor...

Posted: **Tue Mar 01, 2005 3:40 am**

Hi,

Can someone please explain me what this problem really wants. Several of my efforts just to match the sample output were turned into failure.

Can someone please explain me what this problem really wants. Several of my efforts just to match the sample output were turned into failure.

Posted: **Tue Aug 09, 2005 12:44 pm**

I am also facing major problems in understanding the problem..

.. some explanation might get me started on this one.

.. some explanation might get me started on this one.

Posted: **Wed Aug 10, 2005 11:29 am**

Hi,

Even though I haven't solved it yet, I can explain the problem for N=4.

Get a 8 X 11.5 paper and put in on the table. Orientation doesn't matter but don't rotate the paper after any folds.

Okay, now take the right side and fold it in half onto the left side.

Now the paper is 1/2 it's original size.

Now take the right side again and fold it in halft onto the left side.

Now the paper is 1/4 it's original size.

Now take the right side again and fold it in halft onto the left side.

Now the paper is 1/8 it's original size.

Now take the right side again and fold it in halft onto the left side.

Now the paper is 1/16 it's original size.

Finally, pick up the paper so that the smallest flat edge is facing you (you will have do some rotations).

This is equivalent to looking at a cylinder and wanting the circular area facing you.

Carefully unfold the paper and keep the unfolding edges at right angles.

Do this unfolding 4 times.

You should get something like a zig-zag in the same input.

Hope this helps.

Even though I haven't solved it yet, I can explain the problem for N=4.

Get a 8 X 11.5 paper and put in on the table. Orientation doesn't matter but don't rotate the paper after any folds.

Okay, now take the right side and fold it in half onto the left side.

Now the paper is 1/2 it's original size.

Now take the right side again and fold it in halft onto the left side.

Now the paper is 1/4 it's original size.

Now take the right side again and fold it in halft onto the left side.

Now the paper is 1/8 it's original size.

Now take the right side again and fold it in halft onto the left side.

Now the paper is 1/16 it's original size.

Finally, pick up the paper so that the smallest flat edge is facing you (you will have do some rotations).

This is equivalent to looking at a cylinder and wanting the circular area facing you.

Carefully unfold the paper and keep the unfolding edges at right angles.

Do this unfolding 4 times.

You should get something like a zig-zag in the same input.

Hope this helps.

Posted: **Sat May 06, 2006 6:33 am**

That's kind of mean.

Posted: **Sat Jul 08, 2006 7:39 pm**

HINT:

List down the direction of each step for N=1.

List down the direction of each step for N=2.

You will see an obvious recursive pattern.

List down the direction of each step for N=1.

List down the direction of each step for N=2.

You will see an obvious recursive pattern.

Posted: **Thu Jul 13, 2006 11:03 am**

The picture you are asked to draw in this problem is actually a fractal, known as the dragon curve in the world of fractal geometry. Fractal geometry has very neat and clean techinque for drawing this figure. One way is to consider it as a input string for some context sensitive grammer and evaluate the string n times. another way is to use turtle geometry.

a lot more than enough hints given.

a lot more than enough hints given.

Posted: **Fri Jul 14, 2006 3:35 am**

Were we supposed to know this to solve the problem?Raiyan Kamal wrote:The picture you are asked to draw in this problem is actually a fractal, known as the dragon curve in the world of fractal geometry. Fractal geometry has very neat and clean techinque for drawing this figure. One way is to consider it as a input string for some context sensitive grammer and evaluate the string n times. another way is to use turtle geometry.