QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#225727 | #7606. Digital Nim | ucup-team484 | RE | 0ms | 0kb | C++17 | 1.3kb | 2023-10-25 02:21:59 | 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