Duyên Hải 2020 - Lớp 11 - Bài 3 - Phần thưởng

View as PDF

Submit solution

Points: 0.80 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Vào ngày ~19~ tháng ~5~, là ngày sinh nhật Bác, thầy Phương sẽ tổ chức một buổi liên hoan và tặng thưởng cho các bạn có nhiều tiến bộ khi tham gia HCC. Có ~n~ bạn được mọi người đánh giá cao, các bạn này sẽ được nhận quà của thầy Phương. Thầy Phương đã chuẩn bị ~m~ món quà, đồng thời thu thập thông tin mong muốn nhận quà của từng bạn. Các bạn được đánh số từ ~1~ đến ~n~, các món quà được đánh số từ ~1~ đến ~m~, với bạn thứ ~i~ ~(i = 1~, ~2~, ..., ~n)~ và món quà ~j~ ~(j = 1~, ~2~, ..., ~m)~ thầy Phương có thông tin ~s_{ij}~ là một số nguyên dương đánh giá nguyện vọng của bạn ~i~ muốn nhận món quà ~j~.

Mỗi một món quà sẽ được tặng cho đúng một bạn, mỗi bạn sẽ được nhận ít nhất một món quà. Gọi ~r_i~ ~(i = 1~, ~2~, ..., ~n)~ là tổng đánh giá nguyện vọng của các món quà mà người ~i~ nhận được và ~w = \min\left\{r_1, r_2, \dots, r_n\right\}~. Thầy Phương muốn tìm cách tặng quà để giá trị ~w~ đạt giá trị càng lớn càng tốt.

Yêu cầu: Cho ~n~, ~m~ và các giá trị ~s_{ij}~, em hãy giúp thầy Phương tìm phương án tặng quà để giá trị ~w~ đạt giá trị càng lớn càng tốt.

Input

Dữ liệu vào từ file BONUS.INP gồm:

  • Dòng đầu chứa hai số nguyên dương ~n~, ~m~ ~(n \leq m)~;
  • Dòng thứ ~i~ ~(i = 1~, ~2~, ..., ~n)~ trong ~n~ dòng tiếp theo chứa ~m~ số nguyên dương ~s_{i1}, s_{i2}, \dots, s_{im}~. Các số có giá trị không vượt quá ~1000~.

Output

Ghi ra file BONUS.OUT ~n~ dòng, dòng thứ ~i~ ~(i = 1~, ~2~, ..., ~n)~ có dạng:

  • Số đầu tiên ghi số ~p_i~ là số món quà mà bạn ~i~ nhận được;
  • Tiếp theo là ~p_i~ số là chỉ số những món quà mà bạn ~i~ được nhận. Các chỉ số được liệt kê theo thứ tự tăng dần.

Giới hạn

Với mỗi test, gọi ~w_P~ là giá trị theo phương án mà thầy Phương tìm được (giá trị này em không được biết, chỉ dùng khi chấm), ~w~ là giá trị theo phương án của em, khi đó em sẽ nhận được ~\min\left\{1, \frac{1000 \times w - 999 \times w_P}{w_P}\right\}~ trên 1 điểm của test đó. Nếu ~1000 \times w < 999 \times w_P~ em sẽ nhận ~0~ điểm.

Subtask

  1. Có ~30\%~ số lượng test ứng với ~30\%~ số điểm thỏa mãn điều kiện: ~m~, ~n \leq 12~;
  2. Có ~40\%~ số lượng test khác ứng với ~40\%~ số điểm thỏa mãn điều kiện: ~m \leq 1200~, ~n = 2~;
  3. Có ~30\%~ số lượng test còn lại ứng với ~30\%~ số điểm thỏa mãn điều kiện: ~m = n \leq 1200~.

Sample Input

2 5
1 2 3 4 5
3 3 4 2 1

Sample Output

2 4 5
3 1 2 3

Note

Theo phương án ở test ví dụ, bạn thứ nhất nhận hai món quà có chỉ số ~4~ và ~5~, bạn thứ hai nhận ba món quà có chỉ số ~1~, ~2~, ~3~. Khi đó ~r_1 = 4 + 5 = 9~, ~r_2 = 3 + 3 + 4 = 9~ và ~w = \min\{9, 10\} = 9~. Nếu ~w_P = 9~ thì em sẽ được ~\min\left\{1, \frac{1000 \times 9 - 999 \times 9}{9}\right\} = 1~ điểm


Comments

Please read the guidelines before commenting.



  • 1
    betapchoi1403   commented on July 6, 2022, 5:29 p.m.

    phần note của bài này bị sai ở chỗ 3+3+4=10 chứ k phải 9 ạ