정렬된 트리거 시각들이 주어질 때, 1000ms 이하 간격은 같은 차량, 2000ms 이상 간격은 다른 차량이라는 규칙에 따라 이륜 차량과 삼륜 차량의 수를 세는 문제이다.
보통6동적 계획법그리디아직 제출이 없습니다시간 제한3초메모리 제한512 MB시의회가 도로에 압력판을 깔아 통행량을 기록한다. 압력판은 차량의 한 축에 달린 바퀴가 판 위를 지날 때마다 그 시각을 기록한다. 이 도로를 지나는 차량은 축이 두 개인 승용차뿐이고, 각 승용차는 축이 하나인 트레일러를 달고 있을 수도 있고 달고 있지 않을 수도 있다.
트레일러가 없는 승용차가 압력판을 지나면 앞바퀴가 지나는 시각과 뒷바퀴가 지나는 시각, 모두 두 개의 시각이 기록된다. 트레일러를 달고 있으면 트레일러 바퀴가 지나는 시각이 하나 더해져 세 개가 기록된다. 한 차량이 남긴 기록은 시간 순서에서 연속으로 놓인다.
기록만 놓고 보면 해석이 하나로 정해지지 않는다. 기록이 6개라면 트레일러가 없는 승용차 세 대일 수도 있고, 트레일러를 단 승용차 두 대일 수도 있다. 이런 모호함을 줄이려고 다음 두 가정을 둔다.
기록된 시각이 주어질 때, 트레일러가 없는 승용차의 대수와 트레일러를 단 승용차의 대수를 구하라.
첫째 줄에 압력판이 눌린 횟수 n (1≤n≤300000)이 주어진다.
둘째 줄에 압력판이 눌린 시각 t1,t2,…,tn (0≤ti<230)이 증가하는 순서로 주어진다. n개의 시각은 모두 다르고, 단위는 밀리초다.
두 종류의 대수가 하나로 정해지면 다음 두 줄을 출력한다. X는 트레일러가 없는 승용차의 대수, Y는 트레일러를 단 승용차의 대수다.
Cars without trailers: X
Cars with trailers: Y
두 가정에 맞는 해석이 하나도 없으면 Impossible을 출력한다. 해석이 여러 가지이고 그중에 대수가 서로 다른 것이 있으면 Ambiguous를 출력한다.