Concours de programmation

Concours de programmation - Java - Programmation

Marsh Posté le 20-12-2019 à 14:16:37    

Bonjour,

 

j'ai résolu un exercice sur un site de programmation et concours dont l'énoncé est la suivant.

 

Énoncé:

 

On vous donne une liste de nombres tous différents. Ces nombres vous sont donnés du plus petit au plus grand.

 

Écrivez un programme qui trouve et affiche deux nombres distincts parmi cette liste, dont la somme vaut 42 000 000. On vous garantit que ces deux nombres existent

 

Dans cet exercice, votre programme doit être rapide pour valider tous les tests. En particulier, si vous énumérez toutes les possibilités de deux nombres, vous ne pourrez obtenir que la moitié des points disponibles pour ce sujet.

 

Entrée
La première ligne de l'entrée contient un entier nbNombres, le nombre d'éléments de la liste, entre 1 et 20 000.

 

Les nbNombres lignes suivantes contiennent chacune un élément de la liste, un nombre entier entre 0 et 42 000 000. Les nombres sont donnés du plus petit au plus grand.

 

Sortie
Vous devez afficher deux nombres différents, chacun sur une ligne : les deux éléments de la liste à additionner pour obtenir 42 000 000, en commençant par le plus petit.

 

Exemples
Voici un exemple d'entrée.

 

6
271
4321
8754
999999
41995679
41998154

 

La sortie attendue est la suivante.

 

4321
41995679

 


Voici mon programme qui fonctionne parfaitement et passe 8 tests sur 10 (car en fait il est lent!) l'objectif est de résoudre l'exercice avec un algo optimisé et rapide à l'exécution sans tester toutes les combinaisons possible ce que mon programme fait hélas.

 
Code :
  1. class Main { 
  2.    static Scanner input = new Scanner(System.in);
  3.    public static void main(String[] args) {
  4.     int nbNombres = input.nextInt();
  5.     int[] liste = new int[100];
  6.     int somme = 0;
  7.     boolean trouve = false;
  8.     int valPetit = 0;
  9.     int valGrand = 0;
  10.     int cPair = 0;
  11.     int cImpair = 0;
  12.     for(int i = 0; i < nbNombres; i++){
  13.       liste[i] = input.nextInt();
  14.     }
  15.     for(int i = 0; i < nbNombres; i++){
  16.       for(int j = i + 1; j < nbNombres; j++){
  17.         if((liste[i] % 2 != 0 && liste[j] % 2 != 0) || (liste[i] % 2 == 0 && liste[j] % 2 == 0) ){
  18.            somme = liste[i] + liste[j];
  19.            if(somme != 42000000){
  20.               somme = 0;
  21.            }else{
  22.               valPetit = liste[i];
  23.               valGrand = liste[j];
  24.               trouve = true;
  25.               break;
  26.               }
  27.            }
  28.         }
  29.      }
  30.     if(trouve){
  31.       System.out.println(valPetit);
  32.       System.out.println(valGrand);
  33.     }
  34.    }
  35.    
  36.    }
 

Une idée pour rendre mon programme plus rapide?

 


Message édité par Nat1329 le 20-12-2019 à 14:18:04
Reply

Marsh Posté le 20-12-2019 à 14:16:37   

Reply

Marsh Posté le 20-12-2019 à 14:55:47    

Je ne suis pas un spécialiste en algorithmie, loin s'en faut, mais déjà si tu supprimes le j déjà effectué à la fin de la boucle i, tu affines ta recherche au fur et a mesure.
 
