1
#include <bits/stdc++.h>
2
using namespace std;
3

4
#define mp make_pair
5
#define pb push_back
6
#define fi first
7
#define se second
8

9
typedef long long ll;
10
typedef pair<int, int> pii;
11

12
const int maxn = 1e5 + 17;
13
const int N = 1e5;
14
const int mo = 1e9 + 7;
15

16

17

18
void debug(int x) {
19
    printf("??? %d\n", x);
20
}
21

22
void debug(int *X, int x) {
23
    printf("??? ");
24
    for(int i = 1; i <= x; i++) printf("%d%c", X[i], " \n"[i == x]);
25
}
26

27
void solve() {
28
    int n, ans;
29
    scanf("%d", &n);
30
    if(n % 3 == 0) ans = n / 3;
31
    else if(n % 3 == 2) ans = n / 3 + 1;
32
    else if(n >= 4) ans = n / 3 + 1;
33
    else ans = 2;
34
    printf("%d\n", ans);
35
}
36

37
int main() {
38
    int T;
39
    // T = 1;
40
    scanf("%d", &T);
41
    // cin >> T;
42
    while(T--) {
43
        solve();
44
    }
45
    return 0;
46
}

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
#define mp make_pair
5
#define pb push_back
6
#define fi first
7
#define se second
8

9
typedef long long ll;
10
typedef pair<int, int> pii;
11

12
const int maxn = 1e5 + 17;
13
const int N = 1e5;
14
const int mo = 1e9 + 7;
15

16

17

18
void debug(int x) {
19
    printf("??? %d\n", x);
20
}
21

22
void debug(int *X, int x) {
23
    // printf("??? ");
24
    for(int i = 1; i <= x; i++) printf("%d%c", X[i], " \n"[i == x]);
25
}
26

27
int a[maxn];
28

29
void solve() {
30
    int n, ans;
31
    scanf("%d", &n);
32
    for(int i = 1; i <= n; i++) a[i] = i;
33
    printf("%d\n", n);
34
    for(int i = 1; i <= n; i++) {
35
        debug(a, n);
36
        swap(a[i + 1], a[1]);
37
    }
38

39
    // printf("%d\n", ans);
40
}
41

42
int main() {
43
    int T;
44
    // T = 1;
45
    scanf("%d", &T);
46
    // cin >> T;
47
    while(T--) {
48
        solve();
49
    }
50
    return 0;
51
}

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
#define mp make_pair
5
#define pb push_back
6
#define fi first
7
#define se second
8

9
typedef long long ll;
10
typedef pair<int, int> pii;
11

12
const int maxn = 4e5 + 17;
13
const ll oo = 1e18;
14

15
void debug(int x) {
16
    printf("??? %d\n", x);
17
}
18

19
void debug(int *X, int x) {
20
    printf("??? ");
21
    for(int i = 1; i <= x; i++) printf("%d%c", X[i], " \n"[i == x]);
22
}
23

24
int m, n, a[maxn], b[maxn];
25

26
struct SegmentTree {
27
    struct node {
28
        ll w, lz;
29
    } t[maxn * 4];
30
    #define ls (x << 1)
31
    #define rs (x << 1 | 1)
32
    #define mid ((l + r) >> 1)
33
    void push_down(int x) {
34
        t[ls].w += t[x].lz;
35
        t[ls].lz += t[x].lz;
36
        t[rs].w += t[x].lz;
37
        t[rs].lz += t[x].lz;
38
        t[x].lz = 0;
39
    }
40
    void push_up(node& nx, node& nl, node& nr) {
41
        nx.w = max(nl.w, nr.w);
42
    }
43
    void build(int x = 1, int l = 1, int r = n) {
44
        t[x].lz = 0;
45
        if(l == r) {
46
            t[x].lz = 0;
47
            t[x].w = a[l] + 1 - (l - 1);
48
            if(l == 1) t[x].w = 0;
49
            // cout << "!!!" << t[x].w << endl;
50
            return;
51
        }
52
        build(ls, l, mid);
53
        build(rs, mid + 1, r);
54
        push_up(t[x], t[ls], t[rs]);
55
        // printf("%d %d %d %lld %lld %lld %lld\n", x, l, r, t[x].mx, t[x].mn, t[x].p, t[x].pp);
56
    }
57
    void modify(int ml, int mr, ll k, int x = 1, int l = 1, int r = n) {
58
        if(ml <= l && r <= mr) {
59
            t[x].w += k;
60
            t[x].lz += k;
61
            return;
62
        }
63
        push_down(x);
64
        if(ml <= mid) modify(ml, mr, k, ls, l, mid);
65
        if(mr > mid) modify(ml, mr, k, rs, mid + 1, r);
66
        push_up(t[x], t[ls], t[rs]);
67
    }
68
    node query(int ql, int qr, int x = 1, int l = 1, int r = n) {
69
        if(ql <= l && r <= qr) return t[x];
70
        push_down(x);
71
        node res, rl, rr;
72
        if(ql <= mid) rl = query(ql, qr, ls, l, mid);
73
        if(qr > mid) rr = query(ql, qr, rs, mid + 1, r);
74
        if(qr <= mid) return rl;
75
        if(ql > mid) return rr;
76
        push_up(res, rl, rr);
77
        return res;
78
    }
79
} sgt;
80

