UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#202155#3523. BLittle091002583ms48152kbC++112.2kb2024-02-13 12:46:012024-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