Je sais pas si je suis clair mais quand tu a fait (avec les chiffres de ton exemple) toutes les tentatives avec 271, il faut le supprimer des choix possible dans ta 2eme boucle for (si 271 et 4321 ne vont pas ensemble, 4321 et 271 n'iront pas mieux).
 
Après c'est de la logique de base, y'a surement des manières de procédé (je le dit au hasard, encore une fois c'est pas mon domaine), ou en alternant +petit et +grand chiffre, ou en partant du milieu vers les extrémités, ce genre de chose, je penses que le fait qu'on connaisse la somme et un indice sur l'algo à utiliser...
 
https://www.google.com/search?q=alg [...] +une+somme
 
Bon courage à toi !


Message édité par mechkurt le 20-12-2019 à 14:56:25

---------------
D3
Reply

Marsh Posté le 20-12-2019 à 14:59:55    

Oh mon dieu, que je suis bête, pourquoi faire une seule liste, faits en 2 ce sera dejà 2 fois plus efficace !
 
...besoin de vacances moi. ^^


---------------
D3
Reply

Marsh Posté le 20-12-2019 à 16:12:55    

Tu peux tenter un algorithme LPT ;) Vu que c'est une somme que de 2 nombres, c'est très facile à optimiser. Tu prend le premier plus grand nb, on va l'appeler GNB1. Tu fais 42000000 - GNB1 = Reste1
Tu cherches dans la liste si un nb correspond exactement à Reste1. Si c'est pas le cas, tu prends le 2ème plus grand nombre GNB2 et tu recommence : 42000000 - GNB2 = Reste2
...


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
Reply

Marsh Posté le 21-12-2019 à 01:53:35    

Perso, en supposant les données passées au programme en argument (l'énoncé n'est pas clair, mais c'est facile a adapter avec un scanner si donné dans un fichier ou tapé interactivement) j'aurais fait ainsi :

Code :
  1. public class Main {
  2.  
  3.    public static void main(String[] args) {
  4.        int entriesNb = Integer.parseInt(args[0]);
  5.        int[] entries = new int[entriesNb + 1];
  6.        for (int i = 1; i <= entriesNb; ++i) {
  7.            entries[i] = Integer.parseInt(args[i]);
  8.        }
  9.  
  10.        int i = 1;
  11.        int j = entriesNb;
  12.        int goal = 42000000;
  13.        while (entries[i] + entries[j] != goal) {
  14.            if (entries[i] + entries[j] > goal) {
  15.                while (entries[i] + entries[--j] > goal);     // Tant qu'on dépasse, il faut diminuer le plus grand nombre
  16.            } else if (entries[i] + entries[j] < goal) {
  17.                while (entries[++i] + entries[j] < goal);     // Tant qu'on manque, il faut augmenter le plus petit nombre
  18.            }
  19.        }
  20.        System.out.println(entries[i]);
  21.        System.out.println(entries[j]);
  22.    }
  23. }


 
Après, si on veut un code robuste qui supporte des données sans solution (on est en dehors de l'énoncé, et plus près de la vraie vie) on peut faire :

Code :
  1. public class Main {
  2.  
  3.    public static void main(String[] args) {
  4.        int entriesNb = Integer.parseInt(args[0]);
  5.        int[] entries = new int[entriesNb + 1];
  6.        for (int i = 1; i <= entriesNb; ++i) {
  7.            entries[i] = Integer.parseInt(args[i]);
  8.        }
  9.  
  10.        int i = 1;
  11.        int j = entriesNb;
  12.        int goal = 42000000;
  13.        while ((entries[i] + entries[j] != goal) && (i < j)) {
  14.            if (entries[i] + entries[j] > goal) {
  15.                // Tant qu'on dépasse, il faut diminuer le plus grand nombre
  16.                while ((entries[i] + entries[--j] > goal) && (i < j));
  17.            } else if (entries[i] + entries[j] < goal) {
  18.                // Tant qu'on manque, il faut augmenter le plus petit nombre
  19.                while ((entries[++i] + entries[j] < goal) && (i < j));
  20.            }
  21.        }
  22.        if ((i < j) && (entries[i] + entries[j] == goal)) {
  23.            System.out.println(entries[i]);
  24.            System.out.println(entries[j]);
  25.        } else {
  26.            System.out.println("Pas de solution pour une somme de "+ goal);
  27.        }
  28.    }
  29. }


(Dans la vraie vie, les données seront en vrac, il faudra d'abord les trier, et il y a Arrays.sort pour cela)
 
A+,

Message cité 1 fois
Message édité par gilou le 21-12-2019 à 10:48:52

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 21-12-2019 à 09:08:05    

Gilou, l'énoncé indique que les données sont déjà triées dans l'ordre croissant, ce qui fait gagner du temps d'exécution.
Du coup, ton algo ressemble pas mal un mon algo LPT je trouve vu que tu pars des 2 extrémités du tableau.


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
Reply

Marsh Posté le 21-12-2019 à 10:44:56    

Oui, je l'avais précisé : on est en dehors de l'énoncé
Pour l'algo, ça y a y ressemblerait si tu précisais dans ton texte que quand tu cherches dans la liste si un nb correspond exactement à Reste2, tu peux partir de la position précédente.
A+,


Message édité par gilou le 21-12-2019 à 10:46:27

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 21-12-2019 à 11:33:26    

tres bien, merci je vais essayer les solutions que vous proposez voir ce que ca donne et vous tenir au courant!

Reply

Marsh Posté le 21-12-2019 à 12:02:25    

Bonjour,
 
Tes algos ne sont pas bon du tout en performance et en vitesse d'exécution.
 
j'ai testé tes deux codes mais aucun ne fonctionne sur le site, il passe 0 test sur 10 et le programme est super lent.(Accès mémoire invalide).
 
Je les ai ensuite testé sur Eclipse et il se trouve qu'il compile deux fois plus lentement que le mien. Je pense que la technique de cette algo est a revoir.
 
Je teste d'autres solutions en ce moment
 

gilou a écrit :

Perso, en supposant les données passées au programme en argument (l'énoncé n'est pas clair, mais c'est facile a adapter avec un scanner si donné dans un fichier ou tapé interactivement) j'aurais fait ainsi :

Code :
  1. public class Main {
  2.  
  3.    public static void main(String[] args) {
  4.        int entriesNb = Integer.parseInt(args[0]);
  5.        int[] entries = new int[entriesNb + 1];
  6.        for (int i = 1; i <= entriesNb; ++i) {
  7.            entries[i] = Integer.parseInt(args[i]);
  8.        }
  9.  
  10.        int i = 1;
  11.        int j = entriesNb;
  12.        int goal = 42000000;
  13.        while (entries[i] + entries[j] != goal) {
  14.            if (entries[i] + entries[j] > goal) {
  15.                while (entries[i] + entries[--j] > goal);     // Tant qu'on dépasse, il faut diminuer le plus grand nombre
  16.            } else if (entries[i] + entries[j] < goal) {
  17.                while (entries[++i] + entries[j] < goal);     // Tant qu'on manque, il faut augmenter le plus petit nombre
  18.            }
  19.        }
  20.        System.out.println(entries[i]);
  21.        System.out.println(entries[j]);
  22.    }
  23. }


 
Après, si on veut un code robuste qui supporte des données sans solution (on est en dehors de l'énoncé, et plus près de la vraie vie) on peut faire :

Code :
  1. public class Main {
  2.  
  3.    public static void main(String[] args) {
  4.        int entriesNb = Integer.parseInt(args[0]);
  5.        int[] entries = new int[entriesNb + 1];
  6.        for (int i = 1; i <= entriesNb; ++i) {
  7.            entries[i] = Integer.parseInt(args[i]);
  8.        }
  9.  
  10.        int i = 1;
  11.        int j = entriesNb;
  12.        int goal = 42000000;
  13.        while ((entries[i] + entries[j] != goal) && (i < j)) {
  14.            if (entries[i] + entries[j] > goal) {
  15.                // Tant qu'on dépasse, il faut diminuer le plus grand nombre
  16.                while ((entries[i] + entries[--j] > goal) && (i < j));
  17.            } else if (entries[i] + entries[j] < goal) {
  18.                // Tant qu'on manque, il faut augmenter le plus petit nombre
  19.                while ((entries[++i] + entries[j] < goal) && (i < j));
  20.            }
  21.        }
  22.        if ((i < j) && (entries[i] + entries[j] == goal)) {
  23.            System.out.println(entries[i]);
  24.            System.out.println(entries[j]);
  25.        } else {
  26.            System.out.println("Pas de solution pour une somme de "+ goal);
  27.        }
  28.    }
  29. }


(Dans la vraie vie, les données seront en vrac, il faudra d'abord les trier, et il y a Arrays.sort pour cela)
 
A+,


Reply

Marsh Posté le 21-12-2019 à 18:00:03    

Salut
 
C'est sur codingame ?  Tu peux mettre un lien vers le truc ?


---------------
Mes apps  |  Viens coder  |  Mon topal de vente
Reply

Marsh Posté le 21-12-2019 à 18:00:03   

Reply

Marsh Posté le 21-12-2019 à 19:42:44    

> Tes algos ne sont pas bon du tout en performance et en vitesse d'exécution.
> j'ai testé tes deux codes mais aucun ne fonctionne sur le site, il passe 0 test sur 10 et le programme est super lent.(Accès mémoire invalide).  
Arf! Ils vont deux fois plus vite que les tiens (et sur un échantillon aussi faible, 6 nb, on voit pas les problèmes du tien, mais il suffirait qu'on passe a un échantillonnage de 20 ou 30 nombres et la, ça va être bien pire, vu que mon algo est linéaire en nb d'échantillons)
Il compile et marche parfaitement sous IntelliJ, qui me signalerait un accès mémoire invalide....
 
Comme je t'ai dit, j'ai passé les données via la ligne de commande, c'est peut être cela que ton site ne sait pas gérer (ou que tu n'as pas configuré) et cela expliquerait le message d'erreur reçu.
Si tu tapes les nombres au fur et a mesure de l’exécution du programme, pourquoi pas, mais c'est pas terrible.
il suffit de remplacer le début par

Code :
  1. public class Main {
  2.    static Scanner input = new Scanner(System.in);
  3.  
  4.    public static void main(String[] args) {
  5.        int entriesNb = input.nextInt();
  6.        int[] entries = new int[entriesNb + 1];
  7.        for (int k = 1; k <= entriesNb; ++k) {
  8.            entries[k] = input.nextInt();
  9.        }


A+,
 
 
 


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 21-12-2019 à 21:24:49    

Salut.

 

Tu peux tenter d'essayer et faire des modifs sur l'exercice qui se trouve au lien suivant https://concours.algorea.org/conten [...] 95141437/.

 

Le.probleme est qu'il faut valider les 5 exercices derriere pour avoir acces a cet exo qui se nomme somme a 42.000.000.

 

Franchement  les exos précédents sont facilement faisable a part lexo du bloc de quatre qui finalement n'est pas si compliqué mais demande un peu plus de reflexion

 

donc si quelqu'un trouve la motivation d'arriver a lexo de 42.000.000 et de proposer une solution qui marche sur le site cest le bienvenue.

 

Message cité 1 fois
Message édité par Nat1329 le 21-12-2019 à 21:32:13
Reply

Marsh Posté le 21-12-2019 à 21:26:55    

gilou a écrit :

> Tes algos ne sont pas bon du tout en performance et en vitesse d'exécution.
> j'ai testé tes deux codes mais aucun ne fonctionne sur le site, il passe 0 test sur 10 et le programme est super lent.(Accès mémoire invalide).  
Arf! Ils vont deux fois plus vite que les tiens (et sur un échantillon aussi faible, 6 nb, on voit pas les problèmes du tien, mais il suffirait qu'on passe a un échantillonnage de 20 ou 30 nombres et la, ça va être bien pire, vu que mon algo est linéaire en nb d'échantillons)
Il compile et marche parfaitement sous IntelliJ, qui me signalerait un accès mémoire invalide....
 
Comme je t'ai dit, j'ai passé les données via la ligne de commande, c'est peut être cela que ton site ne sait pas gérer (ou que tu n'as pas configuré) et cela expliquerait le message d'erreur reçu.
Si tu tapes les nombres au fur et a mesure de l’exécution du programme, pourquoi pas, mais c'est pas terrible.
il suffit de remplacer le début par

Code :
  1. public class Main {
  2.    static Scanner input = new Scanner(System.in);
  3.  
  4.    public static void main(String[] args) {
  5.        int entriesNb = input.nextInt();
  6.        int[] entries = new int[entriesNb + 1];
  7.        for (int k = 1; k <= entriesNb; ++k) {
  8.            entries[k] = input.nextInt();
  9.        }


A+,
 
 
 


 
 
Effectivement le.mien serait tres lent avec de nombreuses valeurs voila pourquoi je veux le corriger

Reply

Marsh Posté le 21-12-2019 à 22:33:39    

Nat1329 a écrit :

Salut.
 
Tu peux tenter d'essayer et faire des modifs sur l'exercice qui se trouve au lien suivant https://concours.algorea.org/conten [...] 95141437/.  
 
Le.probleme est qu'il faut valider les 5 exercices derriere pour avoir acces a cet exo qui se nomme somme a 42.000.000.
 
Franchement  les exos précédents sont facilement faisable a part lexo du bloc de quatre qui finalement n'est pas si compliqué mais demande un peu plus de reflexion
 
donc si quelqu'un trouve la motivation d'arriver a lexo de 42.000.000 et de proposer une solution qui marche sur le site cest le bienvenue.
 

Ça serait dans mes langages principaux ces temps ci, (xslt et xquery) je dirais pas non, mais sinon, non, j'ai autre chose à faire de 3h.
 
A+,


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 21-12-2019 à 22:53:04    

Bonsoir, en deux seconde, je ferais une sorte de recherche dicotomique donc on devrait trouver "/2" quelque par.

Reply

Marsh Posté le 22-12-2019 à 00:05:43    

A partir du moment ou tes données sont triées, il est difficile de faire mieux que l'algo que j'ai donné. Si elles ne sont pas triées, il faut les trier, ce qui est couteux, et il y a plus efficace avec un HashSet.
 
Mais bon, on peut gratter encore un peu sur l'algo que j'ai donné en minimisant les accès au tableau en cachant les valeurs :

Code :
  1. int i = 1;
  2. int j = entriesNb;
  3. int goal = 42000000;
  4. int ei = entries[1];
  5. int ej = entries[entriesNb];
  6. while (ei + ej != goal) {
  7.    if (ei + ej > goal)
  8.        do ej = entries[--j]; while (ej > (goal - ei));
  9.    else
  10.        do ei = entries[++i]; while (ei < (goal - ej));
  11. }


Si on sait qu'on a de gros ensembles de nombres, on peut améliorer l'algo en cherchant le i (resp j) a partir duquel la valeur testée dans le do...while s'inverse par dichotomie.
A+,


Message édité par gilou le 22-12-2019 à 10:25:00

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed