Question

Археологи раскопали Древний Храм, ко входу в который ведет лестница, шириной в 1 (один) метр, из М ступенек различной длины и высоты. Лестница построена из каменных блоков 1x1x1 метр. Археологи хотят для удобства туристов, чтобы лестница состояла из меньшего количества ступенек N. Для этого они могут также устанавливать каменные блоки 1x1x1. Какое минимальное количество блоков необходимо, чтобы сделать лестницу в N ступенек, если известны начальная длина и высота каждой ступеньки. Высоты и длины ступенек новой лестницы могут различаться.

Входные данные
В первой строке через пробел заданы два целых числа M и N (1 ≤ N < M ≤ 100). Далее идут M строк, содержащих пару целых чисел L и H - длина и высота i-ой ступеньки соответственно (1 ≤ L, H ≤ 101). Ступеньки нумеруются снизу вверх.

Выходные данные
В выходной файл выведите единственное число - ответ на задачу.

Примеры
входные данные
5 3
4 2
1 2
5 2
1 2
2 1
выходные данные
3

Answer 1

Ответ:

Задачка мне очень понравилась, прилагаю решение на C#, консольное приложение

Объяснение:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace Археологи_строители

{ class Program

   {

       static void Main(string[] args)

       {

           //Объявляем и задаем переменные "M" и "N", а так же переменную для результата

           int M,N=new int();

           int MyResult = 0;

           Console.WriteLine("Ведите Текущее количество ступенек и Сколько их должно быть:");

           M = int.Parse(Console.ReadLine());

           N = int.Parse(Console.ReadLine());

           // Создаем массив для хранения данных о ступенях. M-Количество ступенек, Цифра - для колонок длины и высоты

           int[,] mass = new int[M,2];

           // Запись значений в массив

           for (int x = 0; x < M; x++){

               for (int y = 0; y < 2; y++){

                   if (y==0){  //Чисто для юзерфрендли отображения

                       Console.Write($"Введите значение Длины для ступеньки №{x + 1}= ");} else{

                       Console.Write($"Введите значение Высоты для ступеньки №{x + 1}= ");}

                   mass[x, y] = Convert.ToInt32(Console.ReadLine());}

                   Console.WriteLine();}

           /* Как оказалось, самый простой способ определить какую же ступеньку надо "поднимать"-

            * это вычислить площадь гипотетически "заполняемого" пространства над ступенькой и взять

            * наименьшее значение.

            *  

            * Итак, допустим если у нас 5 ступенек, то нам нам необходимо записать 4 значения

            * (в рамках лестницы) площади заполняемых ступенек.

            *  

            * Перемножаем Длину ступеньки N на высоту ступеньки N+1, M-1 раз и сохраняем в массив

            */

           int M2 = M; //Дублируем изначальное число ступенек для контроля цикла

           for (int z = 0; z <M2-N; z++)

           {

               int[] acreage = new int[M - 1];

               for (int x = 0; x < M - 1; x++)

               {

                   for (int y = 0; y < 2; y++)

                   {

                       acreage[x] = mass[x, 0] * mass[x + 1, 1];

                   }

               }

               /*

                * И так у нас есть все значения гипотетически заполняемой ступеньки.

                * Ищем минимальное значение площади  

                */

               int minAcreage = acreage[0];

               for (int i = 0; i < M - 1; i++)

               {

                   if (minAcreage > acreage[i])

                   {

                       minAcreage = acreage[i];

                   }

               }

               MyResult = MyResult+minAcreage; //Плюсуем данное значение в переменную результата

               // У нас есть минимальная площадь. Найдем номер данной ступеньки

               int IndexAcreage = Array.IndexOf(acreage, minAcreage);

               //"Достроим нужную нам ступеньку и запишем обновленные данные во временный массив"

               int[,] tempMass = new int[M - 1, 2]; //Он на размер меньше, т.к. и "полных" ступенек у нас стало меньше

               for (int x = 0; x < M - 1; x++)

               {

                   for (int y = 0; y < 2; y++)

                   {

                       //Ступеньки до IndexAcreage мы просто переписываем во временный массив

                       if (x < IndexAcreage)

                       {

                           tempMass[x, y] = mass[x, y];

                       }

                       //2 ступеньки от IndexAcreage мы превращаем в одну (застраивая их блоками)

                       else if (x == IndexAcreage)

                       {

                           tempMass[x, y] = mass[x, y] + mass[x + 1, y];

                       }

                       /* и после IndexAcreage мы та же копируем, но со сдвигом вправо, т.к. полноценных  

                        * ступенек стало меньше

                        */

                       else if (x > IndexAcreage)

                       {

                           tempMass[x, y] = mass[x + 1, y];

                       }

                   }

               }

               M = M - 1; //Поскольку ступенек теперь меньше, то и их фактическое число необходимо уменьшить

               for (int x = 0; x < M + 1; x++)

               {

                   for (int y = 0; y < 2; y++)

                   {

                       mass[x, y] = 0;

                   }

               }

               //переписываем данные в основной массив и запускаем следющую интерацию цикла

               for (int x = 0; x < M; x++)

               {

                   for (int y = 0; y < 2; y++)

                   {

                       mass[x, y] = tempMass[x, y];

                   }

               }

           }

           Console.WriteLine($"Минимально необходимое число блоков: {MyResult}");

           Console.ReadKey(true);

       }

   }

}

f1ef4796e701370067c3341d4b3a3d74.txt