177 - Paper Folding

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

P177

Post by Sherman MXF » 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?

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

P177 WA

Post by Sherman MXF » 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]

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

Hi!

Post by cyfra » Mon Jun 24, 2002 4:56 pm

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 :wink:

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

Post by Sherman MXF » Tue Jun 25, 2002 8:38 am

Thank you. I got Accepted.
:) :)

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Mon Jul 14, 2003 2:45 pm

you are not right

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

177 WA

Post by Park, Kwang-Kyu » 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]

yellow
New poster
Posts: 9
Joined: Tue Oct 26, 2004 6:26 am

Post by yellow » Tue Nov 16, 2004 7:07 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:

Post by stubbscroll » Sun Jan 09, 2005 12:20 pm

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

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

177 - Paper Folding

Post by Mohammad Mahmudur Rahman » 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. :cry:
You should never take more than you give in the circle of life.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » 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.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » 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.

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

Post by Quantris » Sat May 06, 2006 6:33 am

That's kind of mean.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » 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.

Raiyan Kamal
Experienced poster
Posts: 106
Joined: Thu Jan 29, 2004 12:07 pm
Location: Bangladesh
Contact:

Post by Raiyan Kamal » 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. ;)

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Fri Jul 14, 2006 3:35 am

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.
Were we supposed to know this to solve the problem?

Post Reply

Return to “Volume 1 (100-199)”