시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 58 | 36 | 34 | 61.818% |
Taro is playing with a set of toy rail tracks. All of the tracks are arc-shaped with a right central angle (an angle of 90 degrees), but with many different radii. He is trying to construct a single loop using all of them. Here, a set of tracks is said to form a single loop when both ends of all the tracks are smoothly joined to some other track, and all the tracks are connected to all the other tracks directly or indirectly. Please tell Taro whether he can ever achieve that or not.
Tracks may be joined in an arbitrary order, but their directions are restricted by the directions of adjacent tracks, as they must be joined smoothly. For example, if you place a track so that a train enters eastward and turns 90 degrees northward, you must place the next track so that the train enters northward and turns 90 degrees to either east or west (Figure F.1). Tracks may cross or even overlap each other as elevated construction is possible.
Figure F.1. Example of smoothly joining tracks
The input consists of a single test case in the following format.
$n$
$r_1$ $\cdots$ $r_n$
$n$ represents the number of tracks, which is an even integer satisfying $4 ≤ n ≤ 100$. Each $r_i$ represents the radius of the $i$-th track, which is an integer satisfying $1 ≤ r_i ≤ 10000$.
If it is possible to construct a single loop using all of the tracks, print Yes
; otherwise, print No
.
4 1 1 1 1
Yes
6 1 3 1 3 1 3
Yes
6 2 2 1 1 1 1
No
8 99 98 15 10 10 5 2 1
Yes
Possible loops for the sample inputs 1, 2, and 4 are depicted in the following figures.
(a) Sample 1 | (b) Sample 2 | (c) Sample 4 |
Figure F.2. Possible loops for the sample inputs
ICPC > Regionals > Asia Pacific > Japan > ICPC 2022 Asia Yokohama Regional F번