KiDCAT - Kid và lũ mèo.
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: kid2201

Những ngày quá rỗi vì dịch bệnh Corona, Kid chỉ biết vật vờ lên lướt facebook với mong muốn tìm kiếm được chút niềm vui nho nhỏ. Vô tình cô bắt được trào lưu trên mạng rằng : “ Game hot chưa chơi, phim hot chưa xem, nhạc hot chưa nghe, contest hot chưa làm thì sure kèo bạn là người tối cổ rồi!” Cô tự nhủ rằng, hiện tại mình đã là người vô công rỗi nghề, mình không thể trở nên tối cổ được. Sau hàng giờ lần mò, cuối cùng cô đã tìm ra được tựa game hot đang làm điên đảo giới trẻ với hàng triệu lượt tải. Vì là một người có óc quan sát, trong lúc chơi Adorable Home cô đã phát hiện ra rằng, chỉ có 2 loại mèo trong game, đó là loại có lông một màu và loại có lông hai màu. Quá hào hứng, cô áp dụng ngay phát hiện này vào kiến thức Machine learning. Cô tin chắc rằng, việc một con mèo có một màu hay hai màu sẽ phụ thuộc vào cân nặng của chúng.

Để trở nên có ích, cô đã tự đặt cho bản thân một thử thách về đề tài liên quan đến học máy, đó là viết một chương trình dự đoán các con mèo có khối lượng trong khoảng [a,b] sẽ sở hữu bộ lông một màu huyền bí hay hai  màu nổi bật. Kid đã áp dụng lí thuyết “phân loại theo hàng xóm gần nhất” (K – Nearest Neighbors – KNN). Màu lông của một con mèo có khối lượng c sẽ phụ thuộc vào màu lông của con mèo có khối lượng c’ gần c nhất ( tức là abs(c-c’)min). Nếu trường hợp khối lượng của con mèo c nằm chính giữa khối lượng con mèo a và con mèo b ( tức là a - c = c - b), mà trong hai loại mèo này, một con sở hữu bộ lông một màu, một con lại hai màu thì bộ lông của mèo c sẽ được dự đoán là hai màu. Vì quá ham vui, Kid lại đi tụ họp bạn bè mà không ngó ngàng gì đến đề tài mình đang nghiên cứu. Các bạn hãy giúp Kid nhé!

Yêu cầu: Giúp Kid xác định xem trong khoảng [a,b] có bao nhiêu con mèo có 2 màu lông.

Dữ liệu vào:

  • Ba số tự nhiên n, a, b ( 1<= n <= 50000, 1 <= a <= b <= 109), trong đó n là số lượng con mèo có sẵn trong nhà, [a, b] là khoảng khối lượng đang xét.
  • n dòng tiếp theo miêu tả những con mèo có sẵn, mỗi một con mèo được miêu tả bằng một xâu ký tự “S” là hai màu lông, “NS” là một màu lông, và 1 số tự nhiên w chỉ khối lượng.  ( 1 <= w <= 109).

Dữ liệu ra:

  • In ra số lượng con mèo có hai màu trong khoảng [a,b]

Ví dụ

Ví dụ:

 

Input

Output

3 1 10

S 10

NS 4

S 1

6

 

Giải thích: Con mèo có hai màu có khối lượng lần lượt là : 1, 2, 7, 8, 9 và 10.

Vậy tổng cộng có 6 con mèo có hai màu.

Back to Top