81

82
void solve() {
83
    scanf("%d", &m);
84
    ll ans1 = oo, ans = oo;
85
    n = m * 2;
86
    for(int i = 1; i <= m; i++) scanf("%d", &a[i]);
87
    for(int i = 1; i <= m; i++) scanf("%d", &a[m - i + 1 + m]);
88
    // debug(a, n);
89
    sgt.build();
90
    for(int i = 1; i <= m + 1; i += 2) {
91
        ll tmp = sgt.query(1, n).w;
92
        // printf("??? %lld\n", tmp);
93
        // printf("??? ");
94
        // for(int i = 1; i <= n; i++) printf("%d%c", sgt.query(i, i).w, " \n"[i == n]);
95
        ans1 = min(ans1, max(0ll, tmp));
96
        if(i == m + 1) break;
97
        sgt.modify(i + 1, 2 * m - i - 1, -2);
98
        sgt.modify(2 * m - i, 2 * m - i, (2 * (m - i - 1)));
99
        sgt.modify(2 * m - i + 1, 2 * m - i + 1, (2 * (m - i)));
100
    }
101
    ans = min(ans1 + n - 1, ans);
102
    // printf("%lld\n", ans);
103
    for(int i = 1; i <= n; i++) b[i] = a[i];
104
    m--;
105
    int inv = max(b[n] + 2, b[n - 1] + 1);
106
    for(int i = 1; i <= m; i++) a[i] = b[n - i] - inv;
107
    for(int i = 1; i <= m; i++) a[i + m] = b[n / 2 - i + 1] - inv;
108
    // a[1]++;
109
    n -= 2;
110
    // a[1] = 0;
111
    ans1 = oo;
112
    sgt.build();
113
    for(int i = 1; i <= m + 1; i += 2) {
114
        ll tmp = sgt.query(1, n).w;
115
        // printf("??? %lld\n", tmp);
116
        // printf("??? ");
117
        // for(int i = 1; i <= n; i++) printf("%d%c", sgt.query(i, i).w, " \n"[i == n]);
118
        ans1 = min(ans1, max(0ll, tmp));
119
        if(i == m + 1) break;
120
        sgt.modify(i + 1, 2 * m - i - 1, -2);
121
        sgt.modify(2 * m - i, 2 * m - i, (2 * (m - i - 1)));
122
        sgt.modify(2 * m - i + 1, 2 * m - i + 1, (2 * (m - i)));
123
    }
124
    ans1 += n - 1;
125
    // cout << ans1 << endl;
126
    n += 2;
127
    ans = min(ans1 + inv, ans);
128

129
    printf("%lld\n", ans);
130
}
131

132
int main() {
133
    int T;
134
    // T = 1;
135
    scanf("%d", &T);
136
    // cin >> T;
137
    while(T--) {
138
        solve();
139
    }
140
    return 0;
141
}

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
#define mp make_pair
5
#define pb push_back
6
#define fi first
7
#define se second
8

9
typedef long long ll;
10
typedef pair<int, int> pii;
11

12
const int maxn = 2e5 + 17;
13
const int N = 1e5;
14
const int mo = 998244353;
15

16
int add(int x, int y) {
17
    return (x + y) % mo;
18
}
19

20
void debug(int x) {
21
    printf("??? %d\n", x);
22
}
23

24
void debug(int *X, int x) {
25
    // printf("??? ");
26
    for(int i = 1; i <= x; i++) printf("%d%c", X[i], " \n"[i == x]);
27
}
28

29
int n, k, f[2][maxn], ans[maxn];
30

31
void solve() {
32
    scanf("%d%d", &n, &k);
33
    f[0][0] = 1;
34

35
    for(int i = 1, c = 1, lst = 0; i <= n; i++, c ^= 1) {
36
        int st = k * i + i * (i - 1) / 2;
37
        if(st > n) break;
38
        // debug(st);
39
        // debug(lst);
40
        for(int j = st; j <= n; j++) {
41
            int tmp = j - (k + i - 1);
42
            // f[c][j] = add(f[c ^ 1][tmp], f[c][tmp]);
43
            // cout << tmp << endl;
44
            f[c][j] = add(tmp >= lst ? f[c ^ 1][tmp] : 0, tmp >= st ? f[c][tmp] : 0);
45
            ans[j] = add(ans[j], f[c][j]);
46
        }
47
        lst = st;
48
        // debug(f[c], n);
49
    }
50
    // debug(f[c ^ 1], n);
51
    debug(ans, n);
52
    // printf("%d\n", n);
53

54

55
}
56

57
int main() {
58
    int T;
59
    T = 1;
60
    // scanf("%d", &T);
61
    // cin >> T;
62
    while(T--) {
63
        solve();
64
    }
65
    return 0;
66
}