TAKMIČENJA IZ PROGRAMIRANJA


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.

cokolada.cpp    1,463 b      izvorni kod rešenja
cokolada.tests.rar    2,352,721 b      test primeri

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;
}