Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

CROSS12 - VOI 2012 Qua cầu

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/cross12


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á ri đ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+ri 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ố r1, r2, ..., rn), 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 r1, r2, ..., rn (ri ≤ 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

Được gửi lên bởi:VOJ Team
Ngày:2012-01-21
Thời gian chạy:0.200s-0.400s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VOI 2012

hide comments
2019-12-16 15:56:15




































































duonght_pro_xinhgainhathemattroi_:)

Last edit: 2019-12-16 15:57:08
2018-11-26 08:18:22
Solution + Code: https://bit.ly/IEN3qB
2017-11-02 10:25:44
nhật hào sạch

Last edit: 2017-11-02 14:23:47
2017-08-31 05:38:19

THAM KHẢO THUẬT TOÁN VÀ CODE TẠI:

http://yeulaptrinh.pw/1058/cross12-spoj/






2017-07-24 06:20:35
xem code và lời giải ở https://vietcodes.github.io/code/26

Last edit: 2017-08-06 10:55:33
2017-01-14 13:14:52
Code pascal: http://shink.in/jMQJa
2016-12-24 04:12:02 Nguyễn Vĩnh Thịnh
bị ngộ nhận :(
2016-11-24 16:38:43
gg ez http://www.liink.pw/fiOKA
2016-01-01 13:25:51 Ðặng Phương Tân
25đ mãi chỉ vì quên để ansistring @@
2015-10-04 16:41:26
THAM KHẢO SOLUTION VÀ CODE: http://nhatkynghiencuu.blogspot.com/2015/10/qua-cau-ma-cross12-spoj.html
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.