Allocation de verrerie – Épreuve régionale 2016

Niveau 4

É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 ji et ki ; chacun peut être :

  • une matière première (ji < 0, ki < 0, respectivement) ;
  • ou un autre composé déjà produit (0 ≤ ji < i, 0 ≤ ki < 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 ji et ki sont les ingrédients du composé i, et s'ils sont tous deux des composés (et non des matières premières), alors jiki, et l'ensemble des composés formant ji est disjoint de celui formant ki. 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 ji et ki 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 < ji, ki < i, pour tout i tel que 0 ≤ in-1.

Contraintes d'exécution

Utilisation mémoire maximum
1000 kilo-octets
Temps d'exécution maximum
500 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
5
-1 -2
-3 -4
-3 -2
1 2
3 0
Exemple de sortie
2
Commentaire

Ceci est l'exemple décrit ci-dessus.

Exemple d'entrée
4
-5 -4
-3 0
1 -2
-1 2
Exemple de sortie
1
Commentaire

Une réaction peut faire intervenir un composé d'une part et une matière première d'autre part.

1
2
3
4
0  -5 -4
1  -3 0
2  1 -2
3  -1 2