1#include <iostream>
 2#include <map>
 3#include <limits>
 4#include <algorithm>
 5using i64 = long long;
 6
 7int main() {
 8    std::ios::sync_with_stdio(false);
 9    std::cin.tie(nullptr);
10
11    std::map<i64, i64> width;
12    i64 s = 0LL;
13    for (i64 p = 1, v = 1; s < std::numeric_limits<i64>::max() / 10; ++p) {
14        s += width[p] = v;
15        if (p & 1) v *= 2;
16        else v *= 3;
17    }
18
19    i64 t;
20    while (std::cin >> t) {
21        i64 sum = 0LL;
22        auto fnd = std::find_if(width.begin(), width.end(), [t, &sum] (auto x) mutable { return t < (sum += x.second); });
23        auto [p, v] = *fnd;
24
25        std::cout << p << ' ' << t - (sum - v) + 1 << std::endl;
26    }
27
28    return 0;
29}

 1#include <iostream>
 2#include <string>
 3#include <algorithm>
 4#include <cctype>
 5using i64 = long long;
 6
 7int main() {
 8    std::ios::sync_with_stdio(false);
 9    std::cin.tie(nullptr);
10
11    int tt;
12    std::cin >> tt;
13    while (tt--) {
14        std::string s;
15        std::cin >> s;
16        if (!isalpha(s[0]) && s[0] != '_') {
17            std::cout << "No" << std::endl;
18            continue;
19        }
20        if (!std::all_of(s.begin() + 1, s.end(), [](char x) { return isalnum(x) || x == '_'; })) {
21            std::cout << "No" << std::endl;
22            continue;
23        }
24        std::cout << "Yes" << std::endl;
25    }
26
27    return 0;
28}

 1#include <iostream>
 2#include <deque>
 3using i64 = long long;
 4
 5int main() {
 6    std::ios::sync_with_stdio(false);
 7    std::cin.tie(nullptr);
 8
 9    int q;
10    std::cin >> q;
11    std::deque<int> dq;
12    while (q--) {
13        char instruction;
14        std::cin >> instruction;
15        int operand;
16        switch (instruction) {
17        case 's':
18        case 'q':
19            std::cin >> operand;
20            dq.push_back(operand);
21            break;
22        case 'S':
23            if (!dq.empty()) {
24                dq.pop_back();
25            }
26            break;
27        case 'Q':
28            if (!dq.empty()) {
29                dq.pop_front();
30            }
31            break;
32        case 'd':
33            if (dq.empty()) {
34                std::cout << "empty" << std::endl;
35            } else {
36                int n = dq.size();
37                for (int i = 0; i < n; ++i) {
38                    std::cout << dq[i] << ",\n"[i == n - 1];
39                }
40            }
41            break;
42        default:
43            break;
44        }
45    }
46
47    return 0;
48}

 1#include <iostream>
 2#include <string>
 3#include <array>
 4#include <vector>
 5using i64 = long long;
 6
 7void update(std::array<int, 2>&, const char);
 8bool check(const std::array<int, 2>&);
 9
