Lời Giải HSG Tin Tỉnh Quảng Ninh (B) - 2010

Author Hung Nguyen Tuong

Bài 1. Tần số

Cho xâu $S$ chỉ gồm toàn chữ cái tiếng Anh bao gồm chữ thường và chữ in hoa. Hãy viết chương trình cho biết có bao nhiêu chữ cái khác nhau (chữ thường và chữ in hoa coi là như nhau) có mặt trong xâu $S$, số lần xuất hiện (tần số) của từng chữ cái và chữ cái có mặt nhiều nhất.

Dữ liệu

Vào từ file tan_so.inp gồm một dòng chứa xâu $S$ (không quá $255$ chữ cái).

Kết quả

Ghi ra file tan_so.out gồm một dòng ghi lần lượt:

• Số lượng chữ cái khác nhau.
• Từng chữ cái cùng tần số của nó (ghi theo thứ tự bảng chữ cái).
• Chữ cái có tần số lớn nhất (nếu có nhiều chữ cái như vậy thì ghi ra chữ cái đứng trước bảng mã ASCII).

Ví dụ

Lời giải

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl '\n'

int main()
{
    string s; cin >> s;
    int a[121] = {0};
    int cnt=0, mx=0;
    char c;
    for (auto i : s){
        if ('a' <= i && i <= 'z') i -= 32;
        if (a[i]==0) cnt++;
        a[i]++;
    }
    cout << cnt;
    for (int i=0;i<121;i++){
        if (a[i]!=0){
            cout << (char)i << a[i];
            if (a[i] > mx){
                mx = a[i];
                c = (char)i;
            }
        }
    }
    cout << c;
    return 0;
}

Bài 2. Sát sau

Cho một số tự nhiên $A$ gồm $N$ chữ số $(1<N \le 80)$.

Ví dụ với số $A=5264$:

• Nếu hoán vị $4$ chữ số của $A$ ta được $24$ số như sau:

  $$5246,5264,5624,5642,5426,5462,2564,2546,2654,2645,2456,2465,$$
  $$6524,6542,6254,6245,6452,6425,4526,4562,4256,4265,4652,4625$$

• Sau đó sắp xếp $24$ số này theo thứ tự từ điển (tăng dần) ta được:

  $$2456,2465,2546,2564,2645,2654,4256,4265,4526,4562,4625,4652,$$
  $$5246,5264,5426,5462,5624,5642,6245,6254,6425,6452,6524,6542$$

• Lúc này số $5426$ đứng ngay sau số đã cho $5264$ trong kết quả sắp xếp này gọi là số sát sau của số đã cho. Cho số $A$, hãy tìm số sát sau của số $A$.

Dữ liệu

Vào từ file SATSAU.INP có cấu trúc:

• Gồm một dòng chứa số nguyên $A$.

Kết quả

Ghi ra file SATSAU.OUT như sau:

• Nếu có nghiệm thì ghi số sát sau của số $A$.
• Nêu vô nghiệm thì ghi chữ số $0$.

Ví dụ

Lời giải

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl '\n'

int main()
{
    string s;
    cin >> s;
    char min_d = CHAR_MAX;
    int n = s.size(), a = n, b;
    for (int i = n - 1; i > 0; i--)
    {
        if (s[i - 1] < s[i])
        {
            a = i - 1;
            break;
        }
    }
    if (a == n)
    {
        cout << 0;
        return 0;
    }
    for (int i = n - 1; i > a; i--)
    {
        if (s[i] > s[a] && s[i] < min_d)
        {
            min_d = s[i];
            b = i;
        }
    }
    swap(s[a], s[b]);
    sort(s.begin() + a + 1, s.end());
    cout << s;
    return 0;

Bài 3. Trồng cây

Một lớp học được giao nhiệm vụ trồng cây trên một đám đất hình tam giác. Yêu cầu tại mỗi điểm nằm trong tam giác (không kề biên) mà có toạ độ là những số nguyên thì trồng một cây. Hãy viết chương trình tính số cây mà lớp đó phải trồng.

Ví dụ: Cho toạ độ $3$ đỉnh của tam giác là: $A(2;1), \ B(1;6), \ C(-5;2)$.

Số cây phải trồng là $16$.

Dữ liệu

Dữ liệu vào tròn file Trcay.inp gồm 6 số nguyên trên một dòng ngăn cách bởi dấu cách, tương ứng là toạ độ đỉnh $A, B,C$ của tam giác tạo nên đám đất phải trồng cây (Toạ độ ba đỉnh của tam giác là các số nguyên thuộc đoạn $[-150;150]$).

Kết quả

Dữ liệu ra trong file Trcay.out gồm một số nguyên là số cây phải trồng.

Ví dụ

Lời giải

Giả sử ta có tam giác $ABC$, và điểm $D$.

$D$ nằm trong tam giác nếu: $dt_{ABC} = dt_{ABD} + dt_{BCD} + dt_{CAD}$.

Nếu $D$ nằm trên 1 trong 3 cạnh $AB,BC,CA$ thì điều trên cũng thoả mãn, tuy nhiên diện tích tam giác tạo bởi $D$ và 2 đỉnh của cạnh nó nằm trên sẽ có diện tích là $0$, có nghĩa là: $dt_{ABD} \times dt_{BCD} \times dt_{CAD} = 0$.

Độ phức tạp: $O((x_{\max}-x_{\min}) \times (y_{\max}-y_{\min}))$.

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl '\n'

double area(int a1, int a2, int b1, int b2, int m1, int m2)
{
    int n1 = b2 - a2, n2 = a1 - b1;
    return abs((double)(n1 * (m1 - a1) + n2 * (m2 - a2)) * 0.5);
}
int main()
{
    int a[7];
    int min_x, max_x, min_y, max_y, ans = 0;
    min_x = min_y = 300;
    max_x = max_y = -300;
    for (int i = 1; i <= 6; i++)
    {
        cin >> a[i];
        if (i % 2 != 0)
        {
            min_x = min(min_x, a[i]);
            max_x = max(max_x, a[i]);
        }
        else
        {
            min_y = min(min_y, a[i]);
            max_y = max(max_y, a[i]);
        }
    }
    double total_area = area(a[1], a[2], a[3], a[4], a[5], a[6]);
    for (int x = min_x; x <= max_x; x++)
    {
        for (int y = min_y; y <= max_y; y++)
        {
            double area1 = area(a[1], a[2], a[3], a[4], x, y);
            double area2 = area(a[5], a[6], a[3], a[4], x, y);
            double area3 = area(a[1], a[2], a[5], a[6], x, y);
            double sum = area1 + area2 + area3, eps = 1e-5;
            if (area1 * area2 * area3 == 0)
                continue;
            if (abs(sum - total_area) <= eps)
                ans++;
        }
    }
    cout << ans;
    return 0;
}