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.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