P3417 [POI2005]BANK-Cash Dispenser

    • 98通过
    • 235提交
  • 题目提供者 codesonic
  • 评测方式 云端评测
  • 标签 POI 2005 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB


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

    推荐的相关题目 显示


    The BBB (short for Byteotian Bit Bank) owns the largest net of cash dispensers in Byteotia. The clients of the BBB can draw their money from the cash dispensers on the basis of a cash card and a 4-digit PIN code. Lately, in order to increase their clients' security, the BBB has had a camera installed by each cash dispenser. The cameras transmit the recorded image to the BBB using radio signals. Unfortunately, the signals are being intercepted by a gang of computer thieves. The thieves attempt to discover the 4-digit PIN codes of the BBB clients, whose cash cards they subsequently steal. Being aware of this fact, the BBB clients try to perform redundant movements over the keyboard while entering the PIN. The camera is not able to pick out the keystrokes, it only records the finger movements. Consequently, it is usually not possible to determine the PIN unambiguously. For instance, the client moving his finger over the key 1 and then over the key 5 could have entered the following PIN codes: 1111, 1115, 1155, 1555, 5555. Desperate thieves glean the camera recordings, counting on being able to determine the PIN of a client or at least limiting the number of possible codes on the basis of multiple recordings of his transactions. Having accumulated sequences entered by a particular wealthy client of the BBB, they made you an "unnegotiable proposition".

    TaskWrite a programme which:

    reads from the standard input a description of the recorded sequences of finger movements, which the client has performed whilst entering his PIN,determines the number of distinct PIN codes, which the client can have (i.e. the number of those 4-digit PIN codes, which could have been entered by performing the given finger movement sequences),writes the outcome to the standard output.

    BBB(Byteotian Bit Bank的缩写)拥有Byteotia最大的自动提款机网络。 BBB的客户可以根据现金卡和4位数的PIN码从自动柜员机中提取款项。最近,为了提高客户的安全性,BBB已经给每台自动提款机安装了相机。摄像机使用无线电信号将记录的图像发送到BBB。不幸的是,这些信号正被一群电脑盗贼拦截。盗贼试图发现BBB用户的4位PIN码,他们随后窃取了他们的现金卡。意识到这一事实,BBB用户尝试在输入PIN时执行键盘上的冗余动作。相机只能记录手指的动作。因此,通常不可能明确地确定PIN码。例如,用户将手指移动到键1上,然后移动到键5可以输入以下PIN码:1111,1115,1155,1555,5555。绝望的盗贼们收集相机记录,现在盗贼们给你一个手指移动序列,要求你确定用户可以具有的不同PIN码的数量。





    The first line of the standard input contains a single integer $n$ denoting the number of recorded scenes depicting the action of entering the PIN by the client, $1\le n\le 1\ 000$. In the following $n$ lines there are descriptions of these scenes, a single one per line. The description of each scene consists of two positive integers separated by a single space. The first of those numbers, $t$, denotes the length of the sequence of movements, $1\le t\le 10\ 000$. The other is a $t$-digit number, whose consecutive digits denote consecutive keys, over which the client has moved his finger. The total length of all sequences does not exceed $1\ 000\ 000$.

    标准输入的第一行包含一个整数n,表示用户输入PIN的动作数,$1\le n\le 1\ 000$。 在以下n行中,对这些动作进行了描述,每行描述一个动作。每个动作的描述由两个由单个空格分开的正整数组成。 这些数中的第一个数字t表示运动序列的长度,$1\le t\le 10\ 000$。另一个是一个t位的正整数,其连续的数字表示连续的键,表示用户移动他的手指到的目标。保证$\sum t\le 1\ 000\ 000$。


    The first and only line of the output should contain a single positive integer - the number of possible PIN codes of the client.



    输入样例#1: 复制
    3 123
    3 234
    输出样例#1: 复制