#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, s;
    cin >> n >> s;

    vector<int> nums(n + 1, 1);

    for (int i = s; i <= n; i++)
    {
        for (int j = 101; j <= 200; j++)
        {
            if ((i * j) % 100 == 0 and (i * j) / 100 <= n)
            {
                nums[(i * j) / 100] = nums[(i * j) / 100] > nums[i] + 1 ? nums[(i * j) / 100] : nums[i] + 1;
            }
        }
    }

    cout << nums[n] << endl;

    return 0;
}

Try testcases
12 11
1
12 10
2
100 7
7
20 7
2
1000 1
26
10000 1
37
10000 13
25
100 25
8

Simply use DP with Recurse and You'll get AC!

I got WA3,a AC program getWA3, too.

the last salary may be less than what we thought.

input: 100 16
output: 10

if the last salary were 100, he got 9 jobs in all.
but in this case, the last salary is not 100. it's 99. So he has got 10 jobs.
try this and that's all clear

input: 99 16
output: 10

Edited by author 07.05.2011 20:39

I assume the percentage is'nt exceed 100% and i got AC, this is a rule of problem or in any way we can prove this???

sorry for my poor english.

program ural1138;
  var
    i,ans,n,s:integer;
    f:array[1..10000] of integer;

procedure dp;
  var i,j:integer;
  begin
    f[s]:=1;
    for i:=s to n-1 do
     for j:=1 to 100 do
      if ((i*j) mod 100=0)and(i+(i*j) div 100<=n)
       then if f[i]+1>f[i+(i*j) div 100]
       then f[i+(i*j) div 100]:=f[i]+1
  end;

begin
  readln(n,s);
  dp;
  ans:=0;
  for i:=n downto s do if f[i]>ans then ans:=f[i];
  writeln(ans)
end.

here is my prog :
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
const maxn=10000;
var
  n,i,j,s,k   : integer;
  a           : array[0..maxn] of integer;
begin
  readln(n,s);
  fillchar(a,sizeof(a),0);a[s]:=1;
  for i:=s+1 to n do
    for j:=s to i-1 do
      if (i-j)*100 mod j = 0 then
        begin
          if a[j]+1>a[i] then a[i]:=a[j]+1;
        end;
  k:=0;
  for i:=s to n do
    if a[i]>k then k:=a[i];
  writeln(k);
end.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SABER
ssf_digi@hotmail.com

Program ex;
Const
  Infile = 'ural1138.in';
  Outfile = 'ural1138.out';
Var
  n, m, i, j, Max, Max1, Ans: Integer;
  Temp: Real;
  Data: Array [1..10000] Of Integer;
Begin
  ReadLn(n, m);
  If (n < m) Then Begin
    WriteLn(0);
    Halt;
  End;
  Data[m] := 1;
  Ans := -1;
  For i:=m+1 To n Do Begin
    Max := -1;
    For j:=m To i-1 Do Begin
      Temp := Frac((i * 100) / j - 100);
      If (Temp = 0) Then Begin
        Max1 := Data[j] + 1;
        If (Max1 > Max) Then Max := Max1;
      End;
    End;
    Data[i] := Max;
    If (Data[i] > Ans) Then Ans := Data[i];
  End;
  WriteLn(Ans);
End.

It's nearly O(n) and it only uses 0.001 second.
As follows:


#include<stdio.h>
#include<string.h>
#include<math.h>
int n,s;
int f[100001];

int gcd(int a,int b)
{
       if(b==0)  return a;
       return gcd(b,a%b);
}

void work()
{
      int i,j,k,max=0;
      memset(f,0,sizeof(f));
      f[s]=1;
      for(i=s;i<=n;i++){
            if(f[i]){
                 if(i>100) k=gcd(i,100);
                 else k=gcd(100,i);
                 k=i/k;
                 for(j=k;j<=i&&i+j<=n;j+=k){//据说只要加到100%就可以了
                       if(f[i]+1>f[i+j])
                         f[i+j]=f[i]+1;
                 }
                if(f[i]>max)
                  max=f[i];
            }
      }
      printf("%d\n",max);
}
int main()
{
     int i;
     scanf("%d%d",&n,&s);
     work();
     return 0;

}

