Aktivne in neaktivne celice po k dneh
Podano je binarno polje velikosti n, kjer je n > 3 . True (ali 1) vrednost v matriki pomeni aktivno in false (ali 0) pomeni neaktivno. Za podano število k je naloga najti število aktivnih in neaktivnih celic po k dneh. Po vsakem dnevu status i-te celice postane aktiven, če leva in desna celica nista enaki, in neaktiven, če sta leva in desna celica enaki (obe 0 ali obe 1).
Ker pred skrajno levimi in za skrajno desnimi celicami ni celic, se celice z vrednostmi pred skrajno levimi in za skrajno desnimi celicami vedno obravnavajo kot 0 (ali neaktivne).
Primeri:
Input : cells[] = {1 0 1 1} k = 2 Output : Active cells = 3 Inactive cells = 1 After 1 day cells[] = {0 0 1 1} After 2 days cells[] = {0 1 1 1} Input : cells[] = {0 1 0 1 0 1 0 1} k = 3 Output: Active Cells = 2 Inactive Cells = 6 Explanation : After 1 day cells[] = {1 0 0 0 0 0 0 0} After 2 days cells[] = {0 1 0 0 0 0 0 0} After 3 days cells[] = {1 0 1 0 0 0 0 0} Input : cells[] = {0 1 1 1 0 1 1 0} k = 4 Output: Active Cells = 3 Inactive Cells = 5 Edina pomembna stvar je zagotoviti, da ohranimo kopijo dane matrike, ker potrebujemo prejšnje vrednosti za posodobitev za naslednji dan. Spodaj so podrobni koraki.
- Najprej kopiramo matriko celic[] v matriko temp[] in naredimo spremembe v matriki temp[] glede na dane pogoje.
- V pogoju je podano, da če sta leva in desna celica i-te celice neaktivni ali aktivni, postane naslednji dan i neaktiven, tj. (celice[i-1] == 0 in celice[i+1] == 0) ali (celice[i-1] == 1 in celice[i+1] == 1), potem celice[i] = 0 te pogoje je mogoče uporabiti z uporabo XOR za celice[i-1] in celice[i+1].
- Za 0'to indeksno celico temp[0] = 0^celice[1] in za (n-1)'to indeksno celico temp[n-1] = 0^celice[n-2].
- Zdaj za indekse od 1 do n-2 naredite naslednjo operacijo temp[i] = celice[i-1] ^ celice[i+1]
- Postopek ponavljajte, dokler ne preteče k dni.
Sledi izvedba zgornjih korakov.
C++ // C++ program to count active and inactive cells after k // days #include using namespace std ; // cells[] - store current status of cells // n - Number of cells // temp[] - to perform intermediate operations // k - number of days // active - count of active cells after k days // inactive - count of active cells after k days void activeAndInactive ( bool cells [] int n int k ) { // copy cells[] array into temp [] array bool temp [ n ]; for ( int i = 0 ; i < n ; i ++ ) temp [ i ] = cells [ i ]; // Iterate for k days while ( k -- ) { // Finding next values for corner cells temp [ 0 ] = 0 ^ cells [ 1 ]; temp [ n -1 ] = 0 ^ cells [ n -2 ]; // Compute values of intermediate cells // If both cells active or inactive then temp[i]=0 // else temp[i] = 1. for ( int i = 1 ; i <= n -2 ; i ++ ) temp [ i ] = cells [ i -1 ] ^ cells [ i + 1 ]; // Copy temp[] to cells[] for next iteration for ( int i = 0 ; i < n ; i ++ ) cells [ i ] = temp [ i ]; } // count active and inactive cells int active = 0 inactive = 0 ; for ( int i = 0 ; i < n ; i ++ ) ( cells [ i ] == 1 ) ? active ++ : inactive ++ ; printf ( 'Active Cells = %d Inactive Cells = %d' active inactive ); } // Driver program to check the test case int main () { bool cells [] = { 0 1 0 1 0 1 0 1 }; int k = 3 ; int n = sizeof ( cells ) / sizeof ( cells [ 0 ]); activeAndInactive ( cells n k ); return 0 ; }
Java // Java program to count active and // inactive cells after k days class GFG { // cells[] - store current status // of cells n - Number of cells // temp[] - to perform intermediate operations // k - number of days // active - count of active cells after k days // inactive - count of active cells after k days static void activeAndInactive ( boolean cells [] int n int k ) { // copy cells[] array into temp [] array boolean temp [] = new boolean [ n ] ; for ( int i = 0 ; i < n ; i ++ ) temp [ i ] = cells [ i ] ; // Iterate for k days while ( k -- > 0 ) { // Finding next values for corner cells temp [ 0 ] = false ^ cells [ 1 ] ; temp [ n - 1 ] = false ^ cells [ n - 2 ] ; // Compute values of intermediate cells // If both cells active or inactive then // temp[i]=0 else temp[i] = 1. for ( int i = 1 ; i <= n - 2 ; i ++ ) temp [ i ] = cells [ i - 1 ] ^ cells [ i + 1 ] ; // Copy temp[] to cells[] for next iteration for ( int i = 0 ; i < n ; i ++ ) cells [ i ] = temp [ i ] ; } // count active and inactive cells int active = 0 inactive = 0 ; for ( int i = 0 ; i < n ; i ++ ) if ( cells [ i ] == true ) active ++ ; else inactive ++ ; System . out . print ( 'Active Cells = ' + active + ' ' + 'Inactive Cells = ' + inactive ); } // Driver code public static void main ( String [] args ) { boolean cells [] = { false true false true false true false true }; int k = 3 ; int n = cells . length ; activeAndInactive ( cells n k ); } } // This code is contributed by Anant Agarwal.
Python3 # Python program to count # active and inactive cells after k # days # cells[] - store current # status of cells # n - Number of cells # temp[] - to perform # intermediate operations # k - number of days # active - count of active # cells after k days # inactive - count of active # cells after k days def activeAndInactive ( cells n k ): # copy cells[] array into temp [] array temp = [] for i in range ( n + 1 ): temp . append ( False ) for i in range ( n ): temp [ i ] = cells [ i ] # Iterate for k days while ( k > 0 ): # Finding next values for corner cells temp [ 0 ] = False ^ cells [ 1 ] temp [ n - 1 ] = False ^ cells [ n - 2 ] # Compute values of intermediate cells # If both cells active or # inactive then temp[i]=0 # else temp[i] = 1. for i in range ( 1 n - 2 + 1 ): temp [ i ] = cells [ i - 1 ] ^ cells [ i + 1 ] # Copy temp[] to cells[] # for next iteration for i in range ( n ): cells [ i ] = temp [ i ] k -= 1 # count active and inactive cells active = 0 inactive = 0 ; for i in range ( n ): if ( cells [ i ] == True ): active += 1 else : inactive += 1 print ( 'Active Cells =' active ' ' 'Inactive Cells =' inactive ) # Driver code cells = [ False True False True False True False True ] k = 3 n = len ( cells ) activeAndInactive ( cells n k ) # This code is contributed # by Anant Agarwal.
C# // C# program to count active and // inactive cells after k days using System ; class GFG { // cells[] - store current status // of cells n - Number of cells // temp[] - to perform intermediate // operations k - number of days // active - count of active cells // after k days inactive - count // of active cells after k days static void activeAndInactive ( bool [] cells int n int k ) { // copy cells[] array into // temp [] array bool [] temp = new bool [ n ]; for ( int i = 0 ; i < n ; i ++ ) temp [ i ] = cells [ i ]; // Iterate for k days while ( k -- > 0 ) { // Finding next values // for corner cells temp [ 0 ] = false ^ cells [ 1 ]; temp [ n - 1 ] = false ^ cells [ n - 2 ]; // Compute values of intermediate cells // If both cells active or inactive then // temp[i]=0 else temp[i] = 1. for ( int i = 1 ; i <= n - 2 ; i ++ ) temp [ i ] = cells [ i - 1 ] ^ cells [ i + 1 ]; // Copy temp[] to cells[] // for next iteration for ( int i = 0 ; i < n ; i ++ ) cells [ i ] = temp [ i ]; } // count active and inactive cells int active = 0 inactive = 0 ; for ( int i = 0 ; i < n ; i ++ ) if ( cells [ i ] == true ) active ++ ; else inactive ++ ; Console . Write ( 'Active Cells = ' + active + ' ' + 'Inactive Cells = ' + inactive ); } // Driver code public static void Main () { bool [] cells = { false true false true false true false true }; int k = 3 ; int n = cells . Length ; activeAndInactive ( cells n k ); } } // This code is contributed by Nitin Mittal.
PHP // PHP program to count active // and inactive cells after k // days // cells[] - store current status // of cells n - Number of cells // temp[] - to perform intermediate // operations k - number of days // active - count of active cells // after k days inactive - count of // active cells after k days function activeAndInactive ( $cells $n $k ) { // copy cells[] array into // temp [] array $temp = array (); for ( $i = 0 ; $i < $n ; $i ++ ) $temp [ $i ] = $cells [ $i ]; // Iterate for k days while ( $k -- ) { // Finding next values // for corner cells $temp [ 0 ] = 0 ^ $cells [ 1 ]; $temp [ $n - 1 ] = 0 ^ $cells [ $n - 2 ]; // Compute values of // intermediate cells // If both cells active // or inactive then temp[i]=0 // else temp[i] = 1. for ( $i = 1 ; $i <= $n - 2 ; $i ++ ) $temp [ $i ] = $cells [ $i - 1 ] ^ $cells [ $i + 1 ]; // Copy temp[] to cells[] // for next iteration for ( $i = 0 ; $i < $n ; $i ++ ) $cells [ $i ] = $temp [ $i ]; } // count active and // inactive cells $active = 0 ; $inactive = 0 ; for ( $i = 0 ; $i < $n ; $i ++ ) ( $cells [ $i ] == 1 ) ? $active ++ : $inactive ++ ; echo 'Active Cells = ' $active ' Inactive Cells = ' $inactive ; } // Driver Code $cells = array ( 0 1 0 1 0 1 0 1 ); $k = 3 ; $n = count ( $cells ); activeAndInactive ( $cells $n $k ); // This code is contributed by anuj_67. ?>
JavaScript < script > // javascript program to count active and // inactive cells after k days // cells - store current status // of cells n - Number of cells // temp - to perform intermediate operations // k - number of days // active - count of active cells after k days // inactive - count of active cells after k days function activeAndInactive ( cells n k ) { // copy cells array into temp array var temp = Array ( n ). fill ( false ); for ( i = 0 ; i < n ; i ++ ) temp [ i ] = cells [ i ]; // Iterate for k days while ( k -- > 0 ) { // Finding next values for corner cells temp [ 0 ] = false ^ cells [ 1 ]; temp [ n - 1 ] = false ^ cells [ n - 2 ]; // Compute values of intermediate cells // If both cells active or inactive then // temp[i]=0 else temp[i] = 1. for ( i = 1 ; i <= n - 2 ; i ++ ) temp [ i ] = cells [ i - 1 ] ^ cells [ i + 1 ]; // Copy temp to cells for next iteration for ( i = 0 ; i < n ; i ++ ) cells [ i ] = temp [ i ]; } // count active and inactive cells var active = 0 inactive = 0 ; for ( i = 0 ; i < n ; i ++ ) if ( cells [ i ] == true ) active ++ ; else inactive ++ ; document . write ( 'Active Cells = ' + active + ' ' + 'Inactive Cells = ' + inactive ); } // Driver code var cells = [ false true false true false true false true ]; var k = 3 ; var n = cells . length ; activeAndInactive ( cells n k ); // This code is contributed by Rajput-Ji < /script>
Izhod
Active Cells = 2 Inactive Cells = 6
Časovna zahtevnost: O(N*K) kjer je N velikost niza in K število dni.
Pomožni prostor: O(N)
Ta članek je pregledala ekipa geeksforgeeks. Če imate boljši pristop k tej težavi, delite.
