Aktivní a neaktivní buňky po k dnech
Je dáno binární pole o velikosti n kde n > 3 . Hodnota true (nebo 1) v poli znamená aktivní a false (nebo 0) znamená neaktivní. Zadanému číslu k je úkolem najít počet aktivních a neaktivních buněk po k dnech. Po každém dni se stav i'té buňky stane aktivním, pokud levá a pravá buňka nejsou stejné, a neaktivní, pokud levá a pravá buňka jsou stejné (obě 0 nebo obě 1).
Protože před buňkami nejvíce vlevo a za buňkami nejvíce vpravo nejsou žádné buňky, buňky s hodnotou před buňkami nejvíce vlevo a za buňkami nejvíce vpravo jsou vždy považovány za 0 (nebo neaktivní).
Příklady:
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 Jediná důležitá věc je ujistit se, že udržujeme kopii daného pole, protože potřebujeme, aby se předchozí hodnoty aktualizovaly pro další den. Níže jsou uvedeny podrobné kroky.
- Nejprve zkopírujeme pole cells[] do pole temp[] a provedeme změny v poli temp[] podle dané podmínky.
- Za podmínky je dáno, že pokud je okamžitá levá a pravá buňka i'té buňky buď neaktivní nebo aktivní, stane se i následující den neaktivní, tj.; (buňky[i-1] == 0 a buňky[i+1] == 0) nebo (buňky[i-1] == 1 a buňky[i+1] == 1) pak buňky[i] = 0 lze tyto podmínky použít pomocí XOR buněk[i-1] a buněk[i+1].
- Pro 0. index buňky temp[0] = 0^buňky[1] a pro (n-1)'-tý index temp[n-1] = 0^buňky[n-2].
- Nyní pro index 1 až n-2 proveďte následující operaci temp[i] = buňky[i-1] ^ buňky[i+1]
- Proces opakujte, dokud nebude dokončeno k dní.
Následuje implementace výše uvedených kroků.
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>
Výstup
Active Cells = 2 Inactive Cells = 6
Časová složitost: O(N*K) kde N je velikost pole a K je počet dní.
Pomocný prostor: O(N)
Tento článek je recenzován týmem geeksforgeeks. Pokud máte lepší přístup k tomuto problému, podělte se.
