[Lập trình newbie] Mỗi ngày một bài toán (số 16)

[09520281]

Tình hình là 15 số trước mấy bài toán không làm khó mấy bạn được, đây là một điều đáng mừng cho UIT. Hôm nay mới nhận tin bạn Đăng Châu (giải 3 Olympic 2011) đã lên đường đi du học Phần Lan :unhappy:. Nhưng không sao chúng ta phải tự hào chứ nhỉ :sogood:. Sau đây là một bài toán rất là "củ chuối" :shock:.
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.

Ràng buộc

• 1 ≤ T ≤ 100
• 0 ≤ countA, countB, maxA, maxB ≤ 10⁶
• Trong 50% số test, 0 ≤ countA, countB, maxA, maxB ≤ 100

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
Chúc mấy pro vui vẻ :love:

[12520527]

Đề post lâu rồi mà sao chẳng có ai tham gia :sad: nghĩ nhanh code ẩu vậy, chưa tối ưu và test kĩ, mọi người ném gạch ít ít thôi nhé :brick:

#include <iostream>
#include <stdio.h>
using namespace std;

int min(int a,int b)
{
    if (a>=b) return b;
    return a;
}
int main()
{
    int t,i,len,countA,countB,maxA,maxB,count,res,left;
    scanf("%d\n",&t);
    for (i=1;i <= t;i++)
    {
        scanf("%d %d %d %d",&countA,&countB,&maxA,&maxB);
        if ((maxA==0) || (maxB==0))
        {
            printf("%d",0);
            continue;
        }
        len = min(countA,countB);
        countA-=len;
        countB-=len;
        if (countB==0)
        {
            countB = countA;
            maxB=maxA;
            if (countB==0)
            {
                res = 2*len;
                printf("%d",res);
                continue;
            }
        }
        if (maxB==1)
        {
            res = 2*len+1;
            printf("%d",res);
            continue;
        }
        count = countB/(maxB-1);
        if (count <= len)
        {
            res = 2*len + count*(maxB-1);
            left = countB-count*(maxB-1);
            res += min(left,countB);
        };
        if (count > len)
        {
            res = 2*len + len*(maxB-1);
            left = countB-(len-1)*maxB;
            res += min(left,countB);
        };
        printf("%d\n",res);
    };
    return 0;
}

[09520281]

up cho các bạn chưa xem ^^

[12520070]

không hiểu cái gì luôn

[09520281]

Bạn đọc mấy số trước để làm quen với mấy dạng đề toán này

[kengo14]

Mình nghĩ bạn nên có lời giải thích , hoặc nêu thuật tóan , giả code trước, dùng comment với mỗi hàng code để mọi người có thể hiểu ý bạn làm gì. ^^.

[12520527]

Chả biết giải thích như thế nào cho dễ hiểu, tại mình chẳng có năng khiếu sư phạm :shot: Thôi thì thế này vậy
Đề yêu cầu có tối đa countA kí tự 'A', countB kí tự 'B'. Chúng ta sẽ thành lập 1 xâu có độ dài là len = min(countA,countB)*2 gồm các kí tự 'A' và 'B' xen kẽ. VD : ABABABABA ....
Như vậy số kí tự A và số kí tự B tối đa còn có thể thêm vào được là countA-len và countB-len. Chúng ta lần lượt thêm vào ở vị trí các kí tự A và B đó maxA-1 và maxB-1 cho đến khi nào countA < maxA và countB < maxB hoặc đã thêm vào hết tất cả các vị trí (tùy theo min là countA hay count B, kí tự thêm vào sẽ là kí tự ngược lại). Số lượng còn lại sẽ được thêm vào đầu hoặc cuối xâu tùy theo kí tự là 'A' hay 'B'.
ps:ps:ps:ps:ps:

[12520527]

Ế rồi
Bùn thế nhỉ ps:ps:ps:ps:ps:

[12520527]

Topic không thu hút được sự chú ý :unhappy:
Úp úp úp úp úp
Chán thế nhỉ :aboom:

[12520568]

không có sự chú ý nào hết. năm nhất thì chưa học gì nên chả biết giải......like me... năm 2,3,4 giải được không. e cũng không biết mà nếu giải được thì dễ wá chăng nên không thèm giải...... để kiếm cái máy học C++ vài tháng sẽ góp vui.... hi!

[09520281]

chắc phải hạ level xuống đại trà rồi có bài toán mở rộng thêm, hợp lý ko ta :kool:

[11520447]

đúng rầu đó a, bài này e chưa hiểu hạ lv đi a

[12520123]

Mình mới bắt đầu học C++ dc ít ngày:vip: mới giải dc cái pt bậc 2 thôi:brick: nhìn cái này mù tịt:shot:

[12520527]

Có test thì OK luôn anh :sexy:

[09520281]

Mấy bro đâu rồi ^^