Задание 26
Пример 1
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя.
По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные.
В первой строке входного файла 26.txt находятся два числа: S – размер свободного места на диске (натуральное число, не превышающее 100 000) и N – количество пользователей (натуральное число, не превышающее 10000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример входного файла:
100 4
80
30
50
40
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар – 50, поэтому ответ для приведённого примера:
2 50
В этой задаче необходимо просто прочитать все размеры файлов, упорядочить их по возрастанию. После этого необходимо просто перебирать размеры и складывать их вместе, пока сумма не превысит заданное.
Такой алгоритм построен на логике, что чем меньше размеры файлов, тем больше их влезет в заданный объём.
Когда мы определим, сколько минимальных по размеру файлов поместится в заданный объём, нам необходимо будет проверить, нельзя ли не сохранять какой-то один файл из уже выбранных, а вместо него добавить какой-то из ещё не взятых, большего размера.
- Java
- C++
- Python
package problem26;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;
public class Example1 {
// главный метод программы, не забудьте throws FileNotFoundException, иначе программа,
// работающая с файлом не запустится
public static void main(String[] args) throws FileNotFoundException {
// открываем файл, относительный путь строится от корня проекта
// можно вместо этого закинуть файл куда-нибудь на диск и указать полный путь
Scanner in = new Scanner(new File("src/main/java/problem26/26.txt"));
// читаем объём хранилища
int s = in.nextInt();
// читаем кол-во файлов
int n = in.nextInt();
// создаём массив размеров файла
int[] arr = new int[n];
// читаем размеры
for (int i = 0; i < n; i++) {
arr[i] = in.nextInt();
}
// сортируем размеры по возрастанию
Arrays.sort(arr);
// сумма файлов
int sum = 0;
// индекс файла максимального размера
int posMax = 0;
// перебираем упорядоченные размеры файлов
for (int i = 0; i < n; i++) {
// если добавление
if (sum + arr[i] <= s) {
// прибавляем к сумме
sum += arr[i];
// т.к. мы перебираем размеры файлов в порядке возрастания,
// то в переменной posMax сохранится индекс файла, наибольшего размера
posMax = i;
} else
break;
}
// сохраняем максимальную сумму
int max = sum;
// максимальный размер сохраняемого файла
int maxSize = arr[posMax];
// перебираем все возможные пары элементов массива
// первый элемент - один из индексов файлов, взятых для сохранения
// их индексы находятся в диапазоне [0, posMax]
for (int i = 0; i <= posMax; i++) {
// второй элемент - один из индексов файлов, не взятых для сохранения
// их индексы находятся в диапазоне [posMax+1, n)
for (int j = posMax + 1; j < n; j++) {
// находим сумму, которая бы получилась, если бы мы не сохранили файл, перебираемый
// первым циклом и сохранили файл, перебираемый вторым
int nSum = sum - arr[i] + arr[j];
// если новая сумма не превышает заданный размер и
// при этом больше найденной
if (nSum <= s && nSum >= max) {
// сохраняем её в качестве найденной
max = nSum;
// если новый файл по размеру больше максимального из сохранённых
// нужно сравнивать именно с размером сохранённого
// файла максимального размера, полученного на предыдущем этапе
// ведь каждая проверка на замену файла происходит независимо
if (arr[j] > arr[posMax])
// сохраняем размер
maxSize = arr[j];
}
}
}
// выводим сумму и размер
System.out.println(sum + " " + maxSize);
}
}
#include <iostream>
#include <fstream>
#include <algorithm>
// главный метод программы
int main() {
// открываем файл
std::ifstream myfile;
// бинарник собирается в отдельной папке, поэтому относительный путь такой
// можно вместо этого закинуть файл куда-нибудь на диск и указать полный путь
myfile.open("../problem26/26.txt");
// читаем объём хранилища
int s;
myfile >> s;
// читаем кол-во файлов
int n;
myfile >> n;
// создаём массив размеров файла
int arr[n];
// читаем размеры
for (int i = 0; i < n; i++) {
myfile >> arr[i];
}
// сортируем размеры по возрастанию
std::sort(arr, arr + n);
// сумма файлов
int sum = 0;
// индекс файла максимального размера
int posMax = 0;
// перебираем упорядоченные размеры файлов
for (int i = 0; i < n; i++) {
// если добавление
if (sum + arr[i] <= s) {
// прибавляем к сумме
sum += arr[i];
// т.к. мы перебираем размеры файлов в порядке возрастания,
// то в переменной maxSize сохранится самый большой размер
posMax = i;
} else
break;
}
// сохраняем максимальную сумму
int max = sum;
// максимальный размер сохраняемого файла
int maxSize = arr[posMax];
// перебираем все возможные пары элементов массива
// первый элемент - один из индексов файлов, взятых для сохранения
// их индексы находятся в диапазоне [0, posMax]
for (int i = 0; i <= posMax; i++) {
// второй элемент - один из индексов файлов, не взятых для сохранения
// их индексы находятся в диапазоне [posMax+1, n)
for (int j = posMax + 1; j < n; j++) {
// находим сумму, которая бы получилась, если бы мы не сохранили файл, перебираемый
// первым циклом и сохранили файл, перебираемый вторым
int nSum = sum - arr[i] + arr[j];
// если новая сумма не превышает заданный размер и
// при этом больше найденной
if (nSum <= s && nSum >= max) {
// сохраняем её в качестве найденной
max = nSum;
// если новый файл по размеру больше максимального из сохранённых
// нужно сравнивать именно с размером сохранённого
// файла максимального размера, полученного на предыдущем этапе
// ведь каждая проверка на замену файла происходит независимо
if (arr[j] > arr[posMax])
// сохраняем размер
maxSize = arr[j];
}
}
}
// выводим максимальное количество
std::cout << sum << " " << maxSize << std::endl;
return 0;
}
# открываем файл, относительный путь строится от папки со скриптом
# можно вместо этого закинуть файл куда-нибудь на диск и указать полный путь
with open('26.txt') as f:
# читаем строку файла
line = f.readline()
# получаем элементы
elems = line.split(' ')
# объём хранилища - первый элемент
s = int(elems[0])
# кол-во файлов - второй
n = int(elems[1])
# создаём массив размеров файла
arr = []
# читаем размеры
for i in range(n):
arr.append(int(f.readline()))
# сортируем размеры по возрастанию
arr.sort()
# сумма файлов
sum = 0
# индекс файла максимального размера
posMax = 0
# перебираем упорядоченные размеры файлов
for i in range(n):
# если добавление
if sum + arr[i] <= s:
# прибавляем к сумме
sum += arr[i]
# т.к. мы перебираем размеры файлов в порядке возрастания,
# то в переменной posMax индекс файла, наибольшего размера
posMax = i
else:
break
# сохраняем максимальную сумму
max = sum
# максимальный размер сохраняемого файла
maxSize = arr[posMax]
# перебираем все возможные пары элементов массива
# первый элемент - один из индексов файлов, взятых для сохранения
# их индексы находятся в диапазоне [0, posMax]
for i in range(0, posMax + 1):
# второй элемент - один из индексов файлов, не взятых для сохранения
# их индексы находятся в диапазоне [posMax+1, n)
for j in range(posMax + 1, n):
# находим сумму, которая бы получилась, если бы мы не сохранили файл, перебираемый
# первым циклом и сохранили файл, перебираемый вторым
nSum = sum - arr[i] + arr[j]
# если новая сумма не превышает заданный размер и
# при этом больше найденной
if nSum <= s and nSum >= max:
# сохраняем её в качестве найденной
max = nSum
# если новый файл по размеру больше максимального из сохранённых
# нужно сравнивать именно с размером сохранённого
# файла максимального размера, полученного на предыдущем этапе
# ведь каждая проверка на замену файла происходит независимо
if arr[j] > arr[posMax]:
# сохраняем размер
maxSize = arr[j]
# выводим сумму и размер
print(sum, maxSize)
Программа выведет:
8176 50
Ответ: 8176 50
Пример 2
Организация купила для своих сотрудников все места в нескольких подряд идущих рядах на концертной площадке. Известно, какие места уже распределены между сотрудниками. Найдите ряд с наибольшим номером, в котором есть два соседних места, таких что слева и справа от них в том же ряду места уже распределены (заняты). Гарантируется, что есть хотя бы один ряд, удовлетворяющий условию.
Входные данные представлены в файле 26-59.txt следующим образом. В первой строке входного файла находится одно число: N – количество занятых мест (натуральное число, не превышающее 10 000). В следующих N строках находятся пары чисел: ряд и место выкупленного билета, не превышающие 100000. В ответе запишите два целых числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар.
Пример входного файла:
10
5 5
5 9
5 6
16 9
16 3
16 6
20 23
20 28
20 35
20 40
В данном примере есть следующие свободные места, удовлетворяющие условию: 7 и 8 в ряду 5, 4 и 5 в ряду 16, а также 7 и 8 в ряду 16. Выбираем наибольший номер ряда: 16 и наименьший номер места: 4. В ответе нужно указать: 16 4.
В этой задаче можно было бы создать двумерный массив, заполнить его значениями и после перебрать, но у него будет слишком большой диапазон, из-за чего без дополнительных ключей компилятор просто не сможет выделить столько памяти.
Поэтому лучше всего использовать словарь. Словарь - это множество пар ключ:значение. В качестве ключа мы будем использовать номер ряда, а в качестве значений хранить упорядоченные множества уже найденных номеров мест для ряда.
Упорядоченное множество удобно тем, что одной командой мы можем получить самое большое и самое маленькое значения, после чего можно просто перебрать все значения от меньшего к большему и первое, удовлетворяющее требованию задачи сохранить в качестве минимельного.
- Java
- C++
- Python
import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;
public class Example2 {
// главный метод программы, не забудьте throws FileNotFoundException, иначе программа,
// работающая с файлом не запустится
public static void main(String[] args) throws FileNotFoundException {
// открываем файл, относительный путь строится от корня проекта
// можно вместо этого закинуть файл куда-нибудь на диск и указать полный путь
Scanner in = new Scanner(new File("src/main/java/problem26/26-59.txt"));
// словарь записей вида: "номер ряда: упорядоченное множество мест"
TreeMap<Integer, TreeSet<Integer>> map = new TreeMap<>();
// читаем кол-во записей
int n = in.nextInt();
// читаем сами записи
for (int i = 0; i < n; i++) {
// читаем номер ряда
int r = in.nextInt();
// читаем номер места
int v = in.nextInt();
// если в словаре есть запись с текущим номером ряда
if (map.containsKey(r)) {
// получаем ряд
TreeSet<Integer> row = map.get(r);
// добавляем номер места в ряд
row.add(v);
} else {
// создаём новый ряд
TreeSet<Integer> row = new TreeSet<>();
// добавляем в него место
row.add(v);
// добавляем в словарь ряд с ключом, соответствующим его номеру
map.put(r, row);
}
}
// максимальный номер ряда
int maxR = 0;
// минимальный номер места
int minV = -1;
// перебираем записи словаря
for (Map.Entry<Integer, TreeSet<Integer>> entry : map.entrySet()) {
// получаем ряд
TreeSet<Integer> row = entry.getValue();
// получаем минимальный номер места в ряде
int l = row.first();
// получаем максимальный номер места в ряде
int r = row.last();
// перебираем все места ряда
for (int i = l; i <= r; i++) {
// если текущее место занято и занято через два,
// значит выполняется условие задачи для места с номером i+1
if (row.contains(i) && row.contains(i + 3)) {
// если номер ряда больше максимального
if (entry.getKey() > maxR) {
// сохраняем в качестве минимального номера
// номер следующего места
minV = i + 1;
// сохраняем номер ряда
maxR = entry.getKey();
}
// завершаем перебор мест
break;
}
}
}
// выводим номер ряда и номер места
System.out.println(maxR + " " + minV);
}
}
#include <iostream>
#include <fstream>
#include <map>
#include <set>
// главный метод программы
int main() {
// открываем файл
std::ifstream myfile;
// бинарник собирается в отдельной папке, поэтому относительный путь такой
// можно вместо этого закинуть файл куда-нибудь на диск и указать полный путь
myfile.open("../problem26/26-59.txt");
// словарь записей вида: "номер ряда: упорядоченное множество мест"
std::map<int, std::set<int>> mp;
// читаем кол-во записей
int n;
myfile >> n;
// читаем сами записи
for (int i = 0; i < n; i++) {
// читаем номер ряда
int r;
myfile >> r;
// читаем номер места
int v;
myfile >> v;
// если в словаре есть запись с текущим номером ряда
if (mp.count(r)) {
// добавляем номер места в ряд с номером r
mp.at(r).insert(v);
} else {
// создаём новый ряд
std::set<int> row;
// добавляем в него место
row.insert(v);
// добавляем в словарь ряд с ключом, соответствующим его номеру
mp.insert({r, row});
}
}
// закрываем файл
myfile.close();
// максимальный номер ряда
int maxR = 0;
// минимальный номер места
int minV = -1;
// перебираем записи словаря
for (std::pair<int, std::set<int>> entry: mp) {
// получаем ряд
std::set<int> row = entry.second;
// получаем минимальный номер места в ряде
int l = *row.begin();
// получаем максимальный номер места в ряде
int r = *row.rbegin();
// перебираем все места ряда
for (int i = l; i <= r; i++) {
// если текущее место занято и занято через два,
// значит выполняется условие задачи для места с номером i+1
if (row.count(i) && row.count(i + 3)) {
// если номер ряда больше максимального
if (entry.first > maxR) {
// сохраняем в качестве минимального номера
// номер следующего места
minV = i + 1;
// сохраняем номер ряда
maxR = entry.first;
}
// завершаем перебор мест
break;
}
}
}
// выводим максимальное количество
std::cout << maxR << " " << minV << std::endl;
return 0;
}
# открываем файл, относительный путь строится от папки со скриптом
# можно вместо этого закинуть файл куда-нибудь на диск и указать полный путь
with open('26-59.txt') as f:
# словарь записей вида: "номер ряда: упорядоченное множество мест"
mp = {}
# читаем кол-во записей
n = int(f.readline())
# читаем сами записи
for i in range(n):
# читаем строку файла
line = f.readline()
# получаем элементы
elems = line.split(' ')
# номер ряда - первый элемент
r = int(elems[0])
# номер места - второй
v = int(elems[1])
# если в словаре есть запись с текущим номером ряда
if r in mp.keys():
# получаем ряд
row = mp[r]
# добавляем номер места в ряд
row.append(v)
else:
# создаём новый ряд
row = []
# добавляем в него место
row.append(v)
# добавляем в словарь ряд с ключом, соответствующим его номеру
mp[r] = row
# максимальный номер ряда
maxR = 0
# минимальный номер места
minV = -1
# перебираем записи словаря
for key in mp.keys():
# получаем ряд
row = sorted(mp[key])
# получаем минимальный номер места в ряде
l = row[0]
# получаем максимальный номер места в ряде
r = row[-1]
# перебираем все места ряда
for i in range(l, r + 1):
# если текущее место занято и занято через два,
# значит выполняется условие задачи для места с номером i+1
if i in row and i + 3 in row:
# если номер ряда больше максимального
if key > maxR:
# сохраняем в качестве минимального номера
# номер следующего места
minV = i + 1
# сохраняем номер ряда
maxR = key
# завершаем перебор мест
break
# выводим номер ряда и номер места
print(maxR, minV)
Программа выведет:
20164 63
Ответ: 20164 63
В python нет упорядоченного множества, поэтому мы будем использовать список и сортировать его при необходимости вручную.
Пример 3
Начинающему админу Ване для тренировки выдали аппарат для сварки оптоволокна и N кусков оптоволокна, из которых попросили получить цельные куски по M метров. С целью снижения затухания сигнала в полученном кабеле нужно минимизировать количество сварок. Да и работы меньше. Укажите в ответе два числа: сколько всего сварок будет в цельных кусках и сколько останется кусков, из которых не сварить цельный кусок требуемой длины. Ваня выбирал куски строго по уменьшению длины, за исключением последнего, который выбирался исходя из минимизации длины каждого обрезка. Обрезок идет обратно в пучок кусков для следующего использования.
Входные данные представлены в файле 26-57.txt следующим образом. В первой строке входного файла записаны значения N (количество кусков оптоволокна) и M (длина необходимого цельного куска). Каждая из следующих N строк содержит одно целое число – длину очередного куска.
Пример входного файла:
10 30
17 15 14 12 11 8 6 5 4 2
Сперва взяли 17 и 14, обрез 1 обратно в кучу [15,12,11,8,6,5,4,2,1] – одна сварка. Затем взяли 15,12 и 4, обрез длиной 1 обратно в кучу [11,8,6,5,2,1,1] – две сварки. И затем взяли 11,8,6 и 5, ровно 30, без обреза – три сварки. Итого: 6 сварок и 3 оставшихся куска оптоволокна.
В этой задаче тоже проще всего динамический список и сортировать его время от времени. Мы будем извлекать наибольший элемент, добавлять его к суммарной длине блока, пока она не превысит заданную или пока не кончатся куски.
Потом в зависимости от того, набрана ли заданная длина, мы из суммы вычтем требуемую длину, получим длину отрезанного излишка.
Эту длину мы просто добавим в множество и начнём заново. Если же длина не набралась, значит кончились куски просто сохраним кол-во этих кусков и выведем в ответе.
- Java
- C++
- Python
import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;
public class Example3 {
// главный метод программы, не забудьте throws FileNotFoundException, иначе программа,
// работающая с файлом не запустится
public static void main(String[] args) throws FileNotFoundException {
// открываем файл, относительный путь строится от корня проекта
// можно вместо этого закинуть файл куда-нибудь на диск и указать полный путь
Scanner in = new Scanner(new File("src/main/java/problem26/26-57.txt"));
// создаём список длин кусков кабеля
LinkedList<Integer> lst = new LinkedList<>();
// получаем кол-во кусков
int n = in.nextInt();
// получаем требуемую длину
int m = in.nextInt();
// читаем длины кусков кабеля
for (int i = 0; i < n; i++) {
// получаем значение
int w = in.nextInt();
// добавляем его в список
lst.add(w);
}
// сортируем список
Collections.sort(lst);
// кол-во сварок
int sCnt = 0;
// кол-во оставшихся кусков
int rCnt = 0;
// пока в множестве есть элементы
while (!lst.isEmpty()) {
// сумма длин для нового блока
int sum = 0;
// кол-во использованных блоков
int eCnt = 0;
// пока суммарная длина меньше заданной и есть элементы в множестве
while (sum < m && !lst.isEmpty()) {
// получаем самый большой элемент множества, т.е. берём
// кусок кабеля самой большой длины
int e = lst.pollLast();
// добавляем его к суммарной длине
sum += e;
// увеличиваем кол-во взятых кусков на 1
eCnt++;
}
// если в итоге сумма меньше требуемой длины,
// значит, куски кабеля кончились, при этом их количество лежит в eCnt
if (sum < m) {
// просто сохраняем оставшееся количество
rCnt = eCnt;
// завершаем цикл
break;
} else { // если суммарная длина больше или равна требуемой
// получаем длину остатка
int nE = sum - m;
// добавляем его в множество
lst.add(nE);
// сортируем список
Collections.sort(lst);
// прибавляем к количеству сварок число сварок для этого блока
// она на 1 меньшее числа кусков, ведь в сварке всегда участвует два блока
sCnt += eCnt - 1;
}
}
// выводим кол-во сварных швов и кол-во оставшихся кусков
System.out.println(sCnt + " " + rCnt);
}
}
#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#include <algorithm>
// главный метод программы
int main() {
// открываем файл
std::ifstream myfile;
// бинарник собирается в отдельной папке, поэтому относительный путь такой
// можно вместо этого закинуть файл куда-нибудь на диск и указать полный путь
myfile.open("../problem26/26-57.txt");
// список длин кусков
std::vector<int> lst;
// получаем кол-во кусков
int n;
myfile >> n;
// получаем требуемую длину
int m;
myfile >> m;
// читаем длины кусков кабеля
for (int i = 0; i < n; i++) {
// получаем значение
int w;
myfile >> w;
// добавляем его в множество
lst.push_back(w);
}
// сортируем список
std::sort(lst.begin(), lst.end());
// кол-во сварок
int sCnt = 0;
// кол-во оставшихся кусков
int rCnt = 0;
// пока в множестве есть элементы
while (!lst.empty()) {
// сумма длин для нового блока
int sum = 0;
// кол-во использованных блоков
int eCnt = 0;
// пока суммарная длина меньше заданной и есть элементы в множестве
while (sum < m && !lst.empty()) {
// получаем самый большой элемент множества, т.е. берём
// кусок кабеля самой большой длины
int e = lst[lst.size()-1];
// убираем последний элемент
lst.pop_back();
// добавляем его к суммарной длине
sum += e;
// увеличиваем кол-во взятых кусков на 1
eCnt++;
}
// если в итоге сумма меньше требуемой длины,
// значит, куски кабеля кончились, при этом их количество лежит в eCnt
if (sum < m) {
// просто сохраняем оставшееся количество
rCnt = eCnt;
// завершаем цикл
break;
} else { // если суммарная длина больше или равна требуемой
// получаем длину остатка
int nE = sum - m;
// добавляем его в множество
lst.push_back(nE);
// сортируем список
std::sort(lst.begin(), lst.end());
// прибавляем к количеству сварок число сварок для этого блока
// она на 1 меньшее числа кусков, ведь в сварке всегда участвует два блока
sCnt += eCnt - 1;
}
}
// выводим максимальное количество
std::cout << sCnt << " " << rCnt << std::endl;
return 0;
}
# открываем файл, относительный путь строится от папки со скриптом
# можно вместо этого закинуть файл куда-нибудь на диск и указать полный путь
with open('26-57.txt') as f:
# читаем строку файла
line = f.readline()
# получаем элементы
elems = line.split(' ')
# кол-во кусков - первый элемент
n = int(elems[0])
# требуемая длину - второй
m = int(elems[1])
# создаём список длин кусков кабеля
lst = []
# читаем длины
for i in range(n):
lst.append(int(f.readline()))
# сортируем длины
lst.sort()
# кол-во сварок
sCnt = 0
# кол-во оставшихся кусков
rCnt = 0
# пока в множестве есть элементы
while len(lst) > 0:
# сумма длин для нового блока
sum = 0
# кол-во использованных блоков
eCnt = 0
# пока суммарная длина меньше заданной и есть элементы в множестве
while sum < m and len(lst) > 0:
# получаем самый большой элемент множества, т.е. берём
# кусок кабеля самой большой длины
e = lst[-1]
# убираем последний самый большой элемент из списка
lst = lst[:-1]
# добавляем его к суммарной длине
sum += e
# увеличиваем кол-во взятых кусков на 1
eCnt = eCnt + 1
# если в итоге сумма меньше требуемой длины,
# значит, куски кабеля кончились, при этом их количество лежит в eCnt
if sum < m:
# просто сохраняем оставшееся количество
rCnt = eCnt
# завершаем цикл
break
# если суммарная длина больше или равна требуемой
else:
# получаем длину остатка
nE = sum - m
# добавляем его в множество
lst.append(nE)
lst.sort()
# прибавляем к количеству сварок число сварок для этого блока
# она на 1 меньшее числа кусков, ведь в сварке всегда участвует два блока
sCnt += eCnt - 1
# выводим кол-во сварных швов и кол-во оставшихся кусков
print(sCnt, rCnt)
Программа выведет:
9833 167
Ответ: 9833 167