10int main() {
11    std::ios::sync_with_stdio(false);
12    std::cin.tie(nullptr);
13
14    std::string s;
15    std::cin >> s;
16    int n = s.length();
17
18    int ans = 0;
19    std::vector<std::array<int, 2>> prev(n), f(n);
20    for (int i = 0; i + 1 < n; ++i) {
21        update(prev[i], s[i]);
22        update(prev[i], s[i + 1]);
23        if (check(prev[i])) {
24            ans = 2;
25        }
26    }
27
28    for (int d = 2; d < n; ++d) {
29        for (int i = 0; i + d < n; ++i) {
30            f[i] = prev[i];
31            update(f[i], s[i + d]);
32            if (d & 1) {
33                if (check(f[i])) {
34                    ans = 1 + d;
35                }
36            }
37        }
38        f.swap(prev);
39    }
40
41    std::cout << ans << std::endl;
42
43    return 0;
44}
45
46void update(std::array<int, 2>& a, const char c) {
47    switch (c) {
48    case 'r': ++a[0]; break;
49    case 'o': --a[0]; break;
50    case 'x': ++a[1]; break;
51    case 'y': --a[1]; break;
52    }
53}
54
55bool check(const std::array<int, 2>& a) {
56    return !a[0] && !a[1];
57}

 1#include <iostream>
 2#include <vector>
 3#include <algorithm>
 4using i64 = long long;
 5
 6struct Student {
 7    int id;
 8    int p, s;
 9    Student() = default;
10    Student(int id, int p, int s) : id{id}, p{p}, s{s} {}
11};
12
13int main() {
14    std::ios::sync_with_stdio(false);
15    std::cin.tie(nullptr);
16
17    constexpr int N = 60;
18    std::vector<Student> v(N);
19    int my_id;
20    std::cin >> my_id;
21    for (int i = 0; i < N; ++i) std::cin >> v[i].id;
22    for (int i = 0; i < N; ++i) std::cin >> v[i].p;
23    for (int i = 0; i < N; ++i) std::cin >> v[i].s;
24
25    std::sort(v.begin(), v.end(), [](const Student& a, const Student& b) {
26        auto af = 2 * a.p + 1 * a.s;
27        auto bf = 2 * b.p + 1 * b.s;
28        if (af != bf)
29            return af > bf;
30        else if (a.p != b.p)
31            return a.p > b.p;
32        else if (a.s != b.s)
33            return a.s > b.s;
34        return a.id < b.id;
35    });
36    
37    auto fnd = std::find_if(v.begin(), v.end(), [my_id](const Student& s) { return s.id == my_id; });
38
39    if (fnd == v.begin()) {
40        std::cout << "Xepa Champion" << std::endl;
41    } else {
42        std::cout << fnd - v.begin() + 1 << std::endl;
43    }
44
45    return 0;
46}

 1#include <iostream>
 2#include <unordered_map>
 3#include <limits>
 4#include <cassert>
 5using i64 = long long;
 6
 7int main() {
 8    std::ios::sync_with_stdio(false);
 9    std::cin.tie(nullptr);
10
11    std::unordered_map<int, i64> t;
12    for (i64 i = 1, v = 2LL; v < i64(std::numeric_limits<int>::max()); ++i, v *= 2) {
13        t[i] = v - 1LL;
14    }
15
16    int n;
17    std::cin >> n;
18
19    int ans = 0;
20    while (n--) {
21        int i;
22        std::cin >> i;
23        ans += static_cast<int>(t[i]);
24        assert(ans >= 0);
25    }
26
27    std::cout << ans << std::endl;
28
29    return 0;
30}

 1#include <iostream>
 2#include <numeric>
 3using i64 = long long;
 4constexpr auto inf = 0x3f3f3f3f;
 5
 6int main() {
 7    std::ios::sync_with_stdio(false);
 8    std::cin.tie(nullptr);
 9
10    int t;
11    std::cin >> t;
12    while (t--) {
13        int g, l, m;
14        std::cin >> g >> l >> m;
15        if (g < l) std::swap(g, l);
16        if (g == l) {
17            if (m % g == 0) {
18                std::cout << m / g << std::endl;
19            } else {
20                std::cout << -1 << std::endl;
21            }
22            continue;
23        }
24
25        int ans = inf;
26        for (int f = m / g + 1; f >= 0; --f) {
27            auto remain = m - f * g;
28            if (remain < 0) continue;
29            if (remain % l == 0) {
30                ans = f + remain / l;
31                break;
32            }
33        }
34
35        std::cout << (ans == inf ? -1 : ans) << std::endl;
36    }
37
38    return 0;
39}

 1#include <iostream>
 2#include <queue>
 3#include <deque>
 4#include <utility>
 5#include <map>
 6using i64 = long long;
 7constexpr int dir[][2] = {1, 0, -1, 0, 0, 1, 0, -1};
 8
 9int operator-(std::pair<int, int> b, std::pair<int, int> a) {
10    return (b.first - a.first) + (b.second - a.second);
11}
12
13int main() {
14    std::ios::sync_with_stdio(false);
15    std::cin.tie(nullptr);
16
17    int w, h;
18    std::cin >> w >> h;
19    std::pair<int, int> start, end;
20    std::cin >> start.first >> start.second >> end.first >> end.second;
21
22    int cnt_portal;
23    std::cin >> cnt_portal;
24    std::map<std::pair<int, int>, std::pair<int, int>> portals;
25    while (cnt_portal--) {
26        int sx, sy, ex, ey;
27        std::cin >> sx >> sy >> ex >> ey;
28        portals[std::make_pair(sx, sy)] = std::make_pair(ex, ey);
29    }
30
31    std::vector vis(w, std::vector(h, false));
32    std::deque<std::pair<int, int>> q;
33    vis[start.first][start.second] = true;
34    q.push_back(start);
35    int depth = 0;
36    bool is_reached = false;
37    while (!q.empty()) {
38        int s = q.size();
39
40        while (s--) {
41            auto fr = q.front();
42            q.pop_front();
43            if (fr == end) {
44                is_reached = true;
45                break;
46            }
47
48            for (int d = 0; d < 4; ++d) {
49                int nxt_x = fr.first + dir[d][0], nxt_y = fr.second + dir[d][1];
50                if (nxt_x < 0 || nxt_x >= w || nxt_y < 0 || nxt_y >= h || vis[nxt_x][nxt_y])
51                    continue;
52                vis[nxt_x][nxt_y] = true;
53                q.push_back({nxt_x, nxt_y});
54            }
55
56            if (auto fnd = portals.find(fr); fnd != portals.end()) {
57                vis[fnd->second.first][fnd->second.second] = true;
58                q.push_back(fnd->second);
59            }
60        }
61        if (is_reached) break;
62        ++depth;
63    }
64
65    std::cout << (end - start) - depth << std::endl;
66
67    return 0;
68}

 1#include <iostream>
 2#include <unordered_map>
 3#include <vector>
 4#include <limits>
 5using i64 = long long;
 6constexpr auto inf = std::numeric_limits<int>::max();
 7
 8int main() {
 9    std::ios::sync_with_stdio(false);
10    std::cin.tie(nullptr);
11
12    int r, n;
13    std::cin >> r >> n;
14    std::unordered_map<int, int> cnt_map;
15    while (n--) {
16        int cnt_rune, val_rune;
17        std::cin >> cnt_rune >> val_rune;
18        cnt_map[val_rune] += cnt_rune;
19    }
20
21    std::vector cnt(cnt_map.begin(), cnt_map.end());
22    n = cnt.size();
23    std::vector f(n + 1, std::vector(r + 1, 0));
24    for (int i_rune = 1; i_rune <= n; ++i_rune) {
25        for (int i_r = 1; i_r <= r; ++i_r) {
26            f[i_rune][i_r] = inf;
27            int rune_val = cnt[i_rune - 1].first;
28            for (int c = 0; c <= cnt[i_rune - 1].second; ++c) {
29                int i_rd = std::max(0, i_r - rune_val * c);
30                if (f[i_rune - 1][i_rd] == inf) continue;
31                int acc = f[i_rune - 1][i_rd] + rune_val * c;
32                if (acc >= i_r) {
33                    f[i_rune][i_r] = std::min(f[i_rune][i_r], acc);
34                }
35            }
36        }
37    }
38
39    std::cout << (f[n][r] == inf ? -1 : f[n][r]) << std::endl;
40
41    return 0;
42}

 1#include <iostream>
 2#include <vector>
 3#include <limits>
 4using i64 = long long;
 5constexpr i64 inf = 0x3f3f3f3f3f3f3f3fLL;
 6
 7// https://oi-wiki.org/graph/shortest-path/#dijkstra-%E7%AE%97%E6%B3%95
 8struct edge {
 9    i64 v, w;
10};
11
12std::vector<std::vector<edge>> e;
13std::vector<i64> dis, vis;
14
15void dijkstra(int n, int s) {
16    dis[s] = 0;
17    for (int i = 1; i <= n; i++) {
18        i64 u = 0, mind = inf;
19        for (int j = 1; j <= n; j++)
20            if (!vis[j] && dis[j] < mind) u = j, mind = dis[j];
21        vis[u] = true;
22        for (auto ed : e[u]) {
23            i64 v = ed.v, w = ed.w;
24            if (dis[v] > dis[u] + w) dis[v] = dis[u] + w;
25        }
26    }
27}
28
29int main()
30{
31    std::ios::sync_with_stdio(false);
32    std::cin.tie(nullptr);
33
34    int n, q;
35    std::cin >> n >> q;
36    e.resize(n + 1);
37    dis.resize(n + 1, std::numeric_limits<i64>::max());
38    vis.resize(n + 1);
39
40    for (int i = 0; i < q; ++i) {
41        int a, b, d;
42        std::cin >> a >> b >> d;
43        e[a].push_back({1LL * b, 1LL * d});
44        e[b].push_back({1LL * a, 1LL * d});
45    }
46
47    dijkstra(n, 1);
48
49    std::cout << (dis[n] == std::numeric_limits<i64>::max() ? -1 : dis[n]) << std::endl;
50
51    return 0;
52}

 1#include <iostream>
 2#include <vector>
 3using i64 = long long;
 4
 5int main() {
 6    std::ios::sync_with_stdio(false);
 7    std::cin.tie(nullptr);
 8
 9    int w, h, n;
10    std::cin >> w >> h >> n;
11    std::vector diff(w + 2, std::vector(h + 2, 0));
12    for (int i = 0; i < n; ++i) {
13        int x1, y1, x2, y2;
14        std::cin >> x1 >> y1 >> x2 >> y2;
15        ++x1, ++y1, ++x2, ++y2;
16        ++diff[x1][y1];
17        --diff[x1][y2 + 1];
18        --diff[x2 + 1][y1];
19        ++diff[x2 + 1][y2 + 1];
20    }
21    for (int i = 1; i <= w; ++i) {
22        for (int j = 1; j <= h; ++j) {
23            diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
24        }
25    }
26    std::vector pref(w + 1, std::vector(h + 1, 0));
27    for (int i = 1; i <= w; ++i) {
28        for (int j = 1; j <= h; ++j) {
29            pref[i][j] = diff[i][j] + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
30        }
31    }
32
33    int q;
34    std::cin >> q;
35    while (q--) {
36        int x1, y1, x2, y2;
37        std::cin >> x1 >> y1 >> x2 >> y2;
38        ++x2, ++y2;
39        std::cout << pref[x2][y2] - pref[x1][y2] - pref[x2][y1] + pref[x1][y1] << std::endl;
40    }
41
42    return 0;
43}

 1#include <iostream>
 2#include <string>
 3#include <vector>
 4#include <unordered_set>
 5#include <algorithm>
 6#include <set>
 7#include <cctype>
 8using i64 = long long;
 9
