printРабочее место участника


2441. Secret Code

Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Rorschach saw how Ozymandias entered the code and turned on the countdown to teleport the Monster to New York. Rorschach noticed all the digits of the code, except one. To cancel the launch, he needs to enter the code again. Rorschach discovered that the system checks the code using Luhn's algorithm.
This algorithm confirms the correctness of the number using a control digit which is always the last digit in the number. Steps to determine the validity of a number are:
  • Starting from the second digit from the right in the number (tens of the number), double the value of every second digit to the left. If this product is greater than nine, then the digits of that product should be summed up.
  • Calculate the sum of all values obtained in the previous step.
  • The sum thus obtained should be multiplied by nine and it should be determined the remainder of division by ten.
  • If the resulting remainder is equal to the last digit of the number (unit), the number is considered valid.
E.g. code 79927398713 is considered valid because the end right digit 3 can be obtained from the remaining digits in the way described.
Code 7 9 9 2 7 3 9 8 7 1 3
Double every other 7 18 9 4 7 6 9 16 7 2  –
Sum 7 9 (1+8) 9 4 7 6 9 7 (6+1) 7 2 Sum=67
`(67*9)\ mod\ 10\ =\ 603\ mod\ 10\ =\ 3`
Write a program that loads the secret code as a string that consists only of digits and exactly one sign "x", and prints the smallest one-digit number which we can replace the sign "x" with so that the code is valid.
In the first line there is an integer number `N` (`1\ ≤\ N\ ≤\ 100`), the length of secret code. In the second line there is a string of length `N` consisting of just digits “0”, “1”, “2”, “3”, “4”, “5”, “6”, “7”, “8”, “9” and exactly one sign "x".
In the only line of the output it should be printed the required one-digit number.

Sample Input 1


Sample Output 1


Sample Input 2


Sample Output 2


Sample Input 3


Sample Output 3

Source: COCI 2018/2019 contest #6