Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
MWP6_1C - Nowa waluta |
Mieszkańcy p państw położonych wzdłuż linii wybrzeża naszego kontynentu mają już dość noszenia ogromnej liczby monet w swoich sakiewkach, które pod ich ciężarem często się przerywają. W związku z powyższym władcy niektórych krajów sąsiadujących ze sobą postanowili wprowadzić nową walutę minimalizując jednocześnie liczbę monet będących w obiegu. Jako, że żaden z miłościwie nam panujących nie ma zamiaru przemęczać się wykonywaniem obliczeń, dlatego też to zadanie przypadło Tobie.
Mając daną grupę sąsiadujących ze sobą państw oblicz ile monet powinno otrzymać każde z nich pamiętając o tym, że łączna liczba monet nowej waluty powinna być jak najmniejsza, zaś stosunek liczby nowych monet dowolnej pary państw musi być identyczny jak w przypadku starej waluty.
Wejście
W pierwszej linii wejścia znajdują się dwie liczby całkowite p oraz q (1 ≤ p, q ≤ 1000) oznaczające odpowiednio liczbę państw oraz liczbę zapytań do obliczenia. W drugiej linii wejścia znajduje się p liczb z przedziału od 1 do 106 określających bieżącą liczbę monet w danym państwie. W kolejnych q liniach znajdują się zapytania. Każde z nich składa się z dwóch liczb a oraz b (1 ≤ a < b ≤ p) określających początek i koniec przedziału państw, dla których należy wyliczyć nową liczbę monet.
Wyjście
Dla każdego zapytania należy w osobnej linii wypisać liczbę monet jakie otrzyma każde z państw w danym przedziale, zaczynając od miasta na pozycji a a kończąc na mieście na pozycji b.
Przykład
Wejście
5 2 4 8 6 2 2 1 2 2 5
Wyjście
1 2 4 3 1 1
Dodane przez: | Maciej Boniecki |
Data dodania: | 2014-02-28 |
Limit czasu wykonania programu: | 0.5s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM64 SCM qobi |