Here's a chomped version of the task:

A program has to be copied to N computers. At the moment the program is installed only on one computer. Other computers do not have floppy drives and are not connected with a local network. The only way to transfer information from one computer to another is to copy it using a null-modem cable (a cable that connects two computers directly). So, if the program is installed on a computer, it can be copied to some other (but only one!) computer within an hour. There are only K null-modem cables. Your task is to estimate the minimal time necessary for copying the program to all the compters, given N and K.

At first sight the task seems trivial. The number of computers copied every hour grows up to K. So, on each hour, the number of copies is min(K, total # of computers). It indeed works and provides correct answers, but fails on time limit. I first implemented it with a loop, but they must be running it for huge N and K and the time limit is 0.1 second, so...

The solution to this problem isn't too difficult... I just left the loop part until the amount of copies reached K. After that, K copies are made each hour, so a simple arithmetic formula says how long is left.

Also, a lesson for the future: test the program for end-cases before submitting. I got wrong answer 8 times before it was finally accepted...


comments powered by Disqus