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

Author Hung Nguyen Tuong

Bài 1. Tìm số

Cho trước số tự nhiên $A$. Hãy viết chương trình tìm số tự nhiên $n$ nhỏ nhất sao cho $S_n \ge A$ trong đó $S_k = 1^2 + 2^2 + 3^2 + ... + k^2$.

Ví dụ: Với số $A=10$ thì số nhỏ nhất thoả mãn bài toán là $n=3$.

Dữ liệu

Vào từ file văn bản TIMSO.INP gồm đúng một số nguyên dương $A \ (1 \ge A \ge 32000)$.

Kết quả

Đưa ra file văn bản TIMSO.OUT gồm đúng một số tự nhiên $n$ tìm được.

Ví dụ

Lời giải

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

int main()
{
    ll A; cin >> A;
    ll S=0, n=0;
    while (S<A){
        n++;
        S+=n*n;
    }
    cout << n;
    return 0;
}

Bài 2. Chấm thi

Trong kỳ thi vấn đáp môn Tin Học, học sinh phải trả lời các câu hỏi của thầy giáo. Nếu trả lời đúng, thầy giáo đánh dấu bằng ký tự $'C' \ (Correct)$, nếu sai thì đánh dấu $'N' \ (Incorrect)$ (Khi học sinh trả lời đúng, thầy sẽ đưa ra câu hỏi tiếp theo khó hơn câu trước, còn khi trả lời sai thầy sẽ cho câu hỏi mới dễ hơn). Sau khi thi xong, kết quả của mỗi học sinh là một xâu các ký tự $'C'$ và $'N'$.

Điểm số của học sinh sẽ được tính như sau:

• Với các câu trả lời sai học sinh không được điểm.
• Với mỗi câu trả lời đúng học sinh nhận được điểm bằng số lần trả lời đúng liên tiếp từ câu trả lời này trở về trước.

Ví dụ: nếu kết quả là $'CCNNCNNCCC'$, thì điểm số sẽ là $1+2+0+0+1+0+0+1+2+3=10$.

Yêu cầu

Cho xâu kết quả độ dài không quá $80$, hãy tính điểm của học sinh.

Dữ liệu

Vào từ file văn bản CHAMTHI.INP gồm một xâu kết quả thi.

Kết quả

Đưa ra file văn bản CHAMTHI.OUT gồm đúng một số nguyên là điểm số của xâu kết quả thi đó.

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 cnt = 0, ans = 0;
    for (int i=0;i<s.size();i++){
        if (s[i]=='N') cnt = 0;
        else{
            cnt++;
            ans+=cnt;
        }
    }
    cout << ans;
    return 0;
}

Bài 3. Mua kem

Nam và các bạn đi nghỉ hè ở đảo Tuần Châu thành phố Hạ Long. Thời tiết quá nóng bức, họ quyết định mua một vài que kem cho đỡ nóng. Có $N$ loại kem mút khác nhau đánh số từ 1 đến $N$. Có một số cặp mùi kỵ nhau làm mất ngon, Nam muốn biết xem có bao nhiêu cách mua $3$ que kem thuộc $3$ loại khác nhau sao cho không có cặp mùi nào kỵ nhau. Trình tự mua không đóng vai trò quan trọng.

Ví dụ:

• $n=5$.
• Số cặp mùi kỵ nhau $m=3:(1,2), \ (3,4), \ (1,3)$. Khi đó Nam có 3 cách mua: $(1,4,5), \ (2,3,5), \ (2,4,5)$.

Dữ liệu

Dòng đầu tiên của file vào chứa 2 số nguyên $N, M \ (1 \le N \le 200, 1 \le M \le 10000)$ tương ứng là số loại kem và số cặp mùi kỵ nhau. Dòng thứ $i$ trong $M$ dòng tiếp theo chứa 2 số nguyên $p,q \ (1 \le p,q \le n, p \neq q)$ ngăn cách nhau bởi một dấu cách, mô tả một cặp mùi kỵ nhau. Không có cặp mùi nào bị lặp lại.

Kết quả

File ra gồm một dòng chứa một số nguyên là kết quả tìm được.

Ví dụ

Lời giải

Ta khai báo mảng bool $a$, với $a[p][q] = a[q][p]$ thể hiện 2 loại kem $p$ và $q$ có mùi kỵ nhau.

Giả sử ta xét $\text{true}$ là kỵ nhau.

Vì trình tự mua không quan trọng, nên số cách mua $3$ loại trong $N$ loại là tổ hợp chập $3$ của $N$.

Ta sử dụng phương pháp sinh để đếm từng bộ 3 loại kem có thể mua bắt đầu từ $(1,2,3)$ và kết thúc tại $(N-2,N-1,N)$. Nếu $a[p][q] = a[q][p] = \text{true}$ thì có nghĩa cách mua đó 2 loại kỵ nhau, nên ta sẽ không đếm cách mua đó.

Độ phức tạp là: $O(C^3_n)$.

Code

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

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<bool>> no_combine(n + 1, vector<bool>(n + 1, false));
    for (int i = 0; i < m; i++)
    {
        int p, q;
        cin >> p >> q;
        no_combine[p][q] = no_combine[q][p] = true;
    }

    if (n < 3)
    {
        cout << 0;
        return 0;
    }

    vector<int> buy = {1, 2, 3};
    int ans = 0;
    while (true)
    {
        if (
            !no_combine[buy[0]][buy[1]] &&
            !no_combine[buy[1]][buy[2]] &&
            !no_combine[buy[2]][buy[0]])
            ans++;

        int reach_max = 2;
        while (reach_max >= 0)
        {
            if (buy[reach_max] != n - 2 + reach_max)
                break;
            reach_max--;
        }

        if (reach_max < 0)
            break;

        buy[reach_max]++;
        for (int i = reach_max + 1; i < 3; i++)
            buy[i] = buy[i - 1] + 1;
    }
    cout << ans;
    return 0;
}