Dhaka Regional ACM ICPC 2016 Preleminary Contest Solution G - Repeater

G. Repeater

Score: 1

CPU: 4s
Memory: 1200MB

Hello soldier, welcome to the military base Ground Zero. The enemies are planning to attack our base. Right now, they are camping in the jungle near our camp for the night. We must destroy them before the sunrise.
Now there are N enemy vehicles in a straight line. The distance of the vehicles are d1, d2, d3, d4,,, dn. The distances are all positive integers between 1 to M.
For all practical purpose, you can think of our base and all the vehicles are dots in a straight line.

Now the enemy doesn’t know about our secret weapon the repeater. The repeater is a powerful weapon with which can destroy the enemy vehicles. When firing the repeater, we can choose a parameter R and the repeater will first destroy everything at exactly Rdistance away, then it will destroy everything in 2R distance, then 3R, 4R until all the multiples of R less than or equal M are destroyed. Once fired, the repeater can’t be stopped. Now your job is to operate the repeater.
Now the cost of firing the repeater with parameter R is Floor(M/R). We want to destroy all the enemy vehicles but we also want to minimize the cost. You can fire the repeater as many times as you want.
So now if M is 10 and enemy vehicles are at 2, 6 and 9 distance away, we can fire the repeater with parameter R=1 and destroy them but the cost will be Floor(10/1) = 10. Better approach is firing with parameter R=2 and R=9 where the total cost will be Floor(10/2) + Floor(10/9) = 5 + 1 = 6.
So, soldier, your mission is to destroy all the enemy vehicles with minimum cost. Don’t disappoint us.

Input

First line of the input is T(≤100), then T test cases follows. Each case start with a line containing 2 positive integers N (1 ≤ N ≤ 17) the number of enemy vehicles and M (1 ≤ M ≤ 1000000). Next line will be N positive integers d1, d2, d3 ,,, ddn ( 1 ≤ di ≤ M ) which are distances of enemy vehicles.

Output

For each test case print a line in “Case I: C” format where I is case number and C is the minimum cost for destroying all the enemy vehicles.

Sample

InputOutput
1 3 10 2 6 9














Comments

Post a Comment

Popular posts from this blog

Solution - Timus Problem 1293. Eniya

1293. Eniya Time limit: 1.0 second Memory limit: 64 MB It’s restless now on the slips of the intergalactic port’s sixth dock of planet of Torn. No longer then in a month the reconstruction of the small ironclad corvette “Eniya” will be finished. And again this battle ship and its brave team would have to struggle for the control over plutonium mines of Sibelius. The work cannot be stopped even for a second, self-powered laser welders work round the clock. Joints of robots-repairers fuse because of this permanent work. Nevertheless, they can’t stop not for a single moment. Now in all this turmoil it is discovered that corvette’s thermopanels again need an urgent processing with thorium sulphide. It is known that the processing of the one square meter of the panel needs 1 nanogramm of sulphide. In general, it is needed to process  N  rectangular panels, which dimensions are  A  by  B  meters. It is necessary to calculate as fast as possible, how m...
Read more...

Solution - Codeforces Problem 327B - Hungry Sequence

B. Hungry Sequence Iahub and Iahubina went to a date at a luxury restaurant. Everything went fine until paying for the food. Instead of money, the waiter wants Iahub to write a Hungry sequence consisting of  n  integers. A sequence  a 1 ,  a 2 , ...,  a n , consisting of  n  integers, is  Hungry  if and only if: Its elements are in increasing order. That is an inequality  a i  <  a j  holds for any two indices  i ,  j   ( i  <  j ) . For any two indices  i  and  j   ( i  <  j ) ,  a j  must  not  be divisible by  a i . Iahub is in trouble, so he asks you for help. Find a Hungry sequence with  n  elements. Input The input contains a single integer:  n  ( 1 ≤  n  ≤ 10 5 ). Output Output a line that contains  n  space-separated integers  a 1   a 2 , ...,  a n   (1 ≤  a i  ≤ 10 7 ) , representing a ...
Read more...

Solution - Timus Problem 1409. Two Gangsters

1409. Two Gangsters Time limit: 1.0 second Memory limit: 64 MB Two gangsters Harry and Larry had a rest at countryside. They decided to spend some time shooting, so they put several beer cans (no more than 10) on a log. Harry started to shoot cans one after another from the leftmost to the right and Larry – from the rightmost to the left. At some moment it happened so that they shot one and the same can. Harry got indignant and claimed that Larry owed him a considerable sum of money because Larry deprived him of shooting some more cans. Larry became furious and told Harry that he owed even greater sum of money to Larry because of the same reason. They started to argufy but nobody remembered how many cans there were at the very beginning. And no one of them was going to search cans which was shot. Anyway, each of them remembered exactly how many cans he shot. Determine how many cans were not shot by Harry and how many cans were not shot by Larry. Input The only inp...
Read more...