#Practice Codeforces Round #100

새로운 연습실에서 처음으로 돈 세트이다.

A,B,C,D를 해결했지만 문제 내에 번뜩이는 아이디어는 없었다. B번의 해석이 이해가 안돼서 많은 시간을 소비했다.

A. New Year Table

반지름 R인 원 안에 반지름이 r인 원 n개를 큰 원의 변에 접하도록 넣을 수 있는 지 묻는 문제이다.(n<=100,r,   R<=1000)

 

Sol :

설명은 아래 그림으로 대체한다.

 

Code : http://ideone.com/Z1stAW

B. New Year Cards

N명의 친구들에게 편지를 받고 나눠주는 문제이다. 편지는 1부터 n까지 차례대로 받게 된다. 편지를 받게되면 그 편지는 여러명의 친구들에게 나누어 줄 수 있다. 또한 각각의 친구는 한장의 편지만 받게 된다.(2<=N<=300)

N명의 친구들은 모두 편지에 대해서 선호도를 가지고있고, 자신도 편지들에 대해서 선호도를 가지고있다.

현재 i번째 편지를 받은 후 자신이 편지를 보낼 때, 가지고 있는 편지들은 사람 x에게 다음 두 규칙을 따라서 줄 수 있다.

1. x가 i와 같으면 i번째 편지는 보낼 수 없다.

2. 위 편지를 제외하고 나머지 편지중, 자신의 선호도가 가장 높은 편지만을 보낼 수 있다.

위와 같은 규칙을 따를때 친구들의 선호도가 가장 높도록 편지를 나누어 주는 방법을 묻는 문제이다.

 

Sol :

각 편지들에 대해서 보낼 수 있는 편지인지 결정한 후, 각 사람들의 선호도가 높은순서로 보낼 수 있는가? 로 풀면 된다..

 

Code: http://ideone.com/xm3N4p

 

C. New Year Snowmen

크기 n의 수열이 입력으로 주어졌을때 서로 다른 3개의 묶음을 얼마나 많이 만들 수 있는가? 를 묻는 문제이다. (1<=n<=10^5)

 

Sol :

각 숫자들을 숫자, 빈도수로 새로 저장을 한 후, 힙을 이용해서 가장 빈도수가 큰 3개의 숫자를 하나로 묶고 다시 힙에 넣어주는 식으로 해결하면 된다.

 

Code : http://ideone.com/tP6Imz

 

D. New Year Contest

n개의 숫자를 입력받고 icpc패널티를 최소화 시키는 문제이다. 경기시간은 720분이고, 문제읽는 시간을 10분 소모한다. 360분이 지난 후에 패널티를 추가하는 방식이다.

 

Sol :

문제를 푸는데 드는 시간이 적은 문제부터 해결하면 된다.

 

Code : http://ideone.com/svvTeC