|
Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja
možete slati na e-mail:
tak.prog@gmail.com
U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.
|
logo by Igor Antolović
|
|
|
zadatak: Čokoladomat
|
Noćica mnogo voli čokoladu. Na sreću, odmah na ulazu firme u kojoj radi, "Megahard", nalazi se automat za
čokoladu, čokoladomat. Njena firma se bavi proizvodnjom operativnog sistema "Dors" i, logično, softver na
čokoladomatu zasnovan je upravo na tom operativnom sistemu. Nažalost, mnogi tvrde da je ovaj operativni sistem
daleko inferioran u odnosu na konkurentski, čija je maskota polarni medved (a koji mnogo voli Noćičin prijatelj
Tugomir, što je i predmet njihovih čestih prepirki, ali to nije bitno za ovu priču). Upravo da propagatori
konkurencije ne bi dobili za pravo, ono što se jutros desilo s čokoladomatom u "Megahardu" mora ostati tajna — a
pošto znamo da ste vi savesna deca, koja neće okolo širiti tračeve (a i budući da Noćica traži pomoć od
vas, pa i nema baš neki izbor), ispričaćemo vam.
Softver u čokoladomatu načisto je pobrljavio. Umesto da iznose ubačenih apoena sabere (kako bi bilo prirodno), on
na sve njih primeni operaciju XOR. Zaposleni u firmi to su brzo shvatili, ali proći će dosta vremena
dok ne stignu rezervni delovi, što je Noćicu bacilo u očaj.
Srećom, uprava firme donela je odluku da se čokoladomat može koristiti i dok ovako pogrešno obračunava ubačen
iznos. To je malo olakšalo muke Noćici, ali i dalje je u nedoumici: ukoliko dođe pred čokoladomat s određenom
količinom apoena, šta od toga treba da ubaci kako bi dobila što više čokolade, tj. kako bi čokoladomat zaračunao
što je veći mogući iznos? Postoji još jedna začkoljica: pauze za uzimanje čokolade u "Megahardu" ne traju
baš dugo, pa Noćica nema vremena da polagano prebira po novčaniku. Jedino može stići da odabere dve novčanice,
i sve što je u novčaniku između njih (uključujući njih) stavi u čokoladomat. Jasno, Noćica je vrhunska
programerka, te joj u normalnim okolnostima ovo ne bi predstavljalo nikakav problem, ali kako ne može da funkcioniše
bez čokolade, preklinje vas da joj pomognete.
Ulaz:
(Ulazni podaci se nalaze u datoteci cokolada.in) U prvom redu ulazne datoteke nalazi se prirodan broj n
(1 ≤ n ≤ 250.000), koji predstavlja broj apoena koje Noćica ima kod sebe (neki od njih mogu biti
i jednaki). U narednih n redova nalazi se po jedan ceo broj iz intervala [0,60.000], pri čemu svaki od njih
predstavlja vrednost po jednog Noćičinog apoena.
Izlaz:
(Izlazne podatke upisati u datoteku cokolada.out) U prvi red i jedini red izlazne datoteke treba
upisati jedan ceo broj, koji predstavlja maksimalnu moguću svotu koju Noćici može zaračunati čokoladomat.
Primer 1:
cokolada.in
|
|
cokolada.out
|
5
13
3
11
18
12
|
|
30
|
|
|
fajl: cokolada.cpp
|
/*
Author: Slobodan Mitrovic
e-mail: boba5555@gmail.com
date: 31.05.2009.
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ffor(_a,_f,_t) for(int _a=(_f),__t=(_t);_a<__t;_a++)
#define all(_v) (_v).begin() , (_v).end()
#define sz size()
#define pb push_back
#define SET(__set, val) memset(__set, val, sizeof(__set))
#define FOR(__i, __n) ffor (__i, 0, __n)
using namespace std;
const int TREE_SIZE = 1 << 17;
bool tree[TREE_SIZE];
void add(int val){
int idx = 1, bit = 1 << 16;
FOR (i, 17){
tree[idx] = true;
bit >>= 1;
idx <<= 1;
idx += ((val & bit) != 0);
}
}
int read(int val){
int idx = 1, cld, cb, ob, ret = val, goonB;
int bit = 1 << 15;
FOR (i, 16){
idx <<= 1;
cb = (val & bit) != 0; // current bit
ob = cb ^ 1; // opposite bit
if (tree[idx + ob])
goonB = ob;
else
goonB = cb;
idx += goonB;
ret ^= (goonB * bit);
bit >>= 1;
}
return ret;
}
unsigned short int s;
bool ex[1 << 16];
int n, a;
int main(){
freopen("cokoladomat.in", "rt", stdin);
freopen("cokoladomat.out", "wt", stdout);
SET(tree, 0);
SET(ex, 0);
scanf("%d", &n);
s = 0;
add(0);
int ret = 0;
FOR (i, n){
scanf("%d", &a);
s ^= a;
if (!ex[s]){
ex[s] = true;
ret >?= read(s);
add(s);
}
}
printf("%d\n", ret);
return 0;
}
|
|
|