ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#202155 | #3523. B | Little09 | 100 | 2583ms | 48152kb | C++11 | 2.2kb | 2024-02-13 12:46:01 | 2024-02-13 13:03:44 |
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define mem(x) memset(x,0,sizeof(x))
#define endl "\n"
#define printYes cout << "Yes\n"
#define printYES cout << "YES\n"
#define printNo cout << "No\n"
#define printNO cout << "NO\n"
#define lowbit(x) ((x)&(-(x)))
#define pb push_back
#define mkp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define rep(i,j,k) for (int i=(j);i<=(k);i++)
#define per(i,j,k) for (int i=(j);i>=(k);i--)
#define pcnt(x) __builtin_popcount(x)
mt19937 rnd(time(0));
template<class T>void chkmin(T&x,T y){x=min(x,y);}
template<class T>void chkmax(T&x,T y){x=max(x,y);}
const ll inf=1000000000000000000;
//const ll inf=1000000000;
//const ll mod=998244353;
//const ll mod=1000000007;
int dp[20][200][100][20];
int nxt[200][1000][20],w[10000];
ll n;
int S(ll x)
{
if (x==0) return 0;
return S(x/10)+x%10;
}
int dfs(int p,int s,int x,int k)
{
if (dp[p][s][x/10][k]!=-1) return dp[p][s][x/10][k];
if (p==3) return dp[p][s][x/10][k]=nxt[s][x][k];
int y=x;
rep(i,0,9)
{
if (i!=9) y=dfs(p-1,s+i,y,0);
else y=dfs(p-1,s+i,y,k+1);
}
return dp[p][s][x/10][k]=y;
}
int calc(int s,int x,int k)
{
if (x>=1000) return x-1000;
int det=0;
while (1)
{
det+=10;
if (x+det<1000)
{
if (det>w[x+det]+s) return calc(s,x+det,k);
}
else
{
if (det>w[x+det]+s-k*9) return calc(s,x+det,k);
}
}
}
int a[20];
void work()
{
cin >> n;
ll m=n;
rep(i,0,18)
{
a[i]=m%10;
m/=10;
}
int x=0,s=0;
per(i,18,3)
{
rep(j,0,a[i]-1)
{
x=dfs(i,s,x,0),s++;
}
}
m=x;
ll bas=1000;
rep(i,3,18) m+=bas*a[i],bas*=10;
while (m<n)
{
ll det=0;
while (1)
{
det+=10;
if (det>S(m+det)) break;
}
m+=det;
}
if (m==n) cout << "Bob\n";
else cout << "Alice\n";
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
memset(dp,-1,sizeof(dp));
rep(i,0,9999) w[i]=S(i);
rep(i,0,999) rep(j,0,199) rep(k,0,19) nxt[j][i][k]=calc(j,i,k);
int T;
cin >> T;
while (T--) work();
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 266ms
memory: 48152kb
input:
9576 706100 503160 285080 707728 64450 295760 101564 846990 561329 940050 178140 96440 414590 452424...
output:
Alice Bob Alice Alice Alice Bob Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Alice Alic...
result:
ok 9576 lines
Subtask #2:
score: 20
Accepted
Test #2:
score: 20
Accepted
time: 269ms
memory: 48148kb
input:
9576 706109500 164285080 707725800 445702956 910156444 699556130 99400507 814909649 414598454 254630...
output:
Alice Alice Bob Alice Alice Alice Alice Alice Alice Bob Alice Alice Alice Alice Alice Alice Bob Alic...
result:
ok 9576 lines
Subtask #3:
score: 30
Accepted
Test #3:
score: 30
Accepted
time: 254ms
memory: 48140kb
input:
1 500698580031188390
output:
Alice
result:
ok single line: 'Alice'
Test #4:
score: 0
Accepted
time: 249ms
memory: 48144kb
input:
1 842458467121479090
output:
Bob
result:
ok single line: 'Bob'
Test #5:
score: 0
Accepted
time: 250ms
memory: 48140kb
input:
1 195398762261421610
output:
Bob
result:
ok single line: 'Bob'
Test #6:
score: 0
Accepted
time: 251ms
memory: 48140kb
input:
1 800393465955164690
output:
Bob
result:
ok single line: 'Bob'
Test #7:
score: 0
Accepted
time: 250ms
memory: 48144kb
input:
1 668414232459612220
output:
Bob
result:
ok single line: 'Bob'
Test #8:
score: 0
Accepted
time: 247ms
memory: 48140kb
input:
1 613497414884141803
output:
Alice
result:
ok single line: 'Alice'
Test #9:
score: 0
Accepted
time: 247ms
memory: 48144kb
input:
1 654719730182142310
output:
Bob
result:
ok single line: 'Bob'
Subtask #4:
score: 40
Accepted
Test #10:
score: 40
Accepted
time: 300ms
memory: 48152kb
input:
9576 706109503164285080 707725806445702956 910156448469955612 99400501781490960 494145984524254630 4...
output:
Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alice Alic...
result:
ok 9576 lines
Extra Test:
score: 0
Extra Test Passed