Show all threads Hide all threads Show all messages Hide all messages | Some tests here | Georgiy Platonov | 1356. Something Easier | 19 Jun 2022 19:04 | 3 | Here are some test cases and my AC prog's answers 1000000000 999999929 71 999999000 999998981 19 999000999 3 5 999000991 405 3 5 397 101 101 1001 3 7 991 10001 5 23 9973 100001 3 7 99991 1000001 5 13 999983 10000001 3 7 9999991 100000001 5 7 99999989 555555555 3 11 555555541 191919191 5 23 191919163 838383838 838383779 59 123456789 5 23 123456761 987654321 987654319 2 987654319 987654319 101010101 3 19 101010079 Good luck Thanks for this testset, helped me find the bug :) The same, in a more reusable format: 18 1000000000 999999000 999000999 405 101 1001 10001 100001 1000001 10000001 100000001 555555555 191919191 838383838 123456789 987654321 987654319 101010101 71 999999929 19 999998981 3 5 999000991 3 5 397 101 3 7 991 3 31 9967 3 7 99991 3 19 999979 3 7 9999991 3 67 99999931 3 11 555555541 3 61 191919127 59 838383779 3 29 123456757 2 987654319 987654319 3 19 101010079 | hint | >>> | 1356. Something Easier | 1 Nov 2021 14:44 | 3 | hint >>> 1 Nov 2021 14:30 / Edited by author 01.11.2021 14:38 / Edited by author 01.11.2021 14:38 просто while() и проверка на prime() а насчет доказательства не знаю, но существует утверждение о том, что любое чётное число, начиная с 4, можно представить в виде суммы двух простых чисел. ( Проблема Гольдбаха ). Хотя пока она не доказана. Но В 1966 году Чэнь Цзинжунь доказал, что любое достаточно большое чётное число представимо или в виде суммы двух простых чисел, или же в виде суммы простого числа и полупростого | Hint.. | esger | 1356. Something Easier | 12 Jan 2019 19:52 | 4 | Be sure that(at least for the given interval, [4,2*10^9]) every even number can be shown as sum of two prime numbers. 1. if n is prime, {n} 2. if n is even, {n = p1 + p2} 3. if n is odd {n = 3 + p1 + p2} ( n-3 is even, so that recall second case.) For convenience, prime numbers under 10^5 can be initialized. Edited by author 03.12.2012 03:00 Edited by author 03.12.2012 03:00 Re: Hint.. Mishail [USU SESC division by zero masters] 21 Feb 2013 23:57 If he could proof it, he would get 1 thousand million dollar Edited by author 02.08.2015 20:59 > if n is odd {n = 3 + p1 + p2} ( n-3 is even, so that recall second case.) IMO this is wrong. 85 = 2 + 83 is the counter-case. > For convenience, prime numbers under 10^5 can be initialized. this way too big. :) Edited by author 12.01.2019 19:53 Edited by author 12.01.2019 19:54 | Give me some hint please; | Mishail [USU SESC division by zero masters] | 1356. Something Easier | 18 Dec 2013 00:13 | 2 | если число четное то его можно представить как сумму двух простых чисел, а если оно нечетно то либо как сумму 2 простых либо как 3 + (a + b), a, b - простые, как определить для нечетного числа надо 3 или 2 числа --- if the number is even then it can be written as the sum of two primes, and if it is odd then either as the sum of two simple or as 3 + (a + b), a, b - prime. How to determine the odd numbers must be 3 or 2 numbers? The sum of 2 odd numbers is always an odd number. To have 2 numbers sum up to an odd number, one needs an even number and an odd number. In this case, 2 + (n-2) (because 2 is the only even prime). Now, I'm stuck on how to solve the problem fast for even numbers | Who can give me a little hint ? | FBI | 1356. Something Easier | 24 Feb 2013 23:29 | 2 | Who can give me a little hint ? Test 10 has T=0, take care :) | More than one answer? | lancs | 1356. Something Easier | 25 Jan 2013 18:20 | 1 | Using Pascal I have got correct answers to samples and tests in the forum. There is more than one solution to some integers e.g. 27 = 19 3 5 and 23 2 2 Are we expected to provide one particular answer. I keep getting WA3 Thanks Please ignore: syntax error was the cause. Edited by author 26.01.2013 19:59 | Чем бы заменить решето? | Alexsander827 | 1356. Something Easier | 17 Oct 2012 01:04 | 1 | | If input is 1212131 , what is output? | FBI | 1356. Something Easier | 8 Aug 2012 15:18 | 2 | If input is 1212131 , what is output? My accepted program gives: 3 7 1212121 | How to solve this problem? (-) | Victor Barinov (TNU) | 1356. Something Easier | 12 Nov 2011 20:21 | 9 | During the contest I also didn't know how to solve it. I tried to submit dull solution: 1) 3 is enough. 2) The smallest prime number is not more than 500 3) The second prime number is not more than 50000 4) The biggest prime number is any. ...and I had AC. Just remember that any even number can be presented as sum of two prime numbers, and any odd - as sum of 3 prime numbers. P.S. As far as I know, this problem is known as Goldbach's Problem... Edited by author 20.03.2005 22:01 What about 21? - it is odd number, however it can be presented by 2 numbers 2 and 19!!! So, you idea is not right! The idea stands for a maximum of 3 primes in decomposition; obviously that for an already prime number, its decomposition has only one prime, i.e. itself. The Goldbach Conjecture, as I remember, stands that every even number >= 4 is decomposable into 2 primes Edited by author 21.03.2005 23:23 He said can be... witch means that the number of primes for any n is 1, 2 or 3. -if n is prime the answer is N -else if n is even the answer are two numbers ( hint one if them is very small ) -else if n is odd a) N can be presented as 2 and other prime number b) N can be presented as sum of 3 prime numbers. The answer is 3 and solve( N - 3 ) (n - 3 is even => it is presented by 2 prime numbers ) I hope this is helpful:) May i ask why the presume is right?? | eh | Ezio - Altair | 1356. Something Easier | 12 Jul 2010 13:02 | 1 | eh Ezio - Altair 12 Jul 2010 13:02 | Who can help me? I have WA8... | Someone | 1356. Something Easier | 13 Nov 2008 17:10 | 2 | Look at it. I think it is easy to understand this source: [code deleted :) ] You need only time to find bugs in programms. Good Luck! Edited by author 21.01.2006 03:52 i also have WA#8. here is my code: program z1356; {$APPTYPE CONSOLE} uses SysUtils; var n,k,c,i,j,t,p:longint; const mas :array [1..5133] of longint = ( 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71, 73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173, 179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281, 283,//etc :) last number 49999/// ); procedure init; begin {$IFNDEF ONLINE_JUDGE} assign(input,'input.txt'); reset(Input); assign(output,'output.txt'); rewrite(output); {$ENDIF} end; procedure print; begin {$IFNDEF ONLINE_JUDGE} close(input); close(output); {$ENDIF} halt(0); end; function simple(x:longint):boolean; var i:longint; begin result:=false; if x=1 then exit; if x=2 then begin result:=true; exit; end; for i:=2 to trunc(sqrt(x)) do if x mod i=0 then exit; result:=true; end; function canbe(x,k,st:longint):boolean; var i:longint; begin if (x=0) then result:=true else if (k=3) then begin if simple(x) then begin result:=true; write(x,' '); end else result:=false; end else begin canbe:=false; while mas[st]>x do dec(st); for i:=st downto 1 do begin result:=canbe(x-mas[i],k+1,st); if result then begin write(mas[i],' '); exit; end; end; end; end; procedure couldbe(t:longint); var i,k:longint; begin k:=5133; while mas[k]>t do dec(k); if mas[k]=t then write(mas[k]) else begin for i:=k downto 1 do if simple(t-mas[i]) then begin write(mas[i], ' ',t-mas[i]); exit; end; end; end; begin init; read(n); for i:=1 to n do begin read(t); if odd(t) then canbe(t,1,5133) else couldbe(t); writeln; end; print; end. | WA#2 | ABC | 1356. Something Easier | 2 Jan 2007 13:06 | 2 | WA#2 ABC 30 Dec 2006 20:21 Who knows what is test #2? Re: WA#2 [SSAU_#617]snipious aka Pimenov Sergey Nikolaevich 2 Jan 2007 13:06 Write me your code to snipious@mail.ru. I will try help you. Edited by author 02.01.2007 13:07 | Hint(+) | Виктор Крупко | 1356. Something Easier | 29 Jul 2006 13:39 | 3 | Hint(+) Виктор Крупко 4 Jun 2005 03:03 To take a file of 300 first simple numbers 1) To check up number 2) 2 number 300 fist simple numbers 3) 2 number 300 3 number 50 fist simple number ....and AC 133 kb and 0.46 c (bad english) simple number== prime number | How to really solve this problem? | Yuanming Yu | 1356. Something Easier | 20 Jun 2006 02:20 | 5 | Acoording to Goldbach's problem, a even number can write as two prime numbers' sum(when n is not quite big,it is absolutely true)...... And an odd number can write as 3 + 2x, so our task is to solve when n is even...... But how to solve it fast? I don't know. I make an assume that the smaller prime is less than 100000... I test some random number, it did produce an correct answer So just search for the smaller prime and test whether the other one is prime or not......You can got AC...... But I am not sure, maybe my assume is wrong... So, if some one can really solve it,say something. Thanks. Edited by author 29.03.2005 22:33 http://www.ieeta.pt/~tos/goldbach.html is worth seeing. They are investigating the Goldbach conjecture there. They say: Let n be an even number larger than two, and let n=p+q, with p and q prime numbers, p<=q, be a Goldbach partition of n. In order to verify the Goldbach conjecture for a given n, it is sufficient to find one of its Goldbach partitions. Our strategy will be to find the minimal Goldbach partition, i.e., the one that uses the smallest possible prime number p. They also say: So far, we have tested all consecutive even numbers up to 2·10^17, and double-checked our results up to 10^17. Some extra intervals were also tested. About 157.3 CPU years were used to do all this. At least 28.2% of the work necessary to reach 10^18 is already done. So, we may assume when solving this problem that the Goldbach conjecture is true. (It is because upper limit is only 10^9 which is much less than 10^17 :-). > But how to solve it fast? > I don't know. > Neither do I. But I tried looking through all even numbers 2..100 000 000 and finding minimal Goldbach partitions for them. The maximal p that I had used was 1093. More details: 2..100 000 000 -> maxP was 1093 2..10 000 000 -> maxP was 751 2..1 000 000 -> maxP was 523 2..100 000 -> maxP was 293 2..10 000 -> maxP was 173 2..1 000 -> maxP was 73 So, It doesn't seem to grow quickly... If I knew a suitable formula... I could have written a quicker solution. Anyway, I got AC ( http://acm.timus.ru/status.aspx?space=1&pos=867798). Details: 1356 Pascal Accepted 0.031 61 KB. Please post anything you know on this topic. Are there better ways to find Goldbach partitions? Or are there better ideas on solving this problem? Well, there are about n/lnn prime in 1 .. n,so when I choose the smaller prime in 1 to 100000, it can almost guarantee that the answer always exist. I send similar solution and it got AC in 0.015 sek. You idea is right! I used first two prime numbers less than 32000. Edited by author 20.06.2006 02:21 Special case: 6=3+3 but 9=2+7 not 9=3+3+3 | WA#13 | Zubyk Taras(Khmelnitsky) | 1356. Something Easier | 20 May 2006 16:01 | 1 | WA#13 Zubyk Taras(Khmelnitsky) 20 May 2006 16:01 I have WA#13. But I do not understand why. Can anyone help me? I will have written normal recursion. Give some tests or show me my mistake. Please help me. Thanks . P.S. Sorry, for my bad English. | why I got 'ACCESS_VIOLATION' | visitor | 1356. Something Easier | 11 Mar 2006 13:29 | 3 | Here's my program: program p1356; var fb:array[1..600000] of boolean; pn:array[1..60000] of longint; np,t,ii,n:longint; procedure init; var i,j:longint; begin np:=0; fillchar(fb,sizeof(fb),true); fb[1]:=false; for i:=2 to round(sqrt(600000)) do if not fb[i] then continue else begin inc(np); pn[np]:=i; for j:=2 to 600000 div i do fb[i*j]:=false; end; for i:=round(sqrt(600000)) to 600000 do if fb[i] then begin inc(np); pn[np]:=i; end; end; procedure main; var i,j,ij:longint; begin if fb[n] then begin writeln(n); exit; end; if not odd(n) then begin for i:=1 to np do if (pn[i]<n)and(fb[n-pn[i]]) then begin writeln(pn[i],' ',n-pn[i]); exit; end; end else begin for i:=1 to np do if pn[i]>n then break else if fb[n-pn[i]] then begin writeln(pn[i],' ',n-pn[i]); exit; end else begin for j:=1 to np do if n-pn[i]-pn[j]<0 then break else if not fb[n-pn[i]-pn[j]] then continue else begin writeln(pn[i],' ',pn[j],' ',n-pn[i]-pn[j]); exit; end; end; end; end; begin init; readln(t); if t=0 then halt; for ii:=1 to t do begin readln(n); main; end; end. [code deleted] Edited by moderator 11.03.2006 17:04 LOL (-) Michael Rybak (accepted@ukr.net) 11 Mar 2006 13:29 | What is wrong? Way WA on test 1? | ss | 1356. Something Easier | 29 Mar 2005 18:07 | 1 | |var t:longint; | x,i,a,b,c,len:longint; | ar:array[1..11000]of longint; | | |function simple(x:longint):boolean; |var i:integer; |begin | if x=1 then begin simple:=false; exit; end; | for i:=2 to trunc(sqrt(x))do | if x mod i =0 then begin | simple:=false; | exit | end; | simple:=true; |end; | |procedure razb(x:longint;var a,b,c:longint); |var i,j,k:longint; |begin | j:=1; | i:=1; | while (ar[i]<=x) and (i<=len) do begin | j:=i; | while (ar[j]<=x)and (j<=len) do begin | if x-ar[i]-ar[j]>=0 then | if simple(x-ar[i]-ar[j]) then begin | a:=ar[i]; | b:=ar[j]; | c:=x-ar[i]-ar[j]; | if(a=0) or(b=0) or(c=0) then begin | a:=ar[i]; | b:=ar[j]; | c:=x-ar[i]-ar[j]; | exit; | end | end; | inc(j); | end; | inc(i); | end; |end; | | |begin | t:=1; | for i:=2 to 100000 do | if simple(i) then begin | ar[t]:=i; | inc(t); | end; | len:=t; | readln(t); | for i:=1 to t do begin | readln(x); | if simple(x) then begin writeln(x); continue; end | else razb(x,a,b,c); | if a<>0 then write(a,' '); | if b<>0 then write(b,' '); | if c<>0 then writeln(c,' '); | end; |end. |
|
|