304 North Cardinal St.
Dorchester Center, MA 02124

## Blade Master CodeChef Solution in C++14

``````#include <cstdio>

typedef long long LL;

int N,M,Q;
int Sx,Sy;
int p[6][2];
int NM;

scanf("%d %d %d %d %d", &N, &M, &Q, &Sx, &Sy);
--Sx; --Sy;
for (int k = 0; k < 6; ++k)	{
scanf("%d %d", &p[k][0], &p[k][1]);
}
NM = N * M;
}

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int dir[6][2] = {
{0, 1},
{2, 3},
{0, 3},
{3, 1},
{1, 2},
{2, 0}
};

const int maxNM = 34;

LL move[maxNM][6];
const int H = maxNM / 2;
const int HALF = (1 << H) - 1;
int bitcnt[1 << H];
LL cross[maxNM];
int r6[maxNM];

void precalc()
{

for (int i = 0; i < M + N; ++i) {
r6[i] = i % 6;
}

for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
for (int k = 0; k < 6; ++k) {

LL grid = 1LL << (M * i + j);

for (int h = 0; h < 2; ++h) {
int x = i, y = j;
while (true) {
x += dx[dir[k][h]] * p[k][h];
y += dy[dir[k][h]] * p[k][h];
if (!(0 <= x && x < N && 0 <= y && y < M)) {
break;
}
grid |= 1LL << (M * x + y);
}
}
move[M * i + j][k] = grid;
}
}
}

bitcnt[0] = 0;
for (int i = 1; i < (1 << H); ++i) {
bitcnt[i] = bitcnt[i / 2] + i % 2;
}

for (int i = 0; i < N; ++i) {
for (int j = 0; j < M; ++j) {
int u = M * i + j;
cross[u] = 0;

for (int k = 0; k < N; ++k) {
cross[u] |= 1LL << (M * k + j);
}

for (int k = 0; k < M; ++k) {
cross[u] |= 1LL << (M * i + k);
}
}
}
}

int BITCNT(LL grid) {
return bitcnt[grid & HALF] + bitcnt[grid >> H & HALF];
}

const int PER = 350000;
const int SIZE = 700001;
LL grid;
int len;
LL grids[PER];
int ind[SIZE];
int sum[PER];

void init() {

for (int i = 0; i < SIZE; ++i) {
ind[i] = -1;
}

grid = 1LL << (M * Sx + Sy);

ind[grid % SIZE] = 0;
grids[0] = grid;
sum[0] = 1;
len = 1;
}

int main() {

precalc();
init();

int q = 0, p = 0;
while (p == 0) {

LL new_grid=0;
for (int u = 0; u < NM; ++u) {

if (grid & 1LL << u) {

new_grid ^= move[u][BITCNT(grid & cross[u])%6];
}
}
grid = new_grid;

grids[len] = grid;
sum[len] = sum[len - 1] + BITCNT(grid);

int pos = grid % SIZE;
for(;;)
{

if (ind[pos] < 0) {
ind[pos] = len;
++len;
break;
} else {

if (grids[ind[pos]] == grid) {
q = ind[pos];
p = len;
break;
} else {

++pos;

if (pos == SIZE) {
pos = 0;
}
}
}
}
}

int w = p - q;
LL period_sum = sum[p] - sum[q];
for (int i = 0; i < Q; ++i) {
LL T;
scanf("%lld", &T);

LL ans;
if (T <= p) {
ans=sum[T];
} else {
LL L = (T - q) / w;
int r = T - L * w;
ans = sum[r] + L * period_sum;
}
printf("%lld\n", ans);
}
return 0;
} ``````

## Blade Master CodeChef Solution in C

``````
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <unistd.h>

#ifndef NULL
#define NULL ((void *)0)
#endif

#define BIT(x) (1ULL << (x))

#define HASHSIZE 20

typedef unsigned long long U64;

const U64 bit64[64] = {
BIT(0),  BIT(1),  BIT(2),  BIT(3),  BIT(4),  BIT(5),  BIT(6),  BIT(7),  BIT(8),  BIT(9),
BIT(10), BIT(11), BIT(12), BIT(13), BIT(14), BIT(15), BIT(16), BIT(17), BIT(18), BIT(19),
BIT(20), BIT(21), BIT(22), BIT(23), BIT(24), BIT(25), BIT(26), BIT(27), BIT(28), BIT(29),
BIT(30), BIT(31), BIT(32), BIT(33), BIT(34), BIT(35), BIT(36), BIT(37), BIT(38), BIT(39),
BIT(40), BIT(41), BIT(42), BIT(43), BIT(44), BIT(45), BIT(46), BIT(47), BIT(48), BIT(49),
BIT(50), BIT(51), BIT(52), BIT(53), BIT(54), BIT(55), BIT(56), BIT(57), BIT(58), BIT(59),
BIT(60), BIT(61), BIT(62), BIT(63) };

