Show all threads Hide all threads Show all messages Hide all messages |
Solved have a question about unsigned integer arithmetic in C/C++ | Mahilewets | 1528. Sequence | 28 Jun 2017 13:12 | 1 |
Why if I am trying to precalculate factorials using unsigned long long int there is WA#5? There are 64 last binary digits digits and in this task we are to output at most 32 binary digits. |
A fast algo? | ONU_1785 | 1528. Sequence | 2 Jan 2012 03:36 | 2 |
I got AC with 0.734s:
Who can tell some hints to make it work faster? Edited by author 08.05.2012 14:47 Edited by author 08.05.2012 14:47 You should minimize the number of mod operations. for example when I use mod each iteration i got 0.9 sec. But when I minimized the number of mod operations I got 0.56 sec. You should use long f(java) and calculate (f mod p) when f > 10^14, but not each time you calculate your f. |
So Fast Solution | M@STeR.SoBG | 1528. Sequence | 2 Jan 2012 03:34 | 3 |
How can i solve this problem with time < 1s?? My result is 1.8 s. Could anybody answer me?? The same question. I got AC in 1.7 sec, how to make it faster? Edited by author 01.07.2008 18:46 You should minimize the number of mod operations. for example when I use mod each iteration i got 0.9 sec. But when I minimized the number of mod operations I got 0.56 sec. You should use long f(java) and calculate (f mod p) when f > 10^14, but not each time you calculate your f. |
Accepted in java with only 1 sec....&786kb :-) | Varun Kumar(Fundu) | 1528. Sequence | 6 Jan 2011 11:35 | 2 |
Edited by author 23.10.2008 17:35 Edited by author 23.10.2008 17:35 I accepted in 0.75 sec and 188 KB in C++ |
if you don't know why the answer is n!%p | Megatron | 1528. Sequence | 17 Feb 2009 19:14 | 1 |
Calc g() first, you will find g(n)=n. And you can prove it by induction. Then f(n)=f(n-1)[1+g(n-1)], you will get f(n)=[1+g(1)][1+g(2)]...[1+g(n-1)]. f(n)=n! |
Why WA5? | [中山一中]Rabidstorm | 1528. Sequence | 26 Dec 2008 10:30 | 1 |
Why WA5? [中山一中]Rabidstorm 26 Dec 2008 10:30 program Ural1528; var p:array[1..10000]of qword; q,u,e:array[1..5000]of qword; ans:array[1..5000]of qword; m:qword; a,n,max,x,y:longint; procedure qsort(l,r:longint); var i,j:longint; mid,swap:qword; begin i:=l;j:=r;mid:=u[(i+j)div 2]; repeat while u[i]<mid do inc(i); while u[j]>mid do dec(j); if i<=j then begin swap:=u[i];u[i]:=u[j];u[j]:=swap; swap:=q[i];q[i]:=q[j];q[j]:=swap; swap:=e[i];e[i]:=e[j];e[j]:=swap; inc(i);dec(j); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j); end; procedure readdata; begin n:=0;max:=0; repeat readln(x,y); if (x=0)and(y=0) then exit; inc(n);inc(max); if x>=y then begin ans[n]:=0; dec(max); end else begin q[max]:=x;u[max]:=y;e[max]:=n; end; until (x=0)and(y=0); end; function gcd(o,z:qword):qword; begin if z=0 then exit(o) else exit(gcd(z,o-o div z*z)); end; procedure main; var i,j,mu:longint; o:qword; begin i:=1; j:=1; while i<=max do begin m:=1; mu:=0; o:=1; while (i<=max)and(trunc(ln(m)/ln(10))+trunc(ln(u[i])/ln(10))-trunc(ln(o)/ln(10))<=18)do begin m:=m div o; m:=m*u[i]; if mu<q[i] then mu:=q[i]; inc(i); if i<=max then if u[i]>m then o:=gcd(u[i],m) else o:=gcd(m,u[i]); end; p[1]:=1; for a:=2 to mu do p[a]:=p[a-1]*a mod m; for a:=j to i-1 do ans[e[a]]:=p[q[a]]mod u[a]; j:=i; end; end; procedure writedata; begin for a:=1 to n do writeln(ans[a]); end; begin readdata; qsort(1,max); main; writedata; end. Why WA5? I already get AC.But I want to make it faster, so Where is wrong? |
how to prove it? | FLYlemonsky | 1528. Sequence | 17 Dec 2008 19:00 | 2 |
|
why WA on test 7(!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!) | Petrosian Alexander | 1528. Sequence | 30 Jun 2008 16:30 | 6 |
[code deleted] Edited by moderator 04.02.2020 18:17 Use 64-bit type, like long long or __int64 (maybe with prefix unsigned) Edited by author 19.02.2007 13:49 Can someone give test examples, please? Edited by author 05.10.2007 13:17 I think that you're the DUNKEY!!!!!!!!!!!!! use __int64 instead of int |
Explanation | jagatsastry | 1528. Sequence | 11 Feb 2008 15:24 | 1 |
Can anyone tell me or give me a link as to how the answer to the question is n!%p I got TLE#11 when i submitted the following code [code deleted] Edited by author 11.02.2008 15:27 Edited by moderator 04.02.2020 18:20 |
terrible | Machvi | 1528. Sequence | 15 Dec 2007 21:50 | 7 |
I hate long numbers!!! I am begginer and I don't know them. so I have big problems. I wrote an algorithm but it doesn't work because f is very big!!! ---------------------------------------- I've made it!!! whithout long arithmetics Edited by author 18.02.2007 16:25 alforithm corect for that problem is not using strings :D My program takes only 15 lines :D My AC Program only takes 13 lines. There's no need to use "LONG" numbers Just this: [code deleted] Edited by moderator 04.02.2020 18:21 But what about p? And don't you have to use int64 type instead of longint? Answer, plz Я крыса которая съест тебя! 15 Dec 2007 21:50 is this test true? if yes then why i have WA2????? 10000 1999999999 0 0 1854601288 |
WA 5. What's the problem? | Roman Atangulov | 1528. Sequence | 7 Nov 2007 23:41 | 2 |
[code deleted] Edited by moderator 04.02.2020 18:22 Well, numbers can become more than p. Try to use int64. But I can't say exactly. Edited by author 07.11.2007 23:42 |
Output Limit Exceeded ? | wongiseng | 1528. Sequence | 31 Oct 2007 02:51 | 1 |
Can anyone enlighten me what causes this OLE ? I thought my code was harmless, and I am calculating n!%p. At least that's what I am trying to do. #include<stdio.h> int main(){ long long f,g,n,p; scanf("%lld %lld",&n,&p); while(n+p != 0){ [code deleted] printf("%lld\n",f); scanf("%lld %lld",&n,&p); } return 0; } Edited by moderator 04.02.2020 18:32 |
The problem 1528 is under investigation (+) | Sandro (USU) | 1528. Sequence | 13 Mar 2007 11:31 | 4 |
As you can see, actual number of testcases in this problem is much less than 10000. Many of you will get TL in the tests with 10000 testcases. New tests will be added soon and maybe TL for this problem will be increased. Write more effective solutions. :) Limitations were changed. Now all tests contain 5000 testcases or less. Timelimit was increased from 2 to 3 sec. You can see that correct Java solution can pass TL easily. By the way some new tests were added. 70 authors got TL and Crash. By the way, new tests still too weak... Solution, that works about 5 secs. on my tests (within limitations), passes all timus tests within 1.6 secs. I think, number of tetscases should be decreased down to 1000, and timelimit should be decreased to 2 secs... You can mail me your tests: sandro sobaka plotinka ru . |
WA 5 | ASKAR | 1528. Sequence | 18 Feb 2007 20:42 | 2 |
WA 5 ASKAR 18 Feb 2007 20:41 I got WA #5, who can explain me why??? thnks a lot :) -11 mod 10 = ? (-1 or 9) in this problem? |
some examples | RadekDembkowski | 1528. Sequence | 18 Feb 2007 18:13 | 2 |
pleas give some examples else than in the problem maybe 10 100000 9 1000000 Edited by author 18.02.2007 15:03 |