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 - = 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 thanks! It is very useful for debugging. 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. Current checker disallow replacing + to - while the statement allows it. Admins, please update either the statement or the checker. 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. 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. Validator program has been fixed. Problem has been rejudged. 6 Authors lost AC. You now have WA#1. Thank you! Besides bugs, I had WA1 because I forgot to put number of rows in the output :) Unfortunetely, it's not the case( 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 > 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 First test k=1 This program correct? 3 1 - 1 + > 1 # 2 # < 2 + 2 - = Please explain what wrong. sorry but... NEW question This program correct for k=2 and n=2 ? 3 1 - 2 Q > 2 - 3 + < 3 Q 3 - = Refresh Mail to me. I'l answer to your questions. 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 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. Yes, of course. I used 1..2004 and got AC. 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??? > 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 # > 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. > 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 :-) |
|