← 返回题目列表

AtCoder · gw2015_g

G. 金字塔 - 球体版

中文机器翻译题面 查看原题

問題文

伊织酱的最近兴趣是金字塔。

Iori-chan 的半径为 我有大量 1 球形石头,即 L \times (L+1) \times (L+2) / 6 件 顺时针或逆时针围绕 1 侧面是 L 我试图通过将它们排列成正四面体的形式来制作类似金字塔的东西。以便可以稳定地放置在办公桌上, 我正在尝试将它们排列在带有L \times (L+1) / 2 圆孔的木板上。然而,他在钻孔时犯了错误,有些孔无法放入石头。如果伊织按照排列正四面体的方式排列石头,她能放置多少颗石头?然而,“与将石头排列成正四面体时相同的方式排列石头”是指以下排列。

  • 将石头排列成规则的四面体图案时,从底部开始 i (1 ≦ i ≦ L) 一步,从后面 j (1 ≦ j ≦ L-i+1) 列,从左起 k (1 ≦ k ≦ j) 定位第二个棋子应该放置的位置。 我们称之为 (i,j,k) 。然而,从下面看 1 从后面的台阶 x (1 ≦ x ≦ L) 在栏中 我将其放置在 x 石头排成一排。
  • 首先从底部开始 1 在所有已成功钻孔且可以放置石子的行位置放置石子。
  • 从下面 2 从第一行开始 L 行位置 (i,j,k) ,位置 也位于 (i-1,j,k) 也位于 (i-1,j+1,k) 也位于 (i-1,j+1,k+1) 将棋子放在有棋子的位置,重复此操作,直到没有更多的地方可以放置棋子。 在

入力

输入是按以下格式从标准输入给出的。

L N
A_1 B_1
A_2 B_2
:
A_N B_N
  • 1 行中,2 整数 L (2 ≦ L ≦ 10^5), N (0 ≦ N ≦ Min(10^5, L \times (L+1) / 2)) 用空格分隔。这是 对于1 侧面是 L 石头计划排列成正四面体形状,破洞的位置是 这意味着有 N 。
  • 2 从线 N 行提供有关钻孔失败位置的信息。其中 给出了 i (1 ≦ i ≦ N) 行中,2 整数 A_i (1 ≦ A_i ≦ L), B_i (1 ≦ B_i ≦ A_i) 。这是从后面看 A_i 列,从左起 B_i 表示钻第二个孔失败。然而,同一位置的信息是 保证给予不超过 2 次。

部分点

针对此问题设置了部分分数。

  • N ≦ 20 的数据集 如果您正确回答 1 ,58 点。 如果您正确回答了所有满足
  • 如果所有测试用例都回答正确,将给予满分。

出力

八神酱放置的棋子数量 在 1 行输出。在输出末尾插入换行符。


入力例1

3 1
2 1

出力例1

6

位置 (1,1,1)、位置 (1,2,2)、位置 (1,3,1)、位置 (1,3,2)、位置 (1,3,3)、位置 (2,2,2) 可以得到第 6 您可以在该位置放置石头。


入力例2

100000 0

出力例2

166671666700000

这样,要小心,因为有可能你实际上并没有打孔失败。


入力例3

6 4
3 2
6 6
5 2
3 3

出力例3

25