EDIT: I posted this question searching for a beautiful, original solution to this problem. Therefore, I accepted a user's edited category "popularity-contest". Still, I keep receiving down-votes from people and requests that I make this a search for optimal solutions (i.e. runtime, code size etc.). That is not my intention. I'm leaving the problem open for a few more hours, if people still down-vote it for no reason, I'll just go ahead and delete it. Maybe I am posting to the wrong community (probably should be searching for enthusiastic programmer communities).
John wants to write this phrase multiple times into a text document:
I am a copy-paste master.
He creates a new, empty text document, and types down the phrase. He wants to copy and paste this phrase on a new line until he reaches at least a certain number of lines. He figures out it would be quicker if, from time to time, he selected all the text written so far, copies again and then resumes pasting.
Assume the following:
- At time
t = 0the phrase has been typed for the first time and John begins the copy-paste process.
- It takes
T1to Select All (Ctrl+A), Copy (Ctrl+C) and Clear Selection (End) => Operation 1
- It takes
T2to press Enter and then Paste (Ctrl+V) => Operation 2
- After he has copied the phrase the first time, let
N1be the number of Operations 2 until he does Operation 1 again; then follows
N2times Operation 2, etc., the last set of Operation 2 being done
Lbe the target (minimum) number of lines.
- A solution of the problem consists of the collection: (
A quick example: for
L = 10, possible solutions are:
- (1, 9)
- (2, 4, 1)
- (3, 1, 2, 1)
T2), find the solution (
Nk) that minimizes the total time to reach at least
Obviously the total time is:
T = k * T1 + T2 * SUM(Nj; j=1..k)
And the total number of lines at the end of
L' = PRODUCT(1 + Nj; j=1..k) with the condition
L' >= L
Optimizer's suggestion, I will break down the (3, 1, 2, 1) solution for L = 10:
- step 1: copy 1 line, then 1 paste => 2 lines
- step 2: copy 2 lines, then 2 pastes => 6 lines
- step 3: copy 6 lines, then 1 paste => 12 lines