/*
typedef struct {
long long steps;
long long sum;
} PosHash;

PosHash hashtab[1 << HASHSIZE];
*/
int N, M;
long long T[100] = { 0 };
int Q;
long long nodes = 0LL;

long long cycle_start_t, cycle_length_t, cycle_start_sum, cycle_length_sum;
U64 cycle_start_pos;
long long *cycle_modsum;

int xd[2][6] = { {  0, -1,  0,  1,  0, -1 },  {  0,  1,  1,  0, -1,  0 } };
int yd[2][6] = { { -1,  0, -1,  0,  1,  0 },  {  1,  0,  0,  1,  0, -1 } };
int p[2][6];

U64 cross[64];
U64 curpos;

/* -------------------------------------------------------------------------- */

const int nof_bits[256] = {
0,
1,
1,2,
1,2,2,3,
1,2,2,3,2,3,3,4,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8};

inline int popcount(U64 b) {
unsigned char *a = (unsigned char *)&b;
int ret = nof_bits[*a++];
ret += nof_bits[*a++];
ret += nof_bits[*a++];
ret += nof_bits[*a++];
/*
ret += nof_bits[*a++];
ret += nof_bits[*a++];
ret += nof_bits[*a++];
*/
return ret + nof_bits[*a];
}

/*
inline int popcount(U64 b) {
unsigned buf, acc;

if (b == 0) return 0;

buf = (unsigned)b;
acc = buf;
acc -= ((buf &= 0xEEEEEEEE) >> 1);
acc -= ((buf &= 0xCCCCCCCC) >> 2);
acc -= ((buf &= 0x88888888) >> 3);
buf = (unsigned)(b >> 32);
acc += buf;
acc -= ((buf &= 0xEEEEEEEE) >> 1);
acc -= ((buf &= 0xCCCCCCCC) >> 2);
acc -= ((buf &= 0x88888888) >> 3);
acc = (acc & 0x0F0F0F0F) + ((acc >> 4) & 0x0F0F0F0F);
acc = (acc & 0xFFFF) + (acc >> 16);

return (acc & 0xFF) + (acc >> 8);
}
*/
/* -------------------------------------------------------------------------- */

inline int pop_lsb(U64 *b) {
unsigned register int ret;
__asm volatile("   movl        %0, %%esi"          ::  "memory" (b) : "%esi");
__asm volatile("   bsfl        (%%esi), %%edx"     ::: "%edx");
__asm volatile("   movl   %%edx, %%eax"       ::: "%eax");
__asm volatile("   jnz    1f");
__asm volatile("   addl        \$4, %%esi"          ::: "%esi");
__asm volatile("   bsfl        (%%esi), %%edx"     ::: "%edx");
__asm volatile("   lea    32(%%edx,1), %%eax" ::: "%eax");
__asm volatile("1: btr    %%edx, (%%esi)"     ::: "memory");
__asm volatile("  .att_syntax"                : "=a" (ret));
return ret;
}

/* -------------------------------------------------------------------------- */

U64 u64_set(U64 v, int x, int y) {
return v | bit64[y*M+x];
}

/* -------------------------------------------------------------------------- */

void u64_display(U64 val) {
int x, y;
for (y=0; y<N; y++) {
for (x=0; x<M; x++) {
printf("%i", val & bit64[y*M+x]?1:0);
}
printf("\n");
}
printf("count = %i\n", popcount(val));
}

/* -------------------------------------------------------------------------- */

/*
inline int hash_key(const U64 mask) {
}
*/
#if 0
inline int hash_key(U64 key) {
key = (~key) + (key << 18);
key = key ^ (key >> 31);
key = key * 21;
key = key ^ (key >> 11);
key = key + (key << 6);
key = key ^ (key >> 22);
return (unsigned int) key % (unsigned)1004987;
}

/* -------------------------------------------------------------------------- */

void hash_insert(long long steps, long long sum) {
int key = hash_key(curpos);
if (hashtab[key].sum == 0LL) {
hashtab[key].steps = steps;
hashtab[key].sum = sum;
}
}

/* -------------------------------------------------------------------------- */

void hash_replace(long long steps, long long sum) {
int key = hash_key(curpos);
hashtab[key].steps = steps;
hashtab[key].sum = sum;
}

