# PBinfo #4474 – Magie1 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Vrăjitorul Amaric a găsit un șir cu N numere, pe care vrea să-l transforme astfel încât să conțină o secvență de valori egale de lungime cât mai mare. Pentru aceasta, Amaric a pregătit două feluri de magii:

- magia de tip 1: alege două numere din șir și le schimbă între ele în șir. Această magie se poate aplica de oricâte ori.
- magia de tip 2: alege un număr din șir și îl mărește cu o valoare care este divizor al acestuia. Această magie se poate aplica cel mult o dată pentru fiecare număr din șir.

De exemplu, dacă șirul contine numerele (6, 8, 4, 8), aplicând magia de tip 1 pentru numerele 4 și 8, șirul devine (6, 8, 8, 4). Dacă aplicăm magia de tip 2 pentru numărul 4, el poate deveni 5 sau 6 sau 8.

Cerința
Scrieți un program care să determine lungimea maximă a unei secvențe de numere egale dacă:


Amaric aplică doar magii de tipul 1;
Amaric aplică doar magii de tipul 2;
Amaric aplică magii de tipul 1 și de tipul 2.

Date de intrare
Fișierul de intrare magie.in conține pe prima linie numărul C, care poate fi 1, 2 sau 3, reprezentând cerință care trebuie rezolvată. Pe a doua linie se află numărul N, iar pe a treia linie N numere naturale, separate prin câte un spațiu.

Date de ieșire
Fișierul de ieșire magie.out va conține un număr natural reprezentând lungimea maximă a unei secvențe de numere egale, aplicând magiile permise.

Restricții și precizări

1 ≤ N ≤ 5.000;
1 ≤ numerele din șirul dat ≤ 5.000;
pentru teste în valoare de 30 de puncte, C = 1
pentru teste în valoare de 30 de puncte, C = 2

Exemplul 1
magie.in

1
4
6 8 4 8
magie.out

2
Explicație
Aplicând magia de tipul 1 pentru numerele 8 și 4 șirul devine (6 4 8 8).

Exemplul 2
magie.in

2
4
6 9 8 4
magie.out

3
Explicație
Aplicând magia de tip 2 pentru numărul 6 îl mărim cu 3 și devine 9.
Aplicând magia de tip 2 pentru numărul 8 îl mărim cu 1 și devine 9.
Șirul devine (9 9 9 4).

Exemplul 3
magie.in

3
4
6 9 4 8
magie.out

3
Explicație
Aplicăm o magie de tip 1 pentru numerele 6 și 9 și șirul devine (9, 6, 4, 8). 
Aplicând magia de tip 2 pentru numărul 6 îl mărim cu 2 și devine 8.
Aplicând magia de tip 2 pentru numărul 4 îl mărim cu 4 și devine 8.
Șirul devine (9 8 8 8).

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cassert>
using namespace std;
ifstream fin("magie.in");
ofstream fout("magie.out");
int N, C, A[5001];
int V[10001];
int main()
{
	fin >> C >> N;
	for(int i = 1 ; i <= N ; i ++)
	{
		fin >> A[i];
		assert(A[i] >= 1 && A[i] <= 5000);
	}
	int max;
    for(int i = 1; i <= 10000 ; i ++)
        V[i] = 0;
    max = -1;
    if(C == 1)
    {
        for(int i = 1 ; i <= N ; i ++)
            V[A[i]] ++;
        for(int i = 1 ; i <= 10000; i ++)
            if(V[i] > max)
            max = V[i];
    }
    if(C == 3)
    {
        for(int i = 1 ; i <= N ; i ++)
        {
            V[A[i]] ++;
            for(int d = 1 ; d <= A[i] ; d ++)
                if(A[i] % d == 0)
                V[A[i] + d] ++;
        }
        for(int i = 1 ; i <= 10000; i ++)
            if(V[i] > max)
            max = V[i];
    }
    if(C == 2)
    {
        for(int i = 1 ; i <= N ; i ++)
        {
            for(int j = 1 ; j <= 10000 ; j ++)
            {
                if(j < A[i])
                    V[j] = 0;
                else
                    if(j == A[i])
                    V[j] ++;
                    else
                    if(A[i] % (j - A[i]) != 0)
                    V[j] = 0;
                    else
                    V[j] ++;
                    if(V[j] > max)
                    max = V[j];	
                    }
        }
    }
    fout << max <<endl;
    cout << "C = " << C << ". Max = " << max <<endl;
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4474)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4474/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4474/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)