Curs 4

Putem sa rezolvam problema doar pentru axa x, axa y o vom neglija deoarece prob. este echivalenta daca toate punctele sunt doar pe axa X

Segmentele vor fi paralele cu axa X, deoarece daca sunt oblige acopera mai putin

Problema arata asa. Dandu-se un sir de numere reale, sa se determine lugimea minima a unui segement astfel, sa acoperim cu cel mult k segemente toate punctele

Cautare binara a unui element 
Cautare binara a raspunsului = cautam lungimea minima

Toate probleme de cautare binara a raspunsului au urmatoarea formulare: Sa se determine X minim/maxim astfel, o verificare sa aiba loc
5 3
-5.000 1.000
-2.000 3.000
3.000 2.000
3.000 -2.000
1.000 2.000
     ---    ---- 
    -5   -2      1  3,3
    -|----|-------|----|----
  p[1] p[2]        
  k = 3 
                           1
bool check(int lungmax) {
//TRUE/FALSE Pot acoperi toate punctele cu maxim k segemente de lungime lungmax
 -      -        -  ----- 
 -5   -2      1  3 , 3
start = Points[1];
int nrsegm = 1;
for(int i = 2; i <= n; ++i) {
  int end = Points[i];
  if(end-start > lungmax) {
    ++nrsegm;
    start = Points[i];
  }
}
if(nrsegm <= k)
  return true;
else
  return false;
}

int Points[NMAX];
int main() {
  cin >> n >>k;
  for(int i= 1; i <= n; ++i) {
   double x,y;
   cin >> x >> y;
   Points[i] = (int)(X *10000.0);
  }
  sort(Points+1, Points+n+1);

  int st=1 , dr =10^6;
  int sol = -1;
  while(st<=dr) {
    int lung_mij = (st+dr) / 2;
    if(check(lung_mij)) { 
      dr = mij-1;
      sol = mij;
    }
    else  st = mij+1;
  } 
cout << sol;
}

  CHECK(lung)     1 2 3  4...............100000000
                             0 1 1  1  1  1 1 1 1 1 1 1 1
                             
                             
    CHECK(lung)     1 2 3  4.....50..........100000000
                               1 1 1 1      0 0 0 0 0  00 0 0 0 0 

bool check(int timpul) {
  for(int  i = 1; i <= n; ++i) {
    nrobiecte += timpul/a[i];
    
  }
  if(nrobiecte <= M)
    return true;
  else
    return false;
}

int st = 0, dr = 1e9;

while(st<=dr) {
  int mij = ( st+dr)/2;
  if(check(mij) {
    sol = mij;
    dr = mij-1;
  }
  else
    st = mij+1;
}

cout << sol;

3 12
1 : 3 2
2 : 2 3
3 : 1 1

c1 + c2 + c3 = 12
c1-3
c2+3
c2-2
c3+2
c3-1
c1+1

c1 : -3 + 1 = -2
c2 : 3 -2 = 1
c3: 2-1 = 1
c1-2 = c2 + 1 = c3 + 1 = S/3 = 4

=> c1 = 6 => socatem: 1,2,3..5 = 5 variante => 
   c2 = 3 => scoatem: 1,2 = 2 variante
   c3 = 3 => scoatem : 1,2 = 2 variante
------------------------------------------
(1,1,1); (1,1,2); (1,2,1); (1,2,2),(2,1,1)...
5*2*2 =20
 
  Fiind date n evenimente cu n[i] variante fiecare, numarul de posiblitati este egal cu
  a) Evenimentele sunt indepente: Daca scot din prima cutie 2 cd uri, nu ma afecteza cate scot din celelalte
   ci => ci-1
     Solutia = (n[1] * n[2] * ... n[n])% 9901
  b) Evenimentele sunt dependente:
     n[1] + n[2] + ... n[n];
 const int mod = 9901;
(a*b)%mod = a%mod * b%mod
  int prod = 1;
  for(int i = 1; i <= n;++i)
      prod = (prod*n[i])%mod;


========
const int mod = 9901, NMAX = 100005;
int c[NMAX],n,S, coef[NMAX];
int main() {

cin >> n >> S;
for(int i = 1; i <= n; ++i) {
  cin >> x >>y;
  //din cutia i se muta x cd uri in cutia y
  coef[i]-=x;
  coef[y]+=x;
}
for(int i = 1; i <= n; ++i)
  c[i]  = S/n - coef[i];
  long long prod = 1;
  for(int i = 1; i <= n;++i)
      prod = ( prod*(c[i]-1))%mod;
cout << prod;
}

int n;
long long stupi[NMAX] 
int m;
long long sp[NMAX];
bool check(int pozitie,int capacitate,int zi) {
  
  if(sp[pozitie] + pozitie*zi<= capcitate)
    return true;
  else
    return false;
}

for(int i = 1;i <= n; ++i) {
  cin >> stupi[i];
}
for(int i = 1; i <= n; ++i) {
  sp[i] = sp[i-1] + stupi[i];
}
cin >> m; 
for(int i = 1; i <= m ;++i) { O(m*n*log2N*)
 cin >> capacitate;
  int st = 1,dr=n;
  while(st<=dr) {
    int mij = (st+dr)/2;
    if(check(mij,capcitate,i-1)) {
      ans = mij;
      st = mij+1;
    }
    else
    dr=mij-1;
}
}
}