Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1331. Bus Conductor

Ограничение времени: 0.2 сек.
Ограничение памяти:65536 КБайт
Статистика Послать на проверку Задачу добавил debug

Vasya is a conductor on a bus serving quite an unpopular route, so he is loafing most of his working hours. In order to kill time he often plays a game. He takes a piece of his ticket roll and starts looking for lucky tickets. The tickets in the roll have sequential six-digit numbers. A ticket is lucky if the sum of the first three digits of its number is equal to the sum of the other three. Vasya records his observations making a string of capital Latin letters, writing down “L” for a lucky ticket, and “U” for a common one. For example, for the roll of 10 tickets numbered 001001, 001002, 001003, 001004, 001005, 001006, 001007, 001008, 001009, 001010, the resulting string will be “LUUUUUUUUL”.

Eventually, Vasya considered an inverse problem: would it be possible to come up with a ticket roll for a given string consisting of  “L” and “U” characters? The answer turned out to be negative. For example, there is no roll having two consecutive lucky tickets, that is, no ticket roll exists for string “LL”.

Your task is to write a program that will find a ticket roll corresponding to the given string of “L” and “U” characters, or report that no such roll exists. In case of several possible solutions, the correct roll is the one with the least number of the first ticket.


The input string contains capital letters “L” and “U” only. Its length does not exceed 1000 characters. The input string is non-empty.


The first line of the input file contains an integer n, the number of characters in the input string. The second line contains n characters. The only valid characters here are capital Latin letters “L” and “U”.


The output file should contain either a six-digit integer, the number of the first ticket in the roll corresponding to the input string, or the message “No solution” (without quotation marks) if no such roll exists.









No solution






Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Чемпионат ACM / Рыбинск-2014 /
1330. F - Sages 1331. 1332. H - Cryptography 1333. I - Belt Drive 1334. J - Dominoes
время генерации 0.125 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.