QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#773202#7606. Digital NiminksamuraiWA 3ms31756kbC++232.8kb2024-11-23 04:44:542024-11-23 04:44:54

Judging History

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

  • [2024-11-23 04:44:54]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:31756kb
  • [2024-11-23 04:44:54]
  • 提交

answer

#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define vec(...) vector<__VA_ARGS__>
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

#define yare cout<<"Algosia\n";

#define nare cout<<"Bajtek\n";

int dsum(int x){
	int sun=0;
	while(x) sun+=(x%10),x/=10;
	return sun;
}

const int M=300;

int dp[20][300][2*M];

int qs[20];

int dfs(int i,int ad,int bef){
	if(dp[i][ad][bef+M]!=-1) return dp[i][ad][bef+M];
	int ne_bef=bef;
	rep(x,10){
		if(i>1){
			ne_bef=dfs(i-1,ad+x,ne_bef);
		}else{
			if(ad+x>=ne_bef+1){
				ne_bef+=1;
			}else{
				ne_bef=0;
			}
		}
		// if(i==2) print(ne_bef);
	}
	return dp[i][ad][bef+M]=ne_bef;
}

void gap(){
	rep(len,20){
		rep(ad,300){
			rep(bef,2*M){
				dp[len][ad][bef]=-1;
			}
		}
	}

	// // dfs(2,0,10);
	// for(int len=1;len<=18;len++){
	// 	bef=dfs(len,0,-1);
	// }
	// // print(rec(rec,3,0,19));
}

int naive(int n){
	vi dp(n+3);
	rng(i,1,n+3){
		int s=dsum(i);
		// if(i==90) print("e",s,dp[i-1]);
		dp[i]=dp[i-1]+1;
		if(s<dp[i]) dp[i]=0;
	}
	// print(dp[260]);
	return dp[n];
}

void slv(){
	int n;
	cin>>n;

	if(n==1){
		yare;
		return;
	}

	n-=1;
	vi a;
	int x=n;
	while(x){
		a.pb(x%10);
		x/=10;
	}
	reverse(all(a));

	// for(auto x:a)cout<<x<<" ";
	// print();
	
	map<array<int,4>,int> smdp;
	auto rec=[&](auto self,int i,int ad,int bef,int t){
		if(smdp.find({i,ad,bef,t})!=smdp.end()) return smdp[{i,ad,bef,t}];
		if(t){
			return dfs(sz(a)-i,ad,bef);
		}
		int to=10;
		if(!t) to=a[i]+1;
		int ne_bef=bef;
		rep(x,to){
			if(i!=sz(a)-1){
				ne_bef=self(self,i+1,ad+x,ne_bef,t or (x<a[i]));
				// if(x+1<to){
				// 	ne_bef+=1;
				// }
				// if(i==0) print(x,ne_bef);
			}else{
				// if(i==2 and !t and x==1) print("e",ne_bef,ad+x);
				if(ad+x>=ne_bef+1){
					ne_bef+=1;
				}else{
					ne_bef=0;
				}
			}
			// if(i==1 and x==6 and !t) print("aa",ne_bef);
		}
		// if(i==0) print(ne_bef);
		// if(i==2 and !t and ad==10) print("go",bef,ne_bef,to);
		// if(i==1 and bef==10) print(t,to,ne_bef);
		// return smdp[{i,ad,bef,t}]=ne_bef;
		return ne_bef;
	};

	int bef=rec(rec,0,0,0,0);

	// print(n);
	// print(bef);
	// print(naive(n));
	// assert(bef==naive(n));
	if(dsum(n+1)>=bef){
		yare;
	}else{
		nare;
	}
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	gap();
	// naive(1000);
	int t;
	cin>>t;
	// t=1;
	rep(cs,t){
		slv();
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 31752kb

input:

4
1
10
42
190

output:

Algosia
Bajtek
Algosia
Algosia

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 31708kb

input:

1
1

output:

Algosia

result:

ok single line: 'Algosia'

Test #3:

score: -100
Wrong Answer
time: 3ms
memory: 31756kb

input:

10000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
10...

output:

Algosia
Algosia
Algosia
Algosia
Algosia
Algosia
Algosia
Algosia
Algosia
Bajtek
Algosia
Algosia
Algosia
Algosia
Algosia
Algosia
Algosia
Algosia
Algosia
Bajtek
Algosia
Algosia
Algosia
Algosia
Algosia
Algosia
Algosia
Algosia
Algosia
Bajtek
Algosia
Algosia
Algosia
Algosia
Algosia
Algosia
Algosia
Algosia...

result:

wrong answer 90th lines differ - expected: 'Bajtek', found: 'Algosia'