2120 - Concurs 4

Enunţ

La concursul de patinaj artistic din acest an s-au înscris n concurenţi. După înscriere, participanţilor li se asociază coduri numerice distincte aparţinând mulţimii primelor n numere prime.

Pentru a stabili ordinea intrării în concurs, concurenţii sunt aşezaţi în cerc, după care se procedează astfel:

primul participant în concurs este cel situat pe poziţia 1 pentru alegerea celorlalţi, se parcurge circular lista de concurenţi, alegând din k în k, câte un unul, până la repartizarea tuturor. Regulamentul prevede ca participanţii să intre în concurs în ordinea crescătoare a codurilor lor.

Cerința

Cunoscând numărul n de concurenţi precum şi numărul k folosit la repartizarea concurenţilor în concurs, se cere să se determine şirul codurilor asociate concurenţilor, astfel încât intrarea lor în concurs să se facă conform regulamentului.

Date de intrare

Fişierul concurs4.in conţine pe prima linie numerele naturale n şi k cu semnificaţiile din enunţ.

Date de ieșire

Fişierul concurs4.out va conţine n numere naturale separate prin câte un spaţiu, reprezentând şirul codurilor asociate concurenţilor, astfel încât intrarea lor în concurs să se facă conform regulamentului.

Restricții și precizări

• 2 ≤ k ≤ n ≤ 30000

Exemplu 1

concurs4.in

10 4

concurs4.out

2 29 23 7 3 17 13 19 5 11

Explicație

Distribuirea codurilor se face astfel: 2 29 23 7 3 17 13 19 5 11 Numărând din 4 în 4, începând cu primul cod, se obţine următoarea listă: 2 3 5 7 11 13 17 19 23 29 reprezentând primele 10 numere prime.

Exemplu 2

concurs4.in

1 1

concurs4.out

Valorile pentru n si k trebuie sa fie in intervalul [2, 30000].

Rezolvare

#2120 Concurs4
def este_prim(numar):
    if numar < 2:
        return False
    for i in range(2, int(numar ** 0.5) + 1):
        if numar % i == 0:
            return False
    return True

def genereaza_prime(n):
    prime = []
    numar = 2
    while len(prime) < n:
        if este_prim(numar):
            prime.append(numar)
        numar += 1
    return prime

def alege_concurenti(n, k):
    prime = genereaza_prime(n)
    concurenti = []

    index = 0
    while len(concurenti) < n:
        index = (index + k - 1) % len(prime)
        concurenti.append(prime.pop(index))
    return concurenti

def verifica_date_intrare(n, k):
    if not (2 <= k <= n <= 30000):
        with open("concurs4.out", "w") as f:
            f.write("Valorile pentru n si k trebuie sa fie in intervalul [2, 30000].")
        exit()

def main():
    with open("concurs4.in", "r") as f:
        n, k = map(int, f.readline().split())
        verifica_date_intrare(n, k)

    coduri_concurenti = alege_concurenti(n, k)

    with open("concurs4.out", "w") as f:
        f.write(" ".join(map(str, coduri_concurenti)))

if __name__ == "__main__":
    main()