Antifibo

Time limit: 1s Memory limit: 128MB Input: antifibo.in Output: antifibo.out

În inima cetăţii Numeropolis, se ridica Turnul Infinitului, unde Marele Logofăt, doamna Algoria, păstra Pergamentul Armoniei Numerice. În fiecare toamnă, ea invita înăuntru cei mai îndrăzneţi adepţi ai Şcolii lui Euclid pentru a trece proba Ordinii Echilibrate.

Fiecare candidat primea un manuscris care conţinea un număr natural NN. Misiunea era să aşeze într-un şir AA toate pietrele numerice distincte de la 1 până la NN (aranjare numită Ordine), astfel încât să nu fie respectată proprietatea interzisă:

Să existe vreun 1iN21 \leq i \leq N - 2, pentru care are loc A[i]+A[i+1]=A[i+2]A[i]+A[i + 1]=A[i + 2]

Legenda spune că, dacă cineva încălca această regulă, cele trei pietre se îmbrăcau într-o energie distructivă şi încercau să smulgă Pergamentul din siguranța Turnului.

Odată Ordinea încheiată, concurenţii se îndreptau spre Sala CMMDC-ului, unde fiecare pereche de pietre adiacente, A[i],A[i+1]A[i], A[i + 1], era trecută prin piatra fermecată a Celui Mai Mare Divizor Comun. Rezultatele fiecărei examinări erau însumate, iar scorul final era:

S=(A[1],A[2])+(A[2],A[3])++(A[N1],A[N]).S = (A[1], A[2]) + (A[2], A[3]) + \ldots + (A[N - 1], A[N]).

Cerință

Se dă un TT și TT teste. Pentru fiecare test, se citește un NN și trebuie să construim o Ordine, AA, folosind toate numerele de la 1 la NN, astfel încât niciun triplet aflat pe poziții consecutive să verifice A[i]+A[i+1]=A[i+2]A[i] + A[i + 1] = A[i + 2]. Pentru fiecare Ordine să se afișeze suma tuturor c.m.m.d.c.-urilor perechilor A[i],A[i+1]A[i], A[i + 1], unde 1iN11 \leq i \leq N - 1.

Date de intrare

Fișierul de intrare antifibo.in conține:

  • pe prima linie un număr natural TT;
  • pe următoarele TT linii câte un număr natural NN.

Date de ieșire

Afișează în antifibo.out răspunsul pentru fiecare test pe câte două linii: pe prima cele NN numere în Ordine, iar pe a doua suma c.m.m.d.c.-urilor.

Restricții și precizări

  • 1T1 0001 \leq T \leq 1 \ 000;
  • 3N20 0003 \leq N \leq 20 \ 000;
  • Se garantează că mereu există o Ordine posibilă.
  • Valoarea sumei diferă pentru fiecare Ordine aleasă.
  • Este obligatorie afișarea celor două rânduri pentru fiecare query, altfel nu veți primi punctajul parțial.
  • Daca Ordinea este corectă, dar suma nu, se va acorda doar punctajul pentru Ordine și vice-versa.
  • Pentru Ordine se acordă 60%60\% din punctajul total, iar pentru sumă 40%40\%.
# Punctaj Restricții
1 25 T=1,N10T=1, N \leq 10
2 25 T=1,N20 000T=1, N \leq 20 \ 000
3 25 T100,N20 000T \leq 100, N \leq 20 \ 000
4 25 Fără restricții suplimentare

Exemplu

antifibo.in

6
3
4
5
6
7
8

antifibo.out

2 3 1
2
2 4 3 1
4
3 5 2 4 1
5
5 2 6 1 4 3
6
4 7 2 6 1 5 3
7
3 8 2 7 1 6 4 5
9

Explicație

Pentru testcase-ul 1, avem Ordinea: 2 3 12 \ 3 \ 1, cum 2+3=512 + 3 = 5 ≠ 1, convine. (2,3)+(3,1)=1+1=2(2, 3) + (3, 1) = 1 + 1 = 2.
Pentru testcase-ul 3, avem Ordinea: 3 5 2 4 13 \ 5 \ 2 \ 4 \ 1, cum 3+5=823 + 5 = 8 ≠ 2 și așa mai departe, convine. (3,5)+(5,2)+(2,4)+(4,1)=1+1+2+1=5(3, 5) + (5, 2) + (2, 4) + (4, 1) = 1 + 1 + 2 + 1 = 5.
Pentru testcase-ul 6, avem Ordinea: 3 8 2 7 1 6 4 53 \ 8 \ 2 \ 7 \ 1 \ 6 \ 4 \ 5, cum 3+8=1123 + 8 = 11 ≠ 2 și așa mai departe, convine. (3,8)+(8,2)+(2,7)+(7,1)+(1,6)+(6,4)+(4,5)=1+2+1+1+1+2+1=9(3, 8)+(8, 2)+(2, 7)+ (7, 1) + (1, 6) + (6, 4) + (4, 5) = 1 + 2 + 1 + 1 + 1 + 2 + 1 = 9.

Log in or sign up to be able to send submissions!