GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

Wednesday, 30 November 2022

November 30, 2022

[Solution] Doremy's City Construction Codeforces Solution

[Solution] Doremy's City Construction Codeforces Solution



C. Doremy's City Construction
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Doremy's new city is under construction! The city can be regarded as a simple undirected graph with n vertices. The i-th vertex has altitude ai. Now Doremy is deciding which pairs of vertices should be connected with edges.

Due to economic reasons, there should be no self-loops or multiple edges in the graph.

Due to safety reasons, there should not be pairwise distinct vertices uv, and w such that auavaw and the edges (u,v) and (v,w) exist.

Under these constraints, Doremy would like to know the maximum possible number of edges in the graph. Can you help her?

Note that the constructed graph is allowed to be disconnected.

Input

The input consists of multiple test cases. The first line contains a single integer t (1t104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n (2n2105) — the number of vertices.

The second line of each test case contains n integers a1,a2,,an (1ai106) — the altitudes of each vertex.

It is guaranteed that the sum of n over all test cases does not exceed 2105.

Output

For each test case, output the maximum possible number of edges in the graph.

November 30, 2022

[Solution] Doremy's Perfect Math Class Codeforces Solution

[Solution] Doremy's Perfect Math Class Codeforces Solution



B. Doremy's Perfect Math Class
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

"Everybody! Doremy's Perfect Math Class is about to start! Come and do your best if you want to have as much IQ as me!" In today's math class, Doremy is teaching everyone subtraction. Now she gives you a quiz to prove that you are paying attention in class.

You are given a set S containing positive integers. You may perform the following operation some (possibly zero) number of times:

  • choose two integers x and y from the set S such that x>y and xy is not in the set S.
  • add xy into the set S.

You need to tell Doremy the maximum possible number of integers in S if the operations are performed optimally. It can be proven that this number is finite.

Input

The input consists of multiple test cases. The first line contains a single integer t (1t104) — the number of test cases. The description of the test cases follows.

The first line contains an integer n (2n105) — the size of the set S.

The second line contains n integers a1,a2,,an (1a1<a2<<an109) — the positive integers in S.

It is guaranteed that the sum of n over all test cases does not exceed 2105.

Output

For each test case, you need to output the maximum possible number of integers in S. It can be proven that this value is finite.

Note

In the first test case, no such x and y exist. The maximum possible number of integers in S is 2.

In the second test case,

  • S={5,10,25} at first. You can choose x=25y=10, then add xy=15 to the set.
  • S={5,10,15,25} now. You can choose x=25y=5, then add xy=20 to the set.
  • S={5,10,15,20,25} now. You can not perform any operation now.

After performing all operations, the number of integers in S is 5. It can be proven that no other sequence of operations allows S to contain more than 5 integers.