696 - How Many Knights

[ram]

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]

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)]

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]

As Snap point out, there's a way to put them optimally without using backtracking for n > 2.

This should run really quickly =)

[Moinul(AUST)]

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]

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]

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]

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

[angga888]

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]

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

[kami]

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.

[samueljj]

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?

[sohel]

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]

#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

[sakhassan]

Deleted