QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#773202 | #7606. Digital Nim | inksamurai | WA | 3ms | 31756kb | C++23 | 2.8kb | 2024-11-23 04:44:54 | 2024-11-23 04:44:54 |
Judging History
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'