C++ | 個人用メモ帳

2021年3月21日

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

C++の練習を兼ねて, AtCoder Grand Contest 040 の問題B (Two Contests) を解いてみた.

■感想.
1. 問題Bは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/agc040/editorial.pdf
// 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--)
#define pb push_back
#define all(x) x.begin(), x.end()
const LL INF = 202020202020202020;
LL l[101010], r[101010], as[101010], bt[101010];

struct joy{
    int i;
    LL a, b;
    bool operator < (const joy& rhs) const{
        return (a < rhs.a) || ((a == rhs.a) && (b > rhs.b));
    }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    LL ans = 0, maxL = 0, minR = INF;
    int p = -1, q = -1;
    rep(i, N){
        scanf("%lld %lld", &l[i], &r[i]);
        if(maxL < l[i]){
            maxL = l[i];
            p = i;
        }
        if(minR > r[i]){
            minR = r[i];
            q = i;
        }
        ans = max(ans, r[i] - l[i] + 1LL); // 最も長い区間を保存.
    }
    ans += max(0LL, minR - maxL + 1LL);
    
    // 2. 解説通り.
    vector<joy> v;
    rep(i, N){
        LL a = max(r[i] - maxL + 1LL, 0LL);
        LL b = max(minR - l[i] + 1LL, 0LL);
        joy j;
        j.i = i;
        j.a = a;
        j.b = b;
        v.pb(j);
    }
    
    // 3. sort.
    sort(all(v));
    // for(auto &p : v) printf("i=%d a=%lld b=%lld\n", p.i, p.a, p.b);
    
    // 4. 事前準備.
    rep(i, N + 1)     as[i] = bt[i] = INF;
    repr(i, N - 1, 0) as[i] = min(as[i + 1], v[i].a);
    rep(i, N)         bt[i + 1] = min(bt[i], v[i].b);
    // rep(i, N + 1) printf("%lld ", as[i]);
    // puts("");  
    // rep(i, N + 1) printf("%lld ", bt[i]);
    // puts("");
    
