P142SUMA - ROUND 2A - Tìm số

Link Sub: http://www.spoj.com/PTIT/problems/P142SUMA/
Người Gửi: Dương Lee

• Problem:

Một số được gọi là số tam giác nếu nó có dạng k*(k+1) / 2 với k là một số nguyên dương.  
Nhiệm vụ của bạn là kiểm tra một số có là tổng của 2 số tam giác không, 2 số đó không nhất thiết là phải khác nhau.
Input
Dòng duy nhất là một số nguyên dương n cần kiểm tra (1 <= n <= 10^9).

Output
In ra “YES” nếu số đó thỏa mãn, “NO” trong trường hợp còn lại.

Example:

Input

256

Output:

YES

Input

512

Output:

NO

• Solution:

- Tìm tất cả các số là số tam giác <= n; 
- Nếu một số n là tổng của 2 số tam giác thì: tồn tại một 1 số x là số tam giác sao cho n-x là số tam giác. 
-> Vậy với mỗi số số tam giác tìm được ở bước 1 thì chặt nhị phận tìm số tam giác n-x. Nếu tìm được thì in YES không tìm được thì NO.

• Code:

C++:

JAVA:

BCTEST13 - Tổng may mắn

Link Sub: http://www.spoj.com/PTIT/problems/BCTEST13/
Người Gửi: Dương Lee

• Problem:

Cùng sở thích với Bờm, Tèo cũng rất thích các số may mắn. Ta đã biết rằng một số gọi là số may mắn nếu biểu diễn thập phân của nó chỉ chứa các chữ số may mắn là 4 và 7. Ví dụ: Các số 47,744,4 là số may mắn còn 5,17,467 không phải là số may mắn.  
Nhưng khác với Bờm, Tèo lại định nghĩa next(x) là số may mắn bé nhất lớn hơn hoặc bằng x.  
Mở rộng hơn nữa, Tèo lại nghĩ ra Tổng may mắn LKSUM của hai số l,r (l≤r) như sau:  
LKSUM=next(l)+next(l+1)+...+next(r-1)+next(r)  
Bài toán đã trở nên khó khăn hơn nên Tèo cần sự giúp đỡ của các bạn sinh viên PTIT. Hãy giúp Tèo bài toán trên nhé !!!

Input
Một dòng duy nhất chứa hai số nguyên l và r (1≤l≤r≤109).

Output
Một số nguyên duy nhất là giá trị của tổng LKSUM.

Example:

Input

2 7

Output:

33

Giải thích: next(2)+next(3)+next(4)+next(5)+next(6)+next(7)=4+4+4+7+7+7=33

Input

7 7

Output:

7

Giải thích: next(7)=7

• Solution:

- Cách làm: + Sinh các trường hợp từ 1->10 chữ số cho 4 và 7; Sau khi sinh sẽ có mảng dãy số v[]={ 4, 7, 44, 47, ..., 77..7 } được đánh số thứ tự từ 0, 1, 2, 3, ...., size(). + Chặt nhị phân tìm số lớn hơn gần với nó nhất trong mảng v. (p/s vì sinh tối đa 10 chữ số nên độ phức tạp cũng không nhiều khoảng O(10000) nên có thể dùng tìm kiếm tuyến tính). + Xét các trường hợp và tính toán các khoảng tạo ra. VD: 2 và 8 -> tìm được: 4 và 44 -> tạo ra các khoảng: (2, 4] gồm các số có next()=4; (4, 7] gồm các số có next()=7; (7, 8] gồm các số có next()=44; Như vậy chỉ cần biết được các khoảng chia sẽ biết được có bao nhiêu số trong đó có cùng giá trị next.

• Code:

C++:

JAVA:

P145PROI - ROUND 5I - Mật khẩu

Link Sub: http://www.spoj.com/PTIT/problems/P145PROI/
Người Gửi: Dương Lee

• Problem:

Một xâu ký tự được gọi là mật khẩu “an toàn” nếu xâu có độ dài ít nhất bằng 6 và xâu chứa ít nhất một chữ cái in hoa , một chữ cái thường , một chữ số .  
Ví dụ, ‘a1B2C3’, ‘tinHoc6’ là hai mật khẩu “an toàn”. Còn ‘a1B2C’, ’a1b2c3’, ‘A1B2C3’, ‘tinHoc’ đều không phải là mật khẩu “an toàn”.
Một lần, Tí nhìn thấy một xâu S, chỉ gồm các loại ký tự: chữ cái in hoa, chữ cái thường và chữ số. Tí muốn tự kiểm tra khả năng đoán nhận mật khẩu bằng cách đếm xem có bao nhiêu cặp chỉ số (i, j) thỏa mãn điều kiện:  1 ≤ i < j ≤ length(S) và xâu con gồm các ký tự liên tiếp từ i đến j của S là mật khẩu “an toàn”.  
Cho xâu S, các hãy tính số lượng cặp chỉ số (i, j) thỏa mãn điều kiện nêu trên.
Input
Một dòng chứa xâu S có độ dài <= 10^6.

