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

Signaler
Messages postés
13
Date d'inscription
dimanche 7 février 2016
Statut
Membre
Dernière intervention
15 mars 2018
-
 SMM@ -
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

1 réponse

Messages postés
16104
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
24 janvier 2020
88
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
16104
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
24 janvier 2020
88
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.
Merci bq merci merci :)