kburnik

C++ - Zadatak Zone

Jan 11th, 2014
120
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.     Zadatak: Zone
  3.              http://bit.ly/zadatak-zone
  4.    
  5.  
  6.     Datum: 2014-01-11
  7.  
  8.     Autor: HSIN
  9.    
  10.     Ponuđeno rješenje: Kristijan Burnik, udruga informatičara Božo Težak
  11.  
  12.     Gmail: kristijanburnik
  13. */
  14. #include <iostream>
  15. #include <cstdio>
  16.  
  17. using namespace std;
  18.  
  19. enum Stranica { SZ = 0, SI = 1, JI = 2, JZ = 3};
  20. enum Interval { POC, KRAJ };
  21. string strane = "SIJZ";
  22.  
  23. // prva dva su za brisanje dodirnih tocaka, druga dva su za dodavanje novih dodirnih tocaka
  24. int utjecaj [4][4] = { {SZ,SI,JZ,JI}, {SI,JI,JZ,SZ}, {JZ,JI,SZ,SI}, {JZ,SZ,JI,SI} };
  25.  
  26. // sva cetri ruba pripadaju prvom kvadratu (rombu)  pa su inicijalno intervali [0,0] za sve 4 strane
  27. int rubovi[4][2];
  28.  
  29. // rezultati:
  30. int cijena[300000];
  31.  
  32. int main()
  33. {
  34.     int n;
  35.     cin >> n;
  36.    
  37.     for (int i = 1;  i < n; i++)
  38.     {
  39.         char strana;
  40.         cin >> strana;
  41.        
  42.         // index strane svijeta na koju postavljamo novu zonu
  43.         int str = strane.find( strana );
  44.        
  45.         // brisanje i brojanje
  46.         int poc = 3000000, kraj = -1;
  47.        
  48.         // obradjujemo sve utjecane rubove
  49.         for (int j = 0; j < 2; j++)
  50.         {
  51.             int p = utjecaj[str][j];           
  52.             // trazimo interval zona na koje utjece novododana zona
  53.             poc = min( poc , rubovi[p][POC] );
  54.             kraj = max( kraj , rubovi[p][KRAJ] );          
  55.             // brisanje starih zona i dodavanje nove
  56.             rubovi[p][POC] = rubovi[p][KRAJ] = i;
  57.         }
  58.        
  59.         // nadopuni cijene za prijasnje zone
  60.         for (int k = poc; k <= kraj; k++ )
  61.             cijena[k]++;
  62.            
  63.         // nadopuni cijenu za novu zonu
  64.         cijena[i] += ( kraj - poc + 1 );
  65.        
  66.         // dodavanje nove zone na "vanjske" rubove
  67.         for (int j = 2; j < 4; j++)
  68.             rubovi[ utjecaj[str][j] ][KRAJ] = i;
  69.        
  70.     }
  71.    
  72.     for (int i = 0 ; i < n; i++)
  73.         printf("%d\n",cijena[i]);
  74.        
  75.     return 0;
  76. }
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.

×