02/10/2018, 14:17
C11BEAU spoj – Tên đẹp
Nguồn đề bài: http://vn.spoj.com/problems/C11BEAU/ 1. Đề bài C11BEAU spoj Người dân ở đất nước B11 (láng giềng của đất nước C11) có một phong tục rất đặc biệt. Chuyện là họ rất thích hai chữ cái ‘A’ và ‘B’, cho nên bất kì ai đều được đặt tên chỉ gồm ...
Nguồn đề bài: http://vn.spoj.com/problems/C11BEAU/
1. Đề bài C11BEAU spoj
Người dân ở đất nước B11 (láng giềng của đất nước C11) có một phong tục rất đặc biệt. Chuyện là họ rất thích hai chữ cái ‘A’ và ‘B’, cho nên bất kì ai đều được đặt tên chỉ gồm ‘A’ và ‘B’. Theo họ, một tên đẹp phải bao gồm tất cả các yếu tố sau:
- Tên phải không chứa quá countA chữ cái ‘A’
- Tên phải không chứa quá countB chữ cái ‘B’
- Mỗi xâu con gồm các chữ cái ‘A’ liên tiếp có độ dài không quá maxA
- Mỗi xâu con gồm các chữ cái ‘B’ liên tiếp có độ dài không quá maxB
Vào ngày Quốc khánh sắp tới, nhà vua đất nước B11 muốn tìm một tên đẹp dài nhất để đặt cho hoàng tử mới ra đời. Bạn hãy giúp nhà vua tính xem độ dài tên hoàng tử là bao nhiêu.
Ví dụ với countA = 3, countB = 5, maxA = maxB = 1, ta có tên đẹp dài nhất sẽ là ‘BABABAB’. Như vậy kết quả cần tìm là 7.
Dữ liệu
- Dòng 1: Số nguyên T là số test của chương trình.
- Mỗi dòng trong T dòng tiếp theo: 4 số nguyên countA, countB, maxA, maxB.
Output
Gồm T dòng, mỗi dòng là kết quả tìm được tương ứng với mỗi test.
Ví dụ
Input:
4
0 0 10 10
10 10 0 0
3 5 1 1
6 7 8 9
Output:
0
0
7
13
Ràng buộc
- 1 ≤ T ≤ 100
- 0 ≤ countA, countB, maxA, maxB ≤ 106
- Trong 50% số test, 0 ≤ countA, countB, maxA, maxB ≤ 100
2. Code tham khảo C11BEAU spoj
uses math;
const fi=';
type data=longint;
var
f:text;
t,i:data;
countA,countb,maxa,maxb:int64;
procedure xuli;
begin
if (countA=0) or (maxa=0) then
writeln(min(countb,maxb))
else
if (countb=0) or (maxb=0) then
writeln(min(counta,maxa))
else
begin
if counta=countb then
writeln(2*counta);
if counta < countb then
writeln(2*counta + 1 + min(countb-counta-1,(maxb-1)*(counta+1)));
if countb < counta then
writeln(2*countb + 1 + min(counta - countb - 1, (maxa-1)*(countb + 1)));
end;
end;
begin
assign(f,fi); reset(f);
readln(f,t);
for i:=1 to t do
begin
readln(f,counta,countb,maxa,maxb);
xuli;
end;
close(f);
end.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | uses math; const fi='; type data=longint; var f:text; t,i:data; countA,countb,maxa,maxb:int64; procedure xuli; begin if (countA=0) or (maxa=0) then writeln(min(countb,maxb)) else if (countb=0) or (maxb=0) then writeln(min(counta,maxa)) else begin if counta=countb then writeln(2*counta); if counta < countb then writeln(2*counta + 1 + min(countb-counta-1,(maxb-1)*(counta+1))); if countb < counta then writeln(2*countb + 1 + min(counta - countb - 1, (maxa-1)*(countb + 1))); end; end; begin assign(f,fi); reset(f); readln(f,t); for i:=1 to t do begin readln(f,counta,countb,maxa,maxb); xuli; end; close(f); end. |
