QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#96493 | #5153. Delft Distance | Ahmed_Abdelmegeed | TL | 3070ms | 89432kb | C++20 | 7.0kb | 2023-04-13 22:24:43 | 2023-04-13 22:24:44 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define el "\n"
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ordered_multiset tree<ll, null_type,less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
const ll N = 700 + 10, INF = 1e18;
const ld pi = acos(-1);
const int mod = 1e9 + 7, LOG = 20;
const ld eps = 1e-4;
int dx[] = {0, -1, 0, 1, -1, 1, -1, 1};
int dy[] = {-1, 0, 1, 0, 1, -1, -1, 1};
ll n, m, k, x, y;
ld sidecircle = 0.5 * pi * 5;
ld dis[N][N][10], vis[N][N][10];
char grid[N][N];
void zbtsquare(int x, int y) {
ld cur;
for (int i = 0; i < 8; i++) {
cur = 0;
for (int j = i; j < i + 8; j++) {
dis[x][y][j % 8] = min(cur + dis[x][y][i], dis[x][y][j % 8]);
cur += 5;
}
cur = 0;
for (int j = i; j > i - 8; j--) {
dis[x][y][(j + 8) % 8] = min(cur + dis[x][y][i], dis[x][y][(j + 8) % 8]);
cur += 5;
}
}
}
void zbtcircle(int x, int y) {
ld cur;
for (int i = 1; i < 8; i += 2) {
cur = 0;
for (int j = i; j < i + 8; j += 2) {
//cout << x << " " << y << " " << j << " " << cur + dis[x][y][i] << el;
dis[x][y][j % 8] = min(cur + dis[x][y][i], dis[x][y][j % 8]);
cur += sidecircle;
}
cur = 0;
for (int j = i; j > i - 8; j -= 2) {
//cout << x << " " << y << " " << j << " " << cur + dis[x][y][i] << el;
dis[x][y][(j + 8) % 8] = min(cur + dis[x][y][i], dis[x][y][(j + 8) % 8]);
cur += sidecircle;
}
}
}
bool valid(int x, int y) {
return (x >= 1 && x <= n && y >= 1 && y <= m);
}
void trantition(int x, int y, priority_queue<pair<ld, pair<pair<int, int>, int>>> &pq) {
if (valid(x + 1, y - 1)) {
if (dis[x + 1][y - 1][2] > dis[x][y][6]) {
dis[x + 1][y - 1][2] = dis[x][y][6];
pq.push({-dis[x + 1][y - 1][2], {{x + 1, y - 1}, 2}});
}
}
if (valid(x + 1, y - 1)) {
if (dis[x][y + 1][0] > dis[x][y][2]) {
dis[x][y + 1][0] = dis[x][y][2];
pq.push({-dis[x][y + 1][0], {{x, y + 1}, 0}});
}
if (dis[x][y + 1][7] > dis[x][y][3]) {
dis[x][y + 1][7] = dis[x][y][3];
pq.push({-dis[x][y + 1][7], {{x, y + 1}, 7}});
}
if (dis[x][y + 1][6] > dis[x][y][4]) {
dis[x][y + 1][6] = dis[x][y][4];
pq.push({-dis[x][y + 1][6], {{x, y + 1}, 6}});
}
}
if (valid(x + 1, y + 1)) {
if (dis[x + 1][y + 1][0] > dis[x][y][4]) {
dis[x + 1][y + 1][0] = dis[x][y][4];
pq.push({-dis[x + 1][y + 1][0], {{x + 1, y + 1}, 0}});
}
}
if (valid(x + 1, y)) {
if (dis[x + 1][y][2] > dis[x][y][4]) {
dis[x + 1][y][2] = dis[x][y][4];
pq.push({-dis[x + 1][y][2], {{x + 1, y}, 2}});
}
if (dis[x + 1][y][1] > dis[x][y][5]) {
dis[x + 1][y][1] = dis[x][y][5];
pq.push({-dis[x + 1][y][1], {{x + 1, y}, 1}});
}
if (dis[x + 1][y][0] > dis[x][y][6]) {
dis[x + 1][y][0] = dis[x][y][6];
pq.push({-dis[x + 1][y][0], {{x + 1, y}, 0}});
}
}
if (valid(x - 1, y + 1)) {
if (dis[x - 1][y + 1][6] > dis[x][y][2]) {
dis[x - 1][y + 1][6] = dis[x][y][2];
pq.push({-dis[x - 1][y + 1][6], {{x + 1, y}, 6}});
}
}
if (valid(x, y - 1)) {
if (dis[x][y - 1][2] > dis[x][y][0]) {
dis[x][y - 1][2] = dis[x][y][0];
pq.push({-dis[x][y - 1][2], {{x, y - 1}, 2}});
}
if (dis[x][y - 1][3] > dis[x][y][7]) {
dis[x][y - 1][3] = dis[x][y][7];
pq.push({-dis[x][y - 1][3], {{x, y - 1}, 3}});
}
if (dis[x][y - 1][4] > dis[x][y][6]) {
dis[x][y - 1][4] = dis[x][y][6];
pq.push({-dis[x][y - 1][4], {{x, y - 1}, 4}});
}
}
if (valid(x - 1, y - 1)) {
if (dis[x - 1][y - 1][4] > dis[x][y][0]) {
dis[x - 1][y - 1][4] = dis[x][y][0];
pq.push({-dis[x - 1][y - 1][4], {{x - 1, y - 1}, 4}});
}
}
if (valid(x - 1, y)) {
if (dis[x - 1][y][6] > dis[x][y][0]) {
dis[x - 1][y][6] = dis[x][y][0];
pq.push({-dis[x - 1][y][6], {{x - 1, y}, 6}});
}
if (dis[x - 1][y][5] > dis[x][y][1]) {
dis[x - 1][y][5] = dis[x][y][1];
pq.push({-dis[x - 1][y][5], {{x - 1, y}, 5}});
}
if (dis[x - 1][y][4] > dis[x][y][2]) {
dis[x - 1][y][4] = dis[x][y][2];
pq.push({-dis[x - 1][y][4], {{x - 1, y}, 4}});
}
}
if (valid(x, y + 1)) {
if (dis[x][y + 1][0] > dis[x][y][2]) {
dis[x][y + 1][0] = dis[x][y][2];
pq.push({-dis[x][y + 1][0], {{x, y + 1}, 0}});
}
if (dis[x][y + 1][7] > dis[x][y][3]) {
dis[x][y + 1][7] = dis[x][y][3];
pq.push({-dis[x][y + 1][7], {{x, y + 1}, 7}});
}
if (dis[x][y + 1][6] > dis[x][y][4]) {
dis[x][y + 1][6] = dis[x][y][4];
pq.push({-dis[x][y + 1][6], {{x, y + 1}, 6}});
}
}
//cout << pq.size() << el;
}
void solve() {
priority_queue<pair<ld, pair<pair<int, int>, int>>> pq;
dis[1][1][0] = 0;
pq.push({0, {{1, 1}, 0}});
ld cost;
int state;
while (pq.size()) {
x = pq.top().second.first.first;
y = pq.top().second.first.second;
cost = -pq.top().first;
state = pq.top().second.second;
pq.pop();
if (dis[x][y][state] < cost) {
continue;
}
zbtsquare(x, y);
if (grid[x][y] == 'O') {
zbtcircle(x, y);
zbtsquare(x, y);
}
for (int i = 0; i < 8; i++) {
//cout << dis[x][y][i] << el;
if (vis[x][y][i] > dis[x][y][i]) {
pq.push({-dis[x][y][i], {{x, y}, i}});
//cout << x << " " << y << " " << i << el;
vis[x][y][i] = dis[x][y][i];
}
}
trantition(x, y, pq);
}
}
void dowork() {
cin >> n >> m;
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= 8; k++) {
dis[i][j][k] = vis[i][j][k] = 2e18;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> grid[i][j];
}
}
solve();
cout << fixed << setprecision(10) << dis[n][m][4] << el;
}
signed main() {
fast
int t = 1;
//cin >> t;
for (int i = 1; i <= t; i++) {
dowork();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5672kb
input:
3 5 XOOXO OXOXO XXXXO
output:
71.4159265359
result:
ok found '71.4159265', expected '71.4159265', error '0.0000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 5820kb
input:
1 4 XOOX
output:
45.7079632679
result:
ok found '45.7079633', expected '45.7079633', error '0.0000000'
Test #3:
score: 0
Accepted
time: 2ms
memory: 5684kb
input:
1 1 X
output:
20.0000000000
result:
ok found '20.0000000', expected '20.0000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 3ms
memory: 7896kb
input:
1 1 O
output:
17.8539816340
result:
ok found '17.8539816', expected '17.8539816', error '0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 5692kb
input:
1 3 XOO
output:
35.7079632679
result:
ok found '35.7079633', expected '35.7079633', error '0.0000000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 5664kb
input:
1 5 OXOOO
output:
55.7079632679
result:
ok found '55.7079633', expected '55.7079633', error '0.0000000'
Test #7:
score: 0
Accepted
time: 3ms
memory: 7776kb
input:
6 10 XXXXXOOOOX XXOOOOOOOO XXXOXOOXOX OXOXOXXOOX OOXXOXXXXO OXOXXOOXOO
output:
142.8318530718
result:
ok found '142.8318531', expected '142.8318531', error '0.0000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 5784kb
input:
1 2 XX
output:
30.0000000000
result:
ok found '30.0000000', expected '30.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 3ms
memory: 7836kb
input:
10 1 X X X O O O X O O X
output:
105.7079632679
result:
ok found '105.7079633', expected '105.7079633', error '0.0000000'
Test #10:
score: 0
Accepted
time: 4ms
memory: 7996kb
input:
18 6 OOOOOO OOOOOO XOOOOO OOOOXO OOOXOO OOOOOO OOOOOO OOOOOO OOOOOX OOOOOO OOOXOO OOOOOO OOOOOO OOOOOO OOOOOO OOOOOO OOOOOO OOOOOO
output:
214.2477796077
result:
ok found '214.2477796', expected '214.2477796', error '0.0000000'
Test #11:
score: 0
Accepted
time: 3ms
memory: 8148kb
input:
40 9 OOOOXOXXX XOXXXOXXO OXOXXXXXO OXOXXXOXX XXXXOXOXX XXOOXOXXX XOOXOXXXX XOXXOOXOX OXXOOOOXX XXOOOXXOO OXOOXOXXX OOOOOXOOO OXXXXXXXO OOOOOOOXX OOOXXXOOX OXOXXOOOO OOOOXOXOO OXOXOOOXO OXXOOXXXO OXOOXOOXO XXXOXOXOO XXOOOXOOX OOXXOOXOO XOOXXXXOX OXXXXOOOO OXOOOOXOX XXOXXXOOO OOXOOOXXX OXOOOOXOO OXOOO...
output:
453.5176877776
result:
ok found '453.5176878', expected '453.5176878', error '0.0000000'
Test #12:
score: 0
Accepted
time: 19ms
memory: 8568kb
input:
41 50 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXO XXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXOXXXXXXXXXXXXXXX XXXXXXXXXXXXXOXXXXXXXXXXXXXXOXXXXXXXXXX...
output:
873.5176877776
result:
ok found '873.5176878', expected '873.5176878', error '0.0000000'
Test #13:
score: 0
Accepted
time: 1374ms
memory: 62980kb
input:
329 527 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
8560.0000000000
result:
ok found '8560.0000000', expected '8560.0000000', error '0.0000000'
Test #14:
score: 0
Accepted
time: 110ms
memory: 13472kb
input:
49 297 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
3451.4159265359
result:
ok found '3451.4159265', expected '3451.4159265', error '0.0000000'
Test #15:
score: 0
Accepted
time: 229ms
memory: 23336kb
input:
357 83 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
4342.0575041173
result:
ok found '4342.0575041', expected '4342.0575041', error '0.0000000'
Test #16:
score: 0
Accepted
time: 2169ms
memory: 89432kb
input:
417 615 XXXXXXXXOXXXXXXXXXXXOXXXXXXXXXXXOXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXOXXXXXXXXXXXXXXOXXXXXOXXXOOXXXXXXXXXXXXXXXXXXXXXOXOXXOXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXOXXXXXXOXXXXXXXXOXXXXXXXOXXXXXXXXXXXXXXXXOXXXXXXOXXXXXXXOXXXXXXXXXXOXXXXXXXXOXXXOXXXOXXXXXOXXXOXXXXXXXXXOXXXXXXXXXXXXXXXXXXXX...
output:
9736.2830044411
result:
ok found '9736.2830044', expected '9736.2830044', error '0.0000000'
Test #17:
score: 0
Accepted
time: 856ms
memory: 38252kb
input:
359 225 OOOOXXOOXOXXXOOOOOXOXOOOXOOXXXXXOOOXOXXXOOOOXXOXXOOXOXOXXOXOXXXOXXXXXOOOXXXXXXXOOOOXXXXXOOXOXXOXOXOXXOXOXXOXOXOOOXOXXXOOXOXOXXXXOXOOXXOXXOXOXOXXOXXXOOOXXOOOXXOXXXXXOXOXOOXXOOXOXXOXXOOOOOXOXOOXXXOOXOOXOOOOXOXOOXXOOOXOOOXXXXOXX OXOOOXXXOOXOOXOOXXOOXXOOXXOXXOOOOOXOXXOOXXXOXXXOXOOOXOOXXOOXOXXOXO...
output:
5026.6590392763
result:
ok found '5026.6590393', expected '5026.6590393', error '0.0000000'
Test #18:
score: 0
Accepted
time: 1384ms
memory: 44724kb
input:
261 431 OOOOOOOXOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOXOOOOOOXOOOXXOOOOOOOOOOOOOOXOOXOOOOOOXOOOOOOOOOXOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOXOXOOOOOOOOOOOOOXOOOXOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOXXOOXOOOOOOOOOOOXOOXOOOOXOXXOOOOOOOOOOXOXOOOOOOOOOOOOOXOOOOOOOOOOOOOXOOOOOOOOXOOOOOOOOOOO...
output:
5799.7784129347
result:
ok found '5799.7784129', expected '5799.7784129', error '0.0000000'
Test #19:
score: 0
Accepted
time: 196ms
memory: 11020kb
input:
37 427 OOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOXOOOXOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...
output:
4481.1946409141
result:
ok found '4481.1946409', expected '4481.1946409', error '0.0000000'
Test #20:
score: 0
Accepted
time: 560ms
memory: 21348kb
input:
105 430 OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...
output:
4899.3361431346
result:
ok found '4899.3361431', expected '4899.3361431', error '0.0000000'
Test #21:
score: 0
Accepted
time: 3070ms
memory: 81112kb
input:
465 484 OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...
output:
7494.2029195963
result:
ok found '7494.2029196', expected '7494.2029196', error '0.0000000'
Test #22:
score: 0
Accepted
time: 26ms
memory: 12644kb
input:
266 8 OXOOXXOX OOXOXXXX XXXXOXXX XXOOOOXX XXOXXXOO OXOXXOXO XXOXOXXO OOOXOXOO OXOXOXOO XOOXOOXX XXOXOXXO OXOOOOXO XXOOXOOO OXOOXXXX XOOOXOXO XOXOOXOX OOXOOXOX XXOOOXXO XOOXXOXX XOXOXOXX OXOOOOOO XOOXOXOX OXXXOOXX XXXOOXOO XOOOXXOO OXXXXXXO OXOXXOOX OXXOXXOX OXOXOOXO XXXOXOOO OXOXOOXO OXXXOXXX XXXXOX...
output:
2705.6637061436
result:
ok found '2705.6637061', expected '2705.6637061', error '0.0000000'
Test #23:
score: 0
Accepted
time: 23ms
memory: 11828kb
input:
366 8 XXXXXXXO XXXXXXXX XXXXXXXX XXXXXXXX XXXXXXOX XXXXOXXX XOXXXXXO XXXXOXXX OXXXXOXX XXXXXXXX XXXXXXXX OXXXXXXX XXXXXXXX XXXOXXXX XXOXXXXX XXXOXXOX XXXOXXXX XXXXOXXX XXXXXXXX XXXXXXOO XXXXXXXX XXXXXXXX XXXXOXXX XXXXXXXX XOXXXXXX XXXXXXXX XXXXXXXX XOXXXOXX XXXXXXXX XXXXXXXX XXXXXXXX XXXXXXXX XXXXXX...
output:
3712.1017612417
result:
ok found '3712.1017612', expected '3712.1017612', error '0.0000000'
Test #24:
score: 0
Accepted
time: 0ms
memory: 8180kb
input:
56 2 XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XO XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX
output:
577.8539816340
result:
ok found '577.8539816', expected '577.8539816', error '0.0000000'
Test #25:
score: 0
Accepted
time: 7ms
memory: 11816kb
input:
437 2 XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX OX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX XX ...
output:
4385.7079632679
result:
ok found '4385.7079633', expected '4385.7079633', error '0.0000000'
Test #26:
score: 0
Accepted
time: 7ms
memory: 8000kb
input:
4 204 OXOOXXXOOOXOOXXOXOXXXXOXXXXOXXXOXXOXXOXOOXOOOOXXXOXOXXXOXOOOOOXOXXXOOXOXXXXOXOOXXXOXOXOXXXOXOXXOOOXOOOXOXXXOXOOXXOOXOOOOOXOOOOOOXOXOXXOOOXXXXOOOXOOOXOOOOXXOXXOOXOXXOXOOXOOXXXOOXXOOXXXXOOOXOXXXXOOXXOOOOXXO OXXXXXOOXOOXOXOOXOXOOOOXXOXOOOOOXOOOXOOOXOXXXOXXOXXXOOXOOXXXXXOXOXXXXXXOOXXOXXXXXOXOXOOXO...
output:
2062.8318530718
result:
ok found '2062.8318531', expected '2062.8318531', error '0.0000000'
Test #27:
score: 0
Accepted
time: 7ms
memory: 5840kb
input:
4 164 XXXXXXXXXXXXOXXXXOXXXXXXXXXXXXXXXXXXXXXXOXOXOOXOXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXOXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXOXXXXXXXXXXXXXXXXOXXXO XXXOXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXOXXXXXXXXXXXXOOXXXXXXOXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXOXXX...
output:
1662.8318530718
result:
ok found '1662.8318531', expected '1662.8318531', error '0.0000000'
Test #28:
score: 0
Accepted
time: 21ms
memory: 8056kb
input:
10 243 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
2514.9778714378
result:
ok found '2514.9778714', expected '2514.9778714', error '0.0000000'
Test #29:
score: 0
Accepted
time: 22ms
memory: 7728kb
input:
7 478 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
4847.8539816340
result:
ok found '4847.8539816', expected '4847.8539816', error '0.0000000'
Test #30:
score: 0
Accepted
time: 1673ms
memory: 59820kb
input:
400 400 OOOXXOXOXXXXXOXOXXOOXXXXOOXXXOXXOOXOXOOXOXOOOXXOXXOOOOXXOXOOXOXOXOXXXOOXOXOOXOOXXXOXXXXXXOOXXXXOXOXXXOOXOXOXXOOOOXXXXXOOXXXXXXXOOOXOXXXOXXOOOOXXOXXOXXOOOOXXOXOXOOXXOOXXXOOXOOOXXXXXXOOOXXOXOXOXOOOXOXOXXXXXXXXOXOOOXOXXOOXOXXXXOOXXXXXXOXOOXXXOXOOOOOXOXXOXXXXOOOXXOXOOOXOXOOOOXXXXOXXOXOOOOXOOXOXO...
output:
6823.9819354180
result:
ok found '6823.9819354', expected '6823.9819354', error '0.0000000'
Test #31:
score: 0
Accepted
time: 2037ms
memory: 59276kb
input:
400 400 OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...
output:
6285.3313255456
result:
ok found '6285.3313255', expected '6285.3313255', error '0.0000000'
Test #32:
score: 0
Accepted
time: 1256ms
memory: 60092kb
input:
400 400 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...
output:
8000.0000000000
result:
ok found '8000.0000000', expected '8000.0000000', error '0.0000000'
Test #33:
score: 0
Accepted
time: 1301ms
memory: 60152kb
input:
400 400 XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXOXXXXXXXXXXXXXXXX...
output:
7854.0707511103
result:
ok found '7854.0707511', expected '7854.0707511', error '0.0000000'
Test #34:
score: 0
Accepted
time: 1900ms
memory: 60152kb
input:
400 400 OOOOOOOXOOOOXOOOOXOXOOOOOOXOOOOOOOXOOOOOOOOOOXOOOOXOOOXOOXOOOOOOOOOOOXOOXOXOOOOOOOOOOOOOOXOOXXOXOOOOOOXOXOOOXOOOOOOOXXOOOXOOOXOXOOOOXOOOOOOOOOOOXXOXOOOXXOOOOOOOOOOOOXOOOOXOOOXOOXOOOXOOOOOXXOOOXOOOOOOOOOOOOOOXOOOOOOOXXOOOOXXOOOOOOOOXOOOOOXOOOXOOXOOOOOOOOXOOOOOOXOOOOOOOOXOXOOOOOXXOOOOOOOOOXXXO...
output:
6478.4729784879
result:
ok found '6478.4729785', expected '6478.4729785', error '0.0000000'
Test #35:
score: -100
Time Limit Exceeded
input:
700 700 XXXOXOXOXOOXOOXXXOOOOOXXXXOXOXOOXXOXXXOOOOOXXOXOXXXXOOOXXOXXXOXXXXXOXXXOOXXOOXOOXOXXOOXXXOOOXOOOOXXOXOOXOOXXOOXOOOXXXXOXOXOXOOOXOOXOOXXOOOXOOXOOOOXXXXXXOOXOOXXXOOOOXOOXOOXOXOOOOXOXOOXXXOXXOXOXOXXXXXOXXOOOOXXXOXOXXXOXXXXOOOXXXOXXOXXOXOOOOOOXOXOXOXXXXOXXOXXOXXOOOXXOOXOXXXOXOXOOOXOOXOOOOXOOOOOO...