#Cg2. 循环赛冠军榜

循环赛冠军榜

循环赛冠军榜

题目描述

NN 支队伍参加单循环对抗赛。 每两支队伍之间都会恰好打一场比赛,每场比赛必定分出胜负,没有平局。胜者胜场数加 1,败者胜场数不变。比赛总场数为 N(N−1)2\frac{N(N-1)}{2} 场。

赛事主办方规定:只要一支队伍在整个循环赛中的胜场总数不少于 KK 场,这支队伍就能获得“荣誉优胜奖”。

主办方想知道极端竞争下的情况:在所有可能出现的比赛对局结果中,最多能有多少支队伍同时获得该荣誉?

输入格式

一行两个整数 NN 和 KK,分别表示队伍总数和获奖所需的最低胜场数。

输出格式

一行一个整数,表示最多能同时获奖的队伍数量。

样例

4 2
3
5 4
1
6 2
6

样例解释

  • 样例 1:4 支队伍总共打 6 场比赛。若有 4 队都想拿 2 胜,总胜场至少需要 4×2=8>64 \times 2 = 8 > 6,不可能实现;而前 3 队互相各赢 1 场且都打败第 4 队,则前 3 队各得 2 胜,第 4 队 0 胜。最多能有 3 队获奖。
  • 样例 2:5 支队伍每队总共只打 4 场比赛。若有 2 队获得 4 胜,意味着两队都要全胜,但它们之间的对决必有一负,矛盾!故最多只能有 1 队达成全胜。
  • 样例 3:6 支队伍平均每队胜 2.5 场,可以出现 3 队得 3 胜、3 队得 2 胜的情况。所有 6 支队伍胜场均不小于 2 场,故 6 队全员皆可获奖。

数据规模与提示

对于 100%100\% 的数据,满足 2≤N≤1092 \le N \le 10^9,0≤K≤1090 \le K \le 10^9。 提示:计算请使用 64 位整数。