谷歌承诺 “building for everyone”。

Code Jam to I/O for Women 是谷歌提供的一个平台和机会，让全球顶尖的程序媛们华山论剑！

Code Jam to I/O for Women 是一个单轮的在线算法挑战！全球排名前 150 名的参与者，就有机会获得一张年度 Google I/O 大会的门票（包差旅）哦！！

# code jam to i/O for Women 2019题解

## Grid Escape

### Problem

You are designing a new “escape” adventure that uses a rectangular grid of rooms (unit cells) with R rows and C columns. Each room has four doors oriented in the four orthogonal directions of the grid: north, south, east, and west. The doors on the border of the grid lead outside, and all of the other doors lead to other rooms.

The adventure will be played by exactly R × C players, with each player starting in a different one of the R × C rooms. Once everyone is in position and the game starts, all of the doors close, and there is a mechanical trick: one of the four doors in each room can be opened from inside the room, and the other three doors cannot be opened. This remains consistent throughout the adventure; in a given room, it is always the same door that can be opened. Notice that it is possible that a door that connects two rooms might be able to be opened from one side but not the other.

Each player moves independently of all other players. Players can only go through doors that they opened themselves, and they must close doors behind them. Each player will keep going through doors until they go through a door that leads outside (and therefore they escape), or they have made R × C moves without escaping (at which point they are considered to have failed, and they do not escape).

You want to choose which door in each room can be opened, such that exactly K of the players will be able to escape. Can you find a way to do this, or determine that it is IMPOSSIBLE?

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line containing three integers R, C, and K, as described above.

### Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is IMPOSSIBLE if there is no solution, or POSSIBLE if there is. If there is a solution, output R more lines of C characters each, representing the grid of rooms. The j-th character on the i-th of these lines represents the room in the i-th row and j-th column of the grid; each character must be either uppercase N, S, E, or W, according to whether the door that opens from that room is the one that leads north, south, east, or west.

If multiple answers are possible, you may output any one of them.

### Limits

1 ≤ T ≤ 100.

#### Time limit:

20 seconds per test set. (10 seconds per test run.)

#### Memory limit:

1GB.

1 ≤ R.

1 ≤ C.

0 ≤ K ≤ R × C.

Test set 1 (Visible)

1 ≤ (R × C) ≤ 8.

Test set 2 (Hidden)

1 ≤ (R × C) ≤ 100.

### Sample

Input

```
2
2 3 2
1 1 0
```

Output

```
Case #1: POSSIBLE
SES
SNW
Case #2: IMPOSSIBLE
```

In our solution for Sample Case #1, the two players who start in the westernmost two rooms will go south until they escape, whereas the four players who start in the other four rooms will travel between those rooms in an endless clockwise circle and cannot escape.

In Sample Case #2, there is only one room, so the player can definitely escape regardless of which particular door can be opened.

### 解题思路

这是一道构造题。每个人构造方式必然不尽相同，分享一下我的思路吧。

首先我们需要明确什么时候直接输出IMPOSSIBLE。一开始我以为只有1 1 0才满足这个条件。但是后来在写构造的过程中我发现只要满足条件C*W-k==1的，都是不能够构造出来的。

采用反证法，假设C*W-k==1可以构造，即所有格子只有一个格子不能逃脱。那这个格子不管开哪扇门，必然都可以进入可逃脱区，与已知不能逃脱相悖。因此C*W-k==1是不能被构造的。

那么我们可以从后往前对格子进行可逃脱赋值。最后一排格子标记为’E’,剩余只需要标记为’S’，即可从右下角离开。完成这部分标记后，需对剩余格子进行一遍搜索配对。

如果我们选取两个相邻格子，让他们可以开启同一扇门（即相邻边），则这两个格子都无法逃脱，陷入死循环。因此剩余偶数个格子时随意搜索应该都可以配对成功。

如果剩余奇数格子时，则只需要将最后三个格子配对，也可以形成死循环。

代码如下：

