12月, 2019 | 個人用メモ帳

2019年12月29日2020年2月29日

C++ の動作確認をしてみた（１４０）

C++の練習を兼ねて, AtCoder Beginner Contest 149 の問題D (D – Prediction and Restriction) を解いてみた.

■感想.
1. 回答の糸口までに, 時間かかってしまったものの, 何とかAC版となった.
2. まだまだ, 理解出来てないアルゴリズムが多いので, 非常に時間かかると思われるが, 過去問を通して, 少しずつ確認していきたいと思う.

本家のサイトABC 149解説をご覧下さい.

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

#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)
char T[101010];
int win[101010];

int main(){
    
    // 1. 入力情報.
    int N, K, R, S, P;
    scanf("%d %d %d %d %d", &N, &K, &R, &S, &P);
    scanf("%s", T);
    
    // 2. 勝利時の得点を集計.
    rep(i, N){
        if(T[i] == 'r') win[i] = P;
        if(T[i] == 's') win[i] = R;
        if(T[i] == 'p') win[i] = S;
    }
    
    // 3. 条件を満たすように得点を抽出.
    // -> K回前と同じだったら, 得点を加算しない.
    int ans = 0;
    rep(i, K) ans += win[i];
    repx(i, K, N){
        if(T[i] == 'r'){
            if(T[i - K] != 'r' || win[i - K] == 0) ans += P;
            else                                   win[i] = 0;
        }
        if(T[i] == 's'){
            if(T[i - K] != 's' || win[i - K] == 0) ans += R;
            else                                   win[i] = 0;
        }
        if(T[i] == 'p'){
            if(T[i - K] != 'p' || win[i - K] == 0) ans += S;
            else                                   win[i] = 0;
        }
    }
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

#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)

char T[101010];

int win[101010];

int main(){

// 1. 入力情報.

int N, K, R, S, P;

scanf("%d %d %d %d %d", &N, &K, &R, &S, &P);

scanf("%s", T);

// 2. 勝利時の得点を集計.

rep(i, N){

if(T[i] == 'r') win[i] = P;

if(T[i] == 's') win[i] = R;

if(T[i] == 'p') win[i] = S;

}

// 3. 条件を満たすように得点を抽出.

// -> K回前と同じだったら, 得点を加算しない.

int ans = 0;

rep(i, K) ans += win[i];

repx(i, K, N){

if(T[i] == 'r'){

if(T[i - K] != 'r' || win[i - K] == 0) ans += P;

else win[i] = 0;

}

if(T[i] == 's'){

if(T[i - K] != 's' || win[i - K] == 0) ans += R;

else win[i] = 0;

}

if(T[i] == 'p'){

if(T[i - K] != 'p' || win[i - K] == 0) ans += S;

else win[i] = 0;

}

// 4. 出力.

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

return 0;

}

[入力例]
5 2
8 7 6
rsrpr

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

[入力例]
7 1
100 10 1
ssssppr

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

[入力例]
30 5
325 234 123
rspsspspsrpspsppprpsprpssprpsr

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

[入力例]
60 5
543 432 321
pprrpprspsrrrrrrspppspssrpspsssrrppprpsprpssprpsrssssssspsss

[出力例]
20427

[入力例]
150 5
543 432 321
ppspspspsrrrpppprrsrrppssppssrrppsssppsspprrsssspprrpprspsrrrsssrrpppsrspppspssrpspsssrrppprpsprpssprpsrssssrpprrrpppssspprssspsppssrrrsspprrrssppprrp

[出力例]
51975

[入力例]

5 2

8 7 6

rsrpr

[出力例]

※AtCoderテストケースより

[入力例]

7 1

100 10 1

ssssppr

[出力例]

211

※AtCoderテストケースより

[入力例]

30 5

325 234 123

rspsspspsrpspsppprpsprpssprpsr

[出力例]

4996

※AtCoderテストケースより

[入力例]

60 5

543 432 321

pprrpprspsrrrrrrspppspssrpspsssrrppprpsprpssprpsrssssssspsss

[出力例]

20427

[入力例]

150 5

543 432 321

ppspspspsrrrpppprrsrrppssppssrrppsssppsspprrsssspprrpprspsrrrsssrrpppsrspppspssrpspsssrrppprpsprpssprpsrssssrpprrrpppssspprssspsppssrrrsspprrrssppprrp

[出力例]

51975

■参照サイト
AtCoder Beginner Contest 149

2019年12月29日

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

C++の練習を兼ねて, AtCoder Grand Contest 041 の問題A (A – Table Tennis Training) を解いてみた.

■感想.
1. 時間かかってしまったものの, 何とかAC版となった.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
    
    // 1. 入力情報.
    LL N, A, B;
    scanf("%lld %lld %lld", &N, &A, &B);
    
    // 2. 最小のラウンド数は？
    LL ans = 0;
    if((B - A) & 1){
        // 卓 1, N のうち, 近い方は？
        LL near = min(A - 1, N - B);
        
        // A, B の いずれかが, 卓 1, N に 到達し, 1回停止できるように勝敗をコントロール.
        ans = near + 1;
        
        // A, B が お互いに近づくように勝敗をコントロール.
        if(near == A - 1) ans += (B - near - 1) / 2;
        else              ans += (N - near - 1 - A) / 2;
    }else{
        ans = (B - A) / 2;
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main(){

// 1. 入力情報.

LL N, A, B;

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

// 2. 最小のラウンド数は？

LL ans = 0;

if((B - A) & 1){

// 卓 1, N のうち, 近い方は？

LL near = min(A - 1, N - B);

// A, B のいずれかが, 卓 1, N に到達し, 1回停止できるように勝敗をコントロール.

ans = near + 1;

// A, B がお互いに近づくように勝敗をコントロール.

if(near == A - 1) ans += (B - near - 1) / 2;

else ans += (N - near - 1 - A) / 2;

}else{

ans = (B - A) / 2;

}

// 3. 出力.

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

return 0;

}

[入力例]
5 2 4

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

[入力例]
5 2 3

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

[入力例]
7 2 7

[出力例]
3
※ A, B は, 以下のように動けば良さそう(w: 勝利, l: 敗北).
A: l(3) -> l(4) -> l(5)
B: l(7) -> w(6) -> w(5)

[入力例]
9 2 7

[出力例]
4
※ A, B は, 以下のように動けば良さそう(w: 勝利, l: 敗北).
A: w(1) -> w(1) -> l(2) -> l(3)
B: w(6) -> w(5) -> w(4) -> w(3)

[入力例]
10 5 8

[出力例]
4
※ A, B は, 以下のように動けば良さそう(w: 勝利, l: 敗北).
A: l(6) -> l(7)  -> l(8)  -> l(9)
B: l(9) -> l(10) -> l(10) -> w(9)

[入力例]
10000000000 12345678 23456789

[出力例]
17901233

[入力例]
10000000000 7890123456 8901234567

[出力例]
1604320989

[入力例]

5 2 4

[出力例]

※AtCoderテストケースより

[入力例]

5 2 3

[出力例]

※AtCoderテストケースより

[入力例]

7 2 7

[出力例]

※ A, B は, 以下のように動けば良さそう(w: 勝利, l: 敗北).

A: l(3) -> l(4) -> l(5)

B: l(7) -> w(6) -> w(5)

[入力例]

9 2 7

[出力例]

※ A, B は, 以下のように動けば良さそう(w: 勝利, l: 敗北).

A: w(1) -> w(1) -> l(2) -> l(3)

B: w(6) -> w(5) -> w(4) -> w(3)

[入力例]

10 5 8

[出力例]

※ A, B は, 以下のように動けば良さそう(w: 勝利, l: 敗北).

A: l(6) -> l(7) -> l(8) -> l(9)

B: l(9) -> l(10) -> l(10) -> w(9)

[入力例]

10000000000 12345678 23456789

[出力例]

17901233

[入力例]

10000000000 7890123456 8901234567

[出力例]

1604320989

■参照サイト
AtCoder Grand Contest 041

2019年12月25日

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

C++の練習を兼ねて, AtCoder Beginner Contest 148 の問題F (F – Playing Tag on Tree) を解いてみた.

■感想.
1. 解答の糸口(※中間地点を考慮する必要があること)に気付くまでに時間かかったものの, 何とかAC版となった.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイトABC 148解説をご覧下さい.

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

// コメント修正して, 再提出.
#include <bits/stdc++.h>
using namespace std;
using vvi = vector<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 pb push_back
int du[101010], dv[101010], duv[101010]; // 距離を保存

// グラフを幅優先探索する.
// https://ja.wikipedia.org/wiki/幅優先探索
// ※bfsの動作確認用.
// @param G: グラフ.
// @param s: グラフの探索開始頂点.
// @param d: 探索開始地点からの距離.
// @return: 特に無し.
void bfs(vvi &G, int s, int* d){
    
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. 訪問済みフラグ設定.
    // ※スタート地点は, 距離ゼロを指定.
    d[s] = 0;
    
    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    while(!q.empty()){
        
        // 4. キューから取り出す.
        int u = q.front();
        q.pop();
        
        // 5. 取り出した要素を処理.
        for(auto &e : G[u]){
            
            // 6. 訪問済であれば, 処理をスキップ.
            if(d[e] > 0)            continue;
            if(d[e] == 0 && e != s) d[e] = d[u] + 1, q.push(e);
        }
    }
    return;
}

int main(){
    
    // 1. 入力情報.
    int N, u, v;
    scanf("%d %d %d", &N, &u, &v);
    u--, v--;
    vvi G(N);
    rep(i, N - 1){
        int a, b;
        scanf("%d %d", &a, &b);
        a--, b--;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 頂点 u, v から 各頂点までの距離を計算.
    bfs(G, u, du);
    bfs(G, v, dv);
    
    // 3. 頂点 u, v の 中間地点 m を 取得.
    // -> 但し, 中間地点については, 頂点 u, v の 間の距離 du[v] が, 
    // 偶数 か 奇数 で 変わってくる点を考慮する必要があるっぽい.
    // [偶数の場合(du[v] = 8)]
    // ex.
    // 24 17 6
    // 1 2
    // 2 3
    // 11 2
    // 12 11
    // 4 3
    // 4 5
    // 4 6
    // 7 6
    // 8 7
    // 9 3
    // 13 12
    // 9 10
    // 14 12
    // 14 16
    // 14 15
    // 16 17
    // 17 18
    // 15 19
    // 19 24
    // 20 19
    // 20 21
    // 21 22
    // 23 22
    // -> 11 が 正解のはず.
    // 
    // [奇数の場合(du[v] = 3)]
    // ex.
    // 9 5 2
    // 1 2
    // 7 9
    // 7 4
    // 6 5
    // 5 4
    // 8 3
    // 4 3
    // 3 2
    // -> 3 が 正解のはず.
    int m = -1, dm = du[v] / 2;
    rep(i, N){
        if(du[v] % 2 == 0){
            if(du[i] == dm && dv[i] == dm){
                m = i;
                break;
            }
        }else{
            if(du[i] == dm && dv[i] == dm + 1){
                m = i;
                break;
            }
        }
    }
    
    // 4. 頂点 m から 各頂点までの距離を計算.
    bfs(G, m, duv);
    
    // 5. 頂点 m から 最も遠い頂点 f を 取得.
    // ※ 但し, 頂点 v よりも 頂点 u に近いものに限定.
    int f = -1, df = 0;
    rep(i, N){
        if(df < duv[i] && du[i] < dv[i]) f = i, df = max(df, duv[i]);
    }
    
    // 6. 出力.
    printf("%d\n", duv[v] + duv[f] - 1);
    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

// コメント修正して, 再提出.

#include <bits/stdc++.h>

using namespace std;

using vvi = vector<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 pb push_back

int du[101010], dv[101010], duv[101010]; // 距離を保存

// グラフを幅優先探索する.

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

// ※bfsの動作確認用.

// @param G: グラフ.

// @param s: グラフの探索開始頂点.

// @param d: 探索開始地点からの距離.

// @return: 特に無し.

void bfs(vvi &G, int s, int* d){

// 1. 空のキュー.

queue<int> q;

// 2. 訪問済みフラグ設定.

// ※スタート地点は, 距離ゼロを指定.

d[s] = 0;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

// 6. 訪問済であれば, 処理をスキップ.

if(d[e] > 0) continue;

if(d[e] == 0 && e != s) d[e] = d[u] + 1, q.push(e);

}

return;

}

int main(){

// 1. 入力情報.

int N, u, v;

scanf("%d %d %d", &N, &u, &v);

u--, v--;

vvi G(N);

rep(i, N - 1){

int a, b;

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

a--, b--;

G[a].pb(b);

G[b].pb(a);

}

// 2. 頂点 u, v から各頂点までの距離を計算.

bfs(G, u, du);

bfs(G, v, dv);

// 3. 頂点 u, v の中間地点 m を取得.

// -> 但し, 中間地点については, 頂点 u, v の間の距離 du[v] が,

// 偶数か奇数で変わってくる点を考慮する必要があるっぽい.

// [偶数の場合(du[v] = 8)]

// ex.

// 24 17 6

// 1 2

// 2 3

// 11 2

// 12 11

// 4 3

// 4 5

// 4 6

// 7 6

// 8 7

// 9 3

// 13 12

// 9 10

// 14 12

// 14 16

// 14 15

// 16 17

// 17 18

// 15 19

// 19 24

// 20 19

// 20 21

// 21 22

// 23 22

// -> 11 が正解のはず.

// [奇数の場合(du[v] = 3)]

// ex.

// 9 5 2

// 1 2

// 7 9

// 7 4

// 6 5

// 5 4

// 8 3

// 4 3

// 3 2

// -> 3 が正解のはず.

int m = -1, dm = du[v] / 2;

rep(i, N){

if(du[v] % 2 == 0){

if(du[i] == dm && dv[i] == dm){

m = i;

break;

}

}else{

if(du[i] == dm && dv[i] == dm + 1){

m = i;

break;

}

// 4. 頂点 m から各頂点までの距離を計算.

bfs(G, m, duv);

// 5. 頂点 m から最も遠い頂点 f を取得.

// ※ 但し, 頂点 v よりも頂点 u に近いものに限定.

int f = -1, df = 0;

rep(i, N){

if(df < duv[i] && du[i] < dv[i]) f = i, df = max(df, duv[i]);

}

// 6. 出力.

printf("%d\n", duv[v] + duv[f] - 1);

return 0;

}

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

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

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

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

[入力例]
2 1 2
1 2

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

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

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

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

[出力例]
11

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

[出力例]
14

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

[出力例]
3

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

[入力例]

5 4 1

1 2

2 3

3 4

3 5

[出力例]

※AtCoderテストケースより

[入力例]

5 4 5

1 2

1 3

1 4

1 5

[出力例]

※AtCoderテストケースより

[入力例]

2 1 2

1 2

[出力例]

※AtCoderテストケースより

[入力例]

9 6 1

1 2

2 3

3 4

4 5

5 6

4 7

7 8

8 9

[出力例]

※AtCoderテストケースより

[入力例]

24 17 6

1 2

2 3

11 2

12 11

4 3

4 5

4 6

7 6

8 7

9 3

13 12

9 10

14 12

14 16

14 15

16 17

17 18

15 19

19 24

20 19

20 21

21 22

23 22

[出力例]

[入力例]

33 21 3

32 33

30 31

28 29

31 32

30 28

24 28

1 2

2 3

3 4

4 5

4 7

7 6

9 8

9 7

10 9

12 10

10 11

14 11

14 13

15 14

16 15

17 18

15 17

19 18

20 17

21 20

21 22

22 23

24 20

25 24

26 25

27 26

[出力例]

[入力例]

9 5 2

1 2

7 9

7 4

6 5

5 4

8 3

4 3

3 2

[出力例]

■参照サイト
AtCoder Beginner Contest 148

2019年12月23日

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

C++の練習を兼ねて, AtCoder Beginner Contest 148 の問題E (E – Double Factorial) を解いてみた.

■感想.
1. 5 で何回割れるか見ることに気付いたので, 何とかAC版となった.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイトABC 148解説をご覧下さい.

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
    
    // 1. 入力情報.
    LL N, ans = 0;
    scanf("%lld", &N);
    
    // 2. 奇数ならば, 0.
    if(N & 1){
        puts("0");
        return 0;
    }
    
    // 3. 偶数の場合は, N / 2 を 5 で 割ったものを, 逐次加算.
    N >>= 1;
    while(N) ans += N / 5, N /= 5;
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main(){

// 1. 入力情報.

LL N, ans = 0;

scanf("%lld", &N);

// 2. 奇数ならば, 0.

if(N & 1){

puts("0");

return 0;

}

// 3. 偶数の場合は, N / 2 を 5 で割ったものを, 逐次加算.

N >>= 1;

while(N) ans += N / 5, N /= 5;

// 4. 出力.

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

return 0;

}

[入力例]
12

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

[入力例]
5

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

[入力例]
1000000000000000000

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

[入力例]
987654321098765432

[出力例]
123456790137345667

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

1000000000000000000

[出力例]

124999999999999995

※AtCoderテストケースより

[入力例]

987654321098765432

[出力例]

123456790137345667

■参照サイト
AtCoder Beginner Contest 148

2019年12月22日2019年12月23日

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

C++の練習を兼ねて, AtCoder Beginner Contest 148 の問題D (D – Brick Break) を解いてみた.

■感想.
1. 解説見る前に, AC版となったので良かったと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイトABC 148解説をご覧下さい.

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

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, 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 a first
#define b second
#define pb push_back
const int MAX = 202020;
int a[MAX];
vector<P> block;

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", a + i);
        block.pb({a[i], i});
    }
    
    // 2. sort.
    sort(block.begin(), block.end());
    // for(auto& p : block) printf("%d %d\n", p.a, p.b);
    
    // 3. レンガ を 1 2 ... K のように残すには？
    int res = 0, cur = 1, index = -1;
    for(auto& p : block){
        if(cur == p.a && p.b > index){
            // 残すレンガの数をインクリメント.
            res++;
            // 次のレンガを探すため, index更新.
            index = p.b;
            // 次のレンガを探すため, インクリメント.
            cur++;
        }
    }
    
    // 4. 出力.
    int ans = N - res;
    printf("%d\n", (ans == N) ? -1 : ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, 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 a first

#define b second

#define pb push_back

const int MAX = 202020;

int a[MAX];

vector<P> block;

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

scanf("%d", a + i);

block.pb({a[i], i});

}

// 2. sort.

sort(block.begin(), block.end());

// for(auto& p : block) printf("%d %d\n", p.a, p.b);

// 3. レンガを 1 2 ... K のように残すには？

int res = 0, cur = 1, index = -1;

for(auto& p : block){

if(cur == p.a && p.b > index){

// 残すレンガの数をインクリメント.

res++;

// 次のレンガを探すため, index更新.

index = p.b;

// 次のレンガを探すため, インクリメント.

cur++;

}

// 4. 出力.

int ans = N - res;

printf("%d\n", (ans == N) ? -1 : ans);

return 0;

}

[入力例]
3
2 1 2

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

[入力例]
3
2 2 2

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

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

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

[入力例]
1
1

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

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

[出力例]
12

[入力例]
250
93 14 45 33 97 76 1 7 96 2 55 31 97 91 74 3 76 17 15 18 38 4 94 52 85 62 69 5 39 89 6 39 80 78 79 39 9 76 7 97 50 95 62 29 70 21 17 99 6 46 7 43 14 8 4 89 16 72 58 60 14 14 9 94 11 82 9 31 9 69 56 10 11 95 93 24 51 37 65 12 66 81 75 52 87 36 19 11 61 19 10 13 80 29 17 13 83 14 75 95 42 26 36 15 95 87 34 31 16 84 74 99 60 72 19 17 94 20 95 47 66 85 92 8 4 31 39 44 18 84 95 34 34 17 96 17 27 61 18 31 34 14 39 5 92 26 51 19 22 81 88 20 89 48 41 54 20 89 31 20 65 3 14 23 76 33 28 63 4 83 31 14 72 29 83 21 29 16 22 15 23 33 20 61 93 27 79 23 4 51 19 23 79 68 24 8 84 24 60 11 24 75 15 55 33 94 66 16 54 14 44 67 81 86 78 11 83 62 85 95 9 84 25 10 89 23 82 76 58 22 71 88 99 85 40 72 74 99 52 70 82 48 72 22 39 67 59 80 14 23

[出力例]
225

[入力例]

2 1 2

[出力例]

※AtCoderテストケースより

[入力例]

2 2 2

[出力例]

-1

※AtCoderテストケースより

[入力例]

3 1 4 1 5 9 2 6 5 3

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7 5 6 7 8

[出力例]

[入力例]

250

93 14 45 33 97 76 1 7 96 2 55 31 97 91 74 3 76 17 15 18 38 4 94 52 85 62 69 5 39 89 6 39 80 78 79 39 9 76 7 97 50 95 62 29 70 21 17 99 6 46 7 43 14 8 4 89 16 72 58 60 14 14 9 94 11 82 9 31 9 69 56 10 11 95 93 24 51 37 65 12 66 81 75 52 87 36 19 11 61 19 10 13 80 29 17 13 83 14 75 95 42 26 36 15 95 87 34 31 16 84 74 99 60 72 19 17 94 20 95 47 66 85 92 8 4 31 39 44 18 84 95 34 34 17 96 17 27 61 18 31 34 14 39 5 92 26 51 19 22 81 88 20 89 48 41 54 20 89 31 20 65 3 14 23 76 33 28 63 4 83 31 14 72 29 83 21 29 16 22 15 23 33 20 61 93 27 79 23 4 51 19 23 79 68 24 8 84 24 60 11 24 75 15 55 33 94 66 16 54 14 44 67 81 86 78 11 83 62 85 95 9 84 25 10 89 23 82 76 58 22 71 88 99 85 40 72 74 99 52 70 82 48 72 22 39 67 59 80 14 23

[出力例]

225

■参照サイト
AtCoder Beginner Contest 148

C++の練習を兼ねて, AtCoder Beginner Contest 149 の 問題D (D – Prediction and Restriction) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 041 の 問題A (A – Table Tennis Training) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 148 の 問題F (F – Playing Tag on Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 148 の 問題E (E – Double Factorial) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 148 の 問題D (D – Brick Break) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 149 の問題D (D – Prediction and Restriction) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 041 の問題A (A – Table Tennis Training) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 148 の問題F (F – Playing Tag on Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 148 の問題E (E – Double Factorial) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 148 の問題D (D – Brick Break) を解いてみた.