QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#722010 | #5537. Storing Eggs | wjt# | WA | 134ms | 3944kb | C++14 | 1.5kb | 2024-11-07 17:26:56 | 2024-11-07 17:26:57 |
Judging History
answer
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <iomanip>
using namespace std;
const int N = 105;
const double eps = 1e-8;
int n, k;
char c[5][N];
bool p[5][N];
bool is_ok(int x, int y, double num) {
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= n; j++) {
if (!p[i][j] || c[i][j] == '#') continue;
if ( (x - i) * (x - i) + (y - j) * (y - j) < num*num ) return 0;
}
}
return 1;
}
bool check(int s, double num, int d) {
for (int i = s; i <= n; i += d) {
p[1][i] = 1;
}
for (int i = 2; i <= 3; i++) {
for (int j = 1; j <= n; j++) {
if (is_ok(i, j, num)) {
p[i][j] = 1;
}
}
}
int cnt = 0;
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= n; j++) {
if (p[i][j] && c[i][j] == '.') {
++cnt;
}
}
}
return (cnt >= k);
}
bool Check(double num) {
int d = int(ceil(num));
for (int i = 1; i <= n; i++) {
memset(p, 0, sizeof(p));
if (check(i, num, d)) return 1;
}
return 0;
}
int main() {
cin >> n >> k;
int tot = 0;
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= n; j++) {
cin >> c[i][j];
if (c[i][j] == '.') ++tot;
}
}
if (tot < k) {
cout << -1 << endl;
return 0;
}
double l = 1.0, r = sqrt((n-1) * (n-1) + 4.0);
double ans = 1.0;
while (r - l > eps) {
double mid = (l + r) / 2.0;
if (Check(mid)) {
ans = mid;
l = mid;
}
else {
r = mid;
}
}
cout << fixed << setprecision(10) << ans << endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3900kb
input:
5 2 #.... ..... ....#
output:
4.4721359485
result:
ok found '4.4721359', expected '4.4721360', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
5 6 ##.## ##### .....
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
3 4 ..# ... ...
output:
1.4142135619
result:
ok found '1.4142136', expected '1.4142140', error '0.0000003'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
2 6 .. .# ..
output:
-1
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
1 2 . . .
output:
1.9999999925
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
100 2 .................................................................................................... .................................................................................................... ...............................................................................................
output:
99.0201999537
result:
ok found '99.0202000', expected '99.0202000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 8ms
memory: 3904kb
input:
100 3 .................................................................................................... .................................................................................................... ...............................................................................................
output:
49.0407993405
result:
ok found '49.0407993', expected '49.0407990', error '0.0000000'
Test #8:
score: 0
Accepted
time: 49ms
memory: 3900kb
input:
100 100 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.9999999951
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #9:
score: 0
Accepted
time: 66ms
memory: 3944kb
input:
100 150 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.4142135602
result:
ok found '1.4142136', expected '1.4142140', error '0.0000003'
Test #10:
score: 0
Accepted
time: 111ms
memory: 3900kb
input:
100 151 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #11:
score: 0
Accepted
time: 111ms
memory: 3932kb
input:
100 200 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #12:
score: 0
Accepted
time: 111ms
memory: 3744kb
input:
100 201 .................................................................................................... .................................................................................................... .............................................................................................
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #13:
score: 0
Accepted
time: 26ms
memory: 3756kb
input:
60 130 ............................................................ ............................................................ ............................................................
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #14:
score: 0
Accepted
time: 67ms
memory: 3844kb
input:
100 100 .................................................................................................... #################################################################################################### .............................................................................................
output:
1.9999999951
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #15:
score: 0
Accepted
time: 134ms
memory: 3888kb
input:
100 51 #################################################################################################### .................................................................................................... ###########################################################################################...
output:
1.0000000000
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
1 2 # # #
output:
-1
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #17:
score: 0
Accepted
time: 54ms
memory: 3880kb
input:
99 50 ################################################################################################### ................................................................................................... ##############################################################################################...
output:
1.9999999947
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #18:
score: -100
Wrong Answer
time: 60ms
memory: 3832kb
input:
100 47 #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#. .#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# #.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...
output:
1.9999999951
result:
wrong answer 1st numbers differ - expected: '2.8284270', found: '2.0000000', error = '0.2928932'