# Untitled

unknown

plain_text

a year ago

13 kB

25

Indexable

Never

^{}

Picking up Jewels There is a maze that has one entrance and one exit. Jewels are placed in passages of the maze. You want to pick up the jewels after getting into the maze through the entrance and before getting out of it through the exit. You want to get as many jewels as possible, but you don’t want to take the same passage you used once. When locations of a maze and jewels are given, find out the greatest number of jewels you can get without taking the same passage twice, and the path taken in this case. Time limit : 1 sec (Java : 2 sec) [Input] There can be more than one test case in the input file. The first line has T, the number of test cases. Then the totally T test cases are provided in the following lines (T ≤ 10 ) In each test case, In the first line, the size of the maze N (1 ≤ N ≤ 10) is given. The maze is N×N square-shaped. From the second line through N lines, information of the maze is given. “0” means a passage, “1” means a wall, and “2” means a location of a jewel. The entrance is located on the upper-most left passage and the exit is located on the lower-most right passage. There is no case where the path from the entrance to the exit doesn’t exist. [Output] Output the greatest number of jewels that can be picked up. [I/O Example] Input 2 5 0 0 0 2 0 2 1 0 1 2 0 0 2 2 0 0 1 0 1 2 2 0 0 0 0 6 0 1 2 1 0 0 0 1 0 0 0 1 0 1 2 1 2 1 0 2 0 1 0 2 0 1 0 1 0 1 2 0 2 1 0 0 Output 6 4 10 6 0 2 0 1 2 0 1 1 0 1 0 1 0 0 2 0 0 2 0 1 1 1 1 2 0 2 0 0 2 2 1 1 1 1 2 2 5 0 0 0 2 0 2 1 0 1 2 0 0 2 2 0 0 1 0 1 2 2 0 0 0 0 10 0 1 0 2 0 0 0 2 0 2 0 0 0 1 1 0 1 0 1 2 2 1 2 1 1 0 1 0 1 0 0 1 2 1 1 0 1 0 1 2 0 0 2 0 0 2 0 0 0 0 0 1 2 1 0 1 0 1 1 0 0 1 0 1 2 1 2 2 1 2 2 1 0 1 0 1 0 2 0 0 0 1 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 7 0 0 0 2 0 0 0 0 1 1 0 1 1 0 2 1 1 0 1 1 0 0 0 0 2 0 2 2 0 1 1 2 1 1 0 0 1 1 0 1 1 0 2 0 0 2 2 1 0 6 0 2 0 1 2 0 2 1 0 1 0 1 2 2 2 0 0 2 0 1 1 0 1 2 0 2 0 0 2 2 1 1 1 1 2 2 10 0 1 2 2 2 0 2 1 1 0 0 1 0 1 1 1 0 2 2 0 0 2 0 2 0 0 0 1 1 0 2 1 0 1 0 1 0 1 2 0 0 1 1 1 0 1 2 1 1 0 2 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0 2 2 0 0 1 0 1 1 1 0 1 2 2 2 1 0 1 1 1 0 1 1 0 0 0 2 0 0 0 0 2 2 0 10 0 0 0 2 0 0 1 0 2 0 0 1 0 1 0 1 1 2 1 0 2 1 0 1 2 1 1 0 1 0 0 0 0 2 0 0 0 0 0 0 0 1 2 1 0 1 0 1 1 0 0 1 2 1 0 1 2 2 1 0 0 1 0 2 0 0 2 1 2 0 0 1 0 1 0 1 2 1 2 0 0 1 0 1 0 1 2 1 1 0 0 0 0 0 0 0 2 1 1 0 10 0 1 0 2 0 0 0 2 0 2 0 0 0 1 1 0 1 0 1 2 2 1 2 1 1 0 1 0 1 0 0 1 2 1 1 0 1 0 1 2 0 0 2 0 0 2 0 0 0 0 0 1 2 1 0 1 0 1 1 0 0 1 0 1 2 1 2 2 1 2 2 1 0 1 0 1 0 2 0 0 0 1 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 10 0 0 0 2 0 0 1 0 2 0 0 1 0 1 0 1 1 2 1 0 2 1 0 1 2 1 1 0 1 0 0 0 0 2 0 0 0 0 0 0 0 1 2 1 0 1 0 1 1 0 0 1 2 1 0 1 2 2 1 0 0 1 0 2 0 0 2 1 2 0 0 1 0 1 0 1 2 1 2 0 0 1 0 1 0 1 2 1 1 0 0 0 0 0 0 0 2 1 1 0 10 0 1 0 2 0 0 0 2 0 2 0 0 0 1 1 0 1 0 1 2 2 1 2 1 1 0 1 0 1 0 0 1 2 1 1 0 1 0 1 2 0 0 2 0 0 2 0 0 0 0 0 1 2 1 0 1 0 1 1 0 0 1 0 1 2 1 2 2 1 2 2 1 0 1 0 1 0 2 0 0 0 1 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 Case #1 -1 -1 Case #2 -1 -1 Case #3 6 6 Case #4 6 6 Case #5 5 5 Case #6 6 6 Case #7 7 7 Case #8 5 9 Case #9 5 5 Case #10 4 4 Case #11 6 6 Case #12 10 16 Case #13 -1 -1 Case #14 -1 -1 Case #15 -1 -1 Case #16 -1 -1 Case #17 8 9 Case #18 -1 -1 Case #19 -1 -1 Case #20 -1 -1 Case #21 12 12 Case #22 21 -1 Case #23 62 -1 Case #24 92 -1 Case #25 -1 -1 Case #26 195 -1 Case #27 199 -1 Case #28 -1 -1 Case #29 999 1001 Case #30 -1 -1 Little Elephants The Little Elephant and his friends from the Zoo were returning from the party. But suddenly they were stopped by the policeman Big Hippo, who wanted to make an alcohol test for elephants. There were N elephants ordered from the left to the right in a row and numbered from 0 to N-1.Let R[i] to be the result of breathalyzer test of i-th elephant. Considering current laws in the Zoo, elephants would be arrested if there exist K consecutive elephants among them for which at least M of these K elephants have the maximal test result among these K elephants. Using poor math notations we can alternatively define this as follows. The elephants would be arrested if there exists i from 0 to N-K, inclusive, such that for at least M different values of j from i to i+K-1,inclusive, we have R[j] = max{R[i], R[i+1], ..., R[i+K-1]}. The Big Hippo is very old and the Little Elephant can change some of the results. In a single operation he can add 1 to the result of any elephant. But for each of the elephants he can apply this operation at most once. What is the minimum number of operations that the Little Elephant needs to apply, such that the sequence of results, after all operations will be applied, let elephants to avoid the arrest? If it is impossible to avoid the arrest applying any number of operations, output -1. Input The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains three space-separated integers N,K, M. The second line contains N space-separated integers R[0],R[1], ..., R[N-1] denoting the test results of the elephants. Output For each test case, output a single line containing the minimum number of operations needed to avoid the arrest. Constraints 1 ≤ T ≤ 10 1 ≤ M ≤ K ≤ N ≤ 17 1 ≤ R[i] ≤ 17 Example Input: 4 5 3 2 1 3 1 2 1 5 3 3 7 7 7 7 7 5 3 3 7 7 7 8 8 4 3 1 1 3 1 2 Output: #1 0 #2 1 #3 1 #4 -1 Explanation Example case 1. Let's follow the poor math definition of arrest. We will consider all values of i from 0 to N-K = 2, inclusive, and should count the number of values of j described in the definition. If it less than M = 2 then this value of i does not cause the arrest, otherwise causes. i {R[i],...,R[i+K-1]} max{R[i],...,R[i+K-1]} For which j = i, ..., i+K-1 we have R[j] = max Conclusion i=0 {1, 3, 1} max = 3 R[j] = 3 for j = 1 does not cause the arrest i=1 {3, 1, 2} max = 3 R[j] = 3 for j = 1 does not cause the arrest i=2 {1, 2, 1} max = 2 R[j] = 2 for j = 3 does not cause the arrest So we see that initial test results of the elephants do not cause their arrest. Hence the Little Elephant does not need to apply any operations. Therefore, the answer is 0. Example case 2.Wehave N = 5, K = 3, M = 3. Let's construct similar table as in example case 1. Here the value of i will cause the arrest if we have at least 3 values of j described in the definition. i {R[i],...,R[i+K-1]} max{R[i],...,R[i+K-1]} For which j = i, ..., i+K-1 we have R[j] = max Conclusion i=0 {7, 7, 7} max = 7 R[j] = 7 for j = 0, 1, 2 causes the arrest i=1 {7, 7, 7} max = 7 R[j] = 7 for j = 1, 2, 3 causes the arrest i=2 {7, 7, 7} max = 7 R[j] = 7 for j = 2, 3, 4 causes the arrest So we see that for initial test results of the elephants each value of i causes their arrest. Hence the Little Elephant needs to apply some operations in order to avoid the arrest. He could achieve his goal by adding1 to the result R[2]. Then results will be {R[0], R[1], R[2], R[3],R[4]} = {7, 7, 8, 7, 7}. Let's check that now elephants will be not arrested. i {R[i],...,R[i+K-1]} max{R[i],...,R[i+K-1]} For which j = i, ..., i+K-1 we have R[j] = max Conclusion i=0 {7, 7, 8} max = 8 R[j] = 8 for j = 2 does not cause the arrest i=1 {7, 8, 7} max = 8 R[j] = 8 for j = 2 does not cause the arrest i=2 {8, 7, 7} max = 8 R[j] = 8 for j = 2 does not cause the arrest So we see that now test results of the elephants do not cause their arrest. Thus we see that using 0 operations we can't avoid the arrest but using 1 operation can. Hence the answer is 1. Example case 3.Wehave N = 5, K = 3, M = 3. Let's construct similar table as in example case 1. Here the value of i will cause the arrest if we have at least 3 values of j described in the definition. i {R[i],...,R[i+K-1]} max{R[i],...,R[i+K-1]} For which j = i, ..., i+K-1 we have R[j] = max Conclusion i=0 {7, 7, 7} max = 7 R[j] = 7 for j = 0, 1, 2 causes the arrest i=1 {7, 7, 8} max = 8 R[j] = 8 for j = 3 does not cause the arrest i=2 {7, 8, 8} max = 8 R[j] = 8 for j = 3, 4 does not cause the arrest So we see that for initial test results of the elephants the value of i =0 causes their arrest. Hence the Little Elephant needs to apply some operations in order to avoid the arrest. He could achieve his goal by adding1 to the result R[1]. Then results will be {R[0], R[1], R[2],R[3], R[4]} = {7, 8, 7, 8, 8}. Let's check that now elephants will be not arrested. i {R[i],...,R[i+K-1]} max{R[i],...,R[i+K-1]} For which j = i, ..., i+K-1 we have R[j] = max Conclusion i=0 {7, 8, 7} max = 8 R[j] = 8 for j = 1 does not cause the arrest i=1 {8, 7, 8} max = 8 R[j] = 8 for j = 1, 3 does not cause the arrest i=2 {7, 8, 8} max = 8 R[j] = 8 for j = 3, 4 does not cause the arrest So we see that now test results of the elephants do not cause their arrest. Thus we see that using 0 operations we can't avoid the arrest but using 1 operation can. Hence the answer is 1. Note that if we increase by 1 the result R[2] instead of R[1] then the value i = 2 will cause the arrest since {R[2], R[3], R[4]}will be {8, 8, 8} after this operation and we will have 3 values of j from 2 to 4,inclusive, for which R[j] = max{R[2], R[3], R[4]}, namely, j= 2, 3, 4. Example case 4. When M= 1 the Little Elephant can't reach the goal since for each value of i from 0 to N-K we have at least one value of j for which R[j] =max{R[i], R[i+1], ..., R[i+K-1]}. #include <iostream> using namespace std; int n, m; int dx, dy; int arr[3001][3001]; int dd[3001][3001]; int dem[3001][3001]; int dR[4] = {-1, 0, 1, 0}; int dC[4] = {0, 1, 0, -1}; typedef struct{ int x, y; }Point; Point data[9000001]; typedef struct { int front, rear; }Queue; void init(Queue &Q){ Q.front = Q.rear = -1; } void push(Queue &Q, Point value){ Q.rear++; data[Q.rear] = value; } Point top(Queue &Q){ Point temp; Q.front++; temp = data[Q.front]; Q.front--; return temp; } void pop(Queue &Q){ Q.front++; } bool empty(Queue &Q){ if(Q.front == Q.rear) return true; return false; } Queue Q; void BFS(Point P){ init(Q); push(Q, P); dd[P.x][P.y] = 1; dem[P.x][P.y] = 1; while(!empty(Q)){ Point P1 = top(Q); pop(Q); for(int k=0; k<4; k++){ int x = P1.x + dR[k]; int y = P1.y + dC[k]; if(x>=1 && x<=n && y>=1 && y<=m && arr[x][y] == 1 && dd[x][y] == 0){ dd[x][y] = 1; dem[x][y] = dem[P1.x][P1.y] + 1; Point P2; P2.x = x; P2.y = y; push(Q, P2); } } } } int main(){ //freopen("vao.txt", "r", stdin); int t; cin >> t; for(int tc = 1; tc<=t; tc++){ cin >> n >> m; cin >> dx >> dy; int xc = -1, yc = -1; for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ cin >> arr[i][j]; if(arr[i][j] == 2 && xc == -1){ xc = i; yc = j; } } } Point P; P.x = dx; P.y = dy; for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ dd[i][j] = 0; dem[i][j] = 0; } } bool flag1 = true; for(int k=0; k<4; k++){ int x = xc + dR[k]; int y = yc + dC[k]; if(x>n || y>m || x<=0 || y<=0){ flag1 = false; break; } } cout << "Case #" << tc << endl; if(flag1){ BFS(P); int count = 0; int count1 = -2; int count2 = -2; for(int k=0; k<4; k++){ int x = xc + dR[k]; int y = yc + dC[k]; if(x>=1 && x<=n && y>=1 && y<=m && dd[x][y] == 1 && arr[x][y] == 1){ count++; count1 = max(count1, dem[x][y]); } } if(count == 4){ cout << count1 << " "; }else{ cout << "-1" << " "; } bool flag = true; for(int i=1; i<=n; i++){ for(int j=1; j<=m; j++){ if(arr[i][j] == 1 && dd[i][j] == 0){ flag = false; i=n+1; break; }else if(arr[i][j] == 1 && dd[i][j] == 1){ count2 = max(count2, dem[i][j]); } } } if(flag){ cout << count2 << endl; }else{ cout << "-1" << endl; } } else{ cout << "-1 -1" << endl; } } return 0; }