Informatică, întrebare adresată de printess199, 8 ani în urmă

2131 pbinfo

Cerința
Iulică este acasă și trebuie să ajungă la patinoar. Patinoarul se află la exact d km de mers pe jos, astfel încât, dacă am considera un sistem de coordonate, casa lui Iulică se află în punctul 0 și patinoarul se află în punctul d.

Între parc și patinoar există k magazine din care se poate cumpăra pâine, magazine situate la a[i] km (1 <= i <= k) față de casa lui Iulică, în aceeași direcție în care se află patinoarul. Fiind foarte departe, Iulică nu poate ajunge foarte repede la patinoar. Astfel, înainte să plece, mama lui Iulică îi da un ghiozdan care poate căra cel mult g pâini, inițial cu g pâini în el. Știind că Iulică poate mânca o pâine sau poate să stea nemâncat pe parcursul unui km, și că poate sta nemâncat maximum t km pe întreg traseul, aflați capacitatea minimă g pe care o poate avea ghiozdanul, astfel încât Iulică să poată ajunge la patinoar fără să moară de foame. Iulică îşi poate umple ghiozdanul de la fiecare magazin gratuit.

Date de intrare
Fișierul de intrare ghiozdan.in conține pe prima linie trei numere naturale d, k, t, separate prin câte un spațiu, fiecare având semnificațiile din enunț. Linia a doua conține k numere naturale a[i] (1 <= i <= k), în ordine crescătoare, reprezentând distanța de la casa lui Iulică la magazinul i.

Date de ieșire
Fișierul de ieșire ghiozdan.out conține pe prima linie un singur număr natural reprezentând capacitatea g minimă a ghiozdanului.

Restricții și precizări
1 <= d <= 10000000
0 <= k <= 100000
1 <= a[i] <= d, 1 <= i <= k
0 <= t <= d
20% din teste vor avea valoarea t = 0



Exemplu
ghiozdan.in

6 1 2
3
ghiozdan.out

2
Explicație
Se observă că dacă ghiozdanul putea căra maximum o pâine, Iulică nu ar fi putut ajunge la patinoar.

Răspunsuri la întrebare

Răspuns de lucaciucandrei
1

#include<fstream>  

using namespace std;

int main() {

   int d, k, t, a[1000001], l = 0, r;

   ifstream f("ghiozdan.in");

   f >> d >> k >> t;

   r = d;

   for (int i = 1; i <= k; i++)

       f >> a[i];

   f.close();

   a[0] = 0;

   a[k + 1] = d;

   while (l < r) {

       int m;

       m = (l + r) / 2;

       int paine = 0;

       for (int i = 1; i <= k + 1; i++)

           if (a[i] - a[i - 1] > m)

               paine = paine + a[i] - a[i - 1] - m;

       if (paine > t)

           l = m + 1;

       else

           r = m;

   }

   ofstream g("ghiozdan.out");

   g << l;

   g.close();

   return 0;

}


printess199: Multumesc mult de tot!
printess199: Ma mai poti ajuta cu o problema, te rog frumos?
printess199: https://brainly.ro/tema/9001955
lucaciucandrei: deja te-am ajutat prea mult
incearca sa rezolvi si singur/singura, altfel nu inveti nimic
printess199: Am incercat. Am facut o functie pt numere prime. Apoi am sortat crescator vectorul si am verificat daca e prim si mi-a dat rezultatul corect, dar pe pbinfo imi da 0 puncte.
printess199: Uite asa am facut-o eu:
printess199: #include
#include
using namespace std;

ifstream cin("soft_prime.in");
ofstream cout("soft_prime.out");

int prim(int n){
if(n<2) return 0;
if(n==2) return 1;
if(n%2==0) return 0;
for(int d=3;d*d<=n;d+=2)
if(n%d==0) return 0;
return 1;
}
int main(){
int n, x, v[40001], p=0, i;
cin>>n;
for(i=1;i<=n;i++){
cin>>x;
if(prim(x)) {
v[++p]=x;
}
}
sort(v+1, v+p+1);
for(i=1;i<=p;i++)
cout<}
printess199: #include< fstream >
#include< algorithm>
using namespace std;

ifstream cin("soft_prime.in");
ofstream cout("soft_prime.out");

int prim(int n){
if(n<2) return 0;
if(n==2) return 1;
if(n%2==0) return 0;
for(int d=3;d*d<=n;d+=2)
if(n%d==0) return 0;
return 1;
}
int main(){
int n, x, v[40001], p=0, i;
cin>>n;
for(i=1;i<=n;i++){
cin>>x;
if(prim(x)) {
v[++p]=x;
}
}
sort(v+1, v+p+1);
for(i=1;i<=p;i++)
cout << v[i] << " " ;
}
Alte întrebări interesante