| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 10664 | easy 8 Puzzles |
|
| 10832 | Pouring Water |
|
Description
一個八數字推盤遊戲由3*3的棋盤組成，每一個格子上都有一個數字(0~8且不重複)，一開始盤面是亂的，
| 1 | 2 | 3 |
| 4 | 0 | 5 |
| 7 | 8 | 6 |
每次操作可以將0與其上.下.左.右的數字互換，經過若干次操作：
step 1 : 0往右與5互換
| 1 | 2 | 3 |
| 4 | 5 | 0 |
| 7 | 8 | 6 |
step 2 : 0往下與6互換
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 0 |
最後將盤面排回
| 1 | 2 | 3 |
| 4 | 5 | 6 |
| 7 | 8 | 0 |
即為正解。
Rody最近沉迷於八數字推盤遊戲當中，但最近要開始期末大爆炸了，Rody不再那麼空閒，因此他決定要先跳過太過困難的題目，等到暑假再來解。
困擾的Rody想要請你幫他鑑定題目的困難度。
Input
input第一行有一整數T(1<=T<=30)，代表底下有T筆測資。
第2~T+1行分別有9個不同的整數(0<=t1,t2,...,t9<=8)，代表一個八數字推盤遊戲。
(註:9個整數以row major方式填入3*3的盤面，如第二組測資 1 2 3 4 0 5 7 8 6 等同於下方示意圖)
| 1 | 2 | 3 |
| 4 | 0 | 5 |
| 7 | 8 | 6 |
Output
對於每組八數字推盤遊戲，若能在14步內完成遊戲，請輸出"You can solve it within x steps."，x為解決該遊戲所需的最少移動次數。
否則，請輸出"You'd better skip this game."
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Suppose that you have an infinite number of containers with different sizes, already filled with water. Given another empty container with size N liters, you need to find out all the possible methods to fill this N-liter empty container using the provided smaller containers. Note that, to avoid water wastage, if you choose to use a container, all the water in this container should be poured.
For example, assume that we have containers in 1, 5, and 10 liters. To get the 17 liters of water, all the possible methods are listed below:
- 1 container of 10 liters, 1 container of 5 liters, and 2 containers of 1 liter.
- 1 container of 10 liters, 0 containers of 5 liters, and 7 containers of 1 liter.
- 0 containers of 10 liters, 3 containers of 5 liters, and 2 containers of 1 liter.
- 0 containers of 10 liters, 2 containers of 5 liters, and 7 containers of 1 liter.
- 0 containers of 10 liters, 1 container of 5 liters, and 12 containers of 1 liter.
- 0 containers of 10 liters, 0 containers of 5 liters, and 17 containers of 1 liter.
Note that
1. This problem involves three files.
- function.h: Function definition of filliing and showResult.
- function.c: Function describe of filling and showResult.
- main.c: A driver program to test your implementation.
You will be provided with main.c and function.h, and asked to implement function.cpp.
2. For OJ submission:
Step 1. Submit only your function.c into the submission block. (Please choose C compiler)
Step 2. Check the results and debug your program if necessary.
function.h
main.c
Hint
You can use the following incomplete code of function.c to solve this problem.
function.c
Input
The input contains three lines.
The first line contains an integer M (0<M<=5) which represents the number of different size containers.
The second line contains M numbers, S1 ,S2 , …, SM. Si represents the size of the i-th container. Note that these M numbers are in decreasing order.
The third line contains an integer N (0<M<100) which represents the size of the empty container.
Output
Display all the possible methods to fill the empty container. Each line represents a method in the format “(C1,C2,…,CM)”, where Ci represents the number of the size Si container.