UP | HOME

Concours Prog @ UNS
web-banner.jpg

Table des matières

Introduction

Vous allez participer à un concours de programmation en binôme pendant 4 heures. Ce concours vous fera progresser sur les aspects suivants :

  1. Algorithmique : élaborer des algorithmes pour résoudre des problèmes simples, principalement de la recherche et du tri.
  2. Programmation : implémentation correcte d’algorithmes et gestion simple entrées/sorties.
  3. Travail en temps limité : organisation et concentration sont nécessaires, mais sans oublier de s’amuser …

Inscription   KEY

DEADLINE: <2018-04-27 ven.>

Vous pouvez vous inscrire sur place, mais il est préférable de s’inscrire à l’avance pour faciliter l’organisation.

Déroulement de la compétition

  1. La compétition dure 4 heures.
  2. 7 problèmes ou plus sont posés.
  3. Chaque solution à un problème soumise au juge est appelée un run.
  4. Chaque run est accepté ou refusé par le juge.

Score

Résoudre le maximum de problèmes le plus rapidement possible.

  1. Les équipes sont classées en fonction du nombre de problèmes résolus.
  2. Les égalités sont arbitrées par le délai total, puis, si nécessaire, la date du dernier run.

Le délai pour résoudre un problème est le temps passé entre le début de la compétition et le run accepté.

Environnement de travail

  • Vous travaillez sur les machines du 2ème et 3ème étages du Petit Valrose.
  • Vous avez accès à internet

Résultats des concours   KEY

Ils sont ici.

ECHO - Commande echo   KEY

Vous allez programmer la fameuse commande echo pour un vecteur d’entiers : réécrire les entiers depuis l’entrée standard vers la sortie standard. Ce programme est un point de départ pour résoudre les autres problèmes.

Input

Une séquence d’entiers (au plus 200000) entre 1 et 1000000.

Output

La séquence d’entiers lue en entrée. Afficher un entier par ligne.

Example

Input:
2
10
20

Output:
2
10
20

Télécharger une solution

La description du problème et des solutions dans plusieurs langages sont disponibles dans ce dépôt github.

Nous expliquons ci-dessous comment tester et soumettre une solution en R : ECHO.R.

Tester votre programme dans un terminal shell

Téléchargez le programme ECHO.R et le fichier d’entrée ECHO-03.in contenant les cas de tests. Ici, le fichier ECHO-03.in ne contient qu’un seul cas de test, les nombres entiers compris entre 4 et 6.

Nous allons maintenant exécuter le programme dans un terminal shell. Allez dans le répertoire où vous avez téléchargé les deux fichiers grâce à la commande cd. Tapez la commande suivante et vérifier que la sortie est conforme aux spécifications :

Rscript ECHO.R < ECHO-03.in

La commande Rscript permet d’exécuter notre script ECHO.R dans un terminal shell. Le contenu du fichier ECHO-03.in est redirigé sur l’entrée standard pour être lu par notre script R.

Soumettre une solution

Il faut maintenant soumettre le fichier ECHO.R pour obtenir le verdict du juge après un run.

  • Lancer la commande pc2team.sh & dans un terminal shell.
  • Entrer votre login et votre mot de passe.
  • Choisissez le langage R, sélectionner votre fichier, puis cliquer sur le bouton submit.
  • En cas de besoin, consulter le guide officiel des équipes (en anglais).

SMPWOW - Wow   EASY

Source : SMPWOW - Wow

Input

Soit un entier \(n\) compris entre 0 et 50 (0 < \(n\) < 50).

Output

Afficher un mot : Wo….ow (la lettre o doit être répétée \(n\) fois).

Example

Input:
1

Output:
Wow


Input:
7

Output:
Wooooooow

SMPDIV - Divisibilité   EASY

Source : SMPDIV - Divisibility

Afficher tous les entiers \(a_i\) divisibles par \(x\), mais pas par \(y\) tels que \(1 \leq a_i < n < 100000\).

Input

Une seule ligne contenant 3 entiers naturels séparés par une espace : \(n\,x\,y\). On suppose que \( 0 < x < n\) et que \(x\) n’est pas divisible par \(y\) (\(y > 0\)).

Output

Les nombres \(a_i\) (un par ligne) triés par ordre croissant.

Example

Input:
7 2 4

Output:
2
6 


Input:
35 5 12

Output:
5
10
15
20
25
30

KAMIL - Défaut de prononciation   EASY

Source : KAMIL - Kamil

Certains enfants ne peuvent pas prononcer toutes les lettres, certaines d’entre elles sont prononcées parfois correctement et parfois incorrectement. Kamil dit parfois T au lieu de K, mais il ne dit jamais K au lieu de T. De même, il dit parfois D au lieu de G. Au lieu de R, il dit parfois L et parfois F. Bien sûr, parfois, il prononce correctement les lettres. Le père de Kamil calcule toujours combien de mots différents peuvent correspondre au mot prononcé par son fils (peu importe qu’ils existent).

Écrire un programme qui lit à partir de l’entrée standard les mots prononcés par Kamil, compte à combien de mots différents cela peut correspondre et écrit le résultat sur la sortie standard.

Input

Dix cas de test, chaque cas de test est sur une ligne unique et correspond à un mot prononcé par Kamil écrit en majuscules. La longueur du mot est d’au plus 20.

Output

Pour chaque test, le nombre de mots pouvant correspondre au mot de Kamil.

Example

Input:
PRODLAMMATION
CONCOURS
MADIQUE
DIFFERENT
WQT
[et 5 autres cas de test]

Output:
8
1
2
16
2
[et 5 autres cas de test]

GNY07A - Fautes d’ortographe   MEDIUM

Source : GNY07A - Mispelling

La faute d’orthographe est une forme d’art dans laquelle les étudiants semblent exceller. Écrivez un programme qui supprime le n-ième caractère d’une chaı̂ne d’entrée.

Input

La première ligne d’entrée contient un seul nombre \(M\) , (\(1 \leq M \leq 1000\)) qui est le nombre de cas de test qui suivent. Chaque cas de test est constituée d’une seule ligne contenant \(n>0\) , d’une espace et d’un seul mot (non vide) composé uniquement de majuscules. \(n\) sera inférieur ou égal à la longueur du mot. La longueur du mot est inférieure ou égale à 80.

Output

Pour chaque cas de test, vous devez afficher une ligne de sortie avec les valeurs suivantes : le numéro de la donnée (un nombre entier, en commençant par 1), une espace et le mot mal orthographié. Le mot mal orthographié est le mot d’entrée avec le caractère indiqué supprimé.

Example

Input:
4
4 ORTHOGRAPHE
1 PROGRAMMATION
7 CONCOURS
3 HASHCODE

Output:
1 ORTOGRAPHE
2 ROGRAMMATION
3 CONCOUS
4 HAHCODE

COINS - Pièces   MEDIUM

Source : COINS - Coins

Le pays de ProgLand, a un système monétaire très étrange. Chaque pièce d’or ProgLandienne a un nombre entier écrit dessus. Une pièce \(n\) peut être échangée dans une banque en trois pièces : \(n/2\), \(n/3\) et \(n/4\). Mais ces chiffres sont tous arrondis à la baisse (les banques doivent faire des bénéfices). Vous pouvez également vendre des pièces de monnaie ProgLandienne pour des euros. Le taux de change est 1:1. Mais vous ne pouvez pas acheter des pièces de monnaie ProgLandienne.

Vous avez une pièce d’or. Quel est le montant maximum d’euros que vous pouvez obtenir pour cela?

Input

L’entrée contiendra sur la première ligne le nombre de cas de test. Chaque cas de test est sur une ligne unique avec un nombre \(n\), \(0 \leq n \leq 1000000000\). C’est le nombre inscrit sur votre pièce.

Output

Pour chaque cas de test, afficher sur une ligne le montant maximum d’euros que vous pouvez obtenir.

Example

Input:
3
12
2
24

Output:
13
2
27

MIRROR - Miroir   MEDIUM

Auteur : Gilles Menez

On souhaite réaliser une fonction capable d’effectuer un effet miroir sur une partie de la représentation binaire d’un nombre entier.

Ainsi, si on applique cet effet sur les 3 bits de poids faible d’un nombre entier :

  • \(b_{31}\ldots b_3000_2\) devient après miroir \(b_{31}\ldots b_3000_2\)
  • \(b_{31}\ldots b_3001_2\) devient après miroir \(b_{31}\ldots b_3100_2\)
  • \(b_{31}\ldots b_3010_2\) devient après miroir \(b_{31}\ldots b_3010_2\)
  • \(b_{31}\ldots b_3011_2\) devient après miroir \(b_{31}\ldots b_3110_2\)
  • \(b_{31}\ldots b_3100_2\) devient après miroir \(b_{31}\ldots b_3001_2\)
  • \(b_{31}\ldots b_3101_2\) devient après miroir \(b_{31}\ldots b_3101_2\)
  • \(b_{31}\ldots b_3110_2\) devient après miroir \(b_{31}\ldots b_3011_2\)
  • \(b_{31}\ldots b_3111_2\) devient après miroir \(b_{31}\ldots b_3111_2\)

