UP | HOME

UCAnCODE
bandeau_web_ucancode.png

Table des matières

SESSION ÉTENDUE   KEY

Vous avez une autre chance de résoudre les quatres derniers problèmes du lundi 17 décembre 21h au mercredi 19 décembre 21h sur la plateforme sphere-engine.

Attention, vous n’avez le droit qu’à un maximum de 5 soumissions pour résoudre un problème.

Vous devez absolument entrer l’adresse email suivante loginENT@etu.unice.fr pour que vos résultats soient pris en compte.

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.

Le formulaire d’inscription est disponible ici.

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

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).

1DTO2D - De la 1D à la 2D   EASY

On considère un tableau de \(n\) lignes et \(m\) colonnes. Il y a \(n\times m\) cases dans le tableau, numérotées de 1 à \(n\times m\).

Par exemple le tableau suivant a 6 lignes, 4 colonnes et les cases sont numérotées de 1 à 24.

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20
21 22 23 24

Input

L’entrée contiendra sur la première ligne le nombre de lignes \(0 < n < 100\), le nombre de colonnes \(0 < m < 100\) et le nombre de cas de tests \(0 \leq t \leq 10000\). Chaque cas de test est sur une ligne unique avec un nombre \(1 \leq c \leq n\times m\) correspondant à une case dans le tableau.

Output

Pour chaque case \(c\), afficher sur une ligne, la ligne et la colonne correspondante.

Example

Input:
6 4 4
1
11
17
24

Output:
1 1
3 3
5 1
6 4

DIGROOT - Racine numérique   EASY

Source : DIGRT

La racine numérique (digital root) d’un entier naturel est la somme des chiffres itérée de ce nombre (pour la notation usuelle en base 10), c’est-à-dire que celle-ci est obtenue en additionnant tous les chiffres du nombre initial, puis en additionnant les chiffres du résultat, et ainsi de suite jusqu’à l’obtention d’un nombre à un seul chiffre.

Par exemple, prenons le nombre 987654,

  • On somme ses chiffres \(d(987654) = 9 + 8 + 7 + 6 + 5 + 4 = 39\).
  • On somme les chiffres de 39. \(d(39) = 3 + 9 = 12\).
  • On somme les chiffres de 12. \(d(12) = 1 + 2 = 3\).

Donc la racine numérique de 987654 est 3.

Input

L’entrée du programme est une suite d’entiers (environ 100) compris entre 1 et 2000000. Il y a un entier \(n\) par ligne. La valeur 0 indique la fin de la séquence.

Output

Pour chaque entier \(n\), afficher sa racine numérique sur une ligne.

Example

Input:
987654
0

Output:
3

POW24 - Puissance 2 ou 4   EASY

Vous devez déterminer si un entier positif \(n\) (\(1 \leq n \leq 2000000000\)) est une puissance de 2, une puissance de 4, ou ni l’une ni l’autre.

Input

Une seule ligne contenant le nombre \(n\).

Output

Vous devez afficher sur une ligne:

  • 2 si \(n\) est une puissance de 2;
  • 4 si \(n\) est aussi une puissance de 4;
  • 0 si \(n\) n’est ni une puissance de 2, ni une puissance de 4.

Example

Input:
1

Output:
4

Input:
4

Output:
4

Input:
6

Output:
0

Input:
16

Output:
4

Input:
32

Output:
2

EXFLOT - Exercice Flottant   MEDIUM

Les programmes ont besoin de manipuler des nombres réels pour représenter des mesures physiques ou faire des calculs. Or les nombres réels peuvent avoir une infinité de décimales, ce qui n’est pas représentable en machine avec une mémoire finie. On a donc inventé une approximation finie de ces nombres, les nombres à virgule flottante ou flottants. Quasiment toutes les programmes actuels utilisent les nombres flottants, le plus souvent sur 32 ou 64 bits.

Néanmoins, l’arithmétique des flottants a un comportement différent de l’arithmétique des réels. Par exemple, une opération sur deux nombres flottants ne donne pas souvent un nombre flottant comme résultat. Pour résoudre ce problème, il existe une fonction d’arrondi, qui va arrondir une valeur vers un flottant représentable en machine.

