Baš je brute force.
Grupe od 5 su produktivnije od grupa od 3 i poenta je napraviti što više grupa od 5 i što manje grupa od 3. Uslov da početni broj robota mora biti veći od 7 je ustvari hint jer se svi prirodni brojevi veći od 7 mogu faktorisati pomoću prostih brojeva 3 i 5.
Dakle od početnog broja robota se oduzimaju grupe po 3 dok se ne dobije broj deljiv sa 5 sve ostalo su grupe po 5 robota, ostatak tj. nezaposlenih robota nikada neće biti.
Ako te profesor pita za objašnjenje:
8 -> 1*5 +
1*3
9 -> 0*5 +
3*3
10 -> 2*5 +
0*3
11 -> 1*5 +
2*3
12 -> 0*5 +
4*3
13 -> 2*5 +
1*3
14 -> 1*5 +
3*3
15 -> 3*5 +
0*3
16 -> 2*5 +
2*3
17 -> 1*5 +
4*3
18 -> 3*5 +
1*3
19 -> 2*5 +
3*3
Ako pogledaš broj grupa po tri robota (boldovano), može se uočiti patern
1-3-0-2-4. Dakle broj grupa od tri robota će uvek biti 0 do 4, i to će se ciklično ponavljati počevši od 8.
Tako za bilo koji broj robota možemo da izračunamo index u ovom nizu
1-3-0-2-4 po formuli:
(brojRobota - 8)
mod 5
Dakle od broja robota oduzimamo 8 jer nam je to startna pozicija, index nula u onom gore nizu, i onda cepamo dalje po modulu 5 jer imamo 5 članova niza.
Na primer 2166 robota:
(2166 - 8) mod 5 = 2158 mod 5 =
3
Dakle iz niza nam treba član sa indexom 3.
10-31-02-23-44 (manji font su indexi niza)
To je u ovom slučaju član koji ima vrednost 2, što znači da će biti 2 grupe od 3 robota.
od početnog broja 2166 oduzimamo tih 6 robota, preostali broj robota tj. 2160 delimo na grupe po 5, dakle imaćemo 432 grupe po 5 robota ili ukupno:
2166 = 2*3 + 432*5
Grupisanje možeš odraditi ovako bez petlji, dovoljno je da napraviš niz koji će da čuva brojeve
1-3-0-2-4 i da po formuli (brojRobota - 8)
mod 5 izračunaš index niza, uzmeš broj i to ti je broj grupa po 3 robota. Od ukupnog broja robota oduzmeš broj robota koji idu u grupe po 3 i dobijeni broj podeliš sa 5 kako bi dobio broj grupa po 5 robota.
Što se tiče dana, najlakše je da uradiš iteracijom, tj. for petljom, ovako kako je Bahati uradio, dakle samo skroz spoljna petlja, ove unutra menjaš sa ovim što sam ti napisao gore.
Edit:
Evo ga prepravljen kod koji je napisao Bahati, ovo je Java kod, daje isti rezultat kao i njegov (za 11 i 11), vreme izvršavanja < 1ms.
Kod:
int dayone = 0;
int daytwo = 0;
int current = 11; //input robota > 7
int numofdays = 11; //input dana >= 0
int max = 0;
int[] threeMemberGroupsPattern = {1, 3, 0, 2, 4};
for (int i = 0; i < numofdays; i++) {
max = 0;
current -= dayone; //oduzimaju se "mrtvaci"
int threeMemberGroups = threeMemberGroupsPattern[(current - 8) % 5];
int fiveMemberGroups = (current - threeMemberGroups * 3) / 5;
max = current + threeMemberGroups * 5 + fiveMemberGroups * 9;
// pomeranje na "stack-u" dana...
dayone = daytwo;
daytwo = current;
current = max;
}
System.out.println(current); // output resenje kada je prosao sve dane
![Bahati [SiD]](/data/avatars/m/1/1880.jpg?1612629395){kind=avatar}
