CROSS12 - VOI 2012 Qua cầu
Giới hạn- Thời gian: 0.4s
- 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.
Một nhóm n bạn đi tập văn nghệ về khuya. Cả nhóm chỉ có 1 chiếc đèn pin và phải qua 1 cây cầu gồm m đoạn, các đoạn được đánh số từ 1 đến m kể từ vị trí bờ đang đứng sang bờ kia. Coi vị trí n bạn đang đứng là đoạn thứ 0 và đầu cầu bên kia là vị trí m+1. Cây cầu đã cũ, do đó có một số đoạn của cầu đã hỏng và không thể đi vào được, hơn nữa cầu chỉ chịu được sức nặng của không quá hai người. Để qua cầu an toàn, các bạn phải tổ chức qua cầu theo cách thức sau: mỗi lượt chỉ có 2 người cầm đèn pin để cùng nhau qua cầu và không được đi vào những vị trí đoạn cầu bị hỏng. Sau khi hai người qua đến đầu cầu bên kia thì những người đã qua cầu phải cử 1 người đem đèn pin trở lại đầu cầu bên này để các bạn khác tiếp tục qua cầu ... Mỗi đơn vị thời gian, bạn thứ i có thể bước không quá r i đoạn, nghĩa là nếu bạn thứ i đang ở đoạn thứ s của cây cầu thì bạn có thể di chuyển vào một trong các đoạn thứ s+1, s+2, ..., s+r i nếu đoạn đó không bị hỏng. Việc thực hiện một bước đi đòi hỏi 1 đơn vị thời gian. Do đó có thể có người qua cầu nhanh hơn, có người qua cầu chậm hơn. Nếu 2 bạn đi cùng nhau qua cầu thì họ phải di chuyển qua cầu với thời gian của bạn chậm hơn. Vì đã quá khuya nên cả nhóm bàn nhau tìm cách qua cầu sớm nhất có thể được.
Yêu cầu : Cho biết vị trí các đoạn cầu bị hỏng và khả năng di chuyển của từng bạn (được mô tả bằng các số r 1 , r 2 , ..., r n ), hãy tính khoảng thời gian ngắn nhất để n bạn qua được cầu. Giải thiết rằng luôn có cách để cả nhóm vượt qua cầu.
Ràng buộc : 50% số tests ứng với 50% số điểm của bài có n ≤ 10.
Input
- Dòng thứ nhất chứa hai số nguyên dương n và m tương ứng là số bạn trong nhóm và số đoạn của cây cầu (n ≤ 10000; m ≤ 100000).
- Dòng thứ hai chứ n số nguyên dương r 1 , r 2 , ..., r n (r i ≤ 100, i = 1, 2, ..., n).
- Dòng thứ ba chứa một xâu gồm m ký tự '0' hoặc '1' mô tả trạng thái của cây cầu. Ký tự thứ i của xâu là '0' nếu đoạn cầu thứ i không bị hỏng có thể đi vào được, là '1' nếu đoạn cầu thứ i bị hỏng không thể đi vào được.
Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.
Output
Ghi ra một số nguyên là khoảng thời gian ngắn nhất để n bạn vượt qua được cây cầu.
Example
Input: 3 5 2 2 4 00100 Output: 8
- Người up: voj
- Nguồn bài: VOI 2012