/* -------------------------------------------------------------------------- */

long long hash_get_time() {
int key = hash_key(curpos);
if (hashtab[key].bitmask == curpos && hashtab[key].sum > 0) return hashtab[key].steps;
else
return -1LL;
}

/* -------------------------------------------------------------------------- */

long long hash_get_sum() {
int key = hash_key(curpos);
if (hashtab[key].bitmask == curpos && hashtab[key].sum > 0) return hashtab[key].sum;
else
return -1LL;
}
#endif

/* -------------------------------------------------------------------------- */

void calc_consts() {
int x, y;
int i, j, X;
unsigned int cx, cy;
U64 a = 0ULL;

for (j=0; j<N; j++) {
for (i=0; i<M; i++) {
a = 0ULL;
for (x=0; x<M; x++) a = u64_set(a, x, j);
for (y=0; y<N; y++) a = u64_set(a, i, y);
cross[j*M+i] = a;
}
}

for (X=0; X<6; X++) {
for (y=0; y<N; y++) {
for (x=0; x<M; x++) {
a = 0ULL;
for (i=0; i<2; i++) {
cx = x + xd[i][X];
cy = y + yd[i][X];
while (cx < M && cy < N) {
a = u64_set(a, cx, cy);
cx += xd[i][X];
cy += yd[i][X];
}
}
}
}
}
}

/* -------------------------------------------------------------------------- */

void update() {
U64 narray = curpos, delta = 0ULL;

while (narray) {
int pos = pop_lsb(&narray);
U64 mask = curpos & cross[pos];
int p = popcount(mask) % 6;
}
curpos ^= delta;
nodes++;
}

/* -------------------------------------------------------------------------- */

U64 lastpos[1<<22];
U64 lastsum[1<<22];
U64 largest_precalc = 0;

void calc_cycle(int sx, int sy) {
U64 t = 0ULL, sum, nu;
int i, j;

nu = 1024;
curpos = u64_set(0ULL, sx, sy);
sum = popcount(curpos);
do {
lastpos[t] = curpos;
lastsum[t] = sum;
update();
sum += popcount(curpos);
t++;
if (t == nu) {
for (j=0; j<t; j++) {
if (lastpos[j] == curpos) goto out;
}
nu *= 3;
nu >>= 1;
}
} while(1);
out:
largest_precalc = t;
cycle_start_t = t;
cycle_length_t = cycle_start_t - j;
cycle_start_sum = sum;
cycle_length_sum = sum - lastsum[j];
cycle_start_pos = curpos;
/*
printf("Earliest cycle: start = %lli length = %lli delta sum = %lli\n",cycle_start_t, cycle_length_t, sum - cycle_length_sum);
exit(0);
*/
cycle_modsum = (long long *)malloc(cycle_length_t*sizeof(long long));
if (cycle_modsum != NULL) {
cycle_modsum[0] = 0LL;
for (i=1; i<cycle_length_t; i++) {
cycle_modsum[i] = cycle_modsum[i-1] + lastsum[j+i] - lastsum[j+i-1];
}
}
}

/* -------------------------------------------------------------------------- */

double current_time(void) {
struct timeval tv;
gettimeofday(&tv, NULL);
return (double)tv.tv_usec / 1000000.0 + (double)tv.tv_sec;
}

/* -------------------------------------------------------------------------- */

void bmaster(void) {
int sx, sy, Q, i;
long long t = 0LL, rt;
long long sum = 1, q;
double start_time;

scanf("%i %i %i", &N, &M, &Q);
scanf("%i %i", &sy, &sx);
sx--; sy--;

for (i=0; i<6; i++) {
scanf("%i %i", &p[0][i], &p[1][i]);
xd[0][i] *= p[0][i];
yd[0][i] *= p[0][i];
xd[1][i] *= p[1][i];
yd[1][i] *= p[1][i];
}

for (q=0; q<Q; q++) scanf("%lli", &T[q]);

calc_consts();
//   memset(hashtab, 0, sizeof(hashtab));

start_time = current_time();
calc_cycle(sx, sy);
//   printf("Processed: %.2lfkn/s\n", (nodes / (current_time() - start_time)) * 0.001);

for (q=0; q<Q; q++) {
curpos = u64_set(0ULL, sx, sy);
sum = popcount(curpos);
t = 0LL;

if (T[q] > cycle_start_t) {
long long periods, rem = 0LL;
t = cycle_start_t;
sum = cycle_start_sum;
curpos = cycle_start_pos;

periods = (T[q] - t) / cycle_length_t;
rem = (T[q] - t) % cycle_length_t;
sum += cycle_length_sum * periods;
t += cycle_length_t * periods;
if (cycle_modsum != NULL) {
sum += cycle_modsum[rem];
t+= rem;
}
}

if (t < largest_precalc) {
U64 target = largest_precalc < T [q] ? largest_precalc : T[q];
t = target;
sum = lastsum[target];
}

for (; t < T[q]; t++) {
update();
sum += popcount(curpos);
}
printf("%lli\n", sum);
}
}

