ultima problemă
grupă: micăsursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
xor1
Timp maxim de execuţie/test:
0.1
secunde
Memorie totală disponibilă/stivă:
2 MB/1 MB
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+1 xor ak+2 xor ... ap-1 xor ap
x3 = ap+1 xor ap+2 xor ... an-1 xor an
Cerinţă
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 xor1.in 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 ieşire
Fişierul de ieşire xor1.out 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
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) 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
Exemplu
xor1.in xor1.out Explicaţie
10 41
Valoarea maximă 41 se obţine împărţind şirul în secvenţele: 5 (x1 = 5)2 = 7 xor 2 xor 9 = 12)3 = 16 xor 8 xor 1 xor 3 xor 6 xor 4 = 24)x1 + x2 + x3 = 41
Probleme recomandate
De la XOR 2010 : ordonare , paltrei , triunghi1 , 123 , traseu1 De acelaşi autor : cai , rebus , harta , comun , axa , sir , ocean14 , reduceri , div3 , patrate6 , vot , reziduu , accesibil , predecesor , permutari , scanduri , ordonare , paltrei , triunghi1 , 123 , traseu1 , parbit , petrecere , secvbiti , subm , triunghi3 , cmmdcsecv , drumuri1 , fillmat , secvb , siruri3 , acces , segmente , echilibru1 , broscute , ksecv , paisprezece , proddiv , perechi2 , expeval , maxtri , combcuv , dfs , qtri , blis , maxbin , probleme , divider , eliminare , minm , genab , grafxy , matd3 , azeval , matrixdel , speed , maxp , split , binremove , sminus , subsets , tcif , sprime , sir2dif , ecp , arbsum , robotzi , permtr , unudoi , matcnt , ssdj , dominant Despre vector : trei , simetric , egal , ruleta , pod , uscat , afise , an , bunici , cursa , onu , tramvai , cadou , kpal , expresie , piticot , roci , petrol , grad , ruleta2 , ecran , palma , concurs , holo , ab2 , tren2 , cifre , mgo , firma , anagrame , joc2 , br , maxim , astre , numere2 , baby , zapada , hd , startrek , vecini2 , drept , teatru , tir , patrate2 , nr , cifra , repeat , unu , criptare , ratb , placi , sume3 , turist , matrice3 , pavaj , sume , kafka , bacan , spair , grup , friends2 , bitslang , fisc , scor2 , cat , nr3 , chimie2 , zid , politics , submat , reteta2 , rezervatie , creioane , felinare , 2numere , exp , scoici , patrate1 , playlist , sqr , carte , oua , turn , ants , div3 , jeton , politic , trecere , maraton , zaruri , suma1 , mere1 , agitatie , lacuri , secv , sotron , triunghi , carti1 , spioni , kalah , excursia , matricea , maxq , oras , furnici , baschet , ingerasi , numar1 , prieteni , aritma , cezar , bifo , pal , seceta , bare , soricel1 , antena , avere , paianjen , bloc , schi , suma3 , fractie , tunel , pepsi , prefix , tren3 , avion , premii1 , csir , top , bsir , secvente , cod4 , cuburi3 , limbaj , panouri , sant1 , zumzi , sport1 , baschet1 , mere3 , powerpuff , placare , sir4 , volei1 , tabel , ocr , numere7 , lacusta , flori , pluton , elfi , mare , grupe1 , maroco , cartonas , cabina , case , cod5 , furnica , numere8 , paritate , comoara1 , exponent , control , exp1 , joc13 , popas , reactivi , siruri1 , vanatoare , submult , text1 , taxe1 , visul , paranteze , puncte3 , cub3 , numere9 , panglica , pietre , poartas , sume2 , bal , secvsir , vot , prefix1 , accesibil , palc , standard , bursa , meteo , jetoane , printesa , palindrom , joker , matriosca , loto , cuvant , cladiri1 , secvente1 , zar , tren4 , asociativ , lego , medalii , figura , joc14 , neuroni , char , dartz , turism1 , calorii , paltrei , album , livada1 , colorare , greutati , brazi , submatrix1 , plaja , cd1 , cifru3 , permutare , miere , tetris1 , conferinta , atelier , radical , bileprime , nx , atletism , sumb , minmax , sumacifre , jocprim , sircifre , cmmdcsecv , secvb , siruri3 , cifru4 , vase , carte1 , grad1 , litere , magic6 , macheta , butoane , ec , stalpi2 , fagure , goe , papusa , taburet , mesaj3 , zar1 , joc16 , talent , joc18 , cos , punctfix , risipa , liste , triburi , nr0 , oneton , nor , nrpomi , paisprezece , anagramabil , zuma , joc20 , dale , perechi2 , consiliu , becuri2 , codpatrat , adprod , qtri , reconst , arme , triunghi4 , deal , ozn1 , cifru5 , flori1 , elicop , roata , trifoi , maxbin , culori2 , numar5 , bile6 , proiecte , alune , cuburi4 , sstabil , intersectii , copaci2 , 7segmente , amedie , drept2 , divider , eliminare , matd3 , prodnr , fraze , vectori1 , compar , unific , galbeni , clepsidru , calcule , puncte6 , maxp , cursa1 , secvp , swap , extraprime , onigim , divizori1 , remi1 , tetris3 , amestec , eoliene , split , momente , secvente2 , ausoara , aranjare2 , vintage , binremove , sminus , subsets , interclasare , palindromuri , colina , doitrei , rebus1 , tcif , munte3 , triunghi6 , schi1 , rascoala , solitar , praslea , vot2 , tema , sprime , sir2dif , aperm , unudoi , prajituri , tan , concurs4 , ech , arc , dominant , ordine , tv1 , nebuni , sort2dist , lightbot , iepuras1 , castig Despre secvenţe : degrade , hora , simetric , egal , ruleta , ecran , sirag , pasi , firma , br , numere2 , termen , div , teatru , repeat , ratb , 2sec , sport , pikachu , suma3 , panouri , sir5 , mare , hof , resturi , efort , livada1 , diff , popic , guess , albine1 , permutare , miere , atelier , obstacole , echilibru1 , lcdr , 3max , ksecv , maxbin , meteo1 , galbeni , maxp , secvp , split , secvente2 , ausoara , sminus , munte3 , cool , betisoare , unudoi , charlie , lasere , arc , dominant , restaurare , roua