Courant Parfait – Épreuve régionale 2023

Niveau 7

Énoncé

Assez sûr de la date actuelle, Valérian encode le déplacement final vers le présent, et actionne la machine. Nos amis arrivent pile dans leur atelier, d’où ils sont partis ! Victoire ! Après un court repos autour d’un goûter bien mérité, Julie s’exclame alors : « Et si on allait dans le futur ? » Cependant, cela est bien plus fastidieux qu’il n’y paraît, car il faut réunir des conditions très précises pour pouvoir explorer sans risque une temporalité que personne n’a encore découvert.

Dans les circuits électroniques soigneusement montés par Cyril, il existe K transistors, numérotés de 1 à K. Chaque transistor, s'il est actif, peut multiplier le courant par son numéro. (Le transistor 2 multiplie le courant par 2 s'il est actif, par exemple).

Dans le circuit, Cyril a positionné N fils alignés, reliés d'une certaine manière aux transistors. Chaque fil porte une étiquette avec un numéro entre 1 et K correspondant au transistor du même numéro. Plusieurs fils peuvent posséder le même numéro. Chaque fil peut être actif ou inactif. Les N valeurs écrites sur les étiquettes sont répertoriées dans la liste S.

La machine possède seulement deux potentiomètres x et y permettant de contrôler lesquels des N fils sont actifs ou non. Les deux potentiomètres peuvent être positionnés sur deux valeurs entières ($1 \leq x \leq y \leq N$), et tous les fils entre les positions x et y seront actifs (et seulement ceux-ci). Par exemple, si $N = 5, x = 2$ et $y = 4$, alors les fils 2, 3 et 4 seront actifs, et les fils 1 et 5 seront inactifs.

Enfin, chaque transistor $i$ possède deux bornes $A_i$ et $B_i$. Un transistor $i$ est actif si et seulement si le nombre de fils numérotés par $i$ étant actifs est compris entre $A_i$ et $B_i$ (bornes incluses).

Le courant d'entrée étant d'un milliampère, le courant de sortie est donc le produit des numéros des transistors actifs, en milliampères. L'objectif, pour pouvoir envoyer la machine dans le futur avec précision, est d'obtenir un courant de sortie de précisément C milliampères.

Aidez Cyril à déterminer le nombre exact de couples $(x, y)$ qui permettent d'obtenir un courant de sortie d'exactement C milliampères !

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : C, le courant idéal.
  • Sur la ligne suivante, un entier : K, le nombre de transistors.
  • Sur la ligne suivante, un entier : N, le nombre de fils reliés aux transistors.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : S, la liste des valeurs affichées sur les étiquettes de chaque fil.
  • Sur les lignes suivantes, une liste de K éléments : potentiometres, la liste des bornes d'activations des transistors.
    • Une ligne par élément de la liste : séparés par des espaces, un entier A (la borne inférieure (inclusive) d'activation du transistor), et un entier B (la borne supérieure (inclusive) d'activation du transistor).

Sortie

Afficher, sur une ligne, le nombre exact de couples de valeurs des deux potentiomètres permettant d'obtenir un courant de sortie égal à C.

Contraintes

  • $1 \le C \le 1000$
  • $1 \le K \le 500$
  • $1 \le N \le 500$
  • $1 \le S_i \le K$
  • $0 \le A \le B \le N$

Contraintes de performance

  • $1 \le K \le 10\,000$
  • $1 \le N \le 10\,000$

Contraintes d'exécution

Utilisation mémoire maximum
20000 kilo-octets
Temps d'exécution maximum
2000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
6
3
10
3 1 1 2 3 3 1 3 3 2
1 2
1 1
0 1
Exemple de sortie
9
Commentaire
  • Pour rendre le transistor 1 actif, il faut que le nombre de fils étiquetés "1" actifs soit compris entre 1 et 2.
  • Pour rendre le transistor 2 actif, il faut qu'il y ait précisément 1 fil actif étiqueté avec un 2.
  • Pour rendre le transistor 3 actif, il faut qu'il y ait 0 ou 1 fil actif étiqueté avec un 3.

Il existe 9 paires d'entier ($x$, $y$) qui permettent d'obtenir un courant total de 6 milliampères:

  • (1, 4) : les fils actifs sont étiquetés 3 1 1 2, cela active les transistors 1, 2 et 3 ;
  • (2, 4) : les fils actifs sont étiquetés 1 1 2, cela active les transistors 1, 2 et 3 ;
  • (2, 5) : les fils actifs sont étiquetés 1 1 2 3, cela active les transistors 1, 2 et 3 ;
  • (3, 4) : les fils actifs sont étiquetés 1 2, cela active les transistors 1, 2 et 3 ;
  • (3, 5) : les fils actifs sont étiquetés 1 2 3, cela active les transistors 1, 2 et 3 ;
  • (4, 4) : le fil actif est étiqueté 2, cela active les transistors 2 et 3 ;
  • (4, 5) : les fils actifs sont étiquetés 2 3, cela active les transistors 2 et 3 ;
  • (9, 10) : les fils actifs sont étiquetés 3 2, cela active les transistors 2 et 3 ;
  • (10, 10) : le fil actif est étiqueté 3, cela active les transistors 2 et 3.
Exemple d'entrée
24
6
9
2 3 4 6 5 2 3 4 6
2 4
1 1
1 2
1 3
1 2
0 0
Exemple de sortie
4
Commentaire
  • Il n'est ici pas possible de rendre actif le transistor 1.
  • Pour activer le transistor 2, il faut que précisément un fil étiqueté "2" soit actif.
  • Pour activer le transistor 3, il faut qu'au moins l'un des deux fils étiquetés "3" soit actif.
  • Pour activer le transistor 4, il faut qu'au moins l'un des deux fils étiquetés "4" soit actif.
  • Pour activer le transistor 5, il faut que le fil étiqueté "5" soit actif.
  • Pour activer le transistor 6, il faut que le fil étiqueté "6" ne soit pas actif.

Il existe donc au total 4 paires d'entier ($x$, $y$) qui permettent d'obtenir le courant désiré de 24 milliampères :

  • (1, 4) : les fils actifs sont étiquetés 2 3 4 6, ce qui active les transistors 2, 3 et 4 ;
  • (3, 3) : le seul fil actif est étiqueté 4, ce qui active les transistors 4 et 6 ;
  • (6, 9) : les fils actifs sont étiquetés 2 3 4 6, ce qui active les transistors 2, 3 et 4 ;
  • (8, 8) : le seul fil actif est étiqueté 4, ce qui active les transistors 4 et 6.

Notez que, pour certains couples ($x$, $y$) distincts, les étiquettes des fils actifs sont identiques. Cependant, ils sont tout de même comptés comme deux combinaisons valides distinctes.