C++ | 個人用メモ帳

2021年10月28日2021年10月28日

C++ の動作確認をしてみた（５６６）

C++の練習を兼ねて, AtCoder Beginner Contest 224 の問題C (Triangle?) ～問題D (8 Puzzle on Graph) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 幅優先探索(応用版, 連想配列の利用)の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 224 解説の各リンクをご覧下さい.

■C++版プログラム(問題C／AC版).

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
LL x[303], y[303];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld %lld", &x[i], &y[i]);
    
    // 2. 三角形の面積が正となるものは？
    int ans = 0;
    rep(i, N){
        repx(j, i + 1, N){
            repx(k, j + 1, N){
                // 点(x[i], y[i]) を 基準として考える.
                LL dx1 = x[j] - x[i], dy1 = y[j] - y[i];
                LL dx2 = x[k] - x[i], dy2 = y[k] - y[i];
                
                // 三角形の面積の二倍.
                LL s = abs(dx1 * dy2 - dy1 * dx2);
                
                // カウント.
                if(s) ans++;
            }
        }
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

LL x[303], y[303];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%lld %lld", &x[i], &y[i]);

// 2. 三角形の面積が正となるものは？

int ans = 0;

rep(i, N){

repx(j, i + 1, N){

repx(k, j + 1, N){

// 点(x[i], y[i]) を基準として考える.

LL dx1 = x[j] - x[i], dy1 = y[j] - y[i];

LL dx2 = x[k] - x[i], dy2 = y[k] - y[i];

// 三角形の面積の二倍.

LL s = abs(dx1 * dy2 - dy1 * dx2);

// カウント.

if(s) ans++;

}

// 3. 出力.

printf("%d\n", ans);

return 0;

}

[入力例]
4
0 1
1 3
1 1
-1 -1

[出力例]
3
※AtCoderテストケースより

[入力例]
20
224 433
987654321 987654321
2 0
6 4
314159265 358979323
0 0
-123456789 123456789
-1000000000 1000000000
124 233
9 -6
-4 0
9 5
-7 3
333333333 -333333333
-9 -1
7 -10
-1 5
324 633
1000000000 -1000000000
20 0

[出力例]
1124
※AtCoderテストケースより

[入力例]
25
524 378
4912 11687
1572 1134
1683 7524
11403 2790
2096 1512
4486 4715
3198 1800
1531 2059
2620 1890
10956 8787
5357 7672
12062 1210
14608 11716
3144 2268
3668 2646
4192 3024
18260 14645
4716 3402
1822 18104
5372 11052
2733 27156
5240 3780
3644 36208
5466 54312

[出力例]
2211

[入力例]

0 1

1 3

1 1

-1 -1

[出力例]

※AtCoderテストケースより

[入力例]

224 433

987654321 987654321

2 0

6 4

314159265 358979323

0 0

-123456789 123456789

-1000000000 1000000000

124 233

9 -6

-4 0

9 5

-7 3

333333333 -333333333

-9 -1

7 -10

-1 5

324 633

1000000000 -1000000000

20 0

[出力例]

1124

※AtCoderテストケースより

[入力例]

524 378

4912 11687

1572 1134

1683 7524

11403 2790

2096 1512

4486 4715

3198 1800

1531 2059

2620 1890

10956 8787

5357 7672

12062 1210

14608 11716

3144 2268

3668 2646

4192 3024

18260 14645

4716 3402

1822 18104

5372 11052

2733 27156

5240 3780

3644 36208

5466 54312

[出力例]

2211

■C++版プログラム(問題D／AC版).

// 解き直し.
// https://atcoder.jp/contests/abc224/editorial/2813
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
int g[10][10], p[10], q[10];

int main(){
    
    // 1. 入力情報.
    int M;
    scanf("%d", &M);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--;
        b--;
        g[a][b] = 1;
        g[b][a] = 1;
    }
    
    // 2. 初期状態.
    rep(i, 10) q[i] = 9;
    rep(i, 8){
        scanf("%d", &p[i]);
        q[p[i]] = i + 1;
    }
    string s = "";
    repx(i, 1, 10) s.pb(q[i] + '0');
    // printf("%s\n", s.c_str());
    
    // 3. 駒の配置(全通り).
    map<string, int> m;
    vi z(9);
    iota(all(z), 1);
    do{
        // 3-1. 駒の配置を作成.
        string t = "";
        rep(i, 9) t.pb(z[i] + '0');
        
        // 3-2. 保存.
        m[t] = -1;
        // printf("%s\n", t.c_str());
    }while(next_permutation(all(z)));
    
    // 4. 初期状態 から コマの配置までの距離を計算.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](string s, map<string, int> &d){
        // 4-1. 空のキュー.
        queue<string> q;
        
        // 4-2. 開始地点の距離.
        d[s] = 0;
        
        // 4-3. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 4-4. キューから取り出す.
            string u = q.front();
            q.pop();
            
            // 4-5. グラフの辺を全探索.
            rep(i, 9){
                repx(j, i + 1, 9){
                    // 辺(i, j) が存在するか？
                    if(g[i][j]){
                        // s[i] = 9 or s[j] = 9 の 場合.
                        if(u[i] == '9' || u[j] == '9'){
                            // コピー作成.
                            string v = u;
                            
                            // s[i], s[j] を 入れ替え.
                            swap(v[i], v[j]);
                            
                            // 未訪問ならば追加.
                            if(m[v] == -1){
                                m[v] = m[u] + 1;
                                q.push(v);
                            }
                        }
                    }
                }
            }
        }
        return;
    };
    bfs(s, m);
    
    // 5. 出力.
    printf("%d\n", m["123456789"]);
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/abc224/editorial/2813

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

#define all(x) x.begin(), x.end()

int g[10][10], p[10], q[10];

