fbpx

Problema #967 – Cifre8 – Rezolvari PBInfo

0

Fie c o cifră, iar s un şir de n numere naturale. Utilizând toate cifrele impare ale unităţilor numerelor din s, se construieşte un nou şir de numere naturale v cu proprietăţile următoare:

  1. toate numerele din şirul v au acelaşi număr de cifre
  2. fiecare număr din v este format doar din cifre identice
  3. şirul v este format din cel mai mic număr de valori naturale care au proprietăţile 1. şi 2.

Cerinţe

Scrieţi un program care să citească numerele c, n şi şirul s, şi să determine:

Exemplu

Intrare

10 9
1943 31 19 1199 34 941 7971 131 223 6

Ieșire

1345
6
4

Explicație

a) numerele prime din şirul s sunt: 31, 19, 941, 131 şi 223. Suma acestora este 1345.
b) cifra c=9 apare de 6 ori în scrierea numerelor din s.
c) cifrele impare ale unităţilor numerelor din s sunt, în ordine crescătoare: 1, 1, 1, 1, 3, 3, 9, 9. Se pot forma minimum 4 numere cu toate cifrele identice: 11, 11, 33, 99, fiecare număr din noul şir având numărul maxim posibil de cifre, adică 2. Numărul minim de termeni ai şirului este egal cu 4.

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

int prim(int n)
{
    int d=2 , cnt=1;
    while(n>1)
    {
        int p = 0;
        while(n%d==0)
        {
            n/=d;
            p++;
        }
        if(p!=0)
        cnt*=(p+1);
        d++;
        if(d*d>n)
        d=n;
    }
    if(cnt==2)
    return 1;
    else
    return 0;
}

int cmmdc(int a , int b)
{
    while(b)
    {
        int r=a%b;
        a=b;
        b=r;
    }
    return a;
}

int main()
{
    int n;
    cin >> n;
    int y;
    cin >> y;
    int a[10000];
    int v[10000];
    int f[10]={0};
    int s=0 , cnt=0;
    int p = 0;
    for(int i = 0 ; i < n ; ++i)
    {
        cin >> a[i];
        if(prim(a[i]))
        s+=a[i];
        int x=a[i];
        while(x)
        {
            if(x%10==y)
            cnt++;
            x/=10;
        }
        if((a[i]%10)%2==1)
        {
            v[p]=a[i]%10;
            p++;
        }
    }
    for(int i = 0 ; i < p ; ++i)
    {
        f[v[i]]++;
    }
    int c , b=-1 , cmd=1 , i;
    for(i = 0 ; i <= 9 ; ++i)
    {
        while(f[i]==0 && b==-1)
        {
            i++;
            b=f[i];
        }
        while(f[i]==0)
        i++;
        c=f[i];
        cmd=cmmdc(c , b);
        b=cmd;
    }
    cout << s << endl << cnt << endl << p/cmd;
    return 0;    
}
Comentarii
Se incarca comentariile...

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More