ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1231. Turing: One, Two, Three, …

shortest solution
Posted by LSBG 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
Re: shortest solution
Posted by Denis Koshman 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 :)
604 lines.
Posted by vgu 31 Oct 2010 00:28
My solution for each k output 604 lines.
Re: 604 lines.
Posted by bsu.mmf.team 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 :(
Re: 604 lines.
Posted by Gilles Deleuze 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