trang chủ / đề bài / icpc24_mt_f

Ba tòa nhà

Đề bài

Mô tả

Bạn là chủ một công ty xây dựng trong thành phố. Công ty có n công nhân, và có ba tòa nhà cần xây (gọi là tòa nhà A, B, C).

Bạn muốn phân công công nhân vào ba tòa nhà này: tòa nhà A, B, C nhận tối đa lần lượt nA, nB, nC công nhân. Mỗi công nhân được phân vào nhiều nhất một tòa nhà, và mỗi công nhân có nguyện vọng về những tòa nhà mà họ muốn được phân vào; một công nhân chỉ có thể được phân vào tòa nhà mà họ muốn.

Ví dụ, giả sử n=4 và nA=nB=nC=1 (đánh số bốn công nhân là 1,2,3,4):

  • Chỉ công nhân 1 muốn vào tòa nhà A.
  • Chỉ công nhân 1 muốn vào tòa nhà B.
  • Cả hai công nhân 2 và 3 muốn vào tòa nhà C.
  • Công nhân 4 không muốn vào tòa nhà nào.

Trong trường hợp này, vì nC=1, ta phải chọn công nhân 2 hoặc công nhân 3 cho tòa nhà C. Công nhân 1 chỉ có thể vào tòa nhà A hoặc tòa nhà B. Do đó, ta phân công được nhiều nhất hai công nhân.

Cho n, nA, nB, nC và nguyện vọng của n công nhân, hãy tính số công nhân lớn nhất có thể phân công vào các tòa nhà.

Dữ liệu vào

  • Dòng đầu tiên chứa số bộ dữ liệu T (1≤T≤10).
  • Mỗi bộ dữ liệu gồm:
    • Dòng đầu chứa n (1≤n≤10000).
    • Dòng thứ hai chứa nA, nB, nC cách nhau bởi dấu cách (1≤nA,nB,nC≤n).
    • Ba dòng tiếp theo mô tả những công nhân muốn vào từng tòa nhà. Dòng thứ nhất bắt đầu bằng mA (số công nhân muốn vào tòa nhà A), tiếp theo là mA số phân biệt (chỉ số của các công nhân đó, từ 1 đến n), cách nhau bởi dấu cách. Tương tự, dòng thứ hai chứa mB và mB số, dòng thứ ba chứa mC và mC số (1≤mA,mB,mC≤n).

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra số công nhân lớn nhất có thể phân công vào ba tòa nhà, mỗi kết quả trên một dòng.

Ràng buộc

  • 1≤T≤10
  • 1≤n≤10000
  • 1≤nA,nB,nC≤n
  • 1≤mA,mB,mC≤n

Ví dụ

Input Output Giải thích
2
5
2 1 1
4 1 2 3 4
1 4
1 5
4
1 1 1
1 1
1 1
2 2 3
4
2
Bộ 1: hai trong ba công nhân 1,2,3 vào tòa nhà A, công nhân 4 vào tòa nhà B, công nhân 5 vào tòa nhà C. Bộ 2: chính là ví dụ trong đề bài.
1
3
1 1 1
3 1 2 3
1 1
1 2
3 Công nhân 1 vào B, công nhân 2 vào C, công nhân 3 vào A.

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