BUET Inter-University Programming Contest
Problem
I – Inked Carpets
Problem
2011
is really a very special year. The last and true Sultan on Earth is going to be
married. What can be more delightful than the marriage ceremony of our beloved
Sultan? As a part of the reception, the Sultan and his bride will walk side by
side on the royal passage which consists of L unit length cells. The
cells are numbered by 1, 2, …, L. Many
photographers and distinguished guests are coming to cover this event, so
Sultan orders his manager to cover the whole passage with beautifully colored
carpets.
His
manager found that the shop provides best quality carpets of different colors
denoted by positive integers from 1 to M and they fit exactly
from cell Start to cell End, inclusive. For
example, if a carpet fits from cell 2 to 4, it cannot be used to cover cell 1
to 3 (though the length is equal) or to cover 2 to 3 (A carpet cannot be used
partially). The carpets cannot be overlapped, i.e. if carpets which can cover 1
to 3 and 2 to 6 are available, both of them cannot be used simultaneously. The
manager has to minimize the cost of covering the whole passage. If he buys 3
consecutive (when they are placed on the passage; see NOTE) segments of same
color, he will get a discount of Minimum(D,
cost of 3rd carpet) from the shop.
Moreover,
the manager has infinite colorless carpets which can be used for any cell and
any number of times, but he must paint it with a color but this is not counted
for discount (see NOTE). The costs of coloring this carpet with different
colors are known. Now, if the change of color in consecutive segments is very
frequent, the Sultan will not like it. So, among multiple selections of
different carpets with the minimum cost, he has to minimize the total number of
color changes. A color change occurs if two consecutive segments have different
colors.
Input
First
line of input contains a positive integer T
which is the number of test cases. For each
case, the first line contains 4 integers, L, N (no. of different
carpets), M and D (amount of discount). 
The next line contains M positive integers, where i-th integer
denotes the cost of coloring unit length of the colorless carpet with i-th color. Each of the next N lines contains
4 positive integers, Start, End,
color and price of i-th
carpet. 
Output
For
each of the cases output “Case x: y z” in a separate line, where x is
case number, y is the minimum cost
and z is the minimum number of color
changes in the selection of carpets with the minimum cost.
Sample Input |
Output for Sample Input |
|
2 1 3 1 2 1 1 5 6 1 2 5 7 2 2 6 2 2 3 2 2 1 2 1 5 3 6 2 5 |
Case 1: 5 1 Case 2: 9 0 |
Explanation of Sample Cases
In the 1st case, we can
use colorless carpet for the whole passage and color that with the 1st color.
This will create a cost of 7 and 0 color changes. For minimum cost, we need to
use carpet 1 and carpet 3. We can use colorless carpet to cover 3 to 4 and
color it with color 1. That will create a cost of 1 + 1*2 + 2 = 5 and no. of
color change will be 1(from 1 to 2 in cell 4 to cell 5).
In
the 2nd case, we have to use 2nd carpet to get the minimum cost. For covering
cell 1 to cell 2, we can use the colorless carpet and color it with any color
for the minimum cost. To minimize color change, we need to color it with color
2. Then total cost = 2*2 + 5 = 9 and no. of color change will be 0.
Note
The
rule of discount can be understood from the following scenario:
Say,
the manager uses carpet of color 1 from cell 1 to cell 2 of price 10 and
colorless carpet from cell 3 to cell 4 and colors it with color 1. Then he uses
4 carpets of color 1 from cell 5 to cell 6 of price 7, from cell 7 to cell 9 of
price 3, from cell 10 to 11 of price 4 and from cell 12 to cell 15 of price 7
and the value of D is 5. Then he does not need to pay anything for cell 10 to
11. For cell 12 to cell 15, he needs to pay 2. He will not get any discount for
other carpets. Say, the coloring cost of unit length with color 1 is 8.
The
following table summarizes this scenario:
|
Start |
End |
Color
or Type |
Price |
Discount |
Final
cost |
|
1 |
2 |
1 |
10 |
0 |
10 |
|
3 |
4 |
Colorless
(1) |
0 |
0 |
2*8
= 16 |
|
5 |
6 |
1 |
7 |
0 |
7 |
|
7 |
9 |
1 |
3 |
0 |
3 |
|
10 |
11 |
1 |
4 |
Min
(4,5) = 4 |
0 |
|
12 |
15 |
1 |
7 |
Min
(5,7) = 5 |
2 |
|
|
|
Problemsetter:
|
Anindya Das |
Special Thanks:
|
Hasnain Heickal Jami
|