Par exemple, si le programme du robot est SCCSSC, alors le
robot effectue les actions suivantes :Pour tous les exercices de cette session, on vous fournit un fichier
squelette SessionB.java.
Les objectifs sont, dans l’ordre, que le code soit
correct, que le code soit efficace et
que le code soit lisible. Des tests unitaires
sont fournis dans SessionBTest.java.
Vous devez être attentifs à la quantité de mémoire nécessaire à votre programme et vous avez le droit d’utiliser toutes les caractéristiques de l’entrée (elles sont indiquées pour chaque exercice) pour concevoir un code efficace.
On donne une chaîne composée de lettres majuscules de l’alphabet. Il est possible de mettre en surbrillance n’importe quel nombre de lettres, éventuellement toutes ou aucune. Les lettres mises en surbrillance n’ont pas besoin d’être consécutives. Ensuite, on produit une nouvelle chaîne en traitant les lettres de gauche à droite : les lettres non surlignées sont ajoutées une seule fois à la nouvelle chaîne, tandis que les lettres surlignées y sont ajoutées deux fois.
Par exemple, si la chaîne initiale est HELLOWORLD, on
peut mettre en surbrillance le H, le premier et le dernier
L, ainsi que le dernier O, pour obtenir
HHELLLOWOORLLD. De même, si aucune lettre n’est surlignée,
on obtient HELLOWORLD, et si toutes les lettres sont
surlignées, on obtient HHEELLLLOOWWOORRLLDD. Remarquer que
chaque occurrence d’une même lettre peut être surlignée indépendamment
des autres.
Étant donnée une chaîne, plusieurs chaînes peuvent être obtenues par
ce procédé, selon le choix des lettres mises en surbrillance. écrivez la
méthode doubleOrOneThing qui, parmi toutes ces chaînes,
renvoie celle qui apparaît en premier dans l’ordre alphabétique (aussi
appelé ordre lexicographique).
Remarque : une chaîne s apparaît avant une chaîne
différente t dans l’ordre alphabétique si s
est un préfixe de t, ou bien si, à la première position où
s et t diffèrent, la lettre de s
apparaît plus tôt dans l’alphabet que celle de t. Par
exemple, les chaînes suivantes sont dans l’ordre alphabétique :
CODE, HELLO, HI,
HIM, HOME, JAM.
public static String doubleOrOneThing(String sequence)Caractéristiques des fichiers de test :
La longueur maximale d’un chaînes est 100.
Exemples :
PEEL --> PEEEEL
AAAAAAAAAA --> AAAAAAAAAA
CODEJAMDAY --> CCODDEEJAAMDAAYDans le premier exemple, voici toutes les chaînes pouvant être
obtenues, dans l’ordre alphabétique : PEEEEL,
PEEEELL, PEEEL, PEEELL,
PEEL, PEELL, PPEEEEL,
PPEEEELL, PPEEEL, PPEEELL,
PPEEL, et PPEELL.
Dans le deuxième exemple, toutes les chaînes possibles ne contiennent que des A. La plus courte est la première dans l’ordre alphabétique, car elle est préfixe de toutes les autres.
Dans le troisième exemple, il existe 1024 chaînes possibles générées
à partir de CODEJAMDAY, parmi lesquelles
CCODDEEJAAMDAAY est la plus petite au sens
lexicographique.
Source: https://dmoj.ca/problem/gcj22r1aa
Étant donnée une chaîne de chiffres S, il faut insérer un nombre minimal de parenthèses ouvrantes et fermantes de sorte que :
La profondeur d’imbrication d’une position est le nombre de paires de parenthèses appariées qui l’entourent. Par exemple, les chaînes suivantes respectent la contrainte “chiffre = profondeur” :
• 0((2)1)
• (((3))1(2))
• ((((4))))
• ((2))((2))(1) Cependant, toutes ne sont pas minimales. Par exemple, pour les
chiffres 221, la chaîne ((22)1) est plus courte que ((2))((2))(1).
Écrire la fonction nestingDepth qui, étant donnée une
séquence de chiffres calcule la séquence parenthésée définie
ci-dessus.
public static String nestingDepth(String sequence)Caractéristiques des fichiers de test :
La longueur maximale d’un chaînes est 100.
Exemples :
0000 --> 0000
1011 --> (1)0(11)
111020 --> (111)0((2))0
2 --> ((2))Les chaînes (1)0((()1) et (1)0(1)(1) ne
sont pas valides parce qu’elles ne sont pas de longueur minimale. De
plus, 1)( et )(1 ne sont pas des solutions
valides car elles contiennent des parenthèses non appariées.
Source: https://dmoj.ca/problem/gcj20qrb
Un robot extra-terrestre menace l’univers à l’aide d’un rayon laser ultra puissant qui peut tout détruire. Il faut l’arrêter !
Heureusement, le fonctionnement du robot est connu. Il commence avec un rayon de puissance 1, puis exécute un programme constitué d’une suite d’instructions, traitées une par une, de gauche à droite. Chaque instruction est :
C (pour charge) : double la puissance du
rayon ;S (pour shoot) : tire avec le rayon, en
infligeant des dégâts égaux à la puissance actuelle du rayon.
Par exemple, si le programme du robot est SCCSSC, alors le
robot effectue les actions suivantes :
Dans ce cas, le programme inflige donc un total de 9 dégâts.
Les meilleurs scientifiques de l’univers ont développé un bouclier capable de résister à un total maximal de D dégâts. Mais le programme actuel du robot peut infliger davantage de dégâts lorsqu’il sera exécuté.
Vous vous êtes porté volontaire pour aller dans l’espace pirater le
programme du robot avant son exécution. La seule manière de le pirater
(sans que le robot ne s’en aperçoive) consiste à échanger deux
instructions adjacentes. Par exemple, vous pourriez pirater une fois le
programme ci-dessus en échangeant les troisième et quatrième
instructions pour obtenir SCSCSC. Cela réduirait le total
des dégâts à 7.
Ensuite, par exemple, vous pourriez pirater à nouveau le programme
pour obtenir SCSSCC, réduisant les dégâts à 5, et ainsi de
suite.
Afin de ne pas éveiller les soupçons du robot, il ne faut pas
effectuer trop de piratages. Quel est le plus petit nombre
possible de piratages permettant de garantir que le programme
n’inflige pas plus de D dégâts au total, si cela
est possible ? Écrire la fonction saveTheUniverse qui,
étant donnés la valeur de dégâts maximale et le programme du robot,
calcule ce nombre de piratages.
public static int saveTheUniverse(long damage, String program)La valeur renvoyée est soit le nombre minimal de piratages nécessaires pour atteindre l’objectif, soit -1 si cela ne peut pas être fait.
Caractéristiques des fichiers de test :
La première ligne de l’entrée contient le nombre de cas de test,
T.
Les T cas de test suivent.
Chacun est constitué d’une ligne contenant le nombre maximal de dégâts
que le bouclier peut encaisser, suivi du programme du robot.
DIFFICULTÉ Niv. 1
Valeur de dommages maximale: 10^9
Longueur du programme du robot max: 30
Le programme du robot contient soit zéro, soit un seul caractère 'C'.
DIFFICULTÉ Niv. 2
Valeur de dommages maximale: 10^9
Longueur du programme du robot max: 30
Le programme du robot peut contenir plusieurs caractères 'C'.
DIFFICULTÉ Niv. 3
Valeur de dommages maximale: 10^9
Longueur du programme du robot max: 30
Le programme du robot peut contenir plusieurs caractères 'C'.Exemples :
6
1 CS --> 1
2 CS --> 0
1 SS --> -1
6 SCCSSC --> 2
2 CC --> 0
3 CSCSS --> 5Dans le cas n°1, on peut échanger les deux instructions pour réduire les dégâts totaux à 1, ce que le bouclier peut supporter.
Dans le cas n°2, on n’a pas besoin de pirater le programme du tout, puisque le bouclier peut déjà résister aux 2 dégâts totaux qu’il provoquera.
Dans le cas n°3, le programme infligera plus de dégâts que le bouclier ne peut en supporter, et le piratage ne changera rien à cela. L’univers est condamné.
Le cas n°4 utilise le programme décrit dans l’énoncé. Celui-ci montre une manière de réduire les dégâts à 5 en utilisant deux piratages. Il n’est pas possible de réduire les dégâts à 6 ou moins avec un seul piratage ; rappelons que l’on ne peut échanger que des instructions adjacentes.
Dans le cas n°5, le robot ne tirera jamais, et n’infligera donc jamais aucun dégât. Aucun piratage n’est nécessaire.
Dans le cas n°6, cinq piratages sont requis. Remarquez que même si deux piratages échangent les instructions aux mêmes deux positions, ils comptent tout de même comme deux piratages distincts.
Source: https://dmoj.ca/problem/gcj18qra
StreamPour chaque exercice de la premières partie, lorsque c’est possible
et si la complexité est la même (en temps et en mémoire), réécrire le
code en utilisant des Stream.