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

Zadanie Apple Catching usaco gold

Object Storage Arubacloud
+1 głos
92 wizyt
pytanie zadane 29 marca w C i C++ przez Dani Obywatel (1,450 p.)
Cześć, zastanawiam się nad rozwiązaniem do zadania : https://usaco.org/index.php?page=viewproblem2&cpid=1233 .

Czytając omówienie nie do końca rozumiem jak rozwiązać ten problem. Może znalazłby się ktoś kto mógłby mi w tym pomóc. https://usaco.guide/problems/usaco-1233-apple-catching/solution

Z góry wielkie dzięki!
komentarz 29 marca przez adrian17 Ekspert (344,800 p.)
Nie napisałeś, czego konkretnie w tym proponowanym rozwiązaniu nie rozumiesz :( To raczej nikt nie wie z czym pomóc.
komentarz 30 marca przez Dani Obywatel (1,450 p.)
Ogólnie to z tego co rozumiem to wychodzą nam dwie nierówności, następnie mamy zamienić jabłka i krowy na punkty : (xi​−ti​,xi​+ti​). Niestety nie do końca rozumiem dalszego rozwiązania. Co powinniśmy zrobić jak juz mamy te punkty?

1 odpowiedź

+2 głosów
odpowiedź 30 marca przez Whistleroosh Maniak (56,980 p.)

Z tych dwóch otrzymanych nierówności wynika, że żeby krowa złapała jabłko, musi sie ono znajdować powyżej i na lewo krowy w układzie współrzędnych. Pozostają 2 pytania:

1. Czy jeżeli jabłko może być złapane przez 2 krowy A i B (B jest bardziej na prawo od A) to która krowa powinna je złapać?

Możemy założyć, że w optymalnym rozwiązaniu krowa B złapała jabłko. Ale nic nie stoi na przeszkodzie, żeby to jednak krowa A złapała to jabłko i rozwiązanie wciąż pozostanie optymalne. Sugeruje to, że możemy wybierać krowy zachłannie od lewej do prawej.

2. Jeśli zdecydujemy się żeby krowa C złapała jakieś jabłko, to które dokładnie powinna złapać?

Jasne jest, że krowy, które są wyżej mają potencjalnie mniejszy wybór jabłek niż krowy, które są niżej. W takim razie krowa C powinna wybierać najniżej położone jabłko, które może złapać, żeby nie podbierać jabłek innym krowom położonym wyżej.

Te obserwacja sugerują, że można przeglądać krowy posortowane od lewej do prawej i dla każdej wybierać najniżej położone jabłko.

Podobne pytania

0 głosów
1 odpowiedź 258 wizyt
pytanie zadane 8 kwietnia 2021 w Algorytmy przez wojtek_suchy Mądrala (6,880 p.)
0 głosów
0 odpowiedzi 123 wizyt
0 głosów
1 odpowiedź 602 wizyt
pytanie zadane 30 maja 2022 w C i C++ przez polandonion Mądrala (6,970 p.)

92,524 zapytań

141,357 odpowiedzi

319,382 komentarzy

61,914 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

Kolejna edycja największej imprezy hakerskiej w Polsce, czyli Mega Sekurak Hacking Party odbędzie się już 20 maja 2024r. Z tej okazji mamy dla Was kod: pasjamshp - jeżeli wpiszecie go w koszyku, to wówczas otrzymacie 40% zniżki na bilet w wersji standard!

Więcej informacji na temat imprezy 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!

...