問題一覧 > 通常問題

No.1495 パンの仕入れ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 16
作問者 : penguinmanpenguinman / テスター : akakimidoriakakimidori kaagekaage
2 ProblemId : 6189 / 出題時の順位表
問題文最終更新日: 2021-04-10 07:04:00

問題文

ペンギン学園の学長である penguinman は、生徒達のためにパンを幾つか仕入れ、購買部で売ることにしました。

仕入れられるパンは $N$ 種類あり、penguinman はその中からちょうど $K$ 個を仕入れて売ります。同じ種類のパンを幾つ仕入れても構いませんし、$1$ つも仕入れないパンがあっても良いです。

仕入れにあたって生徒達にアンケートを取ったところ、$M$ 個の回答が得られ、$i\ (1\leq i\leq M)$ 個目の回答は以下のものでした。

  • $x_i$ 種類目のパンをちょうど $y_i$ 個仕入れて欲しい。

penguinman は生徒達の要望に出来る限り答えたいです。$B_i$ を $i$ 種類目のパンの仕入れ数とした時、適切にパンを仕入れることで $\sum_{i=1}^{M} (B_{x_i}-y_i)^2$ を最小化してください。

$B_i$ はパンの仕入れ数であるため非負整数である必要があり、また先述の条件より $B_i$ の総和は $K$ になる必要があります。この問題の制約下では解は $10^{18}$ 以下に収まります。

$T$ 個のテストケースに答えてください。

入力

入力の $1$ 行目は以下の通りです。

\(T\)

続いて $T$ 個のテストケースが以下のフォーマットで順番に与えられます。

\(N\) \(M\) \(K\)
\(x_1\) \(y_1\)
\(x_2\) \(y_2\)
\(\vdots\)
\(x_M\) \(y_M\)

  • $1\leq T\leq 100$
  • $1\leq N,\ M\leq 2\times 10^5$
  • $1\leq K\leq 10^9$
  • $1\leq x_i\leq N$
  • $1\leq y_i\leq 10^9$
  • $M\times \max(K,\ \max(y))^2\leq 10^{18}$
  • $T$ 個のテストケース全体における $N,\ M$ の総和はそれぞれ $2\times 10^5$ を超えない
  • 入力は全て整数

出力

$T$ 行に渡って出力してください。$k$ 行目には $k$ 個目のテストケースにおける $\sum_{i=1}^{M} (B_{x_i}-y_i)^2$ の最小値を出力してください。

サンプル

サンプル1
入力
2
2 2 3
1 1
2 2
3 4 10
1 4
2 3
1 4
2 4
出力
0
1

$1$ つ目のテストケースでは、$B_1=1,\ B_2=2$ とするべきです。

$2$ つ目のテストケースでは、$B_1=4,\ B_2=3,\ B_3=3$ とするか、或いは $B_1=4,\ B_2=4,\ B_3=2$ とするべきです。

サンプル2
入力
3
5 8 93
2 11
3 80
3 58
1 78
4 8
4 71
1 39
2 30
6 10 56
5 31
1 48
6 8
2 24
4 75
2 83
5 80
5 31
4 60
2 63
6 10 480
5 74
3 64
5 40
3 52
2 98
2 83
2 5
6 53
6 41
2 88
出力
7659
17317
6216

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。