4131 – Joc13

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

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>