Responsive image
Meniu
Toate soluțiile
Soluţii trimise de tine
Compilator online
Ajutor

Xor

Adăugată de :
sorynsoo
Sursă :
XOR2010
Autor :
-
Grupă :
Medie
Punctaj :
0 pc

Restricţii

Citire / Scriere :
stdin, stdout
Limită timp :
100 ms
Limită memorie :
2048 kbytes

Fie un şir de n numere naturale a1, a2, ..., an. Luând doi indici k şi p, împărţim acest şir în 3 secvenţe, prima fiind a1, a2, ..., ak, a doua ak+1, ak+2, ..., ap, iar a treia ap+1, ap+2, ..., an. Pentru fiecare secvenţă se aplică operatorul xor între oricare doi termeni ai secvenţei, obţinând câte un număr natural:

  • x1 = a1 xor a2 xor a3 ... ak-1 xor ak
  • x2 = ak+1xor ak+2 xor  ... ap-1 xor ap
  • x3 = ap+1 xor ap+2 xor ... an-1 xor an

Cerinţa

Să se determine o împărţire a şirului în 3 secvenţe astfel încât valoarea x1 + x2 + x3 să fie maximă.

 

Date de intrare

Fişierul de intrare conţine pe prima linie numărul natural n, iar pe a doua linie se află şirul de n numere naturale a1, a2, ..., an separate prin câte un spaţiu.

 

Date de iesire

Fişierul de iesire va conţine o singură linie pe care va fi scrisă valoarea maximă posibilă care se poate obţine pentru suma x1 + x2 + x3.

 

Restricţii şi precizări:

  • 2 <= n <= 2 000
  • 0 <= ai <= 2 000 000, pentru orice 1 <= i <= n
  • Fiecare din cele trei secvenţe va conţine cel puţin un element din şir
  • operatorul xor (sau exclusiv), scris în Pascal prin xor şi în C/C++ prin ^, este operatorul pe biţi care furnizează rezultatul 1 dacă şi numai dacă unul din cei doi operanzi este 1, iar celălalt 0. Tabela operaţiei: 1 xor 1 = 0,  0 xor 0 = 0,  1 xor 0 = 1,  0 xor 1 = 1

 

Exemple

  Date de intrare

  Date de iesire

Explicaţie

  10

  5 7 2 9 16 8 1 3 6 4

 

  41

  Valoarea maximă 41 se obţine împărţind şirul în     secvenţele:

  • 5 (x1 = 5)
  • 7 2 9 (x2 = 7 xor 2 xor 9 = 12)
  • 16 8 1 3 6 4 (x3 = 16 xor 8 xor 1 xor 3 xor 6 xor 4 = 24)

  x1 + x2 + x3 = 41

 


Trimite o solutie

Format: cpp şi c

Selectează runda

Trebuie să fii logat pentru a trimite surse


Indicații rezolvare

Nu există indicații de rezolvare



Comentarii

Adauga un comentariu: Click !