|
|
Можете дать подсказку? Я понял что количество всех пар всегда три И число дней как посчитать Но не могу подобрать алгоритм чтобы вывести в каком порядке будут солдаты выходить на дежурство Edited by author 02.06.2021 13:24 You can have each pair exactly three times in the answer There is short solution which is easy to prove Solved the problem with pure brute-force in 0.031 sec. BTW, my program works for much larger n's than in the problem statement. I'm wondering whether there is more rigorous solution? There rigorous algo exists. It has O(N^2) complexity and about 10 lines of code. My solution is not much longer - about 20 lines of code. But complexity is O(2^(N/2)*(1/2*N^2)!). But works fast for almost any N =) It means that you are very cool:D For Petrozavodsk this problem was planned as solvable by brute force and some precalculation. Just for fun. Thanks, but, probably, you could give some clue for algorithmic solution of the problem? Try to arrange soldiers in vertices of regular n-polygon and mind geometrically. what is wrong in my solution? Program N1744; Var n,i,j,t,k:integer; A:array[1..100,1..100] of integer; R:array[1..50000,1..3] of integer; begin Readln(n); for i:=1 to N do for j:=1 to N do if i<>j then A[i,j]:=0 else A[i,j]:=3; k:=0; for i:=1 to N do for j:=1 to n do for t:=1 to n do if (A[i,j]<3)and(A[i,t]<3) and(A[j,t]<3) then begin inc(k); R[k,1]:=i; R[k,2]:=j; R[k,3]:=t; inc(A[i,j]); inc(A[i,t]); inc(A[j,t]); inc(A[j,i]); inc(A[t,i]); inc(A[t,j]); end; writeln(k); for i:=1 to k do writeln(R[i,1],' ',R[i,2],' ',R[i,3]); Readln; end. is there a difference in what order the output numbers of soldiers? Edited by author 24.01.2010 16:02 Edited by author 24.01.2010 16:03 For n=7 your program returns k=13 and for n=9 k=28, but correct answers are 21 and 36 Edited by author 27.01.2010 04:07 Can you write full output for n=7 ? For example, 21 1 2 3 1 2 3 1 2 3 1 4 5 1 4 5 1 4 5 1 6 7 1 6 7 1 6 7 2 4 6 2 4 6 2 4 6 2 5 7 2 5 7 2 5 7 3 4 7 3 4 7 3 4 7 3 5 6 3 5 6 3 5 6 I hope, it will help you. |
|
|