/* -------------------------------------------------------------------------- */

int main(int argc, char **argv) {
bmaster();
return 0;
}
``````

## Blade Master CodeChef Solution in JAVA

``````import java.io.BufferedInputStream;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main implements Runnable {
PrintWriter out;
StringTokenizer st;

String nextToken() throws Exception {
while (st == null || !st.hasMoreTokens()) {
}
return st.nextToken();
}

int nextInt() throws Exception {
return Integer.parseInt(nextToken());
}

long nextLong() throws Exception {
return Long.parseLong(nextToken());
}

int n;
int m;
int q;
int[][] p;
long[] t;
long[] cross;

int[] dx = { -1, 0, 1, 0 };
int[] dy = { 0, 1, 0, -1 };
int[] d1 = { 0, 3, 0, 1, 2, 3 };
int[] d2 = { 2, 1, 1, 2, 3, 0 };

long move(int i, int j, int k) {
long nn = 0;
for(int x= i + dx[d1[k]] * p[k][0], y=j + dy[d1[k]]*p[k][0]; x>=0 && x<n && y<m && y >=0; x=x + dx[d1[k]] * p[k][0], y=y + dy[d1[k]]*p[k][0]) {
nn |= 1l << (x*m + y);
}
for(int x= i + dx[d2[k]] * p[k][1], y=j + dy[d2[k]] * p[k][1]; x>=0 && x<n && y<m && y >=0; x=x + dx[d2[k]] * p[k][1], y=y + dy[d2[k]] * p[k][1]) {
nn |= 1l << (x*m + y);
}
return nn;
}

long nextMove(long nn) {
long b = nn;
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if ((nn & (1l << i*m + j)) != 0) {
b ^= mask[i][j][(int) (Long.bitCount((nn & cross[i*m + j])) % 6)];
}
}
}
return b;
}

void solve() throws Exception {
n = nextInt();
m = nextInt();
q = nextInt();

int sx = nextInt() - 1;
int sy = nextInt() - 1;

p = new int[6][2];
for(int i=0;i<6;i++) {
p[i][0] = nextInt();
p[i][1] = nextInt();
}

cross = new long[n*m];
for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
for(int ii=0;ii<n;ii++) {
for(int jj=0;jj<m;jj++) {
if (ii == i || jj ==j) {
cross[i*m + j] |= (1l << ii * m + jj);
}
}
}
}
}

for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
for(int k=0;k<6;k++) {
}
}
}

long[] cm = new long[1000000];
HashMap<Long, Integer> moves = new HashMap<Long, Integer>(300000);

long g = 1l << (sx*m + sy);
int i = 0;
cm[i++] = 0;
for (; !moves.containsKey(g); i++) {
moves.put(g, i);
cm[i] = cm[i - 1] + Long.bitCount(g);
g = nextMove(g);
}

int pp = moves.get(g);
int cc = i - pp;
for (i = 0; i < q; i++) {
long t = nextLong() + 1;
if (t < pp + cc)
out.println(cm[(int) t]);
else {
long ans = cm[pp - 1];
ans += (cm[pp + cc - 1] - cm[pp - 1]) * ((t - pp + 1) / cc);
ans += cm[pp + (int) ((t - pp + 1) % cc) - 1] - cm[pp - 1];
out.println(ans);
}
}
}

public void run() {
try {
out = new PrintWriter(System.out);
solve();
} catch (Exception e) {
e.printStackTrace();
System.exit(1);
} finally {
out.close();
}
}

public static void printGrid(long nn, int n, int m) {

for(int i=0;i<n;i++) {
for(int j=0;j<m;j++) {
if ((nn & (1l<<(i*m + j))) != 0) {
System.out.print("1 ");
} else {
System.out.print("0 ");
}
}
System.out.println("");
}
}

public static void main(String[] args) {
new Main().run();
}

}``````

## Blade Master CodeChef Solution in C#

``````using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

