|
|
please can anyone give me test #13? oh i found the test 9 000123000 --------- 123000000143 (my program) Got it. Never mind. It was simply a 12 digit input which is already prime. :) This problem is quite easy. Easier than a lot of problems with much less rated difficulty. WA7 3 000 -> 000000000002 WA10 0 -> 000000000002 do i misunderstand the meaning of this problem? 64631000033 is a prime,why it not the right answer of the sample? please help me!thanks! If 64631000033 is a prime, it's also good. You should output any, not necessarily minimal. As far as I understand the tasks the 12 digit number should be prime. Can it have leading zeros? Can the number 646310000033 be a corect output for the sample input? And how to format long long (was it "%I64" ?)? Rostislav Edited by author 19.02.2005 15:48 got AC +17... it SHOULD have leading zeros. L CAN be 0 digits CAN be separated by blanks. ALL IS MY IMHO The problem was in the formating (always forget that the compiler is differnt from my own). i have the same question as you,why is 64631000033 not the right answer,can you tell me,please? I just submitted the same code with: * G++ 4.7.2 C++11 (5626316) and got WA3 * Visual C++ 2010 (5626319) and got AC Can you please tell me what works wrong when compiling with G++? Thank you %lld works as %d when you use it in g++ in windows. You should use %I64d instead. Test #7 contain data as follows 11 00000000000 Answer is, for example 000000000003 (thank to Dmitry 'Diman_YES' Kovalioff ) Edited by author 02.03.2013 19:14 1) число может быть с ведущими нулями 2) выводить надо с ведущими нулями(если они есть) короче вот тест 1) 0 000000000002 2) 2 02 020000000089 I doubt there is another way to solve this problem, but to check random suffixes until the prime number is found. As for me, I just used precalc feature to find all the prime numbers less than 1000000, and then tested numbers using this list. My solution gets AC within 0.48 sec. How to check whether the number is prime or not faster? I don't think it is possible here. Miller-Rabin heuristics will obviously fail, because Int64 is not enough to store 24-digit number while modular exponentation. It might be passed, of course, but for what? :) Anyway, some tests for you: 0 923802054017 // 1 1 192380205401 // 12 192380205401 192380205401 // 11 92380205401 923802054017 // 11 00000000000 000000000005 - be careful, I doubt 000000000000 and 000000000001 are ok! // 10 0123456789 012345678923 My program will get TLE when L=12,but I suppose that my programs was to slow leads to TLE. Thank you very much. I used Miller-Rabin heuristics got AC...... You say Int64 is not enough to store 24-digit number Why you have to store 24-digit? In my pro,I think 19-digit is enough... There is a trick to avoid this situation......so one "mod" still take O(1) time...... If you are good at maths,it is not very hard to think out Good luck! There is a trick to avoid this situation......so one "mod" still take O(1) time...... I know how to mutiply integers up to 2^63 in O(log N) time: // multiply a and b modulo c typedef unsigned __int64 ull; ull Mul(ull a, ull b, ull c) { if (b == 0) return 0; if (b == 1) return a%c; ull d = Mul(a, b/2, c); d = (d+d)%c; if (b%2 == 1) d = (d+a)%c; return d; } But how to do it in O(1) time? Sorry,I didn't say it clearly...... calc a^n mod b certainly take at least O(logn) time... I meant that calc a*a mod b in O(1) time,although a may as large as 10^13-1,a*a>int64 ... so Miller-Rabin heuristics still work......just like in small cases...... 11 00000000000 000000000005 - be careful, I doubt 000000000000 and 000000000001 are ok! As I understand, 000000000000 is not right answer, but 000000000001 is right. Edited by author 16.07.2010 00:22 Edited by author 13.06.2012 16:36 the expect running time of my algo is O(100*lognlogn)... judge whether a prime for 100 times... In practise, it did run very fast,AC in 0.031sec... I used a simple idea: read N, put zeroes to fill up to 12 digits and then increase these new digits until N is prime... worked with __int64 from Visual C++ Excellent idea. I have used it and got AC. Another good test: 11 00000000001 Ans: 000000000011 Edited by author 15.05.2010 13:26 masalalarni ishlab charchamaylar can someone give me the test? or some hints ? now ok i got ac, i've forgotten to foreseee when n = 0; Try something like 2 00 or 3 001 ;) In russian wrong: "От ударов, щит разлетается на куски, ..." Right: "От ударов щит разлетается на куски, ..." funny Why it shouldn't? Numbers are _so_ small that "probable" prime turns into "exactly" prime. now it write Restricted function:) For several reasons the calls of nextProbablePrime and isProbablePrime functions leads to Restricted function verdict on Java 6 I got WA#10 on this: readln(n); readln(z); for i:=1 to 12-n do z:=z*10; repeat test; z:=z+1; until false; end. AND WHAT? I got AC on this: read(n); read(z); for i:=1 to 12-n do z:=z*10; repeat test; z:=z+1; until false; end. BUT! "В первой строке находится число уже ушедших Месяцев. Во второй — названные ими числа." So, in test 10 all numbers placed in first line? Or what?.. It's ANFAIR! ;) In Test #10 n=0 - that's why your programme returns WA Can the first number be zero? And if so what we should do then? write a new program and send again n = 0 in test #10, and don't forget write leading zeroes of your answer Edited by author 10.05.2008 22:27 If the input is 0 is 000000000003 correct answer ? it is interesting for this problem, that readln/writeln int64 in pascal always fails??!!?? writeln(int64) fails on case 7 readln(int64) fails on case 10. what kind of pascal compiler do you use?(along with version number) thank you very much I personally invite you (and everyone who is reading this message ;] ) and your team Shangri-La to participate in Timus Top Coders: First Challenge, see http://acm.timus.ru/contest.aspx?id=46 . there are three "shangri-la"s in the past since i have two different teammates each year, and.. i just found two members, i think they will come with me:) You can't use readln(int64) and writeln(int64) in this problem. It's your mistake. thanx safe bird but why i can't use readln(int64) and writeln(int64) in this problem? because of leading zeroes i know why writeln fails not. but... why do "readln(int64)" fail on it? isn't "001234" read as "1234" by readln? the C++ program that "read(int64)" gets AC but the Pascal program that "read(int64)" gets wrong answer on 10:( Edited by author 04.02.2006 23:55 to Safe Bird Var t:Int64; Begin ReadLn(t); WriteLn(T); ReadLn; End. Input 10^10 And What You See For Screen? On My Delphi7 i See 10^10 The first number seems to be 0 on test 10... |
|
|