oj.uz

Submission #98860

# Submission time Handle Problem Language Result Execution time Memory
98860 2019-02-26T19:56:35 Z SpeedOfMagic Sequence (BOI14_sequence) C++17
0 / 100
 89 ms 1792 KB 
/** 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 (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;
    }

    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);
    }
}
void run() {
    int k;
    get k;
    v<v<char>> a(k);
    rep(i, 0, k) {
        int d;
        get d;
        a[i] = {(char) d};
    }

    for (int z = 99; z > 0; z -= ((z > 10) ? 10 : 1))
        rep(i, 0, k) {
            int need = a[i][0];
            int p = z + i;
            while (p) {
                if (need == p % 10)
                    goto nxt;
                else
                    p /= 10;
            }
            break;
            nxt:;
            if (i == k - 1)
                ans = z;
        }
    solve(a, {});

    put ans;
}
/* 61
5
1 2 3 4 6
*//* 89
2
9 9
*//* 8
4
8 9 0 1
*/
signed main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); put fixed << setprecision(12); run(); return 0;}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 7 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 7 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 89 ms 1748 KB Output is correct
3 Correct 89 ms 1764 KB Output is correct
4 Correct 86 ms 1764 KB Output is correct
5 Correct 87 ms 1792 KB Output is correct
6 Incorrect 72 ms 1408 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 8 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -