Рубрики

Проверьте, можно ли строго увеличить две строчки, поменяв местами только соответствующие значения

Для двух n * m матриц A [] [] и B [] [] задача состоит в том, чтобы строго увеличить обе матрицы (строки и столбцы) только путем замены двух элементов в разных матрицах, если они расположены в соответствующей позиции. то есть A [i] [j] можно поменять местами только с B [i] [j] . Если возможно, то напечатайте Да, иначе Нет .

Примеры:

Input: 
A[][] = {{2, 10},      B[][] = {{9, 4},  
         {11, 5}}               {3, 12}}
Output: Yes
Swap 2 with 9 and 5 with 12 then the resulting 
matrices will be strictly increasing.

Input: 
A[][] = {{1, 3},       B[][] = {{3, 1}, 
         {2, 4},                {3, 6}, 
         {5, 10}}               {4, 8}}
Output: No

Подход: мы можем решить эту проблему, используя жадную технику . Поменяйте местами A [i] [j] с B [i] [j], если A [i] [j]> B [i] [j] . В конце для каждого i и j имеем A [i] [j] ≤ B [i] [j] .
Если результирующие матрицы строго увеличиваются, выведите « Да», в противном случае выведите « Нет» .

Ниже приведена реализация вышеуказанного подхода:

питон

# Функция для проверки наличия матриц
# можно сделать строго увеличивая
# с данной операцией

def Check(a, b):

  

    # Менять местами только когда a [i] [j]> b [i] [j]

    for i in range(n):

        for j in range(m):

            if a[i][j]>b[i][j]:

                a[i][j], b[i][j]= b[i][j], a[i][j]

  

    # Проверьте, строго ли растут строки

    for i in range(n):

        for j in range(m-1):

            if(a[i][j]>= a[i][j + 1] or b[i][j]>= b[i][j + 1]):

                return "No"

  

    # Проверьте, строго ли увеличиваются столбцы

    for i in range(n-1):

        for j in range(m):

            if (a[i][j]>= a[i + 1][j] or b[i][j]>= b[i + 1][j]):

                return "No"

  

    return "Yes"

  
# Код драйвера

if __name__=="__main__":

      

    n, m = 2, 2

    a =[[2, 10], [11, 5]]

    b =[[9, 4], [3, 12]]

    print(Check(a, b))

PHP

<?php
// PHP реализация подхода

  
// Функция для проверки наличия матриц
// можно сделать строго увеличивая
// с данной операцией

function Check($a, $b, $n, $m)

  

    // Меняем местами только когда a [i] [j]> b [i] [j]

    for ($i = 0; $i < $n; $i++)

    

        for ($j= 0; $j < $n; $j++)

        

            if ($a[$i][$j] > $b[$i][$j]) 

            {

                $temp = $a[$i][$j];

                $a[$i][$j] = $b[$i][$j];

                $b[$i][$j] = $temp;

            }

        }

    }

              

  

    // Проверяем, строго ли растут строки

    for ($i = 0; $i < $n; $i++)

    

        for ($j= 0;$j < $m-1 ; $j++)

        

            if($a[$i][$j] >= $a[$i][$j + 1] or 

               $b[$i][$j] >= $b[$i][$j + 1])

                return "No";

        }

    }

  

    // Проверяем, строго ли увеличиваются столбцы

    for ($i = 0; $i < $n - 1; $i++)

    {

        for ($j = 0; $j < $m; $j++)

        

            if ($a[$i][$j] >= $a[$i + 1][$j] or 

                $b[$i][$j] >= $b[$i + 1][$j])

                return "No";

        }

    }

    return "Yes";

}

  
// Код драйвера

$n = 2; $m = 2;

$a = array(array(2, 10), array(11, 5)); 

$b = array(array(9, 4), array(3, 12)); 

print(Check($a, $b, $n, $m));

  
// Этот код предоставлен AnkitRai01
?>

Выход:

Yes

Рекомендуемые посты:

Проверьте, можно ли строго увеличить две строчки, поменяв местами только соответствующие значения

0.00 (0%) 0 votes