QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #721991 | #5537. Storing Eggs | Suhy# | WA | 0ms | 2136kb | C++14 | 4.3kb | 2024-11-07 17:23:48 | 2024-11-07 17:23:49 |
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>
int main(){
scanf("%d%d",&n,&k);
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));
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 1960kb
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: 1772kb
input:
5 6 ##.## ##### .....
output:
1
result:
ok found '1.0000000', expected '1.0000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 2056kb
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: 1932kb
input:
2 6 .. .# ..
output:
-1
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 2040kb
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: 2088kb
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: 2000kb
input:
100 3 .................................................................................................... .................................................................................................... ...............................................................................................
output:
49.040799
result:
ok found '49.0407990', expected '49.0407990', error '0.0000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 2008kb
input:
100 100 .................................................................................................... .................................................................................................... .............................................................................................
output:
2.000000
result:
ok found '2.0000000', expected '2.0000000', error '0.0000000'
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 2136kb
input:
100 150 .................................................................................................... .................................................................................................... .............................................................................................
output:
2.828427
result:
wrong answer 1st numbers differ - expected: '1.4142140', found: '2.8284270', error = '0.9999993'