W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Organizatorzy CEOI 2011 zamierzają urządzić przyjęcie z mnóstwem balonów. Będzie ich , wszystkie w kształcie kuli, ułożone w jednym rzędzie na podłodze. Balony trzeba będzie napompować, na razie każdy z nich ma promień zero. Balon o numerze jest przymocowany do podłogi w punkcie o współrzędnej . Balony będą pompowane kolejno, od lewej do prawej. W czasie pompowania promień -tego balonu zwiększa się w sposób ciągły, aż do momentu kiedy osiągnie określoną dla niego górną granicę , lub balon dotknie któregoś z poprzednio napompowanych.
Balony z testu przykładowego, po pełnym napompowaniu.
Organizatorzy chcieliby wiedzieć, ile powietrza będzie potrzebne do napełnienia balonów. Twoim zadaniem jest wyznaczenie promienia, który osiągnie każdy z nich.
Pierwszy wiersz standardowego wejścia zawiera liczbę całkowitą () - liczbę balonów. Kolejne wierszy opisuje balony: -ty z nich zawiera liczby całkowite oraz (, ). Możesz założyć, że balony są podane w kolejności rosnącej współrzędnej .
W testach wartych przynajmniej 40 punktów zachodzi dodatkowa nierówność .
Twój program powinien wypisać wierszy, przy czym -ty z nich powinien zawierać dokładnie jedną liczbę - promień -tego balonu po napełnieniu. Odpowiedź będzie zaakceptowana, jeśli każda liczba będzie różniła się od prawidłowej o co najwyżej .
Dla danych wejściowych:
3 0 9 8 1 13 7
poprawną odpowiedzią jest:
9.000 1.000 4.694
Wskazówka: Aby wypisać wartość a typu long double z dokładnością do trzech miejsc po przecinku w C/C++, możesz użyć instrukcji printf("\%.3Lf\textbackslash n", a);. Aby wypisać to samo z użyciem strumieni w C++, użyj cout << fixed << setprecision(3); przed wypisaniem wartości za pomocą cout << a << "\textbackslash n"; (nie zapomnij dołączyć pliku nagłówkowego iomanip). W Pascalu możesz użyć instrukcji writeln(a:0:3);.
Zalecamy używanie typów long double w C/C++ oraz extended w Pascalu, ze względu na ich większą dokładność (w szczególności, przy ich użyciu żaden z rozważanych przez organizatorów poprawnych algorytmów nie miał problemów z błędami zaokrągleń).
Autor zadania: Jakub Pachocki.