Show all threads Hide all threads Show all messages Hide all messages |
Easy | InstouT94 | 1375. Bill Clevers | 12 Feb 2021 14:28 | 1 |
Easy InstouT94 12 Feb 2021 14:28 Easy solution with O(p) and without using a primality of p. We can build a table of square roots modulo p and then... |
O(p^2) works | buyolitsez`~ | 1375. Bill Clevers | 10 Aug 2020 11:52 | 1 |
0.046 - O(p) solution. 0.468 - O(p^2) solution, please add more tests. UPD: understood, that there is cant be NO SOLUTION. But you can enlarge p. Edited by author 10.08.2020 12:39 |
It is useful for you... | Adhambek | 1375. Bill Clevers | 26 May 2014 22:39 | 2 |
x^2 + y^2 = A * p + k; you use this simple algorithm: A = [0....p] and simple Check: first time : y = 0 and x = sqrt(A*p + k) if(x*x == A*p + k) you should Print this answer: x and y else second time: x = (int) sqrt(A*p + k) and y = sqrt(A*p + k - (int)x*x) if(x*x + y*y == A*p + k) you should Print this answer : x and y else continue and increasing only ONE count of A Sorry my English... Edited by author 04.01.2014 13:44 Edited by author 26.05.2014 22:39 |
'Prime or not?' && 'WA test 8' | Евгения | 1375. Bill Clevers | 25 Mar 2012 18:44 | 1 |
Does the checking system enter only prime number ('p')? Should I do a check of input data? And What is the distinction of test 8? I broke my head, trying to solve the WA! |
I have AC in (0.093) | Yusupov Azat(UB of TUIT) | 1375. Bill Clevers | 14 Oct 2010 10:45 | 1 |
while (true) { int d = (int)Math.sqrt(kk); if (d*d==kk) { System.out.println(0+" "+d); return; } else { long d3 = kk-d*d; int dd = (int)Math.sqrt(d3); if (dd*dd==d3) { System.out.println(dd+" "+d); return; } } kk += p; } |
WHY O(10^12) SOLUTION GET AC? | muhammad | 1375. Bill Clevers | 11 Jul 2010 12:42 | 1 |
I was crazy abt that prob. then submitted stupid brute force and got ac.why so? please somebody tell me how to get ac in .015 sec with simple programming. |
Weak time limit | Fyodor Menshikov | 1375. Bill Clevers | 22 Feb 2010 13:38 | 2 |
Upgrade of Timus test server happened on autumn 2008. I became several times faster, but very few time limits were changed. This problem is one that needs time limit to be lowered. Because with 1s TL and new servers some brute force solutions get AC - solutions that would never get AC on old testing server. I suggest TL=0.2s considering that some languages (Java and C#) need about 0.1s to start program. I became several times faster,... OMG :) I think, that good brute-force solution on С++ avoid TLE and after lowering TL (some authors write about it at forum ). So i think, that your suggest will be rejected. Edited by author 22.02.2010 13:46 |
Memory troubles? | 2rf | 1375. Bill Clevers | 7 Jun 2009 22:42 | 3 |
Well, i have problems with this problem) When I send C++ solutions with such declaration: int d[100000] I receive Crash (access violation) at test 8 as it should be. But when I change it to int d[1000000] I receive Crash (stack overflow) at test 1. Why? What is stack overflow? I use (or should I say don't use?) neither local variables nor recursion. Or maybe I just think so. Memory limit here is 16 MB and size of int d[1000000] is 4 MB, right? Help me please! UPD: I got AC by changing int d[1000000] to vector<int> d(1000000) but I still want to know answer to my question. Edited by author 07.06.2009 14:57 You have got Stack Overflow, because declared local array d[1000000] inside of main() function. Just declare it before main() and you will not have problems with stack. Big thanks for such quick and helpful response! |
Misspelled problem name | Fyodor Menshikov | 1375. Bill Clevers | 19 Mar 2009 11:59 | 2 |
In Russian, the name of the problem is noncomformizm, it should be nonco_n_formizm. |
Is there a faster solution than O(N)?(-) | SPIRiT | 1375. Bill Clevers | 31 Oct 2008 21:01 | 4 |
Probably yes because O(N) solution doesn't use primality of 'p'. Probably yes because O(N) solution doesn't use primality of 'p'. My O(N) solution uses primality of 'p'. Yes. If you can sols the equation x*x = c (mod p) faster then O(P) |
Problem 1375 "Bill Clevers". New tests were added (+) | Sandro (USU) | 1375. Bill Clevers | 29 Oct 2008 02:41 | 4 |
About 100 authors got WA, TL and Crash. If you still have AC with time 0.5 sec or more, try to find very simple and fast solution of this problem. I have AC of 0.123, but my algo is almost brute-force. My algo is pure brute-force. Nevertheless, AC 0.015 even after rejudge... 0.046 nontrivial bruteforce |
2admins: TLE? | Experimenter | 1375. Bill Clevers | 30 Sep 2008 19:51 | 1 |
why this prog ac? i think u must add maxtest #include <iostream> #include <stdio.h> #include <math.h> using namespace std; int main() { int k,p,x,y; cin >> k >> p; for(int x=0; x<p; x++)for(int y=0; y<=x; y++)if((x*x+y*y)%p==k) { cout << x << " " << y; return 0; } return 0; } |
admins - simple mistake | Tural Neymanov | 1375. Bill Clevers | 5 Aug 2008 15:02 | 1 |
Number p is a prime number, 2 ≤ p ≤ 1000000; 0 ≤ k ≤ p−1. p cannot be 1000000 |
why I have WA#10? | test_programs | 1375. Bill Clevers | 1 Apr 2007 19:50 | 3 |
part of my program: ... for x:=0 to p-1 do for y:=0 to p-1 do if f(x,y,p)=(k mod p) then begin writeln(x,' ',y); halt(0); end; writeln('NO SOLUTION'); end. {-----------------------------------} f(x,y,p) = ( x^2 + y^2 ) mod p x can be 10^5 so x^2 can be 10^10... (you can't store it in longint) Don't you have any overflows? Yes in this stupid problem only one problem is overflows just use in64 and I'll have AC without even TL |
WA#5 | khanh45a3kct | 1375. Bill Clevers | 11 Mar 2007 08:53 | 1 |
WA#5 khanh45a3kct 11 Mar 2007 08:53 Give me this test plz I think my alg is not incorrect |
Uncorrect | Alexander Kouprin | 1375. Bill Clevers | 10 Mar 2007 01:56 | 3 |
Uncorrect Alexander Kouprin 10 Mar 2007 01:50 I get AC, but I can't undestand this... var k,p,x,y:int64; begin k:=1; p:=3; x:=0; y:=2; // Like a test #0 (sample) if (x*x+y*y)=k mod p then writeln('correct test') else writeln('uncorrect test'); // x^2+y^2=k(mod p) end. So, anybody can tell me, why sample test is "uncorrect"? Because here can be many correct test, for example 0 1, 2 3 etc. So 1-st test is correct (0^2 + 2^2)mod 3 = 1(mod 3) x^2+y^2 = k (mod p) mean in mathematics that (x^2 + y^2) mod p = k mod p |
In fact,solution always exist.And brute force can AC in 0.015sec | Yu Yuanming | 1375. Bill Clevers | 15 Jan 2007 00:39 | 4 |
115564 1000000 and what about this test? my AC program: NO SOLUTION .....????!!! P must be prime, so your test is incorrect. |
Maybe something wrong? | ftc | 1375. Bill Clevers | 16 Oct 2006 23:55 | 1 |
I wrote solution that uses enumeration and got WA#5. Then, I wrote bruteforce algo and got AC. And then i added checking to solution with enumeration, so it will generate Runtime Error instead of outputting NO SOLUTION or when resulting pair is incorrect. But it was still WA#5. 2Jury: maybe something wrong with checker? I hope you'll check it. Thanks. |
WA#10 (without overflow). Help. | Alex Stoff | 1375. Bill Clevers | 11 Oct 2005 23:04 | 4 |
For x:=0 to p-1 do For y:=0 to p-1 do Begin t1:=x*x; t2:=y*y; If (t1+t2) mod p=k mod p then ... Before, t1,t2:int64. There is no Overflow and no TLE. Help, If you can. Thanks a lot. Send me you code maybe I help you. tolik-tol@inbox.ru oh i find. t1:=x*x it is overflov but t1:=x; t1:=t1*x; not overflow. or t1:=sqr(x) too not overflow. sqr=64bit x*x=32bits but i think you got TLE. good luck. Thanks a lot! I've got AC. I'll take it in! |
WoW AC on 11 lines. | Tolstobrov_Anatoliy[Ivanovo SPU] | 1375. Bill Clevers | 15 Sep 2005 01:37 | 2 |
Now on 10 lines and working 2 times better when last version. begin not use NO SOLUTION alveys you can find x and y; good luck; end. |