oj.uz

답안 #604107

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
604107 2022-07-24T18:16:33 Z chuangsheep Balloons (CEOI11_bal) Java 11
20 / 100
 2000 ms 34164 KB 
import java.io.*;
import java.util.*;

// class Balloons causes compilation error on ojuz
public class bal {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// number of balloonss
		int n = Integer.parseInt(br.readLine());

		// the radius of each balloon after inflating
		double[] res = new double[n];
		// the balloons we should check when we add a new one
		Stack<Balloon> toCheck = new Stack<>();

		// simulate inflating balloons
		for (int i = 0; i < n; i++) {
			// the x coordinate and the maximum radius of the current balloon being inflated
			StringTokenizer st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			double r = Integer.parseInt(st.nextToken());

			// the maximum radius of the current balloon
			double maxR = r;
			/*
			 * as long as the stack is not empty, we want to check
			 * if the last balloon makes the radius of the current balloon smaller
			 */
			while (!toCheck.isEmpty()) {
				// the radius if the current balloon touches the last balloon
				double toLastR = toCheck.peek().calcR(x);
				/*
				 * the maximum possible radius is the smaller one between current 
				 * maximum and the maximum radius so that we touches the last balloon
				 * (by which we have to stop)
				 */
				maxR = Math.min(maxR, toLastR);

				/*
				 * if current maximum radius >= radius of the last balloon, we can
				 * remove the last balloon since it will never be touched by any
				 * new balloons other than the current one
				 */
				if (maxR >= toCheck.peek().r) {
					toCheck.pop();
					// check the next balloon saved which will possibly reduce max_r
					continue;
				}
				/*
				 * otherwise, the current balloon is smaller than the last saved balloon
				 * and we can stop checking
				 */
				else {
					break;
				}
			}
			/*
			 * save the x coordinate and radius of the current balloon, so that
			 * it can be checked later when a new balloon being inflated
			 */
			toCheck.add(new Balloon(x, maxR));
			res[i] = maxR;
		}

		for (double r : res) {
			System.out.println(r);
		}

	}

	// class to save the data of an infalted balloon
	private static class Balloon {
		public int x;
		public double r;

		public Balloon(int x, double r) {
			this.x = x;
			this.r = r;
		}

		/*
		 * how long can the radius of the new balloon at position bx be
		 * so that it touches the ballon a, which is described by
		 * its x position a.first and its radius a.second
		 */
		public double calcR(int bx) {
			return (x - bx) * (x - bx) / (4 * r);
		}
	}
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 8716 KB 10 numbers

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 57 ms 8508 KB 2nd numbers differ - expected: '252735385.4379999936', found: '0.9334151241', error = '252735384.5045848787'
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 8916 KB 505 numbers

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 508 ms 23668 KB 506th numbers differ - expected: '365.0000000000', found: '-2481854.0646065245', error = '2482219.0646065245'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1242 ms 28836 KB 655th numbers differ - expected: '591.0000000000', found: '-2402336.3030539569', error = '2402927.3030539569'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1324 ms 22164 KB 4th numbers differ - expected: '15396.0000000000', found: '-8148.5509720554', error = '23544.5509720554'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1979 ms 33140 KB 7234th numbers differ - expected: '7160.0000000000', found: '-2398141.9988687783', error = '2405301.9988687783'
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1848 ms 26788 KB 4643rd numbers differ - expected: '2427.0000000000', found: '-2355611.7017843765', error = '2358038.7017843765'
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2048 ms 27448 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2048 ms 34164 KB Time limit exceeded
2 Halted 0 ms 0 KB -