Created
April 14, 2023 10:00
-
-
Save maestroviktorin/3c206aa8cc9a62b5e0a69d26b6952fbe to your computer and use it in GitHub Desktop.
Solution to the problem #6040 by A. Rogov from the website of K. Polyakov.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| with open('26-100.txt') as file: | |
| rows = file.readlines() | |
| N, M = tuple(int(x) for x in rows[0].split()) | |
| pipes = sorted(int(x) for x in rows[1:]) | |
| for i in range(N): | |
| pipeline = [pipes[i]] | |
| j = i + 1 | |
| while len(pipeline) < M: | |
| if pipes[j] - pipeline[-1] <= 11: # 11 is the biggest possible gap | |
| # between two pipes according to the task condition. | |
| pipeline.append(pipes[j]) | |
| j += 1 | |
| else: | |
| break | |
| print(min(pipeline), max(pipeline)) | |
| # Then we are to consider only outcomes with the maximum first numbers. | |
| # It must me something like this: | |
| # ... | |
| # 1744 1992 | |
| # 1745 1992 | |
| # 1745 2000 | |
| # `Exception` | |
| # >>> | |
| # I. e. we will consider only `1745 1992` and `1745 2000`. | |
| # As we have to save as much money as possible, | |
| # we build pipeline with bandwith 1745 and maximum diameter 1992. | |
| # If we buy tube with diameter 2000, bandwith still remains 1745. | |
| # So `1745 1992` is the most profitable choice. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment