IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

Besoin d'aide pour un probléme de ICPC


Sujet :

C

  1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2012
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Maroc

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : août 2012
    Messages : 2
    Points : 1
    Points
    1
    Par défaut Besoin d'aide pour un probléme de ICPC
    Bonsoir, je n'arrive pas a trouver le bon chemin pour résoudre ce problème. Pourriez vous m'orienter ?

    LE Problème :

    4970 - A Knights' Tale
    Time limit: 3.000 seconds
    Imagine a chess board that extends indefinitely in both horizontal and vertical directions. N identical knights are placed on this board, each in a different square. N different squares are specially marked, which we will call the target squares, which could be different from where the knights are initially at. We would like you to determine the minimum number of knight-steps needed so that each of the target squares is occupied by one of the knights.



    As illustrated in the figure, a knight moves using the normal ”L” move (1 square in one dimension and 2 squares in the other dimension.) For this problem, it is possible for more than one knight to occupy the same square while trying to reach its final destination as long as each knight ends up in a different target square.

    Input

    Your program will be tested on one or more test cases. Each test case is specified using 2N +1 lines.
    The first line specifies (1 ≤ N ≤ 15) which is the number of knights (or targets.) The following N lines each specifies the position of a knight by specifying two integers representing the x and y location. The remaining N lines each specifies the position of a target square again by specifying two integers representing the x and y location. All coordinates are 32-bit signed integers.
    The last case is followed by a line with a single zero.

    Output

    For each test case, print the following line:
    k. m
    Where k is the test case number (starting at one,) and m is the minimum number of moves.

    Example

    Input:
    2
    3 5
    6 5
    5 3
    7 3
    0
    Output:
    1. 3

  2. #2
    Modérateur
    Avatar de Obsidian
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    septembre 2007
    Messages
    7 286
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2007
    Messages : 7 286
    Points : 23 352
    Points
    23 352
    Par défaut
    Avant toute chose,

    — As-tu besoin que l'on te traduise cet énoncé ou est-ce que tu as bien compris le problème ?
    — Est-ce que c'est bien en C que tu dois écrire ton programme ?

  3. #3
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    août 2012
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Maroc

    Informations professionnelles :
    Activité : Étudiant
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : août 2012
    Messages : 2
    Points : 1
    Points
    1
    Par défaut
    Merci pour votre réponse. J'ai très bien compris l'énoncé mais j'ai pas trouvé la bonne manière pour le résoudre, pour le langage il vaut mieux qu'il soit écrit en C ou C++ ce qui m’intéresse est l'algorithme

  4. #4
    Membre expert
    Avatar de kwariz
    Homme Profil pro
    Chef de projet en SSII
    Inscrit en
    octobre 2011
    Messages
    898
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 49
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet en SSII
    Secteur : Conseil

    Informations forums :
    Inscription : octobre 2011
    Messages : 898
    Points : 3 339
    Points
    3 339
    Par défaut
    Citation Envoyé par SQL ninjaa Voir le message
    Merci pour votre réponse. J'ai très bien compris l'énoncé mais j'ai pas trouvé la bonne manière pour le résoudre, pour le langage il vaut mieux qu'il soit écrit en C ou C++ ce qui m’intéresse est l'algorithme
    Bonjour,

    * si tu possèdes une fonction kd (pour knight distance) qui accepte deux paramètres S (pour les coordonnées de la case source) et T (pour les coordonnées de la case target) et qui renvoie le nombre minimum de déplacements nécessaires à un cheval pour aller de S à T
    [je te rassure cette fonction existe, elle est compliquée à trouver «manuellement» mais elle se google facilement]

    * si tu construis un graphe biparti complet Kn,n (où n<15 est donné par l'input) avec les «S d'un côté» et les «T de l'autre» une arête rejoignant un s de S à t de T ayant pour poids kd(s,t) (donc tous les poids sont positifs ou nuls)

    * si tu as un algorithme qui détermine le couplage de poids le plus faible d'un graphe biparti

    Alors le tour est joué, enfin je pense.

    Remarque: le passage par un graphe biparti complet n'est pas obligatoire, c'est une façon de représenter le problème (enfin surtout de le réduire à une forme connue). Le principal est , à mon avis, de reconnaître un problème avec une distance, la question étant de minimiser une somme de distance.

Discussions similaires

  1. [Free Pascal] Jeu d'arcade : besoin d'aide pour résoudre un problème
    Par kingmodi dans le forum Free Pascal
    Réponses: 2
    Dernier message: 09/11/2014, 12h48
  2. Réponses: 1
    Dernier message: 27/07/2011, 20h00
  3. Besoin d'aide pour un problème d'exécution
    Par parygo dans le forum MATLAB
    Réponses: 1
    Dernier message: 19/12/2010, 15h10
  4. Réponses: 6
    Dernier message: 26/04/2007, 13h57
  5. Réponses: 39
    Dernier message: 21/10/2006, 14h53

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo