Metoda greedy

#include <iostream>
using namespace std;

int n, poz[500];
double a[500], v;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        poz[i] = i;          // numarul de ordine al componentei
    }
    cin >> v;

    /* Metoda greedy: ca suma sa depaseasca v cu cat mai putini termeni,
       se aleg componentele in ordinea descrescatoare a valorilor.
       Se ordoneaza descrescator, prin selectie, pastrand numerele de ordine. */
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++)
            if (a[j] > a[i]) {
                double x = a[i]; a[i] = a[j]; a[j] = x;
                int p = poz[i]; poz[i] = poz[j]; poz[j] = p;
            }

    /* Se alege intai cea mai mare componenta, apoi se adauga, pe rand,
       cea mai mare dintre cele ramase, pana cand suma depaseste v.
       O componenta negativa sau nula nu mai mareste suma, deci acolo
       alegerea se opreste. */
    double s = a[1];
    int k = 1;
    while (k < n && s <= v && a[k + 1] > 0) {
        k++;
        s = s + a[k];
    }

    if (s > v)
        for (int i = 1; i <= k; i++)
            cout << poz[i] << " ";
    else
        cout << "nu este posibil";
    return 0;
}

Programul

• se citesc n, cele n componente și v
  • componentele sunt numere reale, deci se păstrează în variabile de tip double
  • pentru fiecare componentă i se reține și numărul ei de ordine, în poz[i]
• se ordonează componentele descrescător, prin selecție
  • pentru fiecare poziție i, de la 1 la n − 1
    • pentru fiecare poziție j de după ea
      • dacă a[j] > a[i], cele două componente își schimbă locurile
      • odată cu ele își schimbă locurile și numerele lor de ordine, din poz, ca fiecare componentă să-și păstreze numărul
• se alege prima componentă, cea mai mare: suma s pornește de la ea, iar k, numărul celor alese, de la 1
• cât timp mai sunt componente, suma nu depășește v și componenta următoare este pozitivă
  • se alege componenta următoare: k crește cu 1, iar ea se adaugă la sumă
• dacă suma a depășit v
  • se afișează numerele de ordine ale primelor k componente
• altfel
  • se afișează că nu este posibil

Prima componentă se alege întotdeauna, chiar dacă v este negativ: enunțul cere componente alese, deci cel puțin una.

#include <iostream>
#include <fstream>
using namespace std;

int ap[10001];     // ap[x] = 1 daca x se afla in multime

int main() {
    ifstream f("titu.in");
    int n, k, x;
    f >> n >> k;
    for (int i = 1; i <= n; i++) {
        f >> x;
        ap[x] = 1;
    }
    f.close();

    /* Cele mai mari k numere pare: suma lor este cea mai mare posibila. */
    int nr = 0, luatePare = 0;
    long long sPare = 0, sImpare = 0;
    for (x = 10000; x >= 0 && luatePare < k; x = x - 2)
        if (ap[x]) {
            luatePare++;
            sPare = sPare + x;
        }
    nr = luatePare;

    /* Numerele impare, de la cel mai mic, cat timp suma lor ramane
       strict mai mica decat suma numerelor pare alese. */
    for (x = 1; x <= 9999; x = x + 2)
        if (ap[x]) {
            if (sImpare + x < sPare) {
                sImpare = sImpare + x;
                nr++;
            } else
                break;
        }

    if (sPare == 0)    // nicio selectie nu indeplineste conditia
        nr = 0;
    cout << nr;
    return 0;
}

Programul

• se citesc n, k și elementele mulțimii
  • ifstream f("titu.in") deschide fișierul pentru citire
  • fiecare număr citit x se marchează în vectorul caracteristic: ap[x] = 1
• se aleg parele, de la cel mai mare
  • x pornește de la 10000, cel mai mare număr par posibil, și scade din 2 în 2
  • cât timp s-au ales mai puțin de k pare
    • dacă x se află în mulțime, se alege: crește numărul parelor alese, iar x se adaugă la suma parelor
• se aleg imparele, de la cel mai mic
  • x pornește de la 1 și crește din 2 în 2
  • dacă x se află în mulțime
    • dacă suma imparelor, cu x adăugat, rămâne strict mai mică decât suma parelor, x se alege
    • altfel alegerea se oprește: imparele următoare sunt și mai mari
      • break iese din bucla for
• dacă suma parelor alese este 0, nicio alegere nu respectă condiția, deci rezultatul este 0
• se afișează numărul elementelor alese

Parcurgerea vectorului ap de la un capăt la altul dă numerele în ordine, fără o sortare separată.

#include <iostream>
#include <fstream>
using namespace std;

/* Cel mai mare termen al sirului 1, 2, 5, 12, 27, ... aflat in [1, n]. */
int termen(int n) {
    int a = 1, b = 2;          // doi termeni consecutivi
    if (n < 2)
        return 1;
    while (1 + 3 * b - 2 * a <= n) {
        int c = 1 + 3 * b - 2 * a;
        a = b;
        b = c;
    }
    return b;
}

Subprogramul termen(n)

• a și b sunt doi termeni consecutivi ai șirului; pornesc de la primii doi, 1 și 2
• dacă n este 1, cel mai mare termen din [1, 1] este 1, deci se returnează 1
• cât timp termenul următor, 1 + 3·b − 2·a, nu depășește n
  • se calculează termenul următor, c
  • perechea de termeni consecutivi înaintează: a primește b, iar b primește c
• la ieșirea din buclă, b nu depășește n, iar termenul următor îl depășește, deci b este cel mai mare termen din [1, n]; se returnează b

Termenii aproape se dublează de la unul la altul, deci până la 10⁹ sunt cel mult 30 de termeni, iar bucla face cel mult 30 de pași.

int main() {
    int n;
    cin >> n;
    ofstream g("def.out");

    /* Metoda greedy: se scade din n, de fiecare data, cel mai mare termen
       al sirului care nu il depaseste. */
    while (n > 0) {
        int t = termen(n);
        g << t << " ";
        n = n - t;
    }
    g.close();
    return 0;
}

Programul principal

• se citește n
• se deschide fișierul pentru scriere
  • ofstream g("def.out") creează fișierul def.out, gol, și leagă variabila g de el
• cât timp n nu a ajuns la 0
  • se află cel mai mare termen t care nu depășește n, prin apelul termen(n)
  • se scrie t în fișier, urmat de un spațiu
    • g << t << " " scrie în fișier la fel cum cout scrie pe ecran
  • din n se scade t
• se închide fișierul
  • g.close()

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

struct interval {
    int st, dr;
};

interval v[10001];
int n;

bool comparaDr(interval a, interval b) {
    return a.dr < b.dr;
}

int main() {
    ifstream f("titu2021.in");
    f >> n;
    for (int i = 1; i <= n; i++)
        f >> v[i].st >> v[i].dr;
    f.close();

    sort(v + 1, v + n + 1, comparaDr);    // crescator dupa extremitatea dreapta

    int nr = 1;                           // primul interval se alege
    int ultimDr = v[1].dr;
    for (int i = 2; i <= n; i++)
        if (v[i].st >= ultimDr) {         // incepe dupa ultimul interval ales
            nr++;
            ultimDr = v[i].dr;
        }

    cout << nr;
    return 0;
}

Programul

• un interval se reține ca înregistrare, cu două câmpuri
  • struct interval { int st, dr; } definește tipul: st este extremitatea stângă, dr cea dreaptă
• subprogramul comparaDr spune ordinea: intervalul cu extremitatea dreaptă mai mică stă înainte
• se citesc n și cele n intervale
  • ifstream f("titu2021.in") deschide fișierul pentru citire
• se ordonează intervalele crescător după extremitatea dreaptă
  • sort(v + 1, v + n + 1, comparaDr) ordonează pozițiile 1, …, n ale tabloului v după comparaDr; funcția este din biblioteca algorithm
• se alege primul interval, cel care se termină cel mai devreme
  • nr, numărul intervalelor alese, pornește de la 1
  • ultimDr reține unde se termină ultimul interval ales
• pentru fiecare interval următor, în ordinea obținută
  • dacă începe cel mai devreme unde se termină ultimul ales, adică v[i].st >= ultimDr
    • se alege: nr crește cu 1, iar ultimDr primește extremitatea lui dreaptă
  • altfel se intersectează cu ultimul ales și nu se alege
• se afișează nr

Extremitățile sunt din [−10⁹, 10⁹], deci încap în tipul int, al cărui maxim este 2 147 483 647.