ESTIMATION AND IMPLIMENTATION

One Dimensional Game of Life

In Conway's Game of Life, cells in a grid are used to simulate biological cells.
Each cell is considered to be either alive or dead.
At each step of the simulation
each cell's current status and number of living neighbors is used to determine the status
of the cell during the following step of the simulation.

In this one-dimensional version, there are N cells numbered 0 through N-1.
The number of cells does not change at any point in the simulation.
Each cell i is adjacent to cells i-1 and i+1.
Here, the indices are taken modulo N meaning cells 0 and N-1 are also adjacent to eachother.
At each step of the simulation, cells with exactly one living neighbor change their status
(alive cells become dead, dead cells become alive).
For example, if we represent dead cells with a '0' and living cells with a '1', consider
the state with 8 cells:

01100101

• Cells 0 and 6 have two living neighbors.
• Cells 1, 2, 3, and 4 have one living neighbor.
• Cells 5 and 7 have no living neighbors.

Thus, at the next step of the simulation, the state would be:

00011101

Given some state of the game, your task is to determine the state immediately preceding it.
In some cases there may be more than one answer or no possible answer.

Input

Input will begin with an integer T<100, the number of test cases.
Each test case consists of a single line, with between 3 and 50 characters, inclusive.
Each character will be either '0' or '1'.
Each '0' represents a dead cell, and each '1' represents an alive cell.

Output

For each test case, output the state of the game that precedes the given state.
If there is no possible solution, print "No solution" (quotes for clarity only).
If there are multiple possible solutions, print "Multiple solutions" (quotes for clarity only).

Sample Input

4
00011101
000
000001
11110

Sample Output

01100101
Multiple solutions
No solution
10010

-------------------------MY EDITORIAL ---------------------------------------------------------------------------------------------

THIS PROBLEN CAN BE SOLVE BY CONSIDERING FIRSTTWO BIT AND COMPUTING REAT ALL 

NOTE TAH THER ARE ONLY 4 POSSIBLE COMBINATIONS OF FIRST TWO BITS  ie. 00, O1,10,11

FOR ALL THESE COMBINATIONS WE COMPUTE ARRAY 

IF ONLY 1 SUCESS FULL ARRAY COMPUTED THAN OK ELSE IF MORE THAN 1 THAN MULTI ANS 

ELSE NO ANS..

FOR  GENERATING ANY SEQUENCE WE USE TWO CURRENT BIT AND 1 BIT OF GIVEN SEQUENCE   (CORESPOINDING BIT FROM GIVEN SEQUENCE )

NOW FOR A VALID SEQUENCE  LAST BIT MUST BE VALID WHICH IS CHECKED BY 1 ST AND 2 ND LAST BIT .. ALSO 1ST BIT MUST BE VALID WHICH IS CHECKED BY LAST BIT AND 2ND BIT ..

*********************************************CHEF EDITORIAL*********************************************

EXPLANATION

First solution: If we choose an arbitrary assignment for any two adjacent cells of the original state, then the entire rest of the state can be determined from the current state. For example, if we choose values for original[0] and original[1], then current[1] is defined as original[0]^original[1]^original[2] (where '^' is exclusive or), thus original[2]=original[0]^original[1]^current[1]. Repeating the process allows us to determine all cells of the original state. Depending on the initial assignment, this may or may not yield a valid solution. There are only 4 initial assignments to try, and we simply count the number that yield valid solutions.

Second solution: Consider the state of the game as theBINARY representation of an N-bit integer. Let A represent the original state of the game, and B the current state. Then the simulation step simply implies that B=F(A), where F(A)=(A<<<1)^A^(A>>>1), '<<<' is left rotation (not left shift), and '>>>' is right rotation. Now consider these cases:


If N is divisible by 3, then F(011011...011011)=000...000, hence the solution cannot be unique (becase F(X^Y)=F(X)^F(Y), there will either be 0 solutions, or 4 solutions). Denote G(B)=(B<<<1)^(B<<<2)=A^(A<<<3). Now G(B)^(G(B)<<<3)^(G(B)<<<6)^...^(G(B)<<<(N-3)) should equal 0. If this is the case, then there are multiple solutions. Otherwise there is no solution.


