## 177 - Paper Folding

Moderator: Board moderators

Sherman MXF
New poster
Posts: 14
Joined: Sun May 26, 2002 1:54 pm
Location: China

### P177

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

Sherman MXF
New poster
Posts: 14
Joined: Sun May 26, 2002 1:54 pm
Location: China

### P177 WA

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;

begin
end;

procedure makeopc;
var
i:byte;
j:longint;
tc:char;
h,w:longint;
begin
fillchar(opc,sizeof(opc),0);
opc:='R';
opc:='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:='_|';
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
if n<>0 then
begin
makeopc;
buildfig;
out;
end;
until n=0;
end;

begin
run;
end.
[/pascal]

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

### Hi!

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
New poster
Posts: 14
Joined: Sun May 26, 2002 1:54 pm
Location: China
Thank you. I got Accepted.  miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
you are not right

Park, Kwang-Kyu
New poster
Posts: 2
Joined: Tue Jul 15, 2003 2:49 pm

### 177 WA

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;

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
New poster
Posts: 9
Joined: Tue Oct 26, 2004 6:26 am
Are you sure you clearly understand what problem 177 asked for?

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:
Try to check your output with a hex editor...

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

### 177 - Paper Folding

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. You should never take more than you give in the circle of life.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
I am also facing major problems in understanding the problem..
.. some explanation might get me started on this one.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 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.

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
That's kind of mean.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
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
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
a lot more than enough hints given. 