CSES - Putka Open 2020 – 3/5

CSES - Putka Open 2020 – 3/5 - Results

Submission details
Task:	Numerot
Sender:	PallomerenPiikki
Submission time:	2020-10-18 12:51:29 +0300
Language:	C++17
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	WRONG ANSWER	0
#2	WRONG ANSWER	0
#3	WRONG ANSWER	0

Test results
test	verdict	time	group
#1	WRONG ANSWER	0.28 s	1, 2, 3	details
#2	WRONG ANSWER	0.32 s	2, 3	details
#3	WRONG ANSWER	0.57 s	3	details

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>

const int MAXDC = 20;
const int BASE = 10;

int pot[MAXDC+2];
pii dp[MAXDC][BASE][BASE][BASE];

struct Num {
  int val;
  Num(int x=0) : val(x) {}
  int operator[](int pos) const {
    return val / pot[pos] % 10;
  }
  int tzc() const {
    for (int i=2;; i++)
      if (val % pot[i] >= 10) return i-1;
  }
};

pii set_zeros(int k, int count) {
  int totsteps = 0;
  int totdec = 0;
  for (;;) {
    int rem = k % pot[count];
    if (rem < 10 && totsteps) break;
    if (k < 10) break;
    int zc = Num(k).tzc();
    int maxd = 0;
    for (int i=zc+1; i<MAXDC; i++)
      maxd = max(maxd, Num(k)[i]);
    int first = Num(k)[zc];
    int last = Num(k)[0];
    auto [steps, dec] = dp[zc][maxd][first][last];
    if (steps == 0) {
      steps = 1;
      dec = max(maxd, max(first, last));
    }
    totsteps += steps;
    totdec += dec;
    k -= dec;
  }
  return pii(totsteps, totdec);
}

int f(int k) {
  auto [steps, dec] = set_zeros(k, MAXDC);
  return steps + (k-dec>0);
}

int solve(int x) {
  int k = 0;
  int maxk = 1 + 9*x;
  if (x >= 1e6) {
    k = 8 * x;
  }
  for (int b=maxk; b >= 1; b /= 2) {
    while (k+b < maxk && f(k+b) < x) k += b;
  }
  while (f(k) < x) k++;
  return k;
}

void init() {
  pot[0] = 1;
  for (int i=1; i<MAXDC+2; i++)
    pot[i] = 10 * pot[i-1];
  for (int zc=1; zc<MAXDC; zc++) {
    for (int maxd=0; maxd<=9; maxd++) {
      for (int first=0; first<=9; first++) {
        for (int mod10=0; mod10<=9; mod10++) {
          int k = pot[zc+1]*maxd + pot[zc]*first + mod10;
          dp[zc][maxd][first][mod10] = set_zeros(k, zc);
        }
      }
    }
  }
}

signed main() {
  ios::sync_with_stdio(0);
  init();
  int t;
  cin >> t;
  t = min<int>(t, 100);
  while (t--) {
    int x;
    cin >> x;
    int k = solve(x);
    if (f(k) == x) {
      cout << k << '\n';
      cerr << fixed << 1.0*k/x << '\n';
    }
    else {
      cout << "-1\n";
    }
  }
}

Test details

Test 1

Group: 1, 2, 3

Verdict: WRONG ANSWER

input
`1000 1 2 3 4 ...` view save

correct output
`1 10 11 20 22 ...` view save

user output
`1 10 11 20 22 ...` view save

Error:

Test 2

Group: 2, 3

Verdict: WRONG ANSWER

input
`1000 224995 413660 249827 2125 ...` view save

correct output
`1731724 3216040 1940719 14585 532612 ...` view save

user output
`1731724 3216040 1940719 14585 532612 ...` view save

Error:

Test 3

Group: 3

Verdict: WRONG ANSWER

input
`1000 627887018110416188 785474884983906653 653772166720939773 784335285960673683 ...` view save

correct output
`5530371754830260284 6918696171534226533 5757755627065159149 6908439780325129803 3223801064342340738 ...` view save

user output
`5530371754830260284 6918696171534226533 5757755627065159149 6908439780325129803 3223801064342340738 ...` view save

Error:

Putka Open 2020 – 3/5

Numerot

Code

Test details

Test 1

Test 2

Test 3

Tasks

Submissions (PallomerenPiikki)