Untitled

// Turn Over Game
As in , there is a 4×4 sized table. In a grid of the table, there are white or black stones. When you choose a position of stone randomly, the stone and four stones adjacent to the up, down, left and right sides of the stone will turn to the opposite color like turning a white stone to a black & a black stone to a white. Let’s suppose this process as a calculation.

Using such a calculation, you want to change all the stones on the table into all whites or all blacks. Find out the minimum operation count at this time.

Time limit: 1 second (java: 2 seconds)

[Input]
Several test cases can be included in the inputs. T, the number of cases is given in the first row of the inputs. After that, the test cases as many as T (T ≤ 30) are given in a row.
Table info is given without blank over four rows per each test case. Colors are indicated like white for ‘w’ and black for ‘b’.

[Output]
Output the minimum operation count to change all colors as white or black on the first row per each test case. If not possible, output "impossible" .

[I/O Example]
Input
2
bwwb
bbwb
bwwb
bwww
bwbw
wwww
bbwb
bwwb

Output
Case #1

Case #2
impossible

//Painting

The design team at SAMSUNG Electronics considers an innovative design for a new product.

The left figure is the basic diagram and the design team tries to distinguish each area marked by letter of the alphabet with four colors.

When proceeding with this, the design team pursues perfection by researching the combinations of all colors and chooses one of them.

However, they have trouble because they do not know the total number of cases of the color combinations.

Due to this difficulty, you convert the basic diagram on the left to the graph in the center and then you solve the problem by converting it to the adjacency matrix on the right.

The number of cases is 264.

What is the method used to solve this? (Time Limit : 2 seconds)

[Input]

The adjacency matrix about a basic diagram is entered.

On the first line, the number of the test cases (1<=T <= 10) is given.

On the first line of each test case, the size of the matrix n (1<=n <= 30, n is the positive number).

From the second line, the values of matrix are entered by being distinguished as one blank or other.

[Output]

For each test case, you should print "Case #T" in the first line where T means the case number.
In the second line, print out the total number of cases to paint and distinguish them with four colors for each area.

[Sample Input ]

0 0 0 1

1 1 1 0

0 1 1 1 0

1 0 0 1 1

1 0 0 1 0

1 1 1 0 1

0 1 0 1 0

0 1 0 0 1 0 1

1 0 1 0 1 0 0

0 1 0 1 1 0 0

0 0 1 0 1 1 0

1 1 1 1 0 1 1

0 0 0 1 1 0 1

1 0 0 0 1 1 0

[Sample Output]

Case #1
108

Case #2
96

Case #3
264

//Score
Có N vị giám khảo trong kỳ thi chọn đội tuyển tin học. Kỳ thi bao gồm K bài. Vị giám khảo thứ i đề nghị số điểm của bài j là Aịj.

Hội đồng giám khảo muốn xác định số điểm cho mỗi bài sao cho:

Tổng số điểm bằng S.

Điểm của mỗi bài không bé hơn điểm của bài trước đó.

Số điểm của mỗi bài bằng điểm đề nghị cho bài này của một vị giám khảo nào đó.

Input

Dòng đầu tiên chứa số nguyên T là số testcase (T ≤ 100). Trong đó mỗi testcase sẽ chứa:

Dòng đầu chứa ba số nguyên S, K, N (1 ≤ S ≤ 200), (1 ≤ K ≤ 20), (1 ≤ N ≤ 20).

Dòng thứ i trong số N dòng tiếp theo chứa K số nguyên, số thứ j cho biết giá trị Aij là số điểm vị giám khảo thứ i đề nghị cho bài thứ j. (1 ≤ Aij ≤ 100),

Output

Kết quả của mỗi testcase sẽ được in theo định dạng sau:

Dòng đầu tiên là: “Case number_testcase”

Nếu tồn tại một cách cho điểm thỏa mãn yêu cầu in ra số trường hợp thỏa mãn.

Nếu không tồn tại cách cho điểm, in ra -1.

Sample

Input

100 3 2

30 20 40

50 30 50

100 2 3

1 1

2 2

3 3

Output

Case 1

Case 2

-1

//Nâng cấp máy tính
Time limit: 1 giây với C/C++, 2 giây với Java.

Submission limit: 5 lần.

Memory limit: 256MB cho tổng cộng các vùng nhớ heap, global và static (chỉ 1MB cho vùng nhớ stack).

Anh Kim có 1 máy tính đã mua từ thời sinh viên nên hiện giờ cần phải nâng cấp và thay thế L linh kiện để đảm bảo máy tính hoạt động tốt.

Để tìm mua được các thiết bị đó với giá tốt nhất anh Kim đã qua chợ Trời và tham khảo được giá của tất cả N thiết bị của máy tính.

Không chỉ thế, anh đã tìm kiếm thêm trên mạng, và anh rất vui khi có M gói ưu đãi giá rẻ được rao bán trên mạng, mỗi gói có giá bán là P bao gồm K thiết bị của máy tính.

Anh Kim có thể mua một hoặc nhiều gói ưu đãi và có thể mua thừa linh kiện chưa cần thay thế.

Hãy giúp anh Kim mua được đủ L thiết bị cần thiết với tổng giá thành là nhỏ nhất.

Input

Dòng đầu tiên là số lượng test case T (T <= 50).

Mỗi test case gồm các thông tin sau:

- Dòng đầu tiên là số nguyên dương N (1 <= N <= 20) là số lượng thiết bị chính của máy tính.

- Dòng thứ 2 bao gồm N số, số thứ i tương ứng là giá của thiết bị thứ i được bán ở chợ Trời.

- Dòng thứ 3 là số nguyên dương M ( 0 <= M <= 30) là số lượng gói ưu đãi có trên mạng.

- M dòng tiếp theo, mỗi dòng thứ i là thông tin về gói ưu đãi thứ i. Số đầu tiên là giá của gói ưu đãi P ( 1 <= P <= 1000), số tiếp theo là số lượng thiết bị K ( 1 <= K< = N) trong gói ưu đãi đó,

K số tiếp theo là các thiết bị có trong gói ưu đãi đó.

- Dòng cuối cùng của mỗi test case là thông tin về các thiết bị mà anh Kim cần mua. Số đầu tiên là số lượng thiết bị L, L số tiếp theo là các thiết bị anh Kim cần mua

- Các thiết bị được đánh số trong đoạn từ 1 đến N và không có số nào trùng nhau

Output

Bắt đầu mỗi test case là "#x" với x là số thứ tự của test case (bắt đầu từ 1), tiếp theo là một dấu cách và giá thành nhỏ nhất mà anh Kim cần bỏ ra để mua đủ những thiết bị anh cần.

Sample

Input

1 <-- T = 1,

5 <-- Số linh kiện chính của máy tính

20 15 17 18 25 <-- giá chợ Trời của 5 thiết bị từ 1 đến 5 tương ứng

4 <-- 4 gói ưu đãi trên mạng

30 3 1 2 5 <-- gói thứ nhất có giá 30, gồm 3 linh kiện 1, 2, 5

25 2 2 3 <-- gói thứ 2 có giá 25, gồm 2 linh kiện 2, 3

35 3 1 3 5 <-- gói thứ 3 có giá 35, gồm 3 linh kiện 1, 3, 5

20 2 3 4 <-- gói thứ 4 có giá 20, gồm 2 linh kiện 3, 4

3 2 4 5 <-- Số lượng anh Kim cần là 3, lần lượt là 2, 4, 5

Output

#1 48

Giải thích: Để mua được 3 thiết bị 2, 4, 5 với giá rẻ nhất, ta sẽ mua gói giá rẻ 1 gồm 1, 2, 5 với giá 30 và mua thiết bị 4 ở chợ Trời với giá 18, tổng là 30 + 18 = 48.

