package DP;

import java.util.Scanner;

/**
 * @author dx
 * @version 1.0
 * @date 2022年5月14日 11:21
 * @description:剑指offer-46 把数字翻译成字符串
 *
 * dp[i]:表示前i个数字的翻译方法可能个数
 * num = X1X2X3....Xi-1Xi...Xn-1Xn
 * 例如:12258 = X1X2X3X4X5
 * 设 X1X2...Xi-2的翻译方案数量为f(i-2)
 * 设X1X2...X
 */

public class Translation {

 public static void main(String[] args) {
 Scanner sr = new Scanner(System.in);
 int num = sr.nextInt();
 System.out.println(new Tracnslation_Solution().translateNum(num));
 System.out.println(new Tracnslation_Solution().translateNum2(num));
 }
}

class Tracnslation_Solution{

 public int translateNum(int num){
 String s = String.valueOf(num); //int 转换成string
 //初始化 dp[-1] = 0
 int p = 0, q = 0, r = 1;
 for(int i = 0; i < s.length();i++){
 p = q; // q从上一轮的i-1,变为这一轮的i-2 --->p(i-2)
 q = r; //res为上一轮的i,赋值到这一轮的i-1 ---->q(i-1)
 r = 0; //r重置
 r += q; //r开始累计了,当前先加上i-1
 //下面开始尝试,是否要再累加 i-2
 if(i ==0){
 continue;
 }
 String sub = s.substring(i-1,i+1);//不包含i+1,也就是i-1 i
 if(sub.compareTo("25") <= 0 && sub.compareTo("10") >=0){
 r += p;
 }
 }
 return r;
 }
 public int translateNum2(int num){
 String s = String.valueOf(num);
 int n = s.length();
 int [] dp = new int[n+1];
 dp[0] = 1;
 for(int i =1;i<=n;i++){
 dp[i] = dp[i-1]; //单独翻译
 if(i>1){
 int t = (s.charAt(i-2) - '0')*10+s.charAt(i-1) - '0';
 if(t >=10 && t<=25){
 dp[i] += dp[i-2]; //将dp[i]和dp[i-1]组合翻译
 }
 }
 }
 return dp[n];
 }
}