TopCoder SRM 573 - 850: WolfPack

Problem Statement

有n (n <= 50) 个点，每个点每秒钟可以向上下左右移动一单位，
要求m(m <= 100000) 秒后所有点到同一点。求所有行动方案。

Wolf Sothe is a member of the wolf pack called Grid Walkers. The N wolves in the pack are numbered 0 through N-1. (Wolf Sothe is the wolf number 0, but this does not matter.)

At any moment, each wolf is located at some grid point in the plane. Multiple wolves may share the same grid point. For each i, the wolf number i is initially located at (x[i],y[i]). Then there are exactly m rounds in which the wolves move. In each round, each wolf must move from its current grid point to one of the four adjacent grid points. More precisely, the wolf located at (i,j) has to move to (i+1,j), (i-1,j), (i,j+1), or (i,j-1).

The wolves have a goal: all of them have to be located at the same grid point after the m-th round. The grid point at which they all meet is not given - they can choose any grid point.

You are given the int[]s x and y, and the int m. Count and return the number of ways in which the wolves can reach their goal, modulo 1,000,000,007. Two ways of reaching the goal are different if in some round the same wolf moves in a different direction. (Equivalently, two ways of reaching the goal are different if there is some number of rounds x and a wolf y such that the grid point of the wolf y after x rounds of the first way differs from the grid point of the wolf y after x rounds of the second way.)

Definition

Class WolfPack
Method calc
Parameters vector<int> , vector<int> , int
Returns int
Method signature int calc(vector<int> x, vector<int> y, int m)

(be sure your method is public)

Limits

Time limit (s) 2.000
Memory limit (MB) 64

Constraints

x will contain between 2 and 50 elements, inclusive.
y will contain the same number of elements as x.
m will be between 1 and 100,000, inclusive.
Each element of x and y will be between -100,000 and 100,000, inclusive.
The points (x[i],y[i]) will be pairwise distinct.

Test cases

input
- x { 3, 5 }
- y { 0, 0 }
- m 1
output
Returns 1

note

There are two wolves: one at (3,0) and the other at (5,0). There will be 1 round of movement. Thus, the meeting point has to be (4,0), wolf 0 has to move by (+1,0) and wolf 1 by (-1,0). This is the only way of reaching the goal.
input
- x { 0, 0 }
- y { 0, 1 }
- m 1
output
Returns 0

note

In this case the two wolves cannot be at the same grid point at the end. Note that they both have to move.
input
- x { 0, 2, 4 }
- y { 0, 0, 0 }
- m 2
output
Returns 4

note

In this case, the meeting point has to be (2,0). Wolf 0 has to go (0,0) -> (1,0) -> (2,0). Wolf 2 has to go (4,0) -> (3,0) -> (2,0). Wolf 1 has 4 possible ways of reaching the meeting point: in the first step he can choose any direction, and in the second step he will then choose the opposite direction.
input
- x { 7, 8 }
- y { 8, 7 }
- m 1
output
Returns 2

note

This time there are two possible meeting points. For each of them there is a unique way in which the wolves can reach it.
input
- x { -2, -2, -2, 0, 0, 0, 2, 2, 2 }
- y { -2, 0, 2, -2, 0, 2, -2, 0, 2 }
- m 1000
output
Returns 387540818

back to the menu

SRM 573 1 850 WolfPack

Problem Statement

Definition

Limits

Constraints

Test cases