Allocation de verrerie – Épreuve régionale 2016

Énoncé¶

L'Alchimiste des Géniaux Objets prépare des formules pour transmuter la convoitée Opale de Condensation Algébrique et de Matérialisation de Légendes.

Ces formules produisent des composés intermédiaires instables, qui peuvent être contenus seulement par des récipients en cristal de plomb torché, un verre extrêmement coûteux à fabriquer.

Malheureusement, suite à de multiples échecs (l'explosion de gaz hilarant dans le palais avait relocalisé le laboratoire au sommet du volcan, que la dernière expérience a mis en éruption), le Grand Conseil est peu enclin à accorder le budget nécessaire pour ces instruments.

En parcourant les formules de votre ami l'Alchimiste, vous vous apercevez qu'il est possible de réduire le nombre de récipients requis en les réutilisant et en changeant l'ordre des opérations. Vous proposez donc à l'Alchimiste de réarranger ses formules pour faire une commande plus acceptable au Grand Conseil.

Une formule est une suite de réactions produisant des composés instables numérotés de 0 à n - 1, dans le but d'obtenir le composé n - 1.

Prenons par exemple la formule suivante :

1
2
3
4
5

0 ← -1 -2
1 ← -3 -4
2 ← -3 -2
3 ← 1 2
4 ← 3 0

Une réaction pour le composé i fait intervenir deux ingrédients j_i et k_i ; chacun peut être :

• une matière première (j_i < 0, k_i < 0, respectivement) ;
• ou un autre composé déjà produit (0 ≤ j_i < i, 0 ≤ k_i < i, respectivement).

Par exemple, la première ligne de la formule ci-dessus donne la réaction pour le composé 0, qui consomme les matières premières -1 et -2.

Les matières premières sont stables et n'ont pas besoin d'être dans un récipient en cristal de plomb torché.

Naturellement, chaque récipient ne peut contenir qu'un seul composé à la fois.

Dans une formule, chaque composé intermédiaire (d'indice i avec 0 ≤ i < n - 1) est utilisé par exactement une seule réaction. Cela implique en particulier que si j_i et k_i sont les ingrédients du composé i, et s'ils sont tous deux des composés (et non des matières premières), alors j_i ≠ k_i, et l'ensemble des composés formant j_i est disjoint de celui formant k_i. Par contre, rien ne les empêche d'avoir des matières premières en commun.

On peut réarranger les réactions de la formule ci-dessus.

1
2
3
4
5

1 ← -3 -4
2 ← -3 -2
3 ← 1 2
0 ← -1 -2
4 ← 3 0

Tandis que la formule originale requiert trois récipients en cristal de plomb torché, celle-ci n'en nécessite que deux, nommons les A et B :

• à partir de matières premières, on produit d'abord 1 qu'on met dans le récipient A, et 2 dans B ;
• on vide B dans A pour faire réagir 2 avec 1, et produire 3 ;
• on remplit à nouveau B avec 0, fait de matières premières ;
• on fait réagir 0 et 3 et on obtient le composé final 4 dans A.

Entrée¶

L'entrée comprendra :

• sur la première ligne, un entier n donnant la longueur de la formule ;
• sur chacune des n lignes suivantes, indicées par i de 0 à n - 1, deux entiers j_i et k_i séparés par une espace donnant les ingrédients qui réagissent pour produire le composé i.

Sortie¶

Vous afficherez en sortie le nombre minimal de récipients en cristal de plomb torché nécessaires pour exécuter la formule.

Contraintes¶

• 1 ≤ n ≤ 10 000
• -100 < j_i, k_i < i, pour tout i tel que 0 ≤ i ≤ n-1.