#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! Can you prove it? not to much to prove, suppose we have dp[x] where x is an integer number beetwen s and n, we calculate the numbers wich are integer percent of x. for example y is a number wich is an integer percent of x like(y = x*(50/100)), the reccurence is dp[x] = max(dp[x], dp[y] + 1) among all y which are integer percent I got WA3,a AC program getWA3, too. I think all ok. For all : be attantive with start values of array (not zero but -inf!!!) I think all ok. For all : be attantive with start values of array (not zero but -inf!!!) thank you very much! Hi PSV, thanks for the help in finding mistake in my program :) 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 tu n-ai ce face? stai cred ca stiu raspunsul....nu tu n-ai ce face? stai cred ca stiu raspunsul....nu, de ce? give us the mode you arrive from 16 to 100 in 10 increases, if possible and sorry for spam my friend is idiot(alex t) Edited by author 24.10.2013 20:10 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. add these: "if f[i]>0 then......" Thanks. I make a mistake here,too. many thanks, mistake here too 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 add these and get AC: "if a[j]>0 then......" 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 Latest salary (!) did not exceed n. It means that latest salary can be equal or less than n. Correct answers for your tests: 1) n = 111, s = 110 answer: 1 (110 - first and latest salary) 2) n = 400, s = 100 answer: 8 3) n = 123, s = 14 answer: 7 4) n = 333, s = 2 answer: 20 5) n = 1000, s = 67 answer: 7 6) n = 5678, s = 567 answer: 6 7) n = 9800, s = 100 answer: 23 Thank you very much!I had the same mistake.....How fooooool I was!!! > You are to write out the longest sequence that satisfies to the problem statement. 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. > 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. > Could you tell me why you got WA at first > Post your code so that I can help you. Thanks or email me personally to drghalib@yahoo.com You don't need to check all values which are less than the current value. You have to check only all percents from 1 to 100, for each value between s and n. 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. This way be useful: First, add a integer k in the Var Part. Second, change
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;
into:
if n>i*2 then k:=i*2 else k:=n; for j:=i+1 to k do if (opt[j]<opt[i]+1) and (j*100 mod i=0) then opt[j]:=opt[i]+1; I have used this way to get AC. program p1138; const maxn=10000; var c:array [1..maxn] of longint; ans,n,s,i,high,j:longint; begin read(n,s); fillchar(c,sizeof(c),0); c[s]:=1; for i:=s to n-1 do if c[i]>0 then begin if n>i+i then high:=i+i else high:=n; for j:=i+1 to high do if (c[i]+1>c[j]) and (j*100 mod i=0) then c[j]:=c[i]+1; end; ans:=0; for i:=s to n do if c[i]>ans then ans:=c[i]; writeln(ans); 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. |
|