Vizualizare sursă pentru „0722 - Cifru”


Alibaba trebuie să descopere cifrul care deschide cufărul cu comoara cea mare. Cifrul este foarte greu de găsit. El a descoperit mai multe pietre, fiecare piatră având o altă culoare, pe fiecare piatră fiind scris un număr natural cu cel mult <code>4</code> cifre. Alibaba observă că numerele de pe fiecare piatră sunt distincte două câte două. Regula după care se formează cifrul este una foarte simplă, şi Alibaba a reuşit să o obţină destul de uşor: cifrul este format din alăturarea într-o anumită ordine a tuturor pietrelor. Ceea ce Alibaba mai ştie este că pe poziţia <code>p</code> din cifru se găseşte cu siguranţă cifra <code>k</code>.

= Cerința =
Scrieţi un program care determină numărul de variante de cifruri pe care va trebui să le încerce Alibaba. Numărul fiind foarte mare se va calcula modulo <code>46337</code>.

= Date de intrare =
Fișierul de ieșire <code>cifru.out</code> va conține pe prima linie trei numere naturale <code>n</code>, <code>p</code> şi <code>k</code> separate printr-un spaţiu, reprezentând numărul total de numere de pe pergament, poziţia <code>p</code> şi respectiv cifra <code>k</code> care se găseşte pe poziţia <code>p</code> în cifru. Pe următoarele <code>n</code> linii se găseşte câte unul din cele <code>n</code> numere de pe pergament.

= Date de ieșire =
Pe prima linie a fişierului de ieşire <code>cifru.out</code> se va scrie un număr natural reprezentând numărul de variante modulo <code>46337</code> de cifruri pe care va trebui să le încerce Alibaba.

= Restricții și precizări =

* <code>0 < n < 25</code>
* Numerele de pe fiecare piatră sunt strict pozitive mai mici decât <code>10000</code> şi sunt distincte două câte două.
* <code>0 ≤ k ≤ 9</code>
* Două cifruri diferă între ele prin ordinea de aşezare a pietrelor, chiar dacă numărul obţinut prin citirea numerelor de pe pietre este aceeaşi. De exemplu dacă există trei pietre având inscripţionate numerele <code>12</code>, <code>3</code> şi respectiv <code>123</code>, ele se pot lipi astfel: <code>12-3-123</code>, <code>123-12-3</code>, cele două cifruri considerându-se diferite, cifrele având culori diferite.

== Rezolvare ==
<syntaxhighlight lang="python3">
MOD = 46337  

def count_cipher_variants(n, p, k, numbers):
    """Calculates the number of cipher variants modulo MOD."""
   
    total_variants = 1  # One variant with all numbers fixed except for the given one
    fixed_numbers = set([k])  # Set of fixed numbers (initially only k)
    remaining_numbers = set(numbers) - fixed_numbers  # Set of remaining numbers

    for i in range(p - 1, -1, -1):
        choices_for_position_i = len(remaining_numbers)
        total_variants *= choices_for_position_i

       
        fixed_numbers.add(numbers.pop(i))  # Add the number to fixed numbers
        remaining_numbers.remove(numbers.pop(i))  # Remove it from remaining numbers
    return total_variants % MOD

def main():
    n, p, k = map(int, input().split())
    numbers = [int(input()) for _ in range(n)]

    cipher_variants = count_cipher_variants(n, p, k, numbers)
    print(cipher_variants)

if __name__ == "__main__":
    main()

</syntaxhighlight>