제출 #1163194

#제출 시각아이디문제언어결과실행 시간메모리
1163194steveonalexPassword (RMI18_password)C11
0 / 100
4 ms412 KiB
/** * Count symbol frequencies. Choose a symbol at random and count the * frequencies of other symbols to its left and right. Then solve each side * recursively. * * The recurrence for the number of queries is * * Q(n) = num_symbols_used_in_subproblem - 1 + 2 Q(n / 2) * * This performs sigma - 1 queries for larger subproblems, but only n - 1 when * n < sigma. Computing the sum by hand yields a theoretical maximum of N(2 + * log sigma), or 33,500 for the given parameters, although in practice it * never exceeds 24,000. * * The implementation wastes a factor of sigma. We could shave it off by * storing subproblems as pairs <symbol, frequency> for symbols in use (as * opposed to all the sigma frequencies). * * Author: Catalin Francu **/ #include <stdlib.h> #include <string.h> #include <time.h> #define MAX_N 5000 #define MAX_SIGMA 26 char q[MAX_N + 1]; /* build queries here */ char sol[MAX_N + 1]; /* build solution here */ int f[MAX_N][MAX_SIGMA]; int lf[MAX_SIGMA]; /* frequencies left of the current subproblem */ int n, s, solLen; int query(char *q); /* run s-1 queries to determine element frequencies */ /* the last frequency is computed by difference */ void findFrequencies() { int remainder = n; q[n] = '\0'; for (int i = 0; i < s - 1; i++) { memset(q, 'a' + i, n); f[0][i] = query(q); remainder -= f[0][i]; } f[0][s - 1] = remainder; } /* Choose a random character from the current symbol set. If we choose the */ /* 5th occurrence of the 'c' symbol, set *sym = 2, *k = 4 (0-based). */ void chooseRandom(int level, int* sym, int* k) { /* find the problem size */ int len = 0; for (int i = 0; i < s; i++) { len += f[level][i]; } *k = rand() % len; *sym = 0; while (*k >= f[level][*sym]) { *k -= f[level][*sym]; (*sym)++; } } void solve(int level) { /* count used symbols */ int numUsed = 0, solc, solf; for (int i = 0; i < s; i++) { if (f[level][i]) { numUsed++; solc = i; solf = f[level][i]; /* syntactic sugar */ } } if (numUsed == 0) { return; } if (numUsed == 1) { memset(sol + solLen, 'a' + solc, solf); solLen += solf; lf[solc] += solf; return; } int sym, k, answer; /* choose a random symbol */ chooseRandom(level, &sym, &k); /* output enough copies of the pivot so that all queries */ /* pass through the pivot */ memset(q, 'a' + sym, lf[sym] + k + 1); /* compute frequencies of left subproblem */ for (int i = 0; i < s; i++) { if (i == sym) { f[level + 1][i] = k; } else if (f[level][i]) { /* Run a query to count the number of i symbols right of the pivot. */ /* The query consists of: */ /* - all copies of sym up to the pivot, including those already solved; */ /* - all copies of i except those already solved. */ memset(q + lf[sym] + k + 1, 'a' + i, f[0][i] - lf[i]); q[lf[sym] + k + 1 + f[0][i] - lf[i]] = '\0'; /* The answer consists of: */ /* - number of sym's up to the pivot */ /* - number of i's to the right of the current problem */ /* - number of i's in the right subproblem */ /* We want the number of i's in the left subproblem, which we can */ /* compute by difference. */ answer = query(q); answer -= lf[sym] + k + 1; /* keep just the i's */ int left = f[0][i] - answer - lf[i]; f[level + 1][i] = left; } else { f[level + 1][i] = 0; } } solve(level + 1); /* output the pivot itself */ sol[solLen++] = 'a' + sym; lf[sym]++; /* compute frequencies of the right subproblem by difference (f[level] */ /* stores the entire problem and f[level + 1] stores the left subproblem) */ for (int i = 0; i < s; i++) { f[level + 1][i] = f[level][i] - f[level + 1][i]; } f[level + 1][sym]--; /* subtract the pivot itself */ solve(level + 1); } char* guess(int localN, int localS) { srand(time(NULL)); n = localN; s = localS; findFrequencies(); solve(0); sol[solLen] = '\0'; return sol; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...