There is a sequence of N jobs to be processed on one machine. The jobs are numbered
from 1 to N, so that the sequence is 1,2,…, N. The sequence of jobs must be partitioned
into one or more batches, where each batch consists of consecutive jobs in the sequence.
The processing starts at time 0. The batches are handled one by one starting from the
first batch as follows. If a batch b contains jobs with smaller numbers than batch c, then
batch b is handled before batch c. The jobs in a batch are processed successively on the
machine. Immediately after all the jobs in a batch are processed, the machine outputs
the results of all the jobs in that batch. The output time of a job j is the time when the
batch containing j finishes.
A setup time S is needed to set up the machine for each batch. For each job i, we know
its cost factor Fi and the time Ti required to process it. If a batch contains the jobs x, x+1,
…, x+k, and starts at time t, then the output time of every job in that batch is t + S + (Tx
+ Tx+1 +…+ Tx+k). Note that the machine outputs the results of all jobs in a batch at the
same time. If the output time of job i is Oi, its cost is Oi * Fi. For example, assume that
there are 5 jobs, the setup time S = 1, (T1, T2, T3, T4, T5) = (1, 3, 4, 2, 1), and (F1, F2, F3,
F4, F5) = (3, 2, 3, 3, 4). If the jobs are partitioned into three batches {1, 2}, {3}, {4, 5},
then the output times (O1, O2, O3, O4, O5) = (5, 5, 10, 14, 14) and the costs of the jobs
are (15, 10, 30, 42, 56), respectively. The total cost for a partitioning is the sum of the
costs of all jobs. The total cost for the example partitioning above is 153.
You are to write a program which, given the batch setup time and a sequence of jobs
with their processing times and cost factors, computes the minimum possible total cost.
The input file consists of multiple testcases and is ended with EOF. Each of the testcase is described as follow:
Your program reads from standard input. The first line contains the number of jobs N. The second line contains the batch setup time S which is an integer. The following N lines contain information about the jobs 1, 2,…, N in that order
as follows. First on each of these lines is an integer Ti, the processing time
of the job. Following that, there is an integer Fi, the cost factor of the job.
For each testcase your program should write to standard output one line, which contains one integer: the minimum possible total cost.
2 50 100 100 100 100 5 1 1 3 3 2 4 3 2 3 1 4
45000 153
This series of homework are all problems with ungiven input size! It is (at least the original aim of it is) to enable us to acutally think about a problem from scratch, without the "additional informations" implicated by a specific given problem size.
Of course, we do hope it'd be a rather fun experience, since in real life problems often we do not know whether a problem exhibits an efficient algorithm or is even solvable!!
Anyway, the input size, though not specified, will be "reasonable". That is, if the optimal algorithm is O(n3), then n would be something like 300, if O(nlgn), then perhaps 200000.. etc. Also if values are not otherwise specified, they could be expected to be for example, int.
Migrated from old NTUJ.
IOI2002 korea
| No. | Testdata Range | Score |
|---|