It's nearly O(n) and it only uses 0.001 second.
I'm sorry I didn't saw the rule...
"Messages should NOT contain source code (especially correct solutions). "

Fogive me //
A small hint : use the GCD..

Edited by author 26.10.2007 08:58

n=111 s=110
There is no sequence that that leads form 110 to 111. Is it possible such test? I got WA on test 2 and really don't know why. Are this correct?:
input
400 100
output
7
------
123 14
9
------
333 2
20
------
1000 67
11
------
5678 567
8
------
9800 100
22
------

   Thanks

var max:array[1..10000] of longint;
    s,d,e,x,j,i,n,m:longint;

function gcd(a,b:longint):longint;
  begin
    if a mod b=0 then gcd:=b else gcd:=gcd(b,a mod b)
  end;

begin
  fillchar(max,sizeof(max),0);
  read(n,s);
  if n<s then writeln(0) else begin
  max[s]:=1;
  for i:=s to n-1 do
    begin
      d:=gcd(i,100); e:=100 div d;
      for j:=1 to d do begin
        x:=i+i*j*e div 100;
        if (x<=n)and(max[x]<max[i]+1) then max[x]:=max[i]+1
      end;
    end;
  m:=1;
  for i:=s to n do if max[i]>m then m:=max[i];
  writeln(m)
  end
end.

const maxn=10000;
var
  n,i,j,s,k   : integer;
  a           : array[0..maxn] of integer;
begin
  readln(n,s);
  fillchar(a,sizeof(a),0);a[s]:=1;
  for i:=s+1 to n do
    for j:=s to i-1 do
      if (i-j)*100 mod j = 0 then
        begin
          if a[j]+1>a[i] then a[i]:=a[j]+1;
        end;
  k:=0;
  for i:=s to n do
    if a[i]>k then k:=a[i];
  writeln(k);
end.

program URAL1138;
const
    max=10000;
var
    opt:array[1..max] of integer;
    i,j,n,s,t:integer;
begin
    read(n,s);
    fillchar(opt,sizeof(opt),0);
    opt[s]:=1;
    for i:=s to n do
            if opt[i]<>0 then
                 for j:=i+1 to n do
                        if (opt[j]<opt[i]+1) and (j*100 mod i=0) then
                           opt[j]:=opt[i]+1;
    t:=0;
    for i:=s to n do if opt[i]>t then t:=opt[i];
    writeln(t);
end.

program integerp;
var
 n,s:longint;
 p:array[1..10000]of longint;
procedure init;
begin
 readln(n,s);
 if n<s then
  begin
   writeln('0');
   halt;
  end;
end;
procedure solve;
var
 i,j,max:longint;
begin
 fillchar(p,sizeof(p),0);
 p[s]:=1;
 for i:=s+1 to n do
  for j:=i-1 downto s do
   if (i*100 mod j=0) then
    if p[j]+1>p[i] then
      p[i]:=p[j]+1;
 max:=p[s];
 for i:=s+1 to n do
  if p[i]>max then
    max:=p[i];
 writeln(max);
end;
begin
 init;
 solve;
end.

var
 ok:array[1..10000]of longint;
 n,s,i,j,min:longint;
 nf,sf,max:longint;
begin
 fillchar(ok,sizeof(ok),0);
 readln(n,s);
 ok[s]:=1;max:=0;
 for i:=s to n-1 do
 begin
  if i*2>=n then min:=n else min:=i*2;
  for j:=i+1 to min do
   if (ok[i]+1>ok[j])and(j*100 mod i=0) then
    ok[j]:=ok[i]+1;
  if max<ok[i] then max:=ok[i];
 end;
 writeln(max);
end.