시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 1024 MB 0 0 0 0.000%

문제

When you live out in the Finnish woods, far away from all the cities, Internet connectivity has a wildly varying quality. This has clear disadvantages when doing competitive programming, especially since most competitions take place online.

To improve reliability of your connection to the Internet, the Internet Engineering Task Force issued a standard on April 1, 1990 called IP over Avian Carriers. This standard describes how birds can be used to deliver Internet traffic. Birds do not suffer from e.g. cut-off cables or power outages, thus serving as an effective fallback to a standard Internet connection. Unfortunately, birds suffer from other problems. When sending a number of birds with data, they don’t deliver data in order, and sometimes birds are lost on the way.

Your task is to implement two programs to add some redundancy to this bird delivery protocol – an encoder and a decoder. The encoder will be given a string X which consists of C · N bits (i.e. digits 0 or 1), with N > 1. It should produce a vector of K elements S[0], S[1], . . . , S[K − 1] where each S[i] is a string of N bits.

Afterwards, your decoder will be given a subset of C elements from this vector. It should then output the original bit string X.

Encoder

Your encoder should implement the function vector<string> encode(int C, int K, int N, string X). It will be given the integers C, K and N from the task description, and the bit string X. X will have length C · N, and only consists of characters 0 and 1.

The encoder should output a vector of K strings. Each string should be of length N, and only contain characters 0 and 1.

Decoder

The decoder should implement the function string decode(int C, int K, int N, vector<string> Y, vector<int> I). It will be given the integers C, K and N from the task description, and a subset Y of the strings S output by encode(C, K, N, X). Y and I will both have length C. I will contain the zero-based indices of the strings taken from the encoder, such that Y [i] is the I[i]:th string (i.e. Y [i] = S[I[i]]).

The decoder should output the original string X of length exactly C · N.

Implementations

You should not use standard in or standard out (i.e. reading or writing to the terminal) in this task. Doing so will likely cause confusing errors.

Additionally, the program will be restarted before running the decoder. Thus, any global state you use will be erased.

서브태스크 1 (30점)

  • C = 3
  • K = 4
  • 1 < N ≤ 1000

서브태스크 2 (25점)

  • C = 2
  • K = 4
  • 1 < N ≤ 1000
  • N ≡ 0 (mod 2) i.e. N is even.

서브태스크 3 (20점)

  • C = 2
  • K = 4
  • 1 < N ≤ 1000

서브태스크 4 (25점)

  • C = 3
  • K = 5
  • 1 < N ≤ 1000

출처

Olympiad > Nordic Olympiad in Informatics > NOI 2017 C번

  • 문제의 오타를 찾은 사람: eric00513

제출할 수 있는 언어

C++14, C++, C++11, C++17, C++ (Clang), C++11 (Clang), C++14 (Clang), C++17 (Clang)

채점

  • 예제는 채점하지 않는다.