| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 256 MB | 17 | 0 | 0 | 0.000% |
W tym zadaniu rozważamy ciągi liczb całkowitych o długości n. Odległość między dwoma takimi ciągami A = (a1, a2, ..., an) oraz B = (b1, b2, ..., bn) definiujemy jako:
d(A, B) = |a1 - b1| + |a2 - b2| + ... + |an - bn|,
gdzie |x| oznacza wartość bezwzględną liczby x.
Mając dane k ciągów A1, A2, ..., Ak, Twoim zadaniem jest znaleźć ich centrum, czyli ciąg liczb całkowitych, dla którego wartość max{d(Ai, B) : i = 1, 2, ..., k} jest możliwie najmniejsza.
Pierwszy wiersz wejścia zawiera dwie liczby całkowite n oraz k (2 ≤ n ≤ 100 000, 2 ≤ k ≤ 5). Każdy z kolejnych k wierszy zawiera opis jednego z ciągów w postaci n liczb całkowitych nieprzekraczających co do wartości bezwzględnej 109.
W testach wartych 1 punkt zachodzi warunek k ≤ 2. W testach wartych łącznie 3 punkty zachodzi warunek k ≤ 3. W testach wartych łącznie 6 punktów zachodzi warunek k ≤ 4.
Jedyny wiersz wyjścia powinien zawierać n liczb całkowitych pooddzielanych pojedynczymi odstępami, opisujących centrum podanych na wejściu ciągów. Jeśli jest więcej niż jedna poprawna odpowiedź, Twój program może wypisać dowolną z nich.
5 3 1 -1 2 -1 2 1 2 2 1 2 2 2 -1 1 1
1 2 2 1 2
Contest > Algorithmic Engagements > PA 2014 5-1번