1505 - B 210

Enunţ

Vasilică tocmai a învăţat la şcoală despre sistemul de numeraţie cu baza 2. I se pare interesant şi a inventat jocul b210, pe care vrea să îl joace cu prietenul său Gigel. Vasilică îi spune lui Gigel un număr natural nenul n, scris în baza 10. Gigel trebuie să scrie numărul în baza 2, obţinând astfel o secvenţă de cifre binare, care începe cu 1. Asupra scrierii în baza 2 a numărului n Gigel poate aplica una sau mai multe permutări circulare. Printr-o permutare circulară, toate cifrele secvenţei date, exceptând ultima, sunt mutate cu o poziţie spre dreapta, iar ultima cifră devine prima.

De exemplu, dacă n=107, scrierea sa în baza 2 este 1101011. Prin permutări circulare succesive putem obţine, în ordine, secvenţele:

1110101

1111010

0111101

1011110

...

Fiecare astfel de secvenţă este scrierea în baza 2 a unui număr natural, pe care Gigel îl transformă în baza 10. Gigel trebuie să afle care este cel mai mare număr natural m, scris în baza 10, a cărui scriere în baza 2 se poate obţine prin una sau mai multe permutări circulare ale scrierii în baza 2 a numărului n. Lui Gigel jocul nu i se pare aşa interesant şi ar prefera să aibă un program care să determine în locul lui numărul natural m.

Cerința

Scrieţi un program care citeşte numărul natural nenul n şi care determină cel mai mare număr natural m, scris în baza 10, care poate fi obţinut prin una sau mai multe permutări circulare ale scrierii în baza 2 a numărului natural n.

Date de intrare

Fișierul de intrare b210.in conține pe prima linie numărul natural nenul n.

Date de ieșire

Fișierul de ieșire b210.out va conține pe prima linie numărul natural m, cu semnificaţia din enunţ.

Restricții și precizări

0 < n ≤ 1.000.000.000

Exemplu1

b210.in

13

b210.out

14

Explicație

Scrierea în baza 2 a lui 13 este 1101.

Numărul maxim scris în baza 10 a cărui scriere în baza 2 se poate obţine din permutări circulare ale scrierii în baza 2 a lui 13 este 14, a cărui scriere în baza 2 este 1110.

Exemplu2

b210.in

-10

b210.out

Date invalide in fisierul de intrare.

Rezolvare

#1505 B210
def decimal_to_binary(n):
  # Convertim numărul din baza 10 în baza 2
  return bin(n)[2:]

def rotate_left(s):
  # Rotim cifrele la stânga
  return s[1:] + s[0]

def find_largest_permuted_number(n):
  binary = decimal_to_binary(n)
  largest_number = n
  
  # Generăm toate permutările circulare
  for _ in range(len(binary) - 1):
      binary = rotate_left(binary)
      # Convertim înapoi în baza 10
      num = int(binary, 2)
      # Actualizăm cel mai mare număr
      largest_number = max(largest_number, num)
  
  return largest_number

def is_valid_input(n):
  # Verificăm dacă numărul este nenul și se încadrează în limitele impuse
  return 0 < n <= 1000000000

def main():
  with open("b210.in", "r") as f_in:
    n = int(f_in.readline().strip())

  if not is_valid_input(n):
    with open("b210.out", "w") as f_out:
      f_out.write("Date invalide in fisierul de intrare.")
    return
  
  # Determinăm cel mai mare număr permis
  largest_number = find_largest_permuted_number(n)
  
  # Scriem rezultatul în fișierul de ieșire
  with open("b210.out", "w") as f:
    f.write(str(largest_number))

if __name__ == "__main__":
  main()