CTAIN - Containers

Problem

We are given n containers, where 1 <= n <= 4. At the beginning all of them are full of water. The liter capacity of the i-th container is a natural number o_i satisfying inequalities 1 <= o_i <= 49.
Three kinds of moves can be made:  

1. Pouring the whole content of one container into another. This move can be made unless there is too little room in the second container. 
2. Filling up one container with part of the water from another one.
3. Pouring away the whole content of one container into a drain.
   

 

 Task

Write a program that for each test case:

• Reads the number of containers n, the capacity of each container and the requested final amount of water in each container.
• Verifies, whether there exist a series of moves which leads to the requested final situation, and if there is one, the program computes the minimal number of moves leading to the requested situation,
• Writes the result. The result should be the minimal number of moves leading to the requested final situation, or one word "NO" if there is no such a sequence of moves.

Input

One integer in the first line, stating the number of test cases, followed by a blank line. There will be not more than 20 tests.
For each test case, at the first line, one positive integer n is written, n <= 4, this is the number of containers. There are n positive integers written in the second line. These are the capacities of the containers (the i-th integer o_i denotes the capacity if the i-th  container,1 <= o_i <= 49). In the third line there are written n numbers. These are the requested final volumes of water in the containers (the i-th integer w_i denotes the requested final volume of water in the i-th container, 0 <= w_i <= o_i). All integers in the second and the third line are separated by single spaces.
The test cases will be separated by a single blank line.

Output

For each test case : write one integer - the minimal number of moves which lead to the requested final situation or write only one word "NO" if it is not possible to reach the requested final situation making only allowed moves.

Example

Input:
2

3
3 5 5
0 0 4

2
20 25
10 16

Output:
6
NO

Giới hạn

Thời gian chạy:	5s
Giới hạn mã nguồn:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)

Thuật toán 

- Duyệt tất cả các trạng thái của các container (nếu không có container i thì coi như sức chứa của nó là 0, và không thao tác với nó).
- Sử dụng hàng đợi để duyệt theo chiều rộng (BFS).
- Đánh dấu trạng thái đã xuất hiện trong hàng đợi hay chưa? Sử dụng mảng exist[][][][] (kiểu int8_t để khỏi gây lỗi do sử dụng quá nhiều bộ nhớ)

Sample code   

- ideone.com
- Github.com

Read More

NK05MNIM - Bốc sỏi

Bài toán

Hai bạn Nam và Mai cùng chơi một trò chơi với n đống sỏi. Luật chơi như sau:

• Hai bạn sẽ lần lượt đi. Bạn Mai là người đi trước
• Trong mỗi lượt đi, bạn đi sẽ được quyền bốc một số sỏi bất kỳ từ một đống nhất định và phải bốc tối thiểu là 1 viên sỏi.
• Bạn nào bốc phải viên sỏi cuối cùng là người thua cuộc

Bạn hãy giúp Mai xác định xem bạn ấy có thể thắng được trong trò chơi hay không

 

 Dữ liệu vào

Dòng đầu tiên chứa một nguyên t là số bộ test. Các dòng sau là t bộ test.
Mỗi bộ test bao gồm:

• Dòng đầu tiên chứa một số nguyên n (n<=100) là số đống sỏi
• Dòng thứ hai gồm n số nguyên a₁, a₂, a₃,... , a_n, ngăn cách nhau bởi một khoảng trắng. Số nguyên ai cho biết số lượng viên sỏi có trong đống thứ i (1<=a_i<=100)

Kết quả

Với mỗi bộ test, in ra 1 nếu bạn Mai thắng, -1 nếu bạn Mai thua

Ví dụ

Input
2
4
30 4 19 75
3
1 4 5


Output
1 

-1

Giới hạn

Thời gian chạy:	0.460s
Giới hạn mã nguồn:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)

Giải thuật (Thuật thắng trò chơi NIM)

- Tổng Nim của hai số a,b là a xnor b (trong C++ kí hiệu là a^b).

- Nếu số đống sỏi lẻ và mỗi đống chỉ có một viên thì người chơi trước luôn thua.

- Nếu ban đầu (a₁, a₂, a₃,... , a_n ) có tổng Nim duơng thì người chơi trước luôn thắng. (Theo định lý Bouton)

Code mẫu

- ideone.com
- github.com

Read More

NK05ORDR - Trật tự

Bài toán:

Xét các số nguyên từ 1 đế N. Các số này được sắp xếp theo thứ tự từ điển. Ví dụ với N=11, ta có dãy số sau khi sắp xếp là 1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9.
Ký hiệu Q_N,K là vị trí của số K trong dãy được sắp xếp theo cách nói trên. Ví dụ Q_11,2=4 Cho các số nguyên K và M. Hãy tìm số nguyên N nhỏ nhất thỏa mãn Q_N,K=M

 

 Dữ liệu vào

Dòng đầu tiên chứa số nguyên t cho biết số bộ test.
Mỗi bộ test bao gồm 1 dòng duy nhất chứa 2 số nguyên K và M (1<=K,M<=10⁹)

Kết quả

Với mỗi bộ test xuất ra số N, hoặc 0 nếu không tồn tại N

Ví dụ

Input
1
2 4
Output
11

Yêu cầu

Thời gian chạy:	0.374s
Giới hạn mã nguồn:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)

Code mẫu: 

- ideone.com
- github.com

 

Read More