Home
Training
Competitions
Forum
FAQTask DescriptionDiscussion (0)
Task :: Računi - Državno
Djurica loves going to restaurants. Throughout the year he has went to a lot of them, and now he's really hungry and wondering which one to visit next. In all the restaurants Djurica visited, he ordered exactly k different meals, so one particular receipt he got can be described as id s1 s2 ... sk.
The value id represents a unique identifier for one restaurant. A value of one meal can be 0 if the ith meal has not been ordered that time, and otherwise it is an integer representing the amount of money paid for the ith meal. Djurica has collected n receipts, and he is interested in the combined receipts for each restaurant. A combined receipt for a restaurant identified by id is defined as a receipt with k items where the value of the ith item represents the sum of all values for the ith item on all the receipts from the restaurant id.
When Djurica computes all the combined receipts, he considers the best place to go next the one where the combined bill is lexicographically smallest. Djurica is very hungry so he can't think clearly. He asked you to help him by making a program which will determine the lexicographically smallest combined receipt for a given list of receipts.
You should not consider the id value while determining the lexicographically smallest receipt. For two combined receipts a1 a2 ... ak and b1 b2 ... bk we say that the first receipt is lexicographically smaller than the second if there exists a number j such that ai = bi, i < j, and aj < bj.
INPUT:
From the first line of the standard input read two integers n and k (1 ≤ n ≤ 30.000, 1 ≤ k ≤ 30). In the following n lines, the descriptions for each receipt in the format id s1 s2 ... sk are given.
Variable limits are: 1 ≤ id ≤ 1.000.000.000, 0 ≤ sj ≤ 100.000.
From the first line of the standard input read two integers n and k (1 ≤ n ≤ 30.000, 1 ≤ k ≤ 30). In the following n lines, the descriptions for each receipt in the format id s1 s2 ... sk are given.
Variable limits are: 1 ≤ id ≤ 1.000.000.000, 0 ≤ sj ≤ 100.000.
OUTPUT:
Output k numbers representing the lexicographically smallest combined receipt in the first and only line of the standard output.
Output k numbers representing the lexicographically smallest combined receipt in the first and only line of the standard output.
Input:
Output:
Explanation: The combined receipts for restaurants 1, 2 and 7 are, respectively: 3 12, 5 1 and 3 20.
4 2
1 3 4
2 5 1
1 0 8
7 3 20
1 3 4
2 5 1
1 0 8
7 3 20
Output:
3 12
Explanation: The combined receipts for restaurants 1, 2 and 7 are, respectively: 3 12, 5 1 and 3 20.
Input:
Output:
Explanation: The restaurant with ID 13 has the lexicographically smallest combined receipt.
7 4
11 303 0 0 0
2 10 2 8 0
13 20 3 8 1
11 9 4 0 0
2 9 4 0 1
2 3 0 0 5
13 2 3 0 0
11 303 0 0 0
2 10 2 8 0
13 20 3 8 1
11 9 4 0 0
2 9 4 0 1
2 3 0 0 5
13 2 3 0 0
Output:
22 6 8 1
Explanation: The restaurant with ID 13 has the lexicographically smallest combined receipt.
Submit Solution
Available Languages
Task info
| Name: | Računi - Državno |
| Time: | 1 sec. |
| Memory: | 64 MB |
| #Tests: | 10 |
| AddedBy: |  PetarV |
| Source: | Serbian Nationals 2011 |
Task Ratings
| Difficulty: | 3.9 (8 votes) |
| Quality: | 4.5 (8 votes) |
Acceptance Rate
Recent Submissions
Fastest Solutions
| User | Time |
|---|---|
| ja_bre | 0.63 s. |
| bl4ck.c0d3r | 0.69 s. |
| isego1 | 3.09 s. |
| ks08.tsar | 3.21 s. |
| halil | 3.225 s. |
| Aleksandar_sd | 3.33 s. |
| rasic_m | 3.465 s. |
| doctore | 3.465 s. |
| A.Armin | 3.525 s. |
| nikolakatic | 3.69 s. |
Solved By
