Задание 26
Задание 26 (демо-2023). В магазине для упаковки подарков есть N кубических коробок. Самой интересной считается упаковка подарка по принципу матрёшки – подарок упаковывается в одну из коробок, та в свою очередь в другую коробку и т.д. Одну коробку можно поместить в другую, если длина её стороны хотя бы на 3 единицы меньше длины стороны другой коробки. Определите наибольшее количество коробок, которое можно использовать для упаковки одного подарка, и максимально возможную длину стороны самой маленькой коробки, где будет находиться подарок. Размер подарка позволяет поместить его в самую маленькую коробку.
В первой строке входного файла находится число N – количество коробок в магазине (натуральное число, не превышающее 10 000). В следующих N строках находятся значения длин сторон коробок (все числа натуральные, не превышающие 10 000), каждое – в отдельной строке.
Запишите в ответе два целых числа: сначала наибольшее количество коробок, которое можно использовать для упаковки одного подарка, затем максимально возможную длину стороны самой маленькой коробки в таком наборе.
Решение задания проиллюстрировано на рисунке ниже.
| PascalABC.NET |
|---|
## var F:=ReadAllText('26.txt').ToIntegers[1:].SortedDescending.ToArray; var (count,max_len):=(1,F[0]); foreach var i in Range(1,F.Count-1) do if max_len-F[i]>=3 then begin count+=1; max_len:=F[i]; end; print(count,max_len); |
| Python |
F=list(map(int,open('26.txt'))) F=sorted(F[1:])[::-1]
count, max_len = 1, F[0] for i in range(1,len(F)): if max_len-F[i]>=3: count+=1 max_len=F[i] print(count, max_len) |
| Решение А.Богданова на PascalABC.NET |
ReadAllText('26.txt').ToIntegers[1:].OrderDescending .Aggregate((0,maxint), (\(k,p),x) -> p-x>=3 ? (k+1,x):(k,p)) .Print |
Рассмотрим решение в PascalABC.NET. Считываем все строки из файла в переменную F функцией ReadAllText, метод ToIntegers, совмещённый со срезом [1:] преобразует каждое число из строкового значения в целочисленное, начиная со второго элемента (первое число – количество коробок). Сортируем последовательность по убыванию функцией SortedDescending и преобразуем последовательность в массив методом ToArray (чтобы использовать некоторые методы динамических массивов).
Введём переменные count и max_len, запоминающие количество вложенных коробок и длину первой коробки соответственно. Будем проходить от самой большой коробки к самой маленькой и проверять условие: если разница длины коробки max_len и длины текущей коробки F[i] не меньше трёх, коробку можно поместить внутрь большей коробки: count увеличиваем на 1, max_len=F[i]. В ответе выводим count и max_len.
Решение на Python аналогичное: считываем из файла в переменную F значения конструкцией list(map(int,open('26.txt'))). Функция sorted(F[1:]) сортирует список, отбрасывая первый элемент. Срез [::-1] переворачивает список. Далее решение аналогично решению на PascalABC.NET.
Также на рисунке представлено решение А.Богданова с помощью агрегатной функции Aggregate. Функция Aggregate нужна, когда необходимо накапливать какие-то значения, проходя по элементам перечислимого типа данных.
Первая строка считывает числа из файла. В функции Aggregate определим начальное значение как кортеж из двух значений (0, maxint). Это, соответственно, количество коробок и максимальная длина минимальной коробки. Далее указано лямбда-выражение агрегатной функции, в котором мы распаковываем значения кортежа в переменные k и p, а переменная x берёт значения из последовательности чисел файла. Тернарный оператор в правой части лямбда-выражения проверяет, если разница максимальной длины коробки p и текущей длины x не меньше трёх, то исходный кортеж заменяем на изменённый кортеж (k+1, p), иначе оставляем кортеж прежним (k, p). В ответе получится кортеж из двух значений: количество коробок и максимальная длина минимальной коробки.