Submission #421838

#TimeUsernameProblemLanguageResultExecution timeMemory
421838rama_pangSequence (BOI14_sequence)C++17
100 / 100
346 ms9540 KiB
#include <bits/stdc++.h> using namespace std; using lint = long long; int main() { ios::sync_with_stdio(0); cin.tie(0); int N; cin >> N; vector<int> A(N); vector<int> S(N); for (int i = 0; i < N; i++) { cin >> A[i]; S[i] = 1 << A[i]; } const auto CheckAns = [&](lint K) { for (int i = 0; i < N; i++) { auto str = to_string(K); if (count(begin(str), end(str), '0' + A[i]) == 0) { return false; } K += 1; } return true; }; const lint INF = 1e17; vector<vector<int>> save(20, vector<int>(N)); const auto Solve = [&](const auto &self, int sz, int lastNonZero, int depth) -> lint { if (depth >= 17) return INF; if (sz == 0) return lastNonZero ? 0 : 1; if (sz == 1) { if (save[depth][0] == 0) return lastNonZero ? 0 : 1; if (save[depth][0] == 1) return 10; int b = 0; lint res = 0; if (save[depth][0] & 1) { // must have 0 lint opt = 1; for (b = 1; b <= 9; b++) { if ((save[depth][0] >> b) & 1) { opt = b; break; } } res = opt * 10; } for (b++; b <= 9; b++) { if ((save[depth][0] >> b) & 1) { res = res * 10 + b; } } return res; } lint res = INF; for (int st = 0; st <= 9; st++) { int dig = st; int newsz = 0; int last = 0; for (int id = 0; id < sz; id++) { int add = save[depth][id]; if ((add >> dig) & 1) add ^= 1 << dig; last |= add; if (dig == 9) { save[depth + 1][newsz++] = last; last = 0; } dig = (dig + 1) % 10; } if (last != 0) { save[depth + 1][newsz++] = last; } lint newRes = self(self, newsz, st != 0, depth + 1); res = min(res, newRes * 10ll + st); } return res; }; save[0] = S; lint ans = Solve(Solve, N, 0, 0); for (lint i = 1; i <= 1000; i++) { if (CheckAns(i)) { ans = min(ans, i); } } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...