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
#include<bits/stdc++.h>
using namespace std;
const string Szablon="APPAPA";
const int NaStart=5,Max=15;
string S[NaStart+1][Max+1];
mt19937 rng(2137);
int MaxPalinform(string A)
{
    const int n=(int)A.size();
    int w=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;true;j++)
        {
            if(i-j<0||i+j>=n||A[i-j]!=A[i+j])
            {
                w=max(w,j*2-1);
                break;
            }
        }
        for(int j=1;true;j++)
        {
            if(i-j<0||i+j-1>=n||A[i-j]!=A[i+j-1])
            {
                w=max(w,j*2-2);
                break;
            }
        }
    }
    return w;
}
int main()
{ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    for(int I=1;I<=10000;I++)
    {
        int n=rng()%(Max+1);
        string Kand="A";
        for(int i=1;i<n;i++)
        {
            if(rng()%100<50){Kand.push_back('A');}
            else{Kand.push_back('P');}
        }
        int w=MaxPalinform(Kand);
        if(w>NaStart){continue;}
        if(S[w][n].size()==0||S[w][n]<Kand)
        {
            S[w][n]=Kand;
        }
    }
    int N$;
    cin>>N$;
for(int I$=1;I$<=N$;I$++)
{
    int n,k;
    cin>>n>>k;
    if(k<=NaStart&&n<=Max&&S[k][n].size()>0)
    {
        cout<<S[k][n]<<'\n';
        continue;
    }
    if(k<4&&(n>Max||S[k][n].empty())){cout<<"NIE\n";continue;}
    string odp(k,'A');
    if(k==n){cout<<odp<<'\n';continue;}
    int t=1;
    while(odp.size()<n)
    {
        odp.push_back(Szablon[t]);
        t++;
        if(t==Szablon.size()){t=0;}
    }
    cout<<odp<<'\n';
}
    return 0;
}