[信息与未来 2017] 加强版密码锁

Luogu

IDLGB3734

Time1000ms

Memory128MB

DifficultyP4

动态规划 DP2017江苏信息与未来

乌龟偶然获得了一个宝箱，宝箱上又有一把密码锁。密码锁由 $n$ 个拨盘组成，每个拨盘初始时有一个 $0$ 到 $99$ 之间的整数。向上拨使数字 $x$ 变为 $(x+1) \bmod 100$，向下拨使数字 $x$ 变为 $(x+99) \bmod 100$。因为密码锁年久失修，拨盘拨动的次数越多越费力。如果一个拨盘被拨动 $k$ 次，需要花费 $k^2$ 单位时间。密码锁只有在所有的拨盘上的数字形成一个从左到右严格递增的数列时才会解开。乌龟再次请你帮忙，求解解开密码锁的最少时间。 --- 试题中使用的生成数列 $R$ 定义如下：整数 $0\leq R_1\lt 201701$ 在输入中给出。对于 $i\gt 1,R_i=(R_{i−1}\times 6807+2831)\bmod 201701$。 ## Input 两个整数 $n,R_1$，表示拨盘的数量和数列生成的首项。从左向右数第 $i(1\leq i\leq n)$ 个拨盘的初始数字为 $R_i \bmod 100$。 ## Output 一个整数，表示解开密码锁的最少时间。 [samples] ## Note $30\%$ 的数据满足 $n\leq3$，所有数据满足 $1\leq n\leq 100$。 >本题原始满分为 $20\text{pts}$。

Samples

Input #1

10 4

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[信息与未来 2017] 加强版密码锁",
    "description": {
      "content": "乌龟偶然获得了一个宝箱，宝箱上又有一把密码锁。密码锁由  $n$ 个拨盘组成，每个拨盘初始时有一个 $0$ 到 $99$ 之间的整数。向上拨使数字 $x$ 变为 $(x+1) \\bmod 100$， 向下拨使数字 $x$ 变为 $(x+99) \\bmod 100$。 因为密码锁年久失修，拨盘拨动的次数越多越费力。 如果一个拨盘被拨动 $k$ 次，需要花费 $k^2$ 单位时间。 密码锁只有在所",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3734"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "乌龟偶然获得了一个宝箱，宝箱上又有一把密码锁。密码锁由  $n$ 个拨盘组成，每个拨盘初始时有一个 $0$ 到\n$99$ 之间的整数。向上拨使数字 $x$ 变为 $(x+1) \\bmod 100$，\n向下拨使数字 $x$ 变为 $(x+99) \\bmod 100$。\n\n因为密码锁年久失修，拨盘拨动的次数越多越费力。\n如果一个拨盘被拨动 $k$ 次，需要花费 $k^2$ 单位时间。\n\n密码锁只有在所...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments