Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
FR_14_16 - K2 |
Na K2 znajduje się n punktów ponumerowanych liczbami od 1 do n. Są to punkty, gdzie wspinacze mogą odpocząć. Pomiędzy tymi punktami poprowadzonych jest n - 1 lin poręczowych o różnej grubości. Korzystając z tych lin wspinacze przemieszczają się pomiędzy punktami. Z dowolnego punktu można się dostać do dowolnego innego punktu na 1 sposób, korzystając z 1 lub większej liczby lin poręczowych. Punkt numer 1 znajduje się na szczycie K2. U podnóża góry znajdują się te spośród punktów od 2 do n, do których doprowadzona jest tylko 1 lina poręczowa.
Pan Janusz twierdzi, że zdobył K2 w ostatniego sylwestra, bo chciał mieć lepszy widok na pokazy sztucznych ogni. Nasz bohater pamięta fragment trasy, który pokonał wchodząc na szczyt, składający się z k lin poręczowych. Konkretnie Pan Janusz pamięta grubość każdej z kolejnych k lin poręczowych.
Odpowiedz na pytanie, ile jest różnych fragmentów tras, prowadzących w kierunku szczytu, które odpowiadają fragmentowi trasy zapamiętanemu przez Pana Janusza? Dwa fragmenty trasy uznajemy za różne, jeżeli różnią się co najmniej 1 z punktów końcowych.
Wejście
W pierwszej linii wejścia znajdują się dwie liczby naturalne n ∈ [2, 105] i k ∈ [1, n - 1] oznaczających odpowiednio liczbę punktów na K2 oraz liczbę lin poręczowych we fragmencie trasy pokonanym przez naszego bohatera.
W kolejnych n - 1 liniach znajdują się opisy lin poręczowych. Opis każdej liny składa się z numerów punktów pomiędzy którymi poprowadzona jest lina poręczowa u, v (1 ≤ u, v ≤ n; u ≠ v) oraz jej grubości g ∈ [1, 109].
W ostatniej linii wejścia znajduje się k liczb naturalnych z przedziału [1, 109]. Są to grubości kolejnych lin poręczowych we fragmencie trasy zapamiętanym przez naszego bohatera.
Wyjście
W pierwszej linii wyjścia należy wypisać liczbę x będącą odpowiedzią na pytanie, ile jest różnych fragmentów tras, prowadzących w kierunku szczytu, które odpowiadają fragmentowi trasy zapamiętanemu przez Pana Janusza.
W każdej z kolejnych x linii należy wypisać parę numerów punktów pomiędzy którymi znajduje się fragment trasy odpowiadający fragmentowi trasy zapamiętanemu przez naszego bohatera. W ramach każdej pary w pierwszej kolejności wypisujemy numer punktu znajdującego się bliżej podnóża góry. Pary numerów punktów powinny być wypisane w kolejności rosnącej. Oznacza to, że para a1 a2 powinna zostać wypisana przed parą b1 b2 jeżeli a1 < b1 albo a1 = b1 i a2 < b2.
Przykład
Wejście:
14 2 14 5 8 3 8 9 5 13 9 1 8 4 14 1 6 9 11 3 2 8 5 5 10 8 10 12 5 6 2 1 10 7 3 11 3 8 4 11 3 3 8
Wyjście:
3 4 3 7 5 9 3
Wyjaśnienie do przykładu:
Fragmenty tras odpowiadające fragmentowi trasy zapamiętanemu przez Pana Janusza to:
- Punkt 4 - Punkt 11 - Punkt 3
- Punkt 7 - Punkt 10 - Punkt 5
- Punkt 9 - Punkt 11 - Punkt 3
Dodane przez: | Maciej Boniecki |
Data dodania: | 2021-12-17 |
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: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14-CLANG COBOL COFFEE D-CLANG D-DMD ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG R RACKET RUST SCM qobi CHICKEN SQLITE SWIFT UNLAMBDA VB.NET |