    // 5. 最大値は？
    repx(i, 1, N) ans = max(ans, as[i] + bt[i]);
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

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

#define pb push_back

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

const LL INF = 202020202020202020;

LL l[101010], r[101010], as[101010], bt[101010];

struct joy{

int i;

LL a, b;

bool operator < (const joy& rhs) const{

return (a < rhs.a) || ((a == rhs.a) && (b > rhs.b));

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

LL ans = 0, maxL = 0, minR = INF;

int p = -1, q = -1;

rep(i, N){

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

if(maxL < l[i]){

maxL = l[i];

p = i;

}

if(minR > r[i]){

minR = r[i];

q = i;

}

ans = max(ans, r[i] - l[i] + 1LL); // 最も長い区間を保存.

}

ans += max(0LL, minR - maxL + 1LL);

// 2. 解説通り.

vector<joy> v;

rep(i, N){

LL a = max(r[i] - maxL + 1LL, 0LL);

LL b = max(minR - l[i] + 1LL, 0LL);

joy j;

j.i = i;

j.a = a;

j.b = b;

v.pb(j);

}

// 3. sort.

sort(all(v));

// for(auto &p : v) printf("i=%d a=%lld b=%lld\n", p.i, p.a, p.b);

// 4. 事前準備.

rep(i, N + 1) as[i] = bt[i] = INF;

repr(i, N - 1, 0) as[i] = min(as[i + 1], v[i].a);

rep(i, N) bt[i + 1] = min(bt[i], v[i].b);

// rep(i, N + 1) printf("%lld ", as[i]);

// puts("");

// rep(i, N + 1) printf("%lld ", bt[i]);

// puts("");

// 5. 最大値は？

repx(i, 1, N) ans = max(ans, as[i] + bt[i]);

// 6. 出力.

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

return 0;

}

[入力例]
4
4 7
1 4
5 8
2 5

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

[入力例]
4
1 20
2 19
3 18
4 17

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

[入力例]
10
457835016 996058008
456475528 529149798
455108441 512701454
455817105 523506955
457368248 814532746
455073228 459494089
456651538 774276744
457667152 974637457
457293701 800549465
456580262 636471526

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

[入力例]
25
1 6
17 23
16 31
7 22
4 5
3 13
19 27
7 13
11 22
2 3
6 21
3 19
3 13
7 7
15 20
2 11
9 23
17 25
6 15
15 19
9 19
4 5
15 19
1 2
11 21

[出力例]
17

[入力例]

4 7

1 4

5 8

2 5

[出力例]

※AtCoderテストケースより

[入力例]

1 20

2 19

3 18

4 17

[出力例]

※AtCoderテストケースより

[入力例]

457835016 996058008

456475528 529149798

455108441 512701454

455817105 523506955

457368248 814532746

455073228 459494089

456651538 774276744

457667152 974637457

457293701 800549465

456580262 636471526

[出力例]

540049931

※AtCoderテストケースより

[入力例]

1 6

17 23

16 31

7 22

4 5

3 13

19 27

7 13

11 22

2 3

6 21

3 19

3 13

7 7

15 20

2 11

9 23

17 25

6 15

15 19

9 19

4 5

15 19

1 2

11 21

[出力例]

■参照サイト
AtCoder Grand Contest 040

2021年3月19日2021年3月19日

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

C++の練習を兼ねて, AtCoder Regular Contest 099 の問題D (Snuke Numbers) を解いてみた.

■感想.
1. 問題Dは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 個人的には, 条件を整数の抽出方法が, 非常に面白く感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc099/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<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--)
#define pb push_back
const LL INF = 202020202020202020;

int main(){
    
    // 1. 入力情報.
    int K;
    scanf("%d", &K);
    
    // 2. 10の冪乗を用意.
    vl cPow;
    cPow.pb(1);
    while(cPow.back() < 1e18){
        // 最大値を10倍.
        LL p = 10 * cPow.back();
        
        // 保存.
        cPow.pb(p);
    }
    // for(auto &p : cPow) printf("%lld\n", p);
    
    // 3. x を保存.
    // -> N = 792 で, 丁度桁あふれするので, N / S(N) と x / S(x) を比較する部分を修正.
    int count = 0;
    LL N = 1;
    vl v;
    while(count < K){
        // 3-1. N に 対する N / S(N) の 準備.
        string nStr = to_string(N);
        LL sn = 0;
        rep(j, nStr.size()) sn += (nStr[j] - '0');
        
        // 3-2. x に 対する x / S(x) の 準備.
        int d = (int)log10(N) + 1;
        LL S = 0, X = 0, minS = INF, minX = INF;
        rep(j, d + 1){
            X = cPow[j + 1] * (N / cPow[j + 1] + 1) - 1;
            string xStr = to_string(X);
            S = 0;
            rep(k, xStr.size()) S += (xStr[k] - '0');
            
            // 初回確認時.
            if(minS == INF){
                minS = S;
                minX = X;
            }
            
            // 2回目以降.
            if(minS < INF){
                if(X * minS < minX * S){
                    minS = S;
                    minX = X;
                }
            }
        }
        // printf("count=%d S=%lld X=%lld N=%lld\n", count, S, X, N);
        
        // 3-3. N に 対する N / S(N) と x に 対する x / S(x) を 比較.
        // 前者が小さい場合は, 追加.
        // if(N * minS <= minX * sn){ // N = 792 で 桁あふれ.
        if((double)N / (double)sn <= (double)minX / (double)minS){
            // Snuke数 を 追加.
            v.pb(N);
            
            // インクリメント.
            N++;
            count++;
            
            // 次へ.
            continue;
        }
        
        // 3-4. 前者が大きい場合は, 追加しない.
        // if(N * minS > minX * sn) N = minX; // N = 792 で 桁あふれ.
        if((double)minS / (double)sn > (double)minX / (double)N) N = minX;
    }
    
    // 4. 出力.
    for(auto &p : v) printf("%lld\n", p);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<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--)

#define pb push_back

const LL INF = 202020202020202020;

int main(){

// 1. 入力情報.

int K;

scanf("%d", &K);

// 2. 10の冪乗を用意.

vl cPow;

cPow.pb(1);

while(cPow.back() < 1e18){

// 最大値を10倍.

LL p = 10 * cPow.back();

// 保存.

cPow.pb(p);

}

// for(auto &p : cPow) printf("%lld\n", p);

// 3. x を保存.

// -> N = 792 で, 丁度桁あふれするので, N / S(N) と x / S(x) を比較する部分を修正.

int count = 0;

LL N = 1;

vl v;

while(count < K){

// 3-1. N に対する N / S(N) の準備.

string nStr = to_string(N);

LL sn = 0;

rep(j, nStr.size()) sn += (nStr[j] - '0');

// 3-2. x に対する x / S(x) の準備.

int d = (int)log10(N) + 1;

LL S = 0, X = 0, minS = INF, minX = INF;

rep(j, d + 1){

X = cPow[j + 1] * (N / cPow[j + 1] + 1) - 1;

string xStr = to_string(X);

S = 0;

rep(k, xStr.size()) S += (xStr[k] - '0');

// 初回確認時.

if(minS == INF){

minS = S;

minX = X;

}

// 2回目以降.

if(minS < INF){

if(X * minS < minX * S){

minS = S;

minX = X;

}

// printf("count=%d S=%lld X=%lld N=%lld\n", count, S, X, N);

// 3-3. N に対する N / S(N) と x に対する x / S(x) を比較.

// 前者が小さい場合は, 追加.

// if(N * minS <= minX * sn){ // N = 792 で桁あふれ.

if((double)N / (double)sn <= (double)minX / (double)minS){

// Snuke数を追加.

v.pb(N);

// インクリメント.

N++;

count++;

// 次へ.

continue;

}

// 3-4. 前者が大きい場合は, 追加しない.

// if(N * minS > minX * sn) N = minX; // N = 792 で桁あふれ.

if((double)minS / (double)sn > (double)minX / (double)N) N = minX;

}

// 4. 出力.

for(auto &p : v) printf("%lld\n", p);

return 0;

}

[入力例]
10

[出力例]
1
2
3
4
5
6
7
8
9
19
※AtCoderのテストケースより

[入力例]
77

[出力例]
1
2
3
4
5
6
7
8
9
19
29
39
49
59
69
79
89
99
199
299
399
499
599
699
799
899
999
1099
1199
1299
1399
1499
1599
1699
1799
1899
1999
2999
3999
4999
5999
6999
7999
8999
9999
10999
11999
12999
13999
14999
15999
16999
17999
18999
19999
20999
21999
22999
23999
24999
25999
26999
27999
28999
29999
39999
49999
59999
69999
79999
89999
99999
109999
119999
129999
139999
149999

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

199

299

399

499

599

699

799

899

999

1099

1199

1299

1399

1499

1599

1699

1799

1899

1999

2999

3999

4999

5999

6999

7999

8999

9999

10999

11999

12999

13999

14999

15999

16999

17999

18999

19999

20999

21999

22999

23999

24999

25999

26999

27999

28999

29999

39999

49999

59999

69999

79999

89999

99999

109999

119999

129999

139999

149999

■参照サイト
AtCoder Regular Contest 099

2021年3月17日

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

C++の練習を兼ねて, AtCoder Regular Contest 093 の問題D (Grid Components) を解いてみた.

■感想.
1. 問題Dは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc093/editorial.pdf
// 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--)
int board[101][101];

int main(){
    
    // 1. 入力情報.
    int A, B;
    scanf("%d %d", &A, &B);
    
    // 2. 上から K行 を 黒色.
    int K = (int)sqrt(max(2 * A, 2 * B)) + 2; // +1 だと, 02.txt などで, WA となる.
    rep(i, K) rep(j, K * 2) board[i][j] = 1;
    
    // 3. 上から (K - 1)行までで, (A - 1)個 を 白色 に 変更.
    int wRes = A - 1;
    rep(i, K - 1){
        repex(j, 0, K * 2, 2){
            // 残数ゼロならば終了.
            if(!wRes) break;
            
            // 白色に変更するマスを選択.
            if((i + j) & 1){
                // 残数をデクリメント.
                wRes--;
                
                // 白色に変更.
                board[i][j] = 0;
            }
        }
        // 残数ゼロならば終了.
        if(!wRes) break;
    }
    
    // 4. 下から (K - 1)行までで, (B - 1)個 を 黒色 に 変更.
    int bRes = B - 1;
    repx(i, K + 1, K * 2){
        repex(j, 0, K * 2, 2){
            // 残数ゼロならば終了.
            if(!bRes) break;
            
            // 黒色に変更するマスを選択.
            if((i + j) & 1){
                // 残数をデクリメント.
                bRes--;
                
                // 黒色に変更.
                board[i][j] = 1;
            }
        }
        // 残数ゼロならば終了.
        if(!bRes) break;
    }
    
    // 5. 出力.
    printf("%d %d\n", K * 2, K * 2);
    rep(i, K * 2){
        rep(j, K * 2) printf("%s", (board[i][j]) ? "#" : ".");
        puts("");
    }
    return 0;
    
}

// 解き直し.

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

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

int board[101][101];

int main(){

// 1. 入力情報.

int A, B;

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

// 2. 上から K行を黒色.

int K = (int)sqrt(max(2 * A, 2 * B)) + 2; // +1 だと, 02.txt などで, WA となる.

rep(i, K) rep(j, K * 2) board[i][j] = 1;

// 3. 上から (K - 1)行までで, (A - 1)個を白色に変更.

int wRes = A - 1;

rep(i, K - 1){

repex(j, 0, K * 2, 2){

// 残数ゼロならば終了.

if(!wRes) break;

// 白色に変更するマスを選択.

if((i + j) & 1){

// 残数をデクリメント.

wRes--;

// 白色に変更.

board[i][j] = 0;

}

// 残数ゼロならば終了.

if(!wRes) break;

}

// 4. 下から (K - 1)行までで, (B - 1)個を黒色に変更.

int bRes = B - 1;

repx(i, K + 1, K * 2){

repex(j, 0, K * 2, 2){

// 残数ゼロならば終了.

if(!bRes) break;

// 黒色に変更するマスを選択.

if((i + j) & 1){

// 残数をデクリメント.

bRes--;

// 黒色に変更.

board[i][j] = 1;

}

// 残数ゼロならば終了.

if(!bRes) break;

}

// 5. 出力.

printf("%d %d\n", K * 2, K * 2);

rep(i, K * 2){

rep(j, K * 2) printf("%s", (board[i][j]) ? "#" : ".");

puts("");

}

return 0;

}

[入力例]
2 3

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

※但し, 上記のプログラムでは, 以下の内容が出力される.
8 8
########
.#######
########
########
........
#.#.....
........
........

[入力例]
7 8

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

※但し, 上記のプログラムでは, 以下の内容が出力される.
12 12
############
.#.#.#.#.#.#
############
############
############
############
............
#.#.#.#.#.#.
............
#...........
............
............

[入力例]
1 1

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

※但し, 上記のプログラムでは, 以下の内容が出力される.
6 6
######
######
######
......
......
......

[入力例]
3 14

[出力例]
8 18
..................
..................
....##.......####.
....#.#.....#.....
...#...#....#.....
..#.###.#...#.....
.#.......#..#.....
#.........#..####.
※AtCoderテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.
14 14
##############
.#.###########
##############
##############
##############
##############
##############
..............
..............
#.#.#.#.#.#.#.
..............
#.#.#.#.#.#...
..............
..............

[入力例]
20 21

[出力例]
16 16
################
.#.#.#.#.#.#.#.#
################
.#.#.#.#.#.#.#.#
################
.#.#.###########
################
################
................
#.#.#.#.#.#.#.#.
................
#.#.#.#.#.#.#.#.
................
#.#.#.#.........
................
................

[入力例]
314 159

[出力例]
54 54
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
######################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#######################
######################################################
######################################################
######################################################
......................................................
......................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
......................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
......................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
......................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
......................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
......................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.........
......................................................
......................................................
......................................................
......................................................
......................................................
......................................................
......................................................
......................................................
......................................................
......................................................
......................................................
......................................................
......................................................
......................................................

[入力例]
500 500

[出力例]
66 66
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
##################################################################
.#.#.#.###########################################################
##################################################################
..................................................................
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
..................................................................
#.#.#.#...........................................................

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

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

[入力例]

2 3

[出力例]

3 3

##.

..#

#.#

※AtCoderテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.

8 8

########

.#######

########

........

#.#.....

........

[入力例]

7 8

[出力例]

3 5

#.#.#

.#.#.

#.#.#

※AtCoderテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.

12 12

############

.#.#.#.#.#.#

############

............

#.#.#.#.#.#.

............

#...........

............

[入力例]

1 1

[出力例]

4 2

※AtCoderテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.

6 6

######

......

[入力例]

3 14

[出力例]

8 18

..................

....##.......####.

....#.#.....#.....

...#...#....#.....

..#.###.#...#.....

.#.......#..#.....

#.........#..####.

※AtCoderテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.

14 14

##############

.#.###########

##############

..............

#.#.#.#.#.#.#.

..............

#.#.#.#.#.#...

..............

[入力例]

20 21

[出力例]

16 16

################

.#.#.#.#.#.#.#.#

################

.#.#.#.#.#.#.#.#

################

.#.#.###########

################

................

#.#.#.#.#.#.#.#.

................

#.#.#.#.#.#.#.#.

................

#.#.#.#.........

................

[入力例]

314 159

[出力例]

54 54

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#

######################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#######################

######################################################

......................................................

#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.

......................................................

#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.

......................................................

#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.

......................................................

#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.

......................................................

#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.

......................................................

#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.........

......................................................

[入力例]

500 500

[出力例]

66 66

##################################################################

.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#