Output
In ra một số nguyên duy nhất là số cặp chỉ số (i, j) tìm được.

Example:

Input

abc3456789PQ

Output:

6

Input

abc123

Output:

0

• Solution:

- Quy hoạch xâu: Xây dựng mảng pass mà: + Với mỗi một vị trí xác định xem từ đầu xâu cho đến nó có bao nhiêu kí tự số, có bao nhiêu chữ thường, chữ hoa. - Tìm kiếm nhị phân: + Tại mỗi vị trí trên xâu, tìm vị trí gần nhất (VT) mà tại đó mật khẩu an toàn (check_safe) trên mảng pass mới quy hoạch. - Tính toán: + Với mỗi vị trí tìm thấy thì số lượng mật khẩu an toàn tạo được sẽ là +=(n-VT+1) (Vì khi mật khẩu đã an toàn rồi thì thêm bất kì kí tự nào nó vẫn an toàn :v) Độ phức tạp O(NlogN).

• Code:

C++:

https://ideone.com/LmEflP

#include <iostream>
#include <string>
using namespace std;

struct data
{
    int hv_1;
    int hv_A;
    int hv_a;
} typedef data;

data pass[1000006];

int check_safe (int begin, int end)
{
    int num_1=pass[end].hv_1-pass[begin-1].hv_1;
    int num_a=pass[end].hv_a-pass[begin-1].hv_a;
    int num_A=pass[end].hv_A-pass[begin-1].hv_A;
    if (num_1>0 && num_a>0 && num_A>0 && end-begin+1>=6) return 1;
    else return 0;
}

int BSearch (int begin, int front, int back)
{
    int vt=-1;
    while (front<=back && back-begin+1>=6)
    {
        int mid = (front+back)/2;
        if (check_safe (begin, mid)==1)
        {
            vt=mid;
            back=mid-1; 
        }
        else front=mid+1;
    }
    return vt;
}

int main ()
{
    string xau;
    cin>>xau;
    pass[0].hv_1=0;
    pass[0].hv_a=0;
    pass[0].hv_A=0;
    int n=xau.length();
    for (int i=1; i<=n; i++)
    {
        if (xau[i-1]>='0' && xau[i-1]<='9')
        {
            pass[i] = pass[i-1];
            pass[i].hv_1++; 
        }
        else if (xau[i-1]>='a' && xau[i-1]<='z')
        {
            pass[i] = pass[i-1];
            pass[i].hv_a++;
        }
        else if (xau[i-1]>='A' && xau[i-1]<='Z')
        {
            pass[i] = pass[i-1];
            pass[i].hv_A++;
        }
    }
    long long count=0;
    for (int i=1; i<=xau.length()-6+1; i++)
    {
        int VT = BSearch (i, i, n);
        if (VT!=-1)
        {
            count+=n-VT+1;
        } else break;
    }
    cout<<count;
    return 0;
}

JAVA:

P155SUMD - ROUND 5D - Chỉ là sắp xếp

Link Sub: http://www.spoj.com/PTIT/problems/P155SUMD/
Người Gửi: Vô Danh

• Problem:

Cho 2 dãy số, dãy a[] có n phần tử, dãy b[] có m phần tử.  
Yêu cầu : In ra m dòng, dòng thứ i là số lượng số trong dãy a nhỏ hơn hoặc bằng b[i].
Input
Dòng đầu tiên chứa 2 số n, m lần lượt là số lượng phần tử của 2 dãy a[], b[].  
Dòng thứ 2 chứa n số nguyên a[1], a[2], … a[n].  
M dòng tiếp theo mỗi dòng chứa 1 số nguyên b[1], b[2], … b[m]  
(1 <= n, m, a[i], b[i] <= 10^6)

Output
In ra kết quả bài toán.

Example:

Input

5 3
1 2 3 4 5
2
3
4

Output:

2
3
4

• Solution:

- Sắp xếp lại mảng a tăng dần. - Sử dụng biến thể chặt nhị phân tìm vị trí cuối cùng mà nó bé hơn hoặc bằng số cần tìm (bsearch). -> in ra vị trí (chính là số lượng số <= ) *Chú ý: Nếu không tìm thấy in ra '0'; Độ phức tạp O(m*logn) tùy thuộc vào dãy a. (sort trong thư viện là heap sort)

• Code:

C++:

