1731 - Numar 5

Pentru un număr dat cu k cifre , se numeşte algoritm de deplasare circulară spre dreapta de la o cifră iniţială , la o cifră finală , deplasarea din cifră în cifră spre dreapta de ori (1≤i,j≤k). Dacă pe parcursul deplasării s-a ajuns la cifra , se continuă deplasarea circulară spre dreapta cu cifra

.

Un număr cu k cifre se numeşte număr „circular” dacă îndeplineşte următoarele două cerinţe:

• toate cifrele sunt nenule;
• pornind de la cifra , aplicând algoritmul de deplasare circulară spre dreapta de exact k ori, se ajunge din nou la , fiecare dintre cifrele numărului fiind exact o singură dată cifră iniţială.

De exemplu, numărul 2396 este un număr “circular”, pentru că are doar cifre nenule şi algoritmul de deplasare circulară spre dreapta se aplică astfel:

1. Se porneşte de la cifra iniţială 2 (2 3 9 6) şi se numără două cifre spre dreapta, ajungând la cifra finală 9: 2 3 9 6.

2. Se porneşte de la cifra iniţială 9 şi se numără nouă cifre spre dreapta, ajungând la cifra finală 6: 2 3 9 6.

3. Se porneşte de la cifra iniţială 6 şi se numără şase cifre spre dreapta, ajungând la cifra finală 3: 2 3 9 6.

4. Se porneşte de la cifra iniţială 3 şi se numără trei cifre spre dreapta, ajungând la cifra finală 2: 2 3 9 6.

Astfel, se ajunge la prima cifră din număr, adică la cifra 2, după exact 4 aplicări ale algoritmului, iar fiecare dintre cifrele numărului este exact o dată cifră iniţială.

Cerința

Scrieţi un program care citeşte numărul natural nenul n, apoi numerele naturale , şi determină: a) cel mai mare număr din şir în care există cel puţin o cifră care apare de minimum două ori, iar în cazul în care în şir nu există un astfel de număr, se va afişa cel mai mare număr din şir; b) un şir de n numere naturale pentru care un element (1≤i≤n)se calculează astfel:

Date de intrare

Fişierul numar.in conţine pe prima linie numărul n, iar pe următoarele n linii numerele naturale

Date de ieșire

Fişierul numar.out va conţine pe prima linie un număr natural determinat conform cerinţei a), iar pe următoarele n linii şirul de numere determinat conform cerinţei de la punctul b), fiecare număr pe câte un rând.

Restricții și precizări

• 0 < n < 100
• 9 < x < 999589, 1 ≤ i ≤ n

Exemplu:

numar.in

5
15
123
1972
222
515

numar.out

515
15 
117
1959
222
522

Explicație

a) 515 este cel mai mare număr dintre cele cinci numere citite, număr ce conţine o cifră care apare de minimum două ori.

b) Pentru 15: de la cifra iniţială 1, se numără o cifră şi se ajunge la cifra finală 5, apoi începând de la cifra 5 ca cifră iniţială, se numără cinci cifre şi se ajunge la cifra finală 1. Astfel cifrele 1, 5 sunt o singură dată cifre iniţiale şi după două aplicări ale algoritmului de deplasare se ajunge la prima cifră, deci 15 este număr circular.

Încărcare soluție

Lipește codul aici

<syntaxhighlight lang="python" line="1"> import sys

sys.stdin = open('numar.in', 'r') sys.stdout = open('numar.out', 'w')

a = [0] * 10000 n = 0

def date():

   global n
   n = int(input())
   for i in range(n):
       a[i] = int(input())

def cifre_repetate(x):

   digits = [0] * 10
   while x:
       if digits[x % 10] != 0:
           return 1
       else:
           digits[x % 10] = 1
           x = x // 10
   return 0

def max():

   max1 = 0
   max2 = 0
   for i in range(n):
       if cifre_repetate(a[i]):
           if max2 < a[i]:
               max2 = a[i]
       if max1 < a[i]:
           max1 = a[i]
   if max2 == 0:
       return max1
   else:
       return max2

def este(x):

   i = 1
   a = [0] * 100
   b = [0] * 100
   k = 0
   t = 0
   z = 0
   j = 0
   ok = 0

   while x != 0:
       a[i] = x % 10
       if a[i] == 0:
           return 0
       x //= 10
       b[i] = 1
       i += 1

   i -= 1
   for j in range(i // 2):
       z = a[j]
       a[j] = a[i - j]
       a[i - j] = z

   z = 0
   t = a[1]
   k = 1
   ok = 1
   for j in range(1, i + 1):
       if k + t <= i:
           k = k + t
       else:
           k = (t - (i - k + 1)) % i + 1
       if b[k] != 0:
           z += 1
           b[k] = 0
       else:
           ok = 0
       t = a[k]

   if ok:
       return 1
   else:
       return 0

def main():

   global n
   p = -1
   z = 0
   date()
   print(max())
   z = 0
   for i in range(n):
       if este(a[i]):
           print(a[i])
       else:
           p = 0
           x = a[i]
           while not p:
               if este(x):
                   p = 1
               else:
                   x += 1
           p = 0
           y = a[i]
           while not p:
               if este(y):
                   p = 1
               else:
                   y -= 1
           if (x - a[i]) > (a[i] - y):
               print(y)
           else:
               print(x)

if __name__ == '__main__':

    main()

</syntaxhighlight>