1392 - Sumo

Sursa: [1]

---

Cerinţa

Numerele naturale nenule se scriu într-un şir astfel: 12345678910111213141516.... Fiind date numarul de perechi de poziţii din şir de forma (p,q), cu p≤q, să se calculeze suma cifrelor din şir situate pe poziţiile de la p la q.

Date de intrare

Fișierul de intrare sumo.in conține pe prima linie numărul dat, iar pe următoarele n linii câte o pereche de numere naturale (p,q), numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire sumo.out va conține pe fiecare linie de la 1 la numarul de pozitii câte un număr reprezentând suma cifrelor din şir corespunzătoare fiecărei perechi (p,q) din fişierul de intrare

Restricţii şi precizări

• 1 ≤ nr_perechi ≤ 100.000
• 1 ≤ p ≤ q ≤ 2.000.000.000

Exemplu

sumo.in

3

1 5

7 18

22 26

sumo.out

15

35

16

Explicație

De la poziţia 1 la 5 avem cifrele 12345 iar suma lor este 15, de la poziţia 7 la 18 avem cifrele 789101112131 iar suma lor este 35, iar de la poziţia 22 la 26 avem cifrele 16171 iar suma lor este 16.

Rezolvare

<syntaxhighlight lang="python" line>

def calc_suma(start: int, end: int) -> int:

   # Calculează suma cifrelor din șirul de numere de la start la end.
   # Șirul este construit prin concatenarea tuturor numerelor naturale nenule.
   # Exemplu: 12345678910111213141516...
   # start și end sunt numere naturale.

   # inițializăm variabila suma cu 0
   suma_digits = 0
   # șirul concatenat de numere
   sir = "".join([str(i) for i in range(1, end+1)])
   # adunăm cifrele de la start la end în sum_digits
   for i in range(start-1, end):
       suma_digits += int(sir[i])
   # returnăm suma
   return suma_digits

if __name__ == "__main__":

   # deschidem fișierele de intrare și de ieșire
   with open("sumo.in", "r") as fin, open("sumo.out", "w") as fout:
       # citim numărul de perechi de poziții
       nr_perechi = int(fin.readline().strip())
       # verificăm validitatea datelor de intrare
       if not (1 <= nr_perechi <= 100000):
           raise ValueError("n trebuie să fie între 1 și 100000")
       # pentru fiecare pereche de poziții
       for i in range(nr_perechi):
           # citim p și q din fișierul de intrare
           p, q = map(int, fin.readline().strip().split())
           # verificăm validitatea datelor de intrare
           if not (1 <= p <= q <= 2000000000):
               raise ValueError("p și q trebuie să fie numere naturale nenule și să respecte condiția p <= q <= 2000000000")
           # calculăm suma cifrelor pentru p și q
           suma_range = calc_suma(p, q)
           # scriem suma cifrelor în fișierul de ieșire
           fout.write(str(suma_range) + "\n")

</syntaxhighlight>