|
|
this is a not correct setting task, there are many solutions some of them is AC some of WA, but all of them are right for N this is a right solution count is 2*(N - 2) and 2 2 3 3 4 4 .... (N-1) (N-1) isn't it ans.push_back(2); ans.push_back(2); for (int i = 2;;++i){ if (i == n){ ans.push_back(i); break; } ans.push_back(i+1); ans.push_back(i-1); ans.push_back(i); } WA3 if n==5 answer 12 2 2 3 1 2 4 2 3 5 3 4 5 Edited by author 14.02.2016 15:53 Edited by author 14.02.2016 15:53 Here's a simple program testing your answer. It outputs all the possible paths when the figure is still not found. You can modify constants in the header to test another one. program test1789; const nmoves = 12; nwidth = 5; mv: array[1..nmoves] of longint = (2, 2, 3, 1, 2, 4, 2, 3, 5, 3, 4, 5); var i: longint; path: array[0..nmoves] of longint; procedure Solve(v, z: longint); var q: longint; begin if (v < 1) or (v > nwidth) then exit; if z > nmoves then begin for q:=0 to nmoves do write(path[q], ' '); writeln; end else begin //if (v < 1) or (v > nwidth) then exit; if v = mv[z] then exit; path[z]:=v - 1; Solve(v - 1, z + 1); path[z]:=v + 1; Solve(v + 1, z + 1); end; end; begin for i:=1 to nwidth do begin path[0]:=i; Solve(i, 1); end; end. UPD: A small fix, moving one line into a proper place. Edited by author 14.02.2016 16:28 Just print: 1)2*n-1 2)1 2 ... n 3)n n-1 ... 2 It's work, but why? example 4 1 2 3 4 4 3 2 original 4->3->2->1->2->3->4 They don't meet They meet at the 6th point(3 = 3). Why do you need to print that 1 at the beginning? You don't need it. 2 3 4 4 3 2 also works fine. But 3 2 1 3 2 (or 2 3 4 2 3) is shorter. This problem seems hard but the algo is so simple. if there n pedestals then the m is always 2 * n - 1; if you just at i-pedestal and original is at jth, then 1. if abs(i - j) - even you can catch it if you just walk towards it just by one. 2. if abs(i - j) - odd then you just two times take the i-th pedestal to make the difference even and go to 1. For doing above algo just start from the 1st pedestal to n and take n again then go back to the 2nd pedestal Good luck Edited by author 17.10.2010 13:47 You say m is always 2 * (n-1) or is it (2*n) - 1 whichever it is, your initial logic doesn't even satisfy the given output for n = 3. By your above method m should either be 2 * (3-1) = 4 or (2*3) - 1 = 7 whichever formula you intended to say - none of them satisfy the given output i.e. for n = 3 , m = 2 my solution : for (i = 1; i<=n; i++) printf("%d ",i); for (i = n; i > 1; i--) printf("%d ",i); had ac... but it's wrong!! Должна ли быть найденная последовательность действий оптимальной? Да, уточните! Ведь если такая последовательность найдена, добавляя произвольное количество рандомных шагов сути задачи это не изменит. Но на АС это влияет. Your solution can make unnecessary steps 1) print (n-2)*2 2) print from 2 to n-1 3) if n is odd, print from 2 to n-1 again otherwise, print from n-1 downto 2 give me some hints please.. try to consider that initially the ojbect was at an odd (or even) place the algo is very easy. i spent 2 minutes solving this problem. try to find steps for n=3,4,5 without computer, using pen and sheet of paper. you will see the way) PS poor english, i know Just solve the problem for the case when the dodec. is on even place initially. Don't know why so many authors have posted 2*n-1.. That's obviously a wrong solution... Just think about if the stone is in the odd and the man touches the odd, things will be done smoothly. If to walk from 2nd pedestal toward (n-1)th pedestal and to touch dodecahedron on each pedestal twice? F.e.: n = 7 answer: 10 2 2 3 3 4 4 5 5 6 6 Can somebody give me an example demonstrating this way is wrong? For example, n = 4 2 2 3 3 won't work when the stone at 4 The final stone will be 4->3->2->1->2 for example Does the algorithm must have the minimal numbers of steps? Для конкретного постамента, направление, куда переместится с него этот несчастный артефакт, заранее зафиксировано или он может с одного и того же постамента в одном и том же сценарии и направо ходить, и налево по своему желанию? Видимо, по своему желанию может ходить за исключением 1-го и n-ого постамента Может ли артефакт сдвинуться влево, когда стоит на 1-ом месте. Т.е. сдвиги цикличны? нет, это видно из примера |
|
|