Tylko zadania zgodne ze specyfikacją będą oceniane.

Całość stanowi specyfikację.

Problem

Firma "HiperspaceHurt", posiada sieć hurtowni. Każda z nich jest podzielona na sektory identycznej wielkości. Hurtownie mają różne rozmiary, jak i ilość wymiarów w których się rozciągają. Najprostsze hurtownie składają się z jednego sektora. Taka hurtownia nie ma kolejnych sektorów niezależnie od wymiaru w którym się poruszamy, jest więc określana jako zero-wymiarowa. Kolejny rodzaj hurtowni, to ciąg sektorów ułożonych jeden za drugim. Taka hurtownia rozciąga się w jednym wymiarze, a sektory są ponumerowane od 0. Kolejne to dwuwymiarowe - rozciągają się wzdłuż dwóch wymiarów, a sektory są numerowane przez parę współrzędnych. Potem mamy trójwymiarowe, gdzie sektory są określane przez trzy współrzędne. Potem cztero, pięcio, itd. wymiarowe.

Sektory przechowują przeróżne towary. Każdy sektor ma określoną wartość towarów w nim przechowywanych.

Szef potrzebuje dokonać analiz, ile są w sumie warte określone ciągłe bloki sektorów. Potrzebuje znać odpowiedź na zadane pytania jak najszybciej.

W tym celu sporządził specyfikację problemu, formatu danych wejściowych, oraz odpowiedzi. Dzięki temu formatowi będzie kompatybilny z innymi modułami analitycznymi. Programista, który pierwszy dostarczy rozwiązanie otrzyma dyplom przodownika pracy oraz kupony do wesołego miasteczka dla całej rodziny.

Specyfikacja problemu

Wczytać dany opis hurtowni, o d wymiarach, zawierający wartości danych sektorów. Sektory w hurtowni tworzą d wymiarową macierz t.

Dla każdego zapytania o d wymiarowy blok, podać sumaryczną wartość komórek się w nim zawierających.

Zapytanie składa się z opisu przedziałów, w postaci wiesza zawierającego 2*d liczb: "b_1 e_1 b_2 e_2 … b_d e_d". (b_i e_i - skrót od begin_i end_i, gdzie i to numer wymiaru)

Odpowiedzią jest suma:

sum = 0
for x_1 <- b_1 to e_1
        for x_2 <- b_2 to e_2
                ...
                        for x_d <- b_d to e_d
                                sum = sum + t[x_1][x_2]...[x_d]
return sum;

Specyfikacja wejścia

(Uwaga… symbol "⇐" oznacza "mniejsze równe" - potrafi różnie wyglądać w różnych przeglądarkach).

Pierwsza linia wejścia zawiera liczbę wymiarów d oraz rozpiętość w każdym z nich n.

Kolejne n(d-1) wierszy zawiera po n liczb całkowitych, opisujących wartości sektorów. Wypisane są w kolejności:

for x_d <- b_d to e_d
        ...
                for x_2 <- b_2 to e_2
                        for x_1 <- b_1 to e_1
                                print t[x_1][x_2]...[x_d]
                        print newline

W n(d-1)+2 wierszu znajduje się liczba zapytań z.

W kolejnych z wierszach znajdują się zapytania składające się z 2*d liczb, d par liczb określających przedziały dla kolejnych wymiarów: "b_1 e_1 b_2 e_2 … b_d e_d".

Limity danych:

0 ⇐ d ⇐ 3.

1 ⇐ n ⇐ 1’000’000

1 ⇐ nd ⇐ 10’000’000

0 ⇐ t[x_1]…[x_d] ⇐ 10’000 - a suma wartości wszystkich sektorów nigdy nie przekroczy 100’000.

0 ⇐ z ⇐ 1’000’000

(Na dodatkowe punkty chętnych, zainteresowanych wyjazdem na konkursy programistyczne itd. 0 ⇐ d ⇐ 20).

