696  How Many Knights
Moderator: Board moderators
696  How Many Knights
I am getting WA. the only special cases I see are when row or col = 1 or 2
Are there any other special cases???????
Here is the output from my program.
6 3
9 knights
2 2
4 knights
1 10
10 knights
2 3
4 knights
2 4
4 knights
Are there any other special test cases????
Are there any other special cases???????
Here is the output from my program.
6 3
9 knights
2 2
4 knights
1 10
10 knights
2 3
4 knights
2 4
4 knights
Are there any other special test cases????

 Problemsetter
 Posts: 22
 Joined: Tue Jun 11, 2002 12:35 am
No, there are no other special cases. (Make sure you return 6 for 2,5 and 8 for 2,6, etc.) I was getting WA for a while and I proved that the naive setup works when both dimensions are >= 3. Turns out my solution just had a stupid error: I was swapping x and y to get x <= y, but this made my output rows/columns incorrect. D'oh. Maybe you have the same problem?

 New poster
 Posts: 11
 Joined: Tue Dec 10, 2002 11:40 am
 Location: Dhaka, Bangaldesh
 Contact:
Stack Overflow or TLE
I am getting Correct answer for a Board of less than 300x300
I have checked all the suggested inputs above and it seems to count the Knights correctly.
But For a board of 500x500 or less, I am getting 'Time Limit Exceeds'.
I did simple backtracking To place the nights statring from (0,0)
Can anyone suggests, how to reduce the time of placing the nights more quickly in a large board..... For a large board, i get 'Stack Overflow' sometimes.. How to handle this overflow....
Moinul
I have checked all the suggested inputs above and it seems to count the Knights correctly.
But For a board of 500x500 or less, I am getting 'Time Limit Exceeds'.
I did simple backtracking To place the nights statring from (0,0)
Can anyone suggests, how to reduce the time of placing the nights more quickly in a large board..... For a large board, i get 'Stack Overflow' sometimes.. How to handle this overflow....
Moinul

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
As Snap point out, there's a way to put them optimally without using backtracking for n > 2.
This should run really quickly =)
This should run really quickly =)
Last edited by Larry on Sat Dec 14, 2002 12:15 pm, edited 1 time in total.

 New poster
 Posts: 11
 Joined: Tue Dec 10, 2002 11:40 am
 Location: Dhaka, Bangaldesh
 Contact:
At last , I have made the problem accepted in 0:00.156 sec, without any backtracking.
I did some calculation on the given row x col, & shown the output directly.
But, for the cases where any of row or col is less than 3, I stored the results of those cases in a 500x2 array.
Thanks to All of you for your posts.
Moinul
I did some calculation on the given row x col, & shown the output directly.
But, for the cases where any of row or col is less than 3, I stored the results of those cases in a 500x2 array.
Thanks to All of you for your posts.
Moinul
696 knights Why WA
why do I get a WA.
Note: I have assumed that the number of knights is given by the formula,
(rows*columns + 1)/2. It seems to work for the sample Data.
#include<stdio.h>
int main()
{
unsigned long rows,columns,pieces;
do
{
scanf("%lu %lu",&rows,&columns);
if(!rows && !columns) break;
if(rows==1) pieces=columns;
else if(columns==1) pieces=rows;
else if(rows==2 && columns==3) pieces=4;
else if(rows==2 && columns==2) pieces=4;
else if( rows==3 && columns==2) pieces=4;
else pieces=((rows*columns)+1)/2;
printf("%lu knights may be placed on a %lu row %lu column board.\n",pieces,rows,columns);
}while(1);
return 0;
}
Note: I have assumed that the number of knights is given by the formula,
(rows*columns + 1)/2. It seems to work for the sample Data.
#include<stdio.h>
int main()
{
unsigned long rows,columns,pieces;
do
{
scanf("%lu %lu",&rows,&columns);
if(!rows && !columns) break;
if(rows==1) pieces=columns;
else if(columns==1) pieces=rows;
else if(rows==2 && columns==3) pieces=4;
else if(rows==2 && columns==2) pieces=4;
else if( rows==3 && columns==2) pieces=4;
else pieces=((rows*columns)+1)/2;
printf("%lu knights may be placed on a %lu row %lu column board.\n",pieces,rows,columns);
}while(1);
return 0;
}
I think you'd better swap the row and column first so that the column is always bigger than the row, or vice versa (to simplify the calculation).
And don't forget to output exactly the same as the input (although you've swap the column and row).
In your code, you only consider the inputs (2,2) (2,3) and (1,...)
Your formula works only for m>=3 and n>=3. So you must make another formula to face n=2 or m=2. How about (2,5) and (2,6) and also (2,7) (2,...) until (2,500) ?
Try these inputs:
2 5 = 6 pieces
2 6 = 8 pieces
2 7 = 8 pieces
2 10 = 12 pieces
2 100 = 100 pieces
2 250 = 252 pieces
2 497 = 498 pieces
Good Luck!
And don't forget to output exactly the same as the input (although you've swap the column and row).
In your code, you only consider the inputs (2,2) (2,3) and (1,...)
Your formula works only for m>=3 and n>=3. So you must make another formula to face n=2 or m=2. How about (2,5) and (2,6) and also (2,7) (2,...) until (2,500) ?
Try these inputs:
2 5 = 6 pieces
2 6 = 8 pieces
2 7 = 8 pieces
2 10 = 12 pieces
2 100 = 100 pieces
2 250 = 252 pieces
2 497 = 498 pieces
Good Luck!

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore

 New poster
 Posts: 2
 Joined: Wed Jun 16, 2004 9:25 am