```
#include<bits/stdc++.h>
#define ll long long
#define U unsigned
#define sqr(x) ((x)*(x))
#define mem(x,y) memset(x,y,sizeof(x))
#define scd(x) scanf("%d",&x)
#define scs(x) scanf("%s",&x)
#define prd(x) printf("%d",x)
#define prs(x) printf("%s",x)
#define rep(x,a,b) for(int x=a;x<b;x++)
#define rep0(x,n) for(int x=0;x<n;x++)
#define rep1(x,n) for(int x=1;x<=n;x++)
#define per(x,a,b) for(int x=a;x>=b;x--)
#define ls rt<<1
#define rs rt<<1|1
#define lson l,m,ls
#define rson m+1,r,rs
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
const int INF=0x3f3f3f3f;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
char a[105][105];
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t;
cin>>t;
for(int i=1;i<=t;i++)
{
int r,c,k;
cin>>r>>c>>k;
if(r*c-k==1)
cout<<"Case #"<<i<<": IMPOSSIBLE"<<endl;
else
{
int x=r*c;
cout<<"Case #"<<i<<": POSSIBLE"<<endl;
for(int j=1;j<=r;j++)
{
for(int m=1;m<=c;m++)
{
a[j][m]=' ';
}
}
for(int j=0;j<k;j++)
{
if((x-1)/c==r-1)
{
a[r][x%c==0?c:x%c]='E';
}
else
{
a[(x-1)/c+1][x%c==0?c:x%c]='S';
}
x--;
}
for(int j=1;j<=r;j++)
{
for(int m=1;m<=c;m++)
{
if(a[j][m]==' ')
{
if(a[j+1][m]==' ')
{
a[j][m]='S';
a[j+1][m]='N';
}
else if(a[j][m+1]==' ')
{
a[j][m]='E';
a[j][m+1]='W';
}
else
{
if(j>1) a[j][m]='N';
else if(m>1) a[j][m]='W';
}
}
}
}
for(int j=1;j<=r;j++)
{
for(int m=1;m<=c;m++)
{
cout<<a[j][m];
}
cout<<endl;
}
}
}
return 0;
}
```

## Parcel Posts

### Problem

You just bought a parcel of land that is K kilometers long; it is so narrow that, for the purposes of this problem, we will consider it to be a polyline that runs from west to east, varying in elevation. You know the elevations of the land (in meters) at K + 1 regularly spaced measurement marks M0, M1, …, MK. These marks are 0, 1, …, K km, respectively, from the western end.

In this region, a wooden post denotes the boundary between two adjacent parcels of land. Wooden posts can only be placed at measurement marks, and there can be at most one post at each mark. Right now, there are two posts: one at the 0 km mark, and one at the K km mark. A measurement mark with a post is considered to be part of both of the parcels it demarcates, so your parcel of land includes all measurement marks between 0 and K km, inclusive.

A parcel is considered desirable if it contains three measurement marks such that the west-most and east-most of those three marks are both strictly higher than the remaining one of the three marks, or both strictly lower than the remaining one of the three marks. People like some variation in their landscapes! Notice that these three marks are not necessarily consecutive, and the west-most and east-most of the three marks are not necessarily the west-most and east-most marks of the parcel.

Consider an example with K = 5 and M0, M1, …, MK = 5, 6, 6, 1, 2, 4. The measurement marks with elevations 5, 2, and 4 satisfy the condition, as do the measurement marks with elevations 6, 1, and 2. However, the measurement marks with elevations 6, 6, and 1 do not satisfy the condition, nor do the measurement marks with elevations 1, 2, and 4. Any three measurement marks that satisfy the condition make the whole parcel desirable; for example, a parcel containing the measurement marks 4 7 6 7 is desirable because of the first three values.

Your parcel is desirable, but you think it may be possible to extract even more value from it! You want to add additional posts to this parcel to divide it up into multiple parcels, all of which must be desirable, since you do not want to waste any land. What is the largest number of posts you can add?

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with one line containing an integer K: the length, in kilometers, of your parcel of land. Then, there is one more line with K + 1 integers M0, M1, …, Mk; where Mi is the elevation (in meters) at the measurement mark that is i km from the western end of your land.

### Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the largest possible number of posts you can add, as described above.

### Limits

#### Time limit:

20 seconds per test set. (10 seconds per test run.)

#### Memory limit:

1GB.

1 ≤ T ≤ 100.

0 ≤ Mi ≤ 1000, for all i.

(Mi - Mj) × (Mk - Mj) > 0, for some i < j < k. (Your starting parcel is desirable.)

Test set 1 (Visible)

4 ≤ K ≤ 10.

Test set 2 (Hidden)

4 ≤ K ≤ 1000.

### Sample

Input

```
4
4
4 8 7 3 5
4
4 8 7 7 5
7
1 2 2 1 2 1 2 1
6
2 1 3 10 9 12 20
```

Output

```
Case #1: 1
Case #2: 0
Case #3: 2
Case #4: 1
```

In Sample Case #1, you can add one post at 2 km to get a total of two desirable parcels. The parcel from 0 to 2 km is desirable because 4 < 8 and 8 > 7. The parcel from 2 to 4 km is desirable because 7 > 3 and 3 < 5.

In Sample Case #2, there is no way to add another post. If you added one at 1 km or 3 km, one of the parcels would include only two measurement marks and could not be desirable. If you added one at 2 km, the parcel between 0 and 2 km would be desirable, but the parcel between 2 and 4 km would not.

In Sample Case #3, posts can be added at 3 km and 5 km.

In Sample Case #4, a post can be added at 2 km. Notice that the parcel from 2 km to 6 km is desirable because 10 > 9 and 9 < 12. However, there is no way to add a second post.

### 解题思路

我真的没想到……就是个暴力（努力想了半天发现数据小，而且！给了20s！！！绝了。这大概也是跟codeforces最大的不同吧，无法想象codeforces给20s是一种怎样的体验。）