int main(){

// 1. 入力情報.

int M;

scanf("%d", &M);

rep(i, M){

int a, b;

scanf("%d %d", &a, &b);

a--;

b--;

g[a][b] = 1;

g[b][a] = 1;

}

// 2. 初期状態.

rep(i, 10) q[i] = 9;

rep(i, 8){

scanf("%d", &p[i]);

q[p[i]] = i + 1;

}

string s = "";

repx(i, 1, 10) s.pb(q[i] + '0');

// printf("%s\n", s.c_str());

// 3. 駒の配置(全通り).

map<string, int> m;

vi z(9);

iota(all(z), 1);

do{

// 3-1. 駒の配置を作成.

string t = "";

rep(i, 9) t.pb(z[i] + '0');

// 3-2. 保存.

m[t] = -1;

// printf("%s\n", t.c_str());

}while(next_permutation(all(z)));

// 4. 初期状態からコマの配置までの距離を計算.

// https://ja.wikipedia.org/wiki/幅優先探索

auto bfs = [&](string s, map<string, int> &d){

// 4-1. 空のキュー.

queue<string> q;

// 4-2. 開始地点の距離.

d[s] = 0;

// 4-3. 探索地点 s をキュー q に追加.

q.push(s);

while(!q.empty()){

// 4-4. キューから取り出す.

string u = q.front();

q.pop();

// 4-5. グラフの辺を全探索.

rep(i, 9){

repx(j, i + 1, 9){

// 辺(i, j) が存在するか？

if(g[i][j]){

// s[i] = 9 or s[j] = 9 の場合.

if(u[i] == '9' || u[j] == '9'){

// コピー作成.

string v = u;

// s[i], s[j] を入れ替え.

swap(v[i], v[j]);

// 未訪問ならば追加.

if(m[v] == -1){

m[v] = m[u] + 1;

q.push(v);

}

return;

};

bfs(s, m);

// 5. 出力.

printf("%d\n", m["123456789"]);

return 0;

}

[入力例]
5
1 2
1 3
1 9
2 9
3 9
3 9 2 4 5 6 7 8

[出力例]
5
※AtCoderテストケースより

[入力例]
5
1 2
1 3
1 9
2 9
3 9
1 2 3 4 5 6 7 8

[出力例]
0
※AtCoderテストケースより

[入力例]
12
8 5
9 6
4 5
4 1
2 5
8 9
2 1
3 6
8 7
6 5
7 4
2 3
1 2 3 4 5 6 8 7

[出力例]
-1
※AtCoderテストケースより

[入力例]
12
6 5
5 4
4 1
4 7
8 5
2 1
2 5
6 9
3 6
9 8
8 7
3 2
2 3 4 6 1 9 7 8

[出力例]
16
※AtCoderテストケースより

[入力例]
0
1 6 4 8 5 2 3 7

[出力例]
-1

[入力例]
11
1 9
1 6
2 6
2 4
4 9
6 9
3 6
3 9
5 9
5 7
7 9
6 4 2 1 7 3 5 8

[出力例]
11

[入力例]
30
4 7
1 9
2 5
1 5
3 5
6 8
2 4
3 9
4 9
3 7
5 6
5 9
1 2
3 6
5 7
7 8
2 3
2 9
3 8
7 9
2 6
2 8
1 4
2 7
3 4
4 6
4 8
1 8
1 3
4 5
3 2 6 7 5 1 4 8

[出力例]
7

[入力例]
36
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 3
2 4
2 5
2 6
2 7
2 8
2 9
3 4
3 5
3 6
3 7
3 8
3 9
4 5
4 6
4 7
4 8
4 9
5 6
5 7
5 8
5 9
6 7
6 8
6 9
7 8
7 9
8 9
8 5 7 3 6 2 4 1

[出力例]
11

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

[入力例]

1 2

1 3

1 9

2 9

3 9

3 9 2 4 5 6 7 8

[出力例]

※AtCoderテストケースより

[入力例]

1 2

1 3

1 9

2 9

3 9

1 2 3 4 5 6 7 8

[出力例]

※AtCoderテストケースより

[入力例]

8 5

9 6

4 5

4 1

2 5

8 9

2 1

3 6

8 7

6 5

7 4

2 3

1 2 3 4 5 6 8 7

[出力例]

-1

※AtCoderテストケースより

[入力例]

6 5

5 4

4 1

4 7

8 5

2 1

2 5

6 9

3 6

9 8

8 7

3 2

2 3 4 6 1 9 7 8

[出力例]

※AtCoderテストケースより

[入力例]

1 6 4 8 5 2 3 7

[出力例]

-1

[入力例]

1 9

1 6

2 6

2 4

4 9

6 9

3 6

3 9

5 9

5 7

7 9

6 4 2 1 7 3 5 8

[出力例]

[入力例]

4 7

1 9

2 5

1 5

3 5

6 8

2 4

3 9

4 9

3 7

5 6

5 9

1 2

3 6

5 7

7 8

2 3

2 9

3 8

7 9

2 6

2 8

1 4

2 7

3 4

4 6

4 8

1 8

1 3

4 5

3 2 6 7 5 1 4 8

[出力例]

[入力例]

1 2

1 3

1 4

1 5

1 6

1 7

1 8

1 9

2 3

2 4

2 5

2 6

2 7

2 8

2 9

3 4

3 5

3 6

3 7

3 8

3 9

4 5

4 6

4 7

4 8

4 9

5 6

5 7

5 8

5 9

6 7

6 8

6 9

7 8

7 9

8 9

8 5 7 3 6 2 4 1

[出力例]

■参照サイト
AtCoder Beginner Contest 224

2021年10月27日

C++ の動作確認をしてみた（５６５）

C++の練習を兼ねて, AtCoder Beginner Contest 223 の問題F (Parenthesis Checking) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説プログラムを参考に提出して, ようやく, AC版に到達出来た.
2. 遅延評価セグメント木が復習できたので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 223 解説の各リンクをご覧下さい.

■C++版プログラム(問題F／AC版).

// 解答不能.
// https://atcoder.jp/contests/abc223/editorial/2774
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const int INF = 2020202020;

// AtCoder Library(https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp)
// -> 一部改変(2021/10/27).
template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct LazySegmentTree{
  public:
    LazySegmentTree() : LazySegmentTree(0){}
    explicit LazySegmentTree(int n) : LazySegmentTree(vector<S>(n, e())){}
    explicit LazySegmentTree(const vector<S>& v) : _n(int(v.size())){
        log = 0;
        while((1 << log) < _n) log++;
        size = 1 << log;
        d = vector<S>(2 * size, e());
        lz = vector<F>(size, id());
        rep(i, _n) d[size + i] = v[i];
        repr(i, size - 1, 1) update(i);
    }
    void set(int p, S x){
        assert(0 <= p && p < _n);
        p += size;
        repr(i, log, 1) push(p >> i);
        d[p] = x;
        repx(i, 1, log + 1) update(p >> i);
    }
    S get(int p){
        assert(0 <= p && p < _n);
        p += size;
        repr(i, log, 1) 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;
        repr(i, log, 1){
            if(((l >> i) << i) != l) push(l >> i);
            if(((r >> i) << i) != r) push((r - 1) >> 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;
        repr(i, log, 1) push(p >> i);
        d[p] = mapping(f, d[p]);
        repx(i, 1, log + 1) 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;
        repr(i, log, 1){
            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;
        }
        repx(i, 1, log + 1){
            if(((l >> i) << i) != l) update(l >> i);
            if(((r >> i) << i) != r) update((r - 1) >> i);
        }
    }
private:
    int _n, size, log;
    vector<S> d;
    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();
    }
};

int op(int a, int b){
    return min(a, b);
}
int e(){
    return INF;
}
int mapping(int f, int x){
    return f + x;
}
int composition(int f, int g){
    return f + g;
}
int id(){
    return 0;
}

int main(){
    
    // 1. 入力情報.
    int N, Q;
    char c[202020];
    scanf("%d %d %s", &N, &Q, c);
    string s(c);
    
    // 2. 前処理.
    vi v(N + 1);
    rep(i, N) v[i + 1] = (s[i] == '(') ? v[i] + 1 : v[i] - 1;
    
    // 3. クエリ回答.
    LazySegmentTree<int, op, e, int, mapping, composition, id> seg(v);
    rep(i, Q){
        // 3-1. クエリ情報.
        int t, l, r;
        scanf("%d %d %d", &t, &l, &r);
        
        // 3-2. パターン 1.
        if(t == 1){
            // l文字目, r文字目更新.
            if(s[l - 1] == '(' && s[r - 1] == ')') seg.apply(l, r, -2);
            if(s[l - 1] == ')' && s[r - 1] == '(') seg.apply(l, r, 2);
            
            // l文字目, r文字目 を 入れ替え.
            swap(s[l - 1], s[r - 1]);
        }
        
        // 3-3. パターン 2.
        if(t == 2){
            // (l - 1)文字目, r文字目 までの累積和.
            int lCum = seg.get(l - 1);
            int rCum = seg.get(r);
            
            // [l - 1, r] の 最小値.
            int bMin = seg.prod(l - 1, r + 1);
            
            // 出力.
            printf("%s\n", (bMin == lCum && lCum == rCum) ? "Yes" : "No");
        }
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

// 解答不能.

// https://atcoder.jp/contests/abc223/editorial/2774

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

const int INF = 2020202020;

// AtCoder Library(https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp)

// -> 一部改変(2021/10/27).

template <class S,

S (*op)(S, S),

S (*e)(),

class F,

S (*mapping)(F, S),

F (*composition)(F, F),

F (*id)()>

struct LazySegmentTree{

public:

LazySegmentTree() : LazySegmentTree(0){}

explicit LazySegmentTree(int n) : LazySegmentTree(vector<S>(n, e())){}

explicit LazySegmentTree(const vector<S>& v) : _n(int(v.size())){

log = 0;

while((1 << log) < _n) log++;

size = 1 << log;

d = vector<S>(2 * size, e());

lz = vector<F>(size, id());

rep(i, _n) d[size + i] = v[i];

repr(i, size - 1, 1) update(i);

}

void set(int p, S x){

assert(0 <= p && p < _n);

p += size;

repr(i, log, 1) push(p >> i);

d[p] = x;

repx(i, 1, log + 1) update(p >> i);

}

S get(int p){

assert(0 <= p && p < _n);

p += size;

repr(i, log, 1) 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;

repr(i, log, 1){

if(((l >> i) << i) != l) push(l >> i);

if(((r >> i) << i) != r) push((r - 1) >> 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;

repr(i, log, 1) push(p >> i);

d[p] = mapping(f, d[p]);

repx(i, 1, log + 1) 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;

repr(i, log, 1){

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;

}

repx(i, 1, log + 1){

if(((l >> i) << i) != l) update(l >> i);

if(((r >> i) << i) != r) update((r - 1) >> i);

}

private:

int _n, size, log;

vector<S> d;

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();

}

};

int op(int a, int b){

return min(a, b);

}

int e(){

return INF;

}

int mapping(int f, int x){

return f + x;

}

int composition(int f, int g){

return f + g;

}

int id(){

return 0;

}

int main(){

// 1. 入力情報.

int N, Q;

char c[202020];

scanf("%d %d %s", &N, &Q, c);

string s(c);

// 2. 前処理.

vi v(N + 1);

rep(i, N) v[i + 1] = (s[i] == '(') ? v[i] + 1 : v[i] - 1;

// 3. クエリ回答.

LazySegmentTree<int, op, e, int, mapping, composition, id> seg(v);

rep(i, Q){

// 3-1. クエリ情報.

int t, l, r;

scanf("%d %d %d", &t, &l, &r);

// 3-2. パターン 1.

if(t == 1){

// l文字目, r文字目更新.

if(s[l - 1] == '(' && s[r - 1] == ')') seg.apply(l, r, -2);

if(s[l - 1] == ')' && s[r - 1] == '(') seg.apply(l, r, 2);

// l文字目, r文字目を入れ替え.

swap(s[l - 1], s[r - 1]);

}

// 3-3. パターン 2.

if(t == 2){

// (l - 1)文字目, r文字目までの累積和.

int lCum = seg.get(l - 1);

int rCum = seg.get(r);

// [l - 1, r] の最小値.

int bMin = seg.prod(l - 1, r + 1);

// 出力.

printf("%s\n", (bMin == lCum && lCum == rCum) ? "Yes" : "No");

}

return 0;

}

[入力例]
5 3
(())(
2 1 4
2 1 2
2 4 5

[出力例]
Yes
No
No
※AtCoderのテストケースより

[入力例]
5 3
(())(
2 1 4
1 1 4
2 1 4

[出力例]
Yes
No
※AtCoderのテストケースより

[入力例]
8 8
(()(()))
2 2 7
2 2 8
1 2 5
2 3 4
1 3 4
1 3 5
1 1 4
1 6 8

[出力例]
Yes
No
No
※AtCoderのテストケースより

[入力例]
20 15
()(())((((()))))(())
2 1 2
2 3 6
1 18 19
2 7 16
2 17 20
1 5 12
2 2 7
1 6 19
1 11 15
2 8 15
1 7 13
2 13 18
1 3 16
2 5 8
2 15 20

[出力例]
Yes
Yes
Yes
Yes
No
No
Yes
No
Yes

[入力例]
50 20
((()(((()(()((()))(()))(())())))))))))((()))()))))
2 19 22
1 17 20
1 7 11
2 17 20
2 18 28
2 39 44
1 15 24
1 20 39
2 24 27
2 3 26
2 40 43
1 12 31
2 22 32
2 28 29
1 9 15
2 18 23
2 13 16
1 12 37
2 45 48
1 5 8

[出力例]
Yes
Yes
No
Yes
Yes
No
Yes
No
Yes
No
Yes
No

[入力例]
100 30
()(()((()())()((())()()()()((((((())())(((()()(()))())())(()))))(())())((())((((())))))))(()))(()()(
1 37 61
2 7 12
2 30 39
1 23 61
2 25 26
1 7 50
2 9 56
2 45 56
2 77 86
1 40 73
2 28 57
1 6 11
2 47 54
1 34 65
2 40 64
2 73 76
1 6 23
2 29 65
1 15 30
1 32 42
1 43 44
2 20 27
2 44 57
1 34 60
2 26 63
1 49 58
1 17 57
2 90 93
1 30 51
2 96 99

[出力例]
Yes
Yes
No
No
Yes
Yes
No
Yes
No
Yes
No
Yes
Yes
No
Yes
Yes

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

[入力例]

5 3

(())(

2 1 4

2 1 2

2 4 5

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

5 3

(())(

2 1 4

1 1 4

2 1 4

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

8 8

(()(()))

2 2 7

2 2 8

1 2 5

2 3 4

1 3 4

1 3 5

1 1 4

1 6 8

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

20 15

()(())((((()))))(())

2 1 2

2 3 6

1 18 19

2 7 16

2 17 20

1 5 12

2 2 7

1 6 19

1 11 15

2 8 15

1 7 13

2 13 18

1 3 16

2 5 8

2 15 20

[出力例]

Yes

[入力例]

50 20

((()(((()(()((()))(()))(())())))))))))((()))()))))

2 19 22

1 17 20

1 7 11

2 17 20

2 18 28

2 39 44

1 15 24

1 20 39

2 24 27

2 3 26

2 40 43

1 12 31

2 22 32

2 28 29

1 9 15

2 18 23

2 13 16

1 12 37

2 45 48

1 5 8

[出力例]

Yes

[入力例]

100 30

()(()((()())()((())()()()()((((((())())(((()()(()))())())(()))))(())())((())((((())))))))(()))(()()(

1 37 61

2 7 12

2 30 39

1 23 61

2 25 26

1 7 50

2 9 56

2 45 56

2 77 86

1 40 73

2 28 57

1 6 11

2 47 54

1 34 65

2 40 64

2 73 76

1 6 23

2 29 65

1 15 30

1 32 42

1 43 44

2 20 27

2 44 57

1 34 60

2 26 63

1 49 58

1 17 57

2 90 93

1 30 51

2 96 99

[出力例]

Yes

■参照サイト
AtCoder Beginner Contest 223

2021年10月26日

C++ の動作確認をしてみた（５６４）

C++の練習を兼ねて, AtCoder Beginner Contest 223 の問題E (Placing Rectangles) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 個人的には, 全探索を使うテクニックが面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 223 解説の各リンクをご覧下さい.

■C++版プログラム(問題E／AC版).

// 解き直し.
// https://atcoder.jp/contests/abc223/editorial/2781
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
LL p[11];

int main(){
    
    // 1. 入力情報.
    rep(i, 5) scanf("%lld", &p[i]);
    
    // 2. 分割できるか(全探索).
    bool ok = false;
    rep(i, 2){
        rep(j, 2){
            if(i != j){
                // X, Y を 選択.
                LL X = p[i], Y = p[j];
                repx(a, 2, 5){
                    repx(b, 2, 5){
                        repx(c, 2, 5){
                            if(a != b && b != c && c != a){
                                // A, B, C を 選択.
                                LL A = p[a], B = p[b], C = p[c];
                                
                                // 一つ目の長方形.
                                // A を 収納.
                                LL ha = A / X;
                                if(A % X != 0) ha++;
                                
                                // 二つ目の長方形.
                                // -> 縦, 横方向をチェック.
                                LL hbc = Y - ha;
                                if(hbc > 0){
                                    // 横方向で分割できるか？
                                    // B を 収納.
                                    LL hb = B / X;
                                    if(B % X != 0) hb++;
                                    
                                    // C を 収納.
                                    LL hc = C / X;
                                    if(C % X != 0) hc++;
                                    
                                    // 分割OK.
                                    if(hb + hc <= hbc) ok = true;
                                    
                                    // 縦方向で分割できるか？
                                    // B を 収納.
                                    LL wb = B / hbc;
                                    if(B % hbc != 0) wb++;
                                    
                                    // C を 収納.
                                    LL wc = C / hbc;
                                    if(C % hbc != 0) wc++;
                                    
                                    // 分割OK.
                                    if(wb + wc <= X) ok = true;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    
    // 3. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc223/editorial/2781

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

LL p[11];

int main(){

// 1. 入力情報.

rep(i, 5) scanf("%lld", &p[i]);

// 2. 分割できるか(全探索).

bool ok = false;

rep(i, 2){

rep(j, 2){

if(i != j){

// X, Y を選択.

LL X = p[i], Y = p[j];

repx(a, 2, 5){

repx(b, 2, 5){

repx(c, 2, 5){

if(a != b && b != c && c != a){

// A, B, C を選択.

LL A = p[a], B = p[b], C = p[c];

// 一つ目の長方形.

// A を収納.

LL ha = A / X;

if(A % X != 0) ha++;

// 二つ目の長方形.

// -> 縦, 横方向をチェック.

LL hbc = Y - ha;

if(hbc > 0){

// 横方向で分割できるか？

// B を収納.

LL hb = B / X;

if(B % X != 0) hb++;

// C を収納.

LL hc = C / X;

if(C % X != 0) hc++;

// 分割OK.

if(hb + hc <= hbc) ok = true;

// 縦方向で分割できるか？

// B を収納.

LL wb = B / hbc;

if(B % hbc != 0) wb++;

// C を収納.

LL wc = C / hbc;

if(C % hbc != 0) wc++;

// 分割OK.

if(wb + wc <= X) ok = true;

}

// 3. 出力.

printf("%s\n", ok ? "Yes" : "No");

return 0;

}

[入力例]
3 3 2 2 3

[出力例]
Yes
※AtCoderテストケースより

[入力例]
3 3 4 4 1

[出力例]
No
※AtCoderテストケースより

[入力例]
1000000000 1000000000 1000000000000000000 1000000000000000000 1000000000000000000

[出力例]
No
※AtCoderテストケースより

[入力例]
3 5 10 2 3

[出力例]
Yes

[入力例]
5 5 12 8 5

[出力例]
Yes

[入力例]
5 5 13 7 3

[出力例]
No

[入力例]
3 10 13 10 5

[出力例]
Yes

[入力例]
3 10 13 11 4

[出力例]
No

[入力例]
3 10 9 18 3

[出力例]
Yes

[入力例]

3 3 2 2 3

[出力例]

Yes

※AtCoderテストケースより

[入力例]

3 3 4 4 1

[出力例]

※AtCoderテストケースより

[入力例]

1000000000 1000000000 1000000000000000000 1000000000000000000 1000000000000000000

[出力例]

※AtCoderテストケースより

[入力例]

3 5 10 2 3

[出力例]

Yes

[入力例]

5 5 12 8 5

[出力例]

Yes

[入力例]

5 5 13 7 3

[出力例]

[入力例]

3 10 13 10 5

[出力例]

Yes

[入力例]

3 10 13 11 4

[出力例]

[入力例]

3 10 9 18 3

[出力例]

Yes

■参照サイト
AtCoder Beginner Contest 223

2021年10月25日

C++ の動作確認をしてみた（５６３）

C++の練習を兼ねて, AtCoder Library Practice Contest の問題G (SCC) を解いてみた.

■感想.
1. 問題Gは, 強連結成分分解を使う方針で, AC版に到達出来た.
2. 強連結成分分解(Strongly Connected Component)について, 改めて復習できたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

■C++版プログラム(問題G／AC版).

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using P = pair<int, int>;
using PQ = priority_queue<P>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second
#define pb push_back
const int MAX = 505050;
int memo[MAX], scc[MAX];

int main(){
    
    // 1. 入力情報.
    int N, M, a, b;
    scanf("%d %d", &N, &M);
    vvi G1(N), G2(N);
    rep(i, M){
        scanf("%d %d", &a, &b);
        G1[a].pb(b);  // 有向辺.
        G2[b].pb(a);  // 有向辺(逆向き).
    }
    
    // 強連結成分分解(Strongly Connected Component).
    // https://manabitimes.jp/math/1250
    // 2. 行き止まりの順番を保存.
    int idx = 0;
    PQ pq;
    auto dfs1 = [&](auto&& self, int c) -> void{
        // 訪問済フラグ設定.
        memo[c] = 1;
        
        // 取り出した要素を処理.
        for(auto &n : G1[c]) if(!memo[n]) self(self, n);
        
        // 行き止まりの順番を保存.
        pq.push({++idx, c});
    };
    rep(i, N) if(!memo[i]) dfs1(dfs1, i);
    
    // 3. 強連結成分に分解.
    vvi ans(N + 1);
    idx = 0;
    auto dfs2 = [&](auto&& self, int c) -> void{
        // 連結成分番号設定.
        scc[c] = idx;
        
        // 取り出した要素を処理.
        for(auto &n : G2[c]) if(!scc[n]) self(self, n);
        
        // 頂点を保存(トポロジカルソート).
        ans[idx].pb(c);
    };
    while(!pq.empty()){
        // 要素を取り出す.
        P p = pq.top();
        pq.pop();
        
        // 連結成分番号が設定済み.
        if(scc[p.b]) continue;
        
        // インクリメント.
        idx++;
        
        // 連結成分番号設定.
        dfs2(dfs2, p.b);
    }
    
    // 4. 出力.
    printf("%d\n", idx);
    repx(i, 1, idx + 1){
        // 4-1. 強連結成分の頂点数.
        int l = ans[i].size();
        printf("%d ", l);
        
        // 4-2. 頂点を出力.
        rep(j, l){
            printf("%d", ans[i][j]);
            printf("%s", (j < l - 1) ? " " : "\n");
        }
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using P = pair<int, int>;

using PQ = priority_queue<P>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define a first

#define b second

#define pb push_back

const int MAX = 505050;

int memo[MAX], scc[MAX];

int main(){

// 1. 入力情報.

int N, M, a, b;

scanf("%d %d", &N, &M);

vvi G1(N), G2(N);

rep(i, M){

scanf("%d %d", &a, &b);

G1[a].pb(b); // 有向辺.

G2[b].pb(a); // 有向辺(逆向き).

}

// 強連結成分分解(Strongly Connected Component).

// https://manabitimes.jp/math/1250

// 2. 行き止まりの順番を保存.

int idx = 0;

PQ pq;

auto dfs1 = [&](auto&& self, int c) -> void{

// 訪問済フラグ設定.

memo[c] = 1;

// 取り出した要素を処理.

for(auto &n : G1[c]) if(!memo[n]) self(self, n);

// 行き止まりの順番を保存.

pq.push({++idx, c});

};

rep(i, N) if(!memo[i]) dfs1(dfs1, i);

// 3. 強連結成分に分解.

vvi ans(N + 1);

idx = 0;

auto dfs2 = [&](auto&& self, int c) -> void{

// 連結成分番号設定.

scc[c] = idx;

// 取り出した要素を処理.

for(auto &n : G2[c]) if(!scc[n]) self(self, n);

// 頂点を保存(トポロジカルソート).

ans[idx].pb(c);

};

while(!pq.empty()){

// 要素を取り出す.

P p = pq.top();

pq.pop();

// 連結成分番号が設定済み.

if(scc[p.b]) continue;

// インクリメント.

idx++;

// 連結成分番号設定.

dfs2(dfs2, p.b);

}

// 4. 出力.

printf("%d\n", idx);

repx(i, 1, idx + 1){

// 4-1. 強連結成分の頂点数.

int l = ans[i].size();

printf("%d ", l);

// 4-2. 頂点を出力.

rep(j, l){

printf("%d", ans[i][j]);

printf("%s", (j < l - 1) ? " " : "\n");

}

return 0;

}

[入力例]
6 7
1 4
5 2
3 0
5 5
4 1
0 3
4 2

[出力例]
4
1 5
2 4 1
1 2
2 3 0
※AtCoderテストケースより

[入力例]
11 14
0 1
1 0
0 7
7 9
9 8
7 8
8 10
10 7
1 2
2 5
2 3
5 4
4 2
3 4

[出力例]
4
1 6
2 1 0
4 9 8 10 7
4 5 3 4 2

[入力例]
7 10
0 6
6 0
0 1
1 2
2 1
2 3
2 4
4 3
5 4
3 5

[出力例]
3
2 6 0
2 2 1
3 5 4 3

[入力例]
20 25
0 1
1 0
0 7
7 8
8 18
1 9
9 10
10 11
10 12
11 12
12 9
1 2
2 3
3 6
6 5
5 4
4 2
4 19
13 1
13 14
13 17
17 15
16 17
15 16
14 15

[出力例]
10
1 13
1 14
3 16 17 15
2 1 0
1 7
1 8
1 18
5 3 6 5 4 2
1 19
4 10 11 12 9

100

101

[入力例]

6 7

1 4

5 2

3 0

5 5

4 1

0 3

4 2

[出力例]

1 5

2 4 1

1 2

2 3 0

※AtCoderテストケースより

[入力例]

11 14

0 1

1 0

0 7

7 9

9 8

7 8

8 10

10 7

1 2

2 5

2 3

5 4

4 2

3 4

[出力例]

1 6

2 1 0

4 9 8 10 7

4 5 3 4 2

[入力例]

7 10

0 6

6 0

0 1

1 2

2 1

2 3

2 4

4 3

5 4

3 5

[出力例]

2 6 0

2 2 1

3 5 4 3

[入力例]

20 25

0 1

1 0

0 7

7 8

8 18

1 9

9 10

10 11

10 12

11 12

12 9

1 2

2 3

3 6

6 5

5 4

4 2

4 19

13 1

13 14

13 17

17 15

16 17

15 16

14 15

[出力例]

1 13

1 14

3 16 17 15

2 1 0

1 7

1 8

1 18

5 3 6 5 4 2

1 19

4 10 11 12 9

■参照サイト
AtCoder Library Practice Contest
021 – Come Back in One Piece
強連結成分分解の意味とアルゴリズム

2021年10月24日

C++ の動作確認をしてみた（５６２）

C++の練習を兼ねて, AtCoder Grand Contest 038 の問題C (LCMs) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 解説にあるように, 計算削減のために, 逆数を考える方針が, 個人的には, 非常に面白い問題に感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Grand Contest 038 解説をご覧下さい.

■C++版プログラム(問題C／AC版).

// 解き直し.
// https://img.atcoder.jp/agc038/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
using vvl = vector<vl>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const LL MOD = 998244353;
LL a[202020], w[1010101], c[1010101];

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return: べき乗した計算結果(mod版).
LL mPow(LL a, LL b){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return t % MOD;
}

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        scanf("%lld", &a[i]);
        c[(int)a[i]]++; // a[i] = x となる個数を保存.
    }
    
    // 2. w の 計算.
    vvl div(1010101); // a[i] を 約数ごとに分類.
    repx(i, 1, 1010101) w[i] = mPow((LL)i, MOD - 2LL);
    repx(i, 1, 1010101){
        vl v;
        repex(j, i, 1010101, i){
            if(j % i == 0){
                if(j > i){
                    w[j] += MOD - w[i];
                    w[j] %= MOD;
                }
                if(c[j]) rep(k, c[j]) v.pb((LL)j);
            }
        }
        div[i] = v;
    }
    // ex. 
    // w[1] = +1
    // w[2] = -1 / 2 = 499122176
    // w[3] = -2 / 3 = 332748117
    // w[4] = -1 / 4 = 249561088
    // w[5] = -4 / 5 = 598946611
    // w[6] = +1 / 3 = 332748118
    // ...
    // w[10] =  +2 /  5 = 199648871
    // w[11] = -10 / 11 = 272248459
    // w[12] =  +1 /  6 = 166374059
    // ...
    // repx(i, 1, 13) printf("%lld ", w[i]);
    
    // 3. 解説上の数式を計算(Σw[d]Σ(a[i] * a[j])).
    LL ans = 0;
    repx(d, 1, 1010101){
        if(div[d].size()){
            // Σa[i] * a[j] の 計算準備.
            LL p = 0, q = 0;
            rep(i, div[d].size()){
                p += div[d][i];
                p %= MOD;
                q += div[d][i] * div[d][i];
                q %= MOD;
            }
            
            // Σa[i] * a[j] を 計算.
            // -> {(a1 + a2 + ... + ak) * (a1 + a2 + ... + ak) - a1 の 2乗 - ... - ak の 2乗} ÷ 2 で 計算.
            LL t = (p * p + MOD - q) % MOD;
            t *= mPow(2LL, MOD - 2LL);
            t %= MOD;
            
            // w[d] を 反映.
            ans += t * w[d];
            ans %= MOD;
        }
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

// 解き直し.

// https://img.atcoder.jp/agc038/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

using vvl = vector<vl>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

const LL MOD = 998244353;

LL a[202020], w[1010101], c[1010101];

// Fermat's little theorem から, 大きな冪乗の計算を行う.

// @param a: べき乗したい正整数.

// @param b: 指数.

// @return: べき乗した計算結果(mod版).

LL mPow(LL a, LL b){

LL t = 1;

while(b){

if(b & 1) t = (t * a) % MOD;

a = a * a % MOD;

b >>= 1;

}

return t % MOD;

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

scanf("%lld", &a[i]);

c[(int)a[i]]++; // a[i] = x となる個数を保存.

}

// 2. w の計算.

vvl div(1010101); // a[i] を約数ごとに分類.

repx(i, 1, 1010101) w[i] = mPow((LL)i, MOD - 2LL);

repx(i, 1, 1010101){

vl v;

repex(j, i, 1010101, i){

if(j % i == 0){

if(j > i){

w[j] += MOD - w[i];

w[j] %= MOD;

}

if(c[j]) rep(k, c[j]) v.pb((LL)j);

}

div[i] = v;

}

// ex.

// w[1] = +1

// w[2] = -1 / 2 = 499122176

// w[3] = -2 / 3 = 332748117

// w[4] = -1 / 4 = 249561088

// w[5] = -4 / 5 = 598946611

// w[6] = +1 / 3 = 332748118

// ...

// w[10] = +2 / 5 = 199648871

// w[11] = -10 / 11 = 272248459

// w[12] = +1 / 6 = 166374059

// ...

// repx(i, 1, 13) printf("%lld ", w[i]);

// 3. 解説上の数式を計算(Σw[d]Σ(a[i] * a[j])).

LL ans = 0;

repx(d, 1, 1010101){

if(div[d].size()){

// Σa[i] * a[j] の計算準備.

LL p = 0, q = 0;

rep(i, div[d].size()){

p += div[d][i];

p %= MOD;

q += div[d][i] * div[d][i];

q %= MOD;

}

// Σa[i] * a[j] を計算.

// -> {(a1 + a2 + ... + ak) * (a1 + a2 + ... + ak) - a1 の 2乗 - ... - ak の 2乗} ÷ 2 で計算.

LL t = (p * p + MOD - q) % MOD;

t *= mPow(2LL, MOD - 2LL);

t %= MOD;

// w[d] を反映.

ans += t * w[d];

ans %= MOD;

}

// 4. 出力.

printf("%lld\n", ans);

return 0;

}

[入力例]
3
2 4 6

[出力例]
22
※AtCoderテストケースより

[入力例]
8
1 2 3 4 6 8 12 12

[出力例]
313
※AtCoderテストケースより

[入力例]
10
356822 296174 484500 710640 518322 888250 259161 609120 592348 713644

[出力例]
353891724
※AtCoderテストケースより

[入力例]
5
1 2 12 16 18

[出力例]
322

[入力例]
12
2 4 8 18 24 36 48 52 60 64 72 84

[出力例]
15514

[入力例]
20
116 102 98 87 71 105 13 107 34 20 58 117 71 50 27 12 112 118 9 103

[出力例]
726127

[入力例]
50
3638 3573 884 2825 2621 3228 1807 82 3798 2285 358 4277 998 392 2300 3708 4132 4314 3414 363 233 61 1480 3895 4218 2576 3651 3763 4258 1270 135 2566 3098 2900 2407 729 1301 4215 2568 51 1528 2287 410 2305 3707 911 2417 1205 831 1501

[出力例]
518757047

[入力例]

2 4 6

[出力例]

※AtCoderテストケースより

[入力例]

1 2 3 4 6 8 12 12

[出力例]

313

※AtCoderテストケースより

[入力例]

356822 296174 484500 710640 518322 888250 259161 609120 592348 713644

[出力例]

353891724

※AtCoderテストケースより

[入力例]

1 2 12 16 18

[出力例]

322

[入力例]

2 4 8 18 24 36 48 52 60 64 72 84

[出力例]

15514

[入力例]

116 102 98 87 71 105 13 107 34 20 58 117 71 50 27 12 112 118 9 103

[出力例]

726127

[入力例]

3638 3573 884 2825 2621 3228 1807 82 3798 2285 358 4277 998 392 2300 3708 4132 4314 3414 363 233 61 1480 3895 4218 2576 3651 3763 4258 1270 135 2566 3098 2900 2407 729 1301 4215 2568 51 1528 2287 410 2305 3707 911 2417 1205 831 1501

[出力例]

518757047

■参照サイト
AtCoder Grand Contest 038

2021年10月23日

C++ の動作確認をしてみた（５６１）

C++の練習を兼ねて, AtCoder Beginner Contest 217 の問題H (Snuketoon) を解いてみた.

■感想.
1. 問題Hは, 方針が見えなかったので, 解説プログラムを参考に提出して, ようやく, AC版に到達出来た.
※ 解説プログラムが, Python実装だったので, C++版に置き換えて提出した.
2. 新しい知識として, Slope Trick に触れることが出来たので, 非常に良かったと思う.
3. 今後も, 新しいアルゴリズムを, 少しずつ学習していきたいと思った.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 217 解説の各リンクをご覧下さい.

■C++版プログラム(問題H／AC版).

// 解答不能.
// https://atcoder.jp/contests/abc217/editorial/2581
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
using PQ = priority_queue<LL, vector<LL>, greater<LL>>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)

// Slope Trick.
// https://atcoder.jp/contests/abc217/editorial/2581
// https://maspypy.com/slope-trick-1-解説編
// -> 一部改変.
struct SlopeTrick{
    PQ L; // 傾き 0以下で, 傾きの変化点全体の多重集合.
    PQ R; // 傾き 0以上で, 傾きの変化点全体の多重集合.
    LL addL, addR, minF;
    
    SlopeTrick(int n){
        addL = 0LL;
        addR = 0LL;
        minF = 0LL;
        rep(i, n + 1) L.push(0LL);
        rep(i, n + 1) R.push(0LL);
    }
    
    void pushLeft(LL x){
        L.push(-x + addL);
    }
    
    void pushRight(LL x){
        R.push(x - addR);
    }
    
    LL topLeft(){
        return -L.top() + addL;
    }
    
    LL topRight(){
        return R.top() + addR;
    }
    
    LL popLeft(){
        LL ret = -L.top() + addL;
        L.pop();
        return ret;
    }
    
    LL popRight(){
        LL ret = R.top() + addR;
        R.pop();
        return ret;
    }
    
    void addXsubA(LL a){
        minF += (L.size() ? max(0LL, topLeft() - a) : 0LL);
        pushLeft(a);
        pushRight(popLeft());
    }
    
    void addAsubX(LL a){
        minF += (R.size() ? max(0LL, a - topRight()) : 0LL);
        pushRight(a);
        pushLeft(popRight());
    }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. ゲームを進める.
    SlopeTrick st(N);
    LL t = 0;
    rep(i, N){
        // 今回分取得.
        LL T, D, X;
        scanf("%lld %lld %lld", &T, &D, &X);
        
        // Slope Trick を 更新.
        st.addL -= T - t;
        st.addR += T - t;
        if(D) st.addXsubA(X);
        else  st.addAsubX(X);
        
        // 前回分保存.
        t = T;
    }
    
    // 3. 出力.
    printf("%lld\n", st.minF);
    return 0;
    
}

100

// 解答不能.

// https://atcoder.jp/contests/abc217/editorial/2581

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

using PQ = priority_queue<LL, vector<LL>, greater<LL>>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

// Slope Trick.

// https://atcoder.jp/contests/abc217/editorial/2581

// https://maspypy.com/slope-trick-1-解説編

// -> 一部改変.

struct SlopeTrick{

PQ L; // 傾き 0以下で, 傾きの変化点全体の多重集合.

PQ R; // 傾き 0以上で, 傾きの変化点全体の多重集合.

LL addL, addR, minF;

SlopeTrick(int n){

addL = 0LL;

addR = 0LL;

minF = 0LL;

rep(i, n + 1) L.push(0LL);

rep(i, n + 1) R.push(0LL);

}

void pushLeft(LL x){

L.push(-x + addL);

}

void pushRight(LL x){

R.push(x - addR);

}

LL topLeft(){

return -L.top() + addL;

}

LL topRight(){

return R.top() + addR;

}

LL popLeft(){

LL ret = -L.top() + addL;

L.pop();

return ret;

}

LL popRight(){

LL ret = R.top() + addR;

R.pop();

return ret;

}

void addXsubA(LL a){

minF += (L.size() ? max(0LL, topLeft() - a) : 0LL);

pushLeft(a);

pushRight(popLeft());

}

void addAsubX(LL a){

minF += (R.size() ? max(0LL, a - topRight()) : 0LL);

pushRight(a);

pushLeft(popRight());

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. ゲームを進める.

SlopeTrick st(N);

LL t = 0;

rep(i, N){

// 今回分取得.

LL T, D, X;

scanf("%lld %lld %lld", &T, &D, &X);

// Slope Trick を更新.

st.addL -= T - t;

st.addR += T - t;

if(D) st.addXsubA(X);

else st.addAsubX(X);

// 前回分保存.

t = T;

}

// 3. 出力.

printf("%lld\n", st.minF);

return 0;

}

[入力例]
3
1 0 3
3 1 0
4 0 6

[出力例]
7
※AtCoderテストケースより

[入力例]
3
1 0 1
6 1 1
8 0 -1

[出力例]
0
※AtCoderテストケースより

[入力例]
5
1 0 1000000000
2 1 -1000000000
3 0 1000000000
4 1 -1000000000
5 0 1000000000

[出力例]
4999999997
※AtCoderテストケースより

[入力例]
7
1 0 3
3 1 -2
7 0 5
8 0 -1
12 1 -2
17 1 -3
20 0 6

[出力例]
11

※実際, 以下の動作をすると, 合計 11 の ダメージを受ける.
t =  1 (地点) +1 (ダメージ) +3 - 1    = +2
t =  3 (地点) -1 (ダメージ) -1 - (-2) = +1
t =  7 (地点) +3 (ダメージ) +5 - 3    = +2
t =  8 (地点) +2 (ダメージ) +2 >= -1 なので無し.
t = 12 (地点) -2 (ダメージ) -2 == -2 なので無し.
t = 17 (地点) -3 (ダメージ) -3 == -3 なので無し.
t = 20 (地点)  0 (ダメージ) +6 - 0    = +6

[入力例]
12
1 1 5
2 1 8
4 0 -6
7 1 10
10 1 -1
13 0 7
17 0 -2
19 1 8
23 0 9
25 1 -11
29 1 3
30 0 15

[出力例]
34

※実際, 以下の動作をすると, 合計 34 の ダメージを受ける.
t =  1 (地点) +1 (ダメージ) +1 <= +5  なので無し.
t =  2 (地点) +2 (ダメージ) +2 <= +8  なので無し.
t =  4 (地点) +4 (ダメージ) +4 >= -6  なので無し.
t =  7 (地点) +1 (ダメージ) +1 <= +10 なので無し.
t = 10 (地点)  0 (ダメージ)  0 - (-1)  = +1
t = 13 (地点) +3 (ダメージ) +7 - (+3)  = +4
t = 17 (地点) -1 (ダメージ) -1 >= -2 なので無し.
t = 19 (地点) +1 (ダメージ) +1 <= +8 なので無し.
t = 23 (地点) +1 (ダメージ) +9 - (+1)  = +8
t = 25 (地点) -1 (ダメージ) -1 - (-11) = +10
t = 29 (地点) +3 (ダメージ) +3 == +3 なので無し.
t = 30 (地点) +4 (ダメージ) +15 - (+4) = +11

[入力例]

1 0 3

3 1 0

4 0 6

[出力例]

※AtCoderテストケースより

[入力例]

1 0 1

6 1 1

8 0 -1

[出力例]

※AtCoderテストケースより

[入力例]

1 0 1000000000

2 1 -1000000000

3 0 1000000000

4 1 -1000000000

5 0 1000000000

[出力例]

4999999997

※AtCoderテストケースより

[入力例]

1 0 3

3 1 -2

7 0 5

8 0 -1

12 1 -2

17 1 -3

20 0 6

[出力例]

※実際, 以下の動作をすると, 合計 11 のダメージを受ける.

t = 1 (地点) +1 (ダメージ) +3 - 1 = +2

t = 3 (地点) -1 (ダメージ) -1 - (-2) = +1

t = 7 (地点) +3 (ダメージ) +5 - 3 = +2

t = 8 (地点) +2 (ダメージ) +2 >= -1 なので無し.

t = 12 (地点) -2 (ダメージ) -2 == -2 なので無し.

t = 17 (地点) -3 (ダメージ) -3 == -3 なので無し.

t = 20 (地点) 0 (ダメージ) +6 - 0 = +6

[入力例]

1 1 5

2 1 8

4 0 -6

7 1 10

10 1 -1

13 0 7

17 0 -2

19 1 8

23 0 9

25 1 -11

29 1 3

30 0 15

[出力例]

※実際, 以下の動作をすると, 合計 34 のダメージを受ける.

t = 1 (地点) +1 (ダメージ) +1 <= +5 なので無し.

t = 2 (地点) +2 (ダメージ) +2 <= +8 なので無し.

t = 4 (地点) +4 (ダメージ) +4 >= -6 なので無し.

t = 7 (地点) +1 (ダメージ) +1 <= +10 なので無し.

t = 10 (地点) 0 (ダメージ) 0 - (-1) = +1

t = 13 (地点) +3 (ダメージ) +7 - (+3) = +4

t = 17 (地点) -1 (ダメージ) -1 >= -2 なので無し.

t = 19 (地点) +1 (ダメージ) +1 <= +8 なので無し.

t = 23 (地点) +1 (ダメージ) +9 - (+1) = +8

t = 25 (地点) -1 (ダメージ) -1 - (-11) = +10

t = 29 (地点) +3 (ダメージ) +3 == +3 なので無し.

t = 30 (地点) +4 (ダメージ) +15 - (+4) = +11

■参照サイト
AtCoder Beginner Contest 217
slope trick (1) 解説編

2021年10月21日

C++ の動作確認をしてみた（５６０）

C++の練習を兼ねて, AtCoder Beginner Contest 223 の問題C (Doukasen) ～問題D (Restricted Permutation) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. トポロジカルソートの復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 223 解説の各リンクをご覧下さい.

■C++版プログラム(問題C／AC版).

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
double a[101010], b[101010], c[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    double t = 0.0, ans = 0.0;
    rep(i, N){
        scanf("%lf %lf", &a[i], &b[i]);
        c[i] = a[i] / b[i];
        t += c[i];
    }
    
    // 2. ぶつかる箇所は？
    t /= 2.0;
    rep(i, N){
        if(t >= c[i]){
            t -= c[i];
            ans += a[i];
        }else{
            ans += t * b[i];
            break;
        }
    }
    
    // 3. 出力.
    printf("%.15lf\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

double a[101010], b[101010], c[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

double t = 0.0, ans = 0.0;

rep(i, N){

scanf("%lf %lf", &a[i], &b[i]);

c[i] = a[i] / b[i];

t += c[i];

}

// 2. ぶつかる箇所は？

t /= 2.0;

rep(i, N){

if(t >= c[i]){

t -= c[i];

ans += a[i];

}else{

ans += t * b[i];

break;

}

// 3. 出力.

printf("%.15lf\n", ans);

return 0;

}

[入力例]
3
1 1
2 1
3 1

[出力例]
3.000000000000000
※AtCoderテストケースより

[入力例]
3
1 3
2 2
3 1

[出力例]
3.833333333333333
※AtCoderテストケースより

[入力例]
5
3 9
1 2
4 6
1 5
5 3

[出力例]
8.916666666666668
※AtCoderテストケースより

[入力例]
7
3 6
35 7
5 10
15 3
60 12
15 5
20 4

[出力例]
70.000000000000000

[入力例]
10
3 7
5 12
11 8
12 2
2 2
6 2
8 3
10 7
12 8
6 1

[出力例]
38.375000000000000

[入力例]
20
76 34
35 100
47 20
96 11
111 32
38 92
43 30
102 94
28 16
34 24
30 3
100 95
17 8
36 52
6 79
77 80
36 22
103 37
21 79
25 43

[出力例]
574.236966554499077

[入力例]

1 1

2 1

3 1

[出力例]

3.000000000000000

※AtCoderテストケースより

[入力例]

1 3

2 2

3 1

[出力例]

3.833333333333333

※AtCoderテストケースより

[入力例]

3 9

1 2

4 6

1 5

5 3

[出力例]

8.916666666666668

※AtCoderテストケースより

[入力例]

3 6

35 7

5 10

15 3

60 12

15 5

20 4

[出力例]

70.000000000000000

[入力例]

3 7

5 12

11 8

12 2

2 2

6 2

8 3

10 7

12 8

6 1

[出力例]

38.375000000000000

[入力例]

76 34

35 100

47 20

96 11

111 32

38 92

43 30

102 94

28 16

34 24

30 3

100 95

17 8

36 52

6 79

77 80

36 22

103 37

21 79

25 43

[出力例]

574.236966554499077

■C++版プログラム(問題D／AC版).

// 解き直し.
// https://atcoder.jp/contests/abc223/editorial/2777
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using PQ = priority_queue<int, vector<int>, greater<int>>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const int MAX = 202020;
int iDegree[MAX];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);   // 有向グラフ.
        iDegree[b]++; // 入次数.
    }
    
    // 2. 入次数ゼロの頂点は？
    PQ pq;
    rep(i, N) if(!iDegree[i]) pq.push(i);
    
    // 3. トポロジカルソート.
    // https://ja.wikipedia.org/wiki/トポロジカルソート
    vi S;
    while(!pq.empty()){
        // キューから取り出す.
        int u = pq.top();
        pq.pop();
        
        // S に u を 追加.
        S.pb(u);
        
        // 取り出した要素を処理.
        for(auto &v : G[u]){
            // u の 出力辺(u, v) を グラフから削除.
            iDegree[v]--;
            
            // 入次数ゼロの頂点は, キューに追加.
            if(!iDegree[v]) pq.push(v);
        }
    }
    
    // 4. 数列 P が存在しない.
    int l = S.size();
    if(l != N) puts("-1");
    
    // 5. 数列 P が存在する.
    if(l == N){
        rep(i, N){
            printf("%d", S[i] + 1);
            printf("%s", (i < N - 1) ? " " : "\n");
        }
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc223/editorial/2777

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using PQ = priority_queue<int, vector<int>, greater<int>>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

const int MAX = 202020;

int iDegree[MAX];

int main(){

// 1. 入力情報.

int N, M;

scanf("%d %d", &N, &M);

vvi G(N);

rep(i, M){

int a, b;

scanf("%d %d", &a, &b);

a--, b--;

G[a].pb(b); // 有向グラフ.

iDegree[b]++; // 入次数.

}

// 2. 入次数ゼロの頂点は？

PQ pq;

rep(i, N) if(!iDegree[i]) pq.push(i);

// 3. トポロジカルソート.

// https://ja.wikipedia.org/wiki/トポロジカルソート

vi S;

while(!pq.empty()){

// キューから取り出す.

int u = pq.top();

pq.pop();

// S に u を追加.

S.pb(u);

// 取り出した要素を処理.

for(auto &v : G[u]){

// u の出力辺(u, v) をグラフから削除.

iDegree[v]--;

// 入次数ゼロの頂点は, キューに追加.

if(!iDegree[v]) pq.push(v);

}

// 4. 数列 P が存在しない.

int l = S.size();

if(l != N) puts("-1");

// 5. 数列 P が存在する.

if(l == N){

rep(i, N){

printf("%d", S[i] + 1);

printf("%s", (i < N - 1) ? " " : "\n");

}

return 0;

}

[入力例]
4 3
2 1
3 4
2 4

[出力例]
2 1 3 4
※AtCoderテストケースより

[入力例]
2 3
1 2
1 2
2 1

[出力例]
-1
※AtCoderテストケースより

[入力例]
13 12
1 2
7 1
1 5
5 6
5 4
2 8
2 3
8 9
3 12
4 10
3 11
4 11

[出力例]
7 1 2 3 5 4 6 8 9 10 11 12 13

[入力例]
5 5
1 2
3 5
2 3
5 4
4 1

[出力例]
-1

[入力例]
7 7
5 1
7 1
1 3
1 6
1 2
2 4
6 4

[出力例]
5 7 1 2 3 6 4

[入力例]
25 24
16 7
1 7
20 7
7 9
7 3
3 21
3 10
3 25
3 6
6 4
10 22
10 15
10 14
25 5
25 8
8 24
24 2
24 23
4 13
13 18
9 11
9 12
12 19
11 17

[出力例]
1 16 20 7 3 6 4 9 10 11 12 13 14 15 17 18 19 21 22 25 5 8 24 2 23

[入力例]

4 3

2 1

3 4

2 4

[出力例]

2 1 3 4

※AtCoderテストケースより

[入力例]

2 3

1 2

2 1

[出力例]

-1

※AtCoderテストケースより

[入力例]

13 12

1 2

7 1

1 5

5 6

5 4

2 8

2 3

8 9

3 12

4 10

3 11

4 11

[出力例]

7 1 2 3 5 4 6 8 9 10 11 12 13

[入力例]

5 5

1 2

3 5

2 3

5 4

4 1

[出力例]

-1

[入力例]

7 7

5 1

7 1

1 3

1 6

1 2

2 4

6 4

[出力例]

5 7 1 2 3 6 4

[入力例]

25 24

16 7

1 7

20 7

7 9

7 3

3 21

3 10

3 25

3 6

6 4

10 22

10 15

10 14

25 5

25 8

8 24

24 2

24 23

4 13

13 18

9 11

9 12

12 19

11 17

[出力例]

1 16 20 7 3 6 4 9 10 11 12 13 14 15 17 18 19 21 22 25 5 8 24 2 23

■参照サイト
AtCoder Beginner Contest 223

2021年10月19日

C++ の動作確認をしてみた（５５９）

C++の練習を兼ねて, AtCoder Beginner Contest 221 の問題H (Count Multiset) を解いてみた.

■感想.
1. 問題Hは, 方針が見えなかったので, 解説プログラムを参考に提出して, ようやく, AC版に到達出来た.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. M個前の状態を, どのように考慮するかを, 正しく実装出来なかったので, 一つのパターンとして, とりあえず暗記してみる.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 221 解説の各リンクをご覧下さい.

■C++版プログラム(問題H／AC版).

// 解答不能.
// https://atcoder.jp/contests/abc221/editorial/2719
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 998244353;
LL dp[5050][5050], dpSum[5050];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    
    // 2. dp更新(解説通り).
    // ex.
    // N = 11, M = 5 の 場合.
    // -> 以下のようなイメージで, 更新.
    // f(1,  11) = 1.
    // f(2,  11) = f(1, 9) + f(1, 7) + f(1, 5) + f(1, 3) + f(1, 1) 
    //           = 1 + 1 + 1 + 1 + 1 
    //           = 5.
    // f(3,  11) = f(2, 8) + f(2, 5) + f(2, 2) + 
    //             f(1, 8) + f(1, 5) + f(1, 2) 
    //           = 4 + 2 + 1 + 1 + 1 + 1 
    //           = 10.
    // f(4,  11) = f(3, 7) + f(3, 3) + 
    //             f(2, 7) + f(2, 3) + 
    //             f(1, 7) + f(1, 3) 
    //           = 4 + 1 + 3 + 1 + 1 + 1 
    //           = 11.
    // f(5,  11) = f(4, 6) + f(4, 1) + 
    //             f(3, 6) + f(3, 1) + 
    //             f(2, 6) + f(2, 1) + 
    //             f(1, 6) + f(1, 1) 
    //           = 2 + 0 + 3 + 0 + 3 + 0 + 1 + 1 
    //           = 10.
    // f(6,  11) = f(5, 5) + 
    //             f(4, 5) + 
    //             f(3, 5) + 
    //             f(2, 5) + 
    //             f(1, 5) 
    //           = 1 + 1 + 2 + 2 + 1 
    //           = 7.
    // f(7,  11) = f(6, 4) + 
    //             f(5, 4) + 
    //             f(4, 4) + 
    //             f(3, 4) + 
    //             f(2, 4) 
    //           = 0 + 0 + 1 + 1 + 2 
    //           = 4.
    // f(8,  11) = f(7, 3) + 
    //             f(6, 3) + 
    //             f(5, 3) + 
    //             f(4, 3) + 
    //             f(3, 3) 
    //           = 0 + 0 + 0 + 0 + 1 
    //           = 1.
    // f(9,  11) = 0.
    // f(10, 11) = 0.
    // f(11, 11) = 0.
    // -> 以下の dp更新式は, 解説通り.
    dp[0][0] = 1;
    dpSum[0] = 1;
    repx(x, 1, N + 1){
        // dp更新.
        repx(y, x, N + 1){
            dp[x][y] = dpSum[y - x] + dp[x][y - x];
            dp[x][y] %= MOD;
        }
        
        // dp累積和.
        rep(y, N + 1){
            dpSum[y] += dp[x][y];
            dpSum[y] %= MOD;
            if(x >= M){
                dpSum[y] += MOD - dp[x - M][y];
                dpSum[y] %= MOD;
            }
        }
    }
    // rep(i, 20){
    //     rep(j, 20) printf("%lld ", dp[i][j]);
    //     puts("");
    // }
    // rep(i, 20){
    //     rep(j, 20) printf("%lld ", dpSum[i][j]);
    //     puts("");
    // }
    
    // 3. 出力.
    repx(i, 1, N + 1) printf("%lld\n", dp[i][N]);
    return 0;
    
}

100

// 解答不能.

// https://atcoder.jp/contests/abc221/editorial/2719

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

const LL MOD = 998244353;

LL dp[5050][5050], dpSum[5050];

int main(){

// 1. 入力情報.

int N, M;

scanf("%d %d", &N, &M);

// 2. dp更新(解説通り).

// ex.

// N = 11, M = 5 の場合.

// -> 以下のようなイメージで, 更新.

// f(1, 11) = 1.

// f(2, 11) = f(1, 9) + f(1, 7) + f(1, 5) + f(1, 3) + f(1, 1)

// = 1 + 1 + 1 + 1 + 1

// = 5.

// f(3, 11) = f(2, 8) + f(2, 5) + f(2, 2) +

// f(1, 8) + f(1, 5) + f(1, 2)

// = 4 + 2 + 1 + 1 + 1 + 1

// = 10.

// f(4, 11) = f(3, 7) + f(3, 3) +

// f(2, 7) + f(2, 3) +

// f(1, 7) + f(1, 3)

// = 4 + 1 + 3 + 1 + 1 + 1

// = 11.

// f(5, 11) = f(4, 6) + f(4, 1) +

// f(3, 6) + f(3, 1) +

// f(2, 6) + f(2, 1) +

// f(1, 6) + f(1, 1)

// = 2 + 0 + 3 + 0 + 3 + 0 + 1 + 1

// = 10.

// f(6, 11) = f(5, 5) +

// f(4, 5) +

// f(3, 5) +

// f(2, 5) +

// f(1, 5)

// = 1 + 1 + 2 + 2 + 1

// = 7.

// f(7, 11) = f(6, 4) +

// f(5, 4) +

// f(4, 4) +

// f(3, 4) +

// f(2, 4)

// = 0 + 0 + 1 + 1 + 2

// = 4.

// f(8, 11) = f(7, 3) +

// f(6, 3) +

// f(5, 3) +

// f(4, 3) +

// f(3, 3)

// = 0 + 0 + 0 + 0 + 1

// = 1.

// f(9, 11) = 0.

// f(10, 11) = 0.

// f(11, 11) = 0.

// -> 以下の dp更新式は, 解説通り.

dp[0][0] = 1;

dpSum[0] = 1;

repx(x, 1, N + 1){

// dp更新.

repx(y, x, N + 1){

dp[x][y] = dpSum[y - x] + dp[x][y - x];

dp[x][y] %= MOD;

}

// dp累積和.

rep(y, N + 1){

dpSum[y] += dp[x][y];

dpSum[y] %= MOD;

if(x >= M){

dpSum[y] += MOD - dp[x - M][y];

dpSum[y] %= MOD;

}

// rep(i, 20){

// rep(j, 20) printf("%lld ", dp[i][j]);

// puts("");

// }

// rep(i, 20){

// rep(j, 20) printf("%lld ", dpSum[i][j]);

// puts("");

// }

// 3. 出力.

repx(i, 1, N + 1) printf("%lld\n", dp[i][N]);

return 0;

}

[入力例]
4 2

[出力例]
1
2
1
0
※AtCoderテストケースより

[入力例]
7 7

[出力例]
1
3
4
3
2
1
1
※AtCoderテストケースより

[入力例]
5 3

[出力例]
1
2
2
1
0

[入力例]
4 3

[出力例]
1
2
1
0

[入力例]
7 3

[出力例]
1
3
4
3
1
0
0

[入力例]
11 5

[出力例]
1
5
10
11
10
7
4
1
0
0
0

[入力例]
12 8

[出力例]
1
6
12
15
13
11
7
5
3
1
0
0

[入力例]
17 11

[出力例]
1
8
24
39
47
44
38
29
22
15
11
7
4
1
0
0
0

[入力例]
21 20

[出力例]
1
10
37
72
101
110
105
89
73
55
42
30
22
15
11
7
5
3
2
1
0

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

[入力例]

4 2

[出力例]

※AtCoderテストケースより

[入力例]

7 7

[出力例]

※AtCoderテストケースより

[入力例]

5 3

[出力例]

[入力例]

4 3

[出力例]

[入力例]

7 3

[出力例]

[入力例]

11 5

[出力例]

[入力例]

12 8

[出力例]

[入力例]

17 11

[出力例]

[入力例]

21 20

[出力例]

101

110

105

■参照サイト
AtCoder Beginner Contest 221

2021年10月16日

C++ の動作確認をしてみた（５５８）

C++の練習を兼ねて, AtCoder Grand Contest 031 の問題C (Differ by 1 Bit) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 再帰処理の実装を訓練出来たので良かったと思う.
3. 個人的には, 解説の方針で, 順列の抽出を実現可能であることに, 不思議な印象を受けたとともに, 非常に面白く思った.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Grand Contest 031 解説をご覧下さい.

■C++版プログラム(問題C／AC版).

// 解き直し.
// https://img.atcoder.jp/agc031/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vs = vector<string>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int N, A, B;
    scanf("%d %d %d", &N, &A, &B);
    
    // 2. 例外.
    int aCount = __builtin_popcount(A);
    int bCount = __builtin_popcount(B);
    if((aCount + bCount) % 2 == 0){
        puts("No");
        return 0;
    }
    
    // 3. 準備.
    // 3-1. 2 の 冪乗. 
    vi cPow;
    cPow.pb(1);
    rep(i, N + 1){
        int p = cPow.back();
        p <<= 1;
        cPow.pb(p);
    }
    
    // 3-2. 2進数表示.
    string sa = "", sb = "";
    rep(i, N) sa += (A & (1 << (N - 1 - i))) ? "1" : "0";
    rep(i, N) sb += (B & (1 << (N - 1 - i))) ? "1" : "0";
    // printf("sa=%s sb=%s\n", sa.c_str(), sb.c_str());
    
    // 4. 順列 P(解説通り).
    auto dfs = [&](auto self, string aCur, string bCur) -> vs{
        // 4-1. 終了条件.
        int l = aCur.size();
        if(l == 1){
            vs ret;
            ret.pb(aCur);
            ret.pb(bCur);
            return ret;
        }
        // printf("aCur=%s bCur=%s\n", aCur.c_str(), bCur.c_str());
        
        // 4-2. A, B で, 状態が異なる bit の 位置は？
        int x = -1;
        rep(i, l){
            if(aCur[i] != bCur[i]){
                x = i;
                break;
            }
        }
        // printf("x=%d\n", x);
        assert(x != -1);
        
        // 4-3. A', B'.
        string aNex = "", bNex = "";
        rep(i, l) if(i != x) aNex.pb(aCur[i]);
        rep(i, l) if(i != x) bNex.pb(bCur[i]);
        
        // 4-4. C.
        string cNex = aNex;
        cNex[0] = ((cNex[0] - '0' + 1) % 2) + '0';
        // printf("aNex=%s bNex=%s cNex=%s\n", aNex.c_str(), bNex.c_str(), cNex.c_str());
        
        // 4-5. 順列 Q, R.
        vs Q = self(self, aNex, cNex);
        vs R = self(self, cNex, bNex);
        
        // 4-6. 順列 P.
        // 前半.
        vs P;
        for(auto &q : Q){
            string s = "";
            int at = 0;
            for(auto &c : q){
                // x bit目 は, A の x bit目.
                if(at == x) s.pb(aCur[x]);
                s.pb(c);
                at++;
            }
            
            // A の x bit目が, 一番最後に追加されるケース.
            if(at == x) s.pb(aCur[x]);
            
            // 保存.
            P.pb(s);
        }
        
        // 後半.
        for(auto &r : R){
            // P を 構成.
            string s = "";
            int at = 0;
            for(auto &c : r){
                // x bit目 は, B の x bit目.
                if(at == x) s.pb(bCur[x]);
                s.pb(c);
                at++;
            }
            
            // B の x bit目が, 一番最後に追加されるケース.
            if(at == x) s.pb(bCur[x]);
            
            // 保存.
            P.pb(s);
        }
        
        // 4-7. 終了.
        return P;
    };
    vs ans = dfs(dfs, sa, sb);
    
    // 5. 出力.
    puts("Yes");
    rep(i, 1 << N){
        int t = 0;
        rep(j, N) if(ans[i][j] == '1') t += cPow[N - 1 - j];
        printf("%d", t);
        printf("%s", (i < (1 << N) - 1) ? " " : "\n");
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

// 解き直し.

// https://img.atcoder.jp/agc031/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vs = vector<string>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

int main(){

// 1. 入力情報.

int N, A, B;

scanf("%d %d %d", &N, &A, &B);

// 2. 例外.

int aCount = __builtin_popcount(A);

int bCount = __builtin_popcount(B);

if((aCount + bCount) % 2 == 0){

puts("No");

return 0;

}

// 3. 準備.

// 3-1. 2 の冪乗.

vi cPow;

cPow.pb(1);

rep(i, N + 1){

int p = cPow.back();

p <<= 1;

cPow.pb(p);

}

// 3-2. 2進数表示.

string sa = "", sb = "";

rep(i, N) sa += (A & (1 << (N - 1 - i))) ? "1" : "0";

rep(i, N) sb += (B & (1 << (N - 1 - i))) ? "1" : "0";

// printf("sa=%s sb=%s\n", sa.c_str(), sb.c_str());

// 4. 順列 P(解説通り).

auto dfs = [&](auto self, string aCur, string bCur) -> vs{

// 4-1. 終了条件.

int l = aCur.size();

if(l == 1){

vs ret;

ret.pb(aCur);

ret.pb(bCur);

return ret;

}

// printf("aCur=%s bCur=%s\n", aCur.c_str(), bCur.c_str());

// 4-2. A, B で, 状態が異なる bit の位置は？

int x = -1;

rep(i, l){

if(aCur[i] != bCur[i]){

x = i;

break;

}

// printf("x=%d\n", x);

assert(x != -1);

// 4-3. A', B'.

string aNex = "", bNex = "";

rep(i, l) if(i != x) aNex.pb(aCur[i]);

rep(i, l) if(i != x) bNex.pb(bCur[i]);

// 4-4. C.

string cNex = aNex;

cNex[0] = ((cNex[0] - '0' + 1) % 2) + '0';

// printf("aNex=%s bNex=%s cNex=%s\n", aNex.c_str(), bNex.c_str(), cNex.c_str());

// 4-5. 順列 Q, R.

vs Q = self(self, aNex, cNex);

vs R = self(self, cNex, bNex);

// 4-6. 順列 P.

// 前半.

vs P;

for(auto &q : Q){

string s = "";

int at = 0;

for(auto &c : q){

// x bit目は, A の x bit目.

if(at == x) s.pb(aCur[x]);

s.pb(c);

at++;

}

// A の x bit目が, 一番最後に追加されるケース.

if(at == x) s.pb(aCur[x]);

// 保存.

P.pb(s);

}

// 後半.

for(auto &r : R){

// P を構成.

string s = "";

int at = 0;

for(auto &c : r){

// x bit目は, B の x bit目.

if(at == x) s.pb(bCur[x]);

s.pb(c);

at++;

}

// B の x bit目が, 一番最後に追加されるケース.

if(at == x) s.pb(bCur[x]);

// 保存.

P.pb(s);

}

// 4-7. 終了.

return P;

};

vs ans = dfs(dfs, sa, sb);

// 5. 出力.

puts("Yes");

rep(i, 1 << N){

int t = 0;

rep(j, N) if(ans[i][j] == '1') t += cPow[N - 1 - j];

printf("%d", t);

printf("%s", (i < (1 << N) - 1) ? " " : "\n");

}

return 0;

}

[入力例]
2 1 3

[出力例]
YES
1 0 2 3
※AtCoderのテストケースより

[入力例]
3 2 1

[出力例]
NO
※AtCoderのテストケースより

[入力例]
1 0 1

[出力例]
Yes
0 1

[入力例]
1 1 0

[出力例]
Yes
1 0

[入力例]
3 2 3

[出力例]
Yes
2 0 4 6 7 5 1 3

[入力例]
4 12 7

[出力例]
Yes
12 13 15 14 10 11 9 8 0 1 3 2 6 4 5 7

[入力例]
5 6 11

[出力例]
Yes
6 7 5 4 0 1 3 2 18 19 17 16 20 21 23 22 30 31 29 28 24 25 27 26 10 8 12 14 15 13 9 11

[入力例]
7 26 45

[出力例]
Yes
26 27 25 24 28 29 31 30 22 23 21 20 16 17 19 18 2 3 1 0 4 5 7 6 14 15 13 12 8 9 11 10 74 75 73 72 76 77 79 78 70 71 69 68 64 65 67 66 82 83 81 80 84 85 87 86 94 95 93 92 88 89 91 90 122 123 121 120 124 125 127 126 118 119 117 116 112 113 115 114 98 99 97 96 100 101 103 102 110 111 109 108 104 105 107 106 42 43 41 40 32 33 35 34 50 51 49 48 56 57 59 58 62 63 61 60 52 53 55 54 38 39 37 36 44 46 47 45

[入力例]
10 314 159

[出力例]
Yes
314 315 313 312 316 317 319 318 310 311 309 308 304 305 307 306 290 291 289 288 292 293 295 294 302 303 301 300 296 297 299 298 266 267 265 264 268 269 271 270 262 263 261 260 256 257 259 258 274 275 273 272 276 277 279 278 286 287 285 284 280 281 283 282 346 347 345 344 348 349 351 350 342 343 341 340 336 337 339 338 322 323 321 320 324 325 327 326 334 335 333 332 328 329 331 330 362 363 361 360 364 365 367 366 358 359 357 356 352 353 355 354 370 371 369 368 372 373 375 374 382 383 381 380 376 377 379 378 506 507 505 504 508 509 511 510 502 503 501 500 496 497 499 498 482 483 481 480 484 485 487 486 494 495 493 492 488 489 491 490 458 459 457 456 460 461 463 462 454 455 453 452 448 449 451 450 466 467 465 464 468 469 471 470 478 479 477 476 472 473 475 474 410 411 409 408 412 413 415 414 406 407 405 404 400 401 403 402 386 387 385 384 388 389 391 390 398 399 397 396 392 393 395 394 426 427 425 424 428 429 431 430 422 423 421 420 416 417 419 418 434 435 433 432 436 437 439 438 446 447 445 444 440 441 443 442 954 955 953 952 956 957 959 958 950 951 949 948 944 945 947 946 930 931 929 928 932 933 935 934 942 943 941 940 936 937 939 938 906 907 905 904 908 909 911 910 902 903 901 900 896 897 899 898 914 915 913 912 916 917 919 918 926 927 925 924 920 921 923 922 986 987 985 984 988 989 991 990 982 983 981 980 976 977 979 978 962 963 961 960 964 965 967 966 974 975 973 972 968 969 971 970 1002 1003 1001 1000 1004 1005 1007 1006 998 999 997 996 992 993 995 994 1010 1011 1009 1008 1012 1013 1015 1014 1022 1023 1021 1020 1016 1017 1019 1018 890 891 889 888 892 893 895 894 886 887 885 884 880 881 883 882 866 867 865 864 868 869 871 870 878 879 877 876 872 873 875 874 842 843 841 840 844 845 847 846 838 839 837 836 832 833 835 834 850 851 849 848 852 853 855 854 862 863 861 860 856 857 859 858 794 795 793 792 796 797 799 798 790 791 789 788 784 785 787 786 770 771 769 768 772 773 775 774 782 783 781 780 776 777 779 778 810 811 809 808 812 813 815 814 806 807 805 804 800 801 803 802 818 819 817 816 820 821 823 822 830 831 829 828 824 825 827 826 570 571 569 568 572 573 575 574 566 567 565 564 560 561 563 562 546 547 545 544 548 549 551 550 558 559 557 556 552 553 555 554 522 523 521 520 524 525 527 526 518 519 517 516 512 513 515 514 530 531 529 528 532 533 535 534 542 543 541 540 536 537 539 538 602 603 601 600 604 605 607 606 598 599 597 596 592 593 595 594 578 579 577 576 580 581 583 582 590 591 589 588 584 585 587 586 618 619 617 616 620 621 623 622 614 615 613 612 608 609 611 610 626 627 625 624 628 629 631 630 638 639 637 636 632 633 635 634 762 763 761 760 764 765 767 766 758 759 757 756 752 753 755 754 738 739 737 736 740 741 743 742 750 751 749 748 744 745 747 746 714 715 713 712 716 717 719 718 710 711 709 708 704 705 707 706 722 723 721 720 724 725 727 726 734 735 733 732 728 729 731 730 666 667 665 664 668 669 671 670 662 663 661 660 656 657 659 658 642 643 641 640 644 645 647 646 654 655 653 652 648 649 651 650 682 683 681 680 684 685 687 686 678 679 677 676 672 673 675 674 690 691 689 688 692 693 695 694 702 703 701 700 696 697 699 698 186 187 185 184 188 189 191 190 182 183 181 180 176 177 179 178 162 163 161 160 164 165 167 166 174 175 173 172 168 169 171 170 234 235 233 232 236 237 239 238 230 231 229 228 224 225 227 226 242 243 241 240 244 245 247 246 254 255 253 252 248 249 251 250 122 123 121 120 124 125 127 126 118 119 117 116 112 113 115 114 98 99 97 96 100 101 103 102 110 111 109 108 104 105 107 106 42 43 41 40 44 45 47 46 38 39 37 36 32 33 35 34 50 51 49 48 52 53 55 54 62 63 61 60 56 57 59 58 26 27 25 24 28 29 31 30 22 23 21 20 16 17 19 18 2 3 1 0 4 5 7 6 14 15 13 12 8 9 11 10 74 75 73 72 76 77 79 78 70 71 69 68 64 65 67 66 82 83 81 80 84 85 87 86 94 95 93 92 88 89 91 90 218 219 217 216 220 221 223 222 214 215 213 212 208 209 211 210 194 195 193 192 196 197 199 198 206 207 205 204 200 201 203 202 138 139 137 136 140 141 143 142 134 135 133 132 128 129 131 130 146 147 145 144 148 149 151 150 158 156 152 154 155 153 157 159

[入力例]
13 3605 5512

[出力例]
Yes
3605 3604 3606 3607 3603 3602 3600 3601 3609 3608 3610 3611 3615 3614 3612 3613 3597 3596 3598 3599 3595 3594 3592 3593 3585 3584 3586 3587 3591 3590 3588 3589 3621 3620 3622 3623 3619 3618 3616 3617 3625 3624 3626 3627 3631 3630 3628 3629 3645 3644 3646 3647 3643 3642 3640 3641 3633 3632 3634 3635 3639 3638 3636 3637 3701 3700 3702 3703 3699 3698 3696 3697 3705 3704 3706 3707 3711 3710 3708 3709 3693 3692 3694 3695 3691 3690 3688 3689 3681 3680 3682 3683 3687 3686 3684 3685 3653 3652 3654 3655 3651 3650 3648 3649 3657 3656 3658 3659 3663 3662 3660 3661 3677 3676 3678 3679 3675 3674 3672 3673 3665 3664 3666 3667 3671 3670 3668 3669 3797 3796 3798 3799 3795 3794 3792 3793 3801 3800 3802 3803 3807 3806 3804 3805 3789 3788 3790 3791 3787 3786 3784 3785 3777 3776 3778 3779 3783 3782 3780 3781 3813 3812 3814 3815 3811 3810 3808 3809 3817 3816 3818 3819 3823 3822 3820 3821 3837 3836 3838 3839 3835 3834 3832 3833 3825 3824 3826 3827 3831 3830 3828 3829 3765 3764 3766 3767 3763 3762 3760 3761 3769 3768 3770 3771 3775 3774 3772 3773 3757 3756 3758 3759 3755 3754 3752 3753 3745 3744 3746 3747 3751 3750 3748 3749 3717 3716 3718 3719 3715 3714 3712 3713 3721 3720 3722 3723 3727 3726 3724 3725 3741 3740 3742 3743 3739 3738 3736 3737 3729 3728 3730 3731 3735 3734 3732 3733 3989 3988 3990 3991 3987 3986 3984 3985 3993 3992 3994 3995 3999 3998 3996 3997 3981 3980 3982 3983 3979 3978 3976 3977 3969 3968 3970 3971 3975 3974 3972 3973 4005 4004 4006 4007 4003 4002 4000 4001 4009 4008 4010 4011 4015 4014 4012 4013 4029 4028 4030 4031 4027 4026 4024 4025 4017 4016 4018 4019 4023 4022 4020 4021 4085 4084 4086 4087 4083 4082 4080 4081 4089 4088 4090 4091 4095 4094 4092 4093 4077 4076 4078 4079 4075 4074 4072 4073 4065 4064 4066 4067 4071 4070 4068 4069 4037 4036 4038 4039 4035 4034 4032 4033 4041 4040 4042 4043 4047 4046 4044 4045 4061 4060 4062 4063 4059 4058 4056 4057 4049 4048 4050 4051 4055 4054 4052 4053 3925 3924 3926 3927 3923 3922 3920 3921 3929 3928 3930 3931 3935 3934 3932 3933 3917 3916 3918 3919 3915 3914 3912 3913 3905 3904 3906 3907 3911 3910 3908 3909 3941 3940 3942 3943 3939 3938 3936 3937 3945 3944 3946 3947 3951 3950 3948 3949 3965 3964 3966 3967 3963 3962 3960 3961 3953 3952 3954 3955 3959 3958 3956 3957 3893 3892 3894 3895 3891 3890 3888 3889 3897 3896 3898 3899 3903 3902 3900 3901 3885 3884 3886 3887 3883 3882 3880 3881 3873 3872 3874 3875 3879 3878 3876 3877 3845 3844 3846 3847 3843 3842 3840 3841 3849 3848 3850 3851 3855 3854 3852 3853 3869 3868 3870 3871 3867 3866 3864 3865 3857 3856 3858 3859 3863 3862 3860 3861 3349 3348 3350 3351 3347 3346 3344 3345 3353 3352 3354 3355 3359 3358 3356 3357 3341 3340 3342 3343 3339 3338 3336 3337 3329 3328 3330 3331 3335 3334 3332 3333 3365 3364 3366 3367 3363 3362 3360 3361 3369 3368 3370 3371 3375 3374 3372 3373 3389 3388 3390 3391 3387 3386 3384 3385 3377 3376 3378 3379 3383 3382 3380 3381 3445 3444 3446 3447 3443 3442 3440 3441 3449 3448 3450 3451 3455 3454 3452 3453 3437 3436 3438 3439 3435 3434 3432 3433 3425 3424 3426 3427 3431 3430 3428 3429 3397 3396 3398 3399 3395 3394 3392 3393 3401 3400 3402 3403 3407 3406 3404 3405 3421 3420 3422 3423 3419 3418 3416 3417 3409 3408 3410 3411 3415 3414 3412 3413 3541 3540 3542 3543 3539 3538 3536 3537 3545 3544 3546 3547 3551 3550 3548 3549 3533 3532 3534 3535 3531 3530 3528 3529 3521 3520 3522 3523 3527 3526 3524 3525 3557 3556 3558 3559 3555 3554 3552 3553 3561 3560 3562 3563 3567 3566 3564 3565 3581 3580 3582 3583 3579 3578 3576 3577 3569 3568 3570 3571 3575 3574 3572 3573 3509 3508 3510 3511 3507 3506 3504 3505 3513 3512 3514 3515 3519 3518 3516 3517 3501 3500 3502 3503 3499 3498 3496 3497 3489 3488 3490 3491 3495 3494 3492 3493 3461 3460 3462 3463 3459 3458 3456 3457 3465 3464 3466 3467 3471 3470 3468 3469 3485 3484 3486 3487 3483 3482 3480 3481 3473 3472 3474 3475 3479 3478 3476 3477 3221 3220 3222 3223 3219 3218 3216 3217 3225 3224 3226 3227 3231 3230 3228 3229 3213 3212 3214 3215 3211 3210 3208 3209 3201 3200 3202 3203 3207 3206 3204 3205 3237 3236 3238 3239 3235 3234 3232 3233 3241 3240 3242 3243 3247 3246 3244 3245 3261 3260 3262 3263 3259 3258 3256 3257 3249 3248 3250 3251 3255 3254 3252 3253 3317 3316 3318 3319 3315 3314 3312 3313 3321 3320 3322 3323 3327 3326 3324 3325 3309 3308 3310 3311 3307 3306 3304 3305 3297 3296 3298 3299 3303 3302 3300 3301 3269 3268 3270 3271 3267 3266 3264 3265 3273 3272 3274 3275 3279 3278 3276 3277 3293 3292 3294 3295 3291 3290 3288 3289 3281 3280 3282 3283 3287 3286 3284 3285 3157 3156 3158 3159 3155 3154 3152 3153 3161 3160 3162 3163 3167 3166 3164 3165 3149 3148 3150 3151 3147 3146 3144 3145 3137 3136 3138 3139 3143 3142 3140 3141 3173 3172 3174 3175 3171 3170 3168 3169 3177 3176 3178 3179 3183 3182 3180 3181 3197 3196 3198 3199 3195 3194 3192 3193 3185 3184 3186 3187 3191 3190 3188 3189 3125 3124 3126 3127 3123 3122 3120 3121 3129 3128 3130 3131 3135 3134 3132 3133 3117 3116 3118 3119 3115 3114 3112 3113 3105 3104 3106 3107 3111 3110 3108 3109 3077 3076 3078 3079 3075 3074 3072 3073 3081 3080 3082 3083 3087 3086 3084 3085 3101 3100 3102 3103 3099 3098 3096 3097 3089 3088 3090 3091 3095 3094 3092 3093 2069 2068 2070 2071 2067 2066 2064 2065 2073 2072 2074 2075 2079 2078 2076 2077 2061 2060 2062 2063 2059 2058 2056 2057 2049 2048 2050 2051 2055 2054 2052 2053 2085 2084 2086 2087 2083 2082 2080 2081 2089 2088 2090 2091 2095 2094 2092 2093 2109 2108 2110 2111 2107 2106 2104 2105 2097 2096 2098 2099 2103 2102 2100 2101 2165 2164 2166 2167 2163 2162 2160 2161 2169 2168 2170 2171 2175 2174 2172 2173 2157 2156 2158 2159 2155 2154 2152 2153 2145 2144 2146 2147 2151 2150 2148 2149 2117 2116 2118 2119 2115 2114 2112 2113 2121 2120 2122 2123 2127 2126 2124 2125 2141 2140 2142 2143 2139 2138 2136 2137 2129 2128 2130 2131 2135 2134 2132 2133 2261 2260 2262 2263 2259 2258 2256 2257 2265 2264 2266 2267 2271 2270 2268 2269 2253 2252 2254 2255 2251 2250 2248 2249 2241 2240 2242 2243 2247 2246 2244 2245 2277 2276 2278 2279 2275 2274 2272 2273 2281 2280 2282 2283 2287 2286 2284 2285 2301 2300 2302 2303 2299 2298 2296 2297 2289 2288 2290 2291 2295 2294 2292 2293 2229 2228 2230 2231 2227 2226 2224 2225 2233 2232 2234 2235 2239 2238 2236 2237 2221 2220 2222 2223 2219 2218 2216 2217 2209 2208 2210 2211 2215 2214 2212 2213 2181 2180 2182 2183 2179 2178 2176 2177 2185 2184 2186 2187 2191 2190 2188 2189 2205 2204 2206 2207 2203 2202 2200 2201 2193 2192 2194 2195 2199 2198 2196 2197 2453 2452 2454 2455 2451 2450 2448 2449 2457 2456 2458 2459 2463 2462 2460 2461 2445 2444 2446 2447 2443 2442 2440 2441 2433 2432 2434 2435 2439 2438 2436 2437 2469 2468 2470 2471 2467 2466 2464 2465 2473 2472 2474 2475 2479 2478 2476 2477 2493 2492 2494 2495 2491 2490 2488 2489 2481 2480 2482 2483 2487 2486 2484 2485 2549 2548 2550 2551 2547 2546 2544 2545 2553 2552 2554 2555 2559 2558 2556 2557 2541 2540 2542 2543 2539 2538 2536 2537 2529 2528 2530 2531 2535 2534 2532 2533 2501 2500 2502 2503 2499 2498 2496 2497 2505 2504 2506 2507 2511 2510 2508 2509 2525 2524 2526 2527 2523 2522 2520 2521 2513 2512 2514 2515 2519 2518 2516 2517 2389 2388 2390 2391 2387 2386 2384 2385 2393 2392 2394 2395 2399 2398 2396 2397 2381 2380 2382 2383 2379 2378 2376 2377 2369 2368 2370 2371 2375 2374 2372 2373 2405 2404 2406 2407 2403 2402 2400 2401 2409 2408 2410 2411 2415 2414 2412 2413 2429 2428 2430 2431 2427 2426 2424 2425 2417 2416 2418 2419 2423 2422 2420 2421 2357 2356 2358 2359 2355 2354 2352 2353 2361 2360 2362 2363 2367 2366 2364 2365 2349 2348 2350 2351 2347 2346 2344 2345 2337 2336 2338 2339 2343 2342 2340 2341 2309 2308 2310 2311 2307 2306 2304 2305 2313 2312 2314 2315 2319 2318 2316 2317 2333 2332 2334 2335 2331 2330 2328 2329 2321 2320 2322 2323 2327 2326 2324 2325 2837 2836 2838 2839 2835 2834 2832 2833 2841 2840 2842 2843 2847 2846 2844 2845 2829 2828 2830 2831 2827 2826 2824 2825 2817 2816 2818 2819 2823 2822 2820 2821 2853 2852 2854 2855 2851 2850 2848 2849 2857 2856 2858 2859 2863 2862 2860 2861 2877 2876 2878 2879 2875 2874 2872 2873 2865 2864 2866 2867 2871 2870 2868 2869 2933 2932 2934 2935 2931 2930 2928 2929 2937 2936 2938 2939 2943 2942 2940 2941 2925 2924 2926 2927 2923 2922 2920 2921 2913 2912 2914 2915 2919 2918 2916 2917 2885 2884 2886 2887 2883 2882 2880 2881 2889 2888 2890 2891 2895 2894 2892 2893 2909 2908 2910 2911 2907 2906 2904 2905 2897 2896 2898 2899 2903 2902 2900 2901 3029 3028 3030 3031 3027 3026 3024 3025 3033 3032 3034 3035 3039 3038 3036 3037 3021 3020 3022 3023 3019 3018 3016 3017 3009 3008 3010 3011 3015 3014 3012 3013 3045 3044 3046 3047 3043 3042 3040 3041 3049 3048 3050 3051 3055 3054 3052 3053 3069 3068 3070 3071 3067 3066 3064 3065 3057 3056 3058 3059 3063 3062 3060 3061 2997 2996 2998 2999 2995 2994 2992 2993 3001 3000 3002 3003 3007 3006 3004 3005 2989 2988 2990 2991 2987 2986 2984 2985 2977 2976 2978 2979 2983 2982 2980 2981 2949 2948 2950 2951 2947 2946 2944 2945 2953 2952 2954 2955 2959 2958 2956 2957 2973 2972 2974 2975 2971 2970 2968 2969 2961 2960 2962 2963 2967 2966 2964 2965 2709 2708 2710 2711 2707 2706 2704 2705 2713 2712 2714 2715 2719 2718 2716 2717 2701 2700 2702 2703 2699 2698 2696 2697 2689 2688 2690 2691 2695 2694 2692 2693 2725 2724 2726 2727 2723 2722 2720 2721 2729 2728 2730 2731 2735 2734 2732 2733 2749 2748 2750 2751 2747 2746 2744 2745 2737 2736 2738 2739 2743 2742 2740 2741 2805 2804 2806 2807 2803 2802 2800 2801 2809 2808 2810 2811 2815 2814 2812 2813 2797 2796 2798 2799 2795 2794 2792 2793 2785 2784 2786 2787 2791 2790 2788 2789 2757 2756 2758 2759 2755 2754 2752 2753 2761 2760 2762 2763 2767 2766 2764 2765 2781 2780 2782 2783 2779 2778 2776 2777 2769 2768 2770 2771 2775 2774 2772 2773 2645 2644 2646 2647 2643 2642 2640 2641 2649 2648 2650 2651 2655 2654 2652 2653 2637 2636 2638 2639 2635 2634 2632 2633 2625 2624 2626 2627 2631 2630 2628 2629 2661 2660 2662 2663 2659 2658 2656 2657 2665 2664 2666 2667 2671 2670 2668 2669 2685 2684 2686 2687 2683 2682 2680 2681 2673 2672 2674 2675 2679 2678 2676 2677 2613 2612 2614 2615 2611 2610 2608 2609 2617 2616 2618 2619 2623 2622 2620 2621 2605 2604 2606 2607 2603 2602 2600 2601 2593 2592 2594 2595 2599 2598 2596 2597 2565 2564 2566 2567 2563 2562 2560 2561 2569 2568 2570 2571 2575 2574 2572 2573 2589 2588 2590 2591 2587 2586 2584 2585 2577 2576 2578 2579 2583 2582 2580 2581 533 532 534 535 531 530 528 529 537 536 538 539 543 542 540 541 525 524 526 527 523 522 520 521 513 512 514 515 519 518 516 517 549 548 550 551 547 546 544 545 553 552 554 555 559 558 556 557 573 572 574 575 571 570 568 569 561 560 562 563 567 566 564 565 629 628 630 631 627 626 624 625 633 632 634 635 639 638 636 637 621 620 622 623 619 618 616 617 609 608 610 611 615 614 612 613 581 580 582 583 579 578 576 577 585 584 586 587 591 590 588 589 605 604 606 607 603 602 600 601 593 592 594 595 599 598 596 597 725 724 726 727 723 722 720 721 729 728 730 731 735 734 732 733 717 716 718 719 715 714 712 713 705 704 706 707 711 710 708 709 741 740 742 743 739 738 736 737 745 744 746 747 751 750 748 749 765 764 766 767 763 762 760 761 753 752 754 755 759 758 756 757 693 692 694 695 691 690 688 689 697 696 698 699 703 702 700 701 685 684 686 687 683 682 680 681 673 672 674 675 679 678 676 677 645 644 646 647 643 642 640 641 649 648 650 651 655 654 652 653 669 668 670 671 667 666 664 665 657 656 658 659 663 662 660 661 917 916 918 919 915 914 912 913 921 920 922 923 927 926 924 925 909 908 910 911 907 906 904 905 897 896 898 899 903 902 900 901 933 932 934 935 931 930 928 929 937 936 938 939 943 942 940 941 957 956 958 959 955 954 952 953 945 944 946 947 951 950 948 949 1013 1012 1014 1015 1011 1010 1008 1009 1017 1016 1018 1019 1023 1022 1020 1021 1005 1004 1006 1007 1003 1002 1000 1001 993 992 994 995 999 998 996 997 965 964 966 967 963 962 960 961 969 968 970 971 975 974 972 973 989 988 990 991 987 986 984 985 977 976 978 979 983 982 980 981 853 852 854 855 851 850 848 849 857 856 858 859 863 862 860 861 845 844 846 847 843 842 840 841 833 832 834 835 839 838 836 837 869 868 870 871 867 866 864 865 873 872 874 875 879 878 876 877 893 892 894 895 891 890 888 889 881 880 882 883 887 886 884 885 821 820 822 823 819 818 816 817 825 824 826 827 831 830 828 829 813 812 814 815 811 810 808 809 801 800 802 803 807 806 804 805 773 772 774 775 771 770 768 769 777 776 778 779 783 782 780 781 797 796 798 799 795 794 792 793 785 784 786 787 791 790 788 789 277 276 278 279 275 274 272 273 281 280 282 283 287 286 284 285 269 268 270 271 267 266 264 265 257 256 258 259 263 262 260 261 293 292 294 295 291 290 288 289 297 296 298 299 303 302 300 301 317 316 318 319 315 314 312 313 305 304 306 307 311 310 308 309 373 372 374 375 371 370 368 369 377 376 378 379 383 382 380 381 365 364 366 367 363 362 360 361 353 352 354 355 359 358 356 357 325 324 326 327 323 322 320 321 329 328 330 331 335 334 332 333 349 348 350 351 347 346 344 345 337 336 338 339 343 342 340 341 469 468 470 471 467 466 464 465 473 472 474 475 479 478 476 477 461 460 462 463 459 458 456 457 449 448 450 451 455 454 452 453 485 484 486 487 483 482 480 481 489 488 490 491 495 494 492 493 509 508 510 511 507 506 504 505 497 496 498 499 503 502 500 501 437 436 438 439 435 434 432 433 441 440 442 443 447 446 444 445 429 428 430 431 427 426 424 425 417 416 418 419 423 422 420 421 389 388 390 391 387 386 384 385 393 392 394 395 399 398 396 397 413 412 414 415 411 410 408 409 401 400 402 403 407 406 404 405 149 148 150 151 147 146 144 145 153 152 154 155 159 158 156 157 141 140 142 143 139 138 136 137 129 128 130 131 135 134 132 133 165 164 166 167 163 162 160 161 169 168 170 171 175 174 172 173 189 188 190 191 187 186 184 185 177 176 178 179 183 182 180 181 245 244 246 247 243 242 240 241 249 248 250 251 255 254 252 253 237 236 238 239 235 234 232 233 225 224 226 227 231 230 228 229 197 196 198 199 195 194 192 193 201 200 202 203 207 206 204 205 221 220 222 223 219 218 216 217 209 208 210 211 215 214 212 213 85 84 86 87 83 82 80 81 89 88 90 91 95 94 92 93 77 76 78 79 75 74 72 73 65 64 66 67 71 70 68 69 101 100 102 103 99 98 96 97 105 104 106 107 111 110 108 109 125 124 126 127 123 122 120 121 113 112 114 115 119 118 116 117 53 52 54 55 51 50 48 49 57 56 58 59 63 62 60 61 45 44 46 47 43 42 40 41 33 32 34 35 39 38 36 37 5 4 6 7 3 2 0 1 9 8 10 11 15 14 12 13 29 28 30 31 27 26 24 25 17 16 18 19 23 22 20 21 1045 1044 1046 1047 1043 1042 1040 1041 1049 1048 1050 1051 1055 1054 1052 1053 1037 1036 1038 1039 1035 1034 1032 1033 1025 1024 1026 1027 1031 1030 1028 1029 1061 1060 1062 1063 1059 1058 1056 1057 1065 1064 1066 1067 1071 1070 1068 1069 1085 1084 1086 1087 1083 1082 1080 1081 1073 1072 1074 1075 1079 1078 1076 1077 1141 1140 1142 1143 1139 1138 1136 1137 1145 1144 1146 1147 1151 1150 1148 1149 1133 1132 1134 1135 1131 1130 1128 1129 1121 1120 1122 1123 1127 1126 1124 1125 1093 1092 1094 1095 1091 1090 1088 1089 1097 1096 1098 1099 1103 1102 1100 1101 1117 1116 1118 1119 1115 1114 1112 1113 1105 1104 1106 1107 1111 1110 1108 1109 1237 1236 1238 1239 1235 1234 1232 1233 1241 1240 1242 1243 1247 1246 1244 1245 1229 1228 1230 1231 1227 1226 1224 1225 1217 1216 1218 1219 1223 1222 1220 1221 1253 1252 1254 1255 1251 1250 1248 1249 1257 1256 1258 1259 1263 1262 1260 1261 1277 1276 1278 1279 1275 1274 1272 1273 1265 1264 1266 1267 1271 1270 1268 1269 1205 1204 1206 1207 1203 1202 1200 1201 1209 1208 1210 1211 1215 1214 1212 1213 1197 1196 1198 1199 1195 1194 1192 1193 1185 1184 1186 1187 1191 1190 1188 1189 1157 1156 1158 1159 1155 1154 1152 1153 1161 1160 1162 1163 1167 1166 1164 1165 1181 1180 1182 1183 1179 1178 1176 1177 1169 1168 1170 1171 1175 1174 1172 1173 1429 1428 1430 1431 1427 1426 1424 1425 1433 1432 1434 1435 1439 1438 1436 1437 1421 1420 1422 1423 1419 1418 1416 1417 1409 1408 1410 1411 1415 1414 1412 1413 1445 1444 1446 1447 1443 1442 1440 1441 1449 1448 1450 1451 1455 1454 1452 1453 1469 1468 1470 1471 1467 1466 1464 1465 1457 1456 1458 1459 1463 1462 1460 1461 1525 1524 1526 1527 1523 1522 1520 1521 1529 1528 1530 1531 1535 1534 1532 1533 1517 1516 1518 1519 1515 1514 1512 1513 1505 1504 1506 1507 1511 1510 1508 1509 1477 1476 1478 1479 1475 1474 1472 1473 1481 1480 1482 1483 1487 1486 1484 1485 1501 1500 1502 1503 1499 1498 1496 1497 1489 1488 1490 1491 1495 1494 1492 1493 1365 1364 1366 1367 1363 1362 1360 1361 1369 1368 1370 1371 1375 1374 1372 1373 1357 1356 1358 1359 1355 1354 1352 1353 1345 1344 1346 1347 1351 1350 1348 1349 1381 1380 1382 1383 1379 1378 1376 1377 1385 1384 1386 1387 1391 1390 1388 1389 1405 1404 1406 1407 1403 1402 1400 1401 1393 1392 1394 1395 1399 1398 1396 1397 1333 1332 1334 1335 1331 1330 1328 1329 1337 1336 1338 1339 1343 1342 1340 1341 1325 1324 1326 1327 1323 1322 1320 1321 1313 1312 1314 1315 1319 1318 1316 1317 1285 1284 1286 1287 1283 1282 1280 1281 1289 1288 1290 1291 1295 1294 1292 1293 1309 1308 1310 1311 1307 1306 1304 1305 1297 1296 1298 1299 1303 1302 1300 1301 1813 1812 1814 1815 1811 1810 1808 1809 1817 1816 1818 1819 1823 1822 1820 1821 1805 1804 1806 1807 1803 1802 1800 1801 1793 1792 1794 1795 1799 1798 1796 1797 1829 1828 1830 1831 1827 1826 1824 1825 1833 1832 1834 1835 1839 1838 1836 1837 1853 1852 1854 1855 1851 1850 1848 1849 1841 1840 1842 1843 1847 1846 1844 1845 1909 1908 1910 1911 1907 1906 1904 1905 1913 1912 1914 1915 1919 1918 1916 1917 1901 1900 1902 1903 1899 1898 1896 1897 1889 1888 1890 1891 1895 1894 1892 1893 1861 1860 1862 1863 1859 1858 1856 1857 1865 1864 1866 1867 1871 1870 1868 1869 1885 1884 1886 1887 1883 1882 1880 1881 1873 1872 1874 1875 1879 1878 1876 1877 2005 2004 2006 2007 2003 2002 2000 2001 2009 2008 2010 2011 2015 2014 2012 2013 1997 1996 1998 1999 1995 1994 1992 1993 1985 1984 1986 1987 1991 1990 1988 1989 2021 2020 2022 2023 2019 2018 2016 2017 2025 2024 2026 2027 2031 2030 2028 2029 2045 2044 2046 2047 2043 2042 2040 2041 2033 2032 2034 2035 2039 2038 2036 2037 1973 1972 1974 1975 1971 1970 1968 1969 1977 1976 1978 1979 1983 1982 1980 1981 1965 1964 1966 1967 1963 1962 1960 1961 1953 1952 1954 1955 1959 1958 1956 1957 1925 1924 1926 1927 1923 1922 1920 1921 1929 1928 1930 1931 1935 1934 1932 1933 1949 1948 1950 1951 1947 1946 1944 1945 1937 1936 1938 1939 1943 1942 1940 1941 1685 1684 1686 1687 1683 1682 1680 1681 1689 1688 1690 1691 1695 1694 1692 1693 1677 1676 1678 1679 1675 1674 1672 1673 1665 1664 1666 1667 1671 1670 1668 1669 1701 1700 1702 1703 1699 1698 1696 1697 1705 1704 1706 1707 1711 1710 1708 1709 1725 1724 1726 1727 1723 1722 1720 1721 1713 1712 1714 1715 1719 1718 1716 1717 1781 1780 1782 1783 1779 1778 1776 1777 1785 1784 1786 1787 1791 1790 1788 1789 1773 1772 1774 1775 1771 1770 1768 1769 1761 1760 1762 1763 1767 1766 1764 1765 1733 1732 1734 1735 1731 1730 1728 1729 1737 1736 1738 1739 1743 1742 1740 1741 1757 1756 1758 1759 1755 1754 1752 1753 1745 1744 1746 1747 1751 1750 1748 1749 1621 1620 1622 1623 1619 1618 1616 1617 1625 1624 1626 1627 1631 1630 1628 1629 1613 1612 1614 1615 1611 1610 1608 1609 1601 1600 1602 1603 1607 1606 1604 1605 1637 1636 1638 1639 1635 1634 1632 1633 1641 1640 1642 1643 1647 1646 1644 1645 1661 1660 1662 1663 1659 1658 1656 1657 1649 1648 1650 1651 1655 1654 1652 1653 1589 1588 1590 1591 1587 1586 1584 1585 1593 1592 1594 1595 1599 1598 1596 1597 1581 1580 1582 1583 1579 1578 1576 1577 1569 1568 1570 1571 1575 1574 1572 1573 1541 1540 1542 1543 1539 1538 1536 1537 1545 1544 1546 1547 1551 1550 1548 1549 1565 1564 1566 1567 1563 1562 1560 1561 1553 1552 1554 1555 1559 1558 1556 1557 5653 5652 5654 5655 5651 5650 5648 5649 5657 5656 5658 5659 5663 5662 5660 5661 5645 5644 5646 5647 5643 5642 5640 5641 5633 5632 5634 5635 5639 5638 5636 5637 5669 5668 5670 5671 5667 5666 5664 5665 5673 5672 5674 5675 5679 5678 5676 5677 5693 5692 5694 5695 5691 5690 5688 5689 5681 5680 5682 5683 5687 5686 5684 5685 5749 5748 5750 5751 5747 5746 5744 5745 5753 5752 5754 5755 5759 5758 5756 5757 5741 5740 5742 5743 5739 5738 5736 5737 5729 5728 5730 5731 5735 5734 5732 5733 5701 5700 5702 5703 5699 5698 5696 5697 5705 5704 5706 5707 5711 5710 5708 5709 5725 5724 5726 5727 5723 5722 5720 5721 5713 5712 5714 5715 5719 5718 5716 5717 5845 5844 5846 5847 5843 5842 5840 5841 5849 5848 5850 5851 5855 5854 5852 5853 5837 5836 5838 5839 5835 5834 5832 5833 5825 5824 5826 5827 5831 5830 5828 5829 5861 5860 5862 5863 5859 5858 5856 5857 5865 5864 5866 5867 5871 5870 5868 5869 5885 5884 5886 5887 5883 5882 5880 5881 5873 5872 5874 5875 5879 5878 5876 5877 5813 5812 5814 5815 5811 5810 5808 5809 5817 5816 5818 5819 5823 5822 5820 5821 5805 5804 5806 5807 5803 5802 5800 5801 5793 5792 5794 5795 5799 5798 5796 5797 5765 5764 5766 5767 5763 5762 5760 5761 5769 5768 5770 5771 5775 5774 5772 5773 5789 5788 5790 5791 5787 5786 5784 5785 5777 5776 5778 5779 5783 5782 5780 5781 6037 6036 6038 6039 6035 6034 6032 6033 6041 6040 6042 6043 6047 6046 6044 6045 6029 6028 6030 6031 6027 6026 6024 6025 6017 6016 6018 6019 6023 6022 6020 6021 6053 6052 6054 6055 6051 6050 6048 6049 6057 6056 6058 6059 6063 6062 6060 6061 6077 6076 6078 6079 6075 6074 6072 6073 6065 6064 6066 6067 6071 6070 6068 6069 6133 6132 6134 6135 6131 6130 6128 6129 6137 6136 6138 6139 6143 6142 6140 6141 6125 6124 6126 6127 6123 6122 6120 6121 6113 6112 6114 6115 6119 6118 6116 6117 6085 6084 6086 6087 6083 6082 6080 6081 6089 6088 6090 6091 6095 6094 6092 6093 6109 6108 6110 6111 6107 6106 6104 6105 6097 6096 6098 6099 6103 6102 6100 6101 5973 5972 5974 5975 5971 5970 5968 5969 5977 5976 5978 5979 5983 5982 5980 5981 5965 5964 5966 5967 5963 5962 5960 5961 5953 5952 5954 5955 5959 5958 5956 5957 5989 5988 5990 5991 5987 5986 5984 5985 5993 5992 5994 5995 5999 5998 5996 5997 6013 6012 6014 6015 6011 6010 6008 6009 6001 6000 6002 6003 6007 6006 6004 6005 5941 5940 5942 5943 5939 5938 5936 5937 5945 5944 5946 5947 5951 5950 5948 5949 5933 5932 5934 5935 5931 5930 5928 5929 5921 5920 5922 5923 5927 5926 5924 5925 5893 5892 5894 5895 5891 5890 5888 5889 5897 5896 5898 5899 5903 5902 5900 5901 5917 5916 5918 5919 5915 5914 5912 5913 5905 5904 5906 5907 5911 5910 5908 5909 4885 4884 4886 4887 4883 4882 4880 4881 4889 4888 4890 4891 4895 4894 4892 4893 4877 4876 4878 4879 4875 4874 4872 4873 4865 4864 4866 4867 4871 4870 4868 4869 4901 4900 4902 4903 4899 4898 4896 4897 4905 4904 4906 4907 4911 4910 4908 4909 4925 4924 4926 4927 4923 4922 4920 4921 4913 4912 4914 4915 4919 4918 4916 4917 4981 4980 4982 4983 4979 4978 4976 4977 4985 4984 4986 4987 4991 4990 4988 4989 4973 4972 4974 4975 4971 4970 4968 4969 4961 4960 4962 4963 4967 4966 4964 4965 4933 4932 4934 4935 4931 4930 4928 4929 4937 4936 4938 4939 4943 4942 4940 4941 4957 4956 4958 4959 4955 4954 4952 4953 4945 4944 4946 4947 4951 4950 4948 4949 5077 5076 5078 5079 5075 5074 5072 5073 5081 5080 5082 5083 5087 5086 5084 5085 5069 5068 5070 5071 5067 5066 5064 5065 5057 5056 5058 5059 5063 5062 5060 5061 5093 5092 5094 5095 5091 5090 5088 5089 5097 5096 5098 5099 5103 5102 5100 5101 5117 5116 5118 5119 5115 5114 5112 5113 5105 5104 5106 5107 5111 5110 5108 5109 5045 5044 5046 5047 5043 5042 5040 5041 5049 5048 5050 5051 5055 5054 5052 5053 5037 5036 5038 5039 5035 5034 5032 5033 5025 5024 5026 5027 5031 5030 5028 5029 4997 4996 4998 4999 4995 4994 4992 4993 5001 5000 5002 5003 5007 5006 5004 5005 5021 5020 5022 5023 5019 5018 5016 5017 5009 5008 5010 5011 5015 5014 5012 5013 4757 4756 4758 4759 4755 4754 4752 4753 4761 4760 4762 4763 4767 4766 4764 4765 4749 4748 4750 4751 4747 4746 4744 4745 4737 4736 4738 4739 4743 4742 4740 4741 4773 4772 4774 4775 4771 4770 4768 4769 4777 4776 4778 4779 4783 4782 4780 4781 4797 4796 4798 4799 4795 4794 4792 4793 4785 4784 4786 4787 4791 4790 4788 4789 4853 4852 4854 4855 4851 4850 4848 4849 4857 4856 4858 4859 4863 4862 4860 4861 4845 4844 4846 4847 4843 4842 4840 4841 4833 4832 4834 4835 4839 4838 4836 4837 4805 4804 4806 4807 4803 4802 4800 4801 4809 4808 4810 4811 4815 4814 4812 4813 4829 4828 4830 4831 4827 4826 4824 4825 4817 4816 4818 4819 4823 4822 4820 4821 4693 4692 4694 4695 4691 4690 4688 4689 4697 4696 4698 4699 4703 4702 4700 4701 4685 4684 4686 4687 4683 4682 4680 4681 4673 4672 4674 4675 4679 4678 4676 4677 4709 4708 4710 4711 4707 4706 4704 4705 4713 4712 4714 4715 4719 4718 4716 4717 4733 4732 4734 4735 4731 4730 4728 4729 4721 4720 4722 4723 4727 4726 4724 4725 4661 4660 4662 4663 4659 4658 4656 4657 4665 4664 4666 4667 4671 4670 4668 4669 4653 4652 4654 4655 4651 4650 4648 4649 4641 4640 4642 4643 4647 4646 4644 4645 4613 4612 4614 4615 4611 4610 4608 4609 4617 4616 4618 4619 4623 4622 4620 4621 4637 4636 4638 4639 4635 4634 4632 4633 4625 4624 4626 4627 4631 4630 4628 4629 6677 6676 6678 6679 6675 6674 6672 6673 6681 6680 6682 6683 6687 6686 6684 6685 6669 6668 6670 6671 6667 6666 6664 6665 6657 6656 6658 6659 6663 6662 6660 6661 6693 6692 6694 6695 6691 6690 6688 6689 6697 6696 6698 6699 6703 6702 6700 6701 6717 6716 6718 6719 6715 6714 6712 6713 6705 6704 6706 6707 6711 6710 6708 6709 6773 6772 6774 6775 6771 6770 6768 6769 6777 6776 6778 6779 6783 6782 6780 6781 6765 6764 6766 6767 6763 6762 6760 6761 6753 6752 6754 6755 6759 6758 6756 6757 6725 6724 6726 6727 6723 6722 6720 6721 6729 6728 6730 6731 6735 6734 6732 6733 6749 6748 6750 6751 6747 6746 6744 6745 6737 6736 6738 6739 6743 6742 6740 6741 6869 6868 6870 6871 6867 6866 6864 6865 6873 6872 6874 6875 6879 6878 6876 6877 6861 6860 6862 6863 6859 6858 6856 6857 6849 6848 6850 6851 6855 6854 6852 6853 6885 6884 6886 6887 6883 6882 6880 6881 6889 6888 6890 6891 6895 6894 6892 6893 6909 6908 6910 6911 6907 6906 6904 6905 6897 6896 6898 6899 6903 6902 6900 6901 6837 6836 6838 6839 6835 6834 6832 6833 6841 6840 6842 6843 6847 6846 6844 6845 6829 6828 6830 6831 6827 6826 6824 6825 6817 6816 6818 6819 6823 6822 6820 6821 6789 6788 6790 6791 6787 6786 6784 6785 6793 6792 6794 6795 6799 6798 6796 6797 6813 6812 6814 6815 6811 6810 6808 6809 6801 6800 6802 6803 6807 6806 6804 6805 7061 7060 7062 7063 7059 7058 7056 7057 7065 7064 7066 7067 7071 7070 7068 7069 7053 7052 7054 7055 7051 7050 7048 7049 7041 7040 7042 7043 7047 7046 7044 7045 7077 7076 7078 7079 7075 7074 7072 7073 7081 7080 7082 7083 7087 7086 7084 7085 7101 7100 7102 7103 7099 7098 7096 7097 7089 7088 7090 7091 7095 7094 7092 7093 7157 7156 7158 7159 7155 7154 7152 7153 7161 7160 7162 7163 7167 7166 7164 7165 7149 7148 7150 7151 7147 7146 7144 7145 7137 7136 7138 7139 7143 7142 7140 7141 7109 7108 7110 7111 7107 7106 7104 7105 7113 7112 7114 7115 7119 7118 7116 7117 7133 7132 7134 7135 7131 7130 7128 7129 7121 7120 7122 7123 7127 7126 7124 7125 6997 6996 6998 6999 6995 6994 6992 6993 7001 7000 7002 7003 7007 7006 7004 7005 6989 6988 6990 6991 6987 6986 6984 6985 6977 6976 6978 6979 6983 6982 6980 6981 7013 7012 7014 7015 7011 7010 7008 7009 7017 7016 7018 7019 7023 7022 7020 7021 7037 7036 7038 7039 7035 7034 7032 7033 7025 7024 7026 7027 7031 7030 7028 7029 6965 6964 6966 6967 6963 6962 6960 6961 6969 6968 6970 6971 6975 6974 6972 6973 6957 6956 6958 6959 6955 6954 6952 6953 6945 6944 6946 6947 6951 6950 6948 6949 6917 6916 6918 6919 6915 6914 6912 6913 6921 6920 6922 6923 6927 6926 6924 6925 6941 6940 6942 6943 6939 6938 6936 6937 6929 6928 6930 6931 6935 6934 6932 6933 7957 7956 7958 7959 7955 7954 7952 7953 7961 7960 7962 7963 7967 7966 7964 7965 7949 7948 7950 7951 7947 7946 7944 7945 7937 7936 7938 7939 7943 7942 7940 7941 7973 7972 7974 7975 7971 7970 7968 7969 7977 7976 7978 7979 7983 7982 7980 7981 7997 7996 7998 7999 7995 7994 7992 7993 7985 7984 7986 7987 7991 7990 7988 7989 8053 8052 8054 8055 8051 8050 8048 8049 8057 8056 8058 8059 8063 8062 8060 8061 8045 8044 8046 8047 8043 8042 8040 8041 8033 8032 8034 8035 8039 8038 8036 8037 8005 8004 8006 8007 8003 8002 8000 8001 8009 8008 8010 8011 8015 8014 8012 8013 8029 8028 8030 8031 8027 8026 8024 8025 8017 8016 8018 8019 8023 8022 8020 8021 8149 8148 8150 8151 8147 8146 8144 8145 8153 8152 8154 8155 8159 8158 8156 8157 8141 8140 8142 8143 8139 8138 8136 8137 8129 8128 8130 8131 8135 8134 8132 8133 8165 8164 8166 8167 8163 8162 8160 8161 8169 8168 8170 8171 8175 8174 8172 8173 8189 8188 8190 8191 8187 8186 8184 8185 8177 8176 8178 8179 8183 8182 8180 8181 8117 8116 8118 8119 8115 8114 8112 8113 8121 8120 8122 8123 8127 8126 8124 8125 8109 8108 8110 8111 8107 8106 8104 8105 8097 8096 8098 8099 8103 8102 8100 8101 8069 8068 8070 8071 8067 8066 8064 8065 8073 8072 8074 8075 8079 8078 8076 8077 8093 8092 8094 8095 8091 8090 8088 8089 8081 8080 8082 8083 8087 8086 8084 8085 7829 7828 7830 7831 7827 7826 7824 7825 7833 7832 7834 7835 7839 7838 7836 7837 7821 7820 7822 7823 7819 7818 7816 7817 7809 7808 7810 7811 7815 7814 7812 7813 7845 7844 7846 7847 7843 7842 7840 7841 7849 7848 7850 7851 7855 7854 7852 7853 7869 7868 7870 7871 7867 7866 7864 7865 7857 7856 7858 7859 7863 7862 7860 7861 7925 7924 7926 7927 7923 7922 7920 7921 7929 7928 7930 7931 7935 7934 7932 7933 7917 7916 7918 7919 7915 7914 7912 7913 7905 7904 7906 7907 7911 7910 7908 7909 7877 7876 7878 7879 7875 7874 7872 7873 7881 7880 7882 7883 7887 7886 7884 7885 7901 7900 7902 7903 7899 7898 7896 7897 7889 7888 7890 7891 7895 7894 7892 7893 7765 7764 7766 7767 7763 7762 7760 7761 7769 7768 7770 7771 7775 7774 7772 7773 7757 7756 7758 7759 7755 7754 7752 7753 7745 7744 7746 7747 7751 7750 7748 7749 7781 7780 7782 7783 7779 7778 7776 7777 7785 7784 7786 7787 7791 7790 7788 7789 7805 7804 7806 7807 7803 7802 7800 7801 7793 7792 7794 7795 7799 7798 7796 7797 7733 7732 7734 7735 7731 7730 7728 7729 7737 7736 7738 7739 7743 7742 7740 7741 7725 7724 7726 7727 7723 7722 7720 7721 7713 7712 7714 7715 7719 7718 7716 7717 7685 7684 7686 7687 7683 7682 7680 7681 7689 7688 7690 7691 7695 7694 7692 7693 7709 7708 7710 7711 7707 7706 7704 7705 7697 7696 7698 7699 7703 7702 7700 7701 7189 7188 7190 7191 7187 7186 7184 7185 7193 7192 7194 7195 7199 7198 7196 7197 7181 7180 7182 7183 7179 7178 7176 7177 7169 7168 7170 7171 7175 7174 7172 7173 7205 7204 7206 7207 7203 7202 7200 7201 7209 7208 7210 7211 7215 7214 7212 7213 7229 7228 7230 7231 7227 7226 7224 7225 7217 7216 7218 7219 7223 7222 7220 7221 7285 7284 7286 7287 7283 7282 7280 7281 7289 7288 7290 7291 7295 7294 7292 7293 7277 7276 7278 7279 7275 7274 7272 7273 7265 7264 7266 7267 7271 7270 7268 7269 7237 7236 7238 7239 7235 7234 7232 7233 7241 7240 7242 7243 7247 7246 7244 7245 7261 7260 7262 7263 7259 7258 7256 7257 7249 7248 7250 7251 7255 7254 7252 7253 7381 7380 7382 7383 7379 7378 7376 7377 7385 7384 7386 7387 7391 7390 7388 7389 7373 7372 7374 7375 7371 7370 7368 7369 7361 7360 7362 7363 7367 7366 7364 7365 7397 7396 7398 7399 7395 7394 7392 7393 7401 7400 7402 7403 7407 7406 7404 7405 7421 7420 7422 7423 7419 7418 7416 7417 7409 7408 7410 7411 7415 7414 7412 7413 7349 7348 7350 7351 7347 7346 7344 7345 7353 7352 7354 7355 7359 7358 7356 7357 7341 7340 7342 7343 7339 7338 7336 7337 7329 7328 7330 7331 7335 7334 7332 7333 7301 7300 7302 7303 7299 7298 7296 7297 7305 7304 7306 7307 7311 7310 7308 7309 7325 7324 7326 7327 7323 7322 7320 7321 7313 7312 7314 7315 7319 7318 7316 7317 7573 7572 7574 7575 7571 7570 7568 7569 7577 7576 7578 7579 7583 7582 7580 7581 7565 7564 7566 7567 7563 7562 7560 7561 7553 7552 7554 7555 7559 7558 7556 7557 7589 7588 7590 7591 7587 7586 7584 7585 7593 7592 7594 7595 7599 7598 7596 7597 7613 7612 7614 7615 7611 7610 7608 7609 7601 7600 7602 7603 7607 7606 7604 7605 7669 7668 7670 7671 7667 7666 7664 7665 7673 7672 7674 7675 7679 7678 7676 7677 7661 7660 7662 7663 7659 7658 7656 7657 7649 7648 7650 7651 7655 7654 7652 7653 7621 7620 7622 7623 7619 7618 7616 7617 7625 7624 7626 7627 7631 7630 7628 7629 7645 7644 7646 7647 7643 7642 7640 7641 7633 7632 7634 7635 7639 7638 7636 7637 7509 7508 7510 7511 7507 7506 7504 7505 7513 7512 7514 7515 7519 7518 7516 7517 7501 7500 7502 7503 7499 7498 7496 7497 7489 7488 7490 7491 7495 7494 7492 7493 7525 7524 7526 7527 7523 7522 7520 7521 7529 7528 7530 7531 7535 7534 7532 7533 7549 7548 7550 7551 7547 7546 7544 7545 7537 7536 7538 7539 7543 7542 7540 7541 7477 7476 7478 7479 7475 7474 7472 7473 7481 7480 7482 7483 7487 7486 7484 7485 7469 7468 7470 7471 7467 7466 7464 7465 7457 7456 7458 7459 7463 7462 7460 7461 7429 7428 7430 7431 7427 7426 7424 7425 7433 7432 7434 7435 7439 7438 7436 7437 7453 7452 7454 7455 7451 7450 7448 7449 7441 7440 7442 7443 7447 7446 7444 7445 6421 6420 6422 6423 6419 6418 6416 6417 6425 6424 6426 6427 6431 6430 6428 6429 6413 6412 6414 6415 6411 6410 6408 6409 6401 6400 6402 6403 6407 6406 6404 6405 6437 6436 6438 6439 6435 6434 6432 6433 6441 6440 6442 6443 6447 6446 6444 6445 6461 6460 6462 6463 6459 6458 6456 6457 6449 6448 6450 6451 6455 6454 6452 6453 6517 6516 6518 6519 6515 6514 6512 6513 6521 6520 6522 6523 6527 6526 6524 6525 6509 6508 6510 6511 6507 6506 6504 6505 6497 6496 6498 6499 6503 6502 6500 6501 6469 6468 6470 6471 6467 6466 6464 6465 6473 6472 6474 6475 6479 6478 6476 6477 6493 6492 6494 6495 6491 6490 6488 6489 6481 6480 6482 6483 6487 6486 6484 6485 6613 6612 6614 6615 6611 6610 6608 6609 6617 6616 6618 6619 6623 6622 6620 6621 6605 6604 6606 6607 6603 6602 6600 6601 6593 6592 6594 6595 6599 6598 6596 6597 6629 6628 6630 6631 6627 6626 6624 6625 6633 6632 6634 6635 6639 6638 6636 6637 6653 6652 6654 6655 6651 6650 6648 6649 6641 6640 6642 6643 6647 6646 6644 6645 6581 6580 6582 6583 6579 6578 6576 6577 6585 6584 6586 6587 6591 6590 6588 6589 6573 6572 6574 6575 6571 6570 6568 6569 6561 6560 6562 6563 6567 6566 6564 6565 6533 6532 6534 6535 6531 6530 6528 6529 6537 6536 6538 6539 6543 6542 6540 6541 6557 6556 6558 6559 6555 6554 6552 6553 6545 6544 6546 6547 6551 6550 6548 6549 6293 6292 6294 6295 6291 6290 6288 6289 6297 6296 6298 6299 6303 6302 6300 6301 6285 6284 6286 6287 6283 6282 6280 6281 6273 6272 6274 6275 6279 6278 6276 6277 6309 6308 6310 6311 6307 6306 6304 6305 6313 6312 6314 6315 6319 6318 6316 6317 6333 6332 6334 6335 6331 6330 6328 6329 6321 6320 6322 6323 6327 6326 6324 6325 6389 6388 6390 6391 6387 6386 6384 6385 6393 6392 6394 6395 6399 6398 6396 6397 6381 6380 6382 6383 6379 6378 6376 6377 6369 6368 6370 6371 6375 6374 6372 6373 6341 6340 6342 6343 6339 6338 6336 6337 6345 6344 6346 6347 6351 6350 6348 6349 6365 6364 6366 6367 6363 6362 6360 6361 6353 6352 6354 6355 6359 6358 6356 6357 6229 6228 6230 6231 6227 6226 6224 6225 6233 6232 6234 6235 6239 6238 6236 6237 6221 6220 6222 6223 6219 6218 6216 6217 6209 6208 6210 6211 6215 6214 6212 6213 6245 6244 6246 6247 6243 6242 6240 6241 6249 6248 6250 6251 6255 6254 6252 6253 6269 6268 6270 6271 6267 6266 6264 6265 6257 6256 6258 6259 6263 6262 6260 6261 6197 6196 6198 6199 6195 6194 6192 6193 6201 6200 6202 6203 6207 6206 6204 6205 6189 6188 6190 6191 6187 6186 6184 6185 6177 6176 6178 6179 6183 6182 6180 6181 6149 6148 6150 6151 6147 6146 6144 6145 6153 6152 6154 6155 6159 6158 6156 6157 6173 6172 6174 6175 6171 6170 6168 6169 6161 6160 6162 6163 6167 6166 6164 6165 4117 4116 4118 4119 4115 4114 4112 4113 4121 4120 4122 4123 4127 4126 4124 4125 4109 4108 4110 4111 4107 4106 4104 4105 4097 4096 4098 4099 4103 4102 4100 4101 4133 4132 4134 4135 4131 4130 4128 4129 4137 4136 4138 4139 4143 4142 4140 4141 4157 4156 4158 4159 4155 4154 4152 4153 4145 4144 4146 4147 4151 4150 4148 4149 4213 4212 4214 4215 4211 4210 4208 4209 4217 4216 4218 4219 4223 4222 4220 4221 4205 4204 4206 4207 4203 4202 4200 4201 4193 4192 4194 4195 4199 4198 4196 4197 4165 4164 4166 4167 4163 4162 4160 4161 4169 4168 4170 4171 4175 4174 4172 4173 4189 4188 4190 4191 4187 4186 4184 4185 4177 4176 4178 4179 4183 4182 4180 4181 4309 4308 4310 4311 4307 4306 4304 4305 4313 4312 4314 4315 4319 4318 4316 4317 4301 4300 4302 4303 4299 4298 4296 4297 4289 4288 4290 4291 4295 4294 4292 4293 4325 4324 4326 4327 4323 4322 4320 4321 4329 4328 4330 4331 4335 4334 4332 4333 4349 4348 4350 4351 4347 4346 4344 4345 4337 4336 4338 4339 4343 4342 4340 4341 4277 4276 4278 4279 4275 4274 4272 4273 4281 4280 4282 4283 4287 4286 4284 4285 4269 4268 4270 4271 4267 4266 4264 4265 4257 4256 4258 4259 4263 4262 4260 4261 4229 4228 4230 4231 4227 4226 4224 4225 4233 4232 4234 4235 4239 4238 4236 4237 4253 4252 4254 4255 4251 4250 4248 4249 4241 4240 4242 4243 4247 4246 4244 4245 4501 4500 4502 4503 4499 4498 4496 4497 4505 4504 4506 4507 4511 4510 4508 4509 4493 4492 4494 4495 4491 4490 4488 4489 4481 4480 4482 4483 4487 4486 4484 4485 4517 4516 4518 4519 4515 4514 4512 4513 4521 4520 4522 4523 4527 4526 4524 4525 4541 4540 4542 4543 4539 4538 4536 4537 4529 4528 4530 4531 4535 4534 4532 4533 4597 4596 4598 4599 4595 4594 4592 4593 4601 4600 4602 4603 4607 4606 4604 4605 4589 4588 4590 4591 4587 4586 4584 4585 4577 4576 4578 4579 4583 4582 4580 4581 4549 4548 4550 4551 4547 4546 4544 4545 4553 4552 4554 4555 4559 4558 4556 4557 4573 4572 4574 4575 4571 4570 4568 4569 4561 4560 4562 4563 4567 4566 4564 4565 4437 4436 4438 4439 4435 4434 4432 4433 4441 4440 4442 4443 4447 4446 4444 4445 4429 4428 4430 4431 4427 4426 4424 4425 4417 4416 4418 4419 4423 4422 4420 4421 4453 4452 4454 4455 4451 4450 4448 4449 4457 4456 4458 4459 4463 4462 4460 4461 4477 4476 4478 4479 4475 4474 4472 4473 4465 4464 4466 4467 4471 4470 4468 4469 4405 4404 4406 4407 4403 4402 4400 4401 4409 4408 4410 4411 4415 4414 4412 4413 4397 4396 4398 4399 4395 4394 4392 4393 4385 4384 4386 4387 4391 4390 4388 4389 4357 4356 4358 4359 4355 4354 4352 4353 4361 4360 4362 4363 4367 4366 4364 4365 4381 4380 4382 4383 4379 4378 4376 4377 4369 4368 4370 4371 4375 4374 4372 4373 5397 5396 5398 5399 5395 5394 5392 5393 5401 5400 5402 5403 5407 5406 5404 5405 5389 5388 5390 5391 5387 5386 5384 5385 5377 5376 5378 5379 5383 5382 5380 5381 5413 5412 5414 5415 5411 5410 5408 5409 5417 5416 5418 5419 5423 5422 5420 5421 5437 5436 5438 5439 5435 5434 5432 5433 5425 5424 5426 5427 5431 5430 5428 5429 5493 5492 5494 5495 5491 5490 5488 5489 5497 5496 5498 5499 5503 5502 5500 5501 5485 5484 5486 5487 5483 5482 5480 5481 5473 5472 5474 5475 5479 5478 5476 5477 5445 5444 5446 5447 5443 5442 5440 5441 5449 5448 5450 5451 5455 5454 5452 5453 5469 5468 5470 5471 5467 5466 5464 5465 5457 5456 5458 5459 5463 5462 5460 5461 5205 5204 5206 5207 5203 5202 5200 5201 5209 5208 5210 5211 5215 5214 5212 5213 5197 5196 5198 5199 5195 5194 5192 5193 5185 5184 5186 5187 5191 5190 5188 5189 5221 5220 5222 5223 5219 5218 5216 5217 5225 5224 5226 5227 5231 5230 5228 5229 5245 5244 5246 5247 5243 5242 5240 5241 5233 5232 5234 5235 5239 5238 5236 5237 5173 5172 5174 5175 5171 5170 5168 5169 5177 5176 5178 5179 5183 5182 5180 5181 5165 5164 5166 5167 5163 5162 5160 5161 5153 5152 5154 5155 5159 5158 5156 5157 5125 5124 5126 5127 5123 5122 5120 5121 5129 5128 5130 5131 5135 5134 5132 5133 5149 5148 5150 5151 5147 5146 5144 5145 5137 5136 5138 5139 5143 5142 5140 5141 5269 5268 5270 5271 5267 5266 5264 5265 5273 5272 5274 5275 5279 5278 5276 5277 5261 5260 5262 5263 5259 5258 5256 5257 5249 5248 5250 5251 5255 5254 5252 5253 5285 5284 5286 5287 5283 5282 5280 5281 5289 5288 5290 5291 5295 5294 5292 5293 5309 5308 5310 5311 5307 5306 5304 5305 5297 5296 5298 5299 5303 5302 5300 5301 5365 5364 5366 5367 5363 5362 5360 5361 5369 5368 5370 5371 5375 5374 5372 5373 5357 5356 5358 5359 5355 5354 5352 5353 5345 5344 5346 5347 5351 5350 5348 5349 5317 5316 5318 5319 5315 5314 5312 5313 5321 5320 5322 5323 5327 5326 5324 5325 5341 5340 5342 5343 5339 5338 5336 5337 5329 5328 5330 5331 5335 5334 5332 5333 5589 5588 5590 5591 5587 5586 5584 5585 5593 5592 5594 5595 5599 5598 5596 5597 5581 5580 5582 5583 5579 5578 5576 5577 5569 5568 5570 5571 5575 5574 5572 5573 5605 5604 5606 5607 5603 5602 5600 5601 5609 5608 5610 5611 5615 5614 5612 5613 5629 5628 5630 5631 5627 5626 5624 5625 5617 5616 5618 5619 5623 5622 5620 5621 5557 5556 5558 5559 5555 5554 5552 5553 5561 5560 5562 5563 5567 5566 5564 5565 5549 5548 5550 5551 5547 5546 5544 5545 5537 5536 5538 5539 5543 5542 5540 5541 5509 5508 5510 5511 5507 5506 5504 5505 5521 5520 5522 5523 5527 5526 5524 5525 5533 5532 5534 5535 5531 5530 5528 5529 5513 5515 5519 5517 5516 5518 5514 5512

[入力例]

2 1 3

[出力例]

YES

1 0 2 3

※AtCoderのテストケースより

[入力例]

3 2 1

[出力例]

※AtCoderのテストケースより

[入力例]

1 0 1

[出力例]

Yes

0 1

[入力例]

1 1 0

[出力例]

Yes

1 0

[入力例]

3 2 3

[出力例]

Yes

2 0 4 6 7 5 1 3

[入力例]

4 12 7

[出力例]

Yes

12 13 15 14 10 11 9 8 0 1 3 2 6 4 5 7

[入力例]

5 6 11

[出力例]

Yes

6 7 5 4 0 1 3 2 18 19 17 16 20 21 23 22 30 31 29 28 24 25 27 26 10 8 12 14 15 13 9 11

[入力例]

7 26 45

[出力例]

Yes

26 27 25 24 28 29 31 30 22 23 21 20 16 17 19 18 2 3 1 0 4 5 7 6 14 15 13 12 8 9 11 10 74 75 73 72 76 77 79 78 70 71 69 68 64 65 67 66 82 83 81 80 84 85 87 86 94 95 93 92 88 89 91 90 122 123 121 120 124 125 127 126 118 119 117 116 112 113 115 114 98 99 97 96 100 101 103 102 110 111 109 108 104 105 107 106 42 43 41 40 32 33 35 34 50 51 49 48 56 57 59 58 62 63 61 60 52 53 55 54 38 39 37 36 44 46 47 45

[入力例]

10 314 159

[出力例]

Yes

314 315 313 312 316 317 319 318 310 311 309 308 304 305 307 306 290 291 289 288 292 293 295 294 302 303 301 300 296 297 299 298 266 267 265 264 268 269 271 270 262 263 261 260 256 257 259 258 274 275 273 272 276 277 279 278 286 287 285 284 280 281 283 282 346 347 345 344 348 349 351 350 342 343 341 340 336 337 339 338 322 323 321 320 324 325 327 326 334 335 333 332 328 329 331 330 362 363 361 360 364 365 367 366 358 359 357 356 352 353 355 354 370 371 369 368 372 373 375 374 382 383 381 380 376 377 379 378 506 507 505 504 508 509 511 510 502 503 501 500 496 497 499 498 482 483 481 480 484 485 487 486 494 495 493 492 488 489 491 490 458 459 457 456 460 461 463 462 454 455 453 452 448 449 451 450 466 467 465 464 468 469 471 470 478 479 477 476 472 473 475 474 410 411 409 408 412 413 415 414 406 407 405 404 400 401 403 402 386 387 385 384 388 389 391 390 398 399 397 396 392 393 395 394 426 427 425 424 428 429 431 430 422 423 421 420 416 417 419 418 434 435 433 432 436 437 439 438 446 447 445 444 440 441 443 442 954 955 953 952 956 957 959 958 950 951 949 948 944 945 947 946 930 931 929 928 932 933 935 934 942 943 941 940 936 937 939 938 906 907 905 904 908 909 911 910 902 903 901 900 896 897 899 898 914 915 913 912 916 917 919 918 926 927 925 924 920 921 923 922 986 987 985 984 988 989 991 990 982 983 981 980 976 977 979 978 962 963 961 960 964 965 967 966 974 975 973 972 968 969 971 970 1002 1003 1001 1000 1004 1005 1007 1006 998 999 997 996 992 993 995 994 1010 1011 1009 1008 1012 1013 1015 1014 1022 1023 1021 1020 1016 1017 1019 1018 890 891 889 888 892 893 895 894 886 887 885 884 880 881 883 882 866 867 865 864 868 869 871 870 878 879 877 876 872 873 875 874 842 843 841 840 844 845 847 846 838 839 837 836 832 833 835 834 850 851 849 848 852 853 855 854 862 863 861 860 856 857 859 858 794 795 793 792 796 797 799 798 790 791 789 788 784 785 787 786 770 771 769 768 772 773 775 774 782 783 781 780 776 777 779 778 810 811 809 808 812 813 815 814 806 807 805 804 800 801 803 802 818 819 817 816 820 821 823 822 830 831 829 828 824 825 827 826 570 571 569 568 572 573 575 574 566 567 565 564 560 561 563 562 546 547 545 544 548 549 551 550 558 559 557 556 552 553 555 554 522 523 521 520 524 525 527 526 518 519 517 516 512 513 515 514 530 531 529 528 532 533 535 534 542 543 541 540 536 537 539 538 602 603 601 600 604 605 607 606 598 599 597 596 592 593 595 594 578 579 577 576 580 581 583 582 590 591 589 588 584 585 587 586 618 619 617 616 620 621 623 622 614 615 613 612 608 609 611 610 626 627 625 624 628 629 631 630 638 639 637 636 632 633 635 634 762 763 761 760 764 765 767 766 758 759 757 756 752 753 755 754 738 739 737 736 740 741 743 742 750 751 749 748 744 745 747 746 714 715 713 712 716 717 719 718 710 711 709 708 704 705 707 706 722 723 721 720 724 725 727 726 734 735 733 732 728 729 731 730 666 667 665 664 668 669 671 670 662 663 661 660 656 657 659 658 642 643 641 640 644 645 647 646 654 655 653 652 648 649 651 650 682 683 681 680 684 685 687 686 678 679 677 676 672 673 675 674 690 691 689 688 692 693 695 694 702 703 701 700 696 697 699 698 186 187 185 184 188 189 191 190 182 183 181 180 176 177 179 178 162 163 161 160 164 165 167 166 174 175 173 172 168 169 171 170 234 235 233 232 236 237 239 238 230 231 229 228 224 225 227 226 242 243 241 240 244 245 247 246 254 255 253 252 248 249 251 250 122 123 121 120 124 125 127 126 118 119 117 116 112 113 115 114 98 99 97 96 100 101 103 102 110 111 109 108 104 105 107 106 42 43 41 40 44 45 47 46 38 39 37 36 32 33 35 34 50 51 49 48 52 53 55 54 62 63 61 60 56 57 59 58 26 27 25 24 28 29 31 30 22 23 21 20 16 17 19 18 2 3 1 0 4 5 7 6 14 15 13 12 8 9 11 10 74 75 73 72 76 77 79 78 70 71 69 68 64 65 67 66 82 83 81 80 84 85 87 86 94 95 93 92 88 89 91 90 218 219 217 216 220 221 223 222 214 215 213 212 208 209 211 210 194 195 193 192 196 197 199 198 206 207 205 204 200 201 203 202 138 139 137 136 140 141 143 142 134 135 133 132 128 129 131 130 146 147 145 144 148 149 151 150 158 156 152 154 155 153 157 159

[入力例]

13 3605 5512

[出力例]

Yes

3605 3604 3606 3607 3603 3602 3600 3601 3609 3608 3610 3611 3615 3614 3612 3613 3597 3596 3598 3599 3595 3594 3592 3593 3585 3584 3586 3587 3591 3590 3588 3589 3621 3620 3622 3623 3619 3618 3616 3617 3625 3624 3626 3627 3631 3630 3628 3629 3645 3644 3646 3647 3643 3642 3640 3641 3633 3632 3634 3635 3639 3638 3636 3637 3701 3700 3702 3703 3699 3698 3696 3697 3705 3704 3706 3707 3711 3710 3708 3709 3693 3692 3694 3695 3691 3690 3688 3689 3681 3680 3682 3683 3687 3686 3684 3685 3653 3652 3654 3655 3651 3650 3648 3649 3657 3656 3658 3659 3663 3662 3660 3661 3677 3676 3678 3679 3675 3674 3672 3673 3665 3664 3666 3667 3671 3670 3668 3669 3797 3796 3798 3799 3795 3794 3792 3793 3801 3800 3802 3803 3807 3806 3804 3805 3789 3788 3790 3791 3787 3786 3784 3785 3777 3776 3778 3779 3783 3782 3780 3781 3813 3812 3814 3815 3811 3810 3808 3809 3817 3816 3818 3819 3823 3822 3820 3821 3837 3836 3838 3839 3835 3834 3832 3833 3825 3824 3826 3827 3831 3830 3828 3829 3765 3764 3766 3767 3763 3762 3760 3761 3769 3768 3770 3771 3775 3774 3772 3773 3757 3756 3758 3759 3755 3754 3752 3753 3745 3744 3746 3747 3751 3750 3748 3749 3717 3716 3718 3719 3715 3714 3712 3713 3721 3720 3722 3723 3727 3726 3724 3725 3741 3740 3742 3743 3739 3738 3736 3737 3729 3728 3730 3731 3735 3734 3732 3733 3989 3988 3990 3991 3987 3986 3984 3985 3993 3992 3994 3995 3999 3998 3996 3997 3981 3980 3982 3983 3979 3978 3976 3977 3969 3968 3970 3971 3975 3974 3972 3973 4005 4004 4006 4007 4003 4002 4000 4001 4009 4008 4010 4011 4015 4014 4012 4013 4029 4028 4030 4031 4027 4026 4024 4025 4017 4016 4018 4019 4023 4022 4020 4021 4085 4084 4086 4087 4083 4082 4080 4081 4089 4088 4090 4091 4095 4094 4092 4093 4077 4076 4078 4079 4075 4074 4072 4073 4065 4064 4066 4067 4071 4070 4068 4069 4037 4036 4038 4039 4035 4034 4032 4033 4041 4040 4042 4043 4047 4046 4044 4045 4061 4060 4062 4063 4059 4058 4056 4057 4049 4048 4050 4051 4055 4054 4052 4053 3925 3924 3926 3927 3923 3922 3920 3921 3929 3928 3930 3931 3935 3934 3932 3933 3917 3916 3918 3919 3915 3914 3912 3913 3905 3904 3906 3907 3911 3910 3908 3909 3941 3940 3942 3943 3939 3938 3936 3937 3945 3944 3946 3947 3951 3950 3948 3949 3965 3964 3966 3967 3963 3962 3960 3961 3953 3952 3954 3955 3959 3958 3956 3957 3893 3892 3894 3895 3891 3890 3888 3889 3897 3896 3898 3899 3903 3902 3900 3901 3885 3884 3886 3887 3883 3882 3880 3881 3873 3872 3874 3875 3879 3878 3876 3877 3845 3844 3846 3847 3843 3842 3840 3841 3849 3848 3850 3851 3855 3854 3852 3853 3869 3868 3870 3871 3867 3866 3864 3865 3857 3856 3858 3859 3863 3862 3860 3861 3349 3348 3350 3351 3347 3346 3344 3345 3353 3352 3354 3355 3359 3358 3356 3357 3341 3340 3342 3343 3339 3338 3336 3337 3329 3328 3330 3331 3335 3334 3332 3333 3365 3364 3366 3367 3363 3362 3360 3361 3369 3368 3370 3371 3375 3374 3372 3373 3389 3388 3390 3391 3387 3386 3384 3385 3377 3376 3378 3379 3383 3382 3380 3381 3445 3444 3446 3447 3443 3442 3440 3441 3449 3448 3450 3451 3455 3454 3452 3453 3437 3436 3438 3439 3435 3434 3432 3433 3425 3424 3426 3427 3431 3430 3428 3429 3397 3396 3398 3399 3395 3394 3392 3393 3401 3400 3402 3403 3407 3406 3404 3405 3421 3420 3422 3423 3419 3418 3416 3417 3409 3408 3410 3411 3415 3414 3412 3413 3541 3540 3542 3543 3539 3538 3536 3537 3545 3544 3546 3547 3551 3550 3548 3549 3533 3532 3534 3535 3531 3530 3528 3529 3521 3520 3522 3523 3527 3526 3524 3525 3557 3556 3558 3559 3555 3554 3552 3553 3561 3560 3562 3563 3567 3566 3564 3565 3581 3580 3582 3583 3579 3578 3576 3577 3569 3568 3570 3571 3575 3574 3572 3573 3509 3508 3510 3511 3507 3506 3504 3505 3513 3512 3514 3515 3519 3518 3516 3517 3501 3500 3502 3503 3499 3498 3496 3497 3489 3488 3490 3491 3495 3494 3492 3493 3461 3460 3462 3463 3459 3458 3456 3457 3465 3464 3466 3467 3471 3470 3468 3469 3485 3484 3486 3487 3483 3482 3480 3481 3473 3472 3474 3475 3479 3478 3476 3477 3221 3220 3222 3223 3219 3218 3216 3217 3225 3224 3226 3227 3231 3230 3228 3229 3213 3212 3214 3215 3211 3210 3208 3209 3201 3200 3202 3203 3207 3206 3204 3205 3237 3236 3238 3239 3235 3234 3232 3233 3241 3240 3242 3243 3247 3246 3244 3245 3261 3260 3262 3263 3259 3258 3256 3257 3249 3248 3250 3251 3255 3254 3252 3253 3317 3316 3318 3319 3315 3314 3312 3313 3321 3320 3322 3323 3327 3326 3324 3325 3309 3308 3310 3311 3307 3306 3304 3305 3297 3296 3298 3299 3303 3302 3300 3301 3269 3268 3270 3271 3267 3266 3264 3265 3273 3272 3274 3275 3279 3278 3276 3277 3293 3292 3294 3295 3291 3290 3288 3289 3281 3280 3282 3283 3287 3286 3284 3285 3157 3156 3158 3159 3155 3154 3152 3153 3161 3160 3162 3163 3167 3166 3164 3165 3149 3148 3150 3151 3147 3146 3144 3145 3137 3136 3138 3139 3143 3142 3140 3141 3173 3172 3174 3175 3171 3170 3168 3169 3177 3176 3178 3179 3183 3182 3180 3181 3197 3196 3198 3199 3195 3194 3192 3193 3185 3184 3186 3187 3191 3190 3188 3189 3125 3124 3126 3127 3123 3122 3120 3121 3129 3128 3130 3131 3135 3134 3132 3133 3117 3116 3118 3119 3115 3114 3112 3113 3105 3104 3106 3107 3111 3110 3108 3109 3077 3076 3078 3079 3075 3074 3072 3073 3081 3080 3082 3083 3087 3086 3084 3085 3101 3100 3102 3103 3099 3098 3096 3097 3089 3088 3090 3091 3095 3094 3092 3093 2069 2068 2070 2071 2067 2066 2064 2065 2073 2072 2074 2075 2079 2078 2076 2077 2061 2060 2062 2063 2059 2058 2056 2057 2049 2048 2050 2051 2055 2054 2052 2053 2085 2084 2086 2087 2083 2082 2080 2081 2089 2088 2090 2091 2095 2094 2092 2093 2109 2108 2110 2111 2107 2106 2104 2105 2097 2096 2098 2099 2103 2102 2100 2101 2165 2164 2166 2167 2163 2162 2160 2161 2169 2168 2170 2171 2175 2174 2172 2173 2157 2156 2158 2159 2155 2154 2152 2153 2145 2144 2146 2147 2151 2150 2148 2149 2117 2116 2118 2119 2115 2114 2112 2113 2121 2120 2122 2123 2127 2126 2124 2125 2141 2140 2142 2143 2139 2138 2136 2137 2129 2128 2130 2131 2135 2134 2132 2133 2261 2260 2262 2263 2259 2258 2256 2257 2265 2264 2266 2267 2271 2270 2268 2269 2253 2252 2254 2255 2251 2250 2248 2249 2241 2240 2242 2243 2247 2246 2244 2245 2277 2276 2278 2279 2275 2274 2272 2273 2281 2280 2282 2283 2287 2286 2284 2285 2301 2300 2302 2303 2299 2298 2296 2297 2289 2288 2290 2291 2295 2294 2292 2293 2229 2228 2230 2231 2227 2226 2224 2225 2233 2232 2234 2235 2239 2238 2236 2237 2221 2220 2222 2223 2219 2218 2216 2217 2209 2208 2210 2211 2215 2214 2212 2213 2181 2180 2182 2183 2179 2178 2176 2177 2185 2184 2186 2187 2191 2190 2188 2189 2205 2204 2206 2207 2203 2202 2200 2201 2193 2192 2194 2195 2199 2198 2196 2197 2453 2452 2454 2455 2451 2450 2448 2449 2457 2456 2458 2459 2463 2462 2460 2461 2445 2444 2446 2447 2443 2442 2440 2441 2433 2432 2434 2435 2439 2438 2436 2437 2469 2468 2470 2471 2467 2466 2464 2465 2473 2472 2474 2475 2479 2478 2476 2477 2493 2492 2494 2495 2491 2490 2488 2489 2481 2480 2482 2483 2487 2486 2484 2485 2549 2548 2550 2551 2547 2546 2544 2545 2553 2552 2554 2555 2559 2558 2556 2557 2541 2540 2542 2543 2539 2538 2536 2537 2529 2528 2530 2531 2535 2534 2532 2533 2501 2500 2502 2503 2499 2498 2496 2497 2505 2504 2506 2507 2511 2510 2508 2509 2525 2524 2526 2527 2523 2522 2520 2521 2513 2512 2514 2515 2519 2518 2516 2517 2389 2388 2390 2391 2387 2386 2384 2385 2393 2392 2394 2395 2399 2398 2396 2397 2381 2380 2382 2383 2379 2378 2376 2377 2369 2368 2370 2371 2375 2374 2372 2373 2405 2404 2406 2407 2403 2402 2400 2401 2409 2408 2410 2411 2415 2414 2412 2413 2429 2428 2430 2431 2427 2426 2424 2425 2417 2416 2418 2419 2423 2422 2420 2421 2357 2356 2358 2359 2355 2354 2352 2353 2361 2360 2362 2363 2367 2366 2364 2365 2349 2348 2350 2351 2347 2346 2344 2345 2337 2336 2338 2339 2343 2342 2340 2341 2309 2308 2310 2311 2307 2306 2304 2305 2313 2312 2314 2315 2319 2318 2316 2317 2333 2332 2334 2335 2331 2330 2328 2329 2321 2320 2322 2323 2327 2326 2324 2325 2837 2836 2838 2839 2835 2834 2832 2833 2841 2840 2842 2843 2847 2846 2844 2845 2829 2828 2830 2831 2827 2826 2824 2825 2817 2816 2818 2819 2823 2822 2820 2821 2853 2852 2854 2855 2851 2850 2848 2849 2857 2856 2858 2859 2863 2862 2860 2861 2877 2876 2878 2879 2875 2874 2872 2873 2865 2864 2866 2867 2871 2870 2868 2869 2933 2932 2934 2935 2931 2930 2928 2929 2937 2936 2938 2939 2943 2942 2940 2941 2925 2924 2926 2927 2923 2922 2920 2921 2913 2912 2914 2915 2919 2918 2916 2917 2885 2884 2886 2887 2883 2882 2880 2881 2889 2888 2890 2891 2895 2894 2892 2893 2909 2908 2910 2911 2907 2906 2904 2905 2897 2896 2898 2899 2903 2902 2900 2901 3029 3028 3030 3031 3027 3026 3024 3025 3033 3032 3034 3035 3039 3038 3036 3037 3021 3020 3022 3023 3019 3018 3016 3017 3009 3008 3010 3011 3015 3014 3012 3013 3045 3044 3046 3047 3043 3042 3040 3041 3049 3048 3050 3051 3055 3054 3052 3053 3069 3068 3070 3071 3067 3066 3064 3065 3057 3056 3058 3059 3063 3062 3060 3061 2997 2996 2998 2999 2995 2994 2992 2993 3001 3000 3002 3003 3007 3006 3004 3005 2989 2988 2990 2991 2987 2986 2984 2985 2977 2976 2978 2979 2983 2982 2980 2981 2949 2948 2950 2951 2947 2946 2944 2945 2953 2952 2954 2955 2959 2958 2956 2957 2973 2972 2974 2975 2971 2970 2968 2969 2961 2960 2962 2963 2967 2966 2964 2965 2709 2708 2710 2711 2707 2706 2704 2705 2713 2712 2714 2715 2719 2718 2716 2717 2701 2700 2702 2703 2699 2698 2696 2697 2689 2688 2690 2691 2695 2694 2692 2693 2725 2724 2726 2727 2723 2722 2720 2721 2729 2728 2730 2731 2735 2734 2732 2733 2749 2748 2750 2751 2747 2746 2744 2745 2737 2736 2738 2739 2743 2742 2740 2741 2805 2804 2806 2807 2803 2802 2800 2801 2809 2808 2810 2811 2815 2814 2812 2813 2797 2796 2798 2799 2795 2794 2792 2793 2785 2784 2786 2787 2791 2790 2788 2789 2757 2756 2758 2759 2755 2754 2752 2753 2761 2760 2762 2763 2767 2766 2764 2765 2781 2780 2782 2783 2779 2778 2776 2777 2769 2768 2770 2771 2775 2774 2772 2773 2645 2644 2646 2647 2643 2642 2640 2641 2649 2648 2650 2651 2655 2654 2652 2653 2637 2636 2638 2639 2635 2634 2632 2633 2625 2624 2626 2627 2631 2630 2628 2629 2661 2660 2662 2663 2659 2658 2656 2657 2665 2664 2666 2667 2671 2670 2668 2669 2685 2684 2686 2687 2683 2682 2680 2681 2673 2672 2674 2675 2679 2678 2676 2677 2613 2612 2614 2615 2611 2610 2608 2609 2617 2616 2618 2619 2623 2622 2620 2621 2605 2604 2606 2607 2603 2602 2600 2601 2593 2592 2594 2595 2599 2598 2596 2597 2565 2564 2566 2567 2563 2562 2560 2561 2569 2568 2570 2571 2575 2574 2572 2573 2589 2588 2590 2591 2587 2586 2584 2585 2577 2576 2578 2579 2583 2582 2580 2581 533 532 534 535 531 530 528 529 537 536 538 539 543 542 540 541 525 524 526 527 523 522 520 521 513 512 514 515 519 518 516 517 549 548 550 551 547 546 544 545 553 552 554 555 559 558 556 557 573 572 574 575 571 570 568 569 561 560 562 563 567 566 564 565 629 628 630 631 627 626 624 625 633 632 634 635 639 638 636 637 621 620 622 623 619 618 616 617 609 608 610 611 615 614 612 613 581 580 582 583 579 578 576 577 585 584 586 587 591 590 588 589 605 604 606 607 603 602 600 601 593 592 594 595 599 598 596 597 725 724 726 727 723 722 720 721 729 728 730 731 735 734 732 733 717 716 718 719 715 714 712 713 705 704 706 707 711 710 708 709 741 740 742 743 739 738 736 737 745 744 746 747 751 750 748 749 765 764 766 767 763 762 760 761 753 752 754 755 759 758 756 757 693 692 694 695 691 690 688 689 697 696 698 699 703 702 700 701 685 684 686 687 683 682 680 681 673 672 674 675 679 678 676 677 645 644 646 647 643 642 640 641 649 648 650 651 655 654 652 653 669 668 670 671 667 666 664 665 657 656 658 659 663 662 660 661 917 916 918 919 915 914 912 913 921 920 922 923 927 926 924 925 909 908 910 911 907 906 904 905 897 896 898 899 903 902 900 901 933 932 934 935 931 930 928 929 937 936 938 939 943 942 940 941 957 956 958 959 955 954 952 953 945 944 946 947 951 950 948 949 1013 1012 1014 1015 1011 1010 1008 1009 1017 1016 1018 1019 1023 1022 1020 1021 1005 1004 1006 1007 1003 1002 1000 1001 993 992 994 995 999 998 996 997 965 964 966 967 963 962 960 961 969 968 970 971 975 974 972 973 989 988 990 991 987 986 984 985 977 976 978 979 983 982 980 981 853 852 854 855 851 850 848 849 857 856 858 859 863 862 860 861 845 844 846 847 843 842 840 841 833 832 834 835 839 838 836 837 869 868 870 871 867 866 864 865 873 872 874 875 879 878 876 877 893 892 894 895 891 890 888 889 881 880 882 883 887 886 884 885 821 820 822 823 819 818 816 817 825 824 826 827 831 830 828 829 813 812 814 815 811 810 808 809 801 800 802 803 807 806 804 805 773 772 774 775 771 770 768 769 777 776 778 779 783 782 780 781 797 796 798 799 795 794 792 793 785 784 786 787 791 790 788 789 277 276 278 279 275 274 272 273 281 280 282 283 287 286 284 285 269 268 270 271 267 266 264 265 257 256 258 259 263 262 260 261 293 292 294 295 291 290 288 289 297 296 298 299 303 302 300 301 317 316 318 319 315 314 312 313 305 304 306 307 311 310 308 309 373 372 374 375 371 370 368 369 377 376 378 379 383 382 380 381 365 364 366 367 363 362 360 361 353 352 354 355 359 358 356 357 325 324 326 327 323 322 320 321 329 328 330 331 335 334 332 333 349 348 350 351 347 346 344 345 337 336 338 339 343 342 340 341 469 468 470 471 467 466 464 465 473 472 474 475 479 478 476 477 461 460 462 463 459 458 456 457 449 448 450 451 455 454 452 453 485 484 486 487 483 482 480 481 489 488 490 491 495 494 492 493 509 508 510 511 507 506 504 505 497 496 498 499 503 502 500 501 437 436 438 439 435 434 432 433 441 440 442 443 447 446 444 445 429 428 430 431 427 426 424 425 417 416 418 419 423 422 420 421 389 388 390 391 387 386 384 385 393 392 394 395 399 398 396 397 413 412 414 415 411 410 408 409 401 400 402 403 407 406 404 405 149 148 150 151 147 146 144 145 153 152 154 155 159 158 156 157 141 140 142 143 139 138 136 137 129 128 130 131 135 134 132 133 165 164 166 167 163 162 160 161 169 168 170 171 175 174 172 173 189 188 190 191 187 186 184 185 177 176 178 179 183 182 180 181 245 244 246 247 243 242 240 241 249 248 250 251 255 254 252 253 237 236 238 239 235 234 232 233 225 224 226 227 231 230 228 229 197 196 198 199 195 194 192 193 201 200 202 203 207 206 204 205 221 220 222 223 219 218 216 217 209 208 210 211 215 214 212 213 85 84 86 87 83 82 80 81 89 88 90 91 95 94 92 93 77 76 78 79 75 74 72 73 65 64 66 67 71 70 68 69 101 100 102 103 99 98 96 97 105 104 106 107 111 110 108 109 125 124 126 127 123 122 120 121 113 112 114 115 119 118 116 117 53 52 54 55 51 50 48 49 57 56 58 59 63 62 60 61 45 44 46 47 43 42 40 41 33 32 34 35 39 38 36 37 5 4 6 7 3 2 0 1 9 8 10 11 15 14 12 13 29 28 30 31 27 26 24 25 17 16 18 19 23 22 20 21 1045 1044 1046 1047 1043 1042 1040 1041 1049 1048 1050 1051 1055 1054 1052 1053 1037 1036 1038 1039 1035 1034 1032 1033 1025 1024 1026 1027 1031 1030 1028 1029 1061 1060 1062 1063 1059 1058 1056 1057 1065 1064 1066 1067 1071 1070 1068 1069 1085 1084 1086 1087 1083 1082 1080 1081 1073 1072 1074 1075 1079 1078 1076 1077 1141 1140 1142 1143 1139 1138 1136 1137 1145 1144 1146 1147 1151 1150 1148 1149 1133 1132 1134 1135 1131 1130 1128 1129 1121 1120 1122 1123 1127 1126 1124 1125 1093 1092 1094 1095 1091 1090 1088 1089 1097 1096 1098 1099 1103 1102 1100 1101 1117 1116 1118 1119 1115 1114 1112 1113 1105 1104 1106 1107 1111 1110 1108 1109 1237 1236 1238 1239 1235 1234 1232 1233 1241 1240 1242 1243 1247 1246 1244 1245 1229 1228 1230 1231 1227 1226 1224 1225 1217 1216 1218 1219 1223 1222 1220 1221 1253 1252 1254 1255 1251 1250 1248 1249 1257 1256 1258 1259 1263 1262 1260 1261 1277 1276 1278 1279 1275 1274 1272 1273 1265 1264 1266 1267 1271 1270 1268 1269 1205 1204 1206 1207 1203 1202 1200 1201 1209 1208 1210 1211 1215 1214 1212 1213 1197 1196 1198 1199 1195 1194 1192 1193 1185 1184 1186 1187 1191 1190 1188 1189 1157 1156 1158 1159 1155 1154 1152 1153 1161 1160 1162 1163 1167 1166 1164 1165 1181 1180 1182 1183 1179 1178 1176 1177 1169 1168 1170 1171 1175 1174 1172 1173 1429 1428 1430 1431 1427 1426 1424 1425 1433 1432 1434 1435 1439 1438 1436 1437 1421 1420 1422 1423 1419 1418 1416 1417 1409 1408 1410 1411 1415 1414 1412 1413 1445 1444 1446 1447 1443 1442 1440 1441 1449 1448 1450 1451 1455 1454 1452 1453 1469 1468 1470 1471 1467 1466 1464 1465 1457 1456 1458 1459 1463 1462 1460 1461 1525 1524 1526 1527 1523 1522 1520 1521 1529 1528 1530 1531 1535 1534 1532 1533 1517 1516 1518 1519 1515 1514 1512 1513 1505 1504 1506 1507 1511 1510 1508 1509 1477 1476 1478 1479 1475 1474 1472 1473 1481 1480 1482 1483 1487 1486 1484 1485 1501 1500 1502 1503 1499 1498 1496 1497 1489 1488 1490 1491 1495 1494 1492 1493 1365 1364 1366 1367 1363 1362 1360 1361 1369 1368 1370 1371 1375 1374 1372 1373 1357 1356 1358 1359 1355 1354 1352 1353 1345 1344 1346 1347 1351 1350 1348 1349 1381 1380 1382 1383 1379 1378 1376 1377 1385 1384 1386 1387 1391 1390 1388 1389 1405 1404 1406 1407 1403 1402 1400 1401 1393 1392 1394 1395 1399 1398 1396 1397 1333 1332 1334 1335 1331 1330 1328 1329 1337 1336 1338 1339 1343 1342 1340 1341 1325 1324 1326 1327 1323 1322 1320 1321 1313 1312 1314 1315 1319 1318 1316 1317 1285 1284 1286 1287 1283 1282 1280 1281 1289 1288 1290 1291 1295 1294 1292 1293 1309 1308 1310 1311 1307 1306 1304 1305 1297 1296 1298 1299 1303 1302 1300 1301 1813 1812 1814 1815 1811 1810 1808 1809 1817 1816 1818 1819 1823 1822 1820 1821 1805 1804 1806 1807 1803 1802 1800 1801 1793 1792 1794 1795 1799 1798 1796 1797 1829 1828 1830 1831 1827 1826 1824 1825 1833 1832 1834 1835 1839 1838 1836 1837 1853 1852 1854 1855 1851 1850 1848 1849 1841 1840 1842 1843 1847 1846 1844 1845 1909 1908 1910 1911 1907 1906 1904 1905 1913 1912 1914 1915 1919 1918 1916 1917 1901 1900 1902 1903 1899 1898 1896 1897 1889 1888 1890 1891 1895 1894 1892 1893 1861 1860 1862 1863 1859 1858 1856 1857 1865 1864 1866 1867 1871 1870 1868 1869 1885 1884 1886 1887 1883 1882 1880 1881 1873 1872 1874 1875 1879 1878 1876 1877 2005 2004 2006 2007 2003 2002 2000 2001 2009 2008 2010 2011 2015 2014 2012 2013 1997 1996 1998 1999 1995 1994 1992 1993 1985 1984 1986 1987 1991 1990 1988 1989 2021 2020 2022 2023 2019 2018 2016 2017 2025 2024 2026 2027 2031 2030 2028 2029 2045 2044 2046 2047 2043 2042 2040 2041 2033 2032 2034 2035 2039 2038 2036 2037 1973 1972 1974 1975 1971 1970 1968 1969 1977 1976 1978 1979 1983 1982 1980 1981 1965 1964 1966 1967 1963 1962 1960 1961 1953 1952 1954 1955 1959 1958 1956 1957 1925 1924 1926 1927 1923 1922 1920 1921 1929 1928 1930 1931 1935 1934 1932 1933 1949 1948 1950 1951 1947 1946 1944 1945 1937 1936 1938 1939 1943 1942 1940 1941 1685 1684 1686 1687 1683 1682 1680 1681 1689 1688 1690 1691 1695 1694 1692 1693 1677 1676 1678 1679 1675 1674 1672 1673 1665 1664 1666 1667 1671 1670 1668 1669 1701 1700 1702 1703 1699 1698 1696 1697 1705 1704 1706 1707 1711 1710 1708 1709 1725 1724 1726 1727 1723 1722 1720 1721 1713 1712 1714 1715 1719 1718 1716 1717 1781 1780 1782 1783 1779 1778 1776 1777 1785 1784 1786 1787 1791 1790 1788 1789 1773 1772 1774 1775 1771 1770 1768 1769 1761 1760 1762 1763 1767 1766 1764 1765 1733 1732 1734 1735 1731 1730 1728 1729 1737 1736 1738 1739 1743 1742 1740 1741 1757 1756 1758 1759 1755 1754 1752 1753 1745 1744 1746 1747 1751 1750 1748 1749 1621 1620 1622 1623 1619 1618 1616 1617 1625 1624 1626 1627 1631 1630 1628 1629 1613 1612 1614 1615 1611 1610 1608 1609 1601 1600 1602 1603 1607 1606 1604 1605 1637 1636 1638 1639 1635 1634 1632 1633 1641 1640 1642 1643 1647 1646 1644 1645 1661 1660 1662 1663 1659 1658 1656 1657 1649 1648 1650 1651 1655 1654 1652 1653 1589 1588 1590 1591 1587 1586 1584 1585 1593 1592 1594 1595 1599 1598 1596 1597 1581 1580 1582 1583 1579 1578 1576 1577 1569 1568 1570 1571 1575 1574 1572 1573 1541 1540 1542 1543 1539 1538 1536 1537 1545 1544 1546 1547 1551 1550 1548 1549 1565 1564 1566 1567 1563 1562 1560 1561 1553 1552 1554 1555 1559 1558 1556 1557 5653 5652 5654 5655 5651 5650 5648 5649 5657 5656 5658 5659 5663 5662 5660 5661 5645 5644 5646 5647 5643 5642 5640 5641 5633 5632 5634 5635 5639 5638 5636 5637 5669 5668 5670 5671 5667 5666 5664 5665 5673 5672 5674 5675 5679 5678 5676 5677 5693 5692 5694 5695 5691 5690 5688 5689 5681 5680 5682 5683 5687 5686 5684 5685 5749 5748 5750 5751 5747 5746 5744 5745 5753 5752 5754 5755 5759 5758 5756 5757 5741 5740 5742 5743 5739 5738 5736 5737 5729 5728 5730 5731 5735 5734 5732 5733 5701 5700 5702 5703 5699 5698 5696 5697 5705 5704 5706 5707 5711 5710 5708 5709 5725 5724 5726 5727 5723 5722 5720 5721 5713 5712 5714 5715 5719 5718 5716 5717 5845 5844 5846 5847 5843 5842 5840 5841 5849 5848 5850 5851 5855 5854 5852 5853 5837 5836 5838 5839 5835 5834 5832 5833 5825 5824 5826 5827 5831 5830 5828 5829 5861 5860 5862 5863 5859 5858 5856 5857 5865 5864 5866 5867 5871 5870 5868 5869 5885 5884 5886 5887 5883 5882 5880 5881 5873 5872 5874 5875 5879 5878 5876 5877 5813 5812 5814 5815 5811 5810 5808 5809 5817 5816 5818 5819 5823 5822 5820 5821 5805 5804 5806 5807 5803 5802 5800 5801 5793 5792 5794 5795 5799 5798 5796 5797 5765 5764 5766 5767 5763 5762 5760 5761 5769 5768 5770 5771 5775 5774 5772 5773 5789 5788 5790 5791 5787 5786 5784 5785 5777 5776 5778 5779 5783 5782 5780 5781 6037 6036 6038 6039 6035 6034 6032 6033 6041 6040 6042 6043 6047 6046 6044 6045 6029 6028 6030 6031 6027 6026 6024 6025 6017 6016 6018 6019 6023 6022 6020 6021 6053 6052 6054 6055 6051 6050 6048 6049 6057 6056 6058 6059 6063 6062 6060 6061 6077 6076 6078 6079 6075 6074 6072 6073 6065 6064 6066 6067 6071 6070 6068 6069 6133 6132 6134 6135 6131 6130 6128 6129 6137 6136 6138 6139 6143 6142 6140 6141 6125 6124 6126 6127 6123 6122 6120 6121 6113 6112 6114 6115 6119 6118 6116 6117 6085 6084 6086 6087 6083 6082 6080 6081 6089 6088 6090 6091 6095 6094 6092 6093 6109 6108 6110 6111 6107 6106 6104 6105 6097 6096 6098 6099 6103 6102 6100 6101 5973 5972 5974 5975 5971 5970 5968 5969 5977 5976 5978 5979 5983 5982 5980 5981 5965 5964 5966 5967 5963 5962 5960 5961 5953 5952 5954 5955 5959 5958 5956 5957 5989 5988 5990 5991 5987 5986 5984 5985 5993 5992 5994 5995 5999 5998 5996 5997 6013 6012 6014 6015 6011 6010 6008 6009 6001 6000 6002 6003 6007 6006 6004 6005 5941 5940 5942 5943 5939 5938 5936 5937 5945 5944 5946 5947 5951 5950 5948 5949 5933 5932 5934 5935 5931 5930 5928 5929 5921 5920 5922 5923 5927 5926 5924 5925 5893 5892 5894 5895 5891 5890 5888 5889 5897 5896 5898 5899 5903 5902 5900 5901 5917 5916 5918 5919 5915 5914 5912 5913 5905 5904 5906 5907 5911 5910 5908 5909 4885 4884 4886 4887 4883 4882 4880 4881 4889 4888 4890 4891 4895 4894 4892 4893 4877 4876 4878 4879 4875 4874 4872 4873 4865 4864 4866 4867 4871 4870 4868 4869 4901 4900 4902 4903 4899 4898 4896 4897 4905 4904 4906 4907 4911 4910 4908 4909 4925 4924 4926 4927 4923 4922 4920 4921 4913 4912 4914 4915 4919 4918 4916 4917 4981 4980 4982 4983 4979 4978 4976 4977 4985 4984 4986 4987 4991 4990 4988 4989 4973 4972 4974 4975 4971 4970 4968 4969 4961 4960 4962 4963 4967 4966 4964 4965 4933 4932 4934 4935 4931 4930 4928 4929 4937 4936 4938 4939 4943 4942 4940 4941 4957 4956 4958 4959 4955 4954 4952 4953 4945 4944 4946 4947 4951 4950 4948 4949 5077 5076 5078 5079 5075 5074 5072 5073 5081 5080 5082 5083 5087 5086 5084 5085 5069 5068 5070 5071 5067 5066 5064 5065 5057 5056 5058 5059 5063 5062 5060 5061 5093 5092 5094 5095 5091 5090 5088 5089 5097 5096 5098 5099 5103 5102 5100 5101 5117 5116 5118 5119 5115 5114 5112 5113 5105 5104 5106 5107 5111 5110 5108 5109 5045 5044 5046 5047 5043 5042 5040 5041 5049 5048 5050 5051 5055 5054 5052 5053 5037 5036 5038 5039 5035 5034 5032 5033 5025 5024 5026 5027 5031 5030 5028 5029 4997 4996 4998 4999 4995 4994 4992 4993 5001 5000 5002 5003 5007 5006 5004 5005 5021 5020 5022 5023 5019 5018 5016 5017 5009 5008 5010 5011 5015 5014 5012 5013 4757 4756 4758 4759 4755 4754 4752 4753 4761 4760 4762 4763 4767 4766 4764 4765 4749 4748 4750 4751 4747 4746 4744 4745 4737 4736 4738 4739 4743 4742 4740 4741 4773 4772 4774 4775 4771 4770 4768 4769 4777 4776 4778 4779 4783 4782 4780 4781 4797 4796 4798 4799 4795 4794 4792 4793 4785 4784 4786 4787 4791 4790 4788 4789 4853 4852 4854 4855 4851 4850 4848 4849 4857 4856 4858 4859 4863 4862 4860 4861 4845 4844 4846 4847 4843 4842 4840 4841 4833 4832 4834 4835 4839 4838 4836 4837 4805 4804 4806 4807 4803 4802 4800 4801 4809 4808 4810 4811 4815 4814 4812 4813 4829 4828 4830 4831 4827 4826 4824 4825 4817 4816 4818 4819 4823 4822 4820 4821 4693 4692 4694 4695 4691 4690 4688 4689 4697 4696 4698 4699 4703 4702 4700 4701 4685 4684 4686 4687 4683 4682 4680 4681 4673 4672 4674 4675 4679 4678 4676 4677 4709 4708 4710 4711 4707 4706 4704 4705 4713 4712 4714 4715 4719 4718 4716 4717 4733 4732 4734 4735 4731 4730 4728 4729 4721 4720 4722 4723 4727 4726 4724 4725 4661 4660 4662 4663 4659 4658 4656 4657 4665 4664 4666 4667 4671 4670 4668 4669 4653 4652 4654 4655 4651 4650 4648 4649 4641 4640 4642 4643 4647 4646 4644 4645 4613 4612 4614 4615 4611 4610 4608 4609 4617 4616 4618 4619 4623 4622 4620 4621 4637 4636 4638 4639 4635 4634 4632 4633 4625 4624 4626 4627 4631 4630 4628 4629 6677 6676 6678 6679 6675 6674 6672 6673 6681 6680 6682 6683 6687 6686 6684 6685 6669 6668 6670 6671 6667 6666 6664 6665 6657 6656 6658 6659 6663 6662 6660 6661 6693 6692 6694 6695 6691 6690 6688 6689 6697 6696 6698 6699 6703 6702 6700 6701 6717 6716 6718 6719 6715 6714 6712 6713 6705 6704 6706 6707 6711 6710 6708 6709 6773 6772 6774 6775 6771 6770 6768 6769 6777 6776 6778 6779 6783 6782 6780 6781 6765 6764 6766 6767 6763 6762 6760 6761 6753 6752 6754 6755 6759 6758 6756 6757 6725 6724 6726 6727 6723 6722 6720 6721 6729 6728 6730 6731 6735 6734 6732 6733 6749 6748 6750 6751 6747 6746 6744 6745 6737 6736 6738 6739 6743 6742 6740 6741 6869 6868 6870 6871 6867 6866 6864 6865 6873 6872 6874 6875 6879 6878 6876 6877 6861 6860 6862 6863 6859 6858 6856 6857 6849 6848 6850 6851 6855 6854 6852 6853 6885 6884 6886 6887 6883 6882 6880 6881 6889 6888 6890 6891 6895 6894 6892 6893 6909 6908 6910 6911 6907 6906 6904 6905 6897 6896 6898 6899 6903 6902 6900 6901 6837 6836 6838 6839 6835 6834 6832 6833 6841 6840 6842 6843 6847 6846 6844 6845 6829 6828 6830 6831 6827 6826 6824 6825 6817 6816 6818 6819 6823 6822 6820 6821 6789 6788 6790 6791 6787 6786 6784 6785 6793 6792 6794 6795 6799 6798 6796 6797 6813 6812 6814 6815 6811 6810 6808 6809 6801 6800 6802 6803 6807 6806 6804 6805 7061 7060 7062 7063 7059 7058 7056 7057 7065 7064 7066 7067 7071 7070 7068 7069 7053 7052 7054 7055 7051 7050 7048 7049 7041 7040 7042 7043 7047 7046 7044 7045 7077 7076 7078 7079 7075 7074 7072 7073 7081 7080 7082 7083 7087 7086 7084 7085 7101 7100 7102 7103 7099 7098 7096 7097 7089 7088 7090 7091 7095 7094 7092 7093 7157 7156 7158 7159 7155 7154 7152 7153 7161 7160 7162 7163 7167 7166 7164 7165 7149 7148 7150 7151 7147 7146 7144 7145 7137 7136 7138 7139 7143 7142 7140 7141 7109 7108 7110 7111 7107 7106 7104 7105 7113 7112 7114 7115 7119 7118 7116 7117 7133 7132 7134 7135 7131 7130 7128 7129 7121 7120 7122 7123 7127 7126 7124 7125 6997 6996 6998 6999 6995 6994 6992 6993 7001 7000 7002 7003 7007 7006 7004 7005 6989 6988 6990 6991 6987 6986 6984 6985 6977 6976 6978 6979 6983 6982 6980 6981 7013 7012 7014 7015 7011 7010 7008 7009 7017 7016 7018 7019 7023 7022 7020 7021 7037 7036 7038 7039 7035 7034 7032 7033 7025 7024 7026 7027 7031 7030 7028 7029 6965 6964 6966 6967 6963 6962 6960 6961 6969 6968 6970 6971 6975 6974 6972 6973 6957 6956 6958 6959 6955 6954 6952 6953 6945 6944 6946 6947 6951 6950 6948 6949 6917 6916 6918 6919 6915 6914 6912 6913 6921 6920 6922 6923 6927 6926 6924 6925 6941 6940 6942 6943 6939 6938 6936 6937 6929 6928 6930 6931 6935 6934 6932 6933 7957 7956 7958 7959 7955 7954 7952 7953 7961 7960 7962 7963 7967 7966 7964 7965 7949 7948 7950 7951 7947 7946 7944 7945 7937 7936 7938 7939 7943 7942 7940 7941 7973 7972 7974 7975 7971 7970 7968 7969 7977 7976 7978 7979 7983 7982 7980 7981 7997 7996 7998 7999 7995 7994 7992 7993 7985 7984 7986 7987 7991 7990 7988 7989 8053 8052 8054 8055 8051 8050 8048 8049 8057 8056 8058 8059 8063 8062 8060 8061 8045 8044 8046 8047 8043 8042 8040 8041 8033 8032 8034 8035 8039 8038 8036 8037 8005 8004 8006 8007 8003 8002 8000 8001 8009 8008 8010 8011 8015 8014 8012 8013 8029 8028 8030 8031 8027 8026 8024 8025 8017 8016 8018 8019 8023 8022 8020 8021 8149 8148 8150 8151 8147 8146 8144 8145 8153 8152 8154 8155 8159 8158 8156 8157 8141 8140 8142 8143 8139 8138 8136 8137 8129 8128 8130 8131 8135 8134 8132 8133 8165 8164 8166 8167 8163 8162 8160 8161 8169 8168 8170 8171 8175 8174 8172 8173 8189 8188 8190 8191 8187 8186 8184 8185 8177 8176 8178 8179 8183 8182 8180 8181 8117 8116 8118 8119 8115 8114 8112 8113 8121 8120 8122 8123 8127 8126 8124 8125 8109 8108 8110 8111 8107 8106 8104 8105 8097 8096 8098 8099 8103 8102 8100 8101 8069 8068 8070 8071 8067 8066 8064 8065 8073 8072 8074 8075 8079 8078 8076 8077 8093 8092 8094 8095 8091 8090 8088 8089 8081 8080 8082 8083 8087 8086 8084 8085 7829 7828 7830 7831 7827 7826 7824 7825 7833 7832 7834 7835 7839 7838 7836 7837 7821 7820 7822 7823 7819 7818 7816 7817 7809 7808 7810 7811 7815 7814 7812 7813 7845 7844 7846 7847 7843 7842 7840 7841 7849 7848 7850 7851 7855 7854 7852 7853 7869 7868 7870 7871 7867 7866 7864 7865 7857 7856 7858 7859 7863 7862 7860 7861 7925 7924 7926 7927 7923 7922 7920 7921 7929 7928 7930 7931 7935 7934 7932 7933 7917 7916 7918 7919 7915 7914 7912 7913 7905 7904 7906 7907 7911 7910 7908 7909 7877 7876 7878 7879 7875 7874 7872 7873 7881 7880 7882 7883 7887 7886 7884 7885 7901 7900 7902 7903 7899 7898 7896 7897 7889 7888 7890 7891 7895 7894 7892 7893 7765 7764 7766 7767 7763 7762 7760 7761 7769 7768 7770 7771 7775 7774 7772 7773 7757 7756 7758 7759 7755 7754 7752 7753 7745 7744 7746 7747 7751 7750 7748 7749 7781 7780 7782 7783 7779 7778 7776 7777 7785 7784 7786 7787 7791 7790 7788 7789 7805 7804 7806 7807 7803 7802 7800 7801 7793 7792 7794 7795 7799 7798 7796 7797 7733 7732 7734 7735 7731 7730 7728 7729 7737 7736 7738 7739 7743 7742 7740 7741 7725 7724 7726 7727 7723 7722 7720 7721 7713 7712 7714 7715 7719 7718 7716 7717 7685 7684 7686 7687 7683 7682 7680 7681 7689 7688 7690 7691 7695 7694 7692 7693 7709 7708 7710 7711 7707 7706 7704 7705 7697 7696 7698 7699 7703 7702 7700 7701 7189 7188 7190 7191 7187 7186 7184 7185 7193 7192 7194 7195 7199 7198 7196 7197 7181 7180 7182 7183 7179 7178 7176 7177 7169 7168 7170 7171 7175 7174 7172 7173 7205 7204 7206 7207 7203 7202 7200 7201 7209 7208 7210 7211 7215 7214 7212 7213 7229 7228 7230 7231 7227 7226 7224 7225 7217 7216 7218 7219 7223 7222 7220 7221 7285 7284 7286 7287 7283 7282 7280 7281 7289 7288 7290 7291 7295 7294 7292 7293 7277 7276 7278 7279 7275 7274 7272 7273 7265 7264 7266 7267 7271 7270 7268 7269 7237 7236 7238 7239 7235 7234 7232 7233 7241 7240 7242 7243 7247 7246 7244 7245 7261 7260 7262 7263 7259 7258 7256 7257 7249 7248 7250 7251 7255 7254 7252 7253 7381 7380 7382 7383 7379 7378 7376 7377 7385 7384 7386 7387 7391 7390 7388 7389 7373 7372 7374 7375 7371 7370 7368 7369 7361 7360 7362 7363 7367 7366 7364 7365 7397 7396 7398 7399 7395 7394 7392 7393 7401 7400 7402 7403 7407 7406 7404 7405 7421 7420 7422 7423 7419 7418 7416 7417 7409 7408 7410 7411 7415 7414 7412 7413 7349 7348 7350 7351 7347 7346 7344 7345 7353 7352 7354 7355 7359 7358 7356 7357 7341 7340 7342 7343 7339 7338 7336 7337 7329 7328 7330 7331 7335 7334 7332 7333 7301 7300 7302 7303 7299 7298 7296 7297 7305 7304 7306 7307 7311 7310 7308 7309 7325 7324 7326 7327 7323 7322 7320 7321 7313 7312 7314 7315 7319 7318 7316 7317 7573 7572 7574 7575 7571 7570 7568 7569 7577 7576 7578 7579 7583 7582 7580 7581 7565 7564 7566 7567 7563 7562 7560 7561 7553 7552 7554 7555 7559 7558 7556 7557 7589 7588 7590 7591 7587 7586 7584 7585 7593 7592 7594 7595 7599 7598 7596 7597 7613 7612 7614 7615 7611 7610 7608 7609 7601 7600 7602 7603 7607 7606 7604 7605 7669 7668 7670 7671 7667 7666 7664 7665 7673 7672 7674 7675 7679 7678 7676 7677 7661 7660 7662 7663 7659 7658 7656 7657 7649 7648 7650 7651 7655 7654 7652 7653 7621 7620 7622 7623 7619 7618 7616 7617 7625 7624 7626 7627 7631 7630 7628 7629 7645 7644 7646 7647 7643 7642 7640 7641 7633 7632 7634 7635 7639 7638 7636 7637 7509 7508 7510 7511 7507 7506 7504 7505 7513 7512 7514 7515 7519 7518 7516 7517 7501 7500 7502 7503 7499 7498 7496 7497 7489 7488 7490 7491 7495 7494 7492 7493 7525 7524 7526 7527 7523 7522 7520 7521 7529 7528 7530 7531 7535 7534 7532 7533 7549 7548 7550 7551 7547 7546 7544 7545 7537 7536 7538 7539 7543 7542 7540 7541 7477 7476 7478 7479 7475 7474 7472 7473 7481 7480 7482 7483 7487 7486 7484 7485 7469 7468 7470 7471 7467 7466 7464 7465 7457 7456 7458 7459 7463 7462 7460 7461 7429 7428 7430 7431 7427 7426 7424 7425 7433 7432 7434 7435 7439 7438 7436 7437 7453 7452 7454 7455 7451 7450 7448 7449 7441 7440 7442 7443 7447 7446 7444 7445 6421 6420 6422 6423 6419 6418 6416 6417 6425 6424 6426 6427 6431 6430 6428 6429 6413 6412 6414 6415 6411 6410 6408 6409 6401 6400 6402 6403 6407 6406 6404 6405 6437 6436 6438 6439 6435 6434 6432 6433 6441 6440 6442 6443 6447 6446 6444 6445 6461 6460 6462 6463 6459 6458 6456 6457 6449 6448 6450 6451 6455 6454 6452 6453 6517 6516 6518 6519 6515 6514 6512 6513 6521 6520 6522 6523 6527 6526 6524 6525 6509 6508 6510 6511 6507 6506 6504 6505 6497 6496 6498 6499 6503 6502 6500 6501 6469 6468 6470 6471 6467 6466 6464 6465 6473 6472 6474 6475 6479 6478 6476 6477 6493 6492 6494 6495 6491 6490 6488 6489 6481 6480 6482 6483 6487 6486 6484 6485 6613 6612 6614 6615 6611 6610 6608 6609 6617 6616 6618 6619 6623 6622 6620 6621 6605 6604 6606 6607 6603 6602 6600 6601 6593 6592 6594 6595 6599 6598 6596 6597 6629 6628 6630 6631 6627 6626 6624 6625 6633 6632 6634 6635 6639 6638 6636 6637 6653 6652 6654 6655 6651 6650 6648 6649 6641 6640 6642 6643 6647 6646 6644 6645 6581 6580 6582 6583 6579 6578 6576 6577 6585 6584 6586 6587 6591 6590 6588 6589 6573 6572 6574 6575 6571 6570 6568 6569 6561 6560 6562 6563 6567 6566 6564 6565 6533 6532 6534 6535 6531 6530 6528 6529 6537 6536 6538 6539 6543 6542 6540 6541 6557 6556 6558 6559 6555 6554 6552 6553 6545 6544 6546 6547 6551 6550 6548 6549 6293 6292 6294 6295 6291 6290 6288 6289 6297 6296 6298 6299 6303 6302 6300 6301 6285 6284 6286 6287 6283 6282 6280 6281 6273 6272 6274 6275 6279 6278 6276 6277 6309 6308 6310 6311 6307 6306 6304 6305 6313 6312 6314 6315 6319 6318 6316 6317 6333 6332 6334 6335 6331 6330 6328 6329 6321 6320 6322 6323 6327 6326 6324 6325 6389 6388 6390 6391 6387 6386 6384 6385 6393 6392 6394 6395 6399 6398 6396 6397 6381 6380 6382 6383 6379 6378 6376 6377 6369 6368 6370 6371 6375 6374 6372 6373 6341 6340 6342 6343 6339 6338 6336 6337 6345 6344 6346 6347 6351 6350 6348 6349 6365 6364 6366 6367 6363 6362 6360 6361 6353 6352 6354 6355 6359 6358 6356 6357 6229 6228 6230 6231 6227 6226 6224 6225 6233 6232 6234 6235 6239 6238 6236 6237 6221 6220 6222 6223 6219 6218 6216 6217 6209 6208 6210 6211 6215 6214 6212 6213 6245 6244 6246 6247 6243 6242 6240 6241 6249 6248 6250 6251 6255 6254 6252 6253 6269 6268 6270 6271 6267 6266 6264 6265 6257 6256 6258 6259 6263 6262 6260 6261 6197 6196 6198 6199 6195 6194 6192 6193 6201 6200 6202 6203 6207 6206 6204 6205 6189 6188 6190 6191 6187 6186 6184 6185 6177 6176 6178 6179 6183 6182 6180 6181 6149 6148 6150 6151 6147 6146 6144 6145 6153 6152 6154 6155 6159 6158 6156 6157 6173 6172 6174 6175 6171 6170 6168 6169 6161 6160 6162 6163 6167 6166 6164 6165 4117 4116 4118 4119 4115 4114 4112 4113 4121 4120 4122 4123 4127 4126 4124 4125 4109 4108 4110 4111 4107 4106 4104 4105 4097 4096 4098 4099 4103 4102 4100 4101 4133 4132 4134 4135 4131 4130 4128 4129 4137 4136 4138 4139 4143 4142 4140 4141 4157 4156 4158 4159 4155 4154 4152 4153 4145 4144 4146 4147 4151 4150 4148 4149 4213 4212 4214 4215 4211 4210 4208 4209 4217 4216 4218 4219 4223 4222 4220 4221 4205 4204 4206 4207 4203 4202 4200 4201 4193 4192 4194 4195 4199 4198 4196 4197 4165 4164 4166 4167 4163 4162 4160 4161 4169 4168 4170 4171 4175 4174 4172 4173 4189 4188 4190 4191 4187 4186 4184 4185 4177 4176 4178 4179 4183 4182 4180 4181 4309 4308 4310 4311 4307 4306 4304 4305 4313 4312 4314 4315 4319 4318 4316 4317 4301 4300 4302 4303 4299 4298 4296 4297 4289 4288 4290 4291 4295 4294 4292 4293 4325 4324 4326 4327 4323 4322 4320 4321 4329 4328 4330 4331 4335 4334 4332 4333 4349 4348 4350 4351 4347 4346 4344 4345 4337 4336 4338 4339 4343 4342 4340 4341 4277 4276 4278 4279 4275 4274 4272 4273 4281 4280 4282 4283 4287 4286 4284 4285 4269 4268 4270 4271 4267 4266 4264 4265 4257 4256 4258 4259 4263 4262 4260 4261 4229 4228 4230 4231 4227 4226 4224 4225 4233 4232 4234 4235 4239 4238 4236 4237 4253 4252 4254 4255 4251 4250 4248 4249 4241 4240 4242 4243 4247 4246 4244 4245 4501 4500 4502 4503 4499 4498 4496 4497 4505 4504 4506 4507 4511 4510 4508 4509 4493 4492 4494 4495 4491 4490 4488 4489 4481 4480 4482 4483 4487 4486 4484 4485 4517 4516 4518 4519 4515 4514 4512 4513 4521 4520 4522 4523 4527 4526 4524 4525 4541 4540 4542 4543 4539 4538 4536 4537 4529 4528 4530 4531 4535 4534 4532 4533 4597 4596 4598 4599 4595 4594 4592 4593 4601 4600 4602 4603 4607 4606 4604 4605 4589 4588 4590 4591 4587 4586 4584 4585 4577 4576 4578 4579 4583 4582 4580 4581 4549 4548 4550 4551 4547 4546 4544 4545 4553 4552 4554 4555 4559 4558 4556 4557 4573 4572 4574 4575 4571 4570 4568 4569 4561 4560 4562 4563 4567 4566 4564 4565 4437 4436 4438 4439 4435 4434 4432 4433 4441 4440 4442 4443 4447 4446 4444 4445 4429 4428 4430 4431 4427 4426 4424 4425 4417 4416 4418 4419 4423 4422 4420 4421 4453 4452 4454 4455 4451 4450 4448 4449 4457 4456 4458 4459 4463 4462 4460 4461 4477 4476 4478 4479 4475 4474 4472 4473 4465 4464 4466 4467 4471 4470 4468 4469 4405 4404 4406 4407 4403 4402 4400 4401 4409 4408 4410 4411 4415 4414 4412 4413 4397 4396 4398 4399 4395 4394 4392 4393 4385 4384 4386 4387 4391 4390 4388 4389 4357 4356 4358 4359 4355 4354 4352 4353 4361 4360 4362 4363 4367 4366 4364 4365 4381 4380 4382 4383 4379 4378 4376 4377 4369 4368 4370 4371 4375 4374 4372 4373 5397 5396 5398 5399 5395 5394 5392 5393 5401 5400 5402 5403 5407 5406 5404 5405 5389 5388 5390 5391 5387 5386 5384 5385 5377 5376 5378 5379 5383 5382 5380 5381 5413 5412 5414 5415 5411 5410 5408 5409 5417 5416 5418 5419 5423 5422 5420 5421 5437 5436 5438 5439 5435 5434 5432 5433 5425 5424 5426 5427 5431 5430 5428 5429 5493 5492 5494 5495 5491 5490 5488 5489 5497 5496 5498 5499 5503 5502 5500 5501 5485 5484 5486 5487 5483 5482 5480 5481 5473 5472 5474 5475 5479 5478 5476 5477 5445 5444 5446 5447 5443 5442 5440 5441 5449 5448 5450 5451 5455 5454 5452 5453 5469 5468 5470 5471 5467 5466 5464 5465 5457 5456 5458 5459 5463 5462 5460 5461 5205 5204 5206 5207 5203 5202 5200 5201 5209 5208 5210 5211 5215 5214 5212 5213 5197 5196 5198 5199 5195 5194 5192 5193 5185 5184 5186 5187 5191 5190 5188 5189 5221 5220 5222 5223 5219 5218 5216 5217 5225 5224 5226 5227 5231 5230 5228 5229 5245 5244 5246 5247 5243 5242 5240 5241 5233 5232 5234 5235 5239 5238 5236 5237 5173 5172 5174 5175 5171 5170 5168 5169 5177 5176 5178 5179 5183 5182 5180 5181 5165 5164 5166 5167 5163 5162 5160 5161 5153 5152 5154 5155 5159 5158 5156 5157 5125 5124 5126 5127 5123 5122 5120 5121 5129 5128 5130 5131 5135 5134 5132 5133 5149 5148 5150 5151 5147 5146 5144 5145 5137 5136 5138 5139 5143 5142 5140 5141 5269 5268 5270 5271 5267 5266 5264 5265 5273 5272 5274 5275 5279 5278 5276 5277 5261 5260 5262 5263 5259 5258 5256 5257 5249 5248 5250 5251 5255 5254 5252 5253 5285 5284 5286 5287 5283 5282 5280 5281 5289 5288 5290 5291 5295 5294 5292 5293 5309 5308 5310 5311 5307 5306 5304 5305 5297 5296 5298 5299 5303 5302 5300 5301 5365 5364 5366 5367 5363 5362 5360 5361 5369 5368 5370 5371 5375 5374 5372 5373 5357 5356 5358 5359 5355 5354 5352 5353 5345 5344 5346 5347 5351 5350 5348 5349 5317 5316 5318 5319 5315 5314 5312 5313 5321 5320 5322 5323 5327 5326 5324 5325 5341 5340 5342 5343 5339 5338 5336 5337 5329 5328 5330 5331 5335 5334 5332 5333 5589 5588 5590 5591 5587 5586 5584 5585 5593 5592 5594 5595 5599 5598 5596 5597 5581 5580 5582 5583 5579 5578 5576 5577 5569 5568 5570 5571 5575 5574 5572 5573 5605 5604 5606 5607 5603 5602 5600 5601 5609 5608 5610 5611 5615 5614 5612 5613 5629 5628 5630 5631 5627 5626 5624 5625 5617 5616 5618 5619 5623 5622 5620 5621 5557 5556 5558 5559 5555 5554 5552 5553 5561 5560 5562 5563 5567 5566 5564 5565 5549 5548 5550 5551 5547 5546 5544 5545 5537 5536 5538 5539 5543 5542 5540 5541 5509 5508 5510 5511 5507 5506 5504 5505 5521 5520 5522 5523 5527 5526 5524 5525 5533 5532 5534 5535 5531 5530 5528 5529 5513 5515 5519 5517 5516 5518 5514 5512

■参照サイト
AtCoder Grand Contest 031

2021年10月14日

C++ の動作確認をしてみた（５５７）

C++の練習を兼ねて, AtCoder Beginner Contest 222 の問題C (Swiss-System Tournament) ～問題D (Between Two Arrays) を解いてみた.

■感想.
1. 問題C, Dは, 方針が見えたので, AC版に到達出来たと思う.
2. 問題D で, 苦手なdpの訓練を積めたことが非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 222 解説の各リンクをご覧下さい.

■C++版プログラム(問題C／AC版).

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using vp = vector<P>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
#define all(x) x.begin(), x.end()
int a[101][101]; // {グー, チョキ, パー} = {1, 2, 3}.
int win[101];    // 勝数.

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, 2 * N){
        char c[101];
        scanf("%s", c);
        rep(j, M){
            if(c[j] == 'G') a[i][j] = 1;
            if(c[j] == 'C') a[i][j] = 2;
            if(c[j] == 'P') a[i][j] = 3;
        }
    }
    
    // 2. ラウンドごとに勝敗を確認.
    vp ans;
    rep(i, M + 1){
        // 2-1. 勝数 と プレイヤー を 保存.
        vp cur;
        rep(j, 2 * N) cur.pb({win[j], j});
        
        // 2-2. sort.
        // -> 勝数が多い人ほど, 順位が高くなるように並べ替える.
        sort(all(cur));
        
        // 2-3. 終了条件.
        if(i == M){
            ans = cur;
            break;
        }
        
        // 2-4. 試合.
        rep(j, N){
            int p = cur[j * 2 + 0].b;
            int q = cur[j * 2 + 1].b;
            int d = (3 + a[p][i] - a[q][i]) % 3;
            
            // 引き分け.
            if(d == 0) continue;
            
            // p が q に 勝利.
            if(d == 2) win[p]--;
            
            // q が p に 勝利.
            if(d == 1) win[q]--;
        }
    }
    
    // 3. 出力.
    rep(i, 2 * N) printf("%d\n", ans[i].b + 1);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vp = vector<P>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

#define a first

#define b second

#define all(x) x.begin(), x.end()

int a[101][101]; // {グー, チョキ, パー} = {1, 2, 3}.

int win[101]; // 勝数.

int main(){

// 1. 入力情報.

int N, M;

scanf("%d %d", &N, &M);

rep(i, 2 * N){

char c[101];

scanf("%s", c);

rep(j, M){

if(c[j] == 'G') a[i][j] = 1;

if(c[j] == 'C') a[i][j] = 2;

if(c[j] == 'P') a[i][j] = 3;

}

// 2. ラウンドごとに勝敗を確認.

vp ans;

rep(i, M + 1){

// 2-1. 勝数とプレイヤーを保存.

vp cur;

rep(j, 2 * N) cur.pb({win[j], j});

// 2-2. sort.

// -> 勝数が多い人ほど, 順位が高くなるように並べ替える.

sort(all(cur));

// 2-3. 終了条件.

if(i == M){

ans = cur;

break;

}

// 2-4. 試合.

rep(j, N){

int p = cur[j * 2 + 0].b;

int q = cur[j * 2 + 1].b;

int d = (3 + a[p][i] - a[q][i]) % 3;

// 引き分け.

if(d == 0) continue;

// p が q に勝利.

if(d == 2) win[p]--;

// q が p に勝利.

if(d == 1) win[q]--;

}

// 3. 出力.

rep(i, 2 * N) printf("%d\n", ans[i].b + 1);

return 0;

}

[入力例]
2 3
GCP
PPP
CCC
PPC

[出力例]
3
1
2
4
※AtCoderテストケースより

[入力例]
2 2
GC
PG
CG
PP

[出力例]
1
2
3
4
※AtCoderテストケースより

[入力例]
5 5
CPGPG
CCCCC
GGCPC
PPPCP
CGCPP
PGGPG
CGCGP
GCPCC
PPGPC
PCGCP

[出力例]
8
3
4
5
9
10
1
6
7
2

[入力例]
10 12
CPPCCPPGCGCC
CPCGCGPPPCPP
PGCCCGCPCGPC
CPGGGPGCGGGC
GCGPPPCCPPPC
PGCCCCGCPCGP
PCCGPPPPCGGG
CGPPCCPGCPCG
CCCGPGGPCCCP
CCPGGPCCPCGG
GCPGPGPCCGGC
PCPCCGPPPCGP
CCGCCCCCPCGG
GGPGGGPPCGGC
CGCCCCGGCGPC
PGPGGPCPCPCP
CCGCGCGPPCPG
CCPGGGCGCCPC
GGCPGCPGGPGC
GGGCPPPCGGCG

[出力例]
8
7
11
18
3
4
16
2
5
6
10
14
15
17
9
12
19
13
20
1

[入力例]

2 3

GCP

PPP

CCC

PPC

[出力例]

※AtCoderテストケースより

[入力例]

2 2

[出力例]

※AtCoderテストケースより

[入力例]

5 5

CPGPG

CCCCC

GGCPC

PPPCP

CGCPP

PGGPG

CGCGP

GCPCC

PPGPC

PCGCP

[出力例]

[入力例]

10 12

CPPCCPPGCGCC

CPCGCGPPPCPP

PGCCCGCPCGPC

CPGGGPGCGGGC

GCGPPPCCPPPC

PGCCCCGCPCGP

PCCGPPPPCGGG

CGPPCCPGCPCG

CCCGPGGPCCCP

CCPGGPCCPCGG

GCPGPGPCCGGC

PCPCCGPPPCGP

CCGCCCCCPCGG

GGPGGGPPCGGC

CGCCCCGGCGPC

PGPGGPCPCPCP

CCGCGCGPPCPG

CCPGGGCGCCPC

GGCPGCPGGPGC

GGGCPPPCGGCG

[出力例]

■C++版プログラム(問題D／AC版).

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 998244353;
int a[3030], b[3030];
LL dp[3030][3030]; // {項番, cの値}.

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    rep(i, N) scanf("%d", &b[i]);
    
    // 2. 整数列 C の ありうる個数は？
    // 2-1. 初期化.
    repx(c, a[0], b[0] + 1) dp[0][c] = 1;
    rep(c, 3029){
        dp[0][c + 1] += dp[0][c];
        dp[0][c + 1] %= MOD;
    }
    
    // 2-2. dp更新.
    repx(i, 1, N){
        // (i - 1)番目 から i番目へ.
        repx(c, a[i], b[i] + 1){
            dp[i][c] += dp[i - 1][c];
            dp[i][c] %= MOD;
        }
        
        // 累積和.
        rep(c, 3029){
            dp[i][c + 1] += dp[i][c];
            dp[i][c + 1] %= MOD;
        }
    }
    
    // 3. 出力.
    printf("%lld", dp[N - 1][b[N - 1]]);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

const LL MOD = 998244353;

int a[3030], b[3030];

LL dp[3030][3030]; // {項番, cの値}.

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%d", &a[i]);

rep(i, N) scanf("%d", &b[i]);

// 2. 整数列 C のありうる個数は？

// 2-1. 初期化.

repx(c, a[0], b[0] + 1) dp[0][c] = 1;

rep(c, 3029){

dp[0][c + 1] += dp[0][c];

dp[0][c + 1] %= MOD;

}

// 2-2. dp更新.

repx(i, 1, N){

// (i - 1)番目から i番目へ.

repx(c, a[i], b[i] + 1){

dp[i][c] += dp[i - 1][c];

dp[i][c] %= MOD;

}

// 累積和.

rep(c, 3029){

dp[i][c + 1] += dp[i][c];

dp[i][c + 1] %= MOD;

}

// 3. 出力.

printf("%lld", dp[N - 1][b[N - 1]]);

return 0;

}

[入力例]
2
1 1
2 3

[出力例]
5
※AtCoderテストケースより

[入力例]
3
2 2 2
2 2 2

[出力例]
1
※AtCoderテストケースより

[入力例]
10
1 2 3 4 5 6 7 8 9 10
1 4 9 16 25 36 49 64 81 100

[出力例]
978222082
※AtCoderテストケースより

[入力例]
5
0 1 5 6 7
0 3 8 9 11

[出力例]
159

[入力例]
7
0 1 2 6 10 10 14
0 1 5 7 11 15 17

[出力例]
336

[入力例]
10
1 2 5 7 11 13 15 18 18 18
2 5 9 13 14 15 18 22 25 27

[出力例]
1670080

[入力例]
25
1 2 6 10 13 13 13 16 17 18 22 23 27 29 32 35 39 42 42 42 44 48 52 56 59
2 6 8 11 15 19 21 22 26 27 31 33 33 33 33 38 41 44 46 48 52 55 59 61 61

[出力例]
494538601

[入力例]

1 1

2 3

[出力例]

※AtCoderテストケースより

[入力例]

2 2 2

[出力例]

※AtCoderテストケースより

[入力例]

1 2 3 4 5 6 7 8 9 10

1 4 9 16 25 36 49 64 81 100

[出力例]

978222082

※AtCoderテストケースより

[入力例]

0 1 5 6 7

0 3 8 9 11

[出力例]

159

[入力例]

0 1 2 6 10 10 14

0 1 5 7 11 15 17

[出力例]

336

[入力例]

1 2 5 7 11 13 15 18 18 18

2 5 9 13 14 15 18 22 25 27

[出力例]

1670080

[入力例]

1 2 6 10 13 13 13 16 17 18 22 23 27 29 32 35 39 42 42 42 44 48 52 56 59

2 6 8 11 15 19 21 22 26 27 31 33 33 33 33 38 41 44 46 48 52 55 59 61 61

[出力例]

494538601

■参照サイト
エクサウィザーズプログラミングコンテスト2021（AtCoder Beginner Contest 222）

C++の練習を兼ねて, AtCoder Beginner Contest 224 の 問題C (Triangle?) ～ 問題D (8 Puzzle on Graph) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 223 の 問題F (Parenthesis Checking) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 223 の 問題E (Placing Rectangles) を解いてみた.

C++の練習を兼ねて, AtCoder Library Practice Contest の 問題G (SCC) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 038 の 問題C (LCMs) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 217 の 問題H (Snuketoon) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 223 の 問題C (Doukasen) ～ 問題D (Restricted Permutation) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 221 の 問題H (Count Multiset) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 031 の 問題C (Differ by 1 Bit) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 222 の 問題C (Swiss-System Tournament) ～ 問題D (Between Two Arrays) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 224 の問題C (Triangle?) ～問題D (8 Puzzle on Graph) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 223 の問題F (Parenthesis Checking) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 223 の問題E (Placing Rectangles) を解いてみた.

C++の練習を兼ねて, AtCoder Library Practice Contest の問題G (SCC) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 038 の問題C (LCMs) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 217 の問題H (Snuketoon) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 223 の問題C (Doukasen) ～問題D (Restricted Permutation) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 221 の問題H (Count Multiset) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 031 の問題C (Differ by 1 Bit) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 222 の問題C (Swiss-System Tournament) ～問題D (Between Two Arrays) を解いてみた.