QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#232607#7606. Digital NimCharlieVinnieTL 475ms7824kbC++234.4kb2023-10-30 17:30:182023-10-30 17:30:19

Judging History

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

  • [2023-10-30 17:30:19]
  • 评测
  • 测评结果:TL
  • 用时:475ms
  • 内存:7824kb
  • [2023-10-30 17:30:18]
  • 提交

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

详细

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...

result: