QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#713891#5537. Storing EggsMeatInTheMiddleAC ✓108ms8708kbC++175.2kb2024-11-05 20:49:502024-11-05 20:49:50

Judging History

This is the latest submission verdict.

  • [2024-11-05 20:49:50]
  • Judged
  • Verdict: AC
  • Time: 108ms
  • Memory: 8708kb
  • [2024-11-05 20:49:50]
  • Submitted

answer

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll mod = 1e9 + 7;

const double inf = 50000;
double d[101][1 << 3][101][1 << 3];
double dd[1 << 3] = {inf, inf, inf, 1, inf, 2, 1, 1};
int dp[101][1 << 3];
int n, k;
vector<string> s(3);

bool valid(double x) {
    for (int i = 1; i <= n; i++)
        for (int is = 1; is < (1 << 3); is++) {
            bool can = true;
            for (int ii = 0; ii < 3; ii++)
                if ((is & (1 << ii)) && s[ii][i] == '#') {
                    can = false;
                    break;
                }
            if (!can) continue;
            dp[i][is] = (dd[is] >= x ? __builtin_popcount(is) : 0);
        }
    for (int i = 0; i <= n; i++) {
        for (int is = 0; is < (1 << 3); is++) {
            bool can = true;
            for (int ii = 0; ii < 3; ii++) {
                if ((is & (1 << ii)) && s[ii][i] == '#') {
                    can = false;
                    break;
                }
            }
            if (!can) continue;
            for (int j = i + 2; j <= n; j++) {
                for (int js = 1; js < (1 << 3); js++) {
                    bool ccan = true;
                    for (int jj = 0; jj < 3; jj++) {
                        if ((js & (1 << jj)) && s[jj][j] == '#') {
                            ccan = false;
                            break;
                        }
                    }
                    if (s[0][j] == '#' && s[1][j] == '#' && s[2][j] == '#') ccan = false;
                    if (!ccan) continue;
                    if (d[i][is][j][js] >= x) {
                        dp[j][js] = max(dp[j][js], dp[i][is] + __builtin_popcount(js));
                        for (int ks = 1; ks < (1 << 3); ks++) {
                            if (min(d[j - 1][ks][j][js], d[i][is][j - 1][ks]) >= x) {
                                dp[j][js] = max(dp[j][js], dp[i][is] + __builtin_popcount(js) + __builtin_popcount(ks));
                            }
                        }
                    }
                }
            }
        }
    }

    int mx = 0;
    for (int i = 0; i <= n; i++)
        for (int is = 1; is < (1 << 3); is++) {
            mx = max(mx, dp[i][is]);
            // cout << "dp: " << i << " " << is << " - " << dp[i][is] << "\n";
        }
    // cout << "x: " << x << " mx: " << mx << "\n";
    if (mx >= k) return true;
    else return false;
}

