시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 1500 | 434 | 330 | 33.000% |
창영이와 현우는 새로운 게임을 하고 있다. 이 게임은 여러 라운드로 이루어져 있다. 매 라운드가 시작할 때, 현우는 창영이에게 100보다 작은 두 숫자 A와 B를 말해준다. 그러고 난 뒤, 창영이는 다음과 같은 문제를 풀어야 한다.
지금까지 현우가 말한 모든 A와 모든 B를 짝짓는다. 이때, 각 쌍의 합 중에서 가장 큰 값을 작게 만들어라.
즉, 현재 라운드가 N 라운드이라고 하면, 현우가 창영이에게 말한 숫자는 a1, a2, ..., an 과 b1, b2, ..., bn이라고 할 수 있다. 이때, 각 숫자를 한 번씩 사용하여 (ai, bj)쌍을 n개 만들 수 있다. 이렇게 쌍을 모두 만들었을 때, ai+bj의 합 중 가장 큰 값을 가능한 작게 만들어야 한다.
첫째 줄에 라운드의 수 N이 주어진다. (1 ≤ N ≤ 100000) 다음 N개의 줄에는 각 라운드에서 현우가 말한 숫자 A와 B가 주어진다. (1 ≤ A, B < 100)
출력은 N줄이다. 각 줄은 해당하는 라운드에서 창영이가 말해야하는 값 (모든 쌍의 합의 최댓값의 최솟값) 이다.
3 2 8 3 1 1 4
10 10 9
3 1 1 2 2 3 3
2 3 4
Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #1 4번