P1076 寻宝

    • 2.9K通过
    • 10.7K提交
  • 题目提供者 CCF_NOI
  • 评测方式 云端评测
  • 标签 概率论,统计 模拟 NOIp普及组 2012 高性能
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    传说很遥远的藏宝楼顶层藏着诱人的宝藏。小明历尽千辛万苦终于找到传说中的这个藏宝楼,藏宝楼的门口竖着一个木板,上面写有几个大字:寻宝说明书。说明书的内容如下:

    藏宝楼共有 $N+1$ 层,最上面一层是顶层,顶层有一个房间里面藏着宝藏。除了顶层外,藏宝楼另 $0$ 有 $N$ 层,每层 $M$ 个房间,这 $M$ 个房间围成一圈并按逆时针方向依次编号为 $0,…,M-1$ 。其中一些房间有通往上一层的楼梯,每层楼的楼梯设计可能不同。每个房间里有一个指示牌,指示牌上有一个数字 $x$ ,表示从这个房间开始按逆时针方向选择第 $x$ 个有楼梯的房间(假定该房间的编号为k),从该房间上楼,上楼后到达上一层的 $k$ 号房间。比如当前房间的指示牌上写着 $2$ ,则按逆时针方向开始尝试,找到第 $2$ 个有楼梯的房间,从该房间上楼。如果当前房间本身就有楼梯通向上层,该房间作为第一个有楼梯的房间。

    寻宝说明书的最后用红色大号字体写着:“寻宝须知:帮助你找到每层上楼房间的指示牌上的数字(即每层第一个进入的房间内指示牌上的数字)总和为打开宝箱的密钥”。

    请帮助小明算出这个打开宝箱的密钥。

    输入输出格式

    输入格式:

    第一行 $2$ 个整数 $N$ 和 $M$ ,之间用一个空格隔开。 $N$ 表示除了顶层外藏宝楼共 $N$ 层楼, $M$ 表示除顶层外每层楼有 $M$ 个房间。

    接下来 $N \times M$ 行,每行两个整数,之间用一个空格隔开,每行描述一个房间内的情况,其中第 $(i-1) \times M+j$ 行表示第 $i$ 层 $j-1$ 号房间的情况( $i=1,2,…, N$ ; $j=1,2,…,M$ )。第一个整数表示该房间是否有楼梯通往上一层( $0$ 表示没有, $1$ 表示有),第二个整数表示指示牌上的数字。注意,从 $j$ 号房间的楼梯爬到上一层到达的房间一定也是 $j$ 号房间。

    最后一行,一个整数,表示小明从藏宝楼底层的几号房间进入开始寻宝(注:房间编号从 $0$ 开始)。

    输出格式:

    一个整数,表示打开宝箱的密钥,这个数可能会很大,请输出对 $20123$ 取模的结果即可。

    输入输出样例

    输入样例#1: 复制
    2 3
    1 2
    0 3
    1 4
    0 1
    1 5
    1 2
    1
    
    输出样例#1: 复制
    5

    说明

    【数据范围】

    对于50%数据,有 $0<N≤1000,0<x≤10000$ ;
    对于100%数据,有 $0<N≤10000,0<M≤100,0<x≤1,000,000$ 。

    NOIP 2012 普及组 第二题

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。