Cerința

Gigel dorește să instaleze în grădină o ghirlandă cu N becuri colorate, numerotate de la 1 la N, care, din minut în minut, să se aprindă și să se stingă automat. Pentru a putea face aceasta el s-a gândit să asocieze fiecărui bec câte un număr, în felul următor: la fiecare minut, un bec se va aprinde dacă prima cifră a numărului asociat lui este număr prim, altfel becul va fi stins. Numerele asociate becurilor, au o proprietate specială, din minut în minut, acestea își mută circular cifrele spre stânga, la fiecare permutare prima cifra a fiecărui număr, devine ultima. Toată ghirlanda se va stinge, la momentul în care, numărul asociat, cu cele mai multe cifre, ajunge, din nou, la valoarea inițială (în acest timp, la fiecare minut, celelalte numere efectuează permutări).

Scrieți un program care să determine:

Cerința

Gigel dorește să instaleze în grădină o ghirlandă cu N becuri colorate, numerotate de la 1 la N, care, din minut în minut, să se aprindă și să se stingă automat. Pentru a putea face aceasta el s-a gândit să asocieze fiecărui bec câte un număr, în felul următor: la fiecare minut, un bec se va aprinde dacă prima cifră a numărului asociat lui este număr prim, altfel becul va fi stins. Numerele asociate becurilor, au o proprietate specială, din minut în minut, acestea își mută circular cifrele spre stânga, la fiecare permutare prima cifra a fiecărui număr, devine ultima. Toată ghirlanda se va stinge, la momentul în care, numărul asociat, cu cele mai multe cifre, ajunge, din nou, la valoarea inițială (în acest timp, la fiecare minut, celelalte numere efectuează permutări).

Scrieți un program care să determine:
1. Câte becuri aprinse sunt în starea inițială;
2. Care este numărul maxim de becuri care pot fi aprinse la un moment dat;
3. Care este becul/becurile care se aprind de cele mai multe ori.

Date de intrare

Fișierul de intrare becuri1.in conține pe prima linie numărul C, ce reprezinta numărul cerinței, de pe cea de-a doua linie un număr natural N ce reprezintă numărul de becuri colorate, iar de pe următoarele N linii, câte un număr natural, ce reprezintă numărul asociat fiecărui bec, în ordinea crescătoare a numerelor de ordine.

Date de ieșire

Fișierul de ieșire becuri1.out dacă C=1 va conține pe prima linie, valoarea cerută la cerința 1. Dacă C=2 va conține pe prima linie, valoarea cerută la cerința 2. Dacă C=3 va conține pe prima linie, numerele de ordine (despărțite prin câte un spațiu) ale becurilor care se aprind de cele mai multe ori; afișarea se va face în ordinea crescătoare a numerelor de ordine atașate becurilor; dacă nu există astfel de becuri în ghirlandă, se va afișa -1.

Restricții și precizări

• 1 ≤ N ≤ 100
• numerele asociate becurilor sunt intre 0 și 1.000.000.000. Pot exista mai multe becuri cu același număr asociat

Exemplul 1:

becuri1.in

1
5
12
5
378
2015
8

becuri1.out

3

Explicație

Cerința 1.
Gigel are o ghirlandă cu 5 becuri. Primul bec are asociat numărul 12 și este stins. Al doilea bec are asociat numărul 5 și este aprins. Al treilea bec are asociat numărul 378 și este aprins. Al patrulea bec are asociat numărul 2015 și este aprins. Al cincilea bec are asociat numărul 8 și este stins.

Exemplul 2:

becuri1.in

2
5
12
5
378
2015
8

becuri1.out

4

Explicație

Cerința 2.
La minutul 0 numerele asociate becurilor sunt: 12, 5, 378, 2015 și 8. La minutul 1 numerele asociate becurilor vor fi: 21, 5, 783, 0152 și 8. La minutul 2 numerele asociate becurilor vor fi: 12, 5, 837, 1520 și 8. La minutul 3 numerele asociate becurilor vor fi: 21, 5, 378, 5201 și 8. Numărul maxim de becuri aprinse va fi 4, la minutul 3.

Exemplul 3:

becuri1.in

3
5
12
5
378
2015
8

becuri1.out

2

Explicație

Cerința 3.
Al doilea bec este cel care se va fi aprins de cele mai multe ori, deoarece numărul asociat cu cele mai multe cifre ajunge la valoarea inițială abia după 4 permutări, timp în care becul al doilea va fi aprins de 4 ori.

#include <bits/stdc++.h>
using namespace std;

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

int cer , n , a[201][201] , maxi;
long long x;

void afiseaza(int n , int p)
{
    int cnt = 0 , c = 0;
    while(n != 0)
    {
        a[p][++cnt] = n % 10;
        n /= 10;
        c++;
    }
    a[p][0] = c;
    maxi = max(maxi , c);
    for(int i = 1 ; i <= cnt / 2 ; i++)
        swap(a[p][i] , a[p][cnt - i + 1]);
}

int prim (int n)
{
    if(n == 0 || n == 1) return 0;
    if(n == 2) return 1;
    if(n % 2 == 0) return 0;
    for(int i = 3 ; i * i <= n ; i += 2)
        if(n % i ==0) return 0;
    return 1;
}

int main()
{
    cin >> cer >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> x;
        if(x != 0)
        afiseaza(x , i);
    }
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= maxi ; j++)
        {
            if(a[i][0] != 0)
            {
            if(a[i][j] == 0 && j % a[i][0] == 0) a[i][j] = a[i][a[i][0]];
            else if(a[i][j] == 0 && j % a[i][0] != 0) a[i][j] = a[i][j % a[i][0]];
            }
        }

    /*for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= maxi ; j++)
            cout << a[i][j] << " ";
            cout << '\n';
    }*/

    if(cer == 1)
    {
        int rez = 0;
        for(int i = 1 ; i <= n ; i++)
            if(prim(a[i][1])) rez++;

        cout << rez;
    }
    else if(cer == 2)
    {
        int rmax = 0;
        for(int j = 1 ; j <= maxi ; j++)
        {
            int rez = 0;
            for(int i = 1 ; i <= n ; i++)
                if(prim(a[i][j])) rez++;
            if(rez > rmax) rmax= rez;
        }
        cout << rmax;
    }
    else
    {
        int rmax = 0 , ok = 0;
        for(int i = 1 ; i <= n ; i++)
        {
            int rez = 0;
            for(int j = 1 ; j <= n ; j++)
                if(prim(a[i][j])) rez++;
            if(rez > rmax) rmax= rez;
        }
        for(int i = 1 ; i <= n ; i++)
        {
            int rez = 0;
            for(int j = 1 ; j <= n ; j++)
                if(prim(a[i][j])) rez++;
            if(rez == rmax && rmax != 0) cout << i << " ", ok++;
        }
        if(ok == 0) cout << -1;
    }
}