Diskusija o drugom krugu kvalifikacija

@milosh
To je kao rešenje za zadatak http://www.spoj.com/problems/PRIME1/
Tj. generisu se svi prosti brojevi do 10^6, i onda se koriste ti brojevi za ispitivanje brojeva do 10^12

1 Like

Nisam na to mislio, inače može i do 10^18 (i više)

Šta je bilo, prpa? :slight_smile:

1 Like

Iskreno i dalje mislim da mi je 4. tacan, mogu da posaljem kod ali me je strah da mi ne nadjete test gde ne radi

Koliko sam primetio, rešenje za drugi je prvi prost broj manji od Ai (ili kako se već zvaše), tj. broj sa najmanjom trivijalnošću u intervalu [2, n] je prvi prost broj <= n, tako da sam bio razočaran kad sam video koliko su mala ograničenja.

Ograničenja su takva da bi prolazili i neki malo sporiji algoritmi, ipak je 2. zadatak

Razmisli o tome sta se desava ako je cena za potez mnogo velika, a cena jednog dzokera bas mala.

Ja sam uradio DP trivijalnost(x) = (trivijalnost(najvecidelilac) * delilac + broj)/broj valjda ce raditi za sve

Četvrti je klasičan https://en.wikipedia.org/wiki/Hirschberg's_algorithm, samo je još potrebno da se implementiraju poeni.

Jasno, samo šteta da je zadatak sa toliko različitih rešenja tek drugi (inače mi se sviđa bez obzira što je jednostavan).

Meni to ne deluje tačno

2 Likes

btw kako dokazati da je resenje prethodni prost broj. Nikako nisam mogao da dokazem

bruteforcovao sam da bih dokazao

trivijalnost(10) = 1.8
trivijalnost(5) = 3 edit: trivijalnost(5) = 1.2
(trivijalnost(5)*5 + 10) /10 = 2.5 edit: = 1.6

Neka je x slozen broj a p neki njegov prost delilac. Onda se lako pokazuje da je trivijalnost od p manja od trivijalnosti od x. Dakle dovoljno je gledati samo proste brojeve. A najtrivijalniji je onaj koji je najveci.

2 Likes

Ali trivijalnost od 5 je 1.2 :slight_smile:

36 ti je kontraprimer

nebitno nebitno nebitno

Moja greska, delio sam sa brojem delioca slucajno, svakako primer radi

I ja mislim da sam negde pogresio, kad unesem do 20k, bude 19999 a trebalo bi 19997 T_T