696 How many Knight
Whats wrong with my code Y it gives wrong answer
#include <iostream>
#include <assert.h>
using namespace std;
int main(void)
{
int count = 0;
int j = 0;
int m = 0;
int n = 0;
//int input[1000];
/* for(int i=0;i <100;i++)
input = 0;
while(true)
{
cin>>m>>n;
assert(m <= 500 && n <= 500);
if(m > 1 && n > 1)
{
input[j] = m;
input[j+1]=n;
}
assert(m > 1 && n > 1);
if(n == 0  m == 0)
{
input[j] = 0;
input[j+1]=0;
break;
}
j+=2;
}
*/
//int l = 0;
cin>>m>>n;
assert(m <= 500 && n <= 500);
assert(m > 1 && n > 1);
while(m != 0 && n != 0)
{
count = 0;
int i=1;
int k=1;
int flag=0;
//if(input[l] == 0)
// break;
//m = input[l];
//n = input[l+1];
j = 0;
if(m == 2)
{
while(j < n)
{
if(flag == 0)
{
if(j+1 == n)
count++;
else
count = count + 2;
flag = 1;
}
else
{
flag = 0;
}
j+=2;
}
count = count * 2;
}
else if(n == 2)
{
while(j < m)
{
if(flag == 0)
{
if(j+1 == m)
count++;
else
count = count + 2;
flag = 1;
}
else
{
flag = 0;
}
j+=2;
}
count = count * 2;
}
else if(m > 1 && n > 1)
{
for(i= 0; i < m;i++)
{
if(flag == 0 && j > n  1)
{
j = 1;
flag = 1;
}
else if(flag == 1 && j >= n)
{
j = 0;
flag = 0;
}
while(j < n)
{
count++;
j = j + 2;
}
}
}
else if(m > 1)
count = m;
else
count = n;
cout<<count;
cout<<" knights may be places on a ";
cout<<m;
cout<<" row ";
cout<<n;
cout<<" column board\n";
//l = l + 2;
cin>>m>>n;
assert(m <= 500 && n <= 500);
assert(m > 1 && n > 1);
}
return 0;
}
#include <iostream>
#include <assert.h>
using namespace std;
int main(void)
{
int count = 0;
int j = 0;
int m = 0;
int n = 0;
//int input[1000];
/* for(int i=0;i <100;i++)
input = 0;
while(true)
{
cin>>m>>n;
assert(m <= 500 && n <= 500);
if(m > 1 && n > 1)
{
input[j] = m;
input[j+1]=n;
}
assert(m > 1 && n > 1);
if(n == 0  m == 0)
{
input[j] = 0;
input[j+1]=0;
break;
}
j+=2;
}
*/
//int l = 0;
cin>>m>>n;
assert(m <= 500 && n <= 500);
assert(m > 1 && n > 1);
while(m != 0 && n != 0)
{
count = 0;
int i=1;
int k=1;
int flag=0;
//if(input[l] == 0)
// break;
//m = input[l];
//n = input[l+1];
j = 0;
if(m == 2)
{
while(j < n)
{
if(flag == 0)
{
if(j+1 == n)
count++;
else
count = count + 2;
flag = 1;
}
else
{
flag = 0;
}
j+=2;
}
count = count * 2;
}
else if(n == 2)
{
while(j < m)
{
if(flag == 0)
{
if(j+1 == m)
count++;
else
count = count + 2;
flag = 1;
}
else
{
flag = 0;
}
j+=2;
}
count = count * 2;
}
else if(m > 1 && n > 1)
{
for(i= 0; i < m;i++)
{
if(flag == 0 && j > n  1)
{
j = 1;
flag = 1;
}
else if(flag == 1 && j >= n)
{
j = 0;
flag = 0;
}
while(j < n)
{
count++;
j = j + 2;
}
}
}
else if(m > 1)
count = m;
else
count = n;
cout<<count;
cout<<" knights may be places on a ";
cout<<m;
cout<<" row ";
cout<<n;
cout<<" column board\n";
//l = l + 2;
cin>>m>>n;
assert(m <= 500 && n <= 500);
assert(m > 1 && n > 1);
}
return 0;
}
Last edited by waqar qayyum on Mon Jun 28, 2004 11:17 am, edited 3 times in total.
"Foolish person"
I have seen your code.
What is the problem with your code?
Do you want to learn C++ then take the book of Ivor Horton and study its first 6 chapters.
Please give us the question what is the problem in this code you have not placed any question.
What is the problem with your code?
Do you want to learn C++ then take the book of Ivor Horton and study its first 6 chapters.
Please give us the question what is the problem in this code you have not placed any question.
Kamran Ahmad
696(Checking the idea)
I think if the knights are placed in the diagonal cells then it will produce the largest number of knights' arrangement. Is this not correct? when this does not work?
novice programmer
not sure
What do you exactly mean by diagonal cells?
If you are trying to place all of them in black or white squares then it will work only if both dimensions of the board is greater than 2, otherwise you have to consider in a different way.
Take the first sample input as example :
.k.
k.k
here you can place 3 knights using the above method.
but if you place it like
kk.
kk.
you can place 4 of them.
If you are trying to place all of them in black or white squares then it will work only if both dimensions of the board is greater than 2, otherwise you have to consider in a different way.
Take the first sample input as example :
.k.
k.k
here you can place 3 knights using the above method.
but if you place it like
kk.
kk.
you can place 4 of them.
696
#include <stdio.h>
#define max(a,b) (a>b?a:b)
int n,m;
int main() {
int ans;
while(scanf("%d%d",&n,&m)==2) {
if(n==1  m==1) ans = max(n,m);
else if(n>=3 && m>=3) ans = (n*m + 1)/2;
else {
int i=0;
int f = max(n,m);
ans = 0;
while(i<=f) {
i++;
if(i>f) break;
ans+=2;
i++;
if(i>f) break;
ans+=2;
i++; if(i>f) break;
i++; if(i>f) break;
}
}
printf("%d knights may be placed on a %d row %d column board.\n",ans,n,m);
}
return 0;
}
I don`t know why this is wa. I think the only possible thing is :
if(n>=3 && m>=3) ans = (n*m + 1)/2;
but it seems right to me
If u can please help
#define max(a,b) (a>b?a:b)
int n,m;
int main() {
int ans;
while(scanf("%d%d",&n,&m)==2) {
if(n==1  m==1) ans = max(n,m);
else if(n>=3 && m>=3) ans = (n*m + 1)/2;
else {
int i=0;
int f = max(n,m);
ans = 0;
while(i<=f) {
i++;
if(i>f) break;
ans+=2;
i++;
if(i>f) break;
ans+=2;
i++; if(i>f) break;
i++; if(i>f) break;
}
}
printf("%d knights may be placed on a %d row %d column board.\n",ans,n,m);
}
return 0;
}
I don`t know why this is wa. I think the only possible thing is :
if(n>=3 && m>=3) ans = (n*m + 1)/2;
but it seems right to me
If u can please help