Rezolvare completă PbInfo #1696 Perechi2

Fie un şir a[1], a[2], …, a[n] de numere naturale, unde n este impar. Avem la dispoziţie o singură operaţie admisă şi anume: putem aduna la două poziţii diferite din şir o aceeaşi valoare naturală nenulă.

Cerința

  1. Să se verifice dacă șirul poate să aibă toate elementele egale după aplicarea unei singure operații.
  2. Folosind de mai multe ori operaţia admisă, să se obţină șirul cu toate elementele egale, dar valoarea egală obţinută să nu depăşească dublul valorii maxime din şirul iniţial.

Date de intrare

Fișierul de intrare perechi2.in conține pe prima linie un număr natural C, pe a doua linie numărul n, iar pe linia a treia, separate prin câte un spațiu, valorile a[1], a[2], …, a[n].

Date de ieșire

Fișierul de ieșire perechi2.out va conține:

  1. Dacă C=1, atunci se va rezolva doar prima cerință, deci se va afișa pe prima linie valoarea 0 dacă nu se pot obține în șir toate elementele egale, sau se vor afișa trei numere naturale i j v cu semnificația: la pozițiile i și j din șir se adaugă valoarea v și astfel toate elementele vectorului vor deveni egale.
  2. Dacă C=2, atunci se va rezolva doar a doua cerință. Pe fiecare linie a fișierului de ieșire se vor afișa exact trei valori i j v cu semnificația: se adună valoarea v la a[i] și la a[j] (unde i și j sunt distincte și sunt cuprinse între 1 și n).

Restricții și precizări

  • 5 ≤ n < 2000, n este impar
  • 0 ≤ a[i] ≤ 100 000 000, pentru orice i=1..n
  • Elementele șirului inițial nu sunt neapărat distincte, dar nu sunt nici toate egale
  • Dacă există mai multe soluții, puteți afișa oricare dintre ele.
  • Dacă numărul operațiilor aplicate este mai mic sau egal decât n, iar valoarea finală este de cel mult două ori cât maximul inițial și rezultatul aplicării operațiilor furnizează în șir aceeași valoare, atunci veți primi 100% din punctaj.
  • Dacă numărul operațiilor este cuprins între n+1 și 2n, iar valoarea finală este de cel mult două ori cât maximul inițial și rezultatul aplicării operațiilor furnizează în șir aceeași valoare, atunci veți primi 70% din punctaj.
  • Dacă numărul operațiilor este mai mare de 2n sau dacă valoarea finală depășește dublul valorii maxime inițiale, atunci veți primi 0 puncte. De asemenea, dacă în urma operațiilor aplicate nu se obține un șir cu aceeași valoare peste tot, sau dacă aplicați o operație în care pozițiile i și j nu sunt din intervalul 1..n, atunci de asemenea veți primi 0 puncte.
  • Pentru teste valorând 20 de puncte vom avea C=1. Pentru restul testelor vom avea C=2, din care pentru 30 de puncte șirul va fi format din numere distincte cuprinse între 1 și n.

Exemplu 1

perechi2.in

1
5
8 2 8 8 2

perechi2.out

2 5 6

Explicație

C=1, deci se va rezolva doar prima cerință! Adunând valoarea 6 la pozițiile 2 și 5 se va obține șirul constant 8 8 8 8 8.

Exemplu 2

perechi2.in

2
5
8 5 6 3 10

perechi2.out

1 2 2
3 4 4
2 4 3

Explicație

C=2, deci se va rezolva doar a doua cerință! Valoarea maximă din șir este 10, deci valoarea finală trebuie să fie maximum 20. Trebuie efectuate cel mult 5 operații pentru 100 puncte.

  • Aplicând operația 1 2 2, obținem șirul 10 7 6 3 10
  • Aplicând operația 3 4 4, obținem șirul 10 7 10 7 10
  • Aplicând operația 2 4 3, obținem șirul 10 10 10 10 10

Exemplu 3

perechi2.in

1
5
8 2 7 8 2

perechi2.out

0

Explicație

C=1, deci se va rezolva doar prima cerință! Nu se poate efectua o singură operație astfel încât toate elementele șirului să devină egale.

Exemplu 4

perechi2.in

2
3
1 2 3

perechi2.out

1 3 1
1 2 2

Explicație

C=2, deci se va rezolva doar a doua cerință! Valoarea maximă din șir este 3, deci valoarea finală trebuie să fie maximum 6. Trebuie efectuate cel mult 3 operații pentru 100 puncte.

  • Aplicând operația 1 3 1, obținem șirul 2 2 4
  • Aplicând operația 1 2 2, obținem șirul 4 4 4

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Perechi2:

#include <fstream>
#define inFile "perechi2.in"
#define outFile "perechi2.out"
#define Dim 10005

using namespace std;

int a[Dim];
int P[Dim];
int n;

void Cerinta1()
{
    int i, cnt;
    ofstream fout(outFile);
    /// verifica nr de numere diferite
    cnt = 1;
    for (i = 2; i <= n; ++i)
        if (a[i] != a[i - 1]) cnt++;
    if (cnt != 2 || a[2] == a[3])
    {
        fout << "0
";
        fout.close();
        return ;
    }
    cnt = a[3] - a[2];
    fout<<P[1]<<" "<<P[2]<<" "<<cnt<<"
";
    fout.close();
}

void Cerinta2()
{
    int i, ultim, v;
    ofstream fout(outFile);
    ultim = n;
    for (i = 1; i < n; i += 2)
    {
        v = a[ultim] - a[i];
        if (v > 0)
        {
            a[i] += v;
            a[i + 1] += v;
            fout << P[i] << " " << P[i + 1] << " " << v << "
";
            a[++ultim] = a[i];
            P[ultim] = P[i];
            a[++ultim] = a[i + 1];
            P[ultim] = P[i + 1];
        }
    }

    for ( ; i < ultim; i += 2)
    {
        v = a[ultim] - a[i];
        if (v > 0)
        {
            a[i] += v;
            a[i + 1] += v;
            fout << P[i] << " " << P[i + 1] << " " << v << "
";
        }
    }
    fout.close();
}

int main()
{
    int i, j, C;
    int aux;

    //citire
    ifstream fin(inFile);
    fin >> C;
    fin >> n;
    for (i = 1; i <= n; ++i)
    {
        fin >> a[i];
        P[i] = i;
    }
    fin.close();

    //sortare
    for (i = 1; i < n; ++i)
        for (j = i + 1; j <= n; ++j)
            if (a[i] > a[j])
            {
                aux = a[i];
                a[i] = a[j];
                a[j] = aux;
                aux = P[i];
                P[i] = P[j];
                P[j] = aux;
            }

    if (C == 1) Cerinta1();
    else Cerinta2();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1696 Perechi2

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1696 Perechi2 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!