# 11012: 【原1012】增长率问题

### 题目描述

author: 刘勤 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1012

## Input Format

30%的数据，$$0 < S < T \leq 100$$ ；

100%的数据，$$0 < S < T \leq 200000$$。

## Sample Input

2 10


## Sample Output

5
2


## 样例解释

2 4 5 6 9以及2 4 5 8 10

## FineArtz's solution

/* 增长率问题 */
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

vector<int> CanInc[200005];
int len[200005] = {0};
long long tms[200005] = {0}, cnt[200005] = {0};
//f[i]表示以i结尾的最长序列长度，tms[i]表示以i结尾的最长序列的个数，cnt[i]表示长度为i的序列数

/*void PreTreatment(int s, int t){
for (int i = s; i != t; ++i)
for (int p = 1; p <= 99; ++p){
if (trunc(s * p * 0.01) == (s * p / 100))
CanInc[i].push_back(p);
}
}
*/
int main(){
int s, t;
cin >> s >> t;
for (int i = s; i <= t; ++i){
len[i] = 1;
tms[i] = 1;
}
cnt[1] = t - s + 1;
long long ans = 1;
for (int i = s; i < t; ++i){
for (int j = 1; j <= 100; ++j){
if (i * j % 100 == 0){
int next = i + i * j / 100;
if (next > t) continue;
if (len[next] == len[i] + 1){
tms[next] += tms[i];
}
else if (len[next] < len[i] + 1){
len[next] = len[i] + 1;
tms[next] = tms[i];
}
ans = (ans > len[next] ? ans : len[next]);
cnt[len[i] + 1] += tms[i];
}
}
}
cout << ans << endl;
cout << cnt[ans] << endl;
return 0;
}


## ligongzzz's solution

#include "iostream"
#include "cstring"
#include "cstdio"
using namespace std;

long long dp_data[500009] = { 0 };
long long cal_num[500009] = { 0 };

long long dp(long long num, long long T) {
if (dp_data[num] > 0)
return dp_data[num];
if (num > T) {
return 0;
}

long long ans = 0;
for (long long i = 1; i <= 100; ++i) {
if (num * i % 100 == 0) {
long long cur_ans = dp(num * i / 100 + num, T) + 1;
ans = cur_ans > ans ? cur_ans : ans;
}
}
for (long long i = 1; i <= 100; ++i) {
if (num * i % 100 == 0) {
if (dp_data[num + num * i / 100] + 1 == ans) {
cal_num[num] += cal_num[num + num * i / 100];
}
}
}
if (ans == 1)
cal_num[num] = 1;
dp_data[num] = ans;
return ans;
}

int main() {
long long S, T;
cin >> S >> T;

long long ans = 0;
for (long long i = S; i <= T; ++i) {
long long cur_ans = dp(i, T);
ans = cur_ans > ans ? cur_ans : ans;
}

long long cnt = 0;
for (long long i = S; i <= T; ++i) {
if (dp(i, T) == ans) {
cnt += cal_num[i];
}
}

cout << ans << endl << cnt;

return 0;
}


## yyong119's solution

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

const int maxn = 200007;
int d[maxn];
long long cnt[maxn], times[maxn];

int main() {

int s, t;
cin >> s >> t;
memset(cnt, 0, sizeof(cnt));
int tmp, ans = 1;
cnt[1] = t - s + 1;

for (int i = s; i <= t; ++i) d[i] = times[i] = 1;

for (int i = s; i <= t; ++i)
for (int j = 1; j <= 100; ++j)
if ((i*j)%100 == 0) {
tmp = i + i * j / 100;
if (tmp <= t) {
if(d[i] + 1 > d[tmp]) {
d[tmp] = d[i] + 1;
times[tmp] = times[i];
}
else if(d[i] + 1 == d[tmp]) times[tmp] += times[i];
ans = max(ans, d[tmp]);
cnt[d[i] + 1] += times[i];
}
}
cout << ans << endl << cnt[ans];
return 0;
}