| ENG RUS | Timus Online Judge |
Common BoardAresakaoni I don't understaind the algo [5] // Problem 1009. K-based Numbers 9 Sep 2006 00:45 please i don't understaind . a[0]=1; a[1]=(k-1); a[i]=(k-1)*(a[i-1]+a[i-2]); for n=2 and k = 10 the answer is 90 allright,but ,from my point of view for n=2 and k = 9 the right answer is 99 ,2 digits number 9 based, but the algo show 72 , I've AC but, is this the right algo?. sorry but my english is too bad . KIRILL Re: I don't understaind the algo [2] // Problem 1009. K-based Numbers 11 Sep 2006 23:47 a[2] = k*k-k This is all numbers from 10 to 88 (if k = 9 and n = 2) FireHeart Re: I don't understaind the algo [1] // Problem 1009. K-based Numbers 25 May 2007 06:56 not all, the number 19, 29, 39, 49 .. 79 is not allowed ! Peter Ivanov Re: I don't understaind the algo // Problem 1009. K-based Numbers 19 Jul 2007 03:08 FireHeart: you don't have the digit '9' when k=9 mathfrog Re: I don't understaind the algo [1] // Problem 1009. K-based Numbers 22 Aug 2007 21:41 that is a CLASSICAL math problem , i didnt realize it till i got 6 WAs. we fix the first number to be nonzero,and let f(n) be all the correct numbers . suppose the second digit is not zero ,we have f(n-1) correct ways. otherwise,we have f(n-2) ways. by addition law ,we have f(n)=(k-1)(f(n-1)+f(n-2)) . the idea is very classical and we should remember it all the time . Boyan Lazov Re: I don't understaind the algo // Problem 1009. K-based Numbers 22 Jul 2008 15:28 It is a classical combinatorial problem. You can solve it with the elegant recurrent relation, but figuring it out how to do it yourself is more valuable. I did it using some combinatoric (i.e.: the number we seek is sum of the K-based numbers with N digits who have exactly X zeroes (i.e. K-X free digits from 1..K-1) and don't have adjacent zeroes (sometimes this is zero, when X > N-X). If f(N,K,X) is this number, we seek sum(X=0 to N-1) f(N,K,X) (we can lower the upper bound X-1 but there's no need if you compute f properly) Edited by author 22.07.2008 15:30 DWED Hints for everyone [3] // Problem 1041. Nikifor 22 Jul 2008 00:43 Hi all. I tried to solve this problem many years ago and now returned to it with new knowledge and forces. Then i used pascal and now use Java. For others, who would try to solve this problem in java i has two hints. 1) Do not use long. Use int instead - or you get TL9. Prime number about 5-6k is ok since 6000^2*50<MAX_INTEGER 2) It is very strange, but creators of tests thought that it is smart enough to give you a 0-vector in 10-th test. It is totally incorrect to do so,... But it is proved that you can throw this vector away. ... Oh - one, more hint - 6000 is small enough to precalculate all reverse values and put them to source - about 40kb. Good luck. Questions to kluchnikovs on mail server mail.ru Edited by author 22.07.2008 00:50 Vedernikoff Sergey (HSE: EconomicsForever!) Re: Hints for everyone [2] // Problem 1041. Nikifor 22 Jul 2008 02:19 You've described very scary way of solving this problem (with 0-vectors and reverse values) =) All you need to do in this problem is Gaussian elimination. Well-realized by some large modulo, it'll give you right answers with high probability and without any precalculations and 0-vectors checkings (by the way, I don't understand why giving 0-vectors is incorrect if not forbidden by the problem statement?) DWED Re: Hints for everyone [1] // Problem 1041. Nikifor 22 Jul 2008 14:34 Indeed I used Gaussian elimination but with small modulo. But on first phase of solution, when i need to gather some basis I used "half-Gaussian" which considered permutation matrix -> so when I was looking for first non-zero vector element I got OutOfBoundsException. Reverse precalculation I used to reduce chances of second TLE (Java is times slow than c++/pascal). By the way. I've did some more thoughts experiments and found that my solution is incorrect, but tests are too weak to find that. For example for input: 6 3 6 0 0 3 0 0 0 5 0 0 2 0 0 0 4 0 0 1 6 5 4 3 2 1 My solution responds: 11 1 3 6 It is all because I throw away "bad" vectors on first stage which could get be in use in right solution. I suspect it can be not only in my solution, so TESTS MUST BE STRENGTHENED! Edited by author 22.07.2008 14:37 Edited by author 22.07.2008 14:37 DWED Re: Hints for everyone // Problem 1041. Nikifor 22 Jul 2008 15:26 Just a moment ago had rewritten my algo - now it doesn't use gaussian elimination at all, only Sherman-Morrison formula. So it need no permutation matrix, etc =) pperm Intresting problem, but very easy :) [6] // Problem 1568. Train Car Sorting 8 Oct 2007 15:09 Only 50 lines :) Pascal or C++ Re: Intresting problem, but very easy :) [4] // Problem 1568. Train Car Sorting 8 Oct 2007 18:05 Can you give me some ideas to solve this problem. I think about it very much. Thanks pperm Re: [3] // Problem 1568. Train Car Sorting 9 Oct 2007 22:12 n p1 p2 ... pn k p1 p2 ... pn ... c1 c2 ... cn-I find it in the first step of my algoritm)) 1 2 ... n My english is bad :) (RUS)Решать надо с конца вот и все :) maksay 2pperm [2] // Problem 1568. Train Car Sorting 4 Nov 2007 21:46 tip: Use translators if your English is bad tip for others: in English it sounds: It is neccesary to solve it from the end and thats all:) LX&R Bacherikov [KNU] Re: 2pperm [1] // Problem 1568. Train Car Sorting 3 Dec 2007 20:35 maksay wrote 4 November 2007 21:46 tip: Use translators if your English is bad tip for others: in English it sounds: It is neccesary to solve it from the end and thats all:) Wow, Maksay. You are so wise! Your tips are so brilliant! Everyone should idolize you! Denis Koshman Re: 2pperm // Problem 1568. Train Car Sorting 22 Jul 2008 13:41 tip: google.com has rus->eng translator in their language tools tip: idolize me too! :))) papayawing Re: Intresting problem, but very easy :) // Problem 1568. Train Car Sorting 28 Oct 2007 05:56 How to do it please? qwerty Admins, 12 test is INCORRECT (+) [3] // Problem 1029. Ministry 21 Jul 2008 17:19 In the description of this problem is written that "Each official collects a fee for signing a document. The fee is a positive integer not exceeding 10^9." But in 12 test there is '0'. I define that by that code and got TL. for(i = 0; i < m; i++) for(j = 0; j < n; j++) { scanf("%d", &a); if(a == 0) while(1); g[i][j] = a; } Please, Check tests or Correct description! Chmel_Tolstiy Re: Admins, 12 test is INCORRECT (+) [2] // Problem 1029. Ministry 21 Jul 2008 20:47 I think your code can get TL using wrong algorithm. is without this line you get WA? Sandro (USU) Re: Admins, 12 test is INCORRECT (+) [1] // Problem 1029. Ministry 21 Jul 2008 23:59 Right! 12 test and some others contain zeroes. Problem statement is corrected now. Chmel_Tolstiy Re: Admins, 12 test is INCORRECT (+) // Problem 1029. Ministry 22 Jul 2008 01:07 Oh, ok. 连连 why? // Problem 1091. Tmutarakan Exams 22 Jul 2008 00:42 Edited by author 22.07.2008 02:17 Soul Reaver Please help... [2] // Problem 1032. Find a Multiple 17 Mar 2007 00:19 Can the sample output be 4 1 2 3 4 ??? Edited by author 17.03.2007 00:19 Ilya Mitin Re: Please help... // Problem 1032. Find a Multiple 29 May 2008 18:01 I think 1 4 Kruglova Irka☺ Re: Please help... // Problem 1032. Find a Multiple 21 Jul 2008 16:31 (1+2+3+4)%5=10%5=0 So it can be. Why do I have WA12??? TestT Please give ans for test 10 [1] // Problem 1339. Babies 25 Feb 2005 06:10 20 0 1 0 0 0 5 0 0 8 0 10 0 12 0 0 0 0 0 0 0 0 0 2 0 4 0 6 7 0 0 0 11 0 0 0 0 0 0 0 0 107th Re: Please give ans for test 10 // Problem 1339. Babies 21 Jul 2008 10:44 1 3 2 5 4 7 6 9 8 11 10 13 12 14 15 16 17 18 19 20 WinAsAlways How I can read till the end in Java? [1] 18 Jul 2008 19:18 Please help me... I beginner in Java... Как читать данные до конца файла? WinAsAlways How I can read till the end in Java? 20 Jul 2008 19:43 Ну что всем трудно ответить?! ну кто пишет на Java скажите, как читать данные до конца? в ЧАВО написано, как делать это на паскале и на С...а Java обделили(((((( LittlePig Why WA #14 [4] // Problem 1587. Flying Pig 28 Oct 2007 13:50 Help me, please.. Thanks.. svr Re: Why WA #14 // Problem 1587. Flying Pig 29 Oct 2007 22:10 Because you passed 14 test with BigNum you is Ok therefore you have problem with logic of the task. In this situation simple but clever test may help and they easy to produce if having AC. Try the next: 15 1 -1 0 2 -2 0 3 -1 0 0 -3 -3 2 0 1 Ans=18 and this one: 11 -1 0 -1 0 -3 0 -1 0 0 0 -2 Ans=0 Edited by author 29.10.2007 22:39 Giorgi Saghinadze (Tbilisi SU) Re: Why WA #14 [2] // Problem 1587. Flying Pig 30 Oct 2007 15:42 I used big numbers only for printing answer. I like my solution :) Denis Koshman Re: Why WA #14 [1] // Problem 1587. Flying Pig 20 Jul 2008 19:25 Got WA14 too... But currently I use big numbers for temporary calculations. Denis Koshman Re: Why WA #14 // Problem 1587. Flying Pig 20 Jul 2008 19:36 Got AC. The problem was with long arithmetics. I wrote it modulo 10000, and it started overflowing after squaring because number of digits also must be taken into consideration. After reverting to modulo 1000, it worked fine. Try test with 50000 of 3s, check if you do not get negatives in the answer. Madhav assert function [2] // Problem 1587. Flying Pig 13 Jun 2008 04:49 assert function doesn't work here. for the program i used assert.it failed there was no response #include<iostream> #include<cassert> using namespace std; int main(){ assert(0==1); return 0; } the above program must result in a statement program aborted.But instead the program gives WA Vladimir Yakovlev (USU) Re: assert function [1] // Problem 1587. Flying Pig 13 Jun 2008 13:59 assert() function outputs a message and ends the program with nonzero return code. Of course, the Judge interprets such behaviour as wrong answer. Denis Koshman Re: assert function // Problem 1587. Flying Pig 20 Jul 2008 19:05 It is not "of course" becase other online judges (and real ACM contest servers) treat non-zero return as runtime error. I usually abort with #define FAIL *(int*)0 = 0 causes CRASH runtime error Dart MirzMan C++ Edition (Mirzoyan Alexey, Rybinsk SAAT) c++ must die, pascal forever (+) [7] // Problem 1591. Abstract Thinking 16 Nov 2007 01:55 It's enough the pascal's extended type to solve this problem. But the C++'s double type has only 15 digits :'( Edited by author 16.11.2007 01:58 Romko [Lviv NU] Re: c++ must die, pascal forever (+) [2] // Problem 1591. Abstract Thinking 18 Nov 2007 16:36 Use long double! AlexF [USTU Frogs] Re: c++ must die, pascal forever (+) // Problem 1591. Abstract Thinking 18 Nov 2007 17:40 I think it's enough int64 KIRILL(ArcSTUpid coder:) Re: c++ must die, pascal forever (+) // Problem 1591. Abstract Thinking 18 Nov 2007 18:29 I agree with topic), but i think it depends on compiler VS help says that long double equals to double and have 15 digits, but actually can store up to 18 strange.. Alias (Alexander Prudaev) Re: c++ must die, pascal forever (+) [3] // Problem 1591. Abstract Thinking 20 Nov 2007 09:57 Int64 is enougth Ivanov Alexander c++ must die, pascal forever (+) [2] // Problem 1591. Abstract Thinking 20 Nov 2007 16:34 Pascal - это наше всё... Desperados[KhAI] >> Starov_Lesha Re: c++ must die, pascal forever (+) [1] // Problem 1591. Abstract Thinking 8 Jul 2008 11:55 If you can't normaly solve the problem, just agree with it. C++ - the best! Pascal - already died. Denis Koshman Re: c++ must die, pascal forever (+) // Problem 1591. Abstract Thinking 20 Jul 2008 17:10 gcc has 10 bytes for long double while VC long double is 8 bytes long. Anyway, __int64 can hold up to 18 digits. And keep it unsigned :) bullshit Problem with reading or TLE #3 [2] // Problem 1007. Code Words 29 Feb 2008 01:44 got TLE#3. I'm confused. there's no cycles except reading data. Could anyone advice something? Faeton (Kyiv - Mohyla Academy) Re: Problem with reading or TLE #3 [1] // Problem 1007. Code Words 29 Feb 2008 01:45 The same problem. it's very intresting Nick Loginov (USU) Re: Problem with reading or TLE #3 // Problem 1007. Code Words 20 Jul 2008 16:08 I had the same problem, because I used too small size for each string (around 255 symbols), but term: N (4 ≤ N ≤ 1000) I got AC, when I change 255 on 2000 Edited by author 20.07.2008 16:08 Pavel Why error?Test number 3 [1] // Problem 1021. Sacrament of the Sum 25 Jun 2008 21:05 Code: var i,l,a,b,max,z,d:integer; otvet:string; x,y:array[1..50000]of integer; bo:boolean; begin bo:=true; readln(a); if (a>=1)and(a<=50000) then begin for i:=1 to a do begin readln(x[i]); end; readln(b); for i:=1 to b do begin readln(y[i]); end; if a>b then max:=a; if b>a then max:=b; for i:=1 to max do begin if bo=true then begin for l:=1 to max do begin z:=x[i]+y[l]; if z=10000 then begin d:=1; bo:=false; end; end; end; end; if d=1 then otvet:='YES' else otvet:='NO'; write(otvet); end; end. BECAUSE ERROR? Alexander Babenko Kyr-Rus Slav U Re: Why error?Test number 3 // Problem 1021. Sacrament of the Sum 20 Jul 2008 14:50 Because you are must use if a>=b then max:=a; if b>a then max:=b; EfremovAleksei What is test 10? WA!!! [8] // Problem 1527. Bad Roads 1 Mar 2007 22:25 Vedernikoff Sergey Re: What is test 10? WA!!! [4] // Problem 1527. Bad Roads 2 Mar 2007 11:58 There is definitely bug in checker. My correct solution gets WA #12, some other solutions with loops get WA #12, and got AC after deleting it (but my solution guarantees there is no loops). I think, we should wait while somebody will deign to fix this bug in checker. But such problems arise only with test #12. If you have WA #10, may be there is problem with your code... Kit Re: What is test 10? WA!!! [3] // Problem 1527. Bad Roads 2 Mar 2007 14:10 From your words I can conclude what though your solution doesn't output any loops, It has some other bugs :) Leave you mail, may be I can help you. Vedernikoff Sergey Re: What is test 10? WA!!! // Problem 1527. Bad Roads 2 Mar 2007 17:00 VedernikoffSM[at]mail[dot]ru Eldar Bogdanov Re: What is test 10? WA!!! [1] // Problem 1527. Bad Roads 18 Jul 2008 05:29 I also have WA12, I have submitted code which should produce a runtime error if there is a loop and it just WAd. Could anybody give me any clue? Eldar Bogdanov Test 12 problem // Problem 1527. Bad Roads 20 Jul 2008 12:59 Accepted. If anybody's interested, my mistake was stopping the Dijkstra when it came across an already found node. It could be that distance to T is even more but still acceptable. Edited by author 24.07.2008 16:29 svr Re: What is test 10? WA!!! [2] // Problem 1527. Bad Roads 28 Jul 2007 10:55 How did you understand specifics of test 10? Help, please. Denis Koshman Re: What is test 10? WA!!! [1] // Problem 1527. Bad Roads 13 Jul 2008 23:58 I had problems with WA#9 and WA#10 due to bugs in my code, nothing conceptual. My solution considers loops, but the way it selects path for the answer, it will never attempt to backtrace a loopy one. Edited by author 13.07.2008 23:58 107th Re: What is test 10? WA!!! // Problem 1527. Bad Roads 15 Jul 2008 18:04 If you have WA 10: "roads are unidirectional" means that roads are one-way )) Y.Y.M. I only use full search and I got AC in 0.015 sec. [3] // Problem 1042. Central Heating 6 Jun 2004 12:09 We can prove that nobody will turn the vales more than once, beacuse if so,he will do things with no effect so that the answer will not be the best one. So there are 2^N situations. I only use search with cut some "bad" answer and got AC. Sorry for my bad English... Tratata (barssimfi@mail.ru) Re: I only use full search and I got AC in 0.015 sec. // Problem 1042. Central Heating 16 Jun 2004 02:54 I also tried this method and got TLE. Can you give me your code? My e-mail is barssimfi@mail.ru ZhangXun Re: I only use full search and I got AC in 0.015 sec. // Problem 1042. Central Heating 14 Nov 2005 11:35 Could you paste your code here? Nickolas Kakà Re: I only use full search and I got AC in 0.015 sec. // Problem 1042. Central Heating 20 Jul 2008 10:03 What is "bad" in your opinion? Mesh BF to precalculate [1] // Problem 1009. K-based Numbers 1 Jul 2008 22:48 I think the easiest way is to precalculate trough Brute Force a table containing the values, hard-code it, and simply give back A[ n ][ k ] :D Plus, the solution will run fast as hell XD guana Re: BF to precalculate // Problem 1009. K-based Numbers 19 Jul 2008 23:00 You can do that with problems that have small values of n and k, but it'll run just as fast with a good algorithm. If you did it that way you have not actually solved the problem. penartur Can the variable hold a negative number? And other questions... // Problem 1438. Time Limit Exceeded 19 Jul 2008 22:52 As i understand from the problem description, all variables holds a UInt32 for a number and Bool for a sign, am i correct? Then, what should i do with: -- a = 1 b = /*2^32-1 here*/ c = a + b print c -- or -- a = 1 b = -1 c = a xor b print c -- ? guana Why WA #4? I'm about to give up. // Problem 1021. Sacrament of the Sum 19 Jul 2008 15:15 I tried to solving this by making an int array num1 where all the input numbers n are. Along it I made another int array num2 that has values 10000 - n. Then I checked if I can find numbers i,j where i!=j so that num1[i] == num2[j]. What's wrong? TestKiller Could someone help me on this? WA @ Test#32!!!!!! // Problem 1058. Chocolate 19 Jul 2008 09:03 Problem 1058 WA @ Test #32! I supposed it to be the problem of precision. But, I don't know why...... Could somebody help me, for example, give me a test? Thx a lot. TestKiller Could someone help me on this? WA @ Test#32!!!!!! 19 Jul 2008 09:02 Problem 1058 WA @ Test #32! I supposed it to be the problem of precision. But, I don't know why...... Could somebody help me, for example, give me a test? Thx a lot.
|