만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

압력판 교통량 세기

시간 제한3초메모리 제한512 MB

요약
정렬된 트리거 시각들이 주어질 때, 1000ms 이하 간격은 같은 차량, 2000ms 이상 간격은 다른 차량이라는 규칙에 따라 이륜 차량과 삼륜 차량의 수를 세는 문제이다.
난이도

보통10점 중 6점

유형
동적 계획법, 그리디
정답자
아직 제출이 없습니다

문제

시의회가 도로에 압력판을 깔아 통행량을 기록한다. 압력판은 차량의 한 축에 달린 바퀴가 판 위를 지날 때마다 그 시각을 기록한다. 이 도로를 지나는 차량은 축이 두 개인 승용차뿐이고, 각 승용차는 축이 하나인 트레일러를 달고 있을 수도 있고 달고 있지 않을 수도 있다.

트레일러가 없는 승용차가 압력판을 지나면 앞바퀴가 지나는 시각과 뒷바퀴가 지나는 시각, 모두 두 개의 시각이 기록된다. 트레일러를 달고 있으면 트레일러 바퀴가 지나는 시각이 하나 더해져 세 개가 기록된다. 한 차량이 남긴 기록은 시간 순서에서 연속으로 놓인다.

기록만 놓고 보면 해석이 하나로 정해지지 않는다. 기록이 6개라면 트레일러가 없는 승용차 세 대일 수도 있고, 트레일러를 단 승용차 두 대일 수도 있다. 이런 모호함을 줄이려고 다음 두 가정을 둔다.

  1. 연속한 두 시각의 차이가 1000 ms 이하이면 두 기록은 같은 차량에서 나온 것이다.
  2. 연속한 두 시각의 차이가 2000 ms 이상이면 두 기록은 서로 다른 차량에서 나온 것이다.

기록된 시각이 주어질 때, 트레일러가 없는 승용차의 대수와 트레일러를 단 승용차의 대수를 구하라.

입력

첫째 줄에 압력판이 눌린 횟수 nn (1≤n≤300 0001 \le n \le 300\,000)이 주어진다.

둘째 줄에 압력판이 눌린 시각 t1,t2,…,tnt_1, t_2, \dots, t_n (0≤ti<2300 \le t_i < 2^{30})이 증가하는 순서로 주어진다. nn개의 시각은 모두 다르고, 단위는 밀리초다.

출력

두 종류의 대수가 하나로 정해지면 다음 두 줄을 출력한다. XX는 트레일러가 없는 승용차의 대수, YY는 트레일러를 단 승용차의 대수다.

Cars without trailers: X
Cars with trailers: Y

두 가정에 맞는 해석이 하나도 없으면 Impossible을 출력한다. 해석이 여러 가지이고 그중에 대수가 서로 다른 것이 있으면 Ambiguous를 출력한다.

예제3

  1. 예제 1

    입력
    7
    10 200 5000 6100 7200 8300 9400
    
    예상 출력
    Cars without trailers: 2
    Cars with trailers: 1
    
  2. 예제 2

    입력
    6
    0 1100 2200 3300 4400 5500
    
    예상 출력
    Ambiguous
    
  3. 예제 3

    입력
    4
    0 1000 2000 3001
    
    예상 출력
    Impossible