Nắp cống và đồng xu

Đề bài

Mô tả

n nắp cống xếp thành một hàng ngang, đánh số từ 1 đến n từ trái sang phải. Trên mỗi nắp cống có đúng một viên đá, và dưới mỗi nắp cống có đúng một đồng xu. Ban đầu, Nastya đứng cạnh nắp cống thứ k.

Trong mỗi lượt, Nastya có thể thực hiện đúng một trong các hành động sau (mỗi hành động tính là một lượt):

  1. Nếu nắp cống mà Nastya đang đứng cạnh có ít nhất một viên đá, ném đúng một viên đá từ nắp đó sang một nắp cống khác bất kỳ (xa hay gần đều được).
  2. Di chuyển sang nắp cống kề bên (trái hoặc phải).
  3. Nếu nắp cống Nastya đang đứng cạnh không còn viên đá nào, mở nắp và lấy đồng xu bên dưới. Sau khi lấy, nắp được đóng lại ngay (không tốn thêm lượt).

Nastya cần lấy toàn bộ n đồng xu. Hãy tính số lượt tối thiểu cần thực hiện.

Dữ liệu vào

Một dòng chứa hai số nguyên nk — số nắp cống và vị trí ban đầu của Nastya.

Dữ liệu ra

In ra một số nguyên duy nhất — số lượt tối thiểu cần thiết để lấy hết tất cả đồng xu.

Ràng buộc

  • 2n5000
  • 1kn

Ví dụ

Input Output Giải thích
2 2 6 Ném viên đá ở nắp 2 sang nắp 1 (1 lượt), mở nắp 2 lấy xu (1 lượt), đi sang nắp 1 (1 lượt), ném từng viên trong 2 viên ở nắp 1 sang nắp 2 (2 lượt), mở nắp 1 lấy xu (1 lượt). Tổng 6 lượt.
4 2 13 Chiến lược tối ưu là gom hết đá về một đầu rồi mở dần các nắp đã sạch.
5 1 15 Khi k=1 hoặc k=n, đáp án bằng 3n.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0