Untitled
unknown
plain_text
5 months ago
22 kB
7
Indexable
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
class Solution {
private static BufferedReader br;
private static UserSolution usersolution = new UserSolution();
private final static int CMD_INIT = 1;
private final static int CMD_COUNT = 2;
private final static int CMD_BUILD = 3;
private final static int MAX_N = 50000;
private static int mHeight[] = new int[MAX_N];
private static boolean run() throws Exception {
StringTokenizer stdin = new StringTokenizer(br.readLine(), " ");
int query_num = Integer.parseInt(stdin.nextToken());
boolean ok = false;
for (int q = 0; q < query_num; q++) {
stdin = new StringTokenizer(br.readLine(), " ");
int query = Integer.parseInt(stdin.nextToken());
if (query == CMD_INIT) {
int N = Integer.parseInt(stdin.nextToken());
for (int i = 0; i < N; i++){
mHeight[i] = Integer.parseInt(stdin.nextToken());
}
usersolution.init(N, mHeight);
ok = true;
} else if (query == CMD_COUNT) {
int mLen = Integer.parseInt(stdin.nextToken());
int mTank[] = new int[mLen];
for (int i = 0; i < mLen; i++){
mTank[i] = Integer.parseInt(stdin.nextToken());
}
int ret = usersolution.countPosition(mLen, mTank);
int ans = Integer.parseInt(stdin.nextToken());
if (ans != ret) {
ok = false;
}
} else if (query == CMD_BUILD) {
int mLen = Integer.parseInt(stdin.nextToken());
int mTank[] = new int[mLen];
for (int i = 0; i < mLen; i++){
mTank[i] = Integer.parseInt(stdin.nextToken());
}
int mWater = Integer.parseInt(stdin.nextToken());
int ret = usersolution.buildAndPourOut(mLen, mTank, mWater);
int ans = Integer.parseInt(stdin.nextToken());
if (ans != ret) {
ok = false;
}
}
}
return ok;
}
public static void main(String[] args) throws Exception {
int T, MARK;
//System.setIn(new java.io.FileInputStream("res/sample_input.txt"));
br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stinit = new StringTokenizer(br.readLine(), " ");
T = Integer.parseInt(stinit.nextToken());
MARK = Integer.parseInt(stinit.nextToken());
for (int tc = 1; tc <= T; tc++) {
int score = run() ? MARK : 0;
System.out.println("#" + tc + " " + score);
}
br.close();
}
}
//====
package Water_Tank;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
class UserSolution {
class Tank{
int count;
List<Integer> vis = new ArrayList<>();
}
List<Integer> k;
int n, l, r, maxL, maxR;
int[] a, temp;
HashMap<Integer, Tank> map = new HashMap<>();
public void init(int N, int mHeight[]) {
n = N;
a = new int[N + 1];
temp = new int[n + 1];
k = new ArrayList<>();
//1 1 2 3 1 1 3 1 1 2 3 4 5 5 5 7 9 1
a = mHeight.clone();
for(int i = 1; i < N - 1; i++){
if(i < N - 2){
k.clear();
for(int j = i + 1; j < i + 3; j++){
k.add(a[i] - a[j] + 5);
}
addMap(k, i);
}
if(i < N - 3){
k.clear();
for(int j = i + 1; j < i + 4; j++){
k.add(a[i] - a[j] + 5);
}
addMap(k, i);
}
if( i < N - 4){
k.clear();
for(int j = i + 1; j < i + 5; j++){
k.add(a[i] - a[j] + 5);
}
addMap(k, i);
}
}
}
public int countPosition(int mLen, int mTank[]) {
int m = mTank[0];
k.clear();
for(int i = 1; i < mLen; i++){
k.add(mTank[i] - m + 5);
}
int key = 0;
for(Integer i : k){
key = key * 10 + i;
}
Tank t = map.get(key);
if(t == null){
System.out.println(0);
return 0;
}
System.out.println(t.count);
return t.count;
}
public int buildAndPourOut(int mLen, int mTank[], int mWater) {
int m = mTank[0];
k.clear();
for(int i = 1; i < mLen; i++){
k.add(mTank[i] - m + 5);
}
int key = 0;
for(Integer i : k){
key = key * 10 + i;
}
Tank t = map.get(key);
int left, right;
left = right = 0;
l = r = maxL = maxR = 0;
int maxRes = 0;
for(Integer id : t.vis){
left = id;
right = id + mLen - 1;
l = left;
r = right;
int resL, resR;
resL = id;
resR = id +mLen-1;
temp = a.clone();
temp[left] += mTank[0];
temp[right] += mTank[mLen - 1];
maxR = temp[left];
boolean check = false;
if(temp[left-1] < temp[left]){
check = true;
resL = leftSide(0, left, mTank, 0, 0, mWater);
}
temp = a.clone();
temp[left] += mTank[0];
temp[right] += mTank[mLen - 1];
maxL = temp[right];
if(temp[right+1] < temp[right]){
check = true;
resR = rightSide(0, right, mTank, 0, 0, mWater, mLen);
}
if(!check){
System.out.println(0);
return 0;
}
int curMax = Math.max(resL, resR);
maxRes = Math.max(maxRes, curMax);
//System.out.println();
}
System.out.println(maxRes);
return maxRes;
}
int leftSide(int start, int left, int[] mTank, int index, int next, int mWater){
start = a[left] + mTank[0];
for(int i = left; i >= 0; i--){
if(i - left > 500) break;
if(a[i] > start){
next = a[i];
maxL = a[i];
break;
}
else if(a[i] < start){
start = a[i];
index = i;
} else {
maxL = a[i];
next = a[i];
if(next > start) break;
}
}
int cnt = 0;
while(mWater != 0){
if(start == maxL || start == maxR) break;
int res = findMaxLeft(index, start, next);// sl day
if(res > mWater){
if(cnt == 0)
return 0;
else return cnt;
}
if(start + 1 == next) {
if(res <= mWater){
start++;
mWater -= res;
cnt += res;
}
break;
}
start++;
mWater -= res;
cnt += res;
}
return cnt;
}
int rightSide(int start, int right, int[] mTank, int index, int next, int mWater, int mLen){
start = a[right] + mTank[mLen - 1];
for(int i = right + 1; i <= n - 1; i++){
if(i - right > 500) break;
if(a[i] > start){
maxR = a[i];
next = a[i];
break;
}
else if(a[i] < start){
start = a[i];
index = i;
} else {
maxR = a[i];
next = a[i];
if(next > start) break;
}
}
int cnt = 0;
while(mWater != 0){
if(start == maxL || start == maxR) break;
int res = findMaxRight(index, start, next);
if(res > mWater) {
if(cnt == 0)
return 0;
else return cnt;
}
if(start + 1 == next) {
if(res <= mWater){
start++;
mWater -= res;
cnt += res;
}
break;
}
start++;
mWater -= res;
cnt += res;
}
return cnt;
}
int findMaxRight(int index, int height, int maxT){
int cnt = 0;
for(int i = index; i > r; i--){
if(temp[i] >= maxL) break;
if(temp[i] > height) break;
if(temp[i] == height) {
if(height == maxT) break;
temp[i]++;
cnt++;
}
else break;
}
for(int i = index + 1; i < n - 1; i++){
if(temp[i] >= maxR) break;
if(temp[i] > height) break;
if(temp[i] == height) {
if(height == maxT) break;
temp[i]++;
cnt++;
}
else break;
}
return cnt;
}
int findMaxLeft(int index, int height, int maxT){
int cnt = 0;
for(int i = index; i >= 1; i--){
if(temp[i] >= maxL) break;
if(temp[i] > height) break;
if(temp[i] == height) {
if(height == maxT) break;
temp[i]++;
cnt++;
}
else break;
}
for(int i = index + 1; i < l; i++){
if(temp[i] >= maxL) break;
if(temp[i] > height) break;
if(temp[i] == height) {
if(height == maxT) break;
temp[i]++;
cnt++;
}
else break;
}
return cnt;
}
void addMap(List<Integer> list, int index){
if(list.size() < 2) return;
int key = 0;
for(Integer i : list){
key = key * 10 + i;
}
Tank t = map.get(key);
if(t == null){
t = new Tank();
}
t.count++;
t.vis.add(index);
map.put(key, t);
}
}
4//==========4
You want to write a program that simplifies and simulates the process of installing a water tank in the valley and creating a puddle.
The width of the valley is N. The respective heights of the unit widths of the valley are given.
If the width of the valley is 10, and the heights of the unit widths of the valley are {8, 7, 5, 4, 3, 3, 5, 6, 7, 8}, the valley looks like [Fig. 1].
[Fig. 1]
A water tank to install in the valley is given.
The width of the tank ranges from 3 to 5. The respective heights of the unit widths of the tank are given in a one-dimensional array.
The heights of the unit widths of the tank range from 1 to 5. The top of the tank is flat.
[Fig. 2] shows tanks in various shapes.
[Fig. 2] (a) is a tank whose width is 4 and the heights of the unit widths are {5, 3, 2, 1}.
[Fig. 2] (b) is a tank whose width is 4 and the heights of the unit widths are {1, 2, 2, 3}.
[Fig. 2] (c) is a tank whose width is 3 and the heights of the unit widths are {3, 3, 3}.
[Fig. 2]
A tank can only be installed in the location where no empty space exists between the valley and the tank when the tank is placed as is in the valley.
In [Fig. 3], the tank in [Fig. 2] (a) is being installed.
In [Fig. 3] (a), the tank can be installed because no empty space exists between the tank and the valley.
In [Fig. 3] (b), the tank cannot be installed because the empty space colored in yellow exists between the tank and the valley.
[Fig. 3]
The location where a tank is installed is represented as the leftmost column number of the tank.
For example, the tank in [Fig. 3] (a) is installed in Column 5.
(Column number starts at 0 and increases from left to right.)
In the valley, there can be 0 or more than 1 location where the tank can be installed.
If the width of the valley is 10, and the heights of the unit widths of the valley are {1, 2, 3, 4, 5, 7, 7, 8, 9, 10},
the tank whose width is 3 and the heights of the unit widths are {3, 2, 1} can be installed in 5 locations.
[Fig. 4] (a) is the shape of the tank to be installed. The red boxes in [Fig. 4] (b) are the locations where the tank can be installed.
The tank can be installed in Column 0, 1, 2, 6, or 7.
The tank in [Fig. 4] (c) whose width is 3 and the heights of the unit widths are {1, 2, 3} cannot be installed anywhere.
[Fig. 4]
After a tank is installed in the valley, you should release water from the tank and create a puddle.
The tank can release a limited amount of water.
1 unit of water can fill up 1 unit square in the valley.
At the top of the tank, there are a left hole and a right hole that can release water.
The left hole releases water to the left.
The right hole releases water to the right.
After being released, water flows to the direction it was released. If it is released to empty space, it falls down first and starts flowing again.
If water keeps being released and pooling, a puddle can be created.
A puddle is defined as below:
Rule 1. A puddle is space connected in four directions (up, down, left, and right) formed by the pooling of water.
Rule 2. The rows within the connected space should not be abutting empty space on the left nor the right.
In other words, the left and the right sides of the space filled with water should be blocked by the valley or the tank.
Rule 3. The height of the valley or the tank abutting the space should remain the same or increase from left to right or right to left starting in the lowest column.
A puddle is space that meets the three rules above.
[Fig. 5] shows various cases of water pooling in the valley. The space filled with water is colored in blue.
[Fig. 5]
According to Rule 1, each of the blue spaces in [Fig. 5] (a) becomes a puddle. In other words, there are two puddles.
According to Rule 2, the blue space in [Fig. 5] (b) is not a puddle because it is abutting empty space on the left in Row 5.
In [Fig. 5] (c), the height of the valley increases from right to left starting in Column 5, which is the lowest column among the columns abutting the space filled with water,
until it decreases in Column 2. According to Rule 3, the blue space in [Fig. 5] (c) is not a puddle.
The blue space in [Fig. 5] (d) is a puddle that meets all the three rules above.
The amount of water used to create the puddle is 3.
The size of a puddle is the amount of water used to create the puddle.
The size of the puddle in [Fig. 5] (d) is 3.
You are required to create a puddle by releasing water to the left or right from the installed tank
and find out the size of the puddle.
Follow the rules below when creating a puddle by releasing water.
Rule 4. If the hole that releases water is blocked, water cannot be released. Therefore, a puddle cannot be created.
Rule 5. Water can be released to either the left or the right.
Rule 6. Water level cannot exceed the top of the tank.
Rule 7. You should create only one puddle. When creating the puddle, use the maximum amount of water that can be released from the tank.
In other words, create the biggest puddle possible by using available water.
In [Fig. 6] (a), a tank is installed.
The red arrows on the tank represent the locations of holes that can release water.
[Fig. 6]
If you use the left hole, a puddle is created by releasing water to the direction of the arrow as in [Fig. 6] (b).
If you release water from the left hole, you cannot use more than 3 units of water to create a puddle according to Rule 6. In other words, if you use the left hole, the maximum size of the puddle is 3.
If you release water from the right hole, water is released to the direction of the arrow as in [Fig. 6] (c). You can create a puddle by using up to 4 units of water.
The maximum size of a puddle that can be created by an installed tank is decided by the amount of available water.
If the amount of available water in [Fig. 6] (a) is 3, the puddle created by using the left hole is the biggest. If the amount of available water in [Fig. 6] (a) is 4, the puddle created by using the right hole is the biggest.
[Fig. 7] shows various cases where tanks are installed.
[Fig. 7]
In [Fig. 7] (a), you can create a puddle on the left. However, according to Rule 4, you cannot create a puddle on the right because the right hole is blocked.
If the amount of available water in [Fig. 7] (b) is 5, you can create a puddle whose size is 3 on the left or a puddle whose size is 1 on the right.
There are cases like [Fig. 7] (c) where you cannot create a puddle after successfully installing a tank because all the holes are blocked.
Given the information on the valley and the tank to be installed, you are required to write a program that finds the locations where the tank can be installed,
the biggest puddle possible that can be created by releasing water to the left or the right from the locations, and the size of the puddle.
Implement each required function by referring to the following API description.
※ The function signature below is based on C/C++. As for other languages, refer to the provided Main and User Code.
The following is the description of API to be written in the User Code.
void init(int N, int mHeight[])
This function is called at the beginning of each test case.
The width of the valley is N. The respective heights of the unit widths are given from left to right in array mHeight.
For each test case, the values of mHeight[0] and mHeight[N-1] are always given as 150.
__Parameters
_____N : Width of the valley (10 ≤ N ≤ 50,000)
_____mHeight : Heights of the unit widths of the valley
(mHeight[0]=150, mHeight[N-1]=150, 1 ≤ mHeight[i] ≤ 100, 1≤ i ≤ N-2)
int countPosition(int mLen, int mTank[])
This function returns the number of locations where the given tank can be installed.
The width of the given tank is mLen, and the respective heights of the unit widths are given in array mTank.
There is no case in which the given tank cannot be installed anywhere.
__Parameters
mLen : Width of the tank (3 ≤ mLen ≤ 5)
mTank : Heights of the unit widths of the tank (1 ≤ mTank[i] ≤ 5, 0 ≤ i ≤ mLen-1)
__Returns
_____Number of locations where the given tank can be installed
int buildAndPourOut(int mLen, int mTank[], int mWater)
This function finds the locations where the given tank can be installed
and the biggest puddle among the puddles that can be created by releasing water from the left or right hole from the locations,
and returns the size of the puddle.
The width of the given tank is mLen, and the respective heights of the unit widths of the tank are given in array mTank.
The amount of available water is given as mWater.
If it is impossible to create a puddle, 0 is returned.
It is guaranteed that the maximum number of locations where the tank can be installed is 30.
If a puddle is created by using the left hole of the given tank,
it is guaranteed that the width from the left side of the tank to the left side of the puddle does not exceed 500.
If a puddle is created by using the right hole of the given tank,
it is guaranteed that the width from the right side of the tank to the right side of the puddle does not exceed 500.
Keep in mind that the tank is not actually installed.
Therefore, the heights of the unit widths of the valley remain as in init() after buildAndPourOut() is called.
__Parameters
mLen : Width of the tank (3 ≤ mLen ≤ 5)
mTank : Heights of the unit widths of the tank (1 ≤ mTank[i] ≤ 5, 0 ≤ i ≤ mLen-1)
mWater : Amount of available water (1 ≤ mWater ≤ 100)
__Returns
_____ The biggest puddle possible that can be created by the given tank.
If it is impossible to create a puddle, 0 is returned.
[Example]
#
Function
Return
Fig.
1
init(20, [150, …, 150])
[Fig. 8] (a)
2
countPosition(3, [2, 2, 1])
2
[Fig. 8] (b)
3
countPosition(3, [4, 4, 3])
2
[Fig. 9] (a)
4
countPosition(3, [5, 4, 3])
4
[Fig. 9] (b)
5
countPosition(4, [3, 3, 2, 1])
2
[Fig.10] (a)
6
countPosition(5, [3, 3, 1, 3, 3])
1
[Fig.10] (b)
7
buildAndPourOut(3, [3, 3, 3], 1)
1
[Fig.11] (a)
8
buildAndPourOut(3, [3, 3, 3], 3)
2
[Fig.11] (b)
9
buildAndPourOut(3, [3, 3, 3], 6)
5
[Fig.11] (c)
10
buildAndPourOut(3, [5, 4, 3], 6)
6
[Fig.12]
11
buildAndPourOut(3, [5, 4, 3], 4)
4
[Fig.13]
12
buildAndPourOut(3, [3, 2, 1], 3)
3
[Fig.14]
13
buildAndPourOut(3, [5, 3, 1], 30)
9
[Fig.15] (a)
14
buildAndPourOut(3, [2, 2, 1], 5)
0
[Fig.15] (b)
(Order 2 – Order 6) The locations where the tank can be installed are represented as red boxes.
[Fig. 8]
[Fig. 9]
[Fig.10]
(Order 7) If the tank is installed in Column 13 and water is released from the right hole, the biggest puddle possible can be created. The size of the puddle is 1.
According to Rule 2, it is impossible to create a puddle by using the left hole.
(Order 8 – Order 9) Since the amount of available water is equal to or greater than 2,
the biggest puddle possible can be created by using the left hole.
[Fig.11]
(Order 10 – Order12) There are four locations where the tank can be installed.
The image below is the simulation result of creating a puddle by releasing water to the left or the right from each of the locations.
If the location of the tank is fixed, the maximum size of the puddle is decided by the amount of available water and the height of the tank.
[Fig.12]
[Fig.13]
[Fig.14]
(Order 13) If the tank is installed in Column 15, and the right hole of the tank is used,
the biggest puddle possible can be created by using 9 units of water.
(Order 14) There are two locations where the tank can be installed,
but it is impossible to create a puddle because all the holes that can release water are blocked.
[Fig.15]
[Constraints]
1. init() is called at the beginning of each test case.
2. For each test case, countPosition() is called up to 100,000 times.
3. For each test case, buildAndPourOut() is called up to 500 times.
[Input and Output]
As the input and output are processed in the provided code in the Main, they are not processed separately in the User Code.
The output result for the sample input is in the format of “#TC number result.” It is the correct answer if the result is 100; it is the wrong answer if the result is 0.
Leave a Comment