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

There are many long trees in a forest. You will be given some relevant information about the trees and your task is to guess the heights of the trees. Let me describe the relevant information.You will be given a list of $N$ pairs. Each pair consists of an integer number $D$ and $F$. Here,

$D$ $=$ A positive integer number.

$F =$ Number of trees which have a height of $H$ where $H \equiv 0 \mod D$

Note that there will be no two pairs in the list such that they contain the same value of $D$. It is guaranteed that the list contains all the divisors of the heights. You have to guess the heights of the trees. *It is guaranteed that an unique solution exists for the given list of pairs.*

The first line of the input contains a single positive integer number $T(1\leq T \leq 10^5)$ where T denotes the number of testcases.

Each test case starts with a single integer $N(1\leq N \leq 10^5)$. Each of the next N lines will contain two positive integer numbers $D(1 \leq D \leq 10^5)$ and $F(1\leq F \leq 10^{5})$.

*Note that, the sum of all* $N$ *in the input file will be at most* $10^6$

For each test case print “Case T:” in a line, where T denotes the test case number. Let there be $M$ unique heights of trees for this test case. Print $M$ in the next line. After that, You have to print $M$pairs in the next $M$ lines. The pair will contain two space separated integers $H_{i}$ and $X_i$. Here,

$H_{i} = i^{th}$shortest unique height of the trees.

$X_{i} =$Number of trees of height $H_{i}$

Input | Output |
---|---|

1 3 1 3 2 2 4 1 | Case 1: 3 1 1 2 1 4 1 |

71% Solution Ratio

fextivityEarliest,

Deshi_TouristFastest, 0.2s

Tahmid690Lightest, 8.8 MB

Deshi_TouristShortest, 848B

Login to submit

The list of heights is a subset of the DDD values in the given lists. The solution is given below: ...

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