## 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????
ram
New poster

Posts: 30
Joined: Wed Mar 06, 2002 2:00 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?
SnapDragon
Problemsetter

Posts: 22
Joined: Tue Jun 11, 2002 12:35 am

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

Posts: 11
Joined: Tue Dec 10, 2002 11:40 am
Location: Dhaka, Bangaldesh

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.
Larry
Guru

Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City

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

Posts: 11
Joined: Tue Dec 10, 2002 11:40 am
Location: Dhaka, Bangaldesh

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

shamim
A great helper

Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Dhaka

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!

angga888
Experienced poster

Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

I can't figure out the answer when the row or col = 2. Is there a formula? Any hints?
junjieliang
Experienced poster

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

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 !

angga888
Experienced poster

Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

### 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[i] = 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.
waqar qayyum
New poster

Posts: 2
Joined: Wed Jun 16, 2004 9:25 am

### "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.
kami
New poster

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

### 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
samueljj
New poster

Posts: 18
Joined: Fri Jul 18, 2003 5:24 am

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

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

### 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
cypressx
New poster

Posts: 41
Joined: Sun Jul 04, 2004 12:16 pm

Deleted
sakhassan
Experienced poster

Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Next