696  How Many Knights
Moderator: Board moderators
696
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??
#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??
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
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
Please help, getting WA!
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, pd);
}
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;
}
#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, pd);
}
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;
}
I've fixed it
Finally found a bug:
there should be 'knights' string all the time, even if result is 1
there should be 'knights' string all the time, even if result is 1
Re: 696  How Many Knights
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.
You tried your best and you failed miserably. The lesson is 'never try'. Homer Simpson

 New poster
 Posts: 21
 Joined: Mon Jun 18, 2012 12:52 am
 Location: Dhaka, Bangladesh.
 Contact:
Re: 696  How Many Knights
@plamplam
yeah, thats the big hint indeed, draw it down into notebook and it worked really great.
yeah, thats the big hint indeed, draw it down into notebook and it worked really great.

 New poster
 Posts: 30
 Joined: Thu Jul 19, 2012 11:24 pm
Re: 696  How Many Knights
I've tried every test cases. I don't know what is wrong with my code..
Can you guys help me on this?
Code: Select all
deleted
Last edited by kier.guevara on Sat Jul 21, 2012 8:14 am, edited 1 time in total.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 696  How Many Knights
2x100 AC output 100.
Check input and AC output for thousands of problems on uDebug!

 New poster
 Posts: 30
 Joined: Thu Jul 19, 2012 11:24 pm
Re: 696  How Many Knights
I fixed it and my output for 2 100 is 100 knights.
here is my code:
It is still WA.
here is my code:
Code: Select all
deleted
Last edited by kier.guevara on Sat Jul 21, 2012 8:14 am, edited 1 time in total.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 696  How Many Knights
tempCounter should be initialized inside the while loop.
Check input and AC output for thousands of problems on uDebug!

 New poster
 Posts: 30
 Joined: Thu Jul 19, 2012 11:24 pm
Re: 696  How Many Knights
Thank you so much! i got AC now!
Run time error
Hi,
I am obtaining Run Time Error in a very simple program for 696. The program is:
#include <iostream>
using namespace std;
int main(){
while(true){
int rows, columns;
cin >> rows >> columns;
int greater = max(rows, columns);
int lower = min(rows, columns);
if ((rows == 0) && (columns == 0)){
break;
}
int solution;
if (lower <= 0){
solution = 0;
} else if (lower == 1){
solution = greater;
} else if (lower == 2){
int blocks = greater / 4;
int remaining = min((greater % 4), 2);
solution = blocks * 4 + remaining * 2;
} else {
solution = (rows * columns + 1) / 2;
}
cout << solution << " knights may be placed on a " << rows << " row " << columns << " column board." << endl;
}
}
Can anyone help me?
Thank you in advance.
I am obtaining Run Time Error in a very simple program for 696. The program is:
#include <iostream>
using namespace std;
int main(){
while(true){
int rows, columns;
cin >> rows >> columns;
int greater = max(rows, columns);
int lower = min(rows, columns);
if ((rows == 0) && (columns == 0)){
break;
}
int solution;
if (lower <= 0){
solution = 0;
} else if (lower == 1){
solution = greater;
} else if (lower == 2){
int blocks = greater / 4;
int remaining = min((greater % 4), 2);
solution = blocks * 4 + remaining * 2;
} else {
solution = (rows * columns + 1) / 2;
}
cout << solution << " knights may be placed on a " << rows << " row " << columns << " column board." << endl;
}
}
Can anyone help me?
Thank you in advance.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: Run time error
Yes, there was a general error in the system some weeks ago, while I was sending the solution.
Thank you for your response.
Thank you for your response.
Re: 696  How Many Knights
First, I found it useful to do Problem #278 (Chess) before solving this one.
Next, Here's some input / output that I found useful during testing / debugging.
Input:
AC Output:
Next, Here's some input / output that I found useful during testing / debugging.
Input:
Code: Select all
1 1
1 0
0 1
2 1
1 2
2 2
2 3
3 2
500 500
45 6
7 9
4 10
10 11
2 5
2 283
484 2
123 2
2 500
13 24
2 100
100 2
2 0
0 2
1 6
1 10
10 1
0 0
Code: Select all
1 knights may be placed on a 1 row 1 column board.
0 knights may be placed on a 1 row 0 column board.
0 knights may be placed on a 0 row 1 column board.
2 knights may be placed on a 2 row 1 column board.
2 knights may be placed on a 1 row 2 column board.
4 knights may be placed on a 2 row 2 column board.
4 knights may be placed on a 2 row 3 column board.
4 knights may be placed on a 3 row 2 column board.
125000 knights may be placed on a 500 row 500 column board.
135 knights may be placed on a 45 row 6 column board.
32 knights may be placed on a 7 row 9 column board.
20 knights may be placed on a 4 row 10 column board.
55 knights may be placed on a 10 row 11 column board.
6 knights may be placed on a 2 row 5 column board.
284 knights may be placed on a 2 row 283 column board.
484 knights may be placed on a 484 row 2 column board.
124 knights may be placed on a 123 row 2 column board.
500 knights may be placed on a 2 row 500 column board.
156 knights may be placed on a 13 row 24 column board.
100 knights may be placed on a 2 row 100 column board.
100 knights may be placed on a 100 row 2 column board.
0 knights may be placed on a 2 row 0 column board.
0 knights may be placed on a 0 row 2 column board.
6 knights may be placed on a 1 row 6 column board.
10 knights may be placed on a 1 row 10 column board.
10 knights may be placed on a 10 row 1 column board.