编程介的小学生 2017-08-07 07:39 采纳率: 20.5%
浏览 916
已采纳

Append

Description

Consider the following encoding scheme used in one famous compresion algorithm. Suppose we will code only sequences of lower case letters. Each such sequence of characters can be encoded to a sequence of pairs (pi, ri), where pi >= 0 is an integer and ri is either a character (if pi = 0) or an integer greater than zero and less or equal than pi (if pi > 0).
We describe now the decoding procedure for our encoding scheme. Let (p1, r1), (p2, r2), be a code of a sequence. We get the sequence as follows: we take successively individual pairs of the code. If pi = 0 then ri is a character and we simply add ri to the end of already decoded sequence. If pi > 0 then ri is an integer, 0 < ri <= pi, and we add to already decoded sequence ri letters from this sequence starting at the position pi places before the end.

For example, consider the sequence of pairs (0 a), (1, 1), (0, b), (3, 3), (3, 3), (3, 2), (0, c). Decoding (0, a) we get a. Decoding (1, 1) we get aa. (0, b) adds b getting aab. (3, 3) will add aab, so now we have aabaab. Next pair (3, 3) will again add aab so we have aabaabaab. (3, 2) will add aa, so our sequence is aabaabaabaa and (0, c) adds c. So the decoded sequence is aabaabaabaac. Note that in general for a given w it can exist more such sequences of pairs.

Let u, v be some sequences. By uv we will understand the sequence created by appending of the sequence v to the end of sequence u. Let Cw be a sequence of pairs which encodes a sequence of lowercase letters w. Suppose we have given a sequence of pairs Cw. The question is how many possibilities does exist for expressing the sequence Cw in the form CuCv where u, v are sequences satisfying the equation w = uv and neither u nor v is empty. Write a program that will answer this question.
Input

The input consists of blocks of lines. Each block describes one sequence of pairs Cw to some w in such a way that the i-th line of the block contains either two integers pi, ri, (ri <= pi < 1000) separated by one space or 0 followed by one space and one character. Each block ends with one empty line.
Output

The output contains the lines corresponding to the blocks in the input. Each line contains the number of possibilities of representation of the sequence Cw in the form Cu Cv where u, v are sequences satisfying the equation w = uv and neither u nor v is empty.
Sample Input

0 a
1 1
0 b
3 3
3 3
3 2
0 c
Sample Output

1

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-08-20 15:49
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗
  • ¥15 钢筋实图交点识别,机器视觉代码
  • ¥15 如何在Linux系统中,但是在window系统上idea里面可以正常运行?(相关搜索:jar包)
  • ¥50 400g qsfp 光模块iphy方案
  • ¥15 两块ADC0804用proteus仿真时,出现异常