[Codeforces] Round #477

다행히 4문제를 풀어내면서 다시 보라색으로 재진입할 수 있었습니다.

 

A - Mind the Gap

 

이 문제도 영어가 잘 안읽혀서 살짝 고생했지만, 결론적으로는 그냥 시간 차가 2s+2 이상 벌어진 곳이 있는지를 찾는 문제입니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20477/A.cpp

B - Watering System

 

앞에서부터 합을 누적해가며 B 이상이 공급 가능한지를 확인하면 됩니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20477/B.cpp

 

C - Stairs and Elevators

 

출발지와 도착지의 왼쪽, 오른쪽에 가장 가까운 엘리베이터 / 계단 총 2+2 = 4개에 대해 시간이 얼마나 소요하는지를 확인해보면 됩니다. 맨 처음에 n, m이 1e8 이하가 아니라 1e6 이하라고 생각해서 미리 테이블을 만들어 해결하려다가 런타임에러를 일으키고, 두 번째로는 출발지와 도착지가 동일 층에 있는 경우를 생각안해서 hack을 당한 후에 맞았습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20477/C.cpp

 

D - Resource Distribution

 

일단 Resource를 정렬해둡시다. 예제인 2 3 5 7 8 9를 보면, 각 resource에 대해 자신 이상의 resource만을 활용할 경우 필요한 resource의 수는 first service(8)의 경우 4 3 2 2 1 1, second service(16)의 경우 8 6 4 3 2 2입니다. 이를 역으로 생각해보면, first service를 제공하고 나면 2, 3, 5의 경우 2개의 resource가 남고, 7, 8의 경우 1개의 resource가 남고, 9의 경우 0개의 resource가 남습니다. 이 남는 resource를 second service에 활용한다고 생각하면 binary search로 찾아낼 수 있음을 알 수 있습니다.

 

https://github.com/blisstoner/Codeforces/blob/master/Round%20477/D.cpp