10int main() {
11    std::ios::sync_with_stdio(false);
12    std::cin.tie(nullptr);
13
14    std::string token;
15    std::vector<std::unordered_set<std::string>> params;
16    std::vector<std::set<std::string>> vars;
17    while (std::cin >> token) {
18        if (token == "#") {
19            params.push_back({});
20            vars.push_back({});
21            while (std::cin >> token) {
22                if (token == ":") break;
23                params.back().insert(token);
24            }
25        } else if (std::all_of(token.begin(), token.end(), islower)) {
26            if (params.back().find(token) == params.back().end()) {
27                vars.back().insert(token);
28            }
29        }
30    }
31
32    int n = vars.size();
33    for (int i = 0; i < n; ++i) {
34        std::cout << i + 1;
35        for (auto var : vars[i]) {
36            std::cout << ' ' << var;
37        }
38        std::cout << std::endl;
39    }
40
41    return 0;
42}

 1width = [0]
 2s = 0
 3UPPER_BOUND = 1 << 63
 4v = 1
 5while s <= UPPER_BOUND:
 6    width.append(v)
 7    s += v
 8    if len(width) % 2 == 0:
 9        v *= 2
10    else:
11        v *= 3
12
13while True:
14    try:
15        n = int(input())
16        s = 0
17        for i, e in enumerate(width):
18            s += e
19            if n < s:
20                break
21        print(i, n - (s - width[i]) + 1)
22    except EOFError:
23        break

 1n = int(input())
 2for _ in range(n):
 3    var = input()
 4    if not (var[0].isalpha() or var[0] == '_'):
 5        print("No")
 6        continue
 7    if any([not (c.isalnum() or c == '_') for c in var]):
 8        print("No")
 9        continue
