앵무새
풀이 (P = 7)

만약 들어오는 수 0 <= N〈= 255 하나를 우리가 0, 1, 2, 3을 이용해서 앵무새를 보내야한다고 해보자. 몇 마리의 앵무새가 필요할까?

7 H 5 = 330 이므로 7마리의 앵무새면 충분하다. (앵무새를 보내지 않는 경우도 생각해야 한다)

그렇다면, 들어오는 수는 모두 64개 이므로, 첫 위치의 수는 0, 1, 2, 3을, 두 번째 위치의 수는 4, 5, 6, 7을, ... 이런 식으로 64번째 위치의 수는 252, 253, 254, 255를 사용하면 된다.

이를 이용하면, 입력되는 문자열의 7배의 길이의 인코딩으로 문제를 해결할 수 있다.

코드 (98 점)
/* encoder.cpp */ #include "encoder.h" #include "encoderlib.h" static int LIB[257][7]; static void init() { int arr[7] = {-1, -1, -1, -1, -1, -1, -1}; for (int i = 0; i < 257; ++i) { for (int j = 0; j < 7; ++j) LIB[i][j] = arr[j]; int k; for (k = 6; arr[k] == 3; --k); ++arr[k]; for (int l = k + 1; l <= 6; ++l) arr[l] = arr[k]; } } void encode(int N, int M[]) { static bool isSet = true; if (isSet) { isSet = false; init(); } for (int i = 0; i < N; ++i) { for (int j = 0; j < 7; ++j) { if (LIB[M[i] + 1][j] == -1) continue; send(LIB[M[i] + 1][j] + (4 * i)); } } }/* decoder.cpp */ #include "decoder.h" #include "decoderlib.h" #include <algorithm> static int LIB[257][7]; static void init() { int arr[7] = {-1, -1, -1, -1, -1, -1, -1}; for (int i = 0; i < 257; ++i) { for (int j = 0; j < 7; ++j) LIB[i][j] = arr[j]; int k; for (k = 6; arr[k] == 3; --k); ++arr[k]; for (int l = k + 1; l <= 6; ++l) arr[l] = arr[k]; } } static int find_num(int arr[7]) { int l = 0, r = 256; while(l <= r) { const int m = (l + r) >> 1; int fl; for (int i = 0; i < 7; ++i) { fl = arr[i] - LIB[m][i]; if (fl != 0) break; } if (fl == 0) return m; else if (fl > 0) l = m + 1; else r = m - 1; } return -1; } void decode(int N, int L, int X[]) { static bool isSet = true; if (isSet) { isSet = false; init(); } std::sort(X, X + L); int arr[7], arl = 0, nl = 3; for (int i = 0; i < L; ++i) { if (nl < X[i]) { nl += 4; for (int j = arl; j < 7; ++j) arr[j] = -1; std::sort(arr, arr + 7); const int n = find_num(arr) - 1; if (n != -1) output(n); arl = 0; } arr[arl++] = X[i] % 4; } for (int j = arl; j < 7; ++j) arr[j] = -1; std::sort(arr, arr + 7); const int n = find_num(arr) - 1; if (n != -1) output(n); }

그러면 100점짜리는? Bigint 써서 모든 조합에 대해 일대일 대응을 해주면 된다.


---


귀찮아서 옛날에 쓴거 배껴옴