[COCI1819 - Contest 05] Bài 2: Jarvis

Xem PDF

Nộp bài

Điểm: 100 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 256M
Input: bàn phím
Output: màn hình

Tác giả:
Dạng bài

Ivan đã gửi ~N~ chiến binh drone đến trận chiến cuối cùng chống lại Tony Stark, còn được biết đến là Iron Man. Mỗi chiếc drone có một tần số xác định, được biểu diễn dưới dạng một số nguyên, trên đó nó nhận lệnh từ Ivan trong khi chiến đấu. Jarvis, trí tuệ nhân tạo được phát triển bởi Toni, phải xác định những tần số đó và từ đó kiểm soát càng nhiều drone càng tốt.

Jarvis biết các giá trị tần số gốc của từng drone tại nhà máy, nhưng các tần số cần thiết cho mỗi drone, không may thay đổi trong quá trình đó.

Jarvis chỉ có một cơ hội. Anh ta có thể chọn một số nguyên X và tăng mỗi tần số của nhà máy lên ~X~ (~X~ có thể âm cũng được). Sau đó, Jarvis sẽ tiếp quản điều khiển mỗi chiếc drone mà tần số nhà máy sửa đổi và tần số yêu cầu bởi drone cụ thể là bằng nhau.

Viết một chương trình sẽ xác định được Jarvis có thể kiểm soát bao nhiêu chiến binh drone.

Input

  • Dòng đầu tiên chứa số nguyên ~N~ ~(1 \leq N \leq 100 000)~, số lượng drone từ câu hỏi.
  • Trong dòng thứ hai có ~N~ số nguyên ~A_i~ ~(-1 000 000 \leq Ai \leq 1 000 000)~ biểu thị các giá trị tần số nhà máy của chiến binh drone.
  • Trong dòng thứ ba có ~N~ số nguyên ~B_i~ ~(-1 000 000 \leq Bi \leq 1 000 000)~ biểu thị các giá trị tần số yêu cầu của các chiến binh drone.

Output

Trong một dòng duy nhất, in ra số lượng lớn nhất của chiến binh drone mà Jarvis có thể kiểm soát được.

Chú ý

~40 \%~ điểm, tất cả các giá trị tuyệt đối của các tần số sẽ nhỏ hơn hoặc bằng ~10~.

Sample Input 1

1
1
2

Sample Output 1

1

Sample Input 2

2
0 0
1 1

Sample Output 2

2

Sample Input 3

2
1 2
5 5

Sample Output 3

1

Giải thích

Trong test thứ ba, nếu chúng ta chọn ~X = 3~, tần số nhà máy sẽ là ~4~ và ~5~ tương ứng (~1 + 3~ và ~2 + 3~), sau đó Jarvis chỉ có thể kiểm soát được chiến binh drone thứ hai. Nếu chúng ta chọn ~X = 4~, tần số nhà máy sẽ là ~5~ và ~6~, và sau đó Jarvis chỉ có thể kiểm soát được chiến binh drone thứ nhất. Không có giá trị ~X~ nào mà Jarvis có thể đồng thời kiểm soát cả hai chiến binh drone.


Bình luận đầu tiên

Bình luận

Không có bình luận nào.