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