Evolució de molècules (2) X62507

En un experiment amb n molècules de diversos pesos enters s’ha detectat un fenomen curiós. Repetidament, les dues molècules més pesades es combinen, despareixen, i generen una nova molècula. Si la molècula més pesada té pes x, i la segona més pesada té pes y, poden passar dues coses. Si x i y acaben amb el mateix dígit, es farà una fusió de tipus A i la nova molècula tindrà pes x − ⌊ y/2 ⌋. Si acaben amb diferent dígit, es farà una fusió de tipus B i la nova molècula tindrà pes x − ⌊ y/4 ⌋. El procés acaba quan només queda una molècula.

Per exemple, si els pesos inicials són 21, 6, 3 i 20, primer es combinen 21 i 20, que fan una fusió de tipus B i generen un 21 − ⌊ 20/4 ⌋ = 21 − 5 = 16. Ara tenim 6, 3 i 16, es combinen 16 i 6, que amb una fusió de tipus A generen un 16 − ⌊ 6/2 ⌋ = 16 − 3 = 13. Ara tenim 3 i 13, que es combinen amb una fusió de tipus A i generen 13 − ⌊ 3/2 ⌋ = 13 − 1 = 12, el qual és el pes de la molècula final. En el procés hem efectuat dues fusions de tipus A i una de tipus B.

Feu un programa que simuli eficientment aquest procés i escrigui el pes de l’última molècula, i el nombre de fusions de cada tipus.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de molècules n, seguit dels n pesos, tots enters entre 1 i 10⁹. Podeu assumir 1 ≤ n ≤ 10⁵.

Sortida

Per a cada cas, escriviu el pes de l’última molècula, seguit del nombre de fusions de tipus A i el nombre de fusions de tipus B.

Observació

Us desaconsellem que feu servir multisets per resoldre aquest problema.