• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie Fulle2

VPS Starter Arubacloud
0 głosów
209 wizyt
pytanie zadane 1 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
edycja 1 kwietnia 2023 przez pasjonat_algorytmiki

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!

komentarz 1 kwietnia 2023 przez polandonion Mądrala (6,970 p.)
przywrócone 1 kwietnia 2023 przez polandonion
Popraw link. Osoby, ktorych nie ma na tym contescie, w tym ja, nie widza tresci zadania. Wyskakuje blad 403.
komentarz 1 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
a drugim linkiem można wejść?
komentarz 1 kwietnia 2023 przez polandonion Mądrala (6,970 p.)
no wlasnie nie
komentarz 1 kwietnia 2023 przez polandonion Mądrala (6,970 p.)

sprobuj zapisac strone jako pdf i udostepnij ja np. tutaj

komentarz 1 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
a takie zdjęcie powinno być ok?
komentarz 1 kwietnia 2023 przez polandonion Mądrala (6,970 p.)
widac wszystko wyraznie :D
komentarz 1 kwietnia 2023 przez Whistleroosh Maniak (56,900 p.)
Może zachłan? Bierzemy 2 rodzaje kart, pierwszy rodzaj dzielimy na segmenty 2, 3, 2, 3..., drugi na segmenty 3, 2, 3, 2... i parujemy odpowiednio ze sobą (2->3, 3->2, 2->3, itd.). Jeśli w jednym rodzaju zostanie dużo kart to możemy korzystać z zamian żeby to jakos poprawnić np. sparowalismy 2->3, 2->3 to zamieniamy to na 3->2, 3->2, 3->2 (tylko trzeba dobrać 5 wolnych kart pierwszego rodzaju)

To powinno dać w miarę dobre oszacowanie wyniku. Może da się to dociągnąć do wzorcówki
komentarz 1 kwietnia 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Ale to się chyba niestety wywali.
komentarz 1 kwietnia 2023 przez Whistleroosh Maniak (56,900 p.)
Nie mówię, że się nie wywali. Ale powinno dać wynik, który nie różni się bardzo od poprawnego i który może można poprawnić do porpawnego. Bardziej chodzi o to, żeby zastanowić się czy istnieją jakieś zależności między tymi parowaniami. Np. w tym pomyśle wyżej zamieniałem 2->3, 2->3 na 3->2, 3->2, 3->2 i to zwiększyło wynik o 1

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

0 głosów
1 odpowiedź 184 wizyt
0 głosów
1 odpowiedź 107 wizyt
pytanie zadane 16 czerwca 2023 w Algorytmy przez nerfiko Nowicjusz (170 p.)
0 głosów
1 odpowiedź 154 wizyt
pytanie zadane 24 kwietnia 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,452 zapytań

141,262 odpowiedzi

319,077 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...