2686번 - 팩스 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 76 | 17 | 16 | 39.024% |
문제
팩스 머신은 run-length encoding(RLE)을 이용해 데이터를 압축한다. 데이터는 같은 값이 연속적으로 많이 나타나는 수열이라 할 수 있다. 이러한 연속적인 같은 값을 run이라 한다. 그래서 RLE는 그 수열을 그대로 저장하는 대신 하나의 데이터 값과 그 값의 개수로 데이터를 표현한다. 이 인코딩 방식은 아이콘이나 텍스트, 선 등의 비교적 간단한 그래픽 이미지 같은 런이 많은 데이터에서 유용하다. 만약 사진과 같이 런이 적은 파일에 적용한다면 오히려 원래 파일 사이즈보다 커질 가능성도 있다.
한 블록의 데이터를 RLE 알고리즘을 사용해 인코딩하려고 한다. 하나의 런은 2바이트 수열을 사용해 표현한다. 첫 번째 바이트는 하나의 값이 반복된 횟수이고, 두 번째 바이트는 그 값을 나타낸다. 반복 횟수는 최상위 비트가 1이고 나머지 7비트는 반복 횟수 - 3인 8비트 수로 표현된다. 따라서 데이터에서 같은 값은 수열의 2바이트 당 최대130번 나타날 수 있다. 또한 런의 최소 수는 3이다. 런이 아닌 바이트들은 prefix 바이트로 인코딩되는데, 이 바이트는 런이 아닌 바이트의 개수 - 1을 나타내며, 최상위 비트는 항상 0이다. 따라서 prefix 바이트의 범위는 0 ~ 127로, 1부터 128까지의 수를 표현한다.
만약 런이 130바이트보다 크다면 여러 개의 2바이트 수열로 표현한다. 이 경우 수열의 첫 번째는 항상 크기가 130인 런이다. 3회 이상 반복된 값은 반드시 런으로 인코딩되어야 한다. 만약 런이 아닌 값이 128바이트보다 길다면 prefix 바이트를 여러 개 사용해 표현한다. 예를 들어, 길이가 262인 런은 크기가 130인 런 두 개와 크기가 2인 prefix 바이트로 인코딩한다.
입력
입력의 첫 줄에 데이터 셋의 수인 정수 P(1 ≤ P ≤ 1000)가 주어진다.
각 데이터 셋의 첫 줄에는 바이트의 수 B(1 ≤ B ≤ 5000)가 십진수 정수로 주어진다.
다음 줄 부터 인코딩 할 데이터가 주어진다. 데이터의 마지막 줄을 제외한 나머지 줄에는 16진수가 80자리 주어지며, 마지막 줄은 80자리보다 적을 수 있다. 두 16진수 자리가 한 바이트를 표현한다. 16진수 자리는 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F로 이뤄져 있다.
출력
각각의 데이터 셋에 대해 첫 줄에는 인코딩 된 바이트의 수를 출력한다. 나머지 줄에는 인코딩 된 데이터를 16진수로 출력한다. 각 줄은 마지막 줄을 제외하고 16진수 80자리를 출력한다. 마지막 줄은 80자리 이하이다.
예제 입력 1
4 1 07 5 F4A5A5A5A5 44 0000000000000000FFFFFF66665A5A5A5A5A71727374758008011011135555555555555501020399 777777CC 40 68686868686868686868686868686868686868686868686868686868686868686868686868686868
예제 출력 1
2 0007 4 00F481A5 32 850080FF016666825A0A717273747580080110111384550301020399807700CC 2 A568
출처
ICPC > Regionals > North America > Greater New York Region > 2010 Greater New York Programming Contest C번
- 문제를 번역한 사람: arine
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호