//Cleaning Robot
We have to plan a path for a cleaning robot to clean a rectangular room floor of size NxM. The room floor paved with square tiles whose size fits the cleaning robot (1 × 1). There are clean tiles and dirty tiles, and the robot can change a dirty tile to a clean tile by visiting the tile. Also there may be some obstacles (furniture) whose size fits a tile in the room. If there is an obstacle on a tile, the robot cannot visit it. The robot moves to an adjacent tile with one move. The tile onto which the robot moves must be one of four tiles (i.e., east, west, north or south) adjacent to the tile where the robot is present. The robot may visit a tile twice or more.

Your task is to write a program which computes the minimum number of moves for the robot to change all dirty tiles to clean tiles, if ever possible.

Time limit: 1s (C/C++), 2s (Java)

Submit limit: 10 times

Example:

The following is a room of size 5x7, with 3 dirty tiles, and 0 furniture. The answer for this case is 8.

Input

The input consists of multiple maps, the first line is the number of test case T (T < = 50).

Each test case begins with N and M representing the size of the room. ( 5 =< N, M <= 100)

The next N line representing the arrangement of the room with following describe:

0 : a clean tile
1 : a dirty tile
2 : a piece of furniture (obstacle)
3 : the robot (initial position)

In the map the number of dirty tiles does not exceed 10 and there is only one robot.

Output

Print each test case on two lines, the first line of each test case is "Case #x", where x is the test case number. The next line is the minimum number of moves for the robot to change all dirty tiles to clean tiles. If the map includes dirty tiles which the robot cannot reach, your program should output -1.

Sample

Input

5 7

0 0 0 0 0 0 0

0 3 0 0 0 1 0

0 0 0 0 0 0 0

0 1 0 0 0 1 0

0 0 0 0 0 0 0

5 15

0 0 0 0 2 0 2 0 0 0 0 1 2 0 1

0 0 0 1 0 2 0 2 2 0 1 2 0 0 0

2 1 0 2 0 1 0 2 0 0 0 0 0 0 0

0 0 0 1 0 2 0 0 1 2 0 0 2 0 0

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

...............

Output

Case #1

Case #2

Case #3

Case #4

-1

Case #5

//Cover rectangle with dominos
You are given 28 different types of domino, each domino has size of 1x2 with 2 numbers on it as follow

And a board of size 7x8, your task is cover the board with above dominos such that a domino can only be placed on two adjacent squares on board if the numbers of the squares and of domino are equal.

How many different way to cover the board?

For example if the board are given as below, there are 18 way to cover it, one of them is as below.

Input

The first line is the number of test case T (T < = 50).

Each test case will be given on 7 lines, each line have 8 numbers separate by a space is the board for the test case. It have a empty line between 2 test cases.

Output

Print each test case on two lines, the first line is "Case #x", where x is the test case number, the next line is the numbers of different way to cover the board.

Sample

Input

6 1 6 5 3 2 5 0

6 6 0 1 6 0 4 4

2 2 3 6 5 5 1 5

1 2 0 4 4 3 4 2

5 2 1 1 4 1 3 0

3 3 0 2 3 5 2 6

1 3 4 6 4 5 0 0

6 6 6 0 1 4 6 3

2 5 3 3 3 5 5 4

0 0 4 3 3 1 2 4

4 4 2 0 5 5 3 0

0 1 2 2 6 1 2 1

4 6 2 6 5 6 0 4

5 0 5 1 1 1 2 3

...

Output

Case #1

Case #2

//Cover rectangle with dominos
You are given 28 different types of domino, each domino has size of 1x2 with 2 numbers on it as follow

And a board of size 7x8, your task is cover the board with above dominos such that a domino can only be placed on two adjacent squares on board if the numbers of the squares and of domino are equal.

How many different way to cover the board?

For example if the board are given as below, there are 18 way to cover it, one of them is as below.

Input

The first line is the number of test case T (T < = 50).

Each test case will be given on 7 lines, each line have 8 numbers separate by a space is the board for the test case. It have a empty line between 2 test cases.

Output

Print each test case on two lines, the first line is "Case #x", where x is the test case number, the next line is the numbers of different way to cover the board.

Sample

