trang chủ / đề bài / icpcwf12_l

Cuộc chiến thâu tóm

Đề bài

Mô tả

Bạn đang nghiên cứu một cuộc chiến thâu tóm giữa hai tập đoàn lớn, Takeover Incorporated và Buyout Limited. Mỗi tập đoàn kiểm soát một số công ty con. Mục tiêu của cuộc chiến đơn giản là đẩy đối thủ ra khỏi thị trường. Takeover Incorporated có N công ty con, Buyout Limited có M công ty con, và bạn biết giá trị thị trường của từng công ty con.

Mỗi tập đoàn có thể chỉ định một công ty con của mình thực hiện một vụ thâu tóm. Vụ thâu tóm có thể là thân thiện hoặc thù địch.

  • Thâu tóm thân thiện: một công ty con của một tập đoàn sáp nhập với một công ty con khác của cùng tập đoàn đó. Giá trị thị trường của công ty sau sáp nhập bằng tổng giá trị thị trường của hai công ty thành phần. Không có ràng buộc nào về độ lớn tương đối của hai công ty tham gia thâu tóm thân thiện.
  • Thâu tóm thù địch: một công ty con A của một tập đoàn tìm cách thâu tóm một công ty con B của tập đoàn kia. Để thành công, giá trị thị trường của A phải lớn hơn giá trị thị trường của B. Sau nước đi này, B biến mất khỏi thị trường. Giá trị thị trường của A không đổi (phần tài sản thu được từ B bù vừa đủ chi phí cho vụ thâu tóm).

Để đơn giản, giả sử không có dãy nước đi nào dẫn tới việc hai công ty con thuộc hai tập đoàn khác nhau có cùng giá trị thị trường.

Hai tập đoàn lần lượt đi các nước trong cuộc chiến, Takeover Incorporated đi trước. Một tập đoàn chỉ được bỏ lượt khi nó không thể thực hiện vụ thâu tóm nào (thân thiện hay thù địch). Tập đoàn nào bị thâu tóm hết mọi công ty con thì thua.

Hãy xác định tập đoàn nào có thể đảm bảo chiến thắng trong cuộc chiến này nếu cả hai đều chơi tối ưu.

Trong bộ test thứ nhất của ví dụ 1, Takeover Incorporated có thể ngay ở nước đầu dùng công ty giá trị 7 thâu tóm một công ty của Buyout Limited. Sau đó nó mất một công ty nhỏ (giá trị 1) vì một vụ thâu tóm thù địch, rồi nó thâu tóm nốt công ty thứ hai của Buyout Limited. Trong bộ test thứ hai, Takeover buộc phải thâu tóm thân thiện ở nước đầu. Buyout Limited gộp hai công ty của mình thành một công ty giá trị 10. Takeover lại buộc phải thâu tóm thân thiện (vì một lần nữa nó không có công ty nào đủ lớn để thâu tóm "gã khổng lồ" của Buyout). Lúc này Takeover có hai công ty, giá trị 9 và 3 hoặc 6 và 6. Trong cả hai trường hợp, Buyout thâu tóm một trong hai công ty, Takeover phải bỏ lượt, rồi Buyout thâu tóm nốt công ty còn lại.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test, đọc tới hết file. Mỗi bộ test gồm ba dòng:

  • Dòng thứ nhất chứa hai số nguyên N và M (1≤N≤105, 1≤M≤105) lần lượt là số công ty con của Takeover Incorporated và của Buyout Limited.
  • Dòng thứ hai chứa N số nguyên ai (1≤ai≤1012) là giá trị các công ty con của Takeover Incorporated.
  • Dòng thứ ba chứa M số nguyên bj (1≤bj≤1012) là giá trị các công ty con của Buyout Limited.

Dữ liệu ra

Với mỗi bộ test, in ra số thứ tự của bộ test và cụm từ Takeover Incorporated hoặc Buyout Limited tùy theo tập đoàn nào thắng cuộc chiến khi cả hai chơi tối ưu, theo định dạng trong ví dụ.

Ràng buộc

  • 1≤N,M≤105.
  • 1≤ai,bj≤1012.
  • Không có dãy nước đi nào làm hai công ty con của hai tập đoàn khác nhau có cùng giá trị.

Ví dụ

Input Output Giải thích
3 2
7 1 1
5 5
4 2
3 3 3 3
5 5
Case 1: Takeover Incorporated
Case 2: Buyout Limited
Như mô tả trong đề.
1 1
5
3
1 2
2
3 1
Case 1: Takeover Incorporated
Case 2: Buyout Limited
Bộ 1: công ty 5 thâu tóm ngay công ty 3. Bộ 2: Takeover chỉ có một công ty giá trị 2; nó không được bỏ lượt nên phải thâu tóm công ty 1, rồi bị công ty 3 thâu tóm.

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.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0