C'est la version facile de ce problème. La seule différence entre les versions facile et difficile est la limite du nombre de déplacements dans votre solution.
Yuki vit sur une grille comportant $n+1$ lignes et $n$ colonnes. Les lignes sont numérotées de $1$ à $n+1$ de haut en bas, et les colonnes de $1$ à $n$ de gauche à droite. Notons $(i,j)$ la case située à la ligne $i$ et à la colonne $j$.
Il y a $n-1$ obstacles sur la grille, et leur répartition satisfait les conditions suivantes :
Il n'y a aucun obstacle sur la ligne $1$ ni sur la ligne $n+1$.
Pour tout $2\le i\le n$, il y a exactement un obstacle sur la ligne $i$.
Pour tout $1\le j\le n$, il y a au plus un obstacle dans la colonne $j$.
Au départ, Yuki se trouve en $(1,1)$. Elle a entendu dire qu'un groupe de kangourous vit sur la ligne $n+1$, et souhaite donc se rendre sur la ligne $n+1$ pour admirer le paysage.
Pour atteindre son objectif, Yuki peut effectuer plusieurs déplacements. À chaque déplacement, elle choisit l'une des quatre directions (haut, bas, gauche, droite) et avance d'une case dans cette direction. Plus précisément, si la case d'arrivée se trouve hors de la grille ou contient un obstacle, le déplacement n'est pas exécuté.
Malheureusement, Yuki ne connaît que les règles de répartition des obstacles, et non leurs positions précises. Elle souhaite donc que vous l'aidiez à définir une suite de déplacements telle que, pour toute répartition valide des obstacles, Yuki atteigne la ligne $n+1$ à un moment donné (il lui suffit d'avoir atteint la ligne $n+1$ au moins une fois ; elle n'a pas besoin d'y rester après avoir effectué tous les déplacements).
Comme Yuki n'est pas pressée, le nombre de déplacements dans votre solution ne doit pas dépasser $30\cdot n$.
Entrée
Une seule ligne contient un entier strictement positif $n$ ($2\le n\le 10^3$).
Sortie
Sur la première ligne, affichez un entier $k$ ($1\le k\le30\cdot n$), représentant le nombre de déplacements dans votre solution.
Sur la deuxième ligne, affichez une chaîne $s$ de longueur $k$, où $s_i$ représente la direction du $i$-ième déplacement de Yuki :
Si $s_i=\texttt{U}$, Yuki se déplace vers le haut.
Si $s_i=\texttt{D}$, Yuki se déplace vers le bas.
Si $s_i=\texttt{L}$, Yuki se déplace vers la gauche.
Si $s_i=\texttt{R}$, Yuki se déplace vers la droite.
Exemples
Entrée 1
2
Sortie 1
4 DRDD
Entrée 2
3
Sortie 2
17 DDDUUURDDDUUURDDD
Remarque
Pour le premier exemple :
- Les cases grises représentent les obstacles et les cases blanches représentent les cases vides. L'image suivante montre toutes les répartitions possibles des obstacles satisfaisant les exigences :
Pour la première répartition des obstacles, le trajet de Yuki est $(1,1)\to(1,1)\to(1,2)\to(2,2)\to(3,2)$.
Pour la deuxième répartition des obstacles, le trajet de Yuki est $(1,1)\to(2,1)\to(2,1)\to(3,1)\to(3,1)$.
Pour toute répartition valide des obstacles, Yuki atteint la ligne $n+1$, donc la sortie de l'exemple est correcte.
Pour le deuxième exemple :
- Les cases grises représentent les obstacles et les cases blanches représentent les cases vides. L'image suivante montre toutes les répartitions possibles des obstacles satisfaisant les exigences :
- Il est facile de prouver que, pour chacune de ces répartitions des obstacles, en suivant les déplacements donnés dans la sortie de l'exemple, Yuki atteindra la ligne $n+1$.