Poudre_de_perlimpinpin.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Poudre de perlimpinpin.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyMlL/k3x21yYMpcpDW4RN4b",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/GeoLabUniLaSalle/Python/blob/main/Poudre_de_perlimpinpin.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "R8kQ2CJh9aDY"
      },
      "source": [
        "## **Poudre de perlimpinpin ★★★**\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "*Exercice disponible sur la plateforme TOSA : Battle Dev Hello Works - Novembre 2019 : https://www.isograd.com/FR/solutionconcours.php*\n",
        "\n",
        "\n",
        "\n",
        "**Enoncé**\n",
        "\n",
        "\n",
        "Vous glissez malencontreusement avec vos babouches sur votre tapis volant et tombez à travers des sables mouvants dans une caverne magique où se trouve un fabuleux trésor.\n",
        "\n",
        "Le trésor est composé de différentes épices et poudres plus précieuses les unes que les autres dont on vous donne le prix au kilogramme ainsi que la quantité totale de chacune des poudres contenues dans la caverne. Le trésor comporte également des pierres précieuses, chacune a un poids et une valeur indivisible. Vous n'avez avec vous qu'une vielle lampe à huile de contenance finie (vous avez cru quoi ? ce n'est pas magique hein !) et vous devez indiquer quelles poudres et pierres précieuses emporter dedans pour maximiser la valeur du trésor que vous allez rapporter à la surface (avide que vous êtes) !\n",
        "\n",
        "\n",
        "Indice : si vous avez reconnu ici le \"problème du sac à dos\" (https://fr.wikipedia.org/wiki/Problème_du_sac_à_dos),\n",
        "vous êtes sur la bonne piste, mais le très grand nombre d'objets change un peu la donne !\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "**Format des données**\n",
        "\n",
        "*Entrée*\n",
        "\n",
        "Ligne 1 : 3 entiers séparés par des espaces : N le nombre de pierres précieuses, M le nombre de types de poudres, C la quantité (en gramme) de pierres ou poudre que peux contenir la lampe, chacun compris entre 1 et 100.\n",
        "\n",
        "Lignes 2 à N + 1 : 2 entiers séparés par des espaces, respectivement la valeur (en pièces d'or) et le poids (en grammes) de chaque pierre précieuse, compris respectivement entre 1 et 1000 et 1 et C\n",
        "\n",
        "Lignes N + 2 à N + M + 2 : 2 entiers séparés par des espaces, respectivement le prix au poids (en pièces d'or par gramme) et la quantité disponible (en grammes) de chaque type de poudre, compris respectivement entre 1 et 100 et 1 et C.\n",
        "\n",
        "\n",
        "*Sortie*\n",
        "\n",
        "La valeur maximale que peux contenir la lampe en pierres précieuses et poudres !\n",
        "\n",
        "*Exemple*\n",
        "\n",
        "Entrée\n",
        "\n",
        "2 2 100\n",
        "\n",
        "600 40\n",
        "\n",
        "1000 50\n",
        "\n",
        "20 40\n",
        "\n",
        "15 80\n",
        "\n",
        "Sortie\n",
        "\n",
        "1950\n",
        "\n",
        "*Commentaire*\n",
        "\n",
        "Dans cet exemple l'optimal est de prendre l'objet de valeur 1000, puis 40 grammes de poudre à 20 pièces d'or par gramme, puis 10 grammes de poudre à 15 pièces d'or par gramme. On arrive alors à une valeur de 1000 + 800 + 150 = 1950"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "LaFrvPhE-Ezb"
      },
      "source": [
        "## **Données**\n",
        "\n",
        "*Accès aux données*"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "2HlpCu_r-aqr",
        "outputId": "b26cd589-0cf1-4e47-bfc1-f6197d871ef9"
      },
      "source": [
        "import csv\n",
        "filedir = ('https://cours.unilasalle.fr/courses/SG4007/document/Exercices_Python/Poudre_de_perlimpinpin/')\n",
        "\n",
        "import ssl\n",
        "ssl._create_default_https_context = ssl._create_unverified_context\n",
        "\n",
        "import urllib.request\n",
        "\n",
        "for x in range(1,5):\n",
        "  f = urllib.request.urlopen(str(filedir+\"input\"+str(x)+\".txt\"))\n",
        "\n",
        "  data=[]\n",
        "  for i in f:\n",
        "      line=i.decode('utf-8').strip()\n",
        "      data.append(line)\n",
        "  print('Entrée',x,':',data)\n",
        "\n",
        "  f = urllib.request.urlopen(str(filedir+\"output\"+str(x)+\".txt\"))\n",
        "  for i in f:\n",
        "      line=i.decode('utf-8').strip()\n",
        "  print('Sortie',x,':',line,'\\n')"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Entrée 1 : ['1 1 10', '87 6', '79 2']\n",
            "Sortie 1 : 245 \n",
            "\n",
            "Entrée 2 : ['10 10 100', '485 84', '675 62', '261 35', '255 2', '817 83', '420 87', '844 64', '233 92', '403 44', '601 36', '64 60', '79 98', '92 38', '60 17', '100 70', '24 37', '3 11', '93 83', '59 36', '49 12']\n",
            "Sortie 2 : 9859 \n",
            "\n",
            "Entrée 3 : ['3 10 2', '97 2', '555 1', '834 2', '25 1', '9 1', '47 2', '86 1', '14 1', '1 1', '1 1', '98 1', '36 2', '39 1']\n",
            "Sortie 3 : 834 \n",
            "\n",
            "Entrée 4 : ['100 100 100', '680 100', '899 79', '770 89', '925 96', '82 87', '220 1', '217 84', '95 24', '515 51', '80 41', '836 23', '858 19', '882 85', '230 29', '106 85', '722 83', '537 29', '636 87', '8 95', '255 7', '694 63', '447 51', '447 10', '112 16', '494 10', '664 44', '754 68', '190 71', '598 23', '810 21', '679 75', '825 10', '289 80', '60 3', '585 97', '240 1', '764 69', '184 99', '794 47', '720 80', '896 2', '293 55', '824 95', '722 46', '29 30', '981 15', '648 78', '288 18', '568 59', '964 57', '756 62', '497 42', '51 59', '388 100', '376 12', '391 57', '548 95', '710 88', '344 86', '344 90', '640 86', '583 34', '708 53', '669 75', '731 55', '413 93', '490 11', '851 61', '538 80', '498 1', '463 68', '894 2', '447 76', '324 100', '287 97', '455 5', '721 90', '488 93', '617 24', '512 73', '751 35', '989 21', '997 22', '114 19', '8 80', '783 48', '202 31', '564 28', '587 95', '881 96', '901 79', '863 95', '266 19', '395 5', '521 4', '978 47', '881 34', '786 6', '852 49', '233 27', '33 86', '68 41', '78 35', '63 1', '97 80', '100 72', '70 63', '17 94', '85 96', '32 90', '74 35', '60 32', '43 1', '72 70', '75 61', '76 50', '54 83', '69 63', '8 65', '77 59', '73 11', '29 83', '43 41', '16 92', '95 81', '25 35', '5 18', '78 13', '67 97', '76 37', '57 99', '3 64', '67 92', '65 80', '69 76', '89 31', '20 64', '71 4', '15 76', '32 72', '1 23', '84 100', '73 100', '59 65', '76 59', '56 58', '17 84', '69 36', '57 38', '63 69', '10 7', '12 29', '32 92', '16 98', '88 50', '68 30', '37 84', '91 64', '68 80', '96 83', '25 73', '85 72', '39 49', '64 40', '18 50', '77 27', '33 40', '70 34', '12 52', '34 3', '24 6', '6 59', '12 86', '86 82', '56 91', '86 86', '35 100', '77 44', '34 92', '70 94', '45 64', '5 2', '100 4', '83 99', '41 35', '93 56', '65 88', '27 36', '27 61', '33 91', '1 27', '74 76', '34 45', '83 64', '51 27', '13 52', '2 22', '84 4', '94 83', '10 91']\n",
            "Sortie 4 : 12334 \n",
            "\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}