| ENG RUS | Timus Online Judge |
Discussion of Problem 1231. Turing: One, Two, Three, …LSBG shortest solution [4] // Problem 1231. Turing: One, Two, Three, … 6 Apr 2008 23:23 I have the feeling that this problem can not be solved with less then 9*k+7 rows in the control table(my solution has exactly 9*k+7 rows) but I have not proven it. Has anybody a shorter solution? Edited by author 06.04.2008 23:24 Denis Koshman Re: shortest solution // Problem 1231. Turing: One, Two, Three, … 22 Jul 2008 16:19 It can be solved using O(log(n) + log(k)) rows. Do it like that: 1) put AA right before # to the left. This is 00 written base 26. 2) go right until you encounter -. Put + there and then go left until you hit #. Increase that number (it will become AB). Then go right again. 3) if you encounter # while walking right, go left and compute coordinate of last - mathematically using cells to the left as memory with base-26 2-digit arithmetics. For arbitrary k and n it will be more than 2 of course, that's why it's O(log(k)+log(n)), but not a constant. 4) like in case of 2 run right/left by putting - instead of + until result becomes zero (decrease it with every - set). 5) Find rightmost - and paint everything to the left with + 6) Find - and stop there Though, I heard in this forum that the checker is wrong as it stops when there are n-1 pluses, but not when invalid state/character pair is met. So, actually you will have to use O(n) states to calculate 'n' and then bring back this value to calculation area inside read/write head :) vgu 604 lines. [2] // Problem 1231. Turing: One, Two, Three, … 31 Oct 2010 00:28 My solution for each k output 604 lines. bsu.mmf.team Re: 604 lines. // Problem 1231. Turing: One, Two, Three, … 12 Dec 2010 19:11 How did you do this? My solution uses 1003 lines for each k, and I don't know how to optimize it :( Gilles Deleuze Re: 604 lines. // Problem 1231. Turing: One, Two, Three, … 13 Sep 2019 18:47 I also came up with 604 lines solution. Just go to the right incrementing the state (200 instructions), then output "X # something_related_to_josephus # <" for X in range [2, 201]. You've spent 400 states. Now your state number should have the information how many steps left you should make outputting '+' -- you will need 199 instructions for this. After that you'll have to add 5 more instructions JOSEPHUS_POINT - LEFT_MODE - < LEFT_MODE - LEFT_MODE + < LEFT_MODE # RIGHT_MODE # > RIGHT_MODE + RIGHT_MODE + > RIGHT_MODE - FINISH - = diablahaker2004 Can anyone check my solutions for k=2? (#WA2) // Problem 1231. Turing: One, Two, Three, … 25 Aug 2015 14:51 Hi, I have a solutions which work correct with all my example and I check answer with http://webspace.ship.edu/deensley/mathdl/Joseph.html but I got #WA2, can anyone help? this is sol for k = 2 2 42 1 - 402 - = 402 + 402 + > 402 - 403 - > 403 + 403 + > 403 - 404 - < 404 + 404 + < 404 - 101 - = 403 # 412 # < 412 + 412 + < 412 - 413 - < 413 - 422 - > 413 + 413 + < 422 + 422 + > 422 - 102 - > 413 # 432 # > 432 + 432 + > 432 - 502 - = 502 - 503 - = 402 # 452 # < 452 + 452 + < 452 - 453 - < 453 + 453 + < 453 - 950 - = 950 - 950 - < 950 + 950 + < 950 # 101 # > 453 # 462 # > 462 + 462 + > 462 - 502 - = 101 - 102 - > 101 + 101 + > 101 # 701 # < 701 - 701 - < 701 + 701 + < 701 # 101 # > 102 - 1102 + = 1102 + 402 + = 102 + 102 + > 102 # 702 # < 702 - 702 - < 702 + 702 + < 702 # 102 # > Maybe someone got AC and can help me? I can send my code, there 30 + 6*k rows Thanks anyway Fly [Yaroslavl_SU] My Turing Machine for you debugging [3] // Problem 1231. Turing: One, Two, Three, … 13 Oct 2005 09:52 http://www.fly33.hotmail.ru/download/Turing_Machine.zip Any question send to fly33@hotmail.ru Alex Tolstov (Vologda STU) Re: My Turing Machine for you debugging [1] // Problem 1231. Turing: One, Two, Three, … 1 Sep 2009 17:37 thanks! vgu Thanks! // Problem 1231. Turing: One, Two, Three, … 31 Oct 2010 00:26 It is very useful for debugging. Fly [Yaroslavl_SU] Re: My Turing Machine for you debugging // Problem 1231. Turing: One, Two, Three, … 19 Apr 2012 19:31 Alexander Fedulin Bug in your checker (+) [1] // Problem 1231. Turing: One, Two, Three, … 10 Sep 2009 19:55 My old solution used condition with negative numbers. Then i tried to change numbers to positive and got Accepted. Please check your ... something and rejudge! Edited by author 10.09.2009 20:10 Edited by author 10.09.2009 20:10 Vladimir Yakovlev (USU) Re: Bug in your checker (+) // Problem 1231. Turing: One, Two, Three, … 13 Sep 2009 03:21 The following limitation was added to the problem statement: The condition numbers may range from 1 to 30000. Fyodor Menshikov Admins, update statement or checher please // Problem 1231. Turing: One, Two, Three, … 27 Jul 2009 01:17 Current checker disallow replacing + to - while the statement allows it. Admins, please update either the statement or the checker. 198808xc If you don't know why you get WA...look at here. (ADMIN, too!) // Problem 1231. Turing: One, Two, Three, … 19 Oct 2008 08:33 One key word that is not mentioned clearly in the problem is that we can NOT place a "-" to the cell IF the cell is not "-" currently. This can make many programmes WA. For example, for n = 1, this code is NOT acceptable: 3 1 - 2 + > 2 # 2 # < 2 + 2 - = (Here we can NOT replace a "+" with a "-") while this one is acceptable: 4 1 - 2 - > 2 - 3 - < 2 # 4 # < 3 - 1 + > Hope the ADMIN to make it clear in the STATEMENT. This problem has driven me crazy for months!!! Good luck. TestKiller Admin : I really wanna to know what have you done!!! [1] // Problem 1231. Turing: One, Two, Three, … 26 Aug 2008 14:37 To see why I got WA, I try this code: if (k>1) { k=0; cout<<1/k<<endl; } else { cout<<0<<endl; return; } This program got WA !!!!!!! Can you explain it to me?????? Obviously Test#1 is k=1, and I got WA @ 2 Not CRASH, but WA!!! Admin, can I say that something had gone wrong?????? Hope to be replied soon. Vladimir Yakovlev (USU) Fixed (+) // Problem 1231. Turing: One, Two, Three, … 9 Sep 2008 03:51 Validator program has been fixed. Problem has been rejudged. 6 Authors lost AC. You now have WA#1. Thank you! Dmitry "Logam" Kobelev [TSOGU] need help! [2] // Problem 1231. Turing: One, Two, Three, … 18 Jul 2008 13:55 I always get wa1. I really dont't know why ( I used Fly's Turing Machine for debugging http://acm.timus.ru/forum/thread.aspx?space=1&num=1231&id=11941&upd=632647939365602435 and this site for checking Joseph http://webspace.ship.edu/deensley/mathdl/Joseph.html All tests I had imagined passed correctly. will someone be so kind and honest to have a look at my code?))) mail: logam@bk.ru icq: 282536626 Denis Koshman Re: need help! [1] // Problem 1231. Turing: One, Two, Three, … 22 Jul 2008 16:39 Besides bugs, I had WA1 because I forgot to put number of rows in the output :) Dmitry "Logam" Kobelev [TSOGU] still need help! // Problem 1231. Turing: One, Two, Three, … 25 Aug 2008 21:25 Unfortunetely, it's not the case( {AESC USU} Dembel Please Help Me! I have WA#1! // Problem 1231. Turing: One, Two, Three, … 13 Aug 2007 20:39 for k=2 this program is correct, isn't it? 38 1 - 1 - < 1 # 11 A > 2 + 2 + < 2 - 3 - > 2 A 4 A > 3 - 13 - = 3 + 3 + > 4 + 4 + > 4 - 5 - > 5 + 5 + > 5 - 6 - < 5 # 7 # < 6 + 6 + < 6 - 13 - = 7 + 7 + < 7 - 8 - < 8 + 8 + < 8 A 9 # > 9 + 9 + > 9 - 10 - = 11 - 2 - < 11 + 11 + > 11 # 12 # < 12 - 12 - < 12 + 12 + < 12 A 11 A > 13 + 13 + > 13 - 14 - > 13 # 15 # < 14 + 14 + > 14 - 11 + = 14 # 16 # < 15 - 15 - < 15 + 15 + < 15 A 13 A > 16 - 16 - < 16 + 16 + < 16 A 14 A > Yaroslavtsev Grigory This problem is really easy! (+) [1] // Problem 1231. Turing: One, Two, Three, … 16 Sep 2004 00:46 I don't understand why this problem has such difficult statistics (30 ACers and 10% of accepted), it is not so difficult, because I got accepted 1/1 and my friend Stupnikov Pavel too. svr Re: This problem is really easy! (+) // Problem 1231. Turing: One, Two, Three, … 2 Aug 2007 21:59 Agree! I have more than 1/1 but at last problem seems absolutely simple. Edited by author 02.08.2007 22:00 ACM.Tolstobrov_Anatoliy[Ivanovo SPU] question. [3] // Problem 1231. Turing: One, Two, Three, … 8 Jul 2006 23:00 First test k=1 This program correct? 3 1 - 1 + > 1 # 2 # < 2 + 2 - = Please explain what wrong. ACM.Tolstobrov_Anatoliy[Ivanovo SPU] Re: question. [2] // Problem 1231. Turing: One, Two, Three, … 10 Jul 2006 03:05 sorry but... NEW question This program correct for k=2 and n=2 ? 3 1 - 2 Q > 2 - 3 + < 3 Q 3 - = ACM.Tolstobrov_Anatoliy[Ivanovo SPU] Refresh [1] // Problem 1231. Turing: One, Two, Three, … 11 Jul 2006 03:22 Refresh Ilya Grebnov[Ivanovo SPU] Re: Refresh // Problem 1231. Turing: One, Two, Three, … 12 Jul 2006 03:09 Mail to me. I'l answer to your questions. Fly I must cross mines only each k-th or I can cross it in any order without last? [1] // Problem 1231. Turing: One, Two, Three, … 24 Oct 2004 22:33 Fly [Yaroslavl_SU] Re: I must cross mines only each k-th or I can cross it in any order without last? // Problem 1231. Turing: One, Two, Three, … 13 Oct 2005 09:53 In any order. Veselin Georgiev Interpreter // Problem 1231. Turing: One, Two, Three, … 7 May 2005 06:45 Btw I wrote a tiny interpreter, if anyone wants it, drop me an email (vessko_AT_SoftHome_d0t_net). The problem turns out to be rather easy once you get the abstract... Edited by author 07.05.2005 06:46 Maigo Akisame (maigoakisame@yahoo.com.cn) A few questions(+) [1] // Problem 1231. Turing: One, Two, Three, … 31 Oct 2004 03:55 1.The prob says we can only place '+','#','A'..'Z' on the tape. So can't we place '-'? But the sample output places '-'! 2.What's the range for condition? So I don't understand why my prog gets WA: program ural1231; const maxn=200; var remain:array[1..maxn]of byte; k,i:byte; begin read(k); remain[1]:=1; for i:=2 to maxn do begin remain[i]:=(remain[i-1]+k) mod i; if remain[i]=0 then remain[i]:=i; end; writeln('1 # 1 # >'); for i:=1 to maxn do writeln(i,' - ',i+1,' + >'); for i:=1 to maxn do writeln(i+1,' # ',1000+i-remain[i],' # <'); for i:=1 to maxn do writeln(1000+i,' + ',999+i,' + <'); writeln('1000 + 1000 - ='); end. Veselin Georgiev Re: A few questions(+) // Problem 1231. Turing: One, Two, Three, … 7 May 2005 06:43 1. I don't know why can't you place "-", but you needn't do it. 2. I believe -/+ MAXINT32. Mine solution used condition like 100001 3. Your prog doesn't output the number of lines of the control table. A New Start Can the "condition" be greater than 9? Can I use the "condition" 1..802? [1] // Problem 1231. Turing: One, Two, Three, … 12 Sep 2003 15:44 Stupnikov Pavel Yes // Problem 1231. Turing: One, Two, Three, … 9 Sep 2004 22:33 Yes, of course. I used 1..2004 and got AC. Lion Hi // Problem 1231. Turing: One, Two, Three, … 23 Aug 2003 11:58 ratrax21 the best solution is here !!!!!!!!!!!!!!!!!!! [1] // Problem 1231. Turing: One, Two, Three, … 17 Mar 2003 16:31 BAI DA PROST MAI ESTI! CвND pleci de-a casе iti iei scra cu tine??? ratrax21 Re: the best solution is here !!!!!!!!!!!!!!!!!!! // Problem 1231. Turing: One, Two, Three, … 17 Mar 2003 16:33 > BAI DA PROST MAI ESTI! > CвND pleci de-a casе iti iei scara cu tine??? > Lin Can anyone tell me if this output is right?(for k=2) [1] // Problem 1231. Turing: One, Two, Three, … 8 Dec 2002 07:58 38 1 - 2 A > 2 + 2 + > 2 # 3 # < 2 - 6 - = 3 + 3 + < 3 A 4 A < 3 - 6 - = 4 + 4 + < 4 # 5 # > 4 - 6 - = 5 + 5 + > 5 A 1000 - > 5 - 6 - = 6 + 6 + < 6 - 6 - < 6 # 7 # > 6 A 8 - = 7 + 7 + > 7 - 7 - > 7 A 8 - = 8 + 8 + > 8 # 9 # < 8 - 10 - > 9 + 9 + < 9 - 9 - < 9 # 8 # > 10 + 10 + > 10 # 11 # < 10 - 12 + > 11 + 11 + < 11 - 11 - < 11 # 10 # > 12 + 12 + > 12 # 13 # < 12 - 1 - = 13 + 13 + < 13 - 13 - < 13 # 12 # > Lin And can anybody send me a judge program?Thank you very // Problem 1231. Turing: One, Two, Three, … 8 Dec 2002 07:59 > 38 > 1 - 2 A > > 2 + 2 + > > 2 # 3 # < > 2 - 6 - = > 3 + 3 + < > 3 A 4 A < > 3 - 6 - = > 4 + 4 + < > 4 # 5 # > > 4 - 6 - = > 5 + 5 + > > 5 A 1000 - > > 5 - 6 - = > 6 + 6 + < > 6 - 6 - < > 6 # 7 # > > 6 A 8 - = > 7 + 7 + > > 7 - 7 - > > 7 A 8 - = > 8 + 8 + > > 8 # 9 # < > 8 - 10 - > > 9 + 9 + < > 9 - 9 - < > 9 # 8 # > > 10 + 10 + > > 10 # 11 # < > 10 - 12 + > > 11 + 11 + < > 11 - 11 - < > 11 # 10 # > > 12 + 12 + > > 12 # 13 # < > 12 - 1 - = > 13 + 13 + < > 13 - 13 - < > 13 # 12 # > WAZZAP Bug in a testing program form Rybinsk // Problem 1231. Turing: One, Two, Three, … 5 Dec 2002 20:29 There is such a bug The execution of your turing machine program stops when the machine emulator will encounter the only one minus remained uncrossed. This does not correspond to the problem text: "The work of the Turing machine is considered to be done if no line in the control table contains the combination of the current character and condition". because we're not explicitly required to implement the suggested brute force Josephus' problem algorithm. 2Admins: please, check this out and write clarifications if possibble. Dmitry 'Diman_YES' Kovalioff IMHO, sample output is wrong, because it works only for n=2. Is it right? [3] // Problem 1231. Turing: One, Two, Three, … 1 Dec 2002 16:32 Dmitry 'Diman_YES' Kovalioff Sample output is really wrong. Admins, check! [2] // Problem 1231. Turing: One, Two, Three, … 3 Dec 2002 13:02 > Leonid Volkov Re: Sample output is really wrong. Admins, check! [1] // Problem 1231. Turing: One, Two, Three, … 4 Dec 2002 10:56 Please read the problem carefully. It is stated in the condition, that the sample is really good only for N=2, so that's no surprise. In fact, to give a full solution in the sample, would be too much :-) Dmitry 'Diman_YES' Kovalioff Yes, my AC-solution gives very big output :) // Problem 1231. Turing: One, Two, Three, … 5 Dec 2002 15:13
|