void solve() {
    cin >> n >> k;
    int scnt = 0;
    for (auto& si : s) {
        cin >> si;
        si = '0' + si;
        for (auto& sij : si)
            if (sij == '#') scnt += 1;
    }
    if (3 * n - scnt < k) {
        cout << "-1\n";
        return;
    }
    for (int j = 1; j <= n; j++)
        for (int js = 1; js < (1 << 3); js++) {
            bool tmp = false;
            for (int jj = 0; jj < 3; jj++) {
                if ((js & (1 << jj)) && s[jj][j] == '#') {
                    d[0][0][j][js] = 0;
                    tmp = true;
                    break;
                }
            }
            if (!tmp) d[0][0][j][js] = dd[js];
            // cout << 0 << " " << 0 << " " << j << " " << js << " : " << d[0][0][j][js] << "\n";
        }
    for (int i = 1; i <= n; i++) {
        for (int is = 1; is < (1 << 3); is++) {
            bool can = true;
            for (int ii = 0; ii < 3; ii++) {
                if ((is & (1 << ii)) && s[ii][i] == '#') {
                    can = false;
                    break;
                }
            }
            if (!can) continue;
            for (int j = i + 1; j <= n; j++) {
                for (int js = 1; js < (1 << 3); js++) {
                    bool ccan = true;
                    for (int jj = 0; jj < 3; jj++) {
                        if ((js & (1 << jj)) && s[jj][j] == '#') {
                            ccan = false;
                            break;
                        }
                    }
                    if (!ccan) continue;
                    d[i][is][j][js] = dd[js];
                    for (int ii = 0; ii < 3; ii++) {
                        if ((is & (1 << ii)) == 0) continue;
                        for (int jj = 0; jj < 3; jj++) {
                            if ((js & (1 << jj)) == 0) continue;
                            d[i][is][j][js] = min(d[i][is][j][js], sqrt(double((i - j) * (i - j) + (ii - jj) * (ii - jj))));
                        }
                    }
                    if (d[i][is][j][js] == inf) d[i][is][j][js] = 0;
                    // cout << i << " " << is << " " << j << " " << js << " : " << d[i][is][j][js] << "\n";
                }
            }
        }
    }
    // valid(1);
    double lo = 0, hi = 1000;
    for (int i = 0; i < 60; i++) {
        double mid = (lo + hi) / 2;
        if (valid(mid)) lo = mid;
        else hi = mid;
    }
    cout << fixed;
    cout.precision(8);
    cout << hi << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3880kb

input:

5 2
#....
.....
....#

output:

4.47213595

result:

ok found '4.4721360', expected '4.4721360', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

5 6
##.##
#####
.....

output:

1.00000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3976kb

input:

3 4
..#
...
...

output:

1.41421356

result:

ok found '1.4142136', expected '1.4142140', error '0.0000003'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

2 6
..
.#
..

output:

-1

result:

ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3784kb

input:

1 2
.
.
.

output:

2.00000000

result:

ok found '2.0000000', expected '2.0000000', error '0.0000000'

Test #6:

score: 0
Accepted
time: 39ms
memory: 8272kb

input:

100 2
....................................................................................................
....................................................................................................
...............................................................................................

output:

99.02019996

result:

ok found '99.0202000', expected '99.0202000', error '0.0000000'

Test #7:

score: 0
Accepted
time: 46ms
memory: 8372kb

input:

100 3
....................................................................................................
....................................................................................................
...............................................................................................

output:

49.04079934

result:

ok found '49.0407993', expected '49.0407990', error '0.0000000'

Test #8:

score: 0
Accepted
time: 80ms
memory: 8208kb

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

2.00000000

result:

ok found '2.0000000', expected '2.0000000', error '0.0000000'

Test #9:

score: 0
Accepted
time: 85ms
memory: 8548kb

input:

100 150
....................................................................................................
....................................................................................................
.............................................................................................

output:

1.41421356

result:

ok found '1.4142136', expected '1.4142140', error '0.0000003'

Test #10:

score: 0
Accepted
time: 105ms
memory: 8244kb

input:

100 151
....................................................................................................
....................................................................................................
.............................................................................................

output:

1.00000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #11:

score: 0
Accepted
time: 107ms
memory: 8672kb

input:

100 200
....................................................................................................
....................................................................................................
.............................................................................................

output:

1.00000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #12:

score: 0
Accepted
time: 108ms
memory: 8204kb

input:

100 201
....................................................................................................
....................................................................................................
.............................................................................................

output:

1.00000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #13:

score: 0
Accepted
time: 39ms
memory: 6912kb

input:

60 130
............................................................
............................................................
............................................................

output:

1.00000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #14:

score: 0
Accepted
time: 24ms
memory: 7112kb

input:

100 100
....................................................................................................
####################################################################################################
.............................................................................................

output:

2.00000000

result:

ok found '2.0000000', expected '2.0000000', error '0.0000000'

Test #15:

score: 0
Accepted
time: 10ms
memory: 8200kb

input:

100 51
####################################################################################################
....................................................................................................
###########################################################################################...

output:

1.00000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

1 2
#
#
#

output:

-1

result:

ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'

Test #17:

score: 0
Accepted
time: 9ms
memory: 8080kb

input:

99 50
###################################################################################################
...................................................................................................
##############################################################################################...

output:

2.00000000

result:

ok found '2.0000000', expected '2.0000000', error '0.0000000'

Test #18:

score: 0
Accepted
time: 17ms
memory: 6884kb

input:

100 47
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...

output:

2.82842712

result:

ok found '2.8284271', expected '2.8284270', error '0.0000000'

Test #19:

score: 0
Accepted
time: 18ms
memory: 8384kb

input:

100 43
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#....

output:

2.82842712

result:

ok found '2.8284271', expected '2.8284270', error '0.0000000'

Test #20:

score: 0
Accepted
time: 33ms
memory: 8480kb

input:

99 2
#........#............#.#.#...................................#................##..............#...
............................##...#......#...##.............#.........#..#...#............#...#.....
#...............................................#..............#.....#.........#.........#........

output:

98.00510191

result:

ok found '98.0051019', expected '98.0051020', error '0.0000000'

Test #21:

score: 0
Accepted
time: 5ms
memory: 5952kb

input:

90 2
#############..######.###.##.#########.###.###########.####.##############################
#...##########.#.#################.############.########################.#################
###################.###.##.####.#######..##.########.#############################.#######

output:

81.00617260

result:

ok found '81.0061726', expected '81.0061730', error '0.0000000'

Test #22:

score: 0
Accepted
time: 35ms
memory: 7592kb

input:

95 3
#.#..............#.............#.......#..##.....#.#............#....#..................##.....
.....#.#........#...#...........#......................#...#.....#.........#.....#...........#.
#.......#.#....#.......#.......#.......#..#.#.#.#....#.#...#..#......#........#..........#....#

output:

47.01063709

result:

ok found '47.0106371', expected '47.0106370', error '0.0000000'

Test #23:

score: 0
Accepted
time: 5ms
memory: 7920kb

input:

92 3
#########################.###########################.####################################.#
#######.##############.#.#################.#########.########.#############################.
###.##.####.###.####.#####.########.#########.########.##.#######.##########################

output:

42.00000000

result:

ok found '42.0000000', expected '42.0000000', error '0.0000000'

Test #24:

score: 0
Accepted
time: 36ms
memory: 8708kb

input:

93 4
##..#.......................#.....#.#.#..............#.....#........#.....................#..
......#...................#..##...................#...............###.....#....#..........#.#
#......#.........#....#.................#......#...#......##..........#.........#.#..#.#..#.#

output:

30.06659276

result:

ok found '30.0665928', expected '30.0665930', error '0.0000000'

Test #25:

score: 0
Accepted
time: 5ms
memory: 7924kb

input:

92 4
###.###############.######.##.#########################.######.###.#####.###################
#.##..#####################.###########################.########..###############.#######...
#######################.###.############.##..####.#################.#.#..####.##############

output:

28.01785145

result:

ok found '28.0178514', expected '28.0178510', error '0.0000000'

Test #26:

score: 0
Accepted
time: 49ms
memory: 8304kb

input:

94 5
#........#....#.................................................#.....................#.......
#................#...............#..##..................#........#.......#...#................
##..................................................##................#.......#...............

output:

23.02172887

result:

ok found '23.0217289', expected '23.0217290', error '0.0000000'

Test #27:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

1 2
#
.
.

output:

1.00000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #28:

score: 0
Accepted
time: 5ms
memory: 6036kb

input:

94 5
##..#.######.##.########.#####.#####.############..##.##############################..########
#######.########.##########.#..################.####.#.###...######..##.######################
######.############.######.#####################.################.##.##############.##########

output:

18.02775638

result:

ok found '18.0277564', expected '18.0277560', error '0.0000000'

Test #29:

score: 0
Accepted
time: 41ms
memory: 7868kb

input:

90 6
#.................#....................#................#.#.........###...................
....................................#........#...................#...##...##....#.....#...
#.#...........#...#........#..#....#.#....................#.........#.....................

output:

17.11724277

result:

ok found '17.1172428', expected '17.1172430', error '0.0000000'

Test #30:

score: 0
Accepted
time: 3ms
memory: 6100kb

input:

100 6
##########.##.##################.###########.###########.##.######################.####.##.#########
##########...#########.#.########.#################.#.###########.#.##########.#.##.################
##############.#####..#######..##################.#######################.########.#########...

output:

16.03121954

result:

ok found '16.0312195', expected '16.0312200', error '0.0000000'

Test #31:

score: 0
Accepted
time: 48ms
memory: 8324kb

input:

92 7
#.#....#..#...#.......#.........................................#.......#...#.............#.
...............#......#............#...#.........................#.....#..............#.....
#..#......#...............#.................#....#............................#.............

output:

15.13274595

result:

ok found '15.1327460', expected '15.1327460', error '0.0000000'

Test #32:

score: 0
Accepted
time: 5ms
memory: 7920kb

input:

92 7
##.###########..######.###############.#.##.#################.##.#############.######.###.##
#############.###############.##..#####################.######.#..#########.###.############
.###.########.###################.########.###################..#######...#########.#####.##

output:

14.03566885

result:

ok found '14.0356689', expected '14.0356690', error '0.0000000'

Test #33:

score: 0
Accepted
time: 46ms
memory: 8268kb

input:

91 8
#..................#..#..............#......................#.......#..........#...#..#....
#....#.#.....#..#......#.....#.................#..#...........................#.........#..
#.......#......#..........#............#.....#...................#..............#.....#....

output:

12.16552506

result:

ok found '12.1655251', expected '12.1655250', error '0.0000000'

Test #34:

score: 0
Accepted
time: 5ms
memory: 7916kb

input:

93 8
############.###########.#######################.############.##.###.######################.#
############.####.###########.#######.####.##########.#######.####.###################.####..
#####.#######.###########.#####.#############.#.##################.##########################

output:

8.06225775

result:

ok found '8.0622578', expected '8.0622580', error '0.0000000'

Test #35:

score: 0
Accepted
time: 70ms
memory: 7868kb

input:

100 109
..#.....#..............#....................#..#.......#.............#................#.#...........
#............##.........#..........#.#....#...............#...#.......#................#...........#
.....#..#......#................................................................#............

output:

1.41421356

result:

ok found '1.4142136', expected '1.4142140', error '0.0000003'

Test #36:

score: 0
Accepted
time: 45ms
memory: 8336kb

input:

97 13
..##...#..........#.........##....##......#............#..........###........#.....#.........#...
##..#....#.............#....#...#.##............#........#.#.#.....................#.......#..#..
........#..#....##.........#.#....#.....#.......#.#...................#......#.......#......##...

output:

8.06225775

result:

ok found '8.0622578', expected '8.0622580', error '0.0000000'

Test #37:

score: 0
Accepted
time: 53ms
memory: 8552kb

input:

100 50
....#......#..................#.......#..#.....#........#.........#......#....#............##.......
#.....##........#.#...........##..#....##....#.#.........##....#.##...........#.....................
......##........#...#....#...#...#............#.......##.#..........##......##....##..#...#...

output:

2.23606798

result:

ok found '2.2360680', expected '2.2360680', error '0.0000000'

Test #38:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

1 3
#
.
.

output:

-1

result:

ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'

Test #39:

score: 0
Accepted
time: 49ms
memory: 7412kb

input:

92 107
..#........#...#...#.....#....#........#...#.......#.........#..#.........#...##.......##.#.
..##.......#..#....##.#..##.#.##........#............#..#.......#..##..............#....#...
#...#.....#..........#........#.....##.#.................#....##...........#............#...

output:

1.41421356

result:

ok found '1.4142136', expected '1.4142140', error '0.0000003'

Test #40:

score: 0
Accepted
time: 62ms
memory: 7680kb

input:

95 125
...##.......#..#.#.............#..##...#..................#......#...##..#.....##....#.......#.
.........#.....#.#....#....#..##.....#...#...#......#...........##..#........#.#...#.#........#
.#..#....................##.........#...#...........#...........#...#...#..........##.....#.##.

output:

1.00000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #41:

score: 0
Accepted
time: 16ms
memory: 6680kb

input:

93 20
#############################################################################################
.#.....#.......###.#..#.###....#...............##...#.....#..#...#...........#.....#....#..#.
....##.....#....#.#......#......#...........#.....#................#......#...#.##........#..

output:

4.12310563

result:

ok found '4.1231056', expected '4.1231060', error '0.0000001'

Test #42:

score: 0
Accepted
time: 7ms
memory: 6156kb

input:

97 21
#################################################################################################
#################################################################################################
......###........#.....#...#.#.........##.#......#.####.##......#....#........#...##....#......#.

output:

4.00000000

result:

ok found '4.0000000', expected '4.0000000', error '0.0000000'

Test #43:

score: 0
Accepted
time: 18ms
memory: 6892kb

input:

93 7
#...#..##..#..#....#...#......#...####.###..##.##.#..#.#.###.##......#..###....#.#..#.#.#...#
.#.#....##..##.##.#...##..##.#..............####.....##.#.#.#.#.#..##....#...#.#.#.......#...
###.###......#.#.#.#...###....#.#.##..#..#...#...#.##.#..##...#.####.#..##.#.###....#.#...#.#

output:

15.13274595

result:

ok found '15.1327460', expected '15.1327460', error '0.0000000'

Test #44:

score: 0
Accepted
time: 22ms
memory: 8340kb

input:

91 15
.##.#..#......#.#####..###....##..#.#...#..##..#.##.....#....#.######.#.#.#......##..##..#.
..#..########....#..#...#.###.#............#.#.#..#..#..#.#.##...##....###.#...#.###..####.
...#.##..####..#.#.#.....#.#..#.#...##.##.#....#....#..#..##.......#####..###.#.#.#.##...#.

output:

6.32455532

result:

ok found '6.3245553', expected '6.3245550', error '0.0000001'

Test #45:

score: 0
Accepted
time: 28ms
memory: 6992kb

input:

98 58
.#..##.....#............###.#####.##.....#.#..#.#.....####..##.##.#.......##...##..#..#....#..#..#
#.#.##.#.#...#.....###...#....##..#..#...#####.##.#.#..#.#.##.#...####.##.#.....###.##.###.#....#.
....#..##..##.##..##...#..#....#.......###...#....#.##..#...#..#.....#....#.#.......####.#.#..#.#.

output:

2.23606798

result:

ok found '2.2360680', expected '2.2360680', error '0.0000000'

Test #46:

score: 0
Accepted
time: 27ms
memory: 8096kb

input:

92 92
.#.#####.......##.##.....#####.....#..#..##.#..###..###.#..#..#.###..##...##..#.#.##..#.....
#..#...#..........##.##.#.#..#.#..#..##..#...#..###.#.#....#..#.#..#..#.##........#....##.##
.........####..#...#.....###...###.##..#.##.#####...##...##.#....#.##..##.##.######.#.#...#.

output:

1.00000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #47:

score: 0
Accepted
time: 8ms
memory: 8092kb

input:

94 40
##############################################################################################
.#.........#.....##.########..#.....##..###..##.#.#..#.####..##...#..#..#....##.#..#....####.#
...#..#.##.#......#......####.....#.#..#.#.#..###.#..#.......##.#.###.#..##......#####.#..#..#

output:

2.00000000

result:

ok found '2.0000000', expected '2.0000000', error '0.0000000'

Test #48:

score: 0
Accepted
time: 7ms
memory: 6092kb

input:

95 21
###############################################################################################
###############################################################################################
..#..#.#....#.#..##.##..#.#.#.##.#.......##.#...#...#.##...#..#..###.#...#......#..##.......#.#

output:

4.00000000

result:

ok found '4.0000000', expected '4.0000000', error '0.0000000'

Test #49:

score: 0
Accepted
time: 0ms
memory: 4028kb

input:

1 3
.
.
.

output:

1.00000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #50:

score: 0
Accepted
time: 11ms
memory: 6328kb

input:

99 4
#...##.#.####.############.##.###..###.###.##.#.###.#####..#.#..#..#.#..###..##...#.#.#..##########
.##..##.###..##.#.#.#######..##...###..#.##.#.##..#...###...#.###...#####.######..#..########.##.#.
#######.##.####..##.##.#...#.###.###..####..###.######..###.##.#.#..#..#.#.###.#.###.#######.##...

output:

32.01562119

result:

ok found '32.0156212', expected '32.0156210', error '0.0000000'

Test #51:

score: 0
Accepted
time: 15ms
memory: 6580kb

input:

100 12
#.###.####...######.###.########.#.##.#..#......##...#####.#.#..#.#..##.##.#.##.###.##.#########..##
#.###..###.#####.##.#..##..#.###....###...##.##.#..#.#.#.##....#..#.#.#####.#.#########..#.#..#..###
#.#.######.########...#...##.#..#.##.####..#.#.#..#.###...#.#.#..###....#...####.#.##..###....

output:

8.24621125

result:

ok found '8.2462112', expected '8.2462110', error '0.0000000'

Test #52:

score: 0
Accepted
time: 13ms
memory: 8128kb

input:

100 36
..######.#.#####.##.##.#.#######.####.#.######.##.#...####.####....##.#.....##..#########..###.#.###
##.######.#.###.####.##..#..##.##..#.#######.##.######.#...#.##.##.#.#..#..####.###.#..#####.#.####.
##.###.#..#.#####.#....###..#....#.#...#...#.##..###.##.########.##.##.########.#####.####....

output:

2.23606798

result:

ok found '2.2360680', expected '2.2360680', error '0.0000000'

Test #53:

score: 0
Accepted
time: 11ms
memory: 6492kb

input:

97 74
..####.#..#.###.##...##.#########...#.....##.##.#####.#.###..##..##...###.#.##...####...##.###.##
..##....#.##.###.###..###..#..#..#####.###..#.##..#####.####.###..##.##...#..###.#####.########.#
...##.#.###.#.##.####.#..##.###.######..#.####.####..########..##.#.###..##..###..#..##.#.##..##.

output:

1.00000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #54:

score: 0
Accepted
time: 8ms
memory: 8188kb

input:

97 28
#################################################################################################
.###.##.##...########.##.###.#..#.###.#.#..#.##..##.#.##...##..#...##....#...##########.#####.###
.##.#####..##..#.####.##.#.###.###....##.##.########..###.####..####.###.##..#.#..###..####....##

output:

2.23606798

result:

ok found '2.2360680', expected '2.2360680', error '0.0000000'

Test #55:

score: 0
Accepted
time: 5ms
memory: 7944kb

input:

90 13
##########################################################################################
##########################################################################################
.##.###..####.####.###..###..###..#.##.#.##..###.###.###..#.#.####.#.###.#..#.######.....#

output:

5.00000000

result:

ok found '5.0000000', expected '5.0000000', error '0.0000000'

Test #56:

score: 0
Accepted
time: 6ms
memory: 6052kb

input:

94 4
###.#############..####..#.####.#####.################.####.#######..######.######.###########
.##############.#####.###.####.##..##########.#.##########.#####.##.####.#####.######.########
#.######.#######..###.########.##.##########.##########.####.######.##..##.##.#####.###.######

output:

28.07133770

result:

ok found '28.0713377', expected '28.0713380', error '0.0000000'

Test #57:

score: 0
Accepted
time: 8ms
memory: 6108kb

input:

100 9
###########.######.#.#.#.###.#####..##.###########..#######.#..####..############.#..#..#.##.#######
.####.##..#.####.#####.##.###.###.################.####.###.##..############################.##.####
###.######...####..#####.#..#.##.##.#.##..#######.#######.#####..############.#####.##.#####...

output:

9.21954446

result:

ok found '9.2195445', expected '9.2195440', error '0.0000000'

Test #58:

score: 0
Accepted
time: 7ms
memory: 8108kb

input:

93 27
##..###.#.#.#####.#############.###.###############.##.##.###########.#.#######..####.#..####
####.#.#####.#.###..####.##.##.#..####.#..##########..######.#########.######.##########..##.
#####...#####################...####.##.#.#####.######.#.###.##.#..########.#.###.#.####..#.#

output:

2.23606798

result:

ok found '2.2360680', expected '2.2360680', error '0.0000000'

Test #59:

score: 0
Accepted
time: 7ms
memory: 7936kb

input:

93 34
#######.#######.##.#.#.#####.##.#################.########...#######.#.#.#..#.##########.####
###...########.##########.##.########.#..##.####.##.#####..######..###.#####..#.###.####.####
#######.#########.#..#####.##.####.##.###.##.###.##.#.#...###.#.######.#####.###.##########.#

output:

2.23606798

result:

ok found '2.2360680', expected '2.2360680', error '0.0000000'

Test #60:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

3 3
.##
.##
.##

output:

1.00000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #61:

score: 0
Accepted
time: 5ms
memory: 5972kb

input:

94 14
##############################################################################################
##.#####.####.###.########.########.##.##.#######.##.#..#.#####.#.#.###########.#####.##.###.#
#.#.############.############.###.######..##.#######.##.###.####..#.#####.#####.######..#.#.##

output:

5.09901951

result:

ok found '5.0990195', expected '5.0990200', error '0.0000001'

Test #62:

score: 0
Accepted
time: 6ms
memory: 7864kb

input:

100 4
####################################################################################################
####################################################################################################
#########..###.####..#.####..#.##.#########.#.####..########.####.#.##.######..#####.#####.....

output:

25.00000000

result:

ok found '25.0000000', expected '25.0000000', error '0.0000000'

Test #63:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

99 208
.......###.##........###.....#...#.##..#.##.#.....#...#.#........#...##..##..#........#.###.#.#..#.
........#.##.#.#.....#..............###....#.........#.#....#..#........#.#..#.#..........#.#..#..#
#.##...#....#.##.#....##.#..#...#.##.#...##...#.#.#......#.....####.#.#.#.....#..#..#...#.......

output:

-1

result:

ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'

Test #64:

score: 0
Accepted
time: 17ms
memory: 6620kb

input:

100 30
##################################################...##.#........#.###.#..#.......#..#....##########
........................................########..#..........#..#..###......#..........#..##########
################################################..#...##.........##.#..#.##....#..........#...

output:

2.82842712

result:

ok found '2.8284271', expected '2.8284270', error '0.0000000'

Test #65:

score: 0
Accepted
time: 18ms
memory: 6840kb

input:

100 30
.#..######..###..#######.#######...#.###.##.###.#.#..##.#######.#...............##.##.######.###...#
#.....#..#..####..####.##...##.#####..####..##..#..####..#####......#.....#.....########...###.#.###
.#.#.#.###.#...#..##.####..####.#.##..####..####.###..########.....#...#.......####.##.####...

output:

3.00000000

result:

ok found '3.0000000', expected '3.0000000', error '0.0000000'

Test #66:

score: 0
Accepted
time: 94ms
memory: 8208kb

input:

100 281
..............................................................................................######
..............................................................................................######
.............................................................................................

output:

1.00000000

result:

ok found '1.0000000', expected '1.0000000', error '0.0000000'

Test #67:

score: 0
Accepted
time: 81ms
memory: 8160kb

input:

99 149
...................................................................................................
...................................................................................................
................................................................................................

output:

1.41421356

result:

ok found '1.4142136', expected '1.4142140', error '0.0000003'

Test #68:

score: 0
Accepted
time: 82ms
memory: 8420kb

input:

100 150
....................................................................................................
....................................................................................................
.............................................................................................

output:

1.41421356

result:

ok found '1.4142136', expected '1.4142140', error '0.0000003'