5/22/24, 12:10 PM Problem - 1731E - Codeforces
|
stdfloat | Logout
HOME TOP CATALOG CONTESTS GYM PROBLEMSET GROUPS RATING EDU API CALENDAR HELP
PROBLEMS SUBMIT STATUS STANDINGS CUSTOM TEST
Codeforces Round 841 (Div. 2) and
E. Graph Cost Divide by Zero 2022
Finished
time limit per test: 2 seconds
memory limit per test: 256 megabytes Practice
input: standard input
output: standard output
You are given an initially empty undirected graph with n nodes, numbered from 1 to n (i. e. n
→ Virtual participation
nodes and 0 edges). You want to add m edges to the graph, so the graph won't contain any
self-loop or multiple edges.
→ Clone Contest to Mashup
If an edge connecting two nodes u and v is added, its weight must be equal to the greatest
common divisor of u and v, i. e. gcd(u, v) .
→ Submit?
In order to add edges to the graph, you can repeat the following process any number of times
(possibly zero):
Language: GNU G++20 13.2 (64 bit, winlibs)
choose an integer k ≥ 1; Choose
Choose File No file chosen
add exactly k edges to the graph, each having a weight equal to k + 1 . Adding these k file:
edges costs k + 1 in total. Submit
Note that you can't create self-loops or multiple edges. Also, if you can't add k edges of weight
k + 1 , you can't choose such k.
For example, if you can add 5 more edges to the graph of weight 6 , you may add them, and it
→ Contest materials
will cost 6 for the whole pack of 5 edges. But if you can only add 4 edges of weight 6 to the
Announcement (en)
graph, you can't perform this operation for k = 5.
Tutorial (en)
Given two integers n and m , find the minimum total cost to form a graph of n vertices and
exactly m edges using the operation above. If such a graph can't be constructed, output −1.
Note that the final graph may consist of several connected components.
Input
Each test contains multiple test cases. The first line contains the number of test cases t (
1 ≤ t ≤ 104 ). Description of the test cases follows.
The first line of each test case contains two integers n and m (2 ≤ n ≤ 106 ;
n(n−1)
1≤m≤ 2
).
6
It is guaranteed that the sum of n over all test cases does not exceed 10 .
Output
For each test case, print the minimum cost to build the graph, or −1 if you can't build such a
graph.
Example
input Copy
4
4 1
6 10
9 4
10 11
output Copy
2
-1
[Link] 1/2
5/22/24, 12:10 PM Problem - 1731E - Codeforces
7
21
Note
In the first test case, we can add an edge between the vertices 2 and 4 with gcd = 2 . This is
the only possible way to add 1 edge that will cost 2 .
In the second test case, there is no way to add 10 edges, so the answer is −1.
In the third test case, we can add the following edges:
k = 1: edge of weight 2 between vertices 2 and 4 (gcd(2, 4) = 2). Cost: 2;
k = 1: edge of weight 2 between vertices 4 and 6 (gcd(4, 6) = 2). Cost: 2;
k = 2: edges of weight 3: (3, 6) and (3, 9) (gcd(3, 6) = gcd(3, 9) = 3 ). Cost: 3.
As a result, we added 1 + 1 + 2 = 4 edges with total cost 2 + 2 + 3 = 7, which is the
minimal possible cost.
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: May/22/2024 12:06:42UTC+5 (l1).
Desktop version, switch to mobile version.
Privacy Policy
Supported by
[Link] 2/2