696 - How Many Knights

[sakhassan]

Can any1 tell me whats wrong with this code? Why WA??

#include<stdio.h>
#include<math.h>

int main()
{
long int m,n,num;

while(1)
{
scanf("%ld%ld",&m,&n);
if(m==0 && n==0)
break;
//if(m==0)
// continue;
//if(n==0)
// continue;
if(m==1 || n==1)
{
if(m<n)
num=n;
else
num=m;
}
else if(m>=3&&n>=3)
num=((m*n)+1)/2;
else if(m==2 || n==2)
{
if(m<n)
num=2*(n/2 + 1);
else
num=2*(m/2 + 1);
}
if(num>1)
printf("%ld knights may be placed on a %ld row %ld column board.\n",num,m,n);
else
printf("%ld knight may be placed on a %ld row %ld column board.\n",num,m,n);

}
return 0;
}


the out put 0f 2*100 board = 102 pieces isnt it true??

[putput]

hi, as far as i can tell your M or N = 2 part is wrong

else if(m==2 || n==2)
{
if(m<n)
num=2*(n/2 + 1);
else
num=2*(m/2 + 1);
}

let's use some easy samples

2x2
2x4

2 x 2
num = 2*(2/2 +1) = 4 this one is correct!

2 x 3
num = 2*(4/2 +1) = 6 <-- WRONG!

point is in a 2 x X board you can place 4 knights every 4 layers
it's something like this

- - <-- from this point we are be able to start inserting more
x x the - are free spaces
x x if you place a K in any of the x spaces in this sample
K K one of the first K will kill it
K K

[rMegaS]

Here's my code, please help!

#include <stdio.h>

int max(int a, int b) {
return a>b? a:b;
}

int mid(int p) {
int d = p/2;
return max(d, p-d);
}

int main() {
while (true) {
int n,m,l;
scanf("%d%d", &n, &m);
if (n==0 && m==0)
break;
l=max(n,m);
int r = mid(n*m);
if (n>0)
r=max(r,m);
if (m>0)
r=max(r,n);
if (n>=2 && m>=2) {
int t=(l/4) * 4;
if (l%4==1)
t+=2;
if (l%4>1)
t+=4;
r=max(r,t);
}
printf("%d knight%s may be placed on a %d row %d column board.\n",r, ((r==1)?"":"s"), n,m);
}
return 0;
}

[rMegaS]

Finally found a bug:
there should be 'knights' string all the time, even if result is 1

[plamplam]

Any hints? Hell yeah I got a hint for ya. You can always draw a m x n chessboard in your notebook(or whatever) and try to find out the cases. Say draw a 2 x 7 chessboard and think what can be the optimal arrangement. And one more hint: If you place a knight on a standard 8 x 8 chessboard, it will attack only squares of the opposite color. Say a knight is placed on a dark square, then it will only attack light squares and vice versa. This works for any values of m x n, however consider the case when m = 2 and n = 2, i.e, a 2 x 2 board. Here, wherever you place a knight, it doesn't actually attack any of the squares inside the board(if there were imaginary squares outside the board, it would attack imaginary squares of opposite color as mentioned above). So here, the maximum number of knights is 4. There are special cases like this in the problem. Before you read other posts here, try to find it on your own.

[PromeNabid]

@plamplam
yeah, thats the big hint indeed, draw it down into notebook and it worked really great.

[kier.guevara]

I've tried every test cases. I don't know what is wrong with my code..

Code: Select all

deleted


Can you guys help me on this?

[brianfry713]

2x100 AC output 100.

[kier.guevara]

I fixed it and my output for 2 100 is 100 knights.
here is my code:

Code: Select all

deleted


It is still WA.

[brianfry713]

tempCounter should be initialized inside the while loop.

[kier.guevara]

Thank you so much! i got AC now!