reflechis a une solution pour ce probléme sans utiliser sys je veux que tu utilise input…
- User
reflechis a une solution pour ce probléme sans utiliser sys je veux que tu utilise input pas readline : Énoncé Joseph est à deux pas de la forteresse ! Il ne reste plus qu'un pont à passer et il pourra enfin atteindre l'entrée. Malheureusement, certaines parties du pont menacent de s'effondrer car il est très vieux. Le scaphandre de Joseph est très lourd et cet objet le fatigue. Il veut éviter de s'épuiser afin d'arriver en bon état à la forteresse.
Le pont est un passage de mètres de long, qui alterne entre zones sûres et zones fragiles. On vous décrit le pont à l'aide d'un tableau de 0 et de 1 : un chiffre tous les mètres, un 0 décrit une position dans une zone sûre, un 1 décrit une position dans une zone fragile. Une zone sûre est donc représentée par un ou plusieurs 0 consécutifs, et une zone fragile par un ou plusieurs 1 consécutifs.
Lors de sa traversée, à chaque mètre, Joseph Nageant peut soit se déplacer en marchant, soit en nageant. Joseph Nageant doit traverser le tunnel en nageant dans toutes les zones de fragiles, pour éviter de faire s'écrouler le pont. Dans les zones sûres, il peut soit passer en nageant, soit en marchant.
Contrairement à l'exercice Passage Tout Juste, Joseph n'est pas obligé de marcher dans chaque zone sûre. Il peut cette fois-ci traverser une zone sûre dans son intégralité en nageant. En revanche, Joseph est obligé de marcher au moins une fois durant son parcours.
Cependant, Joseph dispose d'une certaine endurance qui lui permet de nager pendant au maximum mètres avant de devoir se remettre à marcher. Après avoir nagé, il est obligé de marcher pendant au minimum mètres avant d'entamer sa prochaine nage ou la fin du pont. (Joseph ne peut donc pas commencer une phase de marche pendant les derniers mètres.)
On appelle la force de Joseph la valeur de
. Aidez Joseph Nageant à trouver une stratégie de déplacement qui maximise sa force.
Entrée L’entrée contiendra :
Sur la première ligne, un entier : N, la longueur (en mètres) du pont. Sur la ligne suivante, une liste de N entiers séparés par des espaces : pont, le tableau représentant les zones sûres et les zones fragiles du pont. Un chiffre par mètre : Un 0 correspond à une position dans une zone sûre, et un 1 correspond à une position dans une zone fragile. Sortie Afficher la valeur de force maximale que Joseph Nageant peut obtenir en traversant le pont.
Contraintes Il y a toujours au moins une zone de repos Contraintes de performance Contraintes d'exécution Utilisation mémoire maximum 10000 kilo-octets Temps d'exécution maximum 500 millisecondes Exemples d'entrée/sortie Exemple d'entrée 9 1 0 1 0 0 0 1 1 1 Exemple de sortie 0 Commentaire Joseph Nageant est ici confronté à un pont d'une longueur de 9 mètres. Pour maximiser sa force, Joseph peut considérer une valeur d'endurance , et une valeur de repos .
parcours
Son parcours ressemblerait alors à : - D'abord, il nage par-dessus les deux premières zones fragiles sur trois mètres ( ); - Il effectue les trois mètres suivants, dans la seconde zone sûre, en marchant ( ); - Et finalement, il effectue les trois derniers mètres en nageant pour passer la dernière zone fragile ( ).
Cet exemple de parcours attribue à Joseph une force de . Il n'est pas possible de traverser le pont avec une plus grande force.
Exemple d'entrée 10 1 1 0 0 0 0 1 0 0 0 Exemple de sortie 1 Commentaire Joseph peut maximiser son score d'énergie avec et . Le score est alors . Notez que Joseph ne peut pas prendre comme valeur de repos , car il n'aurait pas le temps de conclure sa dernière phase de repos.
- Assistant
Il semble que le problème décrit nécessite des variables supplémentaires, notamment E (endurance) et R (repos), qui ne sont pas explicitement définies dans l'entrée. Pour fournir une solution complète, je vais faire les hypothèses suivantes :
-
Entrée :
- Première ligne : Entier
N, la longueur du pont. - Seconde ligne :
Nentiers (0 ou 1) représentant le pont. - Troisième ligne : Deux entiers
EetRreprésentant l'endurance et le repos de Joseph.
- Première ligne : Entier
-
Objectif :
- Maximiser la force
F = E - Rtout en respectant les contraintes de traversal du pont.
- Maximiser la force
Approche
-
Identifier les zones fragiles :
- Trouver la longueur maximale de zones consécutives de 1 (fragiles). Cette longueur définit le minimum que
Edoit être pour traverser ces zones.
- Trouver la longueur maximale de zones consécutives de 1 (fragiles). Cette longueur définit le minimum que
-
Déterminer
EetR:- E doit être au moins égal à la longueur maximale des zones fragiles.
- R doit être déterminé de manière à ce que, après chaque période de nage, Joseph puisse reposer suffisamment pour respecter les contraintes.
-
Calcul de la Force :
F = E - Rdoit être maximisé.
Implémentation en Python
Voici une implémentation possible en Python qui lit les entrées en utilisant
input()et calcule la force maximaleFselon les hypothèses ci-dessus :def max_force(N, bridge): # Trouver la longueur maximale des zones fragiles max_fragile = 0 current = 0 for pos in bridge: if pos == 1: current += 1 if current > max_fragile: max_fragile = current else: current = 0 E = max_fragile # Endurance minimale requise # Trouver le R minimal possible pour cet E # Pour simplifier, on peut supposer que R = 1 # Mais il faudrait vérifier si cela est possible # Ceci est une approximation et peut nécessiter une vérification plus approfondie R = 1 # Vérifier si avec E et R donnés, le pont peut être traversé # Implémentation détaillée de la vérification def can_traverse(E, R, bridge): N = len(bridge) i = 0 last_walk = -R # Dernier pas marché walked = False # Au moins un pas marché while i < N: if bridge[i] == 1: # Doit nager dans les zones fragiles swim_length = 0 while i < N and bridge[i] == 1 and swim_length < E: swim_length += 1 i += 1 if swim_length == 0: return False if swim_length > E: return False last_walk = i # Doit marcher après cela else: # Zone sûre, peut marcher ou nager # Pour maximiser F, on privilégie la nage swim_length = 0 start = i while i < N and bridge[i] == 0 and swim_length < E: swim_length += 1 i += 1 # Après avoir nagé, doit marcher au moins R last_walk_candidate = i # Vérifier si possible de marcher R mètres après if last_walk_candidate + R > N: # Ne peut pas marcher R mètres ici, donc opter pour marcher i = start walk_length = 0 while i < N and bridge[i] == 0 and walk_length < R: walk_length += 1 i += 1 if walk_length < R: return False walked = True last_walk = i else: # Peut nager et marcher si nécessaire # Pour simplifier, on suppose qu'on nage tout le possible walked = True # Au moins un pas marché return walked # Chercher le R minimal possible # Aller de R=1 jusqu'à une valeur raisonnable min_R = 1 while min_R <= N: if can_traverse(E, min_R, bridge): R = min_R break min_R += 1 F = E - R return F # Lecture des entrées def main(): N = int(input()) bridge = list(map(int, input().split())) # Si E et R sont fournis dans l'entrée, décommentez les lignes suivantes # E, R = map(int, input().split()) # F = E - R # Sinon, utiliser la fonction max_force pour déterminer F F = max_force(N, bridge) print(F) if __name__ == "__main__": main()Explications
-
Fonction
max_force:- Calcule la longueur maximale des zones fragiles pour déterminer l'endurance minimale
E. - Tente de déterminer le repos minimal
Ren vérifiant si le pont peut être traversé avec ces paramètres. - Retourne la force maximale
F = E - R.
- Calcule la longueur maximale des zones fragiles pour déterminer l'endurance minimale
-
Fonction
can_traverse:- Vérifie si, avec les valeurs actuelles de
EetR, Joseph peut traverser le pont. - Parcourt le pont en nageant dans les zones fragiles et en naviguant dans les zones sûres en fonction des contraintes.
- Vérifie si, avec les valeurs actuelles de
-
Lecture des Entrées :
- Utilise
input()pour lire les données d'entrée. - Vous pouvez ajuster la lecture de
EetRselon la définition exacte du problème.
- Utilise
Remarques
- Hypothèses : Comme les variables
EetRne sont pas clairement définies dans l'entrée, cette solution fait des hypothèses sur leur détermination. - Optimisation : Cette implémentation est une approche de base et peut nécessiter des optimisations pour gérer des entrées plus grandes ou des cas spécifiques.
- Clarifications : Il serait utile d'avoir une définition plus précise des entrées, notamment si
EetRsont fournis ou doivent être déterminés.
Si vous avez des précisions supplémentaires sur le problème ou les entrées, n'hésitez pas à les fournir pour une solution plus précise.
-