Il existe quatre modes d’arrondi possibles :

Arrondi M Description
Au plus proche 2 arrondi au plus proche pair (à la position requise) en cas d’égalité
Vers le haut 1 arrondi vers +infini (qui est un arrondi vers 0 pour les valeurs négatives)
Vers le bas -1 arrondi vers -infini (qui est un arrondi loin de 0 pour les valeurs négatives)
Vers 0 0 arrondi par troncature

À partir d’un nombre flottant à 8 décimales et d’un mode d’arrondi donné, vous calculerez le nombre flottant arrondi à 2 décimales.

Input

L’entrée contiendra sur la première ligne le nombre de cas de test \(0 \leq t \leq 100\). Chaque cas de test est sur une ligne unique avec un nombre flottant, à une précision de 8, et le mode d’arrondi à appliquer.

Output

Pour chaque cas de test, afficher le nombre arrondi correctement à deux décimales près sur une ligne.

Example

Input:
4
1.33333333 1
12.4594454 0
0.11563232 2
-4.43454455 -1

Output:
1.34
12.45
0.12
-4.44

TONNEAUX - Comment bien empiler ses tonneaux   MEDIUM

Marc LEBONCOUP vient de démarrer une petite activité de commerce de vieux bas armagnac et il a acheté un gros stock à plusieurs producteurs. Après quelques jours, l’ensemble des tonneaux est livré en même temps. Puisqu’il soupçonne que le stock ne va pas s’écouler si rapidement que ça, il se dit qu’il vaut mieux disposer les tonneaux convenablement dans la cave afin d’éviter tout encombrement inutile. Il réalise donc que la meilleure façon de faire consiste à disposer les tonneaux l’un à coté de l’autre pour former une base solide et ensuite ranger ceux qui restent par dessus la base en faisant en sorte que chaque tonneau touche deux tonneaux de la rangée inférieure.

  /¯¯\/¯¯\
  \__/\__/
/¯¯\/¯¯\/¯¯\/¯¯\
\__/\__/\__/\__/

Il réalise ensuite que pour mieux accéder aux tonneaux d’une rangée et pour que l’ensemble tienne mieux, il faut que les tonneaux d’une rangée soient mis l’un à côté de l’autre (c’est-à-dire sans qu’il y ait des trous). On appellera une disposition de tonneaux admissible si chaque rangée ne contient pas de trous :

    /¯¯\/¯¯\/¯¯\/¯¯\/¯¯\
____\__/\__/\__/\__/\__/____

Vice-versa une disposition est non-admissible si elle contient des trous :

    /¯¯\/¯¯\    /¯¯\/¯¯\
____\__/\__/____\__/\__/____

Pendant que Marc range ses tonneaux, il commence à se rappeler de ses vieux cours d’Outils Formels pour l’Informatique et il se pose toute une série de questions.

Il se pose en effet la question de combien de manières possibles il pourrait disposer ses tonneaux une fois qu’il a formé une base de taille \(n\). Bien sûr il ne s’intéresse qu’aux dispositions admissibles. Comme ses cours commencent à dater, il a besoin de votre aide.

Exemple pour \(n = 3\), on a 5 dispositions possibles.

                                                                    /¯¯\
                                                                    \__/
                  /¯¯\                /¯¯\        /¯¯\/¯¯\        /¯¯\/¯¯\
                  \__/                \__/        \__/\__/        \__/\__/
/¯¯\/¯¯\/¯¯\    /¯¯\/¯¯\/¯¯\    /¯¯\/¯¯\/¯¯\    /¯¯\/¯¯\/¯¯\    /¯¯\/¯¯\/¯¯\
\__/\__/\__/    \__/\__/\__/    \__/\__/\__/    \__/\__/\__/    \__/\__/\__/
      1               2               3               4               5

Input

L’entrée contiendra sur la première ligne le nombre de cas de test \(0 \leq t \leq 100\). Il y a un cas de test par ligne, un seul entier \(n\) compris entre 0 et 20.

Output

Pour chaque cas de test, afficher le nombre de dispositions de tonneaux admissibles avec une base de taille \(n\).

Example

Input:
4
0
1
2
3

