2014
03-31

# Chinese Paper Folding

Chinese Paper Folding, or Zhezhi, is the art of folding paper that originated in China. It is the predecessor of origami.

Here we only consider a simplified problem. You are given a paper L cm by W cm in size and a list of operations to fold it.

Four types of operation are listed below:
1.  L v , fold the left part of paper along the straight line x = v.
2.  R v , fold the right part of paper along the straight line x = v.
3.  U v , fold the upper part of paper along the straight line y = v.
4.  D v , fold the lower part of paper along the straight line y = v.
Note that v is always an integer.

We define the left-lower corner of current paper as (0, 0) at every step (refer to the picture below). It is guaranteed that each operation is legal, that is, each operation is asked to fold paper of a positive area.

It is obvious that folding will make the straight lines into creases. We wonder the total length of all creases when paper is completely unfolded.

In the first line there is an integer T, indicates the number of test cases. (T <= 50)

For each case, the first line is a pair of integers L and W (1 <= L, W <= 1,000,000), which stands for the length and width of the paper. In the second line, an integer K stands for the number of operations. (K <= 100000) Then K lines follow, each stands for an operation described above.

In the first line there is an integer T, indicates the number of test cases. (T <= 50)

For each case, the first line is a pair of integers L and W (1 <= L, W <= 1,000,000), which stands for the length and width of the paper. In the second line, an integer K stands for the number of operations. (K <= 100000) Then K lines follow, each stands for an operation described above.

2
50 50
4
L 30
D 5
R 3
U 5
65536 1
16
L 32768
L 16384
R 8192
R 4096
L 2048
R 1024
L 512
R 256
R 128
L 64
R 32
R 16
L 8
R 4
L 2
R 1

Case 1: 250
Case 2: 65535

#include <stdio.h>
#include <cstring>
#include <algorithm>
#define maxn 1000010
using namespace std;

typedef long long LL;

int width,height,n;
int L,R,U,D,v;
bool diffx,diffy;
int idx[maxn],idy[maxn];
char ch[10];

void init(int id[],int n)
{
id[0]=id[n]=0;
for (int i=1;i<n;i++)
id[i]=1;
}

int fold(int id[], int &L, int &R, int v, bool &diff)
{
bool dir=false;
int ret;
v+=L;
ret=id[v];
if (abs(L-v)>abs(R-v)) diff=!diff,dir=true;
for (int x=v,y=v;x!=L&&y!=R;x--,y++)
{
if (!dir)
{
id[y]+=id[x];
id[x]=0;
}
else
{
id[x]+=id[y];
id[y]=0;
}
}
if (!dir) L=v;
else R=v;
return ret;
}

int main()
{
int test;
scanf("%d",&test);
for (int ii=1;ii<=test;ii++)
{
scanf("%d%d",&width,&height);
scanf("%d",&n);
diffx=diffy=0;
L=D=0;U=height;R=width;
init(idx,width);
init(idy,height);
LL ans=0;
for (int i=1;i<=n;i++)
{
scanf("%s%d",ch,&v);
if (ch[0]=='L'||ch[0]=='R')
{
if (diffx) v=R-L-v;
if (!diffx && ch[0]=='R') diffx=!diffx;
if (diffx && ch[0]=='L') diffx=!diffx;
ans+=(LL)height*fold(idx, L, R, v, diffx);
}
else
{
if (diffy) v=U-D-v;
if (!diffy && ch[0]=='U') diffy=!diffy;
if (diffy && ch[0]=='D') diffy=!diffy;
ans+=(LL)width*fold(idy, D, U, v, diffy);
}
}
printf("Case %d: %I64d\n",ii,ans);
}
return 0;
}