|
|
I don`t understant brute-force , who can give your code to me ? mail: k13795263@yahoo.cn Edited by author 23.08.2008 05:40 I have a brute-force code for cheking answers Python 3.8 def summa(a): ans = 0 for i in range(len(a)): ans += a[i] * a[i - 1] return ans def recursion(n, do_etogo): a = True mn = 10 ** 9 mx = 0 mnansn = [] mxansn = [] for i in range(2, n + 1): if i in do_etogo: continue a = False mnans, mxans, mnansm, mxansm = recursion(n, do_etogo + [i]) if mnans < mn: mn = mnans mnansn = [mnansm] elif mnans == mn: mnansn.append(mnansm) if mxans > mx: mx = mxans mxansn = [mxansm] elif mxans == mx: mxansn.append(mxansm) if a: return summa(do_etogo), summa(do_etogo), do_etogo, do_etogo return mn, mx, mnansn, mxansn n = int(input()) print(recursion(n, [1])) Timus Sistem have: Test1: n = 4 Test2: n = 2 Test3: n = 3 Right answers for n = 15 1 14 3 12 5 10 7 8 9 6 11 4 13 2 15 1 3 5 7 9 11 13 15 14 12 10 8 6 4 2 n = 16 1 15 3 13 5 11 7 9 8 10 6 12 4 14 2 16 1 3 5 7 9 11 13 15 16 14 12 10 8 6 4 2 Enjoy by problem) А платит ли герой за возвращение в свой город ? Если нет то есть более оптимальное решение чем авторский пример 1324 а не 1423. Если да то примеры приведённые выше равноценны. Платит, куда денется =) What's answer if n = 5 and n == 6? Just brute force for n=5,6 to get it :) It's useful somtimes to solve the problem Is there someone who can tell me the algorithm? Thx... Write brute-force algo and you'll find how does optimal solution look like... this is my program : #include<iostream> using namespace std; int main() { int n; cin>>n; int i; for(i=0;i<n/2;i++) cout<<i+1<<" "<<n-i<<" "; if(n%2!=0) cout<<((int)n/2)+1<<" "; cout<<endl; cout<<"1 "; for(i=3;i<n;i+=2) cout<<i<<" "; int p=n; if(p%2!=0) { p-=1; cout<<n<<" "; } for(p=p;p>1;p-=2) cout<<p<<" "; return 0; } I think its right but I get WA on test 4 anybody knows whats wrong ? Edited by author 06.11.2007 02:56 Edited by author 06.11.2007 02:57 I did some research and I'm sure I've got the correct algorithm. But i get WA on test 4. I'm thinking it could be something with the way I print the numbers (new lines and such). Could anyone please tell me what is N on test 4? Check it yourself)) Smth like if (n > 50) while (1); Thanks, that was a nice trick i hadn't thought of before :) I think it's rather usefull trick)) write brute force program and you will find your mistake Edited by author 13.07.2007 19:42 I have a problem. I think my algorithm is right (I've tested it by search), but solution is not accepted. Could somebody give the first test? I've understood what's the metter. input: 5 possible outputs: 1 5 2 4 3 1 3 5 4 2 or 1 4 3 2 5 1 2 4 5 3 But only the second solution is accepted. Edited by author 25.03.2007 21:09 For 5 correct answer is 1 5 2 3 4 1 3 5 4 2 or 1 4 3 2 5 1 2 4 5 3 Both are acceptable. Edited by author 25.03.2007 14:12 It's very strange... I've sent the solution that gives the first variant of answer and my solution haven't been accepted. Then I've changed only the order of output numbers (the second variant of answer) and my solution have been accepted. I wrote two solutions where one have first result and other have second result. But they both have WA7 subj But better of course - min & max ) Never use System.out. Use BufferedWriter or smth like that instead. (On other programs) Use Arrays.sort for sort. Never implement algorythm by your own if there is a way to avoid it. I think you gave wrong sample test for n=4 min is not 1 4 2 3 it is 4 1 2 3 because 1*4+4*2+2*3=18 but 4*1+1*2+2*3=12 You are wrong. Read the task more carefully. You are wrang, becouse 1*4+4*2+2*3+3*1 = 21, 4*1+1*2+2*3+3*4 = 24. And moreover, the sequence must start with 1. In sample test answer for n=4 is 1 4 2 3 1 3 4 2 but correct answer is 1 3 2 4 1 3 4 2 Maybe, I'm not right, but my program had AC on contest... 1*4+4*2+2*3+3*1=21 1*3+3*2+2*4+4*1=21 Sorry,I thought this must be 1*4+4*2+2*3=18 1*3+3*2+2*4=17 Simple algorithm but hard proof? How to prove that some construction in this problem is optimal? For minimal permutation must be: (p[i] - p[i+1]) * (p[i-1] - p[i+2]) < 0 |
|
|