4131 – Joc13

From Bitnami MediaWiki
Revision as of 18:18, 9 February 2024 by Cristina94 (talk | contribs)

Enunţ

Doi copii vor să joace un joc cu doi pioni și o tablă formată din N căsuțe numerotate de la 1 la N, așezate una după cealaltă, pe aceeași linie. Jocul are următoarele reguli:

  • se așază pionii pe prima căsuță de pe tablă (fiecare copil are propriul pion);
  • primul copil este cel care începe jocul;
  • copiii vin la tabla de joc alternativ;
  • cel care este la rând face, după regula de mai jos, una sau mai multe mutări înainte să cedeze locul celuilalt: calculează o valoare X în modul descris mai jos; își mută pionul înainte cu X poziții iar, dacă valoarea X calculată este 6, are dreptul la calcularea unei alte valori X, deci la încă o mutare, necedând încă locul celuilalt copil, iar dacă valoarea X este diferită de 6 cedează locul la tablă;
  • X se calculează după regula: dacă numărul mutării este impar atunci: X=((numărul_mutării + ((numărul_căsuței_pionului + N) mod 10)) mod 6) + 1, iar dacă numărul mutării este par atunci: X=((((numărul_mutării+1) mod 5) + ((numărul_căsuței_pionului + N) mod 10)) mod 6) + 1
  • unde N este numărul căsuțelor tablei de joc, numărul_mutării semnifică a câta mutare este, mod este operația prin care se obține restul împărțirii întregi a două numere, iar valoarea rezultată, X, este una dintre cifrele 1, 2, 3, 4, 5 sau 6, cum de altfel se deduce din formulele de mai sus.
  • în urma înaintării, dacă pionul ajunge pe o căsuță ocupată în acel moment de celălalt pion, îi ia locul acestuia, iar pionul care ocupa căsuţa este trimis la căsuța cu numărul 1 (întoarcerea acestui pion la poziția 1 nu se contorizează ca mutare);
  • dacă un pion, după înaintare, ar ajunge în afara tablei de joc, este așezat pe căsuța N (ultima);
  • este câștigător copilul care ajunge primul cu pionul la căsuţa N de pe tabla de joc, și atunci jocul se încheie.

Cerința

Dându-se numărul N, determinați:

  • Numărul divizorilor lui N;
  • Numărul maxim de apariții ale unei valori calculate în timpul jocului prin formulele descrise;
  • Numerele căsuțelor ocupate, în timpul jocului, de pionul câștigătorului în ordinea în care acestea sunt vizitate.

Date de intrare

Pe prima linie a fișierului joc.in se află două numere naturale, C și N separate printr-un spațiu. Dacă C=1, atunci se rezolvă doar prima cerință, dacă C=2, atunci se rezolvă doar a doua cerință iar dacă C=3, atunci se rezolvă doar cea de-a treia cerință.

Date de ieșire

Fișierul de ieșire este joc.out. Dacă C=1 sau C=2, acesta conține un număr natural ce reprezintă răspunsul pentru cerința respectivă. Dacă C=3, acesta conține un șir de numere naturale, separate prin câte un spațiu, care reprezintă răspunsul pentru a treia cerință.

Restricții și precizări

  • 2 ≤ N ≤ 10.000
  • Pentru teste în valoare de 23 de puncte, C=1
  • Pentru alte teste în valoare de 33 de puncte, C=2
  • Pentru alte teste în valoare de 44 de puncte, C=3
  • Se garantează că există un câștigător
  • Pe parcursul jocului, copii pot ajunge pe căsuțe pe care le-au mai vizitat
  • Se garantează că numărul căsuțelor ocupate de copii este mai mic decât 100.000
  • Problema nu urmăreşte găsirea vreunei proprietăţi speciale pentru șirurile de valori calculate prin formulele date.

Exemplul 1

joc.in
1 10
joc.out
4

Explicație

C=1 deci se rezolvă prima cerință. N=10 are 4 divizori.

Exemplul 2

joc.in
2 10
joc.out
2

Explicație

C=2 deci se rezolvă a doua cerință. Ambii pioni se află la căsuța 1. Mută primul copil (pionul acestuia se află la căsuța 1).

  • suntem la prima mutare (număr impar);
  • se calculează cifra pentru înaintarea pionului: X = (1 + (1 + 10) mod 10) mod 6 + 1 = 3
  • primul jucător înaintează pionul de la căsuța 1 la căsuța 4

Mută al doilea copil (pionul acestuia se află la căsuța 1)

  • suntem la a doua mutare (număr par);
  • se calculează cifra pentru înaintarea pionului: X = ((((2 + 1) mod 5) + ((1+10) mod 10)) mod 6) + 1 = 5
  • al doilea copil înaintează pionul de la căsuța 1 la căsuța 6

Mută primul copil (pionul acestuia se află la căsuța 4)

  • suntem la a treia mutare (număr impar);
  • se calculează cifra pentru înaintarea pionului: X= (3 + (4 + 10) mod 10) mod 6 + 1 = 2
  • primul copil înaintează pionul de la căsuța 4 la căsuța 6
  • cum pionul celui de-al doilea copil se află la căsuța 6 el este întors la prima căsuță, deci pionul celui de-al doilea copil ocupă acum căsuța 1

Mută al doilea copil (pionul acestuia se află la căsuța 1)

  • suntem la a patra mutare (număr par);
  • se calculează cifra pentru înaintarea pionului: X = ((4 + 1) mod 5 + (1 + 10) mod 10) mod 6 + 1 = 2
  • al doilea copil deplasează pionul de la căsuța 1 la căsuța 3

Mută primul copil (pionul acestuia se află la căsuța 6)

  • suntem la a cincea mutare (număr impar);
  • se calculează cifra pentru înaintarea pionului: X = (5 + (6 + 10) mod 10) mod 6 + 1 = 6
  • primul copil deplasează pionul de la căsuța 6 la căsuța 10 (ar trebui să se deplaseze la căsuța 12 care este în afara tablei de joc)
  • cifra este 6, copilul are dreptul la încă o mutare dar a ajuns deja cu pionul la căsuța de final și se termină jocul.

Primul copil este câștigător. Cifrele calculate au fost, în ordine, 3 5 2 2 6, cifra 2 a apărut de cele mai multe ori adică de 2 ori.

Rezolvare

<syntaxhighlight lang="python" line>

  1. 4131 joc13

import string

def numar_maxim_dublari(s):

   lungime_s = len(s)
   
   for lungime in range(1, lungime_s + 1):
       substr = s[:lungime]
       
       if s == substr * (lungime_s // lungime):
           return lungime_s // lungime
   return 1

def validate_input(s):

   if not s:
       return False, "Șirul de caractere nu poate fi gol."
   if not all(ch in string.ascii_lowercase for ch in s):
       return False, "Șirul de caractere trebuie să conțină doar litere mici ale alfabetului englez."
   return True, None

def main():

   s = input("Introduceți șirul de caractere: ")
   is_valid, error_message = validate_input(s)
   if not is_valid:
       print("Date de intrare invalide:", error_message)
       return
   rezultat = numar_maxim_dublari(s)
   print("Numărul maxim de operații de dublare este:", rezultat)

if __name__ == "__main__":

   main()

</syntaxhighlight>