QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#232607 | #7606. Digital Nim | CharlieVinnie | TL | 475ms | 7824kb | C++23 | 4.4kb | 2023-10-30 17:30:18 | 2023-10-30 17:30:19 |
Judging History
answer
#include "bits/stdc++.h"
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](auto...){}(__VA_ARGS__)
#define debuga(...) [](auto...){}(__VA_ARGS__)
#endif
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
#define assume(expr) ((!!(expr))||(exit((fprintf(stderr,"Assumption Failed: %s on Line %d\n",#expr,__LINE__),-1)),false))
#define range basic_string_view
using namespace std; typedef long long ll;
namespace FastIO{
const int BUF_SIZ=1<<16;
char in_buf[BUF_SIZ],*got_pos=in_buf,*read_pos=in_buf,out_buf[BUF_SIZ],*write_pos=out_buf;
inline char get_next_char(){if(read_pos==got_pos){got_pos=read_pos=in_buf;got_pos+=fread(got_pos,sizeof(char),BUF_SIZ,stdin);}return*(read_pos++);}
inline void flush_output(){fwrite(out_buf,sizeof(char),write_pos-out_buf,stdout);write_pos=out_buf;}
inline void put_char(char ch){*(write_pos++)=ch;if(write_pos==out_buf+BUF_SIZ)flush_output();}
#ifndef FASTIO_READ_NEGATIVE
template<typename T> inline void read(T& res){char ch;while(!isdigit(ch=get_next_char()));res=ch^'0';while(isdigit(ch=get_next_char()))res=(res<<3)+(res<<1)+(ch^'0');}
#else
template<typename T> inline void read(T& res){char ch;bool flg=0;while(!isdigit(ch=get_next_char()))flg|=ch=='-';res=ch^'0';while(isdigit(ch=get_next_char()))res=(res<<3)+(res<<1)+(ch^'0');if(flg)res=-res;}
#endif
template<typename T> inline void write(T x){if(!x){put_char('0');return;}static int lis[25],*lp=lis;while(x){*(++lp)=x%10;x/=10;}while(lp!=lis)put_char((*(lp--))+'0');}
template<typename T> inline void writeln(const T& x){write(x);put_char('\n');}
template<typename T> inline void writesp(const T& x){write(x);put_char(' ');}
class _IO_Flusher{public:~_IO_Flusher(){flush_output();}}__Flusher;
class IStream{public:
template<typename T> inline IStream& operator>>(T& x){read(x);return *this;}
inline IStream& operator>>(char* str){char ch;while(isspace(ch=get_next_char()));(*(str++))=ch;while(!isspace(ch=get_next_char())){if(ch==EOF)break;(*(str++))=ch;}*str=0;return *this;}
}Cin;
class OStream{public:
template<typename T> inline enable_if_t<is_integral<T>::value,OStream&> operator<< (const T& x){write(x);return *this;}
inline OStream& operator<< (const char& ch){put_char(ch);return *this;}
inline OStream& operator<< (const char* str){for(const char* p=str;*p;put_char(*(p++)));return *this;}
}Cout;
}
using namespace FastIO;
#define cin Cin
#define cout Cout
constexpr ll pw[19]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000};
ll f[19][163][163]; // f[i][j][k]: i and higher sum is j, lower is k, get the one before i gets a carry
int D(ll x){int t=0;while(x)t+=x%10,x/=10;;return t;}
ll F(int i,int j,int k){
// assert(j<=162&&k>=0&&k<pw[i]&&k<=162);
if(i==0) return k;
if(f[i][j][k]!=-1) return f[i][j][k];
ll res=k;
while(true){
int O=res/pw[i-1];
// if(res%pw[i-1]>200) debug(i,j,k,res,O);
// if(i==5&&j==175&&k==0) debug(i,j,k,res,O);
// assert(res%pw[i-1]<=162);
res=O*pw[i-1]+F(i-1,j+O,res%pw[i-1]);
ll t=(O+1)*pw[i-1]; while(t-D(t)-j<=res) t++;
if(t>=pw[i]) break;
res=t; //assert(res/pw[i-1]!=O);
}
return f[i][j][k]=res;
}
signed main(){
// Fin("hh.in"); Fout("hh.out");
atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
// ll t=1; For(i,0,18) assert(pw[i]==t),t*=10;
// pw[0]=1; For(i,1,18) pw[i]=10*pw[i-1];
memset(f,-1,sizeof(f));
// For(i,0,18) For(j,0,(18-i)*9) For(k,0,min(pw[i]-1,162ll)) F(i,j,k);
int T; cin>>T; while(T--){
ll n; cin>>n; ll x=0;
Rev(i,18,0){
while(x/pw[i]<n/pw[i]){
x=x/pw[i]*pw[i]+F(i,D(x/pw[i]),x%pw[i]);
ll t=x; while(x-D(x)<=t) x++;
}
if(x>n) break;
}
assert(x>=n);
if(x==n) cout<<"Bajtek\n"; else cout<<"Algosia\n";
}
return 0;
}
// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING
// CONTINUE, NON-STOPPING, FOR CHARLIEVINNIE
// Started Coding On: October 30 Mon, 16 : 34 : 39
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7700kb
input:
4 1 10 42 190
output:
Algosia Bajtek Algosia Algosia
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 7640kb
input:
1 1
output:
Algosia
result:
ok single line: 'Algosia'
Test #3:
score: 0
Accepted
time: 11ms
memory: 7652kb
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:
ok 10000 lines
Test #4:
score: 0
Accepted
time: 44ms
memory: 7824kb
input:
10000 86 385 545 561 563 770 831 859 1123 1218 1423 1437 1602 1650 1884 1960 2096 2160 2330 2552 2662 2762 3359 3382 3425 3556 3606 3669 3790 3962 3980 4009 4060 4128 4418 4424 4458 4483 4510 4540 4594 4659 4704 4766 4822 4946 5073 5139 5195 5225 5267 5390 5490 5557 5885 6171 6235 6307 6371 6442 645...
output:
Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Bajtek Algosia Bajtek Bajtek Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia...
result:
ok 10000 lines
Test #5:
score: 0
Accepted
time: 170ms
memory: 7764kb
input:
10000 63282 121076 318636 395380 405847 473533 850891 859227 876990 877183 1202581 1360154 1416399 1450189 1603717 1618175 1636686 1648221 1649807 1652127 1714183 1730743 1766595 1813769 1883327 1909563 2033458 2034831 2054278 2365137 2398438 2431649 2544385 2591344 2781989 2799879 2946371 3081362 3...
output:
Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Bajtek Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algos...
result:
ok 10000 lines
Test #6:
score: 0
Accepted
time: 475ms
memory: 7740kb
input:
10000 55974796 164367751 726067320 832933581 839242663 874743324 924711240 1273805641 1293241492 1502671500 1580201972 1866598988 1875214768 1887602218 2187236520 2190435343 2200271756 2222335108 2298443856 2312384848 2553086341 2728080634 2847195043 2941043887 3015534723 3032934075 3042416569 30536...
output:
Algosia Algosia Bajtek Algosia Algosia Algosia Algosia Algosia Algosia Bajtek Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosi...
result:
ok 10000 lines
Test #7:
score: -100
Time Limit Exceeded
input:
10000 226734696862 331363710798 571908782674 587317947192 712617926622 750076643202 845071930320 900747937168 1029215192240 1236146558335 1390866543043 1421889212655 1678882652961 1860532340178 1919377401251 2008873081380 2015692609997 2195759385338 2467741475021 2486222596605 2634516025808 26507182...
output:
Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algosia Algo...