0982 - Puteri1: Difference between revisions

Newer edit →

Revision as of 20:19, 23 March 2023

Cerință

Se dau n numere naturale. Aflați câte dintre acestea se pot scrie ca sumă de puteri distincte ale unui număr natural k.

Date de intrare

Programul citește de la tastatură numerele k și n, iar apoi n numere naturale, separate prin spații.

Date de ieșire

Programul va afișa pe ecran numărul de numere din șirul dat care se pot scrie ca sumă de puteri distincte ale lui k.

Restricții de precizări

1 ⩽ n ⩽ 10000

2 ⩽ k ⩽ 10

cele n numere citite vor fi mai mici decât 1.000.000

Exemplul 1

Intrare

5

3

6 37 12 9 5

Ieșire

Datele introduse corespund restricțiilor impuse.

3

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line="1" start="1"> def validare(n, k):

   return 1 <= int(n) <= 100_000 and 2 <= int(k) <= 10

def numar_puteri_distincte(n, k):

   nr = 0
   for i in range(1, n + 1):
       x = int(input("numbers:"))
       c = 1
       while x != 0:
           if x % k > 1:
               c = 0
               break
           x //= k
       if c:
           nr += 1
   return nr

if __name__ == "__main__":

   n = input("n: ")
   k = input("k: ")
   if validare(n, k):
       n, k = int(n), int(k)
       x = numar_puteri_distincte(n, k)
       print("Datele introduse corespund restricțiilor impuse.")
       print(x)
   else:
       print("Datele introduse nu corespund restricțiilor impuse.")

</syntaxhighlight>

@@ Line 27: / Line 27: @@
 :3
-== Rezolvare ver. 1 ==
+==Rezolvare==
+=== Rezolvare ver. 1 ===
 <syntaxhighlight lang="python" line="1" start="1">
-def validare(n, k, puteri):
+def validare(n, k):
-     return n.isdigit() and 1 <= int(n) <= 10000
+     return 1 <= int(n) <= 100_000 and 2 <= int(k) <= 10
-    return k.isdigit() and 2 <= int(k) <= 10
-def numar_puteri_distincte(n, k, puteri):
+def numar_puteri_distincte(n, k):
-     if n == 0:
+     nr = 0
-         return True
+    for i in range(1, n + 1):
-    elif n < 0 or k == 0:
+         x = int(input("numbers:"))
-        return False
+        c = 1
-    elif n in puteri:
+        while x != 0:
-        return False
+            if x % k > 1:
-    else:
+                c = 0
-         puteri.add(n)
+                break
-        return numar_puteri_distincte(n-k**k, k+1, puteri) or numar_puteri_distincte(n, k+1, puteri)
+            x //= k
+         if c:
+            nr += 1
+    return nr
-    numere = []
-    for i in range(numere):
-        numere.append(int(input("Introduceti numarul {}: ".format(i+1))))
-        numar_numere_puteri = 0
-    for numar in numere:
-        if numar_puteri_distincte(numar, k, set()):
-            numar_numere_puteri += 1
-    print("Numarul de numere din sirul dat care se pot scrie ca sumă de puteri distincte ale lui k este: {}".format(
-        numar_numere_puteri))
-if __name__ == '__main__':
-    n = int(input("Introduceti numarul de numere: "))
-    k = int(input("Introduceti numarul k: "))
-    numere = int(input("Introduceti numarul: "))
+if __name__ == "__main__":
+    n = input("n: ")
+    k = input("k: ")
+    if validare(n, k):
+        n, k = int(n), int(k)
+        x = numar_puteri_distincte(n, k)
+        print("Datele introduse corespund restricțiilor impuse.")
+        print(x)
+    else:
+        print("Datele introduse nu corespund restricțiilor impuse.")
-if validare(n, k, numere):
-    n, k, numere = int(n), int(k),  int(numere)
-    print("Datele introduse corespund restricțiilor impuse.")
-    numar_puteri_distincte(n, k, numere)
-else:
-    print("Datele introduse nu corespund restricțiilor impuse.")
 </syntaxhighlight>