LGAME - Trò chơi của Lala
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Lala năm nay mới vào lớp một. Sáng nay, Lala được học về phép tính cộng. Khi về nhà, Lala đã hứng thú đến nỗi đòi anh trai - Alex cho mình thêm các bài tập về phép cộng.
Alex của rất vui khi thấy được niềm đam mê toán học của em gái mình. Alex viết ra N con số vào một tờ giấy. Và đánh dấu các con số theo thứ tự 1 --> N (kí hiệu a[i] là số thứ i). Bây giờ Lala được cho thêm số S và phải viết ra tất cả các bộ số {p[1], p[2], p[3], ..., p[x]} , sao cho p[1]<p[2]<...<p[x] và a[p[1]] + a[p[2]] + ... + a[p[x]] = S . Sau khi nghe xong câu hỏi, Lala liền hỏi ngược lại Alex: "Nếu vậy thì với mỗi số 1, 2, 3, ..., (N-2), (N-1), N, Lala phải viết ít nhất bao nhiêu lần để làm xong bài tập trên vậy anh ?!!".
Lala thì đã cặm cụi viết ra các bộ số từ lâu. Còn Alex thì đang nhức óc với câu hỏi trên. Các bạn hãy giúp Alex giải nhanh câu đố trên trước khi Lala làm xong bài tập nhé. Nếu không thì Alex sẽ mất mặt với em gái mất !!!.
Giới hạn
- N <= 1.000, S <= 10.000, 1<= a[i] <= 1.000
- 60% số test có N <= 100.
Input
- Dòng đầu tiên là 2 số N và S.
- Dòng thứ hai gồm N số trong dãy.
Output
- Gồm N số trên 1 dòng, số thứ i cho biết số lần viết ít nhất số thứ tự i, để hoàn thành bài tập. Vì các số có thể rất lớn nên bạn chỉ cần in ra phần dư của chúng khi chia cho 10^9 + 7.
Example
Input 1: 4 3
1 1 1 2
Output 1: 2 2 2 3
Giải thích:
Các bộ số Lala phải viết: {1,2,3}, {1,4}, {2,4}, {3,4}.
Nên các số 1, 2, 3, 4 được viết lần lượt 2, 2, 2, 3 lần.
Input 2:
10 5
1 1 1 1 1 1 1 1 1 1
Output 2:
126 126 126 126 126 126 126 126 126 126
- Người up: yellowflash12