Problème C : Coding Challenge
Fichier d’entrée : cod.in
Fichier de sortie : cod.out (IN+OUT)
Source : cod.c | cod.cpp | cod.java | cod.cs | cod.php
Après avoir remporté la première édition de Coding challenge, notre champion a décidé de conquérir les développeurs du monde !
Pour réaliser ce défit il est obligé de faire des voyages entre plusieurs villes du monde, pour les premières compétions il n’avait aucun problème il se déplace tranquillement dans les villes ou la compétition se déroulera, mais après les trophées successives, son séjour là-bas est transformé en un enfer, la poursuite des journalistes et des Fun l’empêche de bien préparer les compétitions : pour cela il a décidé de ne pas sortir des aéroports que le jour J, en faisant un voyage par jour.
Une autre contrainte qui se pose pour notre champion c’est qu’il veut minimiser le coût des billets d’avion des vols qui prend. Le cout des billets entre les mêmes aéroports varie selon le jour d’une façon périodique.
Votre mission alors est d’aider notre champion pour lui dire le montant minimale qu’il doit payer pour son vole toute en passant par une suite des aéroports, et en respectant la durée des voyages (qui peux s’étaler sur plusieurs semaines !) ou lui dire que ce n’est pas possible de participer à cette compétition.
Format d’entrée
Le fichier d’entrée contient plusieurs cas de test. Chaque cas de test est décrit comme suit:
- une ligne contenant deux entiers n et k: n est le nombre des aéroports intermédiaires possibles, k est le nombre des vols qu’il veut prendre(le nombre des jours : un vol/jour).
Les aéroports sont notés 1, 2, . . . , n, avec 1 l’aéroport de départ et n l’aéroport de destination. n et k des entiers qui vérifient 2 <= n <= 10 et 1 <= k <= 1000.
- Les premières n(n-1) lignes décrivent les plannings des vols, chaque lignes décrit le planning entre deux aéroports.
Les n-1 plannings correspondent aux vols partants de l’aéroport 1 vers les aéroports (2, 3, . . . , n), respectivement. Les n-1 lignes suivantes correspondent aux vols partants de l’aéroport 2 vers les aéroports (1, 3, 4, . . . , n) respectivement . . .etc.
La description d’un planning commence par un entier d, la longueur de la période des prix pour ce vols, avec 1 <= d <= 30. après il y aura d entiers qui présente le prix du vols pour le jour 1 , 2 , . . . n, Un cout égale à 0 signifie qu’il n’existe aucun vol pour ce jour.
Si par exemple le planning entre deux aéroports est “3 75 0 80” le cout du premier jour est 75, aucun vol le deuxième jour, le cout du vol pour le troisième jour 80, et le cycle se répètent: 75 pour le quatrième jour, pas de vol le cinquième jour, etc.
Le fichier se termine par n = k = 0.
Format de sortie
Pour chaque cas de test, afficher:
- Une ligne contenant ‘scenario #N’, avec N le numéro du cas, N commence par 1. (Un seul espace entre scenario et ‘#’)
- La deuxième ligne contient soit ‘No flight possible.’ Si aucun vol n’est possible
- Soit ‘The best flight costs x.’, avec x le cout minimum avec k vols.
- Après chaque cas afficher une ligne vide.
Exemple de fichiers entrée/sortie :
| cod.in | cod.out |
| 3 6
2 130 150 3 75 0 80 7 120 110 0 100 110 120 0 4 60 70 60 50 3 0 135 140 2 70 80 2 3 2 0 70 1 80 0 0 |
Scenario #1
The best flight costs 460. Scenario #2 No flight possible. |
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.regex.*;
public class cod{
public static void main(String[] args) throws FileNotFoundException{
Scanner in=new Scanner(new File(« cod.in »));
PrintWriter out=new PrintWriter(« cod.out »);
int i=0, n=0 , numero=1;
while(in.hasNextLine()){
int nombrejours=0;
int nombaeroport=0;
boolean possible=true;
int cout=0;
int volpris=0;
String line=in.nextLine();
Pattern p=Pattern.compile(« \\s+ »);
String[] nombres=new String[2];
nombres=p.split(line);
nombaeroport=Integer.valueOf(nombres[0]);
nombrejours=Integer.valueOf(nombres[1]);
if(nombaeroport!=0 && nombrejours!=0){
out.println(« Scenario # »+numero);
int[][] prixvol = new int[90][1000];
for(i=0 ; inombrejours)
n=nombrejours;
for(j=0 ; j<n ; j++){
prixvol[i][j]=Integer.valueOf(planning[j]);
}
if(n<nombrejours)
for(j=n ; j<nombrejours ; j++){
prixvol[i][j]=prixvol[i][j-n];
}
}
int plan=0;
int depart=1; // numéro d'aeroport;
int destination=0; // numéro de destination;
int nbaerosuiv=nombaeroport-depart; // nombre d'aeroports suivants
/* Les conditions sur les choix des vols */
//if(nombaeroport==3)
for(i=1 ; i<=nombrejours ; i++){
if(depart==1 || depart==nombaeroport){
plan=(depart-1)*(nombaeroport-1)+destination;
while(prixvol[plan][i-1]==0){
i++;
}
if(i!=nombrejours && (nombrejours-i)<nbaerosuiv){
out.println("No flight possible.");
out.println(" ");
possible=false;
break;
}
else if(depart==1){
cout+=prixvol[plan][i-1];
volpris++;
depart++;
if(depart1 && depart<nombaeroport){
plan=(depart-1)*(nombaeroport-1)+destination;
while(prixvol[plan][i-1]==0 && prixvol[plan-1][i-1]==0){
i++;
}
if(i!=nombrejours && (nombrejours-i)<nbaerosuiv){
System.out.println("No flight possible.");
System.out.println(" ");
possible=false;
break;
}
else if(prixvol[plan][i-1]==0){
cout+=prixvol[plan-1][i-1];
volpris++;
depart–;
destination–;
}
else if(prixvol[plan-1][i-1]==0){
cout+=prixvol[plan][i-1];
volpris++;
depart++;
if(depart<nombaeroport)
destination++;
}
else if(prixvol[plan-1][i-1]prixvol[plan][i-1]){
cout+=prixvol[plan][i-1];
volpris++;
depart++;
if(depart<nombaeroport)
destination++;
}
}
}
if(!possible || volpris!=nombrejours){
out.println("No flight possible.");
out.println(" ");
}
else {
out.println("The best flight costs "+cout+".");
out.println(" ");
}
}
numero++;
}
in.close();
out.close();
}
}