QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #722021 | #5537. Storing Eggs | Suhy# | WA | 0ms | 2200kb | C++14 | 4.4kb | 2024-11-07 17:28:48 | 2024-11-07 17:28:51 |
Judging History
answer
#include<cstdio>
int n,k,i,j;
bool a[104][3],dp[104][104][5];
bool check1(){
int r=0;
for(i=1;i<=n;++i)
for(j=0;j<3;++j)if(a[i][j])++r;
if(r>=k)return 1;
return 0;
}
void clear(){
for(int i=0;i<=n;++i)
for(int j=0;j<=k;++j)
for(int w=0;w<5;++w)dp[i][j][w]=0;
}
bool checksq2(){
clear();
dp[0][k][4]=1;
for(i=1;i<=n;++i)
for(j=0;j<=k;++j){
if(a[i][0]&&(dp[i-1][j+1][1]||dp[i-1][j+1][2]||dp[i-1][j+1][4]))dp[i][j][0]=1;
if(a[i][1]&&(dp[i-1][j+1][0]||dp[i-1][j+1][2]||dp[i-1][j+1][3]||dp[i-1][j+1][4]))dp[i][j][1]=1;
if(a[i][2]&&(dp[i-1][j+1][0]||dp[i-1][j+1][1]||dp[i-1][j+1][4]))dp[i][j][2]=1;
if(a[i][0]&&a[i][2]&&(dp[i-1][j+2][1]||dp[i-1][j+2][4]))dp[i][j][3]=1;
for(int w=0;w<5;++w)if(dp[i-1][j][w])dp[i][j][4]=1;
}
for(int w=0;w<5;++w)if(dp[n][0][w])return 1;
return 0;
}
bool check2(){
clear();
dp[0][k][4]=1;
for(i=1;i<=n;++i)
for(j=0;j<=k;++j){
if(a[i][0]&&(dp[i-1][j+1][2]||dp[i-1][j+1][4]))dp[i][j][0]=1;
if(a[i][1]&&(dp[i-1][j+1][4]))dp[i][j][1]=1;
if(a[i][2]&&(dp[i-1][j+1][0]||dp[i-1][j+1][4]))dp[i][j][2]=1;
if(a[i][0]&&a[i][2]&&(dp[i-1][j+2][4]))dp[i][j][3]=1;
for(int w=0;w<5;++w)if(dp[i-1][j][w])dp[i][j][4]=1;
}
for(int w=0;w<5;++w)if(dp[n][0][w])return 1;
return 0;
}
bool checksq5(){
clear();
dp[0][k][4]=1;
for(i=1;i<=n;++i)
for(j=0;j<=k;++j){
for(int w=0;w<5;++w)if(dp[i-1][j][w])dp[i][j][4]=1;
}
for(int w=0;w<5;++w)if(dp[n][0][w])return 1;
return 0;
}
bool checkd0(int dx){
int i,j;
clear();
for(i=0;i<dx;++i){
if(a[i][0])dp[i][k-1][0]=1;
if(a[i][1])dp[i][k-1][1]=1;
if(a[i][2])dp[i][k-1][2]=1;
dp[i][k][4]=1;
}
for(i=dx;i<=n;++i)
for(j=0;j<=k;++j){
if(dp[i-dx][j+1][0]||dp[i-dx][j+1][1]||dp[i-dx][j+1][2]||dp[i-dx][j+1][4]){
if(a[i][0])dp[i][j][0]=1;
if(a[i][1])dp[i][j][1]=1;
if(a[i][2])dp[i][j][2]=1;
}
for(int w=0;w<5;++w)if(dp[i-dx][j][w])dp[i][j][4]=1;
}
for(int w=0;w<5;++w)if(dp[n][0][w])return 1;
return 0;
}
bool checkd1(int dx){
int i,j;
clear();
for(i=0;i<dx;++i){
if(a[i][0])dp[i][k-1][0]=1;
if(a[i][1])dp[i][k-1][1]=1;
if(a[i][2])dp[i][k-1][2]=1;
dp[i][k][4]=1;
}
for(i=dx;i<=n;++i)
for(j=0;j<=k;++j){
if(a[i][0]&&(dp[i-dx][j+1][1]||dp[i-dx][j+1][2]||dp[i-dx][j+1][4]))dp[i][j][0]=1;
if(a[i][1]&&(dp[i-dx][j+1][0]||dp[i-dx][j+1][2]||dp[i-dx][j+1][4]))dp[i][j][1]=1;
if(a[i][2]&&(dp[i-dx][j+1][0]||dp[i-dx][j+1][1]||dp[i-dx][j+1][4]))dp[i][j][2]=1;
for(int w=0;w<5;++w)if(dp[i-dx][j][w])dp[i][j][4]=1;
}
for(int w=0;w<5;++w)if(dp[n][0][w])return 1;
return 0;
}
bool checkd2(int dx){
int i,j;
clear();
for(i=0;i<dx;++i){
if(a[i][0])dp[i][k-1][0]=1;
if(a[i][1])dp[i][k-1][1]=1;
if(a[i][2])dp[i][k-1][2]=1;
dp[i][k][4]=1;
}
for(i=dx;i<=n;++i)
for(j=0;j<=k;++j){
if(a[i][0]&&(dp[i-dx][j+1][2]||dp[i-dx][j+1][4]))dp[i][j][0]=1;
if(a[i][1]&&(dp[i-dx][j+1][4]))dp[i][j][1]=1;
if(a[i][2]&&(dp[i-dx][j+1][0]||dp[i-dx][j+1][4]))dp[i][j][2]=1;
for(int w=0;w<5;++w)if(dp[i-dx][j][w])dp[i][j][4]=1;
}
for(int w=0;w<5;++w)if(dp[n][0][w])return 1;
return 0;
}
#include<cmath>
#include<ctime>
#include<cstdlib>
int main(){
scanf("%d%d",&n,&k);
srand(n+k+time(0));
for(i=0;i<3;++i)
for(j=1;j<=n;++j){
char c;
while(c=getchar(),c!='.'&&c!='#');
if(c=='.')a[j][i]=1;
}
if(!check1()){
puts("-1");
return 0;
}
if(!checksq2()){
puts("1");
return 0;
}
if(!check2()){
printf("%lf\n",sqrt(2));
return 0;
}
//sq5
if(!checkd2(2)){
printf("%lf\n",sqrt(4+(rand()&1)));
return 0;
}
double ans=8;
for(i=3;i<=n;++i){
if(!checkd0(i)){
printf("%lf\n",sqrt(ans));
return 0;
}ans=i*i;
if(!checkd1(i)){
printf("%lf\n",sqrt(ans));
return 0;
}ans=i*i+1;
if(!checkd2(i)){
printf("%lf\n",sqrt(ans));
return 0;
}ans=i*i+4;
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 2064kb
input:
5 2 #.... ..... ....#
output:
4.472136
result:
ok found '4.4721360', expected '4.4721360', error '0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 1836kb
input:
5 6 ##.## ##### .....
output:
1
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 2156kb
input:
3 4 ..# ... ...
output:
1.414214
result:
ok found '1.4142140', expected '1.4142140', error '0.0000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 1840kb
input:
2 6 .. .# ..
output:
-1
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 2108kb
input:
1 2 . . .
output:
2.000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 2200kb
input:
100 2 .................................................................................................... .................................................................................................... ...............................................................................................
output:
99.020200
result:
ok found '99.0202000', expected '99.0202000', error '0.0000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 2136kb
input:
100 3 .................................................................................................... .................................................................................................... ...............................................................................................
output:
49.040799
result:
ok found '49.0407990', expected '49.0407990', error '0.0000000'
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 2076kb
input:
100 100 .................................................................................................... .................................................................................................... .............................................................................................
output:
2.236068
result:
wrong answer 1st numbers differ - expected: '2.0000000', found: '2.2360680', error = '0.1180340'