10    print("Yes")

 1n = int(input())
 2seq = []
 3
 4def print_seq(seq):
 5    if len(seq) == 0:
 6        print('empty')
 7        return
 8    print(','.join(seq))
 9
10for _ in range(n):
11    instr = input().split()
12    if instr[0] == 'q' or instr[0] == 's':
13        seq.append(str(int(instr[1])))
14    elif instr[0] == 'd':
15        print_seq(seq)
16    elif instr[0] == 'Q':
17        if len(seq) != 0:
18            seq.pop(0)
19    elif instr[0] == 'S':
20        if len(seq) != 0:
21            seq.pop()

 1s = input()
 2n = len(s)
 3REV = {'r': 'o', 'o': 'r', 'x': 'y', 'y': 'x'}
 4cnt = [0, 0]
 5
 6def update(c):
 7    global cnt
 8    if c == 'r':
 9        cnt[0] += 1
10    elif c == 'o':
11        cnt[0] -= 1
12    elif c == 'x':
13        cnt[1] += 1
14    elif c == 'y':
15        cnt[1] -= 1
16def check():
17    return cnt[0] == 0 and cnt[1] == 0
18
19ans = 0
20for d in range(2, n):
21    cnt = [0, 0]
22    for i in range(d):
23        update(s[i])
24    if check():
25        ans = d
26        continue
27    for i in range(d, n):
28        update(REV[s[i - d]])
29        update(s[i])
30        if check():
31            ans = d
32            break
33
34print(ans)

 1my_id = int(input())
 2ids = list(map(int, input().split()))
 3pps = list(map(int, input().split()))
 4sps = list(map(int, input().split()))
 5
 6class Player:
 7    def __init__(self, pid, pp, sp):
 8        self.pid = pid
 9        self.pp = pp
