divide and conquer: computing the time elapsed

Question

I have to do a little assignment at my university:

I have a server that runs 'n' independent services. All these services started at the same time in the past. And every service 'i' writes 'b[i]' lines to a log file on the server after a certain period of time 's[i]' in seconds. The input consist of 'l' the number of lines of the log file and 'n' the number of services. Then we have in the next 'n' lines for every service i: 's[i]' the period as mentioned and 'b[i]' the number of lines the services writes to the log file.

I have to compute from the number of lines in the log file, how long ago, in seconds, the programs all started running. Example:

input:  
19 3 
7 1
8 1
10 2

Output: 
42

I have to use divide and conquer, but I can't even figure out how to split this in subproblems. Also I have to use this function, where ss is the array of the periods of the services and bs the number of lines which each services writes to the log file:

long linesAt(int t, int[] ss, int[] bs) {
  long out = 0;
  for (int i = 0; i < ss.length; i++) {
     // floor operation
     out += bs[i] * (long)(t/ss[i]);
  }
  return out;

ss and bs are basically arrays of the input, if we take the example they will look like this, where the row above is the index of the array:

ss:

0 1 2
7 8 10

bs:

0 1 2
1 1 2

It is easily seen that 42 should be the output

 linesAt(42) = floor(42/7)*1+floor(42/8)*1+floor(42/10)*2 = 19

Now I have to write a function

int solve(long l, int[] ss, int[] bs)

I already wrote some pseudocode in brute force, but I can't figure out how to solve this with the divide and conquer paradigm, my pseudocode looks like this:

Solve(l, ss, bs)
  out = 0
  t = 0
  while (out != l)
    out = linesAt(t, ss, bs)
    t++
  end while
  return t

I think I have to split l in some way, so to calculate the time for smaller lengths. But I don't really see how, because when you look at this it doesn't seem to be possible:

t           out
0..6        0
7           1
8           2
9           2
10          4
11..13      4
14          5
15          5
16          6
17..19      6
20          8
...
40          18
42          19

Chantal.

Answer 1

You are trying to solve an integer equation:

 floor(n/7)*1+floor(n/8)*1+floor(n/10)*2 = 19

You can remove the floor function and solve for n and get a lower bound and upper bound, then search between these two bounds.

Solving the following equation:

(n/7)*1+(n/8)*1+(n/10)*2 = 19
n=19/(1/7+1/8+2/10)

Having found n, which range of value m0 will be such that floor (m0 / 7) = floor (n/7)?

floor (n/7) * 7 <= m0 <= (ceiling (n/7) * 7) - 1

In the same manner, calculate m1 and m2.

Take max (mi) as upperbound and min(mi) as lowerbound for i between 1 and 3 .

A binary search at this point will probably be an overkill.