Tom, Jerry cùng Phân thân chi thuật

View as PDF

Submit solution

Points: 100.00 (partial)
Time limit: 1.0s
Memory limit: 488M
Input: stdin
Output: stdout

Authors:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

TomJerry là kẻ thù không đội trời chung. Nhưng suốt bao nhiêu năm, mèo Tom vẫn không thể nào bắt được chuột Jerry. Mèo Tom đương nhiên không phục, một con mèo sao lại thua một con chuột ngu ngốc được! Sau khi xem Naruto, cuối cùng Tom cũng học được Phân thân chi thuật, Tom chắc kèo lần này sẽ bắt được Jerry. Tuy nhiên đời không như là mơ, Jerry cũng là một fan của Naruto, và dĩ nhiên, đã học được phân thân chi thuật.

Cả TomJerry đều phân thân ra n1 con mèo Tomn1 con chuột Jerry khác. n chuột Jerry đang ở trong n cái hang khác nhau trên trục tọa độ Ox. Các mèo Tom cũng đang ở những vị trí khác nhau trên trục Ox. Thời gian để một mèo Tom chạy tới hang Jerry được tính bằng khoảng cách vị trí của Tom với hang. Nhưng chuột Jerry rất thông minh, vì vậy để Jerry không thể chạy thoát, các Tom phải tới các hang bắt Jerry trong thời gian ngắn nhất. Mỗi một Tom chỉ có thể bắt một Jerry. Bạn hãy giúp các Tom xác định mục tiêu của mỗi Tom là hang Jerry nào, để thời gian tất cả các Tom bắt được toàn bộ Jerry là ngắn nhất.

Tom rượt đuổi Jerry như phim: Tom & Jerry ep.19 - YouTube

Input:

  • Dòng đầu tiên chứa số n
  • Dòng thứ hai chứa n số nguyên là vị trí của các Tom trên trục số Ox
  • Dòng cuối cùng chứa n số nguyên là vị trí của các Jerry trên trục số Ox

    Output: Một số nguyên duy nhất là thời gian ngắn nhất để các Tom bắt được tất cả Jerry

    Ví dụ:

    Input
Copy
5
1 3 4 2 5 
-2 -1 -4 -5 -3
Output
Copy
6

Giới hạn:

Subtask 1 (30%): n10, các tọa độ có giá trị tuyệt đối không quá 106

Subtask 2 (70%): n106 , các tọa độ có giá trị tuyệt đối không quá 1018


Comments

Please read the guidelines before commenting.


There are no comments at the moment.