UP | HOME

Concours Prog @ UNS

Table des matières

Résultats du concours   KEY

Ils sont ici.

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: <2017-12-12 mar.>

Le concours s’effectue en binôme. Le formulaire d’inscription est disponible ici.

Vous pourrez aussi vous inscrire sur place.

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 3ème étage du Petit Valrose.
  • Vous avez accès à internet

Préparer le concours

ECHO - Commande echo   KEY

Vous allez programmer la fameuse commande echo pour un vecteur d’entiers. Ce programme est un point de départ pour résoudre les autres problème.

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

Nous expliquons ci-dessous comment tester et soumettre une solution en prenant pour l’exemple un script R.

Tester une solution avant de le soumettre.

  • Pour le tester avec un terminal shell (pas dans l’interpréteur R)

    Dans le dépot, le fichier ECHO-03.in contient les nombres entiers compris entre 4 et 6.

    Le contenu du fichier est redirigée sur l’entrée standard de notre script R. La commande Rscript permet d’exécuter un script R dans un terminal shell.

    Rscript ECHO.R < ECHO-03.in
    
  • Pour le tester avec un interpréteur R (par exemple, dans RStudio)
    • Exécuter le programme
    • Taper ou copier/coller l’entrée dans l’invite de l’interpréteur
    • Taper ctrl-d quand vous avez fini

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.
  • En cas de besoin, consulter le guide officiel des équipes (en anglais).

SMPSUM - Iterated sums   EASY

Source : SMPSUM - Iterated sums.

Calculer la somme des carrés des nombres compris entre a et b (inclus).

Input

Les entrées du programme sont deux entiers a et b (a <= b) compris entre 1 et 100 séparés par un espace.

Output

La somme des carrés: a*a + (a+1)*(a+1) + ... + (b-1)*(b-1) + b*b.

Example

Input:
1 4

Output:
30
Input:
5 6

Output:
61

CHITEST1 - Sum of two numbers   EASY

Source: CHITEST1 - Sum of two numbers.

Calculer la somme de deux nombres.

Input

La première ligne de l’entrée donne le nombre N>=0 de tests. Les N lignes suivantes donnent deux nombres flottants compris entre -100000 et 100000 séparés par un espace.

Output

En partant de la deuxième ligne de l’entrée, afficher la somme des deux nombres flottants sur une ligne. La précision de la sortie est de 6 décimales après la virgule.

Example

Input:
3 
2 3
3.3 4
-1 4

Output:
5.000000
7.300000
3.000000

STARTED SMPSEQ5 (traduire) - Fun with Sequences (Act 3)   MEDIUM

Source : SMPSEQ5 - Fun with Sequences (Act 3).

You are given a sequence of n integers S = s1, s2, …, sn and a sequence of m integers Q = q1, q2, …, qm. Please, print in the ascending order all such i, that si = qi, i<=n, i<=m.

Input

In the first line you are given one integer 2<=n<=100, and in the following line n integers: -100 <= si <= 100, si <= si+1.
In the third line you are given one integer 2<=m<=100, and in the following line m integers: -100 <= qi <= 100, qi <= qi+1.

Output

The sequence of requested integers separated by spaces.

Example

Input:
5
-2 -2 -1 1 4 
6
-3 -2 -1 1 2 3

Output:
2 3 4

PLAQ - Radar automatique   MEDIUM

Un radar automatique produit à chaque flash, une chaîne de caractères correspondant à l’immatriculation du véhicule potentiellement verbalisable.

  • Si la photo est bonne, le radar produira une chaîne « correcte » correspondant à :
    1. une voiture/moto/… : 2 lettres majuscules puis 3 chiffres puis 2 lettres majuscules.
    2. une mobylette (\(< 50 cm^3\)) : 2 lettres majuscules puis 2 chiffres puis 1 lettre majuscule.
  • Si la photo n’est pas bonne, le radar produira tout de même une chaîne qui n’aura pas de sens et dont la syntaxe ne sera pas celle d’un véhicule.

Ecrire un programme qui analyse la chaîne produite par le radar et déduit le type du véhicule.

Input

Une seule ligne contenant une plaque d’immatriculation : une chaîne de caractères alphanumériques (majuscule ou chiffre) d’au plus dix caractères sans caractère d’espacement (blanc ou tiret).

Output

  • V si la plaque correspond à une voiture/moto/… ;
  • M si la plaque correspond à une mobylette ;
  • ? si la plaque n’est pas reconnue.

Example

Input:
AA123AA 

Output:
V

Input:
BJ97C 

Output:
M

Input:
Q5213FF 

Output:
?

Input:
Q213FF 

Output:
?

INET1 - Adresse Internet   MEDIUM

Une adresse Internet est un nombre entier sur 4 octets, soit 32 bits. Par exemple, exprimé en base 16 : (C0290614)16.
Dans l’utilisation quotidienne et comme moyen mnémotechnique, elle est souvent présentée comme une succession de valeurs sur 8 bits séparées par des points : 8 bits . 8 bits . 8 bits . 8 bits ; ce qui donne, par exemple,

  • En base 16 : C0.29.06.14. (remarquez le 06)
  • En base 10 : 192.41.6.20.

Écrire un programme qui transforme une adresse internet (sur 32 bits) écrite en base 16 en sa représentation pointée en base 10 ou 16.

Input

Une adresse internet en base 16 et la base (10 ou 16) de sa représentation pointée séparés par un espace. Les chiffres hexadécimaux sont donnés en majuscules (pour les lettres).

Output

