Assign 1:
The task is to develop a program which optimizes time spent while commuting.
Assume we are commuting and we are using public transport. We have just arrived to a station and we need to change to another connection. But, sadly, the connection has departed a few minutes before. What a pity! Hopefully, our program will help us to avoid this undesired situation.
Assume we use connection #1 and we have to change to connection #2 on a certain stop. Connection #1 has fixed intervals (hours : minutes) and connection #2 also has fixed intervals (may be different from connection #1). We assume the intervals do not change (i.e. the frequency is the same, no day/night/peak differences) and we assume the connections adhere to their timetables. When connection #1 arrives to the change stop, we know the time elapsed since the last connection #2 departed. Based on these, the program is to compute optimal time when to arrive. The optimal means a situation where connection #2 departs exactly 1 minute after the arrival of connection #1.
The input consists of three times: interval of connection #1 (hours:minutes), interval of connection #2 (hours:minutes), and the time elapsed since last connection #2 departed (hours:minutes).
The output of the program may be one of the following:
a time (hours:minutes) until the next optimal change (i.e. how long until there is exactly 1 minute between the arrival of connection #1 and departure of connection #2),
optimal change is right now, or
optimal change will never occur.
The exact output format of each variant is shown in sample runs below. Note: the output line must be terminated by a newline ( ).
The program must validate input data. If the input is invalid, the program detects it, it outputs an error message and terminates. If displayed, the error message must be displayed on the standard output (do not send it to the error output) and the error message must be terminated by a newline ( ). The input is considered invalid, if:
invalid hour or minute (non-numeric values, negative),
minutes exceed 59,
zero interval of a connection,
invalid combination of interval #2 and connection #2 last departure.
Advices:
The values may be represented in the int data type to pass the mandatory tests. However, long long or int64_t types must be used to pass the bonus test. Header stdint.h must be included to use int64_t type. The compiler complains about long long type, a warning is issued. This warning is suppressed, thus long long may be used without any penalty.
Use %lld format to display the contents of a long long variable.
Overflow problems are crucial in the bonus tests. The input intervals do not exceed int type range. However, some algorithms/implementations may need to compute intermediate values that exceed the range of long long type. The algorithm must be carefully modified in theses cases (e.g. change the order of some computations, divide the operations, ...).
Bonus test - SPOILER: if you want to solve the bonus by yourself, stop reading. The program does not need the time-consuming main loop. Reference uses extended Euclid's algorithm instead.
Sample program runs:
Connection #1 interval:
0:24
Connection #2 interval:
0:44
Connection #2 left before:
0:27
Connection #2 will depart 1 minute after the arrival of connection #1 in 3:12.
Connection #1 interval:
0:17
Connection #2 interval:
0:12
Connection #2 left before:
0:4
Connection #2 will depart 1 minute after the arrival of connection #1 in 3:07.
Connection #1 interval:
0:17
Connection #2 interval:
0:12
Connection #2 left before:
0:11
Connection #2 will depart 1 minute after the arrival of connection #1 just now.
Connection #1 interval:
0:16
Connection #2 interval:
0:12
Connection #2 left before:
0:6
Connection #2 will never depart 1 minute after the arrival of connection #1
Connection #1 interval:
0:16
Connection #2 interval:
0:12
Connection #2 left before:
0:15
Invalid input.
Connection #1 interval:
test
Invalid input.