Do tego zadania nie będzie wskazówek. Zadanie należy rozwiązywać samodzielnie. Oprócz akceptacji programu w portalu Szkopuł, należy uzyskać akceptację laboranta.
Zadanie KRE (Kreatywna Księgowość), r. akad. 2017/2018
Dostępna pamięć: 128MB.
Bajtazar zaczął pracę w firmie Kreatywna Księgowość sp. z o.o. Jak sama nazwa wskazuje, księgowość w tej firmie jest bardzo dynamiczna. Do pomocy w utrzymywaniu ksiąg potrzebna będzie mu Twoja pomoc.
Pierwszego dnia pracy Bajtazar otrzymał bilans przychodów firmy z podziałem na kolejne miesiące zapisany w tablicy \(A[1 \ldots n]\), gdzie \( A[i] \) oznacza przychody w \( i \)-tym miesiącu.
Bajtazar otrzymuje zlecenia zmiany przychodów postaci \((l, r, \Delta)\) oznaczające konieczność zmiany wszystkich wartości \(A[l],\ldots,A[r]\) o \(\Delta\) (jeśli \(\Delta \ge 0\) — zwiększenie, jeśli \(\Delta<0\) — zmniejszenie).
Jeśli w wyniku takiej operacji wartość któregokolwiek pola tablicy \(A\) znajdzie się poza zakresem \([0, \ldots, 2\,000\,000\,000]\), to operacja kończy się błędem i Bajtazar odpowiada na takie zlecenie wartością \(-1\). W takim wypadku tablica nie jest aktualizowana.
Natomiast jeśli w wyniku takiej operacji wartości tablicy \(A\) pozostaną w wymaganym zakresie, tablica jest aktualizowana oraz Bajtazar w odpowiedzi na zlecenie podaje liczbę miesięcy, w których zanotowano wzrost przychodów, tzn:
$$| \{ i : A[i] > A[i-1]\ \mbox{oraz}\ 1 < i \le n \}|.$$
Napisz program, który:
- wczyta początkową zawartość tablicy \(A\),
- wczyta ciąg \(m\) operacji zmiany przychodów,
- spróbuje sekwencyjnie wykonać każdą operację i wypisze dla każdej z nich jej wynik.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita \(n\) (\(1 \leq n \leq 100\,000\)) oznaczająca liczbę miesięcy. W drugim wierszu znajduje się ciąg \(n\) liczb całkowitych \(a_1, a_2, \ldots, a_n\) (\(0 \le a_i \le 2\,000\,000\,000\)). W trzecim wierszu wejścia znajduje się jedna liczba całkowita \(m\) (\(1 \leq m \leq 200\,000\)) oznaczająca liczbę operacji. W kolejnych \(m\) wierszach zapisany jest ciąg operacji. Każdy z tych wierszy zawiera trzy liczby całkowite \(l_i, r_i, \Delta_i\) (\(1 \le l_i \le r_i \le n\), \(-2\,000\,000\,000 \le \Delta_i \le 2\,000\,000\,000\)).
Wyjście
W każdym z \(m\) wierszy wyjścia należy wypisać jedną liczbę całkowitą — \(i\)-ty wiersz powinien zawierać wynik \(i\)-tej operacji.
Przykład
Dla danych wejściowych:
5
1 2 3 4 5
4
1 5 10
2 2 -100
3 4 2000000000
3 4 -12
poprawnym wynikiem jest:
4
-1
-1
3
Archiwum
Poniżej prezentujemy archiwum zadań zaliczeniowych numer 1 z poprzednich edycji laboratorium z ASD.
Zadanie REL (Relaks), r. akad. 2016/2017
Dostępna pamięć: 128MB.
Tomek lubi chodzić po górach, ale jeszcze bardziej lubi odpoczywać podczas wędrówki – może wtedy obserwować przyrodę i robić zdjęcia telefonem. Tomek woli chodzić po swojemu niż korzystać ze szlaków. Znalazł mapę zbocza góry, na którą chce jutro wejść, i dla każdego miejsca ustalił liczbę punktów, które określają, jak bardzo chciałby odpocząć w danym miejscu. Uzyskał w ten sposób tablicę liczb o \( \displaystyle m \) wierszach i \( \displaystyle n \) kolumnach. Tomek zaczyna wędrówkę od odpoczynku w dowolnym polu w dolnym rzędzie; między każdymi dwoma polami odpoczynku przesuwa się o 1 pole w górę i o co najwyżej 2 pola w lewo lub w prawo. Ostatni odpoczynek odbywa się w dowolnym polu w górnym rzędzie, po czym Tomek wchodzi na szczyt, a następnie zaczyna schodzenie w dół od dowolnego innego pola w górnym rzędzie. Schodzenie jest dla niego dużo mniej męczące, dlatego w jednym ruchu przesuwa się o 2 lub 3 pola w dół i co najwyżej 1 w lewo lub w prawo. Ostatni odpoczynek odbywa się w dowolnym polu w dolnym rzędzie, po czym Tomek kończy wędrówkę. Tomek zawsze tak planuje swoją trasę, by nie odpoczywać dwa razy w tym samym polu, bo to nudne (a poza tym nie ma tam nowych Pokemonów). Jaką trasę powinien wybrać, by zdobyć najwięcej punktów?
Wejście
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite \( \displaystyle m \) oraz \( \displaystyle n \) ( \( \displaystyle 3\le m \le 500 \), \( \displaystyle 2 \le n \le 40 \) ), oznaczające rozmiary tablicy Tomka.
Kolejne \( \displaystyle m \) wierszy zawiera opisy kolejnych rzędów tablicy: \( \displaystyle i \)-ty z nich zawiera \( \displaystyle n \) liczb całkowitych \( \displaystyle s_{i,j} \) ( \( \displaystyle 0 \le s_{i,j} \le 100\,000 \) ) oznaczające liczbę punktów, które zdobędzie Tomek za odpoczynek na polu o współrzędnych \( \displaystyle (i,j) \). Wiersze podawane są od najwyższego (najbliższego szczytu) do najniższego.
Wyjście
W pierwszym i jedynym wierszu powinna znaleźć się dokładnie jedna liczba całkowita – największa liczba punktów, którą może osiągnąć Tomek.
Przykład
Dla danych wejściowych:
6 6
9 1 1 1 6 1
1 1 9 1 1 1
1 1 1 8 1 1
1 9 1 6 1 1
1 1 1 9 1 1
1 1 6 9 1 1
poprawnym wynikiem jest:
71
Wyjaśnienie do przykładu:
W optymalnej trasie Tomek będzie wchodził pod górę, odpoczywając po kolei na wszystkich polach wartych po 8 i 9 punktów, a schodził, odpoczywając po kolei na wszystkich polach wartych po 6 punktów (i żadnych innych). Zwróć uwagę, że Tomek nie mógł dwa razy odpoczywać na polu wartym 8 punktów.
Zadanie WYK (Wykopaliska), r. akad. 2014/2015
Dostępna pamięć: 128MB.
W ramach prac archeologicznych profesorowi Makaremu udało się ustalić położenie niezwykle cennych skarbów. Niestety wszystkie one znajdują się bezpośrednio pod obwodnicą otaczającą stolicę Bajtocji. Przypadek? Zapewne nie. Profesor zastanawia się jednak, w jaki sposób dostać się do skarbów.
Udało mu się przekonać inspektorów Bajtockiego Zarządu Dróg, aby przez jedną noc nie zauważyli prac wykopaliskowych, które będzie przeprowadzał. Musi być jednak spełniony jeden warunek - obwodnica ma pozostać przejezdna.
Profesor musi teraz wybrać miejsca, w których będzie prowadził wykopaliska tak, aby zmaksymalizować wartość wykopanych skarbów i jednocześnie nie zatrzymać ruchu na obwodnicy.
Obwodnica ma kształt pierścienia. Ma ona trzy pasy i jest podzielona na \( \displaystyle n \) równych sektorów. Każda para (pas, sektor) wyznacza obszar na obwodnicy, o kształcie podobnym do banana. Jeśli na obwodnicy prowadzone są jakiekolwiek prace, w szczególności prace wykopaliskowe, to zamykane są całe obszary.
Ruch po obwodnicy jest jednokierunkowy, zgodnie ze wskazówkami zegara. Pojazdy mogą jednak zmieniać obszar ruchu na sąsiedni w tym samym sektorze (zmiana pasa) i mogą to robić dowolnie wiele razy w każdym sektorze. Pojazd nie może jechać po zamkniętym obszarze.
Inspektorzy Bajtockiego Zarządu Dróg traktują przejezdność dość elastycznie - wystarczy im, że możliwe jest zrobienie pełnego "kółka" i powrócenie do punktu wyjścia. W szczególności oznacza to, że niektóre niezamknięte obszary obwodnicy mogą być odcięte od reszty.
Profesor dysponuje ograniczoną liczbą ekip i zastanawia się, do których obszarów obwodnicy je wysłać.
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite \( \displaystyle n \) oraz \( \displaystyle k \) ( \( \displaystyle 1\le k,n \le 5000 \) ), gdzie \( \displaystyle n \) jest liczbą sektorów w obwodnicy, a \( \displaystyle k \) liczbą ekip, które może wysłać profesor. Następne \( \displaystyle n \) wierszy opisuje skarby zgromadzone pod obwodnicą. \( \displaystyle i \)-ty z tych wierszy zawiera trzy liczby \( \displaystyle 0 \le v_{i1},v_{i2},v_{i3} \le 5000 \). Są to wartości skarbów zgromadzonych pod \( \displaystyle i \)-tym sektorem obwodnicy, każda z liczb opisuje jeden z obszarów
(patrz rysunek).
Wyjście
Twój program powinien wypisać jeden wiersz zawierający jedną liczbę całkowitą \( \displaystyle v \) - maksymalną wartość skarbów, jakie może wydobyć profesor, korzystając z nie więcej niż \( \displaystyle k\) ekip.
Przykład
Dla danych wejściowych:
4 4
5 2 1
1 5 2
2 1 5
1 5 2
poprawnym wynikiem jest:
17
Wyjaśnienie do przykładu:
Profesor najchętniej wykopałby cztery skarby, każdy o wartości 5. Niestety wtedy obwodnica przestałaby być przejezdna. Zamiast tego, może on wykopać trzy skarby o wartości 5 i jeden o wartości 2. Rozwiązanie to zostało zaznaczone na rysunku poniżej. Pojazdy mogą wykonywać "kółko" po wewnętrznym pasie.
Natomiast dla danych wejściowych:
4 4
10 10 0
0 0 0
0 10 10
0 0 0
poprawnym wynikiem jest:
40
Zadanie BAJ (Bajtobity), r. akad. 2013/2014
Dostępna pamięć: 64MB.
Przyjazny bajtocki sprzedawca dysponuje pewną liczbą bajtobitów na sprzedaż. Chce je sprzedawać mieszkańcom Bajtocji, biorąc jedną bajtocką monetę za jeden bajtobit. Zgłosiło się do niego kilku mieszkańców, z których każdy dysponuje jakimś budżetem liczonym w bajtockich monetach. Sprzedawca chciałby zadowolić wszystkich kupujących, ale niestety ma mniej bajtobitów niż wynosi suma budżetów. Wie, że kupujący \( \displaystyle A \) będzie niezadowolony wtedy i tylko wtedy, gdy jakiś inny kupujący \( \displaystyle B \) kupi większą liczbę bajtobitów od \( \displaystyle A \) i będzie to liczba, na którą \( \displaystyle A \) stać.
Przykładowo, jeśli pierwszy z kupujących ma budżet 1 i nie kupi ani jednego bajtobitu, a inny kupujący kupi dokładnie jeden bajtobit, to pierwszy kupujący będzie niezadowolony. Natomiast gdyby wszyscy inni kupujący kupili po co najmniej dwa bajtobity, to pierwszy byłby zadowolony. Sprzedawca nie może dzielić bajtobitów, tj. moze sprzedać każdemu klientowi naturalną (z zerem włącznie) liczbę bajtobitów.
Jaką największą liczbę bajtobitów może sprzedać sprzedawca, jeśli chce, żeby nikt nie był niezadowolony?
Wejście
W pierwszym wierszu znajdują się dwie liczby całkowite \( \displaystyle n \) oraz \( \displaystyle m \) ( \( \displaystyle 1 \leq n \leq 1000 \), \( \displaystyle 1 \leq m < 10\,000 \) ), oznaczające liczbę kupujących i liczbę bajtobitów, którymi dysponuje sprzedawca. W drugim wierszu znajdują się budżety klientów ( \( \displaystyle 1 \leq b_i \leq 1000 \) ), podane w porządku niemalejącym. Suma budżetów jest większa niż \( \displaystyle m \), jednak nie przekracza \( \displaystyle 10\,000 \).
Wyjście
W jedynym wierszu wyjścia należy wypisać maksymalną liczbę bajtobitów, które może sprzedać sprzedawca.
Przykład
Dla danych wejściowych:
5 9
2 2 2 3 3
poprawnym wynikiem jest:
9
Zadanie PEN (Pensja), r. akad. 2012/2013
Dostępna pamięć: 32MB.
W związku z kryzysem dyrekcja Bajtockich Zakładów Dezynfekcji Elektrycznych Termoforów zapowiedziała swoim pracownikom cięcia w wynagrodzeniach. Każdy z nich będzie musiał usunąć pewną określoną liczbę cyfr z kwoty swoich miesięcznych dochodów. Pomóż Bajtazarowi napisać program, który pozwoli mu zachować możliwie najwyższą pensję.
Wejście
W pierwszym wierszu znajdują się oddzielone pojedynczymi spacjami dwie liczby całkowite \( \displaystyle n \) i \( \displaystyle k \) ( \( \displaystyle 1 \leq k < n \leq 1\,000\,000 \) ), które oznaczają, odpowiednio, długość zapisu dziesiętnego aktualnej pensji Bajtazara oraz liczbę cyfr do usunięcia.
W drugim wierszu znajduje się liczba \( \displaystyle n \)-cyfrowa (bez wiodących zer) oznaczająca aktualną pensję Bajtazara.
Wyjście
W jedynym wierszu standardowego wyjścia należy wypisać największą liczbę, którą można uzyskać przez usunięcie z aktualnej pensji Bajtazara dokładnie \( \displaystyle k \) cyfr.
Przykład
Dla danych wejściowych:
6 3
768142
poprawnym wynikiem jest:
842
Zadanie TRA (Transport), r. akad. 2011/2012
Dostępna pamięć: 32MB.
Firma przewozowa "Solidnie i nie tak drogo" dowozi do stolicy osoby zamieszkałe w okolicznych wioskach. Każda z osób wsiada do autokaru w swoim miejscu zamieszkania i wysiada w stolicy. Żadne dwie osoby nie wsiadają w tym samym miejscu i wszystkie te miejsca znajdują się na jednej trasie. Opłaty za przejazdy są wnoszone w formie rocznych abonamentów. Firma postanowiła zlecić profesorowi Makaremu wyznaczenie wysokości abonamentów gwarantujących maksymalny zysk. Profesor przeprowadził szereg szczegółowych ankiet, za pomocą których udało mu się oszacować, dla każdej z osób korzystających z usług firmy, maksymalną kwotę, jaką dana osoba jest gotowa zapłacić za abonament - kwotę tę profesor nazwał fachowo "budżetem".
Znając budżety i ceny abonamentów można łatwo przewidzieć zyski firmy. Na osobach, które musiałyby zapłacić za abonament więcej, niż wynosi ich budżet, nie zarabiamy wcale. Na pozostałych osobach zarabiamy dokładnie tyle, ile wynoszą ceny ich abonamentów. Profesor opracował bardzo sprytną metodę pozwalającą wyznaczyć optymalne wysokości abonamentów.
Niestety, algorytm profesora nie bierze pod uwagę ostatnich zmian w przepisach unijnych. Otóż, jeśli trasa A w całości zawiera się w trasie B, to opłata za przejazd trasą A nie może być wyższa niż za przejazd trasą B. Pomóż uratować reputację profesora Makarego i znajdź efektywny algorytm dla tej nieco trudniejszej wersji problemu.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się liczba \( \displaystyle n \) ( \( \displaystyle 1 \le n\le 10\,000 \) ), będąca liczbą przystanków. W drugim wierszu znajduje się \( \displaystyle n \) nieujemnych liczb całkowitych nie większych niż \( \displaystyle 1\,000\,000 \). Liczby te są budżetami kolejnych osób (od osoby mającej do pokonania najwięcej przystanków do osoby, która ze swojego przystanku jedzie bezpośrednio do stolicy).
Wyjście
W pierwszym i jedynym wierszu standardowego wyjścia Twój program powinien wypisać maksymalny zysk, który może osiągnąć firma.
Przykład
Dla danych wejściowych:
4
3 10 5 8
poprawnym wynikiem jest:
20
Zadanie NAW (Nawiasy), r. akad. 2010/2011
Dostępna pamięć: 64MB.
Dana jest dodatnia liczba całkowita \( \displaystyle n \) oraz ciągi rosnące \( \displaystyle { \cal L} \) i \( \displaystyle {\cal R} \) o wartościach ze zbioru \( \displaystyle \{1, 2, \ldots, 2n\} \). Należy określić, ile jest poprawnych wyrażeń nawiasowych długości \( \displaystyle 2n \) takich, że na pozycjach z ciągu \( \displaystyle {\cal L} \) znajdują się nawiasy otwierające, a na pozycjach z ciągu \( \displaystyle {\cal R}\) - zamykające.
Poprawnym wyrażeniem nawiasowym nazywamy napis złożony z nawiasów `[' i `]', zdefiniowany rekurencyjnie:
- [] jest poprawnym wyrażeniem nawiasowym;
- jeśli \( \displaystyle A \) jest poprawnym wyrażeniem nawiasowym, to [\( \displaystyle A \)] również;
- jeśli \( \displaystyle A \) i \( \displaystyle B \) są poprawnymi wyrażeniami nawiasowymi, to \( \displaystyle AB \) (sklejenie \( \displaystyle A \) i \( \displaystyle B \) ) również.
Wejście
W pierwszym wierszu znajdują się trzy liczby całkowite \( \displaystyle n \), \( \displaystyle l \) oraz \( \displaystyle r \) (\( \displaystyle 1 \leq n \leq 2000 \), \( \displaystyle 0\leq l, r \leq n \) ), które oznaczają, odpowiednio, liczbę par nawiasów w wyrażeniu, długość ciągu \( \displaystyle {\cal L}\) zadanych pozycji nawiasów otwierających oraz długość ciągu \( \displaystyle {\cal R}\) zadanych pozycji nawiasów zamykających. Drugi wiersz zawiera \( \displaystyle l \) liczb całkowitych \( \displaystyle L_1, L_2, \ldots, L_l\) ( \( \displaystyle 1\leq L_1 < L_2 < \ldots < L_l\leq 2n \) ), stanowiących kolejne wyrazy ciągu \( \displaystyle {\cal L} \). Trzeci wiersz zawiera \( \displaystyle r \) liczb całkowitych \( \displaystyle R_1, R_2, \ldots, R_r \) ( \( \displaystyle 1\leq R_1 < R_2 < \ldots < R_r\leq 2n \)), stanowiących kolejne wyrazy ciągu \( \displaystyle {\cal R} \). Liczby w każdym wierszu są pooddzielane pojedynczymi odstępami. Jeśli \( \displaystyle l \) lub \( \displaystyle r \) jest równe 0, to, odpowiednio, drugi lub trzeci wiersz jest pusty.
Wyjście
W jedynym wierszu standardowego wyjścia należy wypisać resztę z dzielenia przez \( \displaystyle 10^9+7 \) liczby poprawnych wyrażeń nawiasowych długości \( \displaystyle 2n \) z nawiasami otwierającymi na pozycjach z \( \displaystyle {\cal L} \) i zamykającymi na pozycjach z \( \displaystyle {\cal R} \).
Przykład
Dla danych wejściowych:
4 2 1
1 7
3
poprawnym wynikiem jest:
2
Wyjaśnienie do przykładu: Poprawnymi wyrażeniami nawiasowymi spełniającymi podane warunki są [[][]][] oraz [[]][][].
Zadanie PRO (Procenty), r. akad. 2009/2010
Dostępna pamięć: 256MB.
Mieszkający na wsi przyjaciel profesora Makarego od lat zajmuje się badaniem zawartości cukru w cukrze. Ze względu na to, że badania te są ściśle tajne (Chodzi o potwierdzenie procentu cukru w cukrze w zależności od podziemnego promieniowania na danym terenie.), przyjaciel profesora musi być bardzo ostrożny. W szczególności postanowił on nie kupować w tym samym sklepie więcej niż 1 kg cukru dziennie. Aby zmaksymalizować ilość materiału do badań, przyjaciel profesora chciałby odwiedzić każdego dnia wszystkie sklepy we wsi.
Sklepy są usytuowane przy ulicy Sklepowej i otwierane w tym samym momencie, ale zamykane są o różnej porze. Przyjaciel profesora posiada skuter, na którym porusza się pomiędzy sklepami. Przejechanie jednego kilometra zajmuje mu jedną minutę. Czas zakupu cukru w sklepie jest zaniedbywalny. Przyjaciel profesora może rozpocząć zakupy od dowolnego sklepu i chciałby się dowiedzieć, czy możliwe jest odwiedzenie wszystkich sklepów, a jeśli tak, to jaki minimalny czas musi na to poświęcić. Profesor Makary chciałby pomóc swojemu przyjacielowi, ale po zapoznaniu się z wynikami dotychczasowych badań ma z tym problem. Pomóż.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się liczba \( \displaystyle 1 \le n\le 5\,000 \) oznaczająca liczbę sklepów. W każdym z kolejnych \( \displaystyle n \) wierszy znajdują się dwie liczby całkowite \( \displaystyle 0\le d \le 1\,000\,000 \) oraz \( \displaystyle 0 \le t \le 1\,000\,000\,000 \), będące odpowiednio odległością sklepu w kilometrach od północnego końca ulicy Sklepowej i liczbą minut od otwarcia do zamknięcia sklepu.
Wyjście
Twój program powinien wypisać na standardowe wyjście liczbę minut, które przyjaciel profesora musi poświęcić na zakupy, lub słowo "NIE" (bez cudzysłowów), jeśli nie jest możliwe odwiedzenie wszystkich sklepów jednego dnia.
Przykład
Dla danych wejściowych:
5
1 3
3 1
5 6
8 19
10 15
poprawnym wynikiem jest:
11
Wyjaśnienie do przykładu: Przyjaciel profesora może rozpocząć podróż przy sklepie o parametrach \( \displaystyle (3,1) \), a następnie odwiedzać kolejno sklepy: \( \displaystyle (1,3) \), \( \displaystyle (5,6) \), \( \displaystyle (8,19) \) i \( \displaystyle (10,15) \).
Zadanie WIR (Wirówka liczbowa), r. akad. 2008/2009
Dostępna pamięć: 32MB.
Profesor Makary postanowił zbudować odwracającą wirówkę liczbową. Program wirówki działa w następujący sposób.
- Do wirówki wsypuje się liczby całkowite.
- Jeśli w wirówce pozostała dokładnie jedna liczba, to wirówka kończy pracę.
- Wirówka odwirowuje (czyli wyrzuca) największą z liczb, która w niej się znajduje (jeśli takich liczb jest kilka, to wyrzuca tylko jedną).
- Wszystkie liczby, które pozostały w wirówce, są odwracane wspak (czyli \( \displaystyle 123 \) staje się \( \displaystyle 321 \), a \( \displaystyle 2020 \) staje się \( \displaystyle 202 \) ).
- Wirówka skacze do drugiego kroku programu.
Napisz dla profesora symulator, który będzie przewidywał, jaka liczba pozostanie w wirówce po zakończeniu jej pracy.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita \( \displaystyle n \) ( \( \displaystyle 1\le n \le 1\,000\,000 \) ), oznaczająca ilość liczb wrzuconych do wirówki. W następych \( \displaystyle n \) wierszach znajdują się kolejne liczby całkowite \( \displaystyle a_i \) ( \( \displaystyle 0\le a_i\le 1\,000\,000\,000 \) ), które zostaną wrzucone do wirówki.
Wyjście
W jedynym wierszu standardowego wyjścia należy wypisać liczbę, która pozostanie w wirówce po zakończeniu pracy.
Przykład
Dla danych wejściowych:
3
10
21
13
poprawnym wynikiem jest:
1
