수조 센서의 마지막 유효 패킷

문제

수족관의 통신 담당자는 여러 수조에서 도착한 센서 패킷을 모아 점검 화면을 만들고 있다. 각 패킷은 정확히 16비트이며, 입력에서는 네 자리 대문자 16진수로 표현된다. 비트 번호는 가장 오른쪽을 0번, 가장 왼쪽을 15번으로 센다. 패킷의 15번 비트는 측정값의 유효 여부를 나타낸다. 이 비트가 1이면 유효한 패킷이고, 0이면 무효한 패킷이다. 14번부터 10번까지의 다섯 비트는 수조 번호를 나타내며, 9번부터 0번까지의 열 비트는 측정값을 나타낸다. 수조 번호는 0 이상 31 이하이고 측정값은 0 이상 1023 이하인 정수다. 패킷을 정수 P로 해석하면 P는 유효 여부에 32768을 곱한 값, 수조 번호에 1024를 곱한 값, 측정값을 모두 더한 값이다. 무효한 패킷에도 수조 번호와 측정값에 해당하는 비트가 들어 있지만, 그 내용은 점검 화면에 반영하지 않는다. 패킷은 수신된 순서대로 주어진다. 같은 수조에서 유효한 패킷이 여러 번 도착했다면 입력에서 가장 뒤에 있는 유효한 패킷의 측정값만 남긴다. 무효한 패킷이 나중에 도착하더라도 이미 남겨 둔 측정값을 지우거나 바꾸지 않는다. 서로 다른 수조의 패킷이 섞여 도착할 수 있으며, 같은 패킷이 연속해서 나타날 수도 있다. 입력 순서 자체가 처리 순서이므로 별도의 시각 비교는 하지 않는다. 유효한 패킷이 한 번 이상 도착한 수조만 점검 화면에 표시한다. 표시할 수조의 수와 각 수조의 마지막 유효 측정값을 구하는 프로그램을 작성한다. 수조는 번호가 작은 것부터 출력하며, 유효한 패킷이 하나도 없으면 표시할 수조의 수인 0만 출력한다.

입력

첫째 줄에 패킷 수 N이 주어진다. N은 1 이상 70000 이하인 정수다.
다음 N개 줄에 패킷이 하나씩 주어진다. 각 패킷은 0~9와 A~F로만 이루어진 정확히 네 글자의 대문자 16진수이며, 앞자리의 0도 생략하지 않는다. 모든 16비트 패턴이 입력으로 주어질 수 있다.

출력

첫째 줄에 유효한 패킷이 한 번 이상 도착한 수조의 수 K를 출력한다. 다음 K개 줄에 수조 번호와 그 수조의 마지막 유효 측정값을 공백으로 구분하여 출력한다. 수조 번호의 오름차순으로 출력한다. K가 0이면 첫째 줄만 출력한다.

6
800A
8C14
0000
8007
0C63
FFFF

3
0 7
3 20
31 1023

3
0000
7FFF
0401

0

4
FC00
FC00
7FFF
FFFF

1
31 1023

출처: Devin.KR 자체 제작