public class BMASTER
{
{

{
string[] spl = inp.Split(' ');

int[] a = new int[spl.Length];
for (int i = 0; i < a.Length; i++)
a[i] = int.Parse(spl[i]);
return a;
}

{
}

{
}

{
}

{
}
}

static void Main(string[] args)
{
instream.SetInStream(Console.In);

TextWriter outstream = Console.Out;

solve(instream, outstream);

}

static int n;
static int m;

private static void solve(MyReader instream, TextWriter outstream)
{

n = nmq[0];
m = nmq[1];
int q = nmq[2];

int[][] p = new int[6][];
for (int i = 0; i < 6; i++)

long[] t = new long[q];
for (int i = 0; i < q; i++)
{
}

for (int r = 0; r < n; r++)
{
for (int c = 0; c < m; c++)
{
int shift = r * m + c;
for (int rem = 0; rem < 6; rem++)
{

int rr = r;
int cc = c;

long msk = 0;

while (rr >= 0 && rr < n && cc >= 0 && cc < m)
{
if (rr != r || cc != c)
{
msk |= ((long)1) << (rr * m + cc);
}

switch (rem)
{
case 0: rr -= p[0][0]; break;
case 1: cc -= p[1][0]; break;
case 2: rr -= p[2][0]; break;
case 3: cc += p[3][0]; break;
case 4: rr += p[4][0]; break;
case 5: cc -= p[5][0]; break;
}
}

rr = r;
cc = c;

while (rr >= 0 && rr < n && cc >= 0 && cc < m)
{
if (rr != r || cc != c)
{
msk |= ((long)1) << (rr * m + cc);
}

switch (rem)
{
case 0: rr += p[0][1]; break;
case 1: cc += p[1][1]; break;
case 2: cc += p[2][1]; break;
case 3: rr += p[3][1]; break;
case 4: cc -= p[4][1]; break;
case 5: rr -= p[5][1]; break;
}
}

}
}
}

long curstate = (long)1 << (s[0] - 1) * m + (s[1] - 1);

int step = 0;

Dictionary<long, int> states = new Dictionary<long, int>();
Dictionary<int, long> all_steps = new Dictionary<int, long>();

Dictionary<int, long> sums = new Dictionary<int, long>();

long cursum =  count1(curstate);

long nextstate;

nextstate = nextState(curstate);
while (!states.ContainsKey(nextstate))
{
curstate = nextstate;

int cnt = count1(curstate);
cursum += cnt;

nextstate = nextState(curstate);
}

int cyclestart = states[nextstate];
int cyclelength = step - cyclestart;

for (int i = 0; i < t.Length; i++)
{
if (t[i] < all_steps.Count)
{
Console.WriteLine(sums[(int)t[i]]);
}
else
{
long T = t[i] - cyclestart;

long BeforeCycle = 0;
if (cyclestart > 0) BeforeCycle = sums[cyclestart - 1];

long CyclesCnt = T / cyclelength;
long CycleFree = T % cyclelength;
long CycleSum = sums[step - 1] - BeforeCycle;

long res = BeforeCycle + CycleSum * CyclesCnt;
res += sums[(int)CycleFree + cyclestart] - BeforeCycle;

Console.WriteLine(res);
}
}
}

private static void printState(long curstate)
{
for (int r = 0; r < n; r++)
{
for (int c = 0; c < m; c++)
{
int shift = r * m + c;

if (0 != (curstate & ((long)1) << shift))
Console.Write('1');
else
Console.Write('0');
}
Console.WriteLine();
}
Console.WriteLine();
}

private static int count1(long curstate)
{
int cnt = 0;
while (curstate > 0)
{
if ((curstate & 1) != 0) cnt++;
curstate >>= 1;
}
return cnt;
}

private static long nextState(long curstate)
{
int[] CountInRows = new int[n];
int[] CountInCols = new int[m];

for (int r = 0; r < n; r++)
{
for (int c = 0; c < m; c++)
{
int shift = r * m + c;
long msk = ((long)1) << shift;

if ((curstate & msk) != 0)
{
CountInRows[r]++;
CountInCols[c]++;
}
}
}

long nxState = curstate;

for (int r = 0; r < n; r++)
{
for (int c = 0; c < m; c++)
{
int shift = r * m + c;
long msk = ((long)1) << shift;

if ((curstate & msk) != 0)
{
int cnt = (CountInRows[r] + CountInCols[c] - 1) % 6;

}
}
}

return nxState;
}

}``````
##### Blade Master CodeChef Solution Review:

In our experience, we suggest you solve this Blade Master CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Blade Master CodeChef Solution.

Find on CodeChef

##### Conclusion:

I hope this Blade Master CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!