i checked the permutations i generate with a AC code of 10730.
although the permutations are antiarithmetic , i m gettin WA.
11129 - An antiarithmetic permutation
Moderator: Board moderators
11129 - An antiarithmetic permutation
Last edited by sunny on Mon Oct 23, 2006 8:42 pm, edited 1 time in total.
the problem statement says:
but i got AC just after i changed my program for a input of n<3.
so, there are cases where n=1 or n=2.
Code: Select all
Each line of the input file contains a natural number 3 ≤ n ≤ 10000.
so, there are cases where n=1 or n=2.
My solution is like O(n^2) while the loop is for even numbers.
It worked really fast.
I considered a permutation where all even numbers are left of 0 & odds are on right. Suppose, u've to insert pk. It can always be in the middle of most distant (pi,pj) without forming an arithmetic progression.
Suppose, the so far generated sequence is 2 6 4 0.
So, 8 can be inserted between 4 and 0. then the sequence will be: 2 6 4 8 0.
The same patterned permutation will also be antiarithmetic for the odd numbers.
It worked really fast.
I considered a permutation where all even numbers are left of 0 & odds are on right. Suppose, u've to insert pk. It can always be in the middle of most distant (pi,pj) without forming an arithmetic progression.
Suppose, the so far generated sequence is 2 6 4 0.
So, 8 can be inserted between 4 and 0. then the sequence will be: 2 6 4 8 0.
The same patterned permutation will also be antiarithmetic for the odd numbers.
[ ]
i think the O(n^2) algorithm will not get a tle
first,calculate the permutation for N=10000
then,for the case n<=10000,the solution is the subset of the former permution,from which you just need to printf the element that is smaller than or equal to n.
then we just need to compute 10000^2 times.
and in my computer,10000^2 will not exceed 1 second.
but i still dont know how to solve it...
anyone give some help?
first,calculate the permutation for N=10000
then,for the case n<=10000,the solution is the subset of the former permution,from which you just need to printf the element that is smaller than or equal to n.
then we just need to compute 10000^2 times.
and in my computer,10000^2 will not exceed 1 second.
but i still dont know how to solve it...
anyone give some help?
不鸣则已,一鸣惊人.
let n=13,
first consider 2 0.
now, you've 2 insert 4 and (4,2,0) forms an arithmetic progression. so, insert 4 in the middle of (2,0) so the sequence will be : 2 4 0.
then, it's 6. two arithmetic progression with 6 are (2,4,6) && (0,3,6).
since i put all odd numbers right of 0 and there cant be any (even,even,odd) or (even,odd,odd) progression so, the odd differenced triples can be ignored. so, 6 should be inserted between (2,4) & the sequence will be: 2 6 4 0.
now, u've 2 insert 8. among the two progressions (4,6,8 ) & (0,4,8 ) the (0,4,8 ) is the most differenced one. put 8 between (4,0). as 6 & 8 will be in two different sides of 4, there cant be (4,6,8 ). the sequence will be:2 6 4 8 0
thus, for 10 : 2 10 6 4 8 0 (between 2 and 6 )
thus, for 12: 2 10 6 4 12 8 0 (between 6 and 0 )
the odd numbers can be put on a same way : 2 10 6 4 12 8 0 1 9 5 3 11 7
first consider 2 0.
now, you've 2 insert 4 and (4,2,0) forms an arithmetic progression. so, insert 4 in the middle of (2,0) so the sequence will be : 2 4 0.
then, it's 6. two arithmetic progression with 6 are (2,4,6) && (0,3,6).
since i put all odd numbers right of 0 and there cant be any (even,even,odd) or (even,odd,odd) progression so, the odd differenced triples can be ignored. so, 6 should be inserted between (2,4) & the sequence will be: 2 6 4 0.
now, u've 2 insert 8. among the two progressions (4,6,8 ) & (0,4,8 ) the (0,4,8 ) is the most differenced one. put 8 between (4,0). as 6 & 8 will be in two different sides of 4, there cant be (4,6,8 ). the sequence will be:2 6 4 8 0
thus, for 10 : 2 10 6 4 8 0 (between 2 and 6 )
thus, for 12: 2 10 6 4 12 8 0 (between 6 and 0 )
the odd numbers can be put on a same way : 2 10 6 4 12 8 0 1 9 5 3 11 7