[ Colex @ 22.02.2007. 10:55 ] @
Code:



//Japanska buba uletjela je u špilju punu prepreka: stalagmita (stoje na podu špilje) i stalaktita (vise sa stropa špilje).
//Špilja je duljine N (gdje je N paran broj) i visine H. Prva prepreka je stalagmit a zatim se izmjenjuju stalaktiti i stalagmiti.
//Na slici je primjer jedne špilje duljine 14 i visine 5 (slika odgovara drugom primjeru test podataka):
//         |          |            |            |               |               |              |
//         |   |      |            |            |               |               |              |
//   |         |            |      |       |    |      |        |        |      |        |     |
//   |         |            |      |       |           |                 |               |
//   |         |            |              |           |                 |               |
//Japanskoj bubi se ne da izbjegavati prepreke, nego ona odabere jednu od H razina i zaleti se s jednog kraja špilje na drugi, te sa svojim kung fu vještinama poruši sve prepreke na putu.
//Na primjer, ako u špilji sa prethodne slike odabere četvrtu razinu od poda, onda ce porusiti ukupno osam prepreka:
//       |            |            |            |               |               |              |
//       |     |      |            |            |               |               |              |
//   |         |            |      |       |    |      |        |        |      |        |     |
//   |         |            |      |       |           |                 |               |
//   |         |            |              |           |                 |               |
//U ovom primjeru manje ce se umoriti ako odabere prvu ili petu razinu, jer ce u ta dva slučaja porušiti samo sedam prepreka.
//Zadane su dimenzije špilje i duljine svih prepreka. napišite program koji određuje koliko NAJMANJE PREPREKA buba mora porušiti da bi prošla na drugu stranu, te na koliko različitih razina se postiže ta najmanja vrijednost.
//ULAZNI PODACI:
//U prvom redu ulaza nalaze se prirodni brojevi N i H, 2 =< N =< 200 000, 2 =< H =< 500000, dimenzije špilje. N će biti paran.
//Slijedećih N redova sadrži redom duljine svih prepreka, prirodne brojeve manje od H.
//U prvi i jedini red ispišite dva cijela broja odvojena jednim razmakom, najmanji broj prepreka koji buba mora porušiti te na koliko različitih razina se postiže ta najmanja vrijednost.
//       ULAZ:                     ULAZ:
//       6 7                       14 5
//       1                         1
//       5                         3
//       3                         4
//       3                         2
//       5                         2
//       1                         4
//                                 3
//       IZLAZ:                    4
//       2 3                       3
///                                3
//                                 3 
//                                 2
///                                3
//                                 3
//
///                                IZLAZ: 
//                                 
//                                 7 2
//
//
//
//
[ nticaric @ 24.02.2007. 03:54 ] @
Evo jedno rjesenje:

Code:

#include <iostream>
#include <vector>
#include <stdlib.h>
#include <string.h>
using namespace std;


char ubaciunulu(char *x,int y){
      int i;
      for(i=0; i<y; i++) x[i]='0';

      }

int main(){
    int i, j;
    int duljina, visina, stupbroj, brojac=0, min, zbroj=0; 
    char stupac[200000];
    vector <string> spilja;
    cin>>duljina>>visina;
    
    for(i=1; i<=duljina; i++){
       cin>>stupbroj; 
       ubaciunulu(stupac, visina);
            if(i%2==0){ 
            for(j=visina-1; j>=(visina -stupbroj); j--)
            stupac[j] = '1'; 
            }
            else{
            for(int j=0; j<stupbroj; j++)
            stupac[j] = '1'; 
                 }
spilja.push_back(stupac);
            }
min = duljina;  
for(i=0; i<visina; i++)
    {
     zbroj=0;
         
     for(j=0; j<duljina; j++)
        {
            if(spilja[j][i] == '1')
                {
                  zbroj+=(spilja[j][i]-48);
                 
                }                
        }
if(zbroj<min)min=zbroj; 
    }
  for(i=0; i<visina; i++)
    {
     zbroj=0;
         
     for(j=0; j<duljina; j++)
        {
            if(spilja[j][i] == '1')
                {
                  zbroj+=(spilja[j][i]-48);
                 
                }                
        }
if(zbroj==min)brojac++; 
    }
cout<<min<<" "<<brojac<<endl;
    
    system("pause");
    }

[ nticaric @ 24.02.2007. 03:58 ] @
Evo jos jedan nacin:

Code:

#include <stdio.h>
#include <malloc.h>
int main()
{
int i,j,n,h,min,brmin;
int* pv;
int* br;
scanf("%d",&n); scanf("%d",&h);
pv=(int*) malloc(n*sizeof(int));
for (i=0;i<n;i++)
scanf("%d",&pv[i]);
br=(int*) malloc(h*sizeof(int));
for(j=1;j<=h;j++)  br[j]=0;
for(i=0;i<n;i+=2)
{
for(j=1;j<=h;j++)                 
if ((j+pv[i])>h) br[j]++;   
}
for(i=1;i<n;i+=2)
{
for(j=1;j<=h;j++)                 
if (j<=pv[i]) br[j]++;   

}

//for(j=1;j<=h;j++) 
//printf("\n br[%d]=%d", j,br[j]);
min=n+1;
brmin=0;
for (j=1;j<=h;j++)
{
if (br[j]==min) brmin++;
if (br[j]<min) {min=br[j]; brmin=1;}

}

printf("\n%d %d", min, brmin)   ;
    
    
scanf("%d",i);
}