시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
10 초 | 128 MB | 41 | 8 | 7 | 26.923% |
Kraje zrzeszone w Unii Państw Północno-Południowo-Wschodnio-Zachodnich debatują nad swoimi wydatkami na wewnątrzunijne transakcje. W Unii znajduje się N państw (numerowanych od 1 do N), które zgłosiło łącznie M wymagań określających minimalną i maksymalną wartość wymiany handlowej między nimi.
Dokładniej, każde zgłoszone żądanie jest opisywane przez cztery liczby: a,b,l,h i oznacza, że krajowi a zależy na zakupie towarów z kraju b za kwotę co najmniej l, ale nie więcej niż h.
Zgodnie z najnowszymi dyrektywami unijnymi saldo każdego kraju członkowskiego w handlu wewnętrznym musi być zerowe, tj. dla każdego kraju łączna wartość jego międzypaństwowej sprzedaży musi być dokładnie równa wartości zakupów.
Sprawdź, czy spełnienie unijnych dyrektyw i żądań wszystkich krajów jest w ogóle możliwe.
W pierwszej linii wejścia znajduje się liczba naturalna Z ( Z = 1 ) opisująca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.
Pierwsza linia zestawu składa się z oddzielonych spacjami liczb naturalnych N oraz M ( 1 <= N <= 150, 0 <= M <= 1500 ), oznaczających kolejno liczbę krajów zrzeszonych w UPPPWZ oraz liczbę wszystkich wymagań państw członkowskich. W kolejnych M wierszach opisane są kolejne wymagania, i-te z nich składa się z czterech liczb całkowitych ai, bi, li, hi, które oznaczają, że kraj ai chciałby wydać na towary z kraju bi nie mniej niż li, ale i nie więcej niż hi ( 1 <= ai, bi <= N, 0 < li <= hi <= 150000 ). Każde dwie pary liczb spośród par (ai,bi) są różne. Żaden kraj nie handluje z samym sobą. Handel odbywa się tylko pomiędzy wymienionymi parami krajów.
Na wyjście należy wypisać M liczb całkowitych, każda w osobnej linii, gdzie i-ta linia oznacza, ile kraj ai powinien przeznaczyć pieniędzy na handel z krajem bi. Jeśli istnieje wiele rozwiązań, można wypisać dowolne z nich. Dane testowe gwarantują istnienie przynajmniej jednego takiego kompromisowego planu transakcji.
1 4 6 1 2 3 6 2 1 4 7 1 3 1 8 3 4 3 10 4 1 1 2 4 2 1 4
5 7 3 3 1 2
Contest > Spot > HotSpot 2011 3-4번