Pancake Deque solution codejam

 

Problem

Pancake Deque solution codejam

The lines at the air pump at your gas station are getting too long! You want to optimize the process to help customers more quickly inflate their tires, sports balls, giant parade balloon animals, and other products.

The pump is automatic: you set the pressure to a specific number of pascals and plug the pump into the inflatable product, and it will inflate as needed to that exact pressure. There are only two buttons on the pump: up and down. They increase and decrease the target pressure, respectively, by exactly 11 pascal.

Image of air pump and soccer ball.

There is a line of NN customers, each of whom brings exactly PP products that they need to get inflated by the pump. You know the target pressure of each product. You can inflate the products from a customer in any order you want, but you cannot change the order of the customers. Specifically, you must inflate all products from the ii⁠-th customer before inflating any from the (i+1)(i+1)⁠-th customer. In between handling two products, if those two products have different target pressures, you need to use the buttons on the pump.

ALSO READ:-   I love AAAB solution codeforces

The pump is initially set to  pascals, and it can be left at any number after all products of all customers have been inflated. If you order the products of each customer optimally, what is the minimum number of button presses you need?

Input

Pancake Deque solution codejam

The first line of the input gives the number of test cases, TTTT test cases follow. Each test case starts with a line containing two integers, NN and PP: the number of customers and the number of products each customer brings, respectively. Then, NN lines follow. The ii-th of these lines contains PP integers Xi,1,Xi,2,,Xi,PXi,1,Xi,2,…,Xi,P, representing that the jj-th product that the ii-th customer brings has a target pressure of Xi,jXi,j pascals.

Output

For each test case, output one line containing Case #xxyy, where xx is the test case number (starting from 1) and yy is the minimum number of button presses needed to inflate all products according to their specified pressures.

ALSO READ:-   Controlled Inflation solution codejam

Limits

Time limit: 5 seconds.
Memory limit: 1 GB.
1T1001≤T≤100.
1Xi,j1091≤Xi,j≤109, for all i,ji,j.

Test Set 1 (Visible Verdict)

2N102≤N≤10.
2P32≤P≤3.

Test Set 2 (Hidden Verdict)

Pancake Deque solution codejam

2N10002≤N≤1000.
2P1002≤P≤100.

Sample

Sample Input
content_copy
2
3 3
30 10 40
20 50 60
60 60 50
5 2
1 1000000000
500000000 1000000000
1 1000000000
500000000 1
1 1000000000
Sample Output
content_copy
Case #1: 110
Case #2: 4999999996

In Sample Case #1, an optimal way to use the pump is:

  1. press up 1010 times, setting the pump to 1010; pump the product (from customer 1) that needs 1010 pascals,
  2. press up 3030 times, setting the pump to 4040; pump the product (from customer 1) that needs 4040 pascals,
  3. press down 1010 times, setting the pump to 3030; pump the product (from customer 1) that needs 3030 pascals,
  4. press down 1010 times, setting the pump to 2020; pump the product (from customer 2) that needs 2020 pascals,
  5. press up 3030 times, setting the pump to 5050; pump the product (from customer 2) that needs 5050 pascals,
  6. press up 1010 times, setting the pump to 6060; pump the product (from customer 2) and the two products (from customer 3) that need 6060 pascals, and finally
  7. press down 1010 times, setting the pump to 5050; pump the product (from customer 3) that needs 5050 pascals.
ALSO READ:-   Array Balancing solution codeforces

This is a total of $$$110$$ button presses.

In Sample Case #2, notice that the answer can be larger than 232232.

ANSWER

Click Here

Leave a Comment