CSES - Putka Open 2020 – 3/5 - Results
Submission details
Task:Numerot
Sender:Metabolix
Submission time:2020-10-18 11:12:59
Language:C++17
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED12
#2ACCEPTED13
#3ACCEPTED75
Test results
testverdicttimegroup
#1ACCEPTED0.09 s1, 2, 3details
#2ACCEPTED0.09 s2, 3details
#3ACCEPTED0.17 s3details

Code

#include <bits/stdc++.h>

std::pair<long, long> cache[10 * 10 * 10 * 20];
std::pair<long, long> helppo(int alkumax, int ylin, int nollia, int alin) {
	int key = alkumax + 10 * (ylin + 10 * (alin + 10 * nollia));
	auto val = cache[key];
	if (val.first != 0) {
		return val;
	}

	long askelia = 0, muutos = 0;
	while (ylin > 0) {
		// Nyt luku on muotoa {ylin}00000{alin}
		// Aiheutetaan kymmenylitys, jossa ylin laskee yhdellä.
		int maxnum = std::max({alkumax, ylin, alin});
		if (maxnum <= alin) {
			int maxnum2 = std::max({alkumax, ylin, alin - maxnum});
			askelia += 2;
			muutos -= maxnum + maxnum2;
			alin = (100 + alin - maxnum - maxnum2) % 10;
		} else {
			askelia += 1;
			muutos -= maxnum;
			alin = (100 + alin - maxnum) % 10;
		}
		ylin -= 1;

		if (nollia > 0) {
			// Nyt luku on muotoa {ylin}99999{alin}
			// Tuhotaan yhdeksiköt pienimmästä alkaen.
			for (int i = 0; i < nollia - 1; ++i) {
				auto am = helppo(9, 9, i, alin);
				askelia += am.first;
				muutos += am.second;
				alin = (9099999999999999990l + alin + am.second) % 10;
			}

			// Nyt luku on muotoa {ylin}90000{alin}
			int i = nollia - 1;
			int maxnum = std::max(alkumax, ylin);
			auto am = helppo(maxnum, 9, i, alin);
			askelia += am.first;
			muutos += am.second;
			alin = (9099999999999999990l + alin + am.second) % 10;
		}
	}

	return cache[key] = {askelia, muutos};
}

std::pair<long, long> f(long luku, int maxnum = 0) {
	long askelia = 0, muutos = 0;
	long kymppi = 10;
	int nollia = 0;
	while (luku > 9) {
		int ylin = luku / kymppi % 10;
		int alin = luku % 10;
		auto s = std::to_string(luku / kymppi / 10);
		int alkumax = *std::max_element(s.begin(), s.end()) - '0';
		auto am = helppo(std::max(maxnum, alkumax), ylin, nollia, alin);
		askelia += am.first;
		muutos += am.second;
		luku += am.second;
		kymppi *= 10;
		nollia += 1;
	}
	return {askelia, muutos};
}

long g(long x) {
	return f(x).first + 1;
}

int main() {
	int t;
	std::cin >> t;
	for (int i = 0; i < t; ++i) {
		long x;
		std::cin >> x;
		if (x == 1) {
			std::cout << "1\n";
			continue;
		}
		long k0 = 9, k1 = 9000000000000000001l;
		while (k1 - k0 > 1) {
			long k = ((unsigned long)k1 + (unsigned long)k0) / 2;
			if (g(k) < x) {
				k0 = k;
			} else {
				k1 = k;
			}
		}
		std::cout << k1 << "\n";
	}
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
1000
1
2
3
4
...

correct output
1
10
11
20
22
...

user output
1
10
11
20
22
...

Test 2

Group: 2, 3

Verdict: ACCEPTED

input
1000
224995
413660
249827
2125
...

correct output
1731724
3216040
1940719
14585
532612
...

user output
1731724
3216040
1940719
14585
532612
...

Test 3

Group: 3

Verdict: ACCEPTED

input
1000
627887018110416188
785474884983906653
653772166720939773
784335285960673683
...

correct output
5530371754830260284
6918696171534226533
5757755627065159149
6908439780325129803
3223801064342340738
...

user output
5530371754830260284
6918696171534226533
5757755627065159149
6908439780325129803
3223801064342340738
...