아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

교통량

면접 대비

시간 제한1초메모리 제한256 MB

요약
두 상자에 기록된 순서 없는 시각과 500, 1000, 1500의 고정된 간격을 이용해 왼쪽에서 온 차가 몇 대인지 셉니다.
난이도

보통10점 중 5점

유형
그리디, 정렬, 시뮬레이션
정답자
아직 제출이 없습니다

문제

승민이는 마포대교의 교통량을 측정한다. 도로를 가로지르는 끈 두 개를 일정한 간격을 두고 나란히 매달아 놓았고, 자동차 바퀴가 끈 위를 지날 때마다 끈 끝에 달린 작은 상자에 그 시각이 기록된다. 왼쪽 끈의 기록은 왼쪽 상자에, 오른쪽 끈의 기록은 오른쪽 상자에 쌓인다.

왼쪽에서 오는 자동차 한 대는 기록 네 개를 남긴다.

  • 왼쪽 끈 위로 앞바퀴가 지나간 시각 tt
  • 왼쪽 끈 위로 뒷바퀴가 지나간 시각 t+500t + 500
  • 오른쪽 끈 위로 앞바퀴가 지나간 시각 t+1000t + 1000
  • 오른쪽 끈 위로 뒷바퀴가 지나간 시각 t+1500t + 1500

오른쪽에서 오는 자동차는 왼쪽과 오른쪽을 바꾸어 같은 규칙으로 기록을 남긴다. 즉 오른쪽 상자에 tt와 t+500t + 500이, 왼쪽 상자에 t+1000t + 1000과 t+1500t + 1500이 기록된다.

한 끈 위에는 많아야 자동차 한 대가 지나가고 있다. 두 상자의 시간 기록이 주어질 때, 왼쪽에서 온 자동차가 몇 대인지 구하여라.

입력

첫째 줄에 테스트 케이스의 개수 nn (1≤n≤1001 \le n \le 100)이 주어진다.

각 테스트 케이스의 첫째 줄에는 상자 하나에 기록된 시각의 개수 mm (0≤m≤2000 \le m \le 200)이 주어진다. 자동차 한 대가 상자마다 기록을 두 개씩 남기므로 mm은 짝수이다. 둘째 줄에는 왼쪽 상자에 기록된 시각 mm개가, 셋째 줄에는 오른쪽 상자에 기록된 시각 mm개가 주어진다. 각 시각은 10910^9보다 작은 음이 아닌 정수이고, 주어지는 순서는 정해져 있지 않다. m=0m = 0이면 두 줄은 비어 있다.

입력은 언제나 위 규칙을 지키는 자동차들로 설명할 수 있다.

출력

각 테스트 케이스마다 왼쪽에서 온 자동차의 수를 한 줄에 하나씩 출력한다.

예제4

  1. 예제 1

    입력
    2
    4
    17 517 1432 1932
    432 932 1017 1517
    6
    235 451 735 951 2351 2851
    1235 1351 1451 1735 1851 1951
    
    예상 출력
    1
    2
    
  2. 예제 2

    입력
    2
    2
    0 500
    1000 1500
    2
    1000 1500
    0 500
    
    예상 출력
    1
    0
    
  3. 예제 3

    입력
    1
    4
    10 510 1010 1510
    1010 1510 10 510
    
    예상 출력
    1
    
  4. 예제 4

    입력
    3
    0
    
    
    2
    1007 1507
    7 507
    4
    7 507 2600 3100
    1007 1507 3600 4100
    
    예상 출력
    0
    0
    2