|
|
Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | Страница 1 | How to prove four cells is enough? | riparia | 1552. Brainfuck | 3 окт 2016 22:17 | 1 | | why wa on test 8 | tyomitch | 1552. Brainfuck | 3 сен 2013 22:27 | 2 | It's the first test where more than one memory cell needs to be modified. Do I miss something in the problem statement? E.g. is this test correct? azkazkazkazkazkazkazoazv ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +++++++++++++++++.+++++++++++++++++++++++++.<+++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>>+++++ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ++++++++++++.<.<.>>.<.<.>>.<.<.>>.<.<.>>.<.<.>>.<.<++++.>>.<.----. Try this test: azqhazqhazqhazqhazqhazqhazqhazqhazqhazqhazqhazqh My answer: +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++.<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.<+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>>>.<.<.<.>>>.<.<.<.>>>.<.<.<.>>>.<.<.<.>>>.<.<.<.>>>.<.<.<.>>>.<.<.<.>>>.<.<.<.>>>.<.<.<.>>>.<.<.<.>>>.<.<. | output | jagatsastry | 1552. Brainfuck | 3 дек 2007 23:13 | 2 | output jagatsastry 2 дек 2007 19:31 should the op for "aa" be +++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++.. and "aba" be +++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++++ ++++++++++++++++++++++++++++.<. no. Output of "aba" don't use two cells. You should use one. after you output 'a' do next: +.-. to output 'b' and return back to 'a'. Your task is to minimalize output length | why wa on test 30? | Cheryl | 1552. Brainfuck | 1 июл 2009 11:33 | 6 | I know! Victor Barinov (TNU) 25 сен 2007 16:19 my WA on test 30 was because, I forgot: "If the pointer before increment points to the rightmost byte of the array, then after increment it points to the leftmost byte." and "If the pointer before decrement points to the leftmost byte of the array, then after increment it points to the rightmost byte." In the statement it is said, that you may assume to use at most 4 bytes, but it is not said WHICH four bytes.. In the case of test 30, the best four are the rightmost one and the three leftmost. However, now I'm stuck on 31... Yes!Thank.But I resolved this situation in array[4] but moving initial position in second cell. | why wa on test 28 | stelan | 1552. Brainfuck | 16 дек 2011 04:28 | 7 | 4 memory or 30000 memory ? I have WA 28 Also. First 27 test I have passed with N=3 using Dejkstra. But N==4 means very many possible states 27*27*27*27*4*50 and unprocessing. optimal program use 4 or less cells It's evident that using 5 cells we will have better solution for rather long strings, but jury's programm can't work properly in this situation. Their hight level is 4 when they garantee right answer. I easy found Dejkstra's solution for N=3. But for N=4 I tried DP,BFS with absolutely bad characteristics. If solution depend on unproven statements which help diminish cardinality of set of possible states then it is unfair. It's possible to work with DP over 27*27*27*4*50 states for 4 modifiable cells. Yes, this uses some interesting assumption but it is provable. P.S: got AC Edited by author 14.07.2008 02:52 Edited by author 14.07.2008 03:54 Could you tell me what's your assumption? I think DP should be 27^4 * 4 * 50, and I assume that we just need modify 3 cells... so I got wa#28~ could anybody help me? sorry for my poor English. I think you can assume that cell with position 0 <= i < 4 already have needed char. | Clarification
| Yana | 1552. Brainfuck | 22 сен 2007 13:43 | 2 | You may assume that optimal program will not have to modify more than four memory cells. Does this mean that an optimal solution only uses 4 out of the 30000 given cells? If not, can someone clarify it? The statement is ambiguous. The input string contains only letters ('a'-'z') and the array of 30000 memory cells is full of 0. It seems that all the cells should be modified. Please clarify this. |
Страницы: 1 |
|
|