pstopia Notes for Problem Solving Contest

[Easy] ToastXToast

Topcoder SRM 503 Div1

Problem

under와 over들을 다 모아놓고 수직선에 배열한 상황을 상상해보자. 제일 왼쪽에 있는 over의 왼쪽에 under가 하나라도 없다면 -1 마찬가지로 제일 오른쪽에 있는 under의 오른쪽에 over가 하나라도 없다면 -1 모든 under가 왼쪽에, 모든 over가 오른쪽에 있도록 나누는 point가 존재하면 1 여기까지는 자명하고, 이제 그 외 경우의 답은 무조건 2다. 제일 왼쪽의 under 하나를 고르고 나머지 over를 모두 모아 한 셋에 몰아넣고 제일 오른쪽의 over 하나를 고르고 나머지 under를 모두 모아 한 셋에 몰아넣으면 되기 때문.