L’effet miroir ne doit pas avoir d’effet de bord sur les bits de poids fort non concernés (poids \(\in [3, 31]\) dans l’exemple).

Proposer un programme réalisant cet effet sur les \(n\) bits de poids faible d’un nombre entier \(x\).

Si \(n \notin [2, 32]\) alors le nombre \(x\) n’est pas modifié. Sinon la valeur rendue est celle du nombre \(x\) avec un effet miroir sur ses \(n\) bits de poids faible.

Votre programme lit (sur le stdin) un entier en base 16 ainsi que le nombre de bits concernés par l’effet miroir (un entier en base 10).

Votre programme écrit (sur le stdout) la valeur (en base 16) du nombre \(x\) avec un effet miroir sur ses \(n\) bits de poids faible.

Input

Deux entiers \(x\) (en base 16) et \(n\) (en base 10) par ligne séparés par une espace. L’entrée peut contenir plusieurs lignes.

Output

La valeur (en base 16) du nombre \(x\) avec un effet miroir sur ses \(n\) bits de poids faible. On affiche une valeur par ligne.

Example

Input :
0x1 32
0x701 3
0x40C7A7C 0
0x3117 5
0x3F3 8

Output :
0x80000000
0x704
0x40C7A7C
0x311D
0x3CF

Input :
0x70 14

Output :
0x380

Input :
0x14 30

Output :
0xA000000

BUBBLE - Tri à bulle   MEDIUM

Auteur : Gilles Menez.

L’objectif d’un tri est de ranger en ordre croissant ou décroissant une suite de \(N\) nombres entiers \(a_{i}\) avec \(i \in [1,N]\).

Le principe du tri à bulle en ordre croissant est de parcourir (\(j\) variant de \(1\) à \(N-1\)) à plusieurs reprises la suite \(a_{1},a_{2},\dots,a_{N}\) en intervertissant toute paire d’éléments consécutifs \(a_{j}\) et \(a_{j+1}\) non ordonnés.

Ainsi dès le premier parcours, l’élément maximum se retrouve en position \(N\). On peut alors recommencer sur les éléments positionnés dans \([1,N-1]\)

Le nom de tri à bulle vient de ce que les plus grands entiers se retrouvent successivement à la droite de la suite. Comme si, telles des « bulles », ils étaient remontés de la gauche vers la droite.

Input

Une suite d’entiers \(a_i\) séparés par une espace. La taille maximum \(N\) de la suite est \(15\). L’entrée fait au maximum 255 caractères.

Output

Le nombre minimal d’inversions nécessaires pour trier la liste.

Example

Input :
23 7 12 45 77

Output :
2

Input :
1 2 3 4 5 6 7 

Output:
0

Input :
7 6 5 4 3 2 1

Output :
21


Input :
95

Output :
0


Input :
95 81 98 99 54

Output :
5

CAPES18 - Emploi du temps   HARD

Source : CAPES de mathématiques – Option Informatique – Session 2018

On s’intéresse à l’allocation des salles d’un lycée à partir des horaires des cours.

La donnée du problème est une liste de cours. Un cours est simplement représenté par un intervalle non vide \([deb, fin[\), où \(deb\) est l’instant de début du cours et \(fin\) est l’instant de fin du cours. Les instants peuvent être décomptés en heures ou en minutes au fil de la journée selon les besoins ; ici, les instants sont des nombres entiers et l’unité de temps n’est pas précisée. À chaque cours, on doit allouer une salle. Deux cours peuvent se voir allouer la même salle, uniquement si leurs intervalles sont disjoints. Par exemple, deux cours représentés par les intervalles [4, 6[ et [6, 8[ peuvent se voir allouer la même salle. L’objectif est d’utiliser un minimum de salles.

Input

L’entée commence par un nombre \(n\), \(0 \leq n \leq 1000\) correspondant au nombre de cours. Les \(n\) lignes suivantes sont constituées de deux chiffres séparés d’une espace correspondant à l’intervalle du cours. L’horizon de planification est de 100000, c’est-à-dire que chaque intervalle est inclus dans [0,100000[.

Output

Le nombre minimal de salles nécessaires à l’allocation des cours.

Example

interval_graph.png Le cours C2 est représenté par l’intervalle [4, 11[. Le nombre minimal de salles est 3.

Input:
6
0 2
1 7
4 11
5 6
8 11
9 13

Output:
3

Created: 2018-05-14 lun. 11:39