In primul rand trebuie sa remarc faptul ca am primit 10 surse. Incepe
sa devina decent :-) La mai mare !
Trec apoi la cateva aspecte organizatorice, adresate in primul rand
concurentilor noi de pe lista:
- nu se trimit executabile
- fisierele de intrare/iesire se afla in directorul curent
- mesajul care contine problema va avea subiectul "Problema NN", unde
NN este numarul problemei
- prima linie a sursei va contine ca si comentariu numele concurentului
Mai multe detalii gasiti la http://probleme.lbi.ro.
In ceea ce priveste problema, majoritatea i-ati gasit rezolvarea.
Solutia se gasea rationand in felul urmator:
A gasi numarul de functii surjective cu proprietatile descrise in
problema este echivalent cu a gasi un sir de 0, -1 si 1 care sa aiba
cel putin un 0, un 1 si un -1 (f este surjectiva) si care sa aiba un
numar de elemente nenule (1 sau -1) egal cu s.
Cele n-s elemente nule le putem aseza pe orice pozitii in sir. Vom
avea C(n,n-s) posibilitati, unde cu C(n,n-s) am notat combinari de n
luate cate n-s. Pentru simplificarea formulei scriem C(n,n-s)=C(n,s).
Avand o asemenea aranjare a zerourilor, urmeaza sa asezam elementele
1 si -1. Relativ la cele s pozitii ramase libere, valorile de 1 vor putea
ocupa orice submultime a acestor pozitii mai putin submultimea vida
(care presupune sa nu avem nici un element 1, ceea ce contrazice
surjectivitatea) si submultime tuturor pozitiilor libere (care presupune
sa nu avem nici un element -1, ceea ce de asemenea contrazice conditia
de surjectivitate). Numarul total de astfel de submultimi este in mod
evident 2^s-2.
Numarul cerut de problema este deci C(n,s)*(2^s-2). Simplu, nu ?
Cei neobisnuiti cu astfel de rationamente, sa nu isi faca probleme caci
dupa inca 2-3 probleme de acest tip, vor incepe sa intuiasca rapid
astfel de solutii.
Revenind la rezolvarea problemei, singura grija ramanea faptul ca
trebuia lucrat pe numere mari, deoarece rezultatele puteau depasi usor
maxlongint.
Sper ca v-a placut problema. Mult succes in continuare.
|
|
