Show all threads Hide all threads Show all messages Hide all messages |
shortest solution | LSBG | 1231. Turing: One, Two, Three, … | 13 Sep 2019 18:47 | 5 |
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 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 :) My solution for each k output 604 lines. How did you do this? My solution uses 1003 lines for each k, and I don't know how to optimize it :( 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 - = |
Can anyone check my solutions for k=2? (#WA2) | diablahaker2004 | 1231. Turing: One, Two, Three, … | 25 Aug 2015 14:51 | 1 |
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 |
My Turing Machine for you debugging | Fly [Yaroslavl_SU] | 1231. Turing: One, Two, Three, … | 19 Apr 2012 19:31 | 4 |
It is very useful for debugging. |
Bug in your checker (+) | Alexander Fedulin | 1231. Turing: One, Two, Three, … | 13 Sep 2009 03:21 | 2 |
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 The following limitation was added to the problem statement: The condition numbers may range from 1 to 30000. |
Admins, update statement or checher please | Fyodor Menshikov | 1231. Turing: One, Two, Three, … | 27 Jul 2009 01:17 | 1 |
Current checker disallow replacing + to - while the statement allows it. Admins, please update either the statement or the checker. |
If you don't know why you get WA...look at here. (ADMIN, too!) | 198808xc | 1231. Turing: One, Two, Three, … | 19 Oct 2008 08:33 | 1 |
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. |
Admin : I really wanna to know what have you done!!! | TestKiller | 1231. Turing: One, Two, Three, … | 9 Sep 2008 03:51 | 2 |
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. Fixed (+) Vladimir Yakovlev (USU) 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! |
need help! | Dmitry "Logam" Kobelev [TSOGU] | 1231. Turing: One, Two, Three, … | 25 Aug 2008 21:25 | 3 |
need help! Dmitry "Logam" Kobelev [TSOGU] 18 Jul 2008 13:55 Besides bugs, I had WA1 because I forgot to put number of rows in the output :) Unfortunetely, it's not the case( |
Please Help Me! I have WA#1! | {AESC USU} Dembel | 1231. Turing: One, Two, Three, … | 13 Aug 2007 20:39 | 1 |
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 > |
This problem is really easy! (+) | Yaroslavtsev Grigory | 1231. Turing: One, Two, Three, … | 2 Aug 2007 21:59 | 2 |
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. Agree! I have more than 1/1 but at last problem seems absolutely simple. Edited by author 02.08.2007 22:00 |
question. | ACM.Tolstobrov_Anatoliy[Ivanovo SPU] | 1231. Turing: One, Two, Three, … | 12 Jul 2006 03:09 | 4 |
question. ACM.Tolstobrov_Anatoliy[Ivanovo SPU] 8 Jul 2006 23:00 First test k=1 This program correct? 3 1 - 1 + > 1 # 2 # < 2 + 2 - = Please explain what wrong. Re: question. ACM.Tolstobrov_Anatoliy[Ivanovo SPU] 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 - = Refresh ACM.Tolstobrov_Anatoliy[Ivanovo SPU] 11 Jul 2006 03:22 Re: Refresh Ilya Grebnov[Ivanovo SPU] 12 Jul 2006 03:09 Mail to me. I'l answer to your questions. |
I must cross mines only each k-th or I can cross it in any order without last? | Fly | 1231. Turing: One, Two, Three, … | 13 Oct 2005 09:53 | 2 |
|
Interpreter | Veselin Georgiev | 1231. Turing: One, Two, Three, … | 7 May 2005 06:45 | 1 |
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 |
A few questions(+) | Maigo Akisame (maigoakisame@yahoo.com.cn) | 1231. Turing: One, Two, Three, … | 7 May 2005 06:43 | 2 |
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. 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. |
Can the "condition" be greater than 9? Can I use the "condition" 1..802? | A New Start | 1231. Turing: One, Two, Three, … | 9 Sep 2004 22:33 | 2 |
Yes Stupnikov Pavel 9 Sep 2004 22:33 Yes, of course. I used 1..2004 and got AC. |
Hi | Lion | 1231. Turing: One, Two, Three, … | 23 Aug 2003 11:58 | 1 |
Hi Lion 23 Aug 2003 11:58 |
the best solution is here !!!!!!!!!!!!!!!!!!! | ratrax21 | 1231. Turing: One, Two, Three, … | 17 Mar 2003 16:33 | 2 |
BAI DA PROST MAI ESTI! CвND pleci de-a casе iti iei scra cu tine???
> BAI DA PROST MAI ESTI! > CвND pleci de-a casе iti iei scara cu tine??? > |
Can anyone tell me if this output is right?(for k=2) | Lin | 1231. Turing: One, Two, Three, … | 8 Dec 2002 07:59 | 2 |
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 # > > 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 # > |
Bug in a testing program form Rybinsk | WAZZAP | 1231. Turing: One, Two, Three, … | 5 Dec 2002 20:29 | 1 |
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. |
IMHO, sample output is wrong, because it works only for n=2. Is it right? | Dmitry 'Diman_YES' Kovalioff | 1231. Turing: One, Two, Three, … | 5 Dec 2002 15:13 | 4 |
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 :-) |