Lors de la mise en œuvre d'un circuit pour un robot, vous remarquez certaines anomalies. Il existe $N = 128$ programmes, numérotés de $0$ à $N-1$, que le robot peut exécuter. Normalement, un seul programme (parmi les $N$ programmes) devrait être en cours d'exécution à tout moment. Cependant, pour des raisons inconnues, il arrive que exactement trois programmes s'exécutent simultanément. Heureusement, en tant que programmeur expérimenté, vous savez comment gérer cette situation et décidez de mettre en œuvre un circuit pour détecter de telles anomalies.
Vous créez d'abord $N$ entrées. La $i$-ième entrée est $0$ si le $i$-ième programme n'est pas en cours d'exécution, et $1$ sinon. Ensuite, vous ajoutez des portes logiques, dont les indices sont numérotés consécutivement à partir de $N$. Chaque porte peut prendre un certain nombre d'entrées et produire une seule sortie, soit $0$, soit $1$. Les entrées de la $i$-ième porte peuvent être la sortie de n'importe quelle porte dont l'indice est inférieur à $i$, ou l'une des $N$ entrées initiales.
Il existe trois types de portes :
NOT: prend exactement une entrée. La sortie est $1$ si l'entrée est $0$, et $0$ sinon.OR: prend exactement deux entrées. La sortie est $0$ si les deux entrées sont $0$, et $1$ sinon.AND: prend exactement deux entrées. La sortie est $1$ si les deux entrées sont $1$, et $0$ sinon.
La sortie de la dernière porte doit être $1$ si une anomalie est détectée — c'est-à-dire si exactement trois des $N$ premières entrées sont $1$ — et $0$ si exactement une des $N$ premières entrées est $1$.
Il est garanti que le nombre de $1$ parmi les $N$ premières entrées est soit exactement un, soit exactement trois.
Détails d'implémentation
Vous devez écrire dans un fichier de sortie la description d'un circuit valide pour $\color{red}{N = 128}$.
La première ligne de la sortie doit contenir un entier représentant le nombre de portes utilisées.
Chaque ligne du reste de la sortie doit respecter l'un des trois formats suivants :
NOT in_1 OR in_1 in_2 AND in_1 in_2
Chacune ajoute respectivement une porte NOT, OR ou AND. Pour NOT, in_1 est l'indice de l'entrée de la porte. Pour OR et AND, in_1 et in_2 sont les indices des entrées de la porte. L'indice de la porte ajoutée à la $i$-ième ligne après la première ligne est $N-1 + i$.
Le nombre total de portes ne doit pas dépasser $1024$. En d'autres termes, le nombre total de lignes dans le fichier de sortie ne doit pas dépasser $1025$.
Sous-tâches
- (100 points) Aucune contrainte supplémentaire.
Scoring
Pour chaque sous-tâche, si le circuit ne passe pas un cas de test, votre score sera de $0$.
Sinon, soit $K$ le nombre de portes utilisées par le circuit. Votre score sera $f(K) \times$ [le score de la sous-tâche], où :
$$f(K) = \begin{cases} 0 & 1024 < K \\ 0.3 - 0.1 \times \frac {K - 384}{896} & 384 < K \le 1024 \\ 0.6 - 0.3 \times \frac {K - 256}{128} & 256 < K \le 384 \\ 1 - 0.40 \times \frac{K - 215}{41} & 215 < K \le 256 \\ 1 & K \le 215 \end{cases}$$
Figure 1 : Le score pour la tâche pour chaque valeur de K
Vous devez écrire votre solution dans le fichier de sortie 1.out, puis compresser les fichiers de sortie dans un seul fichier .zip et soumettre ce fichier .zip.
Exemples
Entrée 1
(input data)
Sortie 1
3 OR 0 1 OR 2 3 AND 4 5
Remarque
Considérez une version simplifiée de la tâche avec $N = 4$ (Notez que vous n'avez besoin de fournir la solution que pour $N = 128$). Une solution possible consiste à construire le circuit suivant :
Le circuit possède :
- la porte $4$ qui produit $1$ si au moins l'une des entrées $0$ ou $1$ est $1$ ;
- la porte $5$ qui produit $1$ si au moins l'une des entrées $2$ ou $3$ est $1$ ; et
- la porte $6$ qui produit $1$ si les sorties des portes $4$ et $5$ sont toutes deux $1$.
On peut vérifier que pour toutes les entrées possibles, le circuit donne la réponse correcte.