Page 9 - MATINF Nr. 13-14

a
Concursul de Informatic˘ Programming Day 9

Clasa a X-a

Problema 1 - concursuri

Student , ii anului 1 de la Informatic˘a din POLITEHNICA Bucures , ti - Centrul Universitar
Pites , ti, ˆın num˘ar de N, codificat , i prin 1, 2, . . . , N, trebuie s˘a participe la dou˘a concursuri ˆın
perioade diferite de timp. La primul concurs trebuie s˘a trimit˘a o echip˘a, iar la cel de-al doilea
trei echipe. La primul concurs echipa poate avea cel put , in un student s , i cel mult N student , i.
La al doilea concurs echipele au cˆate un nume PBCUP1, PBCUP2, PBCUP3 s , i cont , in fiecare
cel put , in un student. Nu are important , ˘ ordinea ˆın echip˘a, iar un student poate participa la al
a
a
doilea concurs numai intr-o singur˘ echip˘a.
Cerint , e
a
Cunoscˆand N, num˘arul de student , i, se cere s˘ se determine:
1. ˆın cˆate moduri se poate alege echipa pentru primul concurs;
2. ˆın cˆate moduri se pot alege echipele PBCUP1, PBCUP2, PBCUP3 pentru al doilea concurs.
Acest num˘ar se cere modulo 7919.
Date de intrare
Pe prima linie a fis , ierului de intrare concursuri.in se g˘ases , te C, num˘arul cerint , ei ce trebuie
rezolvat˘a, iar pe linia a doua num˘arul de student , i N.

Date de ies , ire
Pe prima linie a fis , ierului de ies , ire concursuri.out se va g˘asi un singur num˘ar natural, ce
a
reprezint˘ r˘aspunsul corespunz˘ator cerint , ei C din fis , ierul de intrare.
Restrict , ii s , i preciz˘ari
1. 1 ≤ N ≤ 15000.
a
2. m modulo k reprezint˘ restul ˆımp˘art , irii lui m la k.
3. Pentru rezolvarea corect˘ a cerint , ei 1 se vor acorda 20 de puncte.
a
4. Pentru rezolvarea corect˘a a cerint , ei 2 se vor acorda 80 de puncte.
Exemplu

concursuri.in concursuri.out
1 7
3
2 6
3

Explicat , ii

Pentru primul exemplu: ˆın acest caz se rezolv˘a cerint , a C = 1. Echipele pentru primul
concurs pot fi [1], [2], [3], [1,2], [1.3], [2,3] s , i [1,2,3]. Deci sunt 7 variante pentru a participa la
concurs.

Pentru al doilea exemplu: ˆın acest caz se rezolv˘a cerint , a C = 2. Echipele PBCUP1,
PBCUP2, PBCUP3 pentru al doilea concurs pot fi: ([1],[2],[3]), ([1],[3],[2]), ([2],[1],[3]), ([2],[3],[1]),
([3],[1],[2]), ([3],[2],[1]). Deci sunt 6 variante pentru a participa la al doilea concurs.
Timp maxim de execut , ie: 0.1 secunde/test.
Memorie total˘ disponibil˘a: 4 MB.
a