In this HackerRank Minimum MST Graph problem solution you have Given n, m, and s for g graphs satisfying the conditions above, find and print the minimum sum of the lengths of all the edges in each graph on a new line.
Problem solution in Python.
g = int(input().strip()) for a0 in range(g): n, m, s = map(int, input().strip().split(' ')) n2 = (n * n - 3 * n + 4) // 2 if n == 2: print(s) else: if m <= n2: print(s + m - n + 1) else: a1 = n2 + (s - n + 2) * (m - n2 + 1) - 1 x = n - 1 - s % (n - 1) y = s % (n - 1) div = s // (n - 1) t = (x * (x + 1)) // 2 a2 = t * div a2 += max(0, (div + 1) * (m - t)) rem = s - (n - 2) * div kant = ((n - 2) * (n - 1)) // 2 a3 = kant * div + (m - kant) * rem print(min(a1, a2, a3))
Problem solution in Java.
import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.regex.*; public class Solution { private static long minimumWeight(long n, long m, long s) { if (m <= (n - 1)*(n - 2)/2 + 1) { return m + s - n + 1; } else { long core = (n - 1)*(n - 2)/2; long unbalanced = core + (s - n + 2)*(m - core); long base = s/(n - 1); long larger = s - base*(n - 1); long smaller = n - 1 - larger; long midbalanced = base*core + (base + larger)*(m - core); long balanced; if (larger > 0) { core = smaller*(smaller + 1)/2; balanced = base*core + (base + 1)*(m - core); } else { balanced = base*m; } return Math.min(Math.min(unbalanced, balanced), midbalanced); } } private static final Scanner scanner = new Scanner(System.in); public static void main(String[] args) { int g = scanner.nextInt(); scanner.skip("(rn|[nru2028u2029u0085])?"); for (int gItr = 0; gItr < g; gItr++) { String[] nms = scanner.nextLine().split(" "); int n = Integer.parseInt(nms[0]); long m = Long.parseLong(nms[1]); long s = Long.parseLong(nms[2]); System.out.println(String.format("%d", minimumWeight(n, m, s))); } scanner.close(); } }
Problem solution in C++.
#include <iostream> using namespace std; int main() { int tasknum; cin >> tasknum; while (tasknum--) { long long n, m, s; cin >> n >> m >> s; long long ans = 0; if ((n - 1) * (n - 2) / 2 + 1 >= m) { ans = s + m - n + 1; } else { if (-(n-2) * (m - (n - 1) * (n - 2)/2) + (n - 2) * (n - 1) / 2 < 0) { //average long long k = s / (n - 1); long long t = s % (n - 1); ans = (m - (n - 1) * (n - 2) / 2) * (s - (n - 2) * k) + (n - 2) * (n - 1) / 2 * k; if (t != 0) { ans = min(ans, (k + 1) * (m - (n - 1) * (n - 2) / 2) + (n - 1) * (n - 2) / 2 * k + (t - 1) * (2 * n - t - 2) / 2 ); } } else { ans = (m - (n - 1) * (n - 2) / 2) * (s - n + 2) + (n - 2) * (n - 1) / 2; } } cout << ans << endl; } return 0; }
Problem solution in C.
#include<stdio.h> //using namespace std; typedef long long ll; ll min(ll a,ll b) { if(a>b) return b; else return a; } void run() { ll N, M, S; scanf("%lld%lld%lld",&N,&M,&S); //cin >> N >> M >> S; ll blen = S - (N - 2); ll nedge = ((N - 1) * (N - 2)) / 2; ll ans=0; if (M > nedge) { ll bremain = M - nedge; if ((N - 1) * bremain < M) { ans = nedge + (M - nedge) * blen; } else { ll cval = S - (N - 1); ans = M + (M * (cval / (N - 1))); cval %= N - 1; ll lval = cval * bremain; ll rval = 1e18; if (cval) { rval = bremain + (cval - 1) * (N - 2) - (cval - 1) * (cval - 2) / 2; } ans += min (lval, rval); } } else { ans = (M - 1) + blen; } printf("%lldn",ans); // cout << ans << "n"; } int main() { int ntest,test; scanf("%d",&ntest); // cin >> ntest; for (test = 0; test < ntest; test++) run(); }