Contest problemset description

Show PDF Back
BitBeat
(A)
Limit pamięci: 256 MB
Limit czasu: 1.00 s

BitBeat to rytmiczna gra komputerowa, w której gracz układa sekwencje dźwięków. Do dyspozycji ma N dźwięków ponumerowanych liczbami od 1 do N. Musi ułożyć z nich utwór rytmiczny, a zarazem nowatorski i różnorodny pod względem użytych tonów.

Każdy dźwięk ma przypisane dwie liczby: dla i-tego dźwięku są to Ai oraz Bi. Oznaczają one odpowiednio jego wysokość i punktację. Powiemy, że ciąg dźwięków d1, …, dk jest rytmiczny, jeśli Adi XOR1 Adi + 1> max(Adi, Adi + 1) dla każdego i < k. Gracz dostaje punkty za różne2 dźwięki występujące w ciągu. Konkretnie, jeśli w ciągu pojawia się dźwięk x, to gracz dodaje do swojego wyniku liczbę Bx. Za kolejne wystąpienia tego samego dźwięku nie otrzymuje dodatkowych punktów.

Jaś, który dostał tę wspaniałą grę za darmo na Epicu, zastanawia się teraz, od jakiego dźwięku powinien rozpocząć swój ciąg rytmiczny. Pomóż mu i napisz program, który dla każdego i od 1 do N wypisze maksymalną liczbę punktów, jaką może uzyskać, rozpoczynając swój ciąg od dźwięku i.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N oznaczająca liczbę dźwięków.

W drugim wierszu wejścia znajduje się N liczb całkowitych Ai, oddzielonych pojedynczymi odstępami, będących wysokościami kolejnych dźwięków.

W trzecim wierszu wejścia znajduje się N liczb całkowitych Bi, oddzielonych pojedynczymi odstępami, będących punktacją za kolejne dźwięki.

Wyjście

Wyjście powinno składać się z N linii.

W i-tej z nich powinna znaleźć się maksymalna liczba punktów możliwa do uzyskania z ciągu rytmicznego rozpoczynającego się od dźwięku i.

Ograniczenia

1 ≤ N ≤ 100 000.
1 ≤ Ai ≤ 230 − 1.
1 ≤ Bi ≤ 109.

Podzadania

Podzadanie Warunki Punkty
1 N ≤ 200 13
2 N ≤ 2000 18
3 A1 = A2 = … = An 4
4 Liczby Ai są potęgami dwójki. 7
5 Ai ≤ 212 − 1 19
6 Bez dodatkowych ograniczeń 39

Przykład

Wejście Wyjście Wyjaśnienie 
3
2 1 1
20 30 10

60
60
60

W tym przykładzie rytmiczne ciągi to dokładnie takie, w których dźwięk 1 może sąsiadować z dźwiękiem 2 (bo 2 XOR 1 = 3 > max(2, 1) = 2), oraz dźwięk 1 może sąsiadować z dźwiękiem 3 (z tego samego powodu). Dźwięk 2 nie może sąsiadować z dźwiękiem 3, bo 1 XOR 1 = 0 < 1. Ciągi maksymalizujące wynik to np: 1213, 213, 312. Ciągi te zawierają wszystkie dźwięki, więc dają maksymalny wynik.
Wejście Wyjście Wyjaśnienie 
4
5 4 4 5
10 20 30 40

10
20
30
40

W tym przykładzie nie istnieją rytmiczne ciągi o długości większej niż jeden.
Wejście Wyjście 
5
1 2 1 7 11
20 10 30 100 100

60
60
60
200
200

  1. Operacja XOR jest opisana tutaj: XOR Wikipedia. W C++ i Pythonie symbol operacji XOR to ^.↩︎

  2. Dźwięki są różne, jeśli są oznaczone różnymi liczbami. Różne dźwięki mogą mieć tę samą wysokość oraz punktację.↩︎

Kanapki
(B)
Limit pamięci: 1024 MB
Limit czasu: 3.00 s

Bajtek codziennie przed szkołą odwiedza pobliski sklep z kanapkami. Kupuje w nim drugie śniadanie, które pozwala mu przetrwać wszystkie lekcje.

W sklepie sprzedawanych jest N rodzajów kanapek, ponumerowanych od 1 do N. Nie wszystkie z nich są dostępne każdego dnia. Przez kolejne Q dni, i‑tego dnia dostępne będą jedynie kanapki o rodzajach od Ai do Bi włącznie. Sklep jest bardzo popularny i chce obsłużyć jak najwięcej klientów, więc Bajtek może kupić każdy rodzaj kanapki co najwyżej raz dziennie.

