Nu aveti permisiuni pentru a descarca fisierul grader_test16.ok
Diferente pentru fmi-no-stress-7/solutii intre reviziile #7 si #8
Nu exista diferente intre titluri.
Diferente intre continut:
h1. Dicsi
Observăm că numerele de forma [1, 2, 4, 8, ..., 2^k^] necesită folosirea a $k + 1$ culori distincte. Putem obţine o astfel de colorare colorând numărul $i$ cu **suma exponenţilor din descompunerea în factori primi** a acestuia. Echivalent, putem folosi următoarea "euristică": $col[i] = 1 + max{col[d] | d divide pe i}$ (care dă, în final, acelaşi răspuns.
Observăm că numerele de forma [1, 2, 4, 8, ..., 2^k^] necesită folosirea a $k + 1$ culori distincte. Putem obţine o astfel de colorare colorând numărul $i$ cu **suma exponenţilor din descompunerea în factori primi** a acestuia. Echivalent, putem folosi următoarea "euristică": $col[i] = 1 + max{col[d] | d divide pe i}$ (care dă, în final, acelaşi răspuns). Calcularea se poate face în complexitate $O(n sqrt(n))$ cu divizori sau $O(n log(n))$ cu ciur.
h1. Blaturi
