#P1923. Fourier's Lines

Fourier's Lines

描述: 约瑟夫・傅里叶是一位伟大的数学家和物理学家,以其傅里叶级数而闻名。在他的19 19 个兄弟姐妹中,约瑟夫是最小且最聪明的。他在很小的时候就开始对数学表现出兴趣。长大后,他经常与奥塞尔大学的数学教授 C・博纳德通信。

在写给博纳德的一封信中,傅里叶提出了一个问题:如何在平面上画 1717 条线,使其恰好有101 101 个交点,且每个交点恰好属于两条线。显然,这是一个简单的问题,图 1 展示了一个满足他要求的解决方案。现在你面临的是一个更普遍的问题。我们能否在平面上画 NN 条线,使其恰好有 MM 个交点,且每个交点恰好属于两条线呢?如果可以,这些线最多能将平面分成多少部分呢? 输入: 输入可能有多组测试数据。每组数据占一行,包含两个整数NMN和M 1N1000M10000( 1≤N≤100 , 0≤M≤10000 ),它们之间用空格分隔。在测试数据之后有一行包含两个 0 的数据,这表示输入的结束,不应将其作为一组数据处理。

输出: 对于每组输入,按照以下格式输出一行:

情况 i : NN 条线无法恰好产生 MM 个交点。

如果画这些线是不可能的;

或者:

情况 i :恰好有 MM 个交点的 NN 条线最多能将平面分成 KK 部分。

注意:即使 NNMM 等于 11 ,在你的输出中也应该使用 “lines(线)” 和 “crossings(交点)” 这两个单词。

输入数据 1 : 4 3

4 6

4 2

5 11

17 101

0 0

输出数据 1 : 情况 1 :恰好有 3 个交点的 4 条线最多能将平面分成 8 部分。 情况 2 :恰好有 6 个交点的 4 条线最多能将平面分成 11 部分。 情况 3 : 4 条线无法恰好产生 2 个交点。 情况 4 : 5 条线无法恰好产生 11 个交点。 情况 5 :恰好有 101 个交点的 17 条线最多能将平面分成(这里你给的输出数据 1 中情况 5 未完整,推测是要写出最多分成的部分数,你可以补充完整需求后我进一步为你完善)部分 。