Evolució de molècules X74560
En un experiment amb n molècules de diversos pesos enters s’ha detectat un fenomen curiós: Repetidament, la molècula més lleugera i la més pesada es combinen, desapareixen, i generen una nova molècula amb la mitjana dels pesos (truncada si cal). El procés acaba quan només queda una molècula.
Per exemple, si els pesos inicials són 1, 3, 4 i 8, primer es combinen 1 i 8, i generen un ⌊ (1 + 8)/2 ⌋ = 4. Ara tenim 3, 4 i 4, es combinen 3 i un 4, i es genera un ⌊ (3 + 4)/2 ⌋ = 3. Ara tenim 3 i 4, que es combinen i generen un 3, el qual es el resultat final.
Feu un programa que simuli eficientment aquest procés i escrigui el pes de l’última molècula.
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 109. Podeu assumir 1 ≤ n ≤ 105.
Sortida
Per a cada cas, escriviu el pes de l’última molècula.
Observació
Us desaconsellem que feu servir multisets per resoldre aquest problema.
Input
4 1 3 4 8 2 1000000000 999999999 1 42 3 23 23 23 5 5 4 1 2 3
Output
3 999999999 42 23 3
- Author
- Language
- Catalan
- Other languages
- English
- Official solutions
- C++
- User solutions
- C++