JOI 2007 Representative Selection - Ngày 1

Khoa Công nghệ thông tin của Đại học JOI vừa tổ chức kỳ thi tuyển sinh cho \(n\) học sinh. Bài thi được chấm trên thang điểm \(100\). Để quyết định điểm chuẩn, trường cần xếp hạng các học sinh theo kết quả thi.

Cho điểm của từng học sinh, hãy tìm thứ hạng của mỗi người. Những học sinh bằng điểm có cùng thứ hạng; thứ hạng của một học sinh bằng \(1\) cộng với số học sinh có điểm cao hơn người đó.

Giới hạn thời gian là \(5\) giây cho mỗi bộ dữ liệu; giới hạn bộ nhớ là \(64\) MB.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(n\), số học sinh.
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(s_i\), điểm của học sinh có số báo danh \(i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn \(n\) dòng. Dòng thứ \(i\) chứa thứ hạng của học sinh có số báo danh \(i\).

Ràng buộc

• \(1 \le n \le 100\,000\).
• \(0 \le s_i \le 100\) với mọi \(1 \le i \le n\).

Phân nhóm

Có \(5\) bộ dữ liệu được chấm độc lập, tổng cộng \(100\) điểm. Không có điều kiện phân nhóm bổ sung được công bố.

1. Bộ dữ liệu 1: \(20\) điểm.
2. Bộ dữ liệu 2: \(20\) điểm.
3. Bộ dữ liệu 3: \(20\) điểm.
4. Bộ dữ liệu 4: \(20\) điểm.
5. Bộ dữ liệu 5: \(20\) điểm.

Ví dụ

6
100
90
80
90
100
65

1
3
5
3
1
6

Cho số nguyên \(n\). Hãy tìm số nguyên dương nhỏ nhất \(m\) sao cho \(m!\) chia hết cho \(n\). Giai thừa \(m!\) là tích của tất cả các số nguyên từ \(1\) đến \(m\).

Giới hạn thời gian là \(0{,}5\) giây cho mỗi bộ dữ liệu; giới hạn bộ nhớ là \(64\) MB.

Dữ liệu vào

Đọc từ đầu vào chuẩn một dòng chứa số nguyên \(n\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chỉ chứa số nguyên \(m\) nhỏ nhất thỏa mãn yêu cầu.

Ràng buộc

• \(2 \le n \le 100\,000\,000\).

Phân nhóm

Có \(5\) bộ dữ liệu được chấm độc lập, tổng cộng \(100\) điểm. Không có điều kiện phân nhóm bổ sung được công bố.

1. Bộ dữ liệu 1: \(20\) điểm.
2. Bộ dữ liệu 2: \(20\) điểm.
3. Bộ dữ liệu 3: \(20\) điểm.
4. Bộ dữ liệu 4: \(20\) điểm.
5. Bộ dữ liệu 5: \(20\) điểm.

Ví dụ

10

5

12

4

Để chào đón kỳ thi Olympic Tin học Quốc tế năm 2007, thành phố Zagreb dự định xây dựng một trung tâm thương mại lớn ở ngoại ô. Khu đất dự kiến được chia thành một lưới gồm \(m\) cột theo chiều ngang và \(n\) hàng theo chiều dọc. Chẳng hạn, với \(m=10\) và \(n=7\), khu đất có \(10\) cột và \(7\) hàng ô vuông.

Thành phố phải chọn một vùng hình chữ nhật rộng \(a\) ô, cao \(b\) ô để xây trung tâm thương mại. Một số ô đã có người sinh sống nên không thể sử dụng. Nếu một vùng hình chữ nhật có kích thước yêu cầu không chứa ô nào có người ở, thành phố có thể mua tất cả các ô trong vùng đó để xây dựng.

Do ngân sách có hạn, thành phố muốn tổng chi phí mua đất nhỏ nhất. Cho kích thước khu đất, kích thước trung tâm thương mại và thông tin của từng ô, hãy tính chi phí nhỏ nhất cần bỏ ra.

Ký hiệu \((i,j)\) là ô ở cột thứ \(i\) từ trái sang và hàng thứ \(j\) từ trên xuống. Chiều ngang của vùng được chọn phải là \(a\), chiều dọc phải là \(b\).

Giới hạn thời gian là \(6\) giây cho mỗi bộ dữ liệu; giới hạn bộ nhớ là \(64\) MB.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(m,n\).
• Dòng thứ hai chứa hai số nguyên \(a,b\).
• Trong \(n\) dòng tiếp theo, dòng thứ \(j\) chứa \(m\) số nguyên \(c_{1,j},c_{2,j},\ldots,c_{m,j}\). Nếu \(c_{i,j}=-1\), ô \((i,j)\) đã có người ở. Nếu không, \(c_{i,j}\) là chi phí mua ô đó.

Các số trên cùng một dòng được ngăn cách bởi dấu cách. Dữ liệu bảo đảm luôn có thể xây trung tâm thương mại.

Kích thước dữ liệu vào có thể lớn. Cần chú ý tốc độ đọc dữ liệu; trong C++, có thể dùng fscanf khi cần thiết.

Dữ liệu ra

Ghi ra đầu ra chuẩn chi phí mua đất nhỏ nhất để xây trung tâm thương mại.

Ràng buộc

• \(1 \le m,n \le 1000\).
• \(1 \le a,b \le 1000\).
• \(-1 \le c_{i,j} \le 100\) với mọi \(1 \le i \le m\), \(1 \le j \le n\).
• Tồn tại ít nhất một vùng hợp lệ rộng \(a\) ô và cao \(b\) ô.

Phân nhóm

Có \(5\) bộ dữ liệu được chấm độc lập, tổng cộng \(100\) điểm. Không có điều kiện phân nhóm bổ sung được công bố.

1. Bộ dữ liệu 1: \(20\) điểm.
2. Bộ dữ liệu 2: \(20\) điểm.
3. Bộ dữ liệu 3: \(20\) điểm.
4. Bộ dữ liệu 4: \(20\) điểm.
5. Bộ dữ liệu 5: \(20\) điểm.

Ví dụ

7 6
3 2
26 29 84 15 -1 1 71
45 14 38 91 62 77 35
68 -1 -1 90 63 56 70
31 2 4 74 72 41 90
100 26 21 -1 44 72 60
71 4 40 93 48 -1 50

184