La représentation pointée en base 10 ou 16 de cette adresse. En base 16, les 0 ne sont pas omis pour garder la représentation binaire sous jacente.

Example

Input :
C0290614 16

Output :
C0.29.06.14

Input :
C0290614 10

Output :
192.41.6.20

INET2 - Classe d’une adresse internet   MEDIUM

Les 32 bits de l’adresse Internet d’un ordinateur représentent deux informations :

  1. L’information d’identifiation du réseau sur lequel l’ordinateur est connecté : le netid.
  2. L’information d’identification de l’ordinateur sur ce réseau : le hostid.

Originellement, Internet prévoit 5 configurations possibles dans l’interprétation des 4 octets formant l’adresse.

  • Chaque configuration modifie la répartition des bits entre la zone netid et hostid.
  • Une configuration correspond à une classe d’adresse.
  • Les classes sont nommées A,B,C,D ou E.

adresse_ip.png

La classe d’une adresse est déterminée à partir de ses bits de poids fort.

Nom de Classe Valeurs de Bits de classe Taille (en bits) de netid Exemple
A 0 8 18.0.0.0
B 10 16 134.157.0.3
C 110 24 192.0.1.0
D 1110 - 224.1.3.4
E 1111 - 240.4.5.6

Écrire un programme qui détermine la classe d’une adresse internet (sur 32 bits).

Input

Une adresse internet en base 16.

Output

La classe de l’adresse internet

Example

Input:
C0290614

Output:
C

Input:
863B83AC

Output:
B

Input:
C0A80001

Output:
C

Input:
F0040506

Output:
E

INET3 - Masque d’une adresse internet   MEDIUM

Cet exercice ne peut être réalisé que si l’exercice précédent fonctionne.

Écrire un programme qui calcule la valeur entière en base 16 du netid et la valeur entière en base 16 du hostid à partir d’une adresse Internet en base 16. Pour ce qui est des classes D et E, la valeur entière rendue (pour le hostid et le netid ) est celle de l’adresse dans sa globalité. Par exemple, si on a l’adresse (863B8317)16, sa classe est B puisque le codage en base 2 de l’adresse commence par 1000. Le programme affichera:

  • un netid égal à la valeur (863B)16 puisque ce type d’adresse code sur les 16 bits (2 + 14) de poids fort le netid.
  • un hostid égal à la valeur (8317)16 puisque ce type d’adresse code sur les 16 premiers bits de poids faible le hostid.

Input

Une adresse internet en base 16.

Output

Le netid et le hostid séparés par un espace.

Example

Input:
C0290614

Output:
C02906 14

Input:
863B83AC

Output:
863B 83AC

Input:
C0A80001

Output:
C0A800 01

Input:
F0040506

Output:
F0040506 F0040506

REBOND - Filtre à rebonds   HARD

L’automate que vous allez concevoir est appelé filtre à rebonds.
Il s’agit d’un programme qui prend en entrée une séquence de 0 et de 1. Le but est de « lisser » cette séquence en considérant comme un « bruit »:

  • un 0 isolé (c’est à dire encadré par des 1), et en le remplaçant par un 1;
  • de la même façon, un 1 encadré par des 0 sera considéré comme un bruit, et remplacé par un 0.

L’état initial de cet automate est une information importante puisqu’il résume l’information d’un passé supposé : on choisit de définir l’état initial égal à la première valeur de la séquence. Donc, par exemple, si la séquence commence par un 0, c’est que l’on suppose venir d’un passé formé d’une séquence de ’0’.

On doit enlever le dernier chiffre si on ne peut pas déterminer si c’est un rebond ou pas.

Input

Une seule ligne contenant une séquence d’au plus 256 caractères.

Output

La séquence lissée par le filtre à rebonds.

Example

Input:
1

Output:
1

Input:
01

Output:
0

Input:
000

Output:
000

Input:
001

Output:
00

Input:
0011001011100000100001000111001

Output:
001100001110000000000000011100

Remarquez que dans l’automate ne peut conclure sur le dernier 0 de la dernière séquence puisque l’on ne sait pas si il s’agit d’un 0 isolé ou du premier 0 d’une séquence à venir. Il est donc éliminé en sortie et pour cette raison la séquence de sortie comporte un caractère de moins. Attention, ce n’est pas le cas pour les séquences précédentes.

STIR - Nombre de Stirling de seconde espèce   HARD

Le nombre de partitions d’un ensemble à \(n\) éléments en \(k\) sous-ensembles (non vides) est donné par le nombre de stirling de deuxième espèce \(\left\{\begin{array}{l}n \\ k \end{array}\right\}\).

\[ \left\{\begin{matrix} n \\ k \end{matrix}\right\}=\frac{1}{k!}\sum_{j=1}^{k}(-1)^{k-j}{k \choose j} j^n, \]

avec les coefficient binomiaux:

\[ {n \choose p} = C_n^p\, = \frac{n!}{p!(n-p)!}. \]

stirlingvalues.png

Figure 2 : Quelques valeurs du nombre de Stirling de seconde espèce en fonction de ses paramètres.

Écrire un programme qui calcule le nombre de Stirling pour \(n\) et \(k\) fixés. Compte tenu de la présence de la factorielle et des éventuels dépassements de capacité qui pourraient en résulter, nous limiterons les valeurs des paramètres à \(0\leq k \leq n<14\).

Input

Chaque ligne contient deux nombres \(n\) et \(k\).

Output

Pour chaque ligne, afficher le nombre de Stirling de la deuxième espèce.

Example

Input:
6 2
8 4

Output:
31
1701

Created: 2018-02-15 jeu. 13:13