Blade Master CodeChef Solution

Problem -Blade Master CodeChef Solution

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
<<Previous CodeChef Problem Next Codechef Problem>>

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; 
 
void read() {
	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() {
 
	read();
	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
#define HASHMASK ((1<<HASHSIZE) - 1)


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 {
   unsigned long long bitmask;
   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 movemask[6][64];
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) {
   return ((mask >> (34 - HASHSIZE)) ^ mask) & HASHMASK;
}
*/
#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].bitmask = curpos;
      hashtab[key].steps = steps;
      hashtab[key].sum = sum;
   }
}

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

void hash_replace(long long steps, long long sum) {
   int key = hash_key(curpos);
   hashtab[key].bitmask = 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];
               }
            }
            movemask[X][y*M+x] = a;
         }
      }
   }   
}

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

void update() {
   U64 narray = curpos, delta = 0ULL;
   
   while (narray) {
      int pos = pop_lsb(&narray);
      U64 mask = curpos & cross[pos];
      int p = popcount(mask) % 6;
      delta ^= movemask[p][pos];
   }
   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.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.StringTokenizer;

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

	String nextToken() throws Exception {
		while (st == null || !st.hasMoreTokens()) {
			st = new StringTokenizer(in.readLine());
		}
		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;
	long[][][] mask;
	
	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); 
						}
					}
				}
			}
		}
		
		mask = new long[n][m][6];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				for(int k=0;k<6;k++) {
					mask[i][j][k] |= move(i,j,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 {
			in = new BufferedReader(new InputStreamReader(new BufferedInputStream(System.in)));
			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
{
    public class MyReader
    {
        private TextReader instream;

        public int[] ReadIntArray()
        {
            string inp = instream.ReadLine().Trim();
            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;
        }

        public int ReadInt()
        {
            return int.Parse(instream.ReadLine());
        }

        public long ReadLong()
        {
            return long.Parse(instream.ReadLine());
        }

        public void SetInStream(TextReader textReader)
        {
            this.instream = textReader;
        }

        internal string ReadLine()
        {
            return instream.ReadLine();
        }
    }

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

        TextWriter outstream = Console.Out;

        solve(instream, outstream);

    }

    static int n;
    static int m;
    static long[,] mask;

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

        int[] nmq = instream.ReadIntArray();
        n = nmq[0];
        m = nmq[1];
        int q = nmq[2];

        int[] s = instream.ReadIntArray();

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

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

        mask = new long[34, 6];

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

                    mask[shift, rem] = msk;
                }
            }
        }

        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>();

        states.Add(curstate, step++);
        long cursum =  count1(curstate);
        all_steps.Add(0, cursum);

        sums.Add(0, cursum);

        long nextstate;

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

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

            all_steps.Add(step, cnt);
            sums.Add(step, cursum);

            states.Add(nextstate, step++);
            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;

                    nxState ^= mask[shift, cnt];
                }
            }
        }

        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!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn

Leave a Reply

Your email address will not be published. Required fields are marked *