trang chủ / đề bài / threepart

Phân chia đề thi

Đề bài

Mô tả

Một đội gồm ba thí sinh chuẩn bị tham gia kỳ thi có n bài toán, đánh số từ 1 đến n. Mỗi bài toán được in trên một tờ đề riêng.

Ba thí sinh đã thống nhất cách chia đề: thí sinh thứ nhất giữ một tiền tố của dãy đề (một số tờ đầu tiên), thí sinh thứ ba giữ một hậu tố (một số tờ cuối cùng), và thí sinh thứ hai giữ toàn bộ phần còn lại ở giữa. Tuy nhiên các tờ đề bị in sai thứ tự, nên hiện tại mỗi người đang cầm một tập bài toán tùy ý.

Thí sinh thứ nhất đang giữ k1 bài, thí sinh thứ hai giữ k2 bài, thí sinh thứ ba giữ k3 bài. Mỗi bài toán thuộc về đúng một người.

Trong một lượt, một thí sinh có thể đưa một bài toán mình đang giữ cho một thí sinh khác. Hãy tìm số lượt tối thiểu để sau khi chia lại, thí sinh thứ nhất giữ một tiền tố của dãy 1,2,…,n, thí sinh thứ ba giữ một hậu tố, và thí sinh thứ hai giữ phần còn lại.

Sau khi chia lại, một người (hoặc thậm chí hai người) được phép không giữ bài toán nào.

Dữ liệu vào

  • Dòng đầu chứa ba số nguyên k1, k2, k3: số bài toán mà thí sinh thứ nhất, thứ hai và thứ ba đang giữ.
  • Dòng thứ hai chứa k1 số nguyên: các bài toán thí sinh thứ nhất đang giữ.
  • Dòng thứ ba chứa k2 số nguyên: các bài toán thí sinh thứ hai đang giữ.
  • Dòng thứ tư chứa k3 số nguyên: các bài toán thí sinh thứ ba đang giữ.

Dữ liệu ra

In ra một số nguyên duy nhất: số lượt chuyển tối thiểu cần thực hiện.

Ràng buộc

  • 1≤k1,k2,k3≤2·105
  • k1+k2+k3≤2·105
  • Đặt n=k1+k2+k3. Mọi số xuất hiện trong dữ liệu vào đều nằm trong đoạn [1,n] và mỗi giá trị xuất hiện đúng một lần trên toàn bộ ba dòng.

Ví dụ

Input Output Giải thích
2 1 2
3 1
4
2 5
1 n=5. Thí sinh thứ ba đưa bài 2 cho thí sinh thứ nhất. Khi đó người thứ nhất giữ tiền tố {1,2,3}, người thứ hai giữ {4}, người thứ ba giữ hậu tố {5}.
3 2 1
3 2 1
5 4
6
0 Cách chia hiện tại đã hợp lệ: tiền tố {1,2,3}, phần giữa {4,5}, hậu tố {6}.
2 1 3
5 6
4
1 2 3
3 Phương án tốt nhất là dồn toàn bộ 6 bài cho thí sinh thứ ba (tiền tố và phần giữa đều rỗng). Người thứ ba đã giữ sẵn 3 bài nên chỉ cần 3 lượt chuyển.
1 5 1
6
5 1 2 4 7
3
2 Phương án tốt nhất là dồn toàn bộ 7 bài cho thí sinh thứ hai. Người này đã giữ 5 bài, nên cần 2 lượt chuyển.

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