Nộp bài Các bài nộp Làm tốt nhất PDF Về danh sách bài

CTAIN - Containers

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 oi satisfying inequalities 1 <= oi <= 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 oi denotes the capacity if the i-th  container,1 <= oi <= 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 wi denotes the requested final volume of water in the i-th container, 0 <= wi <= oi). 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
Submit solution!
Được gửi lên bởi:Thanh-Vy Hua
Ngày:2004-12-24
Thời gian chạy:5s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:3rd Polish Olympiad in Informatics, stage 1
hide comments
2021-07-23 12:05:03
Ninh Trinh: de qua, lam phat AC luon

Last edit: 2021-07-23 12:05:33
2020-02-21 04:10:27 nguyen ngoc son
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class main {

private static Scanner scanner;
private static int[][] arrs;
static int dx[] = {-1,-2,-2,-1,1,2,2,1};
static int dy[] = {-2,-1,1,2,2,1,-1,-2};

/*ham doc vao ma tran*/
public static void readMX() {
for (int i = 0; i < arrs.length; i++) {
for (int j = 0; j < arrs.length; j++) {
arrs[i][j] = scanner.nextInt();
}
}
}
/*ham in ra ma tran*/
public static void printMX() {
for (int i = 0; i < arrs.length; i++) {
for (int j = 0; j < arrs.length; j++) {
System.out.print(arrs[i][j]+" ");
}
System.out.println();
}
}
/*ham dem tai vi tri x,y*/
public static int Count(int x,int y) {
int cnt = 0;
for(int k=0;k<8;k++) {
int tx = x + dx[k];
int ty = y + dy[k];
if(tx>=0 &&tx<arrs.length && ty>=0 &&ty<arrs.length && arrs[tx][ty]==1) {
cnt++;
}
}
return cnt;
}
/*ham main*/
public static void main(String[] args) throws FileNotFoundException {
System.out.println("Mã đi tuần:");
System.setIn(new FileInputStream("C:\\Users\\SVMC\\eclipse-workspace\\Ma_di_tuan\\src\\input.txt"));
scanner = new Scanner(System.in);

int test_cases=scanner.nextInt();

for(int test=1;test<=test_cases;test++) {
int N = scanner.nextInt();
int M = scanner.nextInt();
int KQ = 0;
arrs = new int[N][M];
//System.out.println(N+" "+M);
/*doc du lieu vao*/
readMX();
//printMX();
/*xu ly*/
for (int i = 0; i < arrs.length; i++) {
for (int j = 0; j < arrs.length; j++) {
if(arrs[i][j]==2) {
KQ = Count(i, j);
break;
}
}
}
System.out.println("#"+test+" "+KQ);
}
}
}
2020-02-21 02:41:17 nguyen ngoc son

8 8
1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1
1 1 1 1 1 1 0 1
1 0 1 2 1 1 1 1
1 0 0 0 1 1 0 1
1 0 1 0 1 1 1 1
1 0 0 1 1 0 1 1
0 0 1 1 0 1 1 1

8 8
1 1 1 0 0 0 1 1
0 0 1 0 1 1 0 1
1 1 1 1 0 1 0 1
0 1 0 2 1 1 0 0
1 1 0 0 1 0 1 1
0 1 0 0 0 1 0 1
1 1 1 0 0 1 1 1
0 1 1 0 0 0 1 1

8 8
0 1 0 1 0 1 1 1
1 0 0 0 1 0 1 1
1 0 0 0 0 1 0 1
0 0 0 0 0 0 1 0
1 1 0 0 0 0 0 0
1 0 0 0 2 1 1 1
0 0 0 1 0 0 0 0
0 1 1 1 0 1 1 1

16 16
1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0
0 0 0 0 0 0 1 1 0 1 1 0 1 1 0 1
0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0
1 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1
1 0 1 1 0 0 0 1 2 1 1 1 1 1 1 1
1 0 1 0 0 0 0 1 0 0 1 0 1 1 1 1
1 0 0 1 0 0 1 0 0 0 1 0 0 1 1 1
0 0 0 1 0 1 1 0 0 1 1 0 1 1 1 0
1 1 1 1 0 0 0 0 0 1 0 0 1 0 1 0
1 1 0 1 0 0 0 1 1 0 0 1 0 0 0 1
0 1 0 1 1 1 0 1 1 1 1 0 1 1 1 1
1 0 1 1 0 1 0 1 1 0 1 1 1 1 0 1
0 0 0 0 1 0 0 1 1 1 1 0 0 1 1 0
0 1 1 1 1 0 1 0 1 0 0 0 1 0 1 0
1 0 0 0 1 1 1 0 1 0 0 0 1 0 0 1
1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1

16 16
0 0 1 0 1 0 1 1 0 0 0 1 0 1 0 0
1 0 1 1 1 1 0 0 1 0 0 0 0 1 1 0
0 0 1 1 1 1 1 1 0 1 1 0 1 0 1 1
1 1 0 1 0 0 0 1 2 1 0 0 1 0 1 0
0 1 0 0 0 0 0 1 0 1 1 1 0 1 0 0
0 0 0 0 1 0 0 1 0 1 0 0 1 1 1 1
1 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0
0 0 0 1 0 1 0 1 1 1 1 1 1 1 0 1
1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 1
0 0 0 1 0 0 1 0 1 1 0 0 0 0 0 1
1 1 1 1 0 0 0 1 1 1 0 0 1 1 0 0
1 0 1 0 0 1 0 0 0 0 0 1 1 1 1 0
0 1 0 0 1 0 1 1 0 1 0 1 1 1 0 1
1 0 1 0 1 0 0 1 1 0 1 0 1 1 0 0
1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 0
0 0 0 1 1 0 1 0 1 0 1 0 0 0 0 1

16 16
0 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0
1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 0
1 0 0 0 0 1 1 1 0 1 1 0 1 0 1 0
0 0 0 1 0 1 1 0 1 1 1 1 0 0 0 0
0 0 1 1 0 0 0 1 0 1 0 1 1 1 1 1
0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1
0 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1
1 1 0 1 1 0 0 1 1 1 0 0 0 0 0 1
0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1
0 0 0 1 1 0 1 0 1 0 2 0 1 0 1 0
1 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0
1 1 0 1 1 0 0 0 0 0 0 1 0 1 1 0
1 1 0 1 1 1 0 0 0 1 0 0 1 1 1 0
0 0 0 0 0 0 0 1 1 0 1 1 0 1 1 1
0 0 0 0 1 1 1 1 0 1 0 0 1 1 1 0
1 1 1 0 1 1 0 0 1 0 1 1 0 1 0 0
#1 5
#2 5
#3 2
#4 4
#5 5
#6 3
2019-07-29 08:56:25
1 đấm ac code: https://bit.ly/2eGhgab . Khỏi cảm ơn
2018-11-29 13:13:40
hi
2017-09-27 09:49:45
Code tham khảo: http://123link.top/CTAIN
2017-09-13 07:29:27
Code AC: http://shink.in/luBqA
2017-09-08 18:41:41 Sơn Tùng M-TP
haha
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.