Porada: Pierwsze zadanie, więc taka mała porada na przyszłość. Limity na dane dają nam pojęcie o tym jaka jest dopuszczalna złożoność algorytmu, jakich typów danych używać by nie stracić precyzji w obliczeniach itd. Naiwne rozwiązanie w postaci zagnieżdżonych pętli to nie jest to! Jeżeli potrafisz zakodować szybszy algorytm tylko dla mniejszej ilości wymiarów (1, 2) to zrób tak, a dla wyższej (3) użyj naiwnego… takie rozwiązanie może dostać kilka punktów. Pełna ilość punktów za optymalne rozwiązanie dla 0 ⇐ d ⇐ 3 , a dodatkowe punkty za więcej wymiarów.

Specyfikacja wyjścia

Wyjście składa się z z linii.

i-ta linia wyjścia zwiera odpowiedź na i-te pytanie, będącą sumą wartości sektorów w danym zakresie.

Limity (implementacja)

Limit pamięci: 200MB. (Dzisiaj hojnie ;) ).

Przykład 1D

Wejście

1 10
1 1 2 2 3 3 4 4 5 5
8
0 0
0 1
0 2
0 3
0 4
4 5
6 7
8 9

Wyjście

1
2
4
6
9
6
8
10

Przykład 2D

Wejście

2 4
1 2 1 0
0 1 1 7
2 0 3 0
0 4 0 5
8
0 0 0 0
1 1 0 0
0 1 0 0
0 1 0 1
1 2 1 2
0 1 2 3
3 3 0 2
2 3 2 3

Wyjście

1
2
3
4
5
6
7
8

Przykład 3D

   4_________5           ^ x_3
  /|        /|          /
 / |       / |         /
0_________1  |        *-----> x_1
|  |      |  |        |
|  6______|__7        |
| /       | /         |
|/        |/          V x_2
2_________3

Wejście

3 2
0 1
2 3
4 5
6 7
6
0 0 0 0 0 0
1 1 1 1 1 1
1 1 0 0 1 1
0 1 0 1 0 0
0 0 0 1 0 1
0 1 1 1 1 1

Wyjście

0
7
5
6
12
13

Kilka uwag i porad na temat implementacji (też specyfikacja, jak całość)

W komentarzu na początku źródeł umieścić: imię, nazwisko, datę, komentarz, opis, tytuł zadania.

Przesyłacie tylko plik tekstowy z kodem źródłowym.

Nie ma szczególnych wymogów co do wybranego języka programowania. Ważne, aby był to język imperatywny. Zwykle pojawiały się rozwiązania w językach C++ , Python, java. Lista języków jest otwarta, jednak prosimy wpierw poprosić (np.drogą mailową) o inny język programowania.

Wczytujemy dane ze standardowego wejścia, wypisujemy na standardowe wyjście (w C++ są to na przykład: cin, cout lub scanf i printf). Jest to szczególnie ważne gdyż programy będą uruchamiane wsadowo na seriach testów. (Testowanie programu powinno wyglądać mniej więcej: "./program <dane_wejsciowe.txt >dane_wyjsciowe.txt". Żadne dodatkowe wyjście poza wyspecyfikowanym nie jest dozwolone. A programy mają zwracać zerowy kod powrotu/błędu.

Programiści java nazywają klasę "Main" jak np: http://www.spoj.pl/forum/viewtopic.php?f=43&t=37 . (Swoją drogą wątek nawiązuje do zadania pod adresem https://www.spoj.pl/problems/TEST/ . Polecam problemy na spoj posortowane malejąco po ACC : https://www.spoj.pl/problems/classical/sort=-7 , jako trening "od najprostszych do najtrudniejszych". Takie zadanka to dobra zabawa :), a system sprawdza od razu jak się nasze rozwiązanie sprawuje i daje informacje zwrotną). Jest wiele pomocy w internecie, m.in. tutoriale koła naukowego Error 501 @ pjwstk : http://error501.wikidot.com/g-moja-pierwsza-kompilacja , http://error501.wikidot.com/c-podstawy-podstaw , http://error501.wikidot.com/c-a-java .

Przed wysłaniem można dla pewności przetestować rozwiązanie na muszelce albo np. na http://ideone.com/, ale pamiętaj (!) o opcji "private", by nie uwidaczniać innym kodu. Tips: Na ideone wybierając język programowania i "sample", możesz znaleźć przykłady programów pracujących na standardowym wejściu/wyjściu dla bardzo wielu języków programowania, a wybierając "syntax highlight" ładnie pokolorować :).