Page 1 of 2

P177

Posted: Tue Jun 18, 2002 4:00 am
by Sherman MXF
Is there any trap in it?
I've checkmy output carefully for over 100 times, why i still got WA?

P177 WA

Posted: Thu Jun 20, 2002 2:02 am
by 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]

Hi!

Posted: Mon Jun 24, 2002 4:56 pm
by 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 :wink:

Posted: Tue Jun 25, 2002 8:38 am
by Sherman MXF
Thank you. I got Accepted.
:) :)

Posted: Mon Jul 14, 2003 2:45 pm
by miras
you are not right

177 WA

Posted: Tue Jul 15, 2003 2:58 pm
by 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]

Posted: Tue Nov 16, 2004 7:07 am
by yellow
Are you sure you clearly understand what problem 177 asked for?

Posted: Sun Jan 09, 2005 12:20 pm
by stubbscroll
Try to check your output with a hex editor...

177 - Paper Folding

Posted: Tue Mar 01, 2005 3:40 am
by 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. :cry:

Posted: Tue Aug 09, 2005 12:44 pm
by sohel
I am also facing major problems in understanding the problem..
.. some explanation might get me started on this one.

Posted: Wed Aug 10, 2005 11:29 am
by 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.

Posted: Sat May 06, 2006 6:33 am
by Quantris
That's kind of mean.

Posted: Sat Jul 08, 2006 7:39 pm
by 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.

Posted: Thu Jul 13, 2006 11:03 am
by 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. ;)

Posted: Fri Jul 14, 2006 3:35 am
by daveon
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?