Bajtek nie przejmuje się ceną kanapek, ale ma ograniczoną pojemność żołądka. Kanapka rodzaju j ma Cj kalorii. Natomiast Bajtek może zjeść co najwyżej Xi kalorii i-tego dnia.

Każda kanapka daje Bajtkowi pewną liczbę punktów satysfakcji. Zjedzenie kanapki j-tego rodzaju zapewnia mu Sj punktów satysfakcji. Satysfakcja Bajtka to po prostu suma punktów za wszystkie kanapki zjedzone przez niego danego dnia.

Dla każdego z Q dni pomóż Bajtkowi znaleźć maksymalną wartość jego satysfakcji, jaką może osiągnąć nie przekraczając limitu kalorii.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N – liczba rodzajów kanapek.

W każdym z kolejnych N wierszy znajdują się dwie liczby całkowite Cj i Sj – kaloryczność i punkty satysfakcji dawane przez j-tą kanapkę.

W następnym wierszu znajduje się jedna liczba całkowita Q – liczba dni.

W każdym z kolejnych Q wierszy znajdują się trzy liczby całkowite Ai, Bi i Xi – zakres dostępnych kanapek i pojemność żołądka Bajtka i-tego dnia.

Wyjście

Na wyjściu powinno znaleźć się Q wierszy.

W i-tym z nich powinna znaleźć się jedna liczba całkowita – maksymalna możliwa satysfakcja Bajtka i-tego dnia.

Ograniczenia

1 ≤ N ≤ 10 000,

1 ≤ Cj ≤ 2 000,

1 ≤ Sj ≤ 109,

1 ≤ Q ≤ 100 000,

1 ≤ Ai ≤ Bi ≤ N,

1 ≤ Xi ≤ 2 000.

Podzadania

Podzadanie Warunki Punkty
1 N ≤ 500, Q ≤ 1 000, Xi ≤ 500 14
2 N ≤ 500, Q ≤ 20 000, Xi ≤ 500 12
3 N ≤ 5 000, Q ≤ 20 000, Xi ≤ 80 29
4 N ≤ 2 000, Q ≤ 4 000 14
5 brak dodatkowych ograniczeń 31

Przykład

Wejście Wyjście Wyjaśnienie 
6
2 2
1 3
4 4
3 5
2 3
3 2
3
1 6 7
2 4 4
5 6 3
 
11
8
3

Pierwszego dnia Bajtek powinien zjeść kanapki rodzajów 2, 4 i 5. Drugiego dnia kanapki rodzaju 2 i 4. Trzeciego dnia kanapkę rodzaju 5.
Wejście Wyjście Wyjaśnienie 
5
1 2
2 3
3 4
4 5
5 6
1
1 5 15
 
20

Bajtek może zjeść wszystkie kanapki.
Wejście Wyjście Wyjaśnienie 
5
2 2
3 3
4 4
5 5
6 6
1
1 5 1
 
0

Bajtek nie może zjeść żadnej kanapki.
Palindromiczna gra
(C)
Limit pamięci: 256 MB
Limit czasu: 5.00 s

Bajtek i Bajtosia grają w grę ze stosem kamieni, który początkowo zawiera S kamieni. Gracze wykonują ruchy na zmianę, a zaczyna Bajtek.

W każdej turze gracz wybiera dodatnią liczbę całkowitą x, która jest palindromem1 i usuwa dokładnie x kamieni ze stosu.

Jeśli na początku tury czyjejś osoby stos jest pusty, ta osoba przegrywa. Bajtek zastanawia się, czy przy optymalnej grze obu graczy uda mu się wygrać. Pomóż mu odpowiedzieć na to pytanie.

Wejście

Pierwsza linia wejścia zawiera liczbę całkowitą S - liczbę kamieni.

Wyjście

Należy wypisać TAK, jeżeli przy optymalnej grze obu graczy wygra Bajtek. W przeciwnym przypadku należy wypisać NIE.

Ograniczenia

1 ≤ S < 10105

Podzadania

Podzadanie Warunki Punkty
1 S < 100 8
2 S < 106 12
3 S < 109 24
5 Brak dodatkowych ograniczeń. 56

Przykład

Wejście Wyjście Wyjaśnienie 
8

TAK

Bajtek może zabrać 8 kamieni, wygrywając grę.
Wejście Wyjście 
10

NIE
Wejście Wyjście 
12

TAK

  1. Dodatnia liczba całkowita jest palindromem, jeśli czyta się tak samo od lewej do prawej i od prawej do lewej. 1, 121, 9009 są palindromami, ale 1212, 112, 990 już nie.↩︎