Komórki aktywne i nieaktywne po k dniach
Biorąc pod uwagę tablicę binarną o rozmiarze n gdzie n > 3 . Wartość true (lub 1) w tablicy oznacza aktywność, a wartość false (lub 0) oznacza nieaktywność. Biorąc pod uwagę liczbę k, zadaniem jest znalezienie liczby aktywnych i nieaktywnych komórek po k dniach. Po każdym dniu status i-tej komórki staje się aktywny, jeśli lewa i prawa komórka nie są takie same, i nieaktywny, jeśli lewa i prawa komórka są takie same (obie 0 lub obie 1).
Ponieważ przed komórkami skrajnie lewymi i po komórkach skrajnie prawych nie ma żadnych komórek, komórki wartości przed komórkami skrajnie lewymi i komórkami skrajnie prawymi są zawsze uznawane za 0 (lub nieaktywne).
Przykłady:
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 Jedyną ważną rzeczą jest to, aby zachować kopię danej tablicy, ponieważ potrzebujemy poprzednich wartości do aktualizacji na następny dzień. Poniżej znajdują się szczegółowe kroki.
- Najpierw kopiujemy tablicę komórek[] do tablicy temp[] i wprowadzamy zmiany w tablicy temp[] zgodnie z podanym warunkiem.
- Pod warunkiem jest dane, że jeśli bezpośrednia lewa i prawa komórka i-tej komórki albo będzie nieaktywna, albo aktywna, następnego dnia i stanie się nieaktywne, tj.; (komórki[i-1] == 0 i komórki[i+1] == 0) lub (komórki[i-1] == 1 i komórki[i+1] == 1) wtedy komórki[i] = 0 te warunki można zastosować za pomocą XOR komórek[i-1] i komórek[i+1].
- Dla 0-tej komórki indeksowej temp[0] = 0^cells[1] i dla (n-1)-tej komórki indeksowej temp[n-1] = 0^cells[n-2].
- Teraz dla indeksu 1 do n-2 wykonaj następującą operację temp[i] = komórki[i-1] ^ komórki[i+1]
- Powtarzaj proces aż do zakończenia k dni.
Poniżej znajduje się realizacja powyższych kroków.
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>
Wyjście
Active Cells = 2 Inactive Cells = 6
Złożoność czasowa: O(N*K) gdzie N to rozmiar tablicy, a K to liczba dni.
Przestrzeń pomocnicza: O(N)
Ten artykuł jest recenzowany przez zespół geeksforgeeks. Jeśli masz lepsze podejście do tego problemu, udostępnij.
