JOI 2009 Representative Selection - Ngày 1

Cho dãy số \(A_1,A_2,\ldots\), trong đó \(m\) số hạng đầu tiên được cho trước. Với mọi \(i\ge m+1\), các số hạng tiếp theo được xác định bởi

Yêu cầu

Đếm số số hạng lẻ trong đoạn \(A_p,A_{p+1},\ldots,A_q\).

Dữ liệu vào

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

• Dòng thứ nhất chứa số nguyên \(m\).
• Dòng thứ hai chứa số nguyên \(p\).
• Dòng thứ ba chứa số nguyên \(q\).
• Dòng thứ \(i+3\) (\(1\le i\le m\)) chứa số nguyên \(A_i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là số số hạng lẻ trong đoạn được chỉ định, tính cả hai đầu mút.

Ràng buộc

• \(2\le m\le24\).
• \(1\le p<q\le2^{60}\).
• \(0\le A_i<2\times10^9\) với \(1\le i\le m\).
• Lưu ý rằng \(p\) và \(q\) có thể không biểu diễn được bằng số nguyên 32 bit.
• Giới hạn thời gian: \(1\) giây cho mỗi test; giới hạn bộ nhớ: \(64\) MB.

Phân nhóm

Tổng điểm là \(100\), gồm \(25\) nhóm, mỗi nhóm \(4\) điểm. Nhóm thứ nhất gồm hai test 01 và 26; các nhóm còn lại lần lượt gồm một test 02, 03, \(\ldots\), 25. Phải vượt qua mọi test trong một nhóm để nhận điểm của nhóm đó.

Mức điểm theo ràng buộc được công bố là \(30\) điểm cho các test có \(q\le10^6\).

Ví dụ

4
2
8
1
2
3
4

3

3
1
100
0
0
0

0

Nhân dịp kỷ niệm \(101\) năm thành lập, hãng sản xuất con dấu IOI mở dịch vụ làm con dấu chứa những thông điệp dài theo yêu cầu. Hãng đã phát triển loại con dấu cho phép chèn, xóa hoặc thay thế từng ký tự bằng thao tác thủ công.

Thông điệp chỉ gồm hai chữ cái I và O. Trước hết, hãng dùng máy để tạo một con dấu có độ dài ít nhất \(1\). Do đặc tính của máy, chuỗi ký tự tạo ra phải bắt đầu và kết thúc bằng I, đồng thời hai ký tự liên tiếp bất kỳ phải khác nhau. Chẳng hạn, máy có thể tạo I, IOI hoặc IOIOIOI.

Việc tạo con dấu bằng máy không tốn thời gian. Sau đó, có thể thực hiện các thao tác sau, mỗi thao tác tốn \(1\) giây:

• Chèn một ký tự vào một vị trí bất kỳ, kể cả đầu hoặc cuối chuỗi.
• Xóa một ký tự.
• Thay một ký tự bằng ký tự còn lại.

Ví dụ, từ IOIOIOI, thay ký tự thứ \(3\) bằng O, rồi chèn một chữ O vào giữa ký tự thứ \(5\) và thứ \(6\) của chuỗi vừa thu được, sẽ tạo thành IOOOIOOI trong \(2\) giây.

Yêu cầu

Cho thông điệp cần tạo, hãy tìm tổng thời gian chỉnh sửa nhỏ nhất. Trong các cách đạt thời gian nhỏ nhất đó, hãy tìm độ dài nhỏ nhất của con dấu ban đầu được tạo bằng máy.

Dữ liệu vào

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

• Dòng thứ nhất chứa số nguyên \(N\), là độ dài thông điệp.
• Dòng thứ hai chứa chuỗi \(S\) gồm \(N\) ký tự I hoặc O, là thông điệp cần tạo.

Dữ liệu ra

Ghi ra đầu ra chuẩn:

• Dòng thứ nhất chứa thời gian chỉnh sửa nhỏ nhất, tính bằng giây.
• Dòng thứ hai chứa độ dài nhỏ nhất của con dấu ban đầu trong các cách đạt thời gian đó.

Ràng buộc

• \(1\le N\le1\,000\,000\).
• \(S\) chỉ gồm hai ký tự I và O.
• Giới hạn thời gian: \(1\) giây cho mỗi test; giới hạn bộ nhớ: \(64\) MB.

Phân nhóm

Tổng điểm là \(100\), gồm \(25\) nhóm, mỗi nhóm \(4\) điểm và chứa đúng một test, lần lượt từ 01 đến 25.

Các test thỏa mãn \(N\le5000\) chiếm \(40\) điểm.

Ví dụ

8
IOOOIOOI

2
7

5
IOIOI

0
5

5
IIIII

2
5

Ở vương quốc JOI cổ đại, mỗi khi một vị vua qua đời, người ta xây một kim tự tháp trên sa mạc làm lăng mộ. Vị trí tâm và chiều cao của kim tự tháp được quyết định bằng bói toán.

Sa mạc là hình chữ nhật có chiều rộng theo hướng đông–tây là \(W\) và chiều dài theo hướng bắc–nam là \(H\), được chia thành các ô vuông \(1\times1\). Mỗi ô được biểu diễn bằng cặp số nguyên \((x,y)\) với \(0\le x<W\), \(0\le y<H\). Ô \((0,0)\) nằm ở góc tây bắc; ô \((x,y)\) nằm cách ô \((0,0)\) một khoảng \(x\) ô về phía đông và \(y\) ô về phía nam.

Một kim tự tháp có tâm tại ô \((X,Y)\) và chiều cao \(h\) yêu cầu số viên đá tại ô \((x,y)\) trong sa mạc là

Không đặt đá ở bên ngoài sa mạc. Chẳng hạn, với \(W=7\), \(H=6\), khi xây kim tự tháp có tâm \((2,1)\) và chiều cao \(3\), số viên đá ở mỗi ô như sau:

Do diện tích vương quốc có hạn, các kim tự tháp có thể chồng lên nhau. Khi xây một kim tự tháp mới yêu cầu \(n\) viên đá tại một ô:

• Nếu ô đó đã có ít nhất \(n\) viên đá thì không thay đổi gì.
• Nếu ô đó có ít hơn \(n\) viên đá thì bổ sung đá để ô đó có đúng \(n\) viên.

Ví dụ, từ trạng thái trên, nếu xây thêm kim tự tháp có tâm \((4,3)\) và chiều cao \(4\), số viên đá ở mỗi ô trở thành:

Yêu cầu

Cho vị trí tâm và chiều cao của tất cả các kim tự tháp, hãy tính tổng số viên đá cần dùng để xây chúng, với sa mạc ban đầu chưa có đá.

Dữ liệu vào

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

• Dòng thứ nhất chứa ba số nguyên \(W,H,N\), trong đó \(N\) là số kim tự tháp.
• Dòng thứ \(i+1\) (\(1\le i\le N\)) chứa ba số nguyên \(x_i,y_i,h_i\), mô tả kim tự tháp thứ \(i\) có tâm \((x_i,y_i)\) và chiều cao \(h_i\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là tổng số viên đá cần dùng để xây tất cả các kim tự tháp.

Ràng buộc

• \(1\le W,H\le3000\).
• \(1\le N\le10\,000\).
• \(0\le x_i<W\), \(0\le y_i<H\).
• \(1\le h_i\le3000\).
• Giới hạn thời gian: \(5\) giây cho mỗi test; giới hạn bộ nhớ: \(64\) MB.

Phân nhóm

Tổng điểm là \(100\), gồm \(20\) nhóm, mỗi nhóm \(5\) điểm và chứa đúng một test, lần lượt từ 01 đến 20.

• \(10\) điểm dành cho các test thỏa mãn \(W,H\le1000\) và \(N\le5\).
• \(25\) điểm dành cho các test thỏa mãn \(W,H\le500\) và chiều cao của mọi kim tự tháp không vượt quá \(100\).

Ví dụ

7 6 2
2 1 3
4 3 4

81

3000 3000 1
1500 1500 3000

17999999500