Ouput
1
1
2
5

Indice

on peut donner la formule pour \(n\) strictement positif : \[ f (n) = 1 + \sum_1^n (n − k) \times f (k). \]

SABLE - Tas de sable   MEDIUM

On appelle tas de sable une suite finie et décroissante d’entiers strictement positifs. Chaque entier représente le nombre de grains de sables empilés à une position donnée. Le tas de sable (5, 3, 2) est représenté ci-dessous.

#
#
##
###
###

Des avalanches peuvent se produire dans les tas de sable si la différence de taille entre deux colonnes successives est supérieure ou égale à 2. La colonne la plus haute perd alors un grain de sable qui est ajouter à la suivante. Une avalanche peut se produire sur la dernière colonne si sa taille est supérieure ou égale à 2. Elle perd alors un grain et une nouvelle colonne de taille 1 est ajouté au tas de sable.

Exemples d’avalanches sur la première ou la dernière colonne.

#                #               
#        ##      #  
##       ##      ## 
###      ###     ##
###      ###     ####
532      442     5311

Un tas de sable est dit stable si aucune avalanche ne peut se produire. Chaque tas de sable évolue en un tas de sable stable par une suite d’avalanches. L’ordre des avalanches n’influe pas sur le résultat final.

Input

L’entrée contiendra sur la première ligne le nombre de cas de test \(0 \leq t \leq 100\). Il y a un cas de test par ligne, un seul entier \(n\) compris entre 1 et 1000000.

Output

Pour chaque cas de test, afficher la suite d’entiers correspondant au tas de sable stable obtenu à partir d’une unique colonne de taille \(n\). Les entiers de la suite sont affichés sur une seule ligne séparés par une espace.

Example

Input:
5
1
2
3
4
5

Output:
1
1 1
2 1
2 1 1
2 2 1

STAR - L’Étoile Noire   HARD

Le vaisseau spatial l’« étoile noire » comme son nom l’indique, est une étoile à \(n\) sommets (\(n\) impair) et comporte \(\frac{n(n-1)}{2}\) couloirs reliants chaque paire de sommets. Les sommets sont numérotés de \(0\) à \(n-1\)

CompleteGraphs_801.gif

Figure 1 : Exemple de graphes complets. K3, K5, et K7 sont de possibles étoiles noires.

Une grande fête a eu lieu récemment, et dans tous les couloirs gisent encore les restes de cette fête. Leonhard est un robot ménager. Sa mission: nettoyer tous les couloirs de l’étoile noire sans repasser deux fois par le même couloir. Pour cela, Leonhard devrait utiliser un algorithme glouton : chaque fois qu’il voit des miettes dans un couloir, il court les ramasser et laisse derrière lui un couloir propre. Mais Leonhard semble avoir un peu trop participé à la fête…

Votre mission : détecter les erreurs de Leonhard. Vous devez examiner la liste ordonnée des sommets décrivant le parcours de Leonhard et vérifier qu’il est bien passé une et une seule fois par chaque couloir.

Input

Une seule ligne contenant la liste des sommets, séparés par des espaces, dans l’ordre de parcours. Le parcours est garanti de passer au moins une fois par le sommet n-1, ce qui permet de déterminer le nombre n de sommets.

Output

La sortie contient une seule ligne avec dans l’ordre les trois nombres suivants :

  • premier nombre : 0 si le parcours de Leonhard est correct, 1 sinon
  • deuxième nombre : le nombre de couloirs qui n’ont pas été visités
  • troisième nombre : le nombre de couloirs qui ont été visités deux fois ou plus

Example

Input:
1 2 0 1

Output:
0 0 0

Input:
0 1 2 0 3 1 4 2 3 4 0

Output:
0 0 0

Input:
0 1 0 3 0 1 4 2 1 3 4 0

Output:
1 2 2

Les deux premiers parcours sont corrects. Le troisième en revanche est incorrect, le couloir entre 0 et 2 et celui entre 2 et 3 n’ont pas été visités. De plus, le couloir entre 0 et 1 a été nettoyé trois fois et celui entre 0 et 3, deux fois.

Created: 2018-12-17 lun. 17:39