trang chủ / bài tập / findcrim

Cảnh sát và tội phạm

Đề bài

Mô tả

n thành phố xếp thành một hàng, đánh số từ 1 đến n. Khoảng cách giữa thành phố i và thành phố j bằng |ij|.

Một cảnh sát sống ở thành phố a. Mỗi thành phố có nhiều nhất một tên tội phạm. Cảnh sát dùng một thiết bị dò: với mỗi khoảng cách d, thiết bị cho biết có bao nhiêu tên tội phạm nằm ở các thành phố cách a đúng d đơn vị (tức tổng số tội phạm ở hai thành phố ada+d, chỉ tính những thành phố tồn tại).

Sau khi đọc thông tin từ thiết bị, cảnh sát chỉ bắt được tội phạm ở những thành phố mà anh ta chắc chắn có tội phạm. Cụ thể, với khoảng cách d:

  • Nếu chỉ có một trong hai thành phố ad, a+d tồn tại thì số tội phạm mà thiết bị báo chính là số tội phạm ở thành phố đó, nên cảnh sát biết chắc.
  • Nếu cả hai thành phố tồn tại và thiết bị báo 2, thì cả hai đều có tội phạm, cảnh sát bắt được cả hai.
  • Nếu cả hai thành phố tồn tại và thiết bị báo 1, cảnh sát không biết tội phạm nằm ở thành phố nào nên không bắt được ai ở khoảng cách đó.

Biết trước vị trí thực tế của các tên tội phạm, hãy đếm số tội phạm mà cảnh sát bắt được.

Dữ liệu vào

  • Dòng đầu chứa hai số nguyên na (1an100): số thành phố và chỉ số thành phố nơi cảnh sát sống.
  • Dòng thứ hai chứa n số nguyên t1,t2,,tn (0ti1): ti là số tội phạm ở thành phố thứ i.

Dữ liệu ra

In ra một số nguyên: số tội phạm mà cảnh sát bắt được.

Ví dụ

Input Output Giải thích
6 3
1 1 1 0 1 0
3 Cảnh sát ở thành phố 3. Khoảng cách 0: một tội phạm ở thành phố 3, bắt được. Khoảng cách 1: một tội phạm (thành phố 2 hoặc 4), không rõ nên bỏ qua. Khoảng cách 2: hai tội phạm ở thành phố 15, bắt cả hai. Tổng cộng bắt được 3.
5 2
0 0 0 1 0
1 Thiết bị báo có một tội phạm ở khoảng cách 2. Chỉ có thành phố 4 ở khoảng cách 2 (thành phố 0 không tồn tại), nên cảnh sát biết chắc và bắt được.

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.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.400 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.2 gforth 0.7.3 gfortran 12.2.0 go 1.27.0 groovyc 5.1.1 javac 25.0.4 node 26.8.1 julia 1.12.7 kotlinc 2.4.10 lean 4.33.1 sbcl 2.2.9 lua 5.4.9 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.10 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.14.7 racket 8.7 ruby 4.0.6 rustc 1.98.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.3.3 tclsh 8.6 bun 1.4.0 deno 2.9.6 v 0.5.2 zig 0.16.0