ばらばらコイン [yukicoder 994]

https://yukicoder.me/problems/no/994

解説

https://yukicoder.me/submissions/433013

N頂点に最大個数コインを置くとN枚になる。
これ以上コインがあった場合は1枚ずつにすることはできない。
よって、N<Kであれば答えは-1となる。

それ以外であれば、操作を行うことで実現可能。
実際の実現方法は聞かれておらず、最短回数だけ聞かれているが、
この答えはグラフの形によらず、K-1回となる。
理想状態にするには、K頂点にコインを置けばいいことになるが、
最初は1頂点にコインがあり、1操作につきコインがある頂点を1つ増やすことができる。
何枚コインを動かすかは、その先に置く頂点の枚数分動かせばよい。
よって、K-1頂点に対して新規でコインを置くので、必要な回数はK-1回であり、
これが最小回数である。

int N, K;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N - 1) {
        int a, b; cin >> a >> b;
    }

    if (N < K) cout << -1 << endl;
    else cout << K - 1 << endl;
}