Sunday, September 15, 2013

acmicpc.net - 2013 인터넷 예선 대비 대회 5


Link : http://www.acmicpc.net/contest/view/11

A. 콘센트 - Accepted
Greedy. Note that if n and m is 0, the answer is 1

B. K번째 숫자 - Accepted
Segment tree, Merge Sort or Binary search

C. 포켓볼 - Accepted
Easy to solve with STL Map or Set.

D. 토너먼트 조작 - Accepted
Given n = (2^k) teams, and a team 1 such that for every team t that 1 cannot beat, 1 can beat a team t` that can beat t and 1 can beat as least half of the teams.
For every round (k in total) of the tournament
1) Match as many teams t that beat 1 to teams t` that can win them.
2) Let 1 play against a team from which it can win.
3) Let any remaining teams play against each other.
4) Remove the losers.

E. 책 쌓기 - Accepted
Pulling out a book in the sorted top is never useful, so always pull out the first non-sorted book
To move a big book from the top to position i, takes ( 2 ^ i )−1 steps.
Through the fact, we can solve this in O(N).

F. RFID 추적
Not solved yet.

G. L퍼즐
2 - SAT. Make connections for 'B'  with 4 directions and 'W' with all of  'B'.

H. 열차 지연 - Accepted
1) Dijkstra with heap or priority queue or 2) Bellman-Ford Algorithm.
D[x][t] = when the time is 't', the minimum cost of station 'x'.

I. 수영장 만들기
Not solved yet.

J. 정수 직사각형 - Accepted
Preprocess - sorting and counting

No comments:

Post a Comment