10        self.sp = sp
11        self.rp = 2 * pp + 1 * sp
12
13players = []
14for i in range(len(ids)):
15    players.append(Player(ids[i], pps[i], sps[i]))
16players.sort(key=lambda p : (-p.rp, -p.pp, -p.sp, p.pid))
17
18for i, player in enumerate(players):
19    if player.pid == my_id:
20        if i == 0:
21            print("Xepa Champion")
22        else:
23            print(i + 1)

 1m = [0]
 2s = 2
 3UPPER_BOUND = 1 << 32
 4while s <= UPPER_BOUND:
 5    m.append(s - 1)
 6    s *= 2
 7
 8n = int(input())
 9ans = 0
10for _ in range(n):
11    t = int(input())
12    ans += m[t]
13print(ans)

 1from math import inf
 2
 3t = int(input())
 4for _ in range(t):
 5    a, b, m = list(map(int, input().split()))
 6    if a < b:
 7        a, b = b, a
 8    elif a == b:
 9        if m % a == 0:
10            print(m // a)
11        else:
12            print(-1)
13        continue
14
15    ans = inf
16    for f in range(m // a + 1, -1, -1):
17        remain = m - f * a
18        if remain < 0: continue
19        if remain % b == 0:
20            ans = f + remain // b
21            break
22
23    print(ans if ans != inf else -1)

 1w, h, ax, ay, bx, by = list(map(int, input().split()))
 2t = int(input())
 3portals = dict()
 4for _ in range(t):
 5    x1, y1, x2, y2 = list(map(int, input().split()))
 6    portals[(x1, y1)] = (x2, y2)
 7
 8DIR = [(1, 0), (-1, 0), (0, 1), (0, -1)]
 9q = []
10q.append((ax, ay))
11vis = [[False] * h for _ in range(w)]
12vis[ax][ay] = True
13depth = 0
14is_reached = False
15while len(q) != 0:
16    s = len(q)
17    for _ in range(s):
18        curr = q[0]
19        q.pop(0)
20        if curr[0] == bx and curr[1] == by:
21            is_reached = True
22            break
23
24        for d in DIR:
25            nxt_x, nxt_y = curr[0] + d[0], curr[1] + d[1]
26            if nxt_x < 0 or nxt_x >= w or nxt_y < 0 or nxt_y >= h or vis[nxt_x][nxt_y]:
27                continue
28            vis[nxt_x][nxt_y] = True
29            q.append((nxt_x, nxt_y))
30
31        if curr in portals:
32            dest = portals[curr]
33            q.append(dest)
34            vis[dest[0]][dest[1]] = True
35
36    if is_reached: break
37    depth += 1
38
39print(abs(ax - bx) + abs(ay - by) - depth)

 1tokens = input().split()
 2func_env = []
 3captured = []
 4
 5is_parsing_params = False
 6for token in tokens:
 7    if is_parsing_params:
 8        if token == ":":
 9            is_parsing_params = False
10            continue
11        func_env[-1].add(token)
12    if token == "#":
13        func_env.append(set())
14        captured.append(set())
15        is_parsing_params = True
16        continue
17    elif all([c.isalpha() for c in token]):
18        if not token in func_env[-1]:
19            captured[-1].add(token)
20
21for i, c in enumerate(captured):
22    print(i + 1, end='')
23    c = sorted(list(c))
24    for name in c:
25        print(' ' + name, end='')
26    print()

 1def check_string(s):
 2    digits = [str(x) for x in range(10)]
 3    chars = [chr(x) for x in range(95) if x != 32]
 4    if s[0] in digits:
 5        return 'No'
 6    if any(c not in set(chars + digits) for c in s):
 7        return 'No'
 8    return 'Yes'
 9
10n = int(input())
11for _ in range(n):
12    s = input().strip()
13    ans = check_string(s)
14    print(ans)

 1def list_operation(commands):
 2    l = []
 3    for cmd in commands:
 4        if cmd[0] == 'q' or cmd[0] == 's':
 5            l.append(int(cmd[1]))
 6        elif cmd[0] == 'S' and l:
 7            l.pop()
 8        elif cmd[0] == 'Q' and l:
 9            l = l[1:]
10        elif cmd[0] == 'd':
11            if not l:
12                print("empty")
13                continue
14            print(','.join(str(i) for i in l))
15    return l
16
17n = int(input())
18commands = [input().split() for _ in range(n)]
19list_operation(commands)

1n = int(input())
2l = [int(input()) for _ in range(n)]
3maxx = max(l)
4mapl = [2 ** (i - 1) for i in range(1, maxx + 2)]
5mapl[1:] = [mapl[i - 1] + mapl[i] for i in range(1, maxx + 1)]
6ans = sum(mapl[i - 1] for i in l)
7print(ans)