Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Car Selection

By shuvon · Limits 2s, 512 MB

Alice and Bob are two friends. They want to buy two cars, one for Alice and one for Bob. That's why they come to a car shop. Alice wants to move faster. So, she wants to purchase the fastest car. On the other hand, Bob wants safety first. So, he wants to purchase the slowest car. They also want to spend the least money possible. So, if multiple cars are fulfilling their speed requirement, they will choose the one among them that has the lowest PricePrice.

At first, there is no car in the shop. When a car arrives, its speed XX will be given. Let’s define, F(X)=F(X) = summation of each digit of XX and G(X)=G(X) = multiplication of (1+1+ each digit of XX). For example, F(355)=3+5+5=13F(355)=3+5+5=13 and G(355)=(1+3)×(1+5)×(1+5)=144G(355)=(1+3)\times (1+5)\times (1+5)=144.

The cars have PointsPoints based on the values of F(x)F(x) and G(x)G(x) where Points=F(X)×G(X)Points = F(X)\times G(X). If a car arrives and this is the only car in the shop then PricePrice of the car is equal to the PointsPoints of the car. Otherwise, PricePrice is the minimum absolute difference between the PointPoint of the selected car and the other existing cars in the shop. PricePrice of a car is defined as soon as the car arrives in the shop.
For example, if the PointsPoints of the cars existing in the shop are: [50,24,18,90,10][50, 24, 18, 90, 10] and a car of Point 20Point\space 20 is arrived, then the PricePrice of the car will be: 1820=2|18-20| = 2, as this is the minimum absolute difference between the PointPoint of the car and the other existing cars in the shop.

You are given an integer QQ. You have to perform total QQ queries of 33 types. They are:


Query type 11:
11 XX
A new car arrives at the shop whose speed is XX

Query type 22:
22
Alice wants to purchase a car. Tell her the price of the car she will purchase.

Query type 33:
33
Bob wants to purchase a car. Tell him the price of the car he will purchase

Once Alice or Bob will purchase a car, that car will be removed from the shop. If there is no car to purchase output 1-1.

Input

Input may contain several test cases. At first, you will be given an integer TT, the number of test cases.
Each test case will start with an integer QQ, the number of queries. Then each query will follow. In the case of query type 1, you will be given an integer XX which is the speed of the car.

Constraints:
1T1051 \leq T \leq 10^5
1Q1061 \leq Q \leq 10^6
1X1091 \leq X \leq 10^9
The summation of QQ in all test cases will not exceed 10610^6.

Output

In each test case, at first print “Case xx:” in a separate line where xx is the case number starting from 11. Then for each query of types 22 and 33, print the desired answer in a new line.

Sample

InputOutput
1
10
1 200
1 100
1 200
3
1 10
2
1 10
3
3
2
Case 1:
4
0
0
4
6

    Discussion

    Statistics


    50% Solution Ratio

    Farhan20Earliest, 2w ago

    mahdi.hasnatFastest, 1.1s

    TurinhstuLightest, 112 MB

    fighterShortest, 2313B

    Submit

    Login to submit

    Editorial

    This problem can be solved using the Greedy approach. We will maintain a multiset for storing the po...

    Toph uses cookies. By continuing you agree to our Cookie Policy.