Danciu: Pagină nouă: 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 `4` 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: cif...

2024-06-04T08:28:07Z

Pagină nouă: 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: cif...

New page

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>

0722 - Cifru - Revision history