Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
Why wrong answer? | Ferro | 1138. Целочисленные проценты | 16 апр 2022 18:44 | 1 |
#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; } |
How to prove the "untill 100 percent" algorithm? | Incognito | 1138. Целочисленные проценты | 12 апр 2020 07:02 | 1 |
|
Random Test Cases | Aditya Singh | 1138. Целочисленные проценты | 19 июн 2019 08:04 | 2 |
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 |
It may be useful: (if You use Dynamic Programming), increasing percentage doesn't exceed 100% | Pasha | 1138. Целочисленные проценты | 11 май 2017 02:05 | 3 |
Simply use DP with Recurse and You'll get AC! 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 |
The data must be wrong! Please check it. | zhougelin | 1138. Целочисленные проценты | 9 апр 2015 02:38 | 5 |
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 :) |
hint for WA | Ade | 1138. Целочисленные проценты | 24 окт 2013 20:07 | 4 |
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 |
why the percentage is'nt exceed 100%? | hoan | 1138. Целочисленные проценты | 6 ноя 2010 22:04 | 1 |
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. |
Why my program get WA?I can't find the mistake. | Sarby Liang | 1138. Целочисленные проценты | 19 окт 2009 09:31 | 4 |
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 |
Please help me my algorithm is short and obvious but i don know why it get WA ??? | Saber | 1138. Целочисленные проценты | 25 июл 2009 19:56 | 2 |
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......" |
What's the hell wrong with this code???Many Thanks,Thanks,Thanks!!!! | coldplayfans | 1138. Целочисленные проценты | 3 окт 2008 18:32 | 1 |
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. |
My AC Code | Neptun | 1138. Целочисленные проценты | 26 окт 2007 08:56 | 1 |
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; } |
My AC Code | Neptun | 1138. Целочисленные проценты | 26 окт 2007 08:56 | 1 |
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 |
Is this test possible? | Diac Paul | 1138. Целочисленные проценты | 26 окт 2007 08:32 | 3 |
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!!! |
Something is wrong with the picture in the problem. | minkerui | 1138. Целочисленные проценты | 19 май 2004 14:53 | 3 |
You are to write out the longest sequence that satisfies to the problem statement. |
Help!Why I got WA!!!!!!!???????!!!!!!!!?????????? | Li Xun | 1138. Целочисленные проценты | 11 май 2004 21:02 | 3 |
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 |
Please anyone O(n) :( i did it N2 and got AC but i want O(n) | Locomotive | 1138. Целочисленные проценты | 29 апр 2003 02:29 | 5 |
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. |
Whats wrong with my short code ???can anybody help me ??? | Saber | 1138. Целочисленные проценты | 18 мар 2003 01:13 | 1 |
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. |
HELP!!! I always get "TIME EXCEEDED!" | turkeys | 1138. Целочисленные проценты | 14 фев 2003 13:59 | 3 |
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. |
help!what's wrong with my code?I always get WA | Destiny | 1138. Целочисленные проценты | 6 ноя 2002 12:36 | 1 |
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. |
Why do I get WA??? | ChuanLin | 1138. Целочисленные проценты | 3 сен 2002 15:33 | 1 |
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. |