Lái xe

Điểm: 0,58 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

by winterwolf94

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Du học Mỹ là ước mơ của nhiều học sinh Việt Nam. Có người nói rằng, muốn đi học ở Mỹ thì phải rất giàu, hoặc là rất giỏi. Trung hội đủ cả ~2~ yếu tố này. Vừa là con nhà đại gia và học ở một trường chuyên danh tiếng, cậu đến Mỹ để hiện thực hóa ước mơ trở thành Batman của mình.

Ở Mỹ phương tiện di chuyển phổ biến nhất là xe hơi. Vốn có niềm đam mê ô tô từ nhỏ, Trung tậu cho mình một chiếc BMW cực xịn để chu du khắp Mỹ. Vào một ngày chủ nhật đẹp trời, Trung bắt đầu chuyến du ngoạn của mình trên xế khủng. Từ Atlanta, Trung lái xe đến New York. Dù không biết đường nhưng nhờ hệ thống định vị toàn cầu Google Map (GM), Trung có thể ung dung chạy trên đường cao tốc. GM báo cho Trung biết đường đến New York gồm ~N~ đoạn đường cao tốc liên tiếp, mỗi đoạn đường gồm ~M~ làn đường. Mỗi đoạn có thể là đường thẳng, quẹo vòng cung ~900~ sang trái hoặc sang phải. Không có ~2~ đoạn đường thẳng liên tiếp (vì nếu vậy đã coi là một đoạn: ~D)~.

Mỗi làn đường rộng ~10m~. Ta xem như xe của Trung là một điểm nhỏ trên hình ví dụ. Trung luôn chạy xe ở chính giữa làn đường. Trên các đoạn đường thẳng, Trung có thể điều khiển cho xe chuyển làn. Để chuyển qua một làn đường (về phía bên trái hoặc bên phải làn đường hiện tại) thì đoạn đường đó ít nhất phải dài là ~100m~. Tương tự để chuyển qua ~2~ làn đường thì độ dài đoạn đường ít nhất phải là ~200m~. Trên các đường quẹo Trung không được chuyển làn xe vì làm vậy sẽ vi phạm luật giao thông và phải nộp phạt.

Là một cựu học sinh chuyên Tin, Trung tìm cách đi sao cho độ dài đường đi ngắn nhất (và dĩ nhiên là tiết kiệm xăng nhất ~J)~. Trung sẽ chọn một làn đường để xuất phát và đến New York trên một làn đường bất kì.

Để xem hình minh họa test ví dụ vào ~1~ trong ~2~ link sau

http://www.freeimagehosting.net/639xb

http://upanh.com/drive_pic_upanh/v/avf0bceq3df.htm

Input

Dòng đầu gồm ~2~ số ~N~, ~M~ -- số đoạn đường và số làn đường trên mỗi đoạn.
Dòng thứ hai gồm ~N~ số nguyên ~L_i~ thể hiện đoạn đường thứ ~i~
- ~L_i~ ~= 0~: đường thẳng
- ~L_i~ ~= 1~: quẹo vòng cung ~900~ sang trái
- ~L_i~ ~= 2~: quẹo vòng cung ~900~ sang phải
Dòng cuối cùng gồm ~N~ số nguyên dương ~S_i~. Nếu đoạn đường thứ ~i~ thẳng: ~S_i~ là chiều dài đoạn đường ~i~ quẹo: ~S_i~ là bán kính trong của khúc quẹo ~i~ (xem trên hình)

Output

In ra một số thực duy nhất là độ dài quãng đường ngắn nhất Trung sẽ đi. Lấy chính xác đến 2 chữ số thập phân.

Giới hạn

~1 \leq N~, ~S_i~ ~\leq 10000~, ~1 \leq M \leq 20~.
Lấy số pi ~=~ ~3.141592654~

Sample Input

3 3
2 0 1
100 1000 100

Sample Output

1330.07

Bình luận

Hãy đọc nội quy trước khi bình luận.

Không có bình luận tại thời điểm này.