首先我们要明确题意（这题目真的非常绕），实质是问你最多能将数组w划定多少个区间，使得每个区间内存在i<j<k，且w[i]<w[j],w[k]<w[j],或者w[i]>w[j],w[k]>w[j]。

那么我们可以通过枚举区间的右端点，极端暴力是O(n^3)，二分优化可以做到O(n^2logn)。但是题目时限非常宽，所以就直接暴力了。

```
#include<bits/stdc++.h>
#define ll long long
#define U unsigned
#define sqr(x) ((x)*(x))
#define mem(x,y) memset(x,y,sizeof(x))
#define scd(x) scanf("%d",&x)
#define scs(x) scanf("%s",&x)
#define prd(x) printf("%d",x)
#define prs(x) printf("%s",x)
#define rep(x,a,b) for(int x=a;x<b;x++)
#define rep0(x,n) for(int x=0;x<n;x++)
#define rep1(x,n) for(int x=1;x<=n;x++)
#define per(x,a,b) for(int x=a;x>=b;x--)
#define ls rt<<1
#define rs rt<<1|1
#define lson l,m,ls
#define rson m+1,r,rs
using namespace std;
const double eps=1e-8;
const double pi=acos(-1.0);
const int INF=0x3f3f3f3f;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
int m[1005];
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int t;
cin>>t;
for(int temp=1;temp<=t;temp++)
{
int k;
cin>>k;
for(int i=0;i<=k;i++) cin>>m[i];
int ans=0,i,j;
for(i=0;i<=k;i=j)
{
for(j=i+2;j<=k;j++)
{
int flag=0;
for(int x=i+1;x<j;x++)
{
if((m[x]>m[i]&&m[x]>m[j])||(m[x]<m[i]&&m[x]<m[j]))
{
ans++;
flag=1;
break;
}
}
if(flag) break;
}
}
cout<<"Case #"<<temp<<": "<<ans-1<<endl;
}
return 0;
}
```

## Sheepwalking

### Problem

Bleatrix Trotter is a sheep who lives in a two-dimensional field that is an infinite grid of unit cells. Her home is in a unit cell that we denote as (0, 0) — that is, all coordinates are given relative to Bleatrix’s home cell. However, because she has been sleepwalking, she is currently in the unit cell at the coordinates (X, Y) — that is, in a cell X columns east of, and Y rows north of, her home cell. The two sheepdogs who have been assigned to protect Bleatrix have just noticed that she is missing, and now they want to herd her back to her home cell.

Before each of Bleatrix’s moves, the two sheepdogs can move to any grid cells that they want, except that they cannot both move to the same cell, and neither one can move to Bleatrix’s current cell. Once the sheepdogs are in place, Bleatrix, who is sleepwalking, will make a random unit move in a direction that would not take her into a cell with a sheepdog. That is, she takes the set of four possible unit moves (north, south, west, east), discards any that would move her into a cell with a sheepdog, and then chooses uniformly at random from the remaining moves. Then the sheepdogs can position themselves again, and so on (notice that, unlike Bleatrix, the sheepdogs do not have to make unit moves).

Once Bleatrix arrives at her home at (0, 0), she stops sleepwalking, wakes up, and grazes peacefully, and does not make any more moves thereafter.

If the sheepdogs coordinate their movements to minimize the expected number of Bleatrix’s moves to reach her home, what is that expected number?

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each case consists of one line with two integers X and Y, representing the coordinates of Bleatrix’s starting cell, as described above.

### Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the expected number of Bleatrix’s moves, as described above. y will be considered correct if it is within an absolute or relative error of 10-6 of the correct answer. See the Competing section of the FAQ for an explanation of what that means, and what formats of real numbers we accept.

### Limits

#### Time limit:

20 seconds per test set. (10 seconds per test run.)

#### Memory limit:

1GB.

(X, Y) ≠ (0, 0).

Test set 1 (Visible)

1 ≤ T ≤ 48.

-3 ≤ X ≤ 3.

-3 ≤ Y ≤ 3.

Test set 2 (Hidden)

1 ≤ T ≤ 100.

-500 ≤ X ≤ 500.

-500 ≤ Y ≤ 500.

### Sample

Input

```
1
-1 1
```

Output

```
Case #1: 4.000000
```

Notice that the values of X and/or Y may be negative. An X value of -1, for example, means that the cell is one unit west of Bleatrix’s home cell. (Similarly, a negative value of Y means the cell is south of Bleatrix’s home cell.)

In the sample case, Bleatrix starts off one cell to the north of, and one cell to the west of, her home. Before she makes her first move, the two sheepdogs could position themselves in cells (-2, 1) and (-1, 2). Then, whichever direction she might choose, she would end up only one step away from her home… but the sheepdogs could not guarantee that she would go there on her next move! The remaining details are left for you to discover.