/** MIT License Copyright (c) 2018-2019 Vasilev Daniil **/
#include <bits/stdc++.h>
using namespace std;
template<typename T> using v = vector<T>;
#define int long long
typedef long double ld;
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define fs first
#define sc second
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
const long double EPS = 1e-10;
#if 0 //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt" : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin >>
#define put fout <<
#else
#define get cin >>
#define put cout <<
#endif
#define eol put endl
void read() {} template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg) ;read(args...) ;}
void print(){} template<typename Arg,typename... Args> void print(Arg arg,Args... args){put (arg)<<" ";print(args...);}
int getInt(){int a; get a; return a;}
//code starts here
v<vint> pos;
int ans = inf;
bool has(v<char>& a, int d) { for (int i : a) if (i == d) return 1; return 0; }
int pw[8] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000};
void solve(v<v<char>> a, int start, int h = 0, bool lez = 1) {
if (sz(a) == 1) {
sort(a[0].begin(), a[0].end());
int p = 0;
int lz = 0;
rep(i, 0, sz(a[0]))
if (i == 0 || a[0][i] > a[0][i - 1]) {
if (a[0][i] == 0)
lz++;
else {
p = (p * 10) + a[0][i];
for (; lz; lz--)
p = (p * 10);
}
}
if (lz) {
p = 1;
for (; lz; lz--)
p = (p * 10);
}
if (p == 0 && lez)
p = 1;
p = p * pw[h] + start;
ans = min(ans, p);
return;
} else if (sz(a) == 2) { //y = 9
for (int i = 0; i < 9; i++) { //because 99 is useless
v<char> r;
for (int j : a[0])
if (j != 9 && j != i)
r.pb(j);
for (int j : a[1])
if (j != 0 && j != i + 1)
r.pb(j);
solve({r}, pw[h + 1] * i + pw[h] * 9 + start, h + 2, i == 0);
}
}
rep(y, 0, 10 - (sz(a) == 2)) {
v<v<char>> b;
b.pb(v<char>());
int d = y;
rep(i, 0, sz(a)) {
for (int j = 0; j < 10; j++)
if (j != d && has(a[i], j))
b.back().pb(j);
d = (d + 1) % 10;
if (d == 0 && i != sz(a) - 1)
b.pb(v<char>());
}
solve(b, y * pw[h] + start, h + 1, y == 0 && sz(a[0]));
}
}
void run() {
int k;
get k;
v<v<char>> a(k);
rep(i, 0, k) {
int d;
get d;
a[i] = {(char) d};
}
solve(a, {});
put ans;
}
/* 61
5
1 2 3 4 6
*//* 89
2
9 9
*//* 8
4
8 9 0 1
*//* 499
5
9 0 5 2 0
*//* 249
5
2 5 2 5 2
*/
signed main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); put fixed << setprecision(12); run(); return 0;}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
16 ms |
384 KB |
Output is correct |
| 3 |
Correct |
6 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
13 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
128 ms |
1756 KB |
Output is correct |
| 3 |
Correct |
112 ms |
1764 KB |
Output is correct |
| 4 |
Correct |
168 ms |
1744 KB |
Output is correct |
| 5 |
Correct |
125 ms |
1816 KB |
Output is correct |
| 6 |
Correct |
85 ms |
1280 KB |
Output is correct |
| 7 |
Correct |
857 ms |
9120 KB |
Output is correct |
| 8 |
Correct |
454 ms |
6056 KB |
Output is correct |
| 9 |
Execution timed out |
1062 ms |
12976 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
13 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
