Mam problem z takim zadaniem:
Nie wiem jak je zrobić w dobrej złożonności, ale mam kilka przemyśleń:
- rodzaje kart nie mają znaczenia, tylko liczy się liczba wystąpień
- jeżeli karta występuje raz, to jej nie użyjemy, dwa razy to zawsze co najwyżej za dwa, a tak jak występuje więcej niż dwa razy, to możemy dzielić ją na kilka (być może zero) wystąpień trójek i dwójek. Czyli jeśli S to suma wystąpień danego rodzaju, to można użyć ją postacią: 3x + 2y, gdzie y,x to liczby naturalne(oczywiście 3x+2y <= S).
- Podejrzewam, że wejdzie tu coś wykładniczego do liczby różnych kart, ale nie wiem jak
Btw. to zadanie to praktycznie kopia z 2 etapu tegorocznego OIJ(fulle), tylko tam każda karta występowała max 4 razy, więc było prościej. A samo to zadanie fulle 2 pochodzi z contestu OKI 2022, olimpiada od podstaw.
Z góry dziękują za poświęcony czas!