| Show all threads Hide all threads Show all messages Hide all messages |
| not correct task | Juve | 1789. Searching for the Dodecahedron | 3 Dec 2023 08:07 | 2 |
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 |
| why this algo is wrong | nomercy | 1789. Searching for the Dodecahedron | 14 Feb 2016 17:17 | 3 |
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 |
| It is very easy problem!!! | Tigran92[RAU] | 1789. Searching for the Dodecahedron | 10 Oct 2015 20:45 | 5 |
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. |
| Hint | Ibragim Atadjanov (Tashkent U of IT) | 1789. Searching for the Dodecahedron | 25 Sep 2014 12:58 | 2 |
Hint Ibragim Atadjanov (Tashkent U of IT) 17 Oct 2010 13:45 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 |
| Why my wrong solution got ac? | Ivan | 1789. Searching for the Dodecahedron | 19 Sep 2012 00:45 | 1 |
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!! |
| Уточните условие | CABALA | 1789. Searching for the Dodecahedron | 28 Mar 2012 00:45 | 3 |
Должна ли быть найденная последовательность действий оптимальной? Да, уточните! Ведь если такая последовательность найдена, добавляя произвольное количество рандомных шагов сути задачи это не изменит. Но на АС это влияет. Your solution can make unnecessary steps |
| Why this solution is wrong? | ucs6 | 1789. Searching for the Dodecahedron | 16 Sep 2011 05:50 | 1 |
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 |
| Can you give me idea or hints ? | Artyom | 1789. Searching for the Dodecahedron | 15 Sep 2011 04:49 | 5 |
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. |
| The real solution | Huang Da | 1789. Searching for the Dodecahedron | 27 Aug 2011 11:46 | 1 |
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. |
| why this solution is not right? | El_ka | 1789. Searching for the Dodecahedron | 17 Aug 2011 15:13 | 3 |
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 |
| Exx | [SESC USU] Efanov N. | 1789. Searching for the Dodecahedron | 14 Nov 2010 16:45 | 1 |
Exx [SESC USU] Efanov N. 14 Nov 2010 16:45 |
| Minimal step | KNU_Cyber | 1789. Searching for the Dodecahedron | 23 Oct 2010 17:39 | 2 |
Does the algorithm must have the minimal numbers of steps? |
| Передвижение | Tbilisi SU: Andrey Lutsenko | 1789. Searching for the Dodecahedron | 16 Oct 2010 15:03 | 2 |
Для конкретного постамента, направление, куда переместится с него этот несчастный артефакт, заранее зафиксировано или он может с одного и того же постамента в одном и том же сценарии и направо ходить, и налево по своему желанию? Видимо, по своему желанию может ходить за исключением 1-го и n-ого постамента |
| По условию | mastersobg | 1789. Searching for the Dodecahedron | 16 Oct 2010 14:36 | 2 |
Может ли артефакт сдвинуться влево, когда стоит на 1-ом месте. Т.е. сдвиги цикличны? нет, это видно из примера |
