Author & Editorialist: Alei Reyes
Tester: Encho Mishinev

CAKEWALK

# PREREQUISITES:

Basic programming

# PROBLEM:

Place a king and some obstacles in a chessboard such that the king can reach exactly K distinct cells.

# SOLUTIONS:

Setter's Solution
``````    import sys
t=input()
for tt in range(t):
k=input()
ans=[['.' for i in range(8)] for j in range(8)]
ans[7][7]='O'
c=64-k
for i in range(8):
for j in range(8):
if c>0:
ans[i][j]='X'
c-=1
for i in range(8):
print "".join(ans[i])
``````
Tester's Solution
``````#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
int i,j;
int t,test;

scanf("%d",&t);

for (test=1;test<=t;test++)
{
int k;
int blocked;

scanf("%d", &k);

blocked = 64 - k;

for (i=1;i<=8;i++)
{
for (j=1;j<=8;j++)
{
if (i == 8 && j == 8)
{
printf("O");
continue;
}

if (blocked > 0)
{
printf("X");
blocked--;
}
else
{
printf(".");
}
}
printf("\n");
}
}

return 0;
}
``````
2 Likes

t=int(input())
for t_cases in range(t):
#n=t_cases
n = int(input())
count = 0
end = n+9
for i in range(0,8):
for j in range(0,8):
if(count in range(n,end)):
print(‘X’,end=’ ‘)
if(j==0 and i==0):
print(‘O’,end=’ ‘)
elif(count=n+9):
print(’.’,end=’ ')
count+=1
print()
#print()

this was by code but din’t worked? why…!

3 Likes
``````#include <bits/stdc++.h>
using namespace std;

int main() {
int t;
cin >> t;
while(t--){
int k;
cin >> k;
for(int i=0;i<8;i++){
for(int j=0;j<8;j++){
if(i==0 && j==0)cout << 'O';
else cout << (k>0 ? '.' : 'X');
k--;
}cout << '\n';
}
}
}``````
5 Likes

Can someone plz explain why for index i&j=0, we put ‘O’ there??

class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner in = new Scanner(System.in);
while(in.hasNext()){
int t = in.nextInt();
while(t-- > 0){
int k = in.nextInt();

``````	        for(int i = 0; i < 8; i++ ){
for(int j = 0; j < 8; j++){
if( i == 0 && j == 0 ){           //why???????????
System.out.print("O");
k--;
}
else if( k > 0 ){
System.out.print(".");
k--;
}
else  {
System.out.print("X");
}

}
System.out.println();

}``````

ITS YOUR CHOICE MAN!! PLACING AT CORNER JUST GIVES U WAY TO PUT ALL OTHER OBSTACLE IN DEFINED AND CONTROLLED WAY! YOU CAN TRY DIFFERENT CORNER OR EVEN CELL!

1 Like

int main()
{
ios_base::sync_with_stdio( false );
cin.tie(NULL);
cout.tie(NULL);

``````  lli t,n,min_location;
cin>>t;
while(t--)
{
lli row,col;
cin>>n;
char a[9][9];
FOR(i,0,8)
{
FOR(j,0,8)
{
a[i][j]='.';
//cout<<a[i][j];
}
//cout<<"\n";
}
if(n%8==0)
{
row=n/8;
FOR(i,0,8)
{
a[row][i]='X';
}
}
else
{
row=(n/8)+1;
col=(n%8);
if(n/8 == 0)
{
FOR(i,0,col+1)
a[row][i]='X';
a[row-1][col]='X';
}
else
{
FOR(i,0,col+1)
a[row][i]='X';
FOR(i,col,8)
a[row-1][i]='X';
}
}

a[0][0]='O';
FOR(i,0,8)
{
FOR(j,0,8)
{
//a[i][j]='.';
cout<<a[i][j];
}
cout<<"\n";
}cout<<"\n";

}
return 0;
``````

}

Thanks dude! gotcha

1 Like

Don’t know why but my code produces the same result. I used the king trapping technique where i fixed the king in left corner cell and placed X’s as a wall…
Can someone explain me why???
Solution:
https://www.codechef.com/viewsolution/35638964

Output for k=1 is wrong itself. King can move diagonally as well.
`In one move, a king can move to any adjacent cell which shares a side or corner with its current cell and does not contain an obstacle.`

Commenting out a bunch of lines fixes that thing-

``````#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
#define setbits(x)      __builtin_popcountll(x)
#define mod             1000000007
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll              long long
#define inf             1e8
#define pre(y,x)        fixed<<setprecision(y)<<x
#define debug(x)        cerr << "[" << #x << ": " << (x) << "] ";
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}

int main()
{
FIO;
ll t; cin>>t;
while(t--)
{
int k; cin>>k; --k;
char a[65][65];
int n = 8;
int flag=1;
for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++){
if(i==1&&j==1)            a[i][j] = 'O';

else{
// if(a[i-1][j]=='X'&&i>1) flag=0;
// if(i==1)
// {
if(k>0)
a[i][j]='.';
else
a[i][j]='X';

// }
// else if(k>0&&i>1&&(a[i-1][j]=='O'||a[i-1][j]=='.'))       a[i][j]='.';
// else if(k<0&&(a[i-1][j]=='O'||a[i-1][j]=='.')&&flag)      a[i][j]='X';
// else
// a[i][j]='.';
// if(i==1&&k<0){
//     a[i][j]='.';
// }
--k;
}
cout<<a[i][j];
}
cout<<'\n';
}
// cout<<endl;
}
return 0;
}
``````

