Accélerer l'éxécution [Résolu]

Messages postés
13
Date d'inscription
dimanche 7 février 2016
Statut
Membre
Dernière intervention
15 mars 2018
-
bonjour
j'ai essayé de faire ce petit programme
while(n>0){
n=n-jour;
if(n>0) {n=n+m;jour++;}
if(n>nini) n=nini;


}

et je veux qu'il s'éxécute en 1s maximum le n et le m sont entrez par l'utilisateur et elle peut prend de 1 jusqu'à 10^18 le probléme quand le n et le m grand le programme prend beaucoup de temp pour s'éxécuter j'ai essayé d'utiliser les thread mais ca change rien si il ya une solution merci d'avance
Afficher la suite 

Votre réponse

1 réponse

Messages postés
15989
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
22 mai 2019
84
0
Merci
Bonjour,

À quoi sert ton programme ?

"le n et le m sont entrez par l'utilisateur"
jour et nini correspondent à quoi ?

Tu as des exemples d'exécution ?
SMM@
Messages postés
13
Date d'inscription
dimanche 7 février 2016
Statut
Membre
Dernière intervention
15 mars 2018
-
mon programme est un solution pour ce problème
http://codeforces.com/problemset/problem/785/C

voici le programme complet

import java.util.Scanner;

public class C785 {

public C785() {
Scanner in=new Scanner(System.in);
Long n,m,nini;

Long jour=1L;
n=in.nextLong();
m=in.nextLong();
nini=n;
if(n==m) System.out.println(n);
else{
while(n>0)

{
n=n-jour;
if(n>0) {n=n+m;jour++;}
if(n>nini) n=nini;
}
System.out.println(jour);
}
}
public static void main(String[] args) {
new C785();

}

}

par exemple j'entre 5 1 et il m'affiche 4
merci pour ta réponse
KX
Messages postés
15989
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
22 mai 2019
84 -
Ce problème peut se résoudre sans boucle. Il faut cependant le traiter de manière mathématiques pour calculer le résultat exact.

Il faut distinguer deux périodes dans l'histoire :

1) dans les M premiers jours, il y a moins de M oiseaux, donc vu que l'on ramène M graines pour remplir la grange elle sera toujours pleine au moment où les oiseaux viennent manger.

2) après les M premiers jours, les oiseaux étant plus nombreux, ils mangent plus que ce qui n'est ramené chaque jour et on perd X graines au jour M+X

Cela revient donc à perdre 1+2+3+4+...+X qui vaut X(X+1)/2
Voir : Somme des premiers entiers

Au jour M+X où la grange devient vide on a donc N <= X(X+1)/2

De là on doit donc résoudre l'équation X(X+1)/2=N pour trouver X, ce qui donne X=√(8N+1)/2-1/2

Evidemment tout cela reste à vérifier, mais en tout cas il faut oublier ta boucle, la solution à ton problème est mathématique, pas informatique.
Commenter la réponse de KX