Bài tập tuần 5: ATM thi lập trình

ATM THI LẬP TRÌNH

Câu lạc bộ EGG Club tổ chức một cuộc thi lập trình cho sinh viên ở Hà Nội. ATM là một sinh viên ngành công nghệ thông tin nên cũng lập một team cùng các bạn trong lớp để tham gia.

Cuộc thi lập trình có tên Hatching of Eggs. Cuộc thi gồm nhiều team tham gia, mỗi team có n người. Mỗi người có một khả năng lập trình, khả năng lập trình của người thứ i là a[i].

Thể lệ thi đấu của cuộc thi là 2 team đối đầu trực tiếp, team nào thắng thì sẽ được vào vòng trong.

Khi thi đấu đối đầu 2 team, mỗi team sẽ cử lần lượt một người ra để thi đấu, 2 team đấu nhau thì sẽ có n cặp đấu cá nhân. Ai giải bài toán tốt hơn (có khả năng lập trình cao hơn) thì sẽ chiến thắng. Nếu 2 người có khả năng lập trình bằng nhau thì cặp đấu đó 2 bên hòa. Bên nào có nhiều cặp chiến thắng hơn thì sẽ thắng team còn lại.

Do là người quen biết rộng nên ATM biết được khả năng lập trình của từng người trong toàn bộ các team. Anh cần đưa ra chiến thuật để team anh có cơ hội giành chiến thắng cao nhất.

Ví dụ:

Team anh có 5 người với khả năng lập trình lần lượt là

14, 6, 3, 1, 2.

Team đối thủ của anh có 5 người với khả năng lập trình lần lượt là

7, 12, 3, 1, 5.

Cách thức tối ưu để team ATM chiến thắng là cử người ra đấu để tạo thành các cặp:

giaithich

 

Với cách đấu này, team ATM sẽ có 3 cặp đấu thắng và 2 cặp thua, như vậy team anh sẽ chiến thắng.

Yêu cầu: Biết n và khả năng lập trình của từng người trong 2 team, đưa ra phương án đấu tốt nhất cho team ATM. Nếu team ATM không thể chiến thắng, thông báo là

khong-the-chien-thang

Nếu team ATM có thể chiến thắng, thông báo là team có thể chiến thắng và đưa ra giải pháp đấu để chiến thắng:

co-the-chien-thang

Mô tả dữ liệu đầu vào và đầu ra:

  • Input.txt:
     5
    14  6  3  1  2
    7  12  3  1  5
  • Output:
    TEAM BAN CO THE CHIEN THANG
    THUC HIEN CAC CAP DAU SAU DE CHIEN THANG:
    1 – 2
    4 – 1
    2 – 5
    3 – 4
    5 – 3
The following two tabs change content below.