kburnik

C++ - Zadatak SUME - rješenje

Dec 7th, 2012
75
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.     Zadatak: SUME
  3.  
  4.     Složenost: N(log N) za sort, N(log N) za brojanje
  5.  
  6.     Autor zadatka: Alen Rakipović
  7.    
  8.     Autor rješenja: Kristijan Burnik, udruga informatičara Božo Težak
  9.  
  10.     Gmail: kristijanburnik
  11. */
  12.  
  13. #include <iostream>
  14. #include <cstdlib>
  15. #include <algorithm>
  16.  
  17. using namespace std;
  18.  
  19. int a[5000];
  20.  
  21. int exists(int start,int end,int key) {
  22.    // binarna pretraga kljuca u nekom  ukljucivom intervalu [start,end]
  23.    while (start <= end) {
  24.        int mid = (start + end) /2;
  25.        if (key > a[mid])
  26.            start = mid + 1;
  27.        else if (key < a[mid])
  28.            end = mid - 1;
  29.        else
  30.             return 1;
  31.     }
  32.     return 0;
  33. }
  34.  
  35. int main() {
  36.    
  37.     int n;
  38.     cin >> n;
  39.  
  40.     // broj nula koje se pojavljuju u nizu
  41.     int zerocount = 0;
  42.    
  43.     // unos
  44.     for (int i = 0 ; i < n; i++) {
  45.         cin >> a[i];
  46.     // vodimo racunu o broju nula koje su u nizu zbog jedne iznimke - triplet: (0,0,0)
  47.         if (a[i] == 0) zerocount++;
  48.     }
  49.    
  50.     // sortiramo niz jer cemo nad istim raditi binarnu pretragu
  51.     sort(a,a+n);
  52.    
  53.     // iznimka postoji kod pojave barem tri nule, tada je to jedan triplet i odmah ga brojimo
  54.     int unique = (zerocount >= 3);
  55.    
  56.     // postavljamo pocetne granice - koje su ukljucive!
  57.     int start = 0;
  58.     int end = n-1;
  59.    
  60.     // trazimo tri broja koji daju 0 u sumi
  61.     int left,right,middle;
  62.    
  63.     // ima smisla brojati dok se krajevi ne poklope
  64.     // te dok je lijevi kraj negativan ili 0
  65.     while (start < end && a[start] <= 0) {
  66.        
  67.     // postavljamo fiksni desni kraj
  68.         end = n-1;
  69.        
  70.     // lijevi broj je uzet s lijevog dijela niza (brojevi koji su <= 0)
  71.         left = a[start];
  72.        
  73.     // ima smisla brojati dok se krajevi ne poklope
  74.     // te dok je desni kraj pozitivan
  75.         while (start < end && a[end] > 0) {
  76.            
  77.             // desni broj je pozitivan
  78.             right = a[end];
  79.            
  80.         // zbrojimo lijevi i desni broj, njegova negacija je srednji broj
  81.             middle = -(left+right);
  82.            
  83.             // pronadji srednji u granicama [start+1, end-1 ] i broji kao novi triplet ako postoji
  84.             unique += exists( start+1 , end-1 , middle );
  85.            
  86.             // pomici desnu granicu
  87.         // (malo optimizacije jer se brojevi mogu ponavljati, a trazimo samo jedinstvene triplete!)
  88.             while (start < end && a[end]==right) end--;
  89.         }
  90.        
  91.         // pomici lijevu granicu (takodjer malo optimizacije)
  92.         while (start < end && a[start]==left) start++;        
  93.     }
  94.    
  95.    
  96.     // ispisi koliko je izbrojano tripleta
  97.     cout << unique << endl;
  98.    
  99.     return 0;
  100. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×