gotcha!! Forget about that. Implemented wrong idea.

Yes. What is the problem then? The sample answers satisfy all conditions. You can count by hand the no. of positions where king can move.

ok. i forget about the X which was placed at second row ,first cell that’ s why king was able to move. Thanks!

1 Like

Video Solution:

its completely your choice he places at (0, 0) you can place any where

What if we are given condition to minimize the obstacles. Firstly we would go with the ‘.’ in the chessboard and then exchange them with the 'X’s as per the requirement.
But I am not able to apply it properly.
Can someone help?

Mark all cells as “Unassigned”. Then set the required cells where the king can move as “Assigned”. Now, for each of the “Assigned” cells, set all of its “Unassigned” adjacent cells as ‘X’.
Example for K=10:

Edit: This doesn’t work always. For example at K=55, this approach gives 9 as answer, but it can be done in 8.

2 Likes
``````#include <iostream>

using namespace std;

#define M 8
#define N 8

char arr[M][N];

int main(int argc, const char * argv[])
{
int t, k;
cin >> t;
while(t > 0)
{
cin >> k;
int i, j;
for(i=0; i<M; i++)
{
for(j=0; j<N; j++)
{
arr[i][j] = 'X';
}
}
k--;
for(i=0; i<M; i++)
{
for(j=0; j<N; j++)
{
if( 0 == i && 0 == j)
{
arr[i][j] = 'O';
}
else
{
if(k == 0)
break;
else
{
arr[i][j] = '.';
k--;
}
}

}
}

for(i=0; i<M; i++)
{
for(j=0; j<N; j++)
{
cout << arr[i][j];
}
cout << "\n";
}

t--;
}
return 0;
}
``````

Not sure why m getting SIGCONT

Hey everyone, this is my solution in java where you dont have to use 2D array or 2 loops:

``````
import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
int size = 64;
while(t--!=0) {
int a = sc.nextInt();
System.out.print("O");
for(int i=2;i<=a;i++) {
if(i%8==0){
System.out.println(".");
}
else{
System.out.print(".");
}
}
for(int i=a+1;i<=size;i++) {
if(i%8==0){
System.out.println("X");
}
else{
System.out.print("X");
}
}
}
}
}
``````