QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#225727#7606. Digital Nimucup-team484RE 0ms0kbC++171.3kb2023-10-25 02:21:592023-10-25 02:21:59

Judging History

你现在查看的是最新测评结果

  • [2023-10-25 02:21:59]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-10-25 02:21:59]
  • 提交

answer

#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define st first
#define nd second
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e6 + 5;
const int M = 17;
const int D = M * 9 / 10;
int dp[M][M * 9][D];
// dp[#trailing zeros][digitsum][distance to next loosing position]
// = distance to next loosing position after we add 10^(#trailing zeros + 1)

int sum(ll x) {
	return !x ? 0 : (x % 10) + sum(x / 10);
}

int check(ll n) {
	if (n % 10 != 0) return 1;
	if (sum(n) < 10) return 0;
	n /= 10;
	int ans = 0;
	vector<int> a;
	for (int i = 0; i < M; i++)
		a.push_back(n % 10), n /= 10;
	for (int i = M - 1, s = 0; i >= 0; i--)
		for (int j = 0; j < a[i]; j++)
			ans = dp[i][s++][ans];
	return ans > 0;
}

void solve() {
	ll n; cin >> n;
	cout << (check(n) ? "Algosia\n" : "Bajtek\n");
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	for (int i = 0; i < M * 9; i++)
		for (int j = 0; j < D; j++)
			dp[0][i][j] = (i + 1) / 10 >= j + 1 ? j + 1 : 0;
	for (int i = 1; i < M; i++)
		for (int j = 0; j < M * 9; j++)
			for (int k = 0; k < D; k++) {
				int x = k;
				for (int l = 0; l < 10; l++)
					x = dp[i - 1][j + l][x];
				dp[i][j][k] = (j + 1) / 10 >= x ? x : 0;
			}
	int t; cin >> t; while (t--) solve();
}

详细

Test #1:

score: 0
Runtime Error

input:

4
1
10
42
190

output:


result: