## 696 - How Many Knights

Moderator: Board moderators

ram
New poster
Posts: 30
Joined: Wed Mar 06, 2002 2:00 am
Contact:

### 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????

SnapDragon
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?

Moinul(AUST)
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 Larry
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 =)
Last edited by Larry on Sat Dec 14, 2002 12:15 pm, edited 1 time in total.

Moinul(AUST)
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

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

### 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;
}

angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
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! junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
I can't figure out the answer when the row or col = 2. Is there a formula? Any hints? angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia
Look at this pattern for maximum knights on row=2.

Row 1: KK..KK..KK..KK.. and so on
Row 2: KK..KK..KK..KK.. and so on

K means Knight.
. means blank square.

Good Luck ! waqar qayyum
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;

/* 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.

kami
New poster
Posts: 2
Joined: Sat May 15, 2004 10:04 pm

### "Foolish person"

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.  samueljj
New poster
Posts: 18
Joined: Fri Jul 18, 2003 5:24 am

### 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

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### 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. cypressx
New poster
Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm

### 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