If N has a remainder of 1 when divided by 3, then F(110110...1101101)=1000...000, hence there is always a unique solution, given by B^(B<<<1)^(B<<<3)^(B<<<4)^(B<<<5)^...^(B<<<(N-3))^(B<<<(N-1)).


If N has a remainder of 2 when divided by 3, then F(101101...10110110)=1000...000, again implying a unique solution, given by B^(B<<<2)^(B<<<3)^(B<<<5)^(B<<<6)^...^(B<<<(N-2))^(B<<<(N-1)).


***********************************************CODE*************************************************************





#include<iostream>


using namespace std;


#include<bits/stdc++.h>


int ans1[1000000],ans2[1000000],ans3[100000],ans4[1000000];// EACH ARRAY CONTAI                                                                                                                                        //N 1  GENERATED SEQ


int main()


{


int t;


cin>>t;


while(t--)


{


int f1=0,f2=0,f3=0,f4=0;


char arr[1000000];


cin>>arr;


int len=strlen(arr);

 	   	 

int count =0;


/* case 0 0*/// IF FIRST 2 BITS ARE 0 0 


int a=0;


int b=0; 


ans1[0]=0;


ans1[1]=0;


for(int i=2;i<len;i++)


{


 	   	    	if(arr[i-1]-'0'==b)// USING CORRESPONDING GIVEN SEQUENCE TO DECIDE                               //NEXT BIT 


{


int temp=b ;    // IF SAME (CHECKED AVOVE) MEANS BOTH SIDE MUST                                                                               //BE SAME BIT SO JUST COPY SAME BIT AS NEXT BIT





b=a;


a=temp;


ans1[i]=b;


}


else 


{


int temp=a;// NOT SAME THAN BOTH SIDE MUST BE NOT SAME BIT


a=b;           // SO GIVE TOGGELED VALUE 


b=1-temp;


ans1[i]=b;


}


}

 	   	    // CHECKING FOR VALID SEQUENCE GENERATED 

if((arr[0]=='0' &&  b==0) ||(arr[0]=='1' && b==1) )// CHECKIG FOR 1ST BIT


{


                     // CHECKING FOR LAST BIT 


if(((arr[len-1]-'0'==b && a==0) || (a==1 && arr[len-1]-'0'!=b)))


{


//	cout<<"test1 sucessfull "<<endl;


					count++; // BOTH 1 ST AND LAST BIT ARE VALID SO INCREAST COUNTER


f1=1;


}

					 

}





// case 0 1


a=0;


b=1; 


ans2[0]=0;


ans2[1]=1;


for(int i=2;i<len;i++)


{


if(arr[i-1]-'0'==b)


{


int temp=b;


b=a;


a=temp;


ans2[i]=b;


}


else 


{


int temp=a;


a=b;


b=1-temp;


ans2[i]=b;


}


}


if((arr[0]=='0' &&  b==1) ||(arr[0]=='1' && b==0))


{


if(((arr[len-1]-'0'==b && a==0) || a==1 && arr[len-1]-'0'!=b))


{


//	cout<<"test2 sucessfull "<<endl;


count++;


f2=1;


}

 	   	    	 

}


/*  for(int i=0;i<len;i++) cout<<ans2[i]<<" ";


 	   	      cout<<endl;*/

 	   	    

// case 1 0 


a=1;


b=0; 


ans3[0]=1;


ans3[1]=0;


for(int i=2;i<len;i++)


{


if(arr[i-1]-'0'==b)


{


int temp=b;


b=a;


a=temp;


ans3[i]=b;


}


else 


{


int temp=a;


a=b;


b=1-temp;


ans3[i]=b;


}


}


if((arr[0]=='0' &&  b==1) ||(arr[0]=='1' && b==0)) 


{


if ((arr[len-1]-'0'==b && a==1) || (a==0 && arr[len-1]-'0'!=b))


{


//cout<<"test3 sucessfull "<<endl;


f3=1;


count++;


}

 	   	    	 

}


/* for(int i=0;i<len;i++) cout<<ans3[i]<<" ";


 	   	      cout<<endl;*/


// case 1 1 


a=1;


b=1; 


ans4[0]=1;


ans4[1]=1;


for(int i=2;i<len;i++)


{


if(arr[i-1]-'0'==b)


{


int temp=b;


b=a;


a=temp;


ans4[i]=b;


}


else 


{


int temp=a;


a=b;


b=1-temp;


ans4[i]=b;


}


}


if((arr[0]=='0' &&  b==0) ||(arr[0]=='1' && b==1)  )


{


if(((arr[len-1]-'0'==b && a==1) || a==0 && arr[len-1]-'0'!=b))


{


count++;


f4=1;


}

 	   	    	

}


/*  for(int i=0;i<len;i++) cout<<ans4[i]<<" ";


 	   	      cout<<endl;*/


if(count ==0 ) cout<<"No solution"<<endl;


else if(count>1) cout<<"Multiple solutions"<<endl;


else


{


        // FIND WHICH SEQUENCE WAS VALID AND PRINT 


if(f1==1)


{


for(int i=0;i<len;i++)cout<<ans1[i];


}


else	if(f2==1)


{


for(int i=0;i<len;i++)cout<<ans2[i];


}


else	if(f3==1)


{


for(int i=0;i<len;i++)cout<<ans3[i];


}


else	if(f4==1)


{


for(int i=0;i<len;i++)cout<<ans4[i];


}


cout<<endl;


}

 	   	      

}


} 

