Paliwo [FR_18_02] [link]
Poziom trudności wg autora zadania: łatwe
Złożoności występujące w zadaniu: zadanie elementarne (arytmetyczne)
Inspiracja
Zadanie wynikające z rzeczywistości zawodowej dosyć wielu osób, w tym funkcjonujących na niniejszym portalu. Rzeczywistość ta została opisana pokrótce w treści zadania. W aktualnym stanie prawnym obliczenia prowadzić należy identycznie, przy czym pojawia się jeszcze zagadnienie zaokrągleń, np. VAT naliczony podlegający odliczeniu zaokrągla się do pełnych złotych. W zadaniu abstrahowałem od tej kwestii.
Rozwiązanie
Wskazówka nr 1
Z treści wynika, że:
netto + vat = brutto.
Wskazówka nr 2
Czyli:
vat = brutto - netto
Wskazówka nr 3
Czyli:
print(vat / 2, netto + vat / 2)
Oczywiście, wynik należy podać z dokładnością do 2. miejsca po przecinku!
Uwagi pozostałe
- To nie są przychody, jak niektórzy pisali w swoich rozwiązaniach, ale koszty (uzyskania przychodów)! Jaś kupił paliwo więc nie zyskał, ale stracił!
- Niektórzy mnożyli netto przez 23% by uzyskać VAT. Było to niezgodne z treścią zadania, ale też - co może zaskoczyć rozwiązujących - ze stanem prawnym! Stawki podatku (tzw. matryca stawek) ustalane są zupełnie inaczej (por.: art. 41 Ustawy z dnia 11 marca 2004 r. o podatku od towarów i usług (Dz.U. Dz.U.2023.1570, a zwłaszcza art. 41 ust. 16). Jeszcze dość niedawno stawki podatku za paliwo były obniżone.
Zakres czujnika [FR_18_09] [link]
Poziom trudności wg autora zadania: łatwe
Złożoności występujące w zadaniu: zadanie programistyczne dotyczące systemu binarnego
Inspiracja
Zadanie rozszerzające problematykę kodowania, której poświęcono już problem FR_02_11. Moim celem było jednak wyjście poza kwestię U2 (bo formalnie kodujemy co chcemy jak chcemy) przy szerszym zakresie danych.
Rozwiązanie
Wskazówka nr 1
Z treści wynika, że unsigned long long int zmieści liczby dodatnie, ale czy zmieści liczby ujemne?
Wskazówka nr 2
W języku C++ można wczytać liczbę jako string, a następnie informację o znaku przechować np. w zmiennej typu bool, a moduł liczby - w zmiennej typu unsigned long long. Można też wykorzystać język Python. Nie są to jedyne rozwiązania, żeby wspomnieć o __int128_t.
Wskazówka nr 3
Pozostaje implementacja i tu nie ma żadnych wskazań ani przeciwwskazań. Bitesty, operatory bitowe, rozwiązania elementarne (np. pisanie po tablicy charów), ... .
Uwagi pozostałe
Mały Książę [FR_18_10] [link]
Poziom trudności wg autora zadania: łatwe
Złożoności występujące w zadaniu: trygonometria
Inspiracja
Problem pochodzi z kultowego podręcznika fizyki. Zawsze bardzo mi się podobał i jak się okazało, spodobał się również zespołowi od Fraktala. W istocie, było to jedno z zadań, które przygotowałem w 2018 r., a którego nie mogłem wrzucić na SPOJa. No i tak od słowa (zdania?) “weźta se moje zadania jeśli chceta bo ja je chciałem wszystkie wywalić” doszliśmy do mojego udziału w przygotowywaniu tej edycji konkursu 
W ten sposób, w miarę płynnie, przechodzę do podziękowań dla ekipy, a zwłaszcza dla @quenthui, za anielską wręcz cierpliwość przy testowaniu zadań, tym bardziej przy moich licznych problemach z systemem, który dopiero poznawałem, a także dla @macbon, za naszą ostatnią rozmowę i dalsze prowadzenie za rękę oraz poprawki np. w treści zadania Karuzela VAT. Bez Twojej uwagi o skrzyżowaniach, liczba rozwiązań byłaby mniejsza. A wracając do zadania, poniżej cytat na zachętę.
Rozwiązanie
Wskazówka nr 1
Zajrzyj do książki. Z niej też dowiesz się, czy problem wymyślili autorzy podręcznika, czy też jest on znany od dłuższego czasu.
Uwagi pozostałe
- Zadanie posiada sporą wadę, która wyklucza je na większości konkursów algorytmicznych: nie operuje na liczbach całkowitych. Fakt ten starałem się zniwelować oczekując bardzo niskiej dokładności rozwiązania.
- Zauważyłem, że wielu ludzi operowało błędnym wzorem, ale było na tyle przekonanych o jego poprawności, iż walczyło z dokładnością obliczeń.
- W ramach testów odporności na obliczenia numeryczne testowanych było wiele rozwiązań operujących na wielu zależnościach trygonometrycznych. Wydaje mi się, że jeśli ktoś nie przekombinował (np. wykorzystując 200 sinusów i 50 sekansów), AC nie powinno być problemem. Jeżeli jednak ktoś jest pewien, że nie mam racji, proszę o info - poprawię testy (zadanie zyska na wartości dla przyszłych rozwiązujących) oraz poprawię się (mniejsza szansa na wtopę, np. gdybym w przyszłości miał coś układać na Fraktal).
- W książce zwrócono uwagę na dwa rozwiązania: uproszczone (wynikające z obserwacji, iż wzrost człowieka jest pomijalny względem rozmiarów planety) oraz pełne. Testy do zadania dobrałem tak, że oba rozwiązania dostaną AC.
Skrzyżowanie I [FR_18_11] [link]
Poziom trudności wg autora zadania: łatwe / średnie
Złożoności występujące w zadaniu: kinematyka
Inspiracja
Problem, w postaci bardzo ogólnej i nieścisłej, został zaprezentowany po raz pierwszy przez fizyka dr Krzysztofa Kaczora, bodaj na jakimś zastępstwie, jeszcze w czasach gdy “cierpiałem” na szkołę. Moje autorstwo sprowadza się do jego uściślenia, wprowadzenia wymiarów, zdefiniowania kilku pojęć oraz znalezienia rozwiązania (dobrą dekadę po “wyleczeniu” się ze szkoły). A przypomniałem sobie o tym problemie dlatego, że pracowałem kiedyś nad sztuczną inteligencją (przetwarzanie mowy i tekstu, coś typu “czy jutro będzie padać między trzecią a czwartą na najbliższej stacji benzynowej?”) do samochodów, a że moda na samochody autonomiczne już trwała to aż się chciało zapytać, czy zmniejszą one korki (patrz: Skrzyżowanie II). Dokładnie stąd wzięła się seria zadań o skrzyżowaniach.
Rozwiązanie
Wskazówka nr 1
Czy wymiary wszystkich zmiennych są zgodne i nadają się do przeliczeń? Czy wiesz, czym są w kinematyce: droga, prędkość, czas, przyspieszenie?
Wskazówka nr 2
Rozwiązanie buduj kawałek po kawałku. Przykładowo, wyobraź sobie, że wszystkie auta ruszają jednocześnie i zatrzymują się jednocześnie po jakimś czasie, np. po minucie. Każde z nich przebyło pewną drogę (identyczną jak inne pojazdy). Przez co należy podzielić tę drogę, aby ustalić, ile aut łącznie przejechało przez skrzyżowanie?
Wskazówka nr 3
Funkcje min oraz max mogą Ci pomóc zapisać jedno zgrabne wyrażenie na drogę pokonaną przez każdy pojazd zamiast wielu ifów. Oczywiście, jeśli wolisz ify, nie ma w tym niczego złego.
Wskazówka nr 4
floor((a * pow(min(V / a, dt), 2.0) / 2.0 + V * max(dt - V / a, 0.0)) / (l + d))
Uwagi pozostałe
- Porównaj wyniki zadań Skrzyżowanie I oraz Skrzyżowanie II. Odpowiedz na pytanie: czy samochody autonomiczne mogą usprawnić przejazdy przez skrzyżowania?
- Czym są w kinematyce udar i zryw?
- (Jeżeli potrafisz rozwiązać równania różniczkowe oraz umiesz rozwijać funkcje w szereg to) wychodząc od przyspieszenia a = const, wyprowadź wzór na drogę. Wykonaj te same kroki dla udaru = const, a potem dla zrywu = const. Czy uzyskane wyniki kojarzą Ci się z czymś ważnym w matematyce?
Epidemia [FR_18_15] [link]
Poziom trudności wg autora zadania: łatwe / średnie
Złożoności występujące w zadaniu: dużo treści (symulacja)
Inspiracja
Modele epidemii są dość liczne i różne. Zainteresowanych odsyłam np. do modelu SIR. Zainteresowanych równaniami różniczkowymi odsyłam jeszcze bardziej, bo można sobie ułożyć układ równań samemu. Ten model jest modelem - nazwa własna - typu zombie. Ot, Antosia coś ugryzło, ale jeszcze chodzi do szkoły. To rączka odpadnie, to dieta stanie się mniej wegańska, … . Aż w końcu zacznie gryźć innych i zarażać. A potem zgnije. Więcej o inspiracji napisałem już odnosząc się do (słusznej) krytyki problemu.
Rozwiązanie
Wskazówka nr 1
W gruncie rzeczy to zadanie jest proste, choć żmudne. Pałujemy punkt po punkcie Pythonem. Żeby nie było TLE, wystarczy odpowiednia ilość słowników. Wg mnie to zadanie jest świetne do nauki Pythona! Komentarze nie stanowią dodatkowej trudności, ale kolejne ułatwienie: można je wrzucać w testowych inputach żeby np. coś zakomentować albo napisać sobie rzeczy potrzebne do debuggu.
Uwagi pozostałe
- Treść zadania była wielokrotnie zmieniana, między innymi dzięki słusznym uwagom poczynionym przez @quenthui. Dziękuję za te uwagi i mam nadzieję, że zadanie posiada walor dydaktyczny oraz jest możliwe do zrozumienia i rozwiązania. A także, że jego rozwiązanie może się komuś spodobać.
- Polecam prostą apkę w konsoli. Jakieś zombie ‘X’ chodzi sobie losowo po planszy, np. 20 x 20. Jak zarazi to zdrowy (’#’) zamienia się w chorego (‘C’), a z czasem zaraża innych (staje się ‘X’). Po jakimś czasie ‘X’ gnije i znika z planszy. Albo zdrowieje i staje się odporny więc też znika, bo drugi raz się nie zarazi. Zostawiam zainteresowanym np. rozwiązania takie jak szczepienia, dzięki którym zniknie z symulacji 50% zdrowych. Albo np. symulowanie drogi do pracy czy zakupów.
- Jeśli pojawi się takie życzenie, mogę do .zipa zapakować wszystkie testy do tego zadania.
Karuzela VAT [FR_18_16] [link]
Poziom trudności wg autora zadania: średnie
Złożoności występujące w zadaniu: przejście grafu w odpowiedni sposób
Inspiracja
O przestępstwach karuzelowych dużo by pisać. Wrzucę zamiast tego link do strony Ministerstwa Finansów, gdzie nawet znajdziecie gotowy schemat. Dokładnie o niego chodziło w treści zadania. Schemat ten nie jest żadną tajemnicą - jego różne wersje można znaleźć w wielu źródłach, w tym medialnych. Dostępne są również materiały audiowizualne, np. na YouTube.
Rozwiązanie
Wskazówka nr 1
Pamiętaj o sortowaniu leksykograficznym.
Wskazówka nr 2
Spośród iluś możliwych rozwiązań, wystarczy nawet DFS. Ważne, żeby analizować każdy towar oddzielnie oraz odpowiedzieć na pytania wynikające z kryteriów przedstawionych w treści zadania.
Wskazówka nr 3
- Czy firma X, którą aktualnie rozważasz, jest polską firmą i sprzedaje towar Y za granicę?
- Czy z dostępnych danych wynika, że towar Y został zakupiony za granicą przez polską firmę inną niż X?
- Czy istnieje ścieżka wskazująca, że towar Y (zakupiony za granicą przez polską firmę inną niż X) może dotrzeć od tej innej firmy do firmy X?
Uwagi pozostałe
- Treść zadania była wielokrotnie zmieniana, między innymi dzięki słusznym uwagom poczynionym przez @macbon. Ponadto, w trakcie testów przeprowadzonych przez @quenthui okazało się, że randomowo generowane testy wprowadzają pewne komplikacje (patrz: jednoznaczność danych opisana w treści zadania). Dziękuję za te uwagi i mam nadzieję, że zadanie posiada walor dydaktyczny oraz jest możliwe do zrozumienia i rozwiązania. A także, że jego rozwiązanie może się komuś spodobać.
Skrzyżowanie II [FR_18_18] [link]
Poziom trudności wg autora zadania: trudne
Złożoności występujące w zadaniu: kinematyka, wyszukiwanie binarne po wyniku
Inspiracja
Patrz: Skrzyżowanie I
Rozwiązanie
Wskazówka nr 1
Rozwiąż prostszą wersję zadania.
Wskazówka nr 2
Wzór istnieje i da się go wyprowadzić, ale może lepiej szukać binarnie po wyniku wykorzystując coś "prostszego" do zaklepania?
Wskazówka nr 3
Wiesz już, jak obliczyć czas, w jakim dowolny samochód pokona pewną drogę, o ile tylko żaden pojazd nie znajduje się przed nim.
Dla pierwszego auta czas wydłuża się o 0 * t = 0, bo stoi bezpośrednio przed światłami i rusza od razu. Drugie auto musi odczekać dodatkowo 1 * t = t, bo poprzedni samochód musi odpowiednio się oddalić. Trzecie auto ma “opóźnienie” 2 (bo tyle aut jest przed nim) * t = 2t, czwarte - 3t itd.
Wskazówka nr 4
bool count_it(const double a, const double V, const double tx, const double dt, const double l, const double d, const int n)
{
const double timeLeft = dt - (n - 1) * tx;
const double tA = max(min(timeLeft, V / a), 0.0);
const double tB = max(timeLeft - tA, 0.0);
return 0.5 * a * pow(tA, 2) + V * tB >= n * (l + d);
}
Uwagi pozostałe
- Porównaj wyniki zadań Skrzyżowanie I oraz Skrzyżowanie II. Odpowiedz na pytanie: czy samochody autonomiczne mogą usprawnić przejazdy przez skrzyżowania?
- Istnieje wiele dróg prowadzących do rozwiązania. Przedstawiona we wskazówkach jest jedynie przykładową z nich. Nie twierdzę, że najlepszą.
