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 :)
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
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; 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.
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 :-)