Olimpiada de Informatica - Clasele a XI-a si a XII-a, Faza judeteana, 23 martie 2003

Problema 1: COMPUS

La ultima expeditie pe Marte a fost descoperit un compus organic necunoscut. Acest compus este acum studiat in laboratoarele NASA. Cercetatorii au descoperit ca acest compus este constituit numai din atomi de hidrigen (H), ixigen (I) si carbin (C) si are masa moleculara M

Se stie ca regulile de formare a compusilor organici pe Marte sunt urmatoarele:

un atom de carbin se poate lega de oricare dintre atomii de C, H si I cu oricate dintre cele 4 legaturi pe care le are (astfel, in combinatia H-C=C primul atom de carbin se leaga prin doua legaturi de alt atom de carbin si cu o legatura de alt atom de hidrigen)

un atom de hidrigen se poate lega numai de un atom de carbin cu singura legatura pe care o poseda

un atom de ixigen se poate lega numai de atomi de carbin cu cele doua legaturi pe care le poseda

un compus este un ansamblu cu proprietatea ca toti atomii de carbin sunt legati conex intre ei si nu exista vreun atom cu una sau mai multe legaturi libere (nelegate de un alt atom).

Combinatia H-C=C nu este un compus deoarece atomii de carbin mai au legaturi libere.

Cercetatorii au in vedere studiul categoriilor de compusi, facand distinctie intre doi compusi numai daca acestia difera prin numarul de atomi de carbin, de ixigen sau de hidrigen.

Cerinta

Scrieti un program care sa determine cati compusi distincti formati din atomi de carbin, hidrigen si ixigen (cel putin unul din fiecare) si care au masa moleculara M exista.

Date de intrare

Fisierul de intrare compus.in contine pe prima linie masa moleculara a compusului.

Date de iesire

Fisierul de iesire compus.out contine o singura linie pe care se afla numarul de compusi determinat.

Restrictii si precizari

30<=M<=1000000

Masa atomului de H este 1, masa atomului de C este 5, iar masa atomului de I este 3. Masa moleculara a unui compus este egala cu suma maselor atomilor din care este constituit compusul respectiv.

Ordinea in care sunt "utilizate" legaturile unui atom nu conteaza. De asemenea, nici ordinea atomilor sau legaturile interne dintre ei nu conteaza atata timp cat respecta regulile de formare enuntate.

Exemple

Exista un singur compus cu masa moleculara 10: cel format cu un atom de C, doi atomi de H si un atom de I (5+2*1+3=10), compus ale carui legaturi pot fi reprezentate astfel:

H-C=I

|

H

Se pot obtine 3 compusi cu masa moleculara 40: (5C, 6H, 3I), (6C, 4H, 2I), (7C, 2H, 1I):

Reprezentarea cu legaturi a oricaruia dintre compusi nu este unica. Orice alta combinatie corespunzatoare aceluiasi triplet nu se considera un compus distinct.

Exemple

Timp maxim de executare/test: 1 sec.