Analysis of task 26 of the 2022 demo
The system administrator creates an archive of user files once a week. However, the size of the disk where it places the archive may be less than the total size of the archived files. It is known how much space each user's file occupies. Given information about the size of user files and the free space on the archive disk, determine the maximum number of users whose files can be archived, as well as the maximum size of an existing file that can be stored in the archive, provided that the files of the maximum possible number of users are saved.
Input
The first line of the input file 26.txt contains two numbers: S – the amount of free disk space (a natural number not exceeding 100,000) and N – number of users (a natural number not exceeding 10000). The next N lines contain the values of each user's files (all natural numbers not exceeding 100), each in a separate line. Write down two numbers in your answer: first, the largest number of users whose files can be archived, then the maximum size of an existing file that can be archived, provided that the files of the maximum possible number of users are stored.
Example input file:
100 4
80
30
50
40
With this initial data, you can save the files of a maximum of two users. The possible sizes of these two files are 30 and 40, 30 and 50 or 40 and 50. The largest file size of the listed – 50, so the answer for this example is:
2 50
Idea of solution
1) Since it is necessary to save the files of the maximum number of users, therefore, we will take the files of those users whose volumes are as small as possible. Then in total we will reach the required volume using as many files as possible.
2) We will collect files until the sum of their volumes is less than the free space on the archive disk.
3) After setting the required volume, most likely we will have some difference (
\(\triangle\)). Thanks to this difference, we can replace one file with another, with a larger volume.
4) You need to replace the file with the largest volume. Why? It must be replaced in such a way that the difference between the files is no more than
\(\triangle\). That is, the condition must be met
\(X - x <= \triangle\), where
X is the value to replace, < code>x - the value to be replaced. Analyzing this expression, one can easily understand that with a larger
X we will replace the larger
x.
Word Algorithm
1) Read the data from the first line into the variables S and N.
2) Read the data into an array.
3) Sort the original array in ascending order.
4) We go through the array and at the same time calculate the sum of the elements, while it is less than or equal to S.
5) We stop iterating over the array at the moment when the next value, when added to the sum, will exceed the value of S.
5) Calculate the difference (
\(\triangle\)) between the calculated sum and S.
6) Go further in the array and look for the
maximum value that satisfies the condition
\(X - x <= \triangle\).
Implement this verbal algorithm yourself.