Birthday Candles IMPLIMENTATION

Birthday Candles  Problem code: CANDLE

SUBMIT MY SUBMISSIONS ALL SUBMISSIONS

All submissions for this problem are available.

The chef is preparing a birthday cake for one of his guests,
and his decided to write the age of the guest in candles on the cake.
There are 10 types of candles, one for each of the digits '0' through '9'.
The chef has forgotten the age of the guest, however, so doesn't know whether he has enough candles of the right types.
For example, if the guest were 101 years old, the chef would need two '1' candles and one '0' candle.
Given the candles the chef has, your task is to determine the smallest positive integer that cannot be represented with those candles.

Input:

Input will begin with an integer T≤100, the number of test cases.
Each test case consists of a single line with exactly 10 integers, each between 0 and 8, inclusive.
The first integer of each test case represents the number of '0' candles the chef has,
the second integer represents the number of '1' candles the chef has, and so on.

Output:

For each test case, output on a single line the smallest positive integer that cannot be expressed with the given candles.

Sample input:

3
2 1 1 4 0 6 3 2 2 2
0 1 1 1 1 1 1 1 1 1
2 2 1 2 1 1 3 1 1 1
 

Sample output:

4
10
22
 

-------------------------------------------------editorial-------------------------------------------------------------------------------

CHECK WHETHER 1 TO 10 CAN BE MADE OR NOT IF NOT THAN GIVE ANSWER AS IN CASE OF TEST CASE 1 

ELSE

CHANCE OF 1 ST NUMBER NO TO FORM IS 10 ,THAN 11 , 22 , 33 , 44 , 55, 66 , 77 ...

100 111,222,333,444......

1000 1111,2222,3333.....

10000 11111 ,22222,33333.....

HENCE COUNT NO OF 0 1,..9 WHOSE VALUE IS LESS THAN WILL GIVE THE ANSWER ..

ALSO NOTE THAT NO OF '  0 ' CAN BE 1 LESS THAN ANY OTHER NO ..

******************************************************CODE*****************************************

#include<iostream>


using namespace std;


#include<bits/stdc++.h>


int main()


{


int t;


cin>>t;


while(t--)


{


int arr[11];


for(int i=0;i<10;i++)


{


cin>>arr[i];


}


int ans=0;


int cc=1;


int i=0;


int f=0;


while(1)


{


if(i==0 )


{

 	         	 

if(arr[i]<cc-1)


{


f=1;


cout<<"1";


for(int j=1;j<cc;j++) cout<<"0";


}

 	         	 
 	         	
 	         	 	

}


else


{


if(arr[i]<cc)


{


f=1;


for(int j=0;j<cc;j++) cout<<i;


}


}


i++;


i%=10;


if(f==1) break;


if(i==0)


{


cc++;

 	         	  	

}


//   cout<<"i "<<i<<"  cc "<<cc<<endl;


}


cout<<endl;


}


}