結果

問題 No.153 石の山
ユーザー penguin46penguin46
提出日時 2020-11-05 16:20:47
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 24 ms / 5,000 ms
コード長 33,622 bytes
コンパイル時間 2,104 ms
コンパイル使用メモリ 145,104 KB
実行使用メモリ 73,612 KB
最終ジャッジ日時 2024-07-22 11:13:23
合計ジャッジ時間 3,778 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'll LSI(vll)':
main.cpp:409:1: warning: control reaches end of non-void function [-Wreturn-type]
  409 | }
      | ^

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <string.h>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <math.h>
#include <algorithm>
#include <numeric>
#include <random>
//#include <atcoder/convolution>
//#include <atcoder/math>
//#include <atcoder/maxflow>
//#include <atcoder/mincostflow>
//#include <atcoder/modint>
//#include <atcoder/scc>
//#include <atcoder/string>
//#include <atcoder/twosat>
//using namespace atcoder;
using namespace std;
// && ================================================
typedef int Int;
typedef int INt;
typedef unsigned int uint;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<bool> vbool;
typedef vector<string> vstring;
typedef vector<pair<int, int>> vpint;
typedef vector<pair<ll, ll>> vpll;
typedef vector<pair<double, double>> vpdouble;
typedef vector<vector<int>> vvint;
typedef vector<vector<ll>> vvll;
typedef vector<vpint> vvpint;
typedef vector<vpll> vvpll;
typedef vector<vector<double>> vvdouble;
typedef vector<vector<string>> vvstring;
typedef vector<vector<bool>> vvbool;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<vector<vector<pll>>> vvvpll;
typedef vector<vector<vector<bool>>> vvvbool;
typedef vector<vector<vector<double>>> vvvdouble;
typedef vector<vector<vector<vector<double>>>> vvvvdouble;
const ll LLINF = 1e18 + 1;
const int DX[9] = { 0, 0, 1, -1, 1, 1, -1, -1, 0 }; // 4;
const int DY[9] = { 1, -1, 0, 0, 1, -1, 1, -1, 0 }; // 8: 9:(0,0)
const double PI = 3.14159265358979323846264338327950288;
const double EPS = 1e-7;
//VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
const ll MOD = 1000000007; //10^9 + 7
//VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } else return false; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } else return false; }
//---------------------------------------------------------------
//
//---------------------------------------------------------------
bool is_overflow(ll a, ll b) {
ll M = numeric_limits<ll>::max();
return (a >= M / b);
}
//---------------------------------------------------------------
//
//---------------------------------------------------------------
ll random_int(ll start, ll last) { return start + rand() % (last - start + 1); }
//---------------------------------------------------------------
// 2()
//---------------------------------------------------------------
template<class T>
void print2D(vector<vector<T>> A)
{
for (vector<T> aa : A) {
for (T a : aa)
cout << a << " ";
cout << endl;
}
cout << endl;
}
//---------------------------------------------------------------
// x∈[a, b)
//---------------------------------------------------------------
bool is_in(ll x, ll a, ll b) { return (a <= x && x < b); }
//---------------------------------------------------------------
//
//---------------------------------------------------------------
ll to_int(string S) { return stoll(S); }
ll to_int(char c) { return int(c) - int('0'); }
ll to_int(const char *c) { return atoi(c); }
//---------------------------------------------------------------
// 2 ()
//---------------------------------------------------------------
template<class T>
vector<vector<T>> get_accum(vector<vector<T>> A)
{
T H = A.size();
T W = A[0].size();
vector<vector<T>> accum(H + 1, vector<T>(W + 1, 0));
for (int h = 0; h < H; h++)
for (int w = 0; w < W; w++)
accum[h + 1][w + 1] = A[h][w];
for (int h = 0; h <= H; h++)
for (int w = 0; w < W; w++)
accum[h][w + 1] += accum[h][w];
for (int h = 0; h < H; h++)
for (int w = 0; w <= W; w++)
accum[h + 1][w] += accum[h][w];
return accum;
}
//---------------------------------------------------------------
// O(√N)
//---------------------------------------------------------------
vll divisor(ll n) {
vll ret;
for (ll i = 1; i * i <= n; i++) { if (n % i == 0) { ret.push_back(i); if (i * i != n) ret.push_back(n / i); } }
sort(begin(ret), end(ret)); return (ret);
}
//---------------------------------------------------------------
// N()
//---------------------------------------------------------------
vbool searchSosuu(ll N) {
vbool sosuu;
for (ll i = 0; i < N; i++) { sosuu.emplace_back(true); }
sosuu[0] = false; sosuu[1] = false;
for (ll i = 2; i < N; i++) { if (sosuu[i]) { for (ll j = 2; i * j < N; j++) { sosuu[i * j] = false; } } }
return sosuu;
}
//---------------------------------------------------------------
//  O(√N)
//---------------------------------------------------------------
vpll to_prime(ll n) {
vpll prime_factor;
for (ll i = 2; i * i <= n; i++) {
ll count = 0; while (n % i == 0) { count++; n /= i; }
if (count) { pair<ll, ll> temp = { i, count }; prime_factor.emplace_back(temp); }
}
if (n != 1) { pair<ll, ll> temp = { n, 1 }; prime_factor.emplace_back(temp); }
return prime_factor;
}
//---------------------------------------------------------------
// (O(N), O(logN))
//---------------------------------------------------------------
class FastPrime
{
public:
vll div; // i 1
vbool is_sosuu; // i
FastPrime(ll N) : div(N + 10, -1), is_sosuu(N + 10, true)
{
for (ll i = 2; i < N; i++)
if (div[i] == -1)
for (ll j = 2; i * j <= N; j++)
{
div[i * j] = i;
is_sosuu[i * j] = false;
}
}
vpll to_prime(ll N)
{
if (N == 1) return vpll({});
vll divs;
while (div[N] != -1)
{
divs.emplace_back(div[N]);
N /= div[N];
}
if (N > 1) divs.emplace_back(N);
sort(divs.begin(), divs.end());
vpll primes;
ll count = 1;
for (int i = 1; i < divs.size(); i++)
{
if (divs[i] > divs[i - 1])
{
primes.emplace_back(pll(divs[i - 1], count));
count = 0;
}
count++;
}
primes.emplace_back(pll(divs[divs.size() - 1], count));
return primes;
}
};
//---------------------------------------------------------------
//
//---------------------------------------------------------------
ll gcd(ll a, ll b) {
if (a < b) { ll tmp = a; a = b; b = tmp; }
ll r = a % b;
while (r != 0) { a = b; b = r; r = a % b; }
return b;
}
//---------------------------------------------------------------
//
//---------------------------------------------------------------
pll reduce(ll a, ll b) {
ll g = gcd(a, b);
return pll(a / g, b / g);
}
//---------------------------------------------------------------
//
//---------------------------------------------------------------
ll lcm(ll a, ll b) { ll temp = gcd(a, b); return temp * (a / temp) * (b / temp); }
//---------------------------------------------------------------
//
//---------------------------------------------------------------
ll factorial(ll n, ll mod = MOD) { if (n <= 1) { return 1; }return (n * (factorial(n - 1))) % mod; }
//---------------------------------------------------------------
// (:O(N) :O(1))
//---------------------------------------------------------------
//
ll comb_const = 3000005;
vll fac(comb_const), finv(comb_const), inv(comb_const);
bool COMineted = false;
void COMinit(ll mod = MOD) {
fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1;
for (ll i = 2; i < comb_const; i++) {
fac[i] = fac[i - 1] * i % mod;
inv[i] = mod - inv[mod % i] * (mod / i) % mod;
finv[i] = finv[i - 1] * inv[i] % mod;
}
COMineted = true;
}
//
ll COM(ll n, ll k, ll mod = MOD) {
if (COMineted == false) COMinit(mod);
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return (fac[n] * (finv[k] * finv[n - k] % mod)) % mod;
}
//---------------------------------------------------------------
// base^sisuu
//---------------------------------------------------------------
ll RepeatSquaring(ll base, ll sisuu, ll mod = MOD) {
if (sisuu < 0) { cout << "RepeatSquaring: !" << endl; return 0; }
if (sisuu == 0) return 1;
if (sisuu % 2 == 0) { ll t = RepeatSquaring(base, sisuu / 2, mod) % mod; return (t * t) % mod; }
return (base * RepeatSquaring(base, sisuu - 1, mod)) % mod;
}
//---------------------------------------------------------------
// (O(logN))
//---------------------------------------------------------------
ll fast_com(ll a, ll b, ll mod = MOD) {
ll bunshi = 1; ll bunbo = 1;
for (ll i = 1; i <= b; i++) { bunbo *= i; bunbo %= mod; bunshi *= (a - i + 1); bunshi %= mod; }
ll ret = bunshi * RepeatSquaring(bunbo, mod - 2, mod); ret %= mod;
while (ret < 0) { ret += mod; }
return ret;
}
//---------------------------------------------------------------
// ll->vbool
//---------------------------------------------------------------
vbool to_bitlist(ll bit, ll fixed_size = 1) {
if (bit == 0) return vbool(fixed_size, 0);
vbool list;
while (bit > 0) { list.emplace_back(bit & 1); bit /= 2; }
while (list.size() < fixed_size) { list.emplace_back(0); }
return list;
}
//---------------------------------------------------------------
//
//---------------------------------------------------------------
ll bit_count(ll bit) {
ll ret = 0;
while (bit) {
ret += bit % 2;
bit /= 2;
}
return ret;
}
//---------------------------------------------------------------
// XOR 0^1^...^N (O(1))
//---------------------------------------------------------------
ll xor_fac(ll N)
{
if (N == 0) return 0;
ll n_pair = (N - 1) / 2;
ll n_one = n_pair + 1;
if (n_pair * 2 + 1 == N) {
return n_one % 2;
}
else {
return (n_one % 2) ^ N;
}
}
//---------------------------------------------------------------
// (O(NlogN)) 0
//---------------------------------------------------------------
class PosPress
{
public:
vll pressed;
map<ll, ll> func; //
map<ll, ll> rev; //
PosPress(vll P) {
pressed = P; sort(P.begin(), P.end()); func[P[0]] = 0; rev[0] = P[0]; ll next = 1;
for (int i = 1; i < P.size(); i++) { if (P[i] != P[i - 1]) { func[P[i]] = next; rev[next] = P[i]; next++; } }
for (int i = 0; i < P.size(); i++) { pressed[i] = func[pressed[i]]; }
}
};
//---------------------------------------------------------------
// (O(N^3))
//---------------------------------------------------------------
vvll mat_cross(vvll A, vvll B) {
ll N = A.size(); ll K = B.size(); ll M = B[0].size();
vvll C(N, vll(M));
// (+, * |, & OK)
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
for (int k = 0; k < K; k++)
C[i][j] += A[i][k] * B[k][j];
return C;
}
//---------------------------------------------------------------
// 2((x1, y1)->(x2, y2) (X1, Y1)->(X2, Y2))
//---------------------------------------------------------------
bool is_cross(ll x1, ll y1, ll x2, ll y2, ll X1, ll Y1, ll X2, ll Y2) {
ll dx_ai = X1 - x1; ll dy_ai = Y1 - y1;
ll dx_bi = X1 - x2; ll dy_bi = Y1 - y2;
ll dx_ai2 = X2 - x1; ll dy_ai2 = Y2 - y1;
ll dx_bi2 = X2 - x2; ll dy_bi2 = Y2 - y2;
ll si = dx_ai * dy_bi - dy_ai * dx_bi;
ll si2 = dx_ai2 * dy_bi2 - dy_ai2 * dx_bi2;
ll si3 = dx_ai * dy_ai2 - dy_ai * dx_ai2;
ll si4 = dx_bi * dy_bi2 - dy_bi * dx_bi2;
return (si * si2 < 0 && si3 * si4 < 0);
}
//---------------------------------------------------------------
// (O(NlogN))
//---------------------------------------------------------------
ll LSI(vll vec)
{
ll size = vec.size();
vll lsi(size + 1, LLINF); // j
lsi[0] = 0; lsi[1] = vec[0];
for (ll i = 1; i < size; i++)
{
// vec[i]
auto Iter = lower_bound(lsi.begin(), lsi.end(), vec[i]);
ll idx = Iter - lsi.begin();
if (idx > 0 && lsi[idx - 1] < vec[i]) { lsi[idx] = vec[i]; }
}
for (ll i = size; i >= 0; i--) { if (lsi[i] < LLINF) { return i; } }
}
//---------------------------------------------------------------
// LCS() O(|S||T|)
//---------------------------------------------------------------
string LCS(string S, string T)
{
vvll dp(S.length() + 1);
for (int i = 0; i < dp.size(); i++) { vll t(T.length() + 1, 0); dp[i] = t; }
for (int i = 0; i < S.length(); i++) {
for (int j = 0; j < T.length(); j++) {
dp[i + 1][j + 1] = max({ dp[i][j] + ll(S[i] == T[j]), dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1] });
}
}
ll len = dp[S.length()][T.length()];
string ans = "";
ll i = dp.size() - 1;
ll j = dp[0].size() - 1;
while (len > 0) {
if (dp[i - 1][j] == len) { i--; }
else if (dp[i][j - 1] == len) { j--; }
else { ans += S[i - 1]; i--; j--; len--; }
}
reverse(ans.begin(), ans.end());
return ans;
}
vll LCS(vll S, vll T)
{
vvll dp(S.size() + 1);
for (int i = 0; i < dp.size(); i++) { vll t(T.size() + 1, 0); dp[i] = t; }
for (int i = 0; i < S.size(); i++) {
for (int j = 0; j < T.size(); j++) {
dp[i + 1][j + 1] = max({ dp[i][j] + ll(S[i] == T[j]), dp[i + 1][j], dp[i][j + 1], dp[i + 1][j + 1] });
}
}
ll len = dp[S.size()][T.size()];
vll ans;
ll i = dp.size() - 1;
ll j = dp[0].size() - 1;
while (len > 0) {
if (dp[i - 1][j] == len) { i--; }
else if (dp[i][j - 1] == len) { j--; }
else { ans.emplace_back(S[i - 1]); i--; j--; len--; }
}
reverse(ans.begin(), ans.end());
return ans;
}
//---------------------------------------------------------------
//
//---------------------------------------------------------------
vll tree_depth(vvll edge, ll root)
{
ll n_node = edge.size();
vll dist(n_node, LLINF);
dist[root] = 0;
stack<pll> S;
S.push({ root, 0 });
while (!S.empty())
{
ll node = S.top().first;
ll d = S.top().second;
dist[node] = d;
S.pop();
for (int i = 0; i < edge[node].size(); i++) {
if (dist[edge[node][i]] == LLINF) {
S.push({ edge[node][i], d + 1 });
}
}
}
return dist;
}
//---------------------------------------------------------------
// (O(N^3)) d: (N*N)
//---------------------------------------------------------------
vvll warshall_floyd(vvll d) {
ll n = d.size();
for (int k = 0; k < n; k++) { //
for (int i = 0; i < n; i++) { //
for (int j = 0; j < n; j++) { //
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
return d;
}
//---------------------------------------------------------------
// Union Find
//---------------------------------------------------------------
class UnionFind {
private:
vll siz; // (1 )
public:
ll n_group; //
vll par; //
// Constructor
UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
for (ll i = 0; i < sz_; ++i) par[i] = i; //
n_group = sz_;
}
void init(ll sz_) {
par.resize(sz_);
siz.assign(sz_, 1LL); // resize
for (ll i = 0; i < sz_; ++i) par[i] = i; //
}
// Member Function
// Find
ll root(ll x) { //
while (par[x] != x) {
x = par[x] = par[par[x]]; // x x
}
return x;
}
// Union(Unite, Merge)
bool merge(ll x, ll y) {
x = root(x);
y = root(y);
if (x == y) return false;
// merge technique
if (siz[x] < siz[y]) swap(x, y);
siz[x] += siz[y];
par[y] = x;
n_group--;
return true;
}
//
bool issame(ll x, ll y) {
return root(x) == root(y);
}
// x
ll size(ll x) {
return siz[root(x)];
}
};
//---------------------------------------------------------------
// (O(ElogV)) edge: from->pair{to, cost}
//---------------------------------------------------------------
class Dijkstra
{
private:
vll past; // (i)
public:
vll dist; // i
// edge[i] -> {to, cost}
Dijkstra(vvpll edge, ll start) : dist(edge.size(), LLINF), past(edge.size(), -1)
{
using Pi = pll;
priority_queue< Pi, vector< Pi >, greater< Pi > > que;
dist[start] = 0;
que.emplace(dist[start], start);
while (!que.empty()) {
ll cost;
int idx;
tie(cost, idx) = que.top();
que.pop();
if (dist[idx] < cost) continue;
for (int i = 0; i < edge[idx].size(); i++)
{
ll next_cost = cost + edge[idx][i].second;
if (dist[edge[idx][i].first] <= next_cost) continue;
dist[edge[idx][i].first] = next_cost;
past[edge[idx][i].first] = idx;
que.emplace(dist[edge[idx][i].first], edge[idx][i].first);
}
}
}
// goal
vll shortest(ll goal)
{
vll ret;
while (goal != -1)
{
ret.emplace_back(goal);
goal = past[goal];
}
reverse(ret.begin(), ret.end());
return ret;
}
};
//---------------------------------------------------------------
// LCA: (O())
//---------------------------------------------------------------
class Lca
{
private:
vvll doubling;
ll n_bit = 30;
public:
vll depth; // 0i
// edge[i] -> {to, cost}
Lca(vvll edge, ll root = 0) : doubling(50, vll(edge.size(), -1))
{
//
depth = tree_depth(edge, root);
// 辿
// j2^i辿
doubling[0][0] = -1;
for (int i = 1; i < edge.size(); i++)
for (int j : edge[i])
if (depth[i] > depth[j]) { doubling[0][i] = j; break; }
for (int i = 1; i < n_bit; i++)
for (int j = 0; j < edge.size(); j++) {
if (doubling[i - 1][j] != -1) doubling[i][j] = doubling[i - 1][doubling[i - 1][j]];
else doubling[i][j] = -1;
}
}
// ab
ll get_lca(ll a, ll b)
{
// depth[a] >= depth[b]
if (depth[a] < depth[b]) swap(a, b);
ll oa = a;
ll ob = b;
ll d = depth[a] - depth[b];
// ad
vbool bit = to_bitlist(d, n_bit);
for (int i = 0; i < n_bit; i++)if (bit[i]) a = doubling[i][a];
// depth[a] == depth[b]
for (int i = n_bit - 1; i >= 0; i--) {
if (doubling[i][a] == doubling[i][b]) continue;
a = doubling[i][a]; b = doubling[i][b];
}
return a == b ? a : doubling[0][a];
}
//
ll path_len(ll a, ll b)
{
return depth[a] + depth[b] - 2 * depth[get_lca(a, b)];
}
//
vll nodes_on_path(ll a, ll b)
{
if (a == b) return vll({ a });
vll ret;
ll lca = get_lca(a, b);
while (a != lca) {
ret.emplace_back(a);
a = doubling[0][a];
}
while (b != lca) {
ret.emplace_back(b);
b = doubling[0][b];
}
ret.emplace_back(lca);
return ret;
}
};
//---------------------------------------------------------------
// Z-algorithm(SS[i:]) O(|S|)
//---------------------------------------------------------------
vll Zalgorithm(string S)
{
ll n = S.size();
vll Z(n, 0);
ll start = -1;
ll last = -1;
for (ll i = 1; i < n; i++) {
if (start >= 0) { Z[i] = min(Z[i - start], last - i); chmax(Z[i], 0LL); }
while (i + Z[i] < S.size() && S[Z[i]] == S[i + Z[i]])
Z[i] ++;
if (last < i + Z[i]) { last = i + Z[i]; start = i; }
}
Z[0] = n;
return Z;
}
vll Zalgorithm(vll S)
{
ll n = S.size();
vll Z(n, 0);
ll start = -1;
ll last = -1;
for (ll i = 1; i < n; i++) {
if (start >= 0) { Z[i] = min(Z[i - start], last - i); chmax(Z[i], 0LL); }
while (i + Z[i] < S.size() && S[Z[i]] == S[i + Z[i]])
Z[i] ++;
if (last < i + Z[i]) { last = i + Z[i]; start = i; }
}
Z[0] = n;
return Z;
}
//---------------------------------------------------------------
// (O(E)) edge ->
//---------------------------------------------------------------
class Bipartite
{
private:
ll N;
public:
vll color; // 2
bool is_bipartite; // 2
Bipartite(vvll edge) : color(edge.size(), -1)
{
N = edge.size();
color[0] = 0;
queue<ll> Q;
Q.push(0);
while (!Q.empty())
{
ll now = Q.front();
Q.pop();
for (int i : edge[now])
{
if (color[i] == -1)
{
color[i] = (color[now] == 0 ? 1 : 0);
Q.push(i);
}
else if (color[i] == color[now])
{
is_bipartite = false;
return;
}
}
}
is_bipartite = true;
}
};
//---------------------------------------------------------------
// (, ) ←
//---------------------------------------------------------------
class Doubling
{
private:
ll M = 100;
vvll doubling;
vvll cost;
bool have_cost = false;
public:
// to[i]: i 1
// fee[i]: i to[i]()
Doubling(vll to, vll fee = {}) : doubling(M, vll(to.size(), -1)), cost(M, vll(to.size(), 0))
{
ll N = to.size();
have_cost = fee.size() > 0;
for (int i = 0; i < N; i++)
{
doubling[0][i] = to[i];
if (have_cost)
cost[0][i] = fee[i];
}
for (int i = 1; i < M; i++)
{
for (int j = 0; j < N; j++)
{
doubling[i][j] = doubling[i - 1][doubling[i - 1][j]];
if (have_cost)
cost[i][j] = cost[i - 1][j] + cost[i - 1][doubling[i - 1][j]];
}
}
}
// from K
ll destination(ll from, ll K)
{
vbool bits = to_bitlist(K);
ll now = from;
ll sum = 0;
for (int i = 0; i < bits.size(); i++)
{
if (bits[i])
{
now = doubling[i][now];
}
}
return now;
}
// from K
ll get_cost(ll from, ll K)
{
vbool bits = to_bitlist(K);
ll now = from;
ll sum = 0;
for (int i = 0; i < bits.size(); i++)
{
if (bits[i])
{
sum += cost[i][now];
now = doubling[i][now];
}
}
return sum;
}
};
//---------------------------------------------------------------
// (O(EV)) edge, from, to -> (cost, have_neg_roop)
//---------------------------------------------------------------
pair<ll, bool> BelmanFord(vvpll edge, ll from, ll to)
{
ll N = edge.size(); //
vll d(N, LLINF); //
d[from] = 0; //0
bool have_negroop = false;
for (ll i = 0; i < N; i++) {
for (ll j = 0; j < N; j++) {
for (int k = 0; k < edge[j].size(); k++)
{
ll from = j;
ll to = edge[j][k].first;
ll cost = edge[j][k].second;
if (d[to] > d[from] + cost) { //
d[to] = d[from] + cost;
//
if (i == N - 1)
{
have_negroop = true;
break;
}
}
}
}
}
return pll(d[to], have_negroop);
}
//---------------------------------------------------------------
// (O(N), (logN))
//---------------------------------------------------------------
/*
<>
lazy_segtree<S, op, e, ll, mapping, composition, id> seg(A);
<> (pos x )
seg.set(int pos, ll x);
<>
seg.get(int pos);
<> ([l, r))
seg.prod(int l, int r);
<>
seg.all_prod();
<>
seg.apply(int pos, ll x);
seg.apply(int l, int r, ll x);
<> (g(op(a[l], a[l + 1], ..., a[r - 1])) = true r)
seg.max_right<g>(int l);
<> (g(op(a[l], a[l + 1], ..., a[r - 1])) = true l)
seg.min_left<g>(int r);
*/
template <class S, S(*op)(S, S), S(*e)(), class F, S(*mapping)(F, S), F(*composition)(F, F), F(*id)()>
struct lazy_segtree {
private:
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
public:
lazy_segtree() : lazy_segtree(0) {}
lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
lazy_segtree(const std::vector<S> &v) : _n(int(v.size())) {
log = ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push(r >> i);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
template <bool (*g)(S)> int max_right(int l) {
return max_right(l, [](S x) { return g(x); });
}
template <class G> int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*g)(S)> int min_left(int r) {
return min_left(r, [](S x) { return g(x); });
}
template <class G> int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
//
//struct S {
// ll value; //
// int size; //
//};
//
//// (data, )
//S op(S l, S r) { return S{ max(l.value, r.value), l.size + r.size }; }
//
////
//S e() { return S{ 0, 0 }; }
//
//// F(x) (or, lazyret)
//S mapping(ll f, S x) { return S{ max(x.value, f), x.size }; }
//
//// (lazy)
//ll composition(ll l, ll r) { return max(l, r); }
//
//// lazy
//ll id() { return 0; }
//
////
//ll V;
//bool g(S v) {
// return V > v.value;
//}
int main() {
//////==================================
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cout << fixed << setprecision(25);
//////==================================
/*
   
 
*/
ll N;
cin >> N;
vll grundy(N + 10, 0);
for (int i = 2; i <= N; i++)
{
vbool used(N + 10, false);
used[grundy[i / 2] ^ grundy[i - (i / 2)]] = true;
if(i % 3 == 0)
used[grundy[i / 3]] = true;
if (i % 3 == 1)
used[grundy[i / 3 + 1]] = true;
if (i % 3 == 2)
used[grundy[i / 3]] = true;
for (int j = 0; j < N + 10; j++)
{
if (!used[j])
{
grundy[i] = j;
break;
}
}
}
cout << (grundy[N] != 0 ? "A" : "B") << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0