Input

6 1 6 5 3 2 5 0

6 6 0 1 6 0 4 4

2 2 3 6 5 5 1 5

1 2 0 4 4 3 4 2

5 2 1 1 4 1 3 0

3 3 0 2 3 5 2 6

1 3 4 6 4 5 0 0

6 6 6 0 1 4 6 3

2 5 3 3 3 5 5 4

0 0 4 3 3 1 2 4

4 4 2 0 5 5 3 0

0 1 2 2 6 1 2 1

4 6 2 6 5 6 0 4

5 0 5 1 1 1 2 3

...

Output

Case #1

Case #2

//Lucky number
Trong một số nước châu Á, 8 và 6 được coi là những chữ số may mắn. Bất cứ số nguyên nào chỉ chứa chữ số 8 và 6 được coi là số may mắn, ví dụ 6, 8, 66, 668, 88, 886 …. Nguyên là một học sinh rất thích toán. Nguyên thích các số may mắn nhưng chỉ thích các số có dạng

S = 8…86…6

trong đó S có ít nhất một chữ số và chữ số 6 và 8 không nhất thiết phải đồng thời xuất hiện. Ví dụ, 8, 88, 6, 66, 86, 886, 8866 … là các số có dạng S.

Cho trước một số nguyên dương X (1 < X < 10 000), Nguyên muốn tìm số may mắn nhỏ nhất dạng S, có không quá 200 chữ số và chia hết cho X.

Nhiệm vụ của bạn là viết một chương trình tìm số đó cho Nguyên.

Input

Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa một số nguyên dương không lớn hơn 20 là số lượng các bộ dữ liệu. Các dòng tiếp theo chứa các bộ dữ liệu.

Trên mỗi dòng tiếp theo chứa một số nguyên X tương ứng với mỗi bộ dữ liệu.

Ouput

Với mỗi bộ dữ liệu, ghi ra số may mắn dạng S nhỏ nhất chia hết cho X. Trường hợp không tồn tại số S có không quá 200 chữ số như vậy, ghi -1.

Sample

Input

Output

Case #1

Case #2

Case #3

Case #4

-1

//Sum it up
Given a specified total t and a list of n integers, find all distinct sums using numbers from the list that add up to t. For example, if t = 4, n = 6, and the list is [4, 3, 2, 2, 1, 1], then there are four different sums that equal 4: 4, 3+1, 2+2, and 2+1+1. (A number can be used within a sum as many times as it appears in the list, and a single number counts as a sum.) Your job is to solve this problem in general.

Input

The input file will contain one or more test cases, one per line. Each test case contains t, the total, followed by n, the number of integers in the list, followed by n integers x1, . . . ,xn. t will be a positive integer less than 1000, n will be an integer between 1 and 12 (inclusive), and x1, . . . , xn will be positive integers less than 100. All numbers will be separated by exactly one space. The numbers in each list may be repetitions.

Output

For each test case, output the total way, if not output -1.

Sample

Input

4 6

4 3 2 2 1 1

5 3

2 1 1

400 12

50 50 50 50 50 50 25 25 25 25 25 25

20 10

1 2 3 4 5 6 7 8 9 10

Output

#1 4

#2 -1

#3 2

#4 31

Giải thích

3+1

2+2

2+1+1

50+50+50+50+50+50+25+25+25+25

50+50+50+50+50+25+25+25+25+25+25

1+2+3+4+10

1+2+3+5+9

1+2+3+6+8

1+2+4+5+8

1+2+4+6+7

1+2+7+10

1+2+8+9

1+3+4+5+7

1+3+6+10

1+3+7+9

1+4+5+10

1+4+6+9

1+4+7+8

1+5+6+8

1+9+10

2+3+4+5+6

2+3+5+10

2+3+6+9

2+3+7+8

2+4+5+9

2+4+6+8

2+5+6+7

2+8+10

3+4+5+8

3+4+6+7

3+7+10

3+8+9

4+6+10

4+7+9

5+6+9

5+7+8

Editor is loading...