SDRIVE - Lái xe
Giới hạn- Thời gian: 1.0s
- 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.
Du học Mỹ là ước mơ của nhiều học sinh Việt Nam. Có người nói rằng, muốn đi học ở Mỹ thì phải rất giàu, hoặc là rất giỏi. Trung hội đủ cả 2 yếu tố này. Vừa là con nhà đại gia và học ở một trường chuyên danh tiếng, cậu đến Mỹ để hiện thực hóa ước mơ trở thành Batman của mình.
Ở Mỹ phương tiện di chuyển phổ biến nhất là xe hơi. Vốn có niềm đam mê ô tô từ nhỏ, Trung tậu cho mình một chiếc BMW cực xịn để chu du khắp Mỹ. Vào một ngày chủ nhật đẹp trời, Trung bắt đầu chuyến du ngoạn của mình trên xế khủng. Từ Atlanta, Trung lái xe đến New York. Dù không biết đường nhưng nhờ hệ thống định vị toàn cầu Google Map (GM), Trung có thể ung dung chạy trên đường cao tốc. GM báo cho Trung biết đường đến New York gồm N đoạn đường cao tốc liên tiếp, mỗi đoạn đường gồm M làn đường. Mỗi đoạn có thể là đường thẳng, quẹo vòng cung 90 0 sang trái hoặc sang phải. Không có 2 đoạn đường thẳng liên tiếp (vì nếu vậy đã coi là một đoạn :D).
Mỗi làn đường rộng 10m. Ta xem như xe của Trung là một điểm nhỏ trên hình ví dụ. Trung luôn chạy xe ở chính giữa làn đường. Trên các đoạn đường thẳng, Trung có thể điều khiển cho xe chuyển làn. Để chuyển qua một làn đường (về phía bên trái hoặc bên phải làn đường hiện tại) thì đoạn đường đó ít nhất phải dài là 100m. Tương tự để chuyển qua 2 làn đường thì độ dài đoạn đường ít nhất phải là 200m. Trên các đường quẹo Trung không được chuyển làn xe vì làm vậy sẽ vi phạm luật giao thông và phải nộp phạt.
Là một cựu học sinh chuyên Tin, Trung tìm cách đi sao cho độ dài đường đi ngắn nhất (và dĩ nhiên là tiết kiệm xăng nhất J). Trung sẽ chọn một làn đường để xuất phát và đến New York trên một làn đường bất kì.
Input
Dòng đầu gồm 2 số N, M – số đoạn đường và số làn đường trên mỗi đoạn.
Dòng thứ hai gồm N số nguyên L i thể hiện đoạn đường thứ i
- L i = 0 : đường thẳng
- L i = 1 : quẹo vòng cung 90 0 sang trái
- L i = 2 : quẹo vòng cung 90 0 sang phải
Dòng cuối cùng gồm N số nguyên dương S i . Nếu đoạn đường thứ i
- thẳng : S i là chiều dài đoạn đường i
- quẹo : S i là bán kính trong của khúc quẹo i (xem trên hình)
Giới hạn : 1 <= N, S i <= 10000, 1 <= M <= 20.
Lấy số pi = 3.141592654
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.
Example
Input: 3 3 2 0 1 100 1000 100 Output: 1330.07
- Người up: yellowflash12
- Nguồn bài: by winterwolf94