177 - Paper Folding

[Sherman MXF]

Is there any trap in it?
I've checkmy output carefully for over 100 times, why i still got WA?

[Sherman MXF]

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]

[cyfra]

Hi!

You have wrong output for this input:

1
0

I have:

b_|
^

b --> blank
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

[Sherman MXF]

Thank you. I got Accepted.

[miras]

you are not right

[Park, Kwang-Kyu]

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]

[yellow]

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

[stubbscroll]

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

[Mohammad Mahmudur Rahman]

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.

[sohel]

I am also facing major problems in understanding the problem..
.. some explanation might get me started on this one.

[daveon]

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.

[Quantris]

That's kind of mean.

[daveon]

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.

[Raiyan Kamal]

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.

[daveon]

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.

Were we supposed to know this to solve the problem?