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;
}

1. 等房地产势头过去，农民工大叔们以踏实肯干的态度，转战现代化农业生产和加工，你坐在房子里，感叹没有自己的土地。。。

2. 对面笑容灿烂的银发少年手中提着一筐仙桃，“我当然是来看你的啊！我手上的这一筐仙桃可是王母特意差人送我的，五百年才结一果可

3. 对面笑容灿烂的银发少年手中提着一筐仙桃，“我当然是来看你的啊！我手上的这一筐仙桃可是王母特意差人送我的，五百年才结一果可

4. 对面笑容灿烂的银发少年手中提着一筐仙桃，“我当然是来看你的啊！我手上的这一筐仙桃可是王母特意差人送我的，五百年才结一果可

5. 对面笑容灿烂的银发少年手中提着一筐仙桃，“我当然是来看你的啊！我手上的这一筐仙桃可是王母特意差人送我的，五百年才结一果可

6. 对面笑容灿烂的银发少年手中提着一筐仙桃，“我当然是来看你的啊！我手上的这一筐仙桃可是王母特意差人送我的，五百年才结一果可

7. 对面笑容灿烂的银发少年手中提着一筐仙桃，“我当然是来看你的啊！我手上的这一筐仙桃可是王母特意差人送我的，五百年才结一果可

8. 对面笑容灿烂的银发少年手中提着一筐仙桃，“我当然是来看你的啊！我手上的这一筐仙桃可是王母特意差人送我的，五百年才结一果可

9. 对面笑容灿烂的银发少年手中提着一筐仙桃，“我当然是来看你的啊！我手上的这一筐仙桃可是王母特意差人送我的，五百年才结一果可

10. 对面笑容灿烂的银发少年手中提着一筐仙桃，“我当然是来看你的啊！我手上的这一筐仙桃可是王母特意差人送我的，五百年才结一果可

11. 对面笑容灿烂的银发少年手中提着一筐仙桃，“我当然是来看你的啊！我手上的这一筐仙桃可是王母特意差人送我的，五百年才结一果可

12. 对面笑容灿烂的银发少年手中提着一筐仙桃，“我当然是来看你的啊！我手上的这一筐仙桃可是王母特意差人送我的，五百年才结一果可

13. 对面笑容灿烂的银发少年手中提着一筐仙桃，“我当然是来看你的啊！我手上的这一筐仙桃可是王母特意差人送我的，五百年才结一果可