JAVA:

DTTUI1 - Cái túi 1

Link Sub: http://vn.spoj.com/problems/DTTUI1/
Người Gửi: Dương Lee

• Problem:

Cây khế nhà Khánh rất sai quả nên có một con chim to to đến ăn. Ăn xong, chim chở Khánh ra đảo để trả công bằng vàng. Đảo có N cục vàng. Anh ấy muốn chuyển hết cả N cục vàng của mình về nhà. Nhưng khổ nổi các cục vàng này lại có trọng lượng và kích thước khổng lồ. Khánh đem theo một cái túi ba trăm gang to đùng nhưng vẫn chưa chắc chứa hết đống vàng này. Khổ quá đi! Lấy cục nào, bỏ cục nào bây giờ! Các bạn giúp anh ấy tìm ra một cách chọn vàng để thu được giá trị lớn nhất mà vẫn không làm rách túi đi.
Input
Dòng 1: Chứa 2 số nguyên: số cục vàng N (1 ≤ N ≤ 40) và tải trọng tối đa của túi M (1 ≤ M ≤ 10^9). 
N dòng sau: Mỗi dòng chứa 2 số nguyên: trọng lượng Wi và giá trị Vi của cục vàng thứ i (1 ≤ Wi, Vi ≤ 10^8).

Output
Một số nguyên duy nhất là giá trị lớn nhất thu được.

Example:

Input

3 4
1 4
2 5
3 6

Output:

10

• Solution:

Bài này N=40 (không quá lớn) nên ta có thể phân tập. Các bước làm: - Chia đôi tập dữ liệu nhận vào: P2: N2=N/2 và P1: N1=N-(N/2); - Sinh nhị phân các trường hợp chọn vàng của P1 và P2 (sao cho khối lượng không quá M ở mỗi tập + nhánh cận để giảm time). - Sắp xếp P2 tăng dần theo khối lượng. - Quy hoạch lại giá trị của mỗi cục vàng (S[]) sao cho S[i] = max (P2_[1->i]_V). - Với mỗi W của P1_i tìm vị trí (VT) P2 có W sao cho (P2_W + P1_i_W <= M). (Tìm nhị phân). - Với mỗi VT ta đã có sẵn S[VT] là giá trị max V của P2 đã quy hoạch ngay trên. Chỉ cần lấy Ans = max (Ans, P1_i_V+S[VT]). *Chú ý: Vì mỗi P1_W và P2_W nó đã <= M rồi nên cũng cần so sánh Ans với P1_V, P2_V;

• Code:

C++:

JAVA:

P147PROG - ROUND 7G - Điểm cân bằng

Link Sub: http://www.spoj.com/PTIT/problems/P147PROG/
Người Gửi: Dương Lee

• Problem:

Trong không gian hai chiều cho một tập hợp n điểm, giả sử mỗi điểm được đặc trưng bởi tọa độ (x_i,y_i) và trọng lượng m_i. Moment trọng lượng theo trục x của tập hợp điểm được xác định theo
công thức: M_x = sum all m_i * (b - y_i).  
Còn moment trọng lượng theo trục y là: M_y = sum all m_i * (a - x_i).  
Điểm cân bằng của tập hợp điểm trên là điểm có tọa độ (a, b) sao cho cả hai moment trên đều bằng 0.
Input
Mỗi bộ test bắt đầu với số nguyên n là số điểm, n dòng tiếp theo lần lượt ghi tọa độ x_i, y_i và giá trị mi của từng điểm. Các bộ test ngăn cách bởi một dòng trống.  
Input kết thúc khi gặp n<0.

Output
Với mỗi bộ test, ghi ra màn hình thứ tự bộ test và giá trị tọa độ a, b tìm được. Các giá trị tọa độ được làm tròn đến 2 số sau dấu phẩy.

Example:

Input

3
1 1 10
22 1 10
1 31 10
3
10 10 100
20 20 50
10 40 30
-4

Output:

Case 1: 8.00 11.00
Case 2: 12.78 17.78

• Solution:

Mình sẽ nói về x nhé còn y sẽ tương tự: - Tìm x_min và x_max - Chặt nhị phân trên số thực với điểm đầu là x_min, điểm cuối là x_max. - Với mỗi lần chặt thì tính theo công thưc M_y bên trên. - tg = Lấy phần nguyên của M_y*100 (vì đề yêu cầu làm tròn hai chữ số). - Nếu tg == 0 thì giá trị chặt đó là giá trị cần tìm. Nếu không? thì chia ra các khoảng tiếp theo để tìm. - Lúc in ra thì áp dụng in trong C là %.2f nó sẽ tự động làm tròn.

• Code:

C++:

JAVA: