IP over Avian Carriers

핀란드 숲속 깊은 곳, 도시에서 멀리 떨어져 살면 인터넷 연결 품질이 심하게 들쭉날쭉하다. 대부분의 대회가 온라인으로 열리는 경쟁 프로그래밍에서는 이것이 분명한 불편이 된다.

1990년 4월 1일, 인터넷 기술 특별 조사단(IETF)은 새를 이용해 인터넷 트래픽을 전달하는 표준인 IP over Avian Carriers를 발표했다. 새는 케이블이 끊기거나 정전이 되어도 영향을 받지 않으므로, 일반 연결을 대신하는 효과적인 대비책이 된다. 다만 새에게도 문제가 있다. 데이터를 실은 새를 여러 마리 보내면 데이터가 순서대로 도착하지 않고, 일부 새는 도중에 길을 잃는다.

여러분의 임무는 이 새 배달 프로토콜에 중복성을 더하는 프로그램 두 개, 즉 인코더와 디코더를 구현하는 것이다. 인코더는 $C \times N$개의 비트(0 또는 1)로 이루어진 문자열 $X$를 입력받는다. 단, $N > 1$이다. 인코더는 각각 $N$비트 문자열인 원소 $S[0], S[1], \ldots, S[K-1]$로 이루어진 벡터를 출력해야 한다. 원소 개수는 $K$개이다.

디코더는 이 벡터의 원소 중 $C$개로 이루어진 부분집합을 입력받는다. 그런 다음 원래의 비트 문자열 $X$를 출력해야 한다.