BOI 2013 - Ngày 2

Brunhilda sắp tổ chức sinh nhật lần thứ bảy và nghĩ ra một trò chơi. Khi một số \(k\) được hô lên, các em nhỏ chia thành những nhóm có đúng \(k\) người. Chừng nào còn ít nhất \(k\) em chưa có nhóm, một nhóm mới tiếp tục được lập. Cuối cùng, số em dư ra, ít hơn \(k\), bị loại khỏi trò chơi. Những em còn lại tiếp tục chơi với các số được hô tiếp theo. Trò chơi kết thúc khi không còn em nào.

Cha của Brunhilda, Wotan, muốn kết thúc trò chơi càng sớm càng tốt để đi xem bóng đá. Brunhilda đưa cho ông một danh sách gồm \(m\) số nguyên tố khác nhau; mỗi lần ông chỉ được chọn một số trong danh sách, nhưng có thể chọn lại một số nhiều lần.

Với \(Q\) khả năng về số người tham gia ban đầu \(n_1,\ldots,n_Q\), hãy tìm số lần hô ít nhất để kết thúc trò chơi, hoặc xác định rằng không thể kết thúc.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(m\) và \(Q\). Dòng thứ hai chứa \(m\) số nguyên tố phân biệt \(p_1,\ldots,p_m\) theo thứ tự tăng dần. Mỗi dòng trong \(Q\) dòng tiếp theo chứa một số nguyên \(n_j\).

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(j\) chứa số lần hô ít nhất để loại hết \(n_j\) người, hoặc xâu oo gồm hai chữ cái o thường nếu không thể kết thúc trò chơi.

Ràng buộc

• \(1 \le m,Q \le 100\,000\).
• \(2 \le p_i \le 10\,000\,000\); các \(p_i\) là số nguyên tố phân biệt, tăng dần.
• \(1 \le n_j \le 10\,000\,000\).

Phân nhóm

• \(20\) điểm: \(m,Q \le 10\,000\) và mọi \(n_j \le 10\,000\).
• Thêm \(20\) điểm: \(Q=1\).
• \(60\) điểm còn lại: không có ràng buộc bổ sung.

Ví dụ

2 2
2 3
5
6

3
oo

Một bãi cỏ hình chữ nhật trong rừng được phủ tuyết mới vào buổi sáng. Thỏ và cáo lần lượt đi qua bãi cỏ, để lại dấu chân trên tuyết. Mỗi con luôn vào ở ô góc trên bên trái và ra ở ô góc dưới bên phải. Trong lúc ở trên bãi cỏ, chúng có thể đi tới lui, chơi đùa và đi qua lại những ô đã ghé thăm.

Chia bãi cỏ thành các ô vuông. Mỗi bước di chuyển sang một ô chung cạnh, không đi chéo hay nhảy qua ô. Khi một con vật vào một ô, dấu chân của nó che phủ hoàn toàn dấu chân trước đó ở ô này. Tại mọi thời điểm có nhiều nhất một con vật trên bãi cỏ, và không con nào vào bãi cỏ nhiều hơn một lần.

Ví dụ, ba hình dưới đây lần lượt mô tả tuyết ban đầu, dấu chân sau khi một con thỏ đi qua, rồi dấu chân sau khi thêm một con cáo đi qua:

........    RRR.....    FFR.....
........    ..RRR...    .FRRR...
........    ..R.....    .FFFFF..
........    ..RRRR.R    ..RRRFFR
........    .....RRR    .....FFF

Bạn được cho bản đồ dấu chân còn nhìn thấy sau các lượt đi qua. Hãy xác định số con vật ít nhất có thể đã đi qua để tạo ra bản đồ đó.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(H,W\), là chiều cao và chiều rộng của bản đồ. Mỗi dòng trong \(H\) dòng tiếp theo chứa đúng \(W\) ký tự:

• .: tuyết chưa bị giẫm lên.
• R: dấu chân trên cùng là của thỏ.
• F: dấu chân trên cùng là của cáo.

Bản đồ mô tả dấu chân tạo ra theo các quy tắc trên và có ít nhất một ô có dấu chân.

Dữ liệu ra

Một số nguyên \(N\ge1\), là số con vật ít nhất có thể đã tạo ra bản đồ.

Ràng buộc

• \(1 \le H,W \le 4000\).

Phân nhóm

• \(30\) điểm: đáp án \(N\le200\) và \(H,W\le500\).
• \(70\) điểm còn lại: không có ràng buộc bổ sung.

Ví dụ

5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF

2

Victor ngưỡng mộ nhà văn Ernest Vincent Wright, người viết tiểu thuyết Gadsby mà không dùng chữ e. Victor cũng viết một tiểu thuyết, chỉ sử dụng mười chữ cái đầu của bảng chữ cái: abcdefghij. Khi phím e bị hỏng giữa chừng, cậu quyết định xóa toàn bộ chữ e đã viết bằng trình soạn thảo Vim.

Victor chỉ biết ba lệnh:

• x: xóa ký tự tại con trỏ. Chỉ số vị trí con trỏ tính từ trái không đổi, nên con trỏ nằm trên ký tự vốn ngay bên phải ký tự vừa xóa. Không được dùng x khi con trỏ ở ký tự cuối cùng của văn bản. Lệnh tốn một lần nhấn phím.
• h: đưa con trỏ sang trái một ký tự. Nếu đã ở đầu văn bản thì không có gì thay đổi. Lệnh tốn một lần nhấn phím.
• fC: nhấn f rồi một ký tự \(C\), đưa con trỏ tới lần xuất hiện đầu tiên của \(C\) nằm bên phải vị trí hiện tại, kể cả khi ký tự hiện tại cũng là \(C\). Nếu không còn \(C\) bên phải thì con trỏ đứng yên. Lệnh tốn hai lần nhấn phím. Vì phím e bị hỏng, không được dùng fe.

Để minh họa cách hoạt động của lệnh, dùng dấu ngoặc vuông đánh dấu ký tự dưới con trỏ; các dấu ngoặc không thuộc văn bản. Từ trạng thái jeff[i]ehadabigidea, thực hiện riêng từng lệnh cho kết quả:

Trong bài toán cần giải, Victor phải xóa tất cả chữ e và không xóa bất kỳ chữ nào khác; lệnh x ở hàng minh họa chỉ giải thích cơ chế của lệnh. Ban đầu con trỏ ở ký tự đầu tiên. Hãy tìm số lần nhấn phím ít nhất.

Dữ liệu vào

Dòng đầu chứa số nguyên \(N\), là độ dài văn bản. Dòng tiếp theo chứa \(N\) chữ cái thường từ a đến j. Ký tự đầu tiên và ký tự cuối cùng đều khác e.

Dữ liệu ra

Một số nguyên là số lần nhấn phím ít nhất để xóa hết các chữ e và giữ nguyên mọi chữ khác.

Ràng buộc

• \(1 \le N \le 70\,000\).
• Ký tự thuộc abcdefghij; ký tự đầu và cuối khác e.

Phân nhóm

• \(50\) điểm: \(N\le500\).
• Thêm \(10\) điểm: \(N\le5000\).
• \(40\) điểm còn lại: không có ràng buộc bổ sung.

Ví dụ

35
chefeddiefedjeffeachbigagedegghehad

36