logo AlgoBeat OnlineJudge
登录 注册

#214661. [RMI 2018] 松鼠 / Squirrel

内存限制:512 MiB 时间限制:9400 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

翻译来自于 LibreOJ

本题时限相较原时限翻倍。


题目译自 Romanian Master of Informatics 2018 Day2 T2 「Squirrel

你站在一个 的树林网格的左上角,坐标为 。一只松鼠在树间跳跃。作为一只计算机科学松鼠,它以特定的方式跳跃,形成了……树的分形图案!这些 分形图案如图所示:

:::align{center} :::

:::align{center} :::

松鼠遵循以下规则:

  • 松鼠从一棵指定的树开始跳跃。
  • 它首先向北跳跃 棵树,其中 是给定的 的幂。
  • 然后,它沿两条长度为 的对角线跳跃。
  • 接着,它形成四个大小为 的分形。
  • 这一过程持续进行,直到创建出大小为 的分形。
  • 图中展示了大小为 的前四个分形。

松鼠会持续跳跃,直到完成一个分形图案,然后开始下一个分形。你想知道在多少棵树上可以看到这只松鼠?

输入格式

第一行包含三个整数 ,分别表示树林网格的行数、列数和分形数量。接下来的 行描述 个分形,每行包含三个整数,表示起始树的坐标以及分形大小。

输出格式

输出一个整数,表示可以看到松鼠的树的位置数量。

样例

样例输入 1

14 20 3
11 10 4
7 6 2
8 7 2

样例输出 1

35

数据范围与提示

样例 1 解释

在样例中:

  • 树林网格有 列。
  • 松鼠跳跃三个分形,分别标记为黑色、红色和绿色。
  • 三角形标记分形的起点。
  • 圆圈标记从坐标 可见的树。
  • 较粗的圆圈标记松鼠多次跳跃的可见树。
  • 在可见树上的总跳跃次数为

:::align{center} :::

数据范围

对于所有输入数据,满足:

  • 如果你和松鼠所在树之间没有其他树阻挡,你可以看到松鼠。
  • 松鼠完成当前分形的所有跳跃后停止,然后开始下一个分形。
  • 松鼠永远不会跳到你的位置
  • 松鼠永远不会跳出树林网格。
  • 如果松鼠多次跳到同一棵可见的树上,该树将多次计入最终结果。
  • 分形大小 ,分形大小为 的幂
  • 总跳跃次数最多为

每个测试点将单独评分。

子任务 分值 附加限制
总跳跃次数最多为
总跳跃次数最多为
总跳跃次数最多为
无附加限制