Se consideră numerele naturale N şi K şi cifrele nenule distincte c[1], c[2], …, c[N].

Cerința

Să se determine câte numere de K cifre formate doar cu cifrele c[1], c[2], …, c[N] sunt divizibile cu 3. Pentru că acest număr poate fi foarte mare, rezultatul se va determina modulo 4001.

Date de intrare

Fișierul de intrare divtrei.in conține pe prima linie numerele naturale N şi K separate printr-un spațiu, iar linia a doua cele N cifre distincte c[1], c[2], …, c[N], separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire divtrei.out va conține o singură linie pe care va fi scris un singur număr natural, reprezentând numărul (modulo 4001) de numere de K cifre formate doar cu cifrele c[1], c[2], …, c[N] și divizibile cu 3.

Restricții și precizări

1 ≤ N ≤ 9
2 ≤ K ≤ 1000
1 ≤ c[1], c[2], ..., c[N] ≤ 9
Definim x modulo 4001 ca fiind restul împărțirii întregi a lui x la 4001. De exemplu, 4002 modulo 4001 = 1.

Exemplu

divtrei.in

3 2
1 3 2

divtrei.out

Explicație

Trebuie determinat numărul de numere de K = 2 cifre formate doar din cifrele 1, 2 şi 3 şi care sunt divizibile cu 3. Acestea sunt în număr de 3, şi anume: 12, 21, 33. Rezultatul 3 împărţit la 4001 furnizează restul 3.

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 divtrei:

/*
  Implementare: Dan Pracsiu
*/
#include<cstdio>
using namespace std;

int r3[3],N,K;
int xp[3],xc[3];

int main()
{
    int i, j, x;
    freopen("divtrei.in", "r", stdin);
    freopen("divtrei.out", "w", stdout);
    scanf("%d %d", &N, &K);
    for (i = 0; i < N; i++)
    {
        scanf("%d", &x);
        r3[x%3]++;
    }

    xp[0] = r3[0];
    xp[1] = r3[1];
    xp[2] = r3[2];
    for (i = 1; i < K; i++)
    {
        if (r3[0] > 0)
        {
            xc[0] += (r3[0] * xp[0]);
            xc[1] += (r3[0] * xp[1]);
            xc[2] += (r3[0] * xp[2]);
        }
        if (r3[1] > 0)
        {
            xc[0] += (r3[1] * xp[2]);
            xc[1] += (r3[1] * xp[0]);
            xc[2] += (r3[1] * xp[1]);
        }
        if (r3[2] > 0)
        {
            xc[0] += (r3[2] * xp[1]);
            xc[1] += (r3[2] * xp[2]);
            xc[2] += (r3[2] * xp[0]);
        }
        for (j = 0;j < 3; j++)
        {
            xp[j] = xc[j] % 4001;
            xc[j] = 0;
        }
    }
    printf("%d\n", xp[0]);
    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 #2408 divtrei

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2408 divtrei 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!

Rezolvare completă PbInfo #2408 divtrei