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

Author Hung Nguyen Tuong

Bài 1. Dãy nguyên tố

Số tự nhiên $p > 1$ là số nguyên tố nếu $p$ có đúng hai ước số là $1$ và $p$. Cho dãy $n$ số tự nhiên $a_1,a_2,...,a_n$.

Yêu cầu

Đếm số các số nguyên tố của dãy, cho biết số nguyên tố lớn nhất trong dãy, vị trí của số đó trong dãy đã cho. (Trường hợp có nhiều số nguyên tố cùng bằng số nguyên tố lớn nhất thì đưa ra vị trí nhỏ nhất).

Dữ liệu

Tệp văn bản DAYNGTO.INP gồm hai dòng:

• Dòng thứ 1 chứa số tự nhiên $n \ (1 \le n \le 10^4)$.
• Dòng thứ 2 chứa $n$ số tự nhiên $a_1,a_2,...,a_n \ (1 \le a_i \le 2*10^9, \ i = 1,\ldots,n)$ cách nhau bởi dấu cách.

Kết quả

Ghi ra tệp văn bản DAYNGTO.OUT một dòng chứa 3 số nguyên là số các số nguyên tố có trong dãy, số nguyên tố lớn nhất và chỉ số của số nguyên tố lớn nhất (cách nhau bởi dấu cách). Ghi khong co nếu không có số nào trong dãy là số nguyên tố.

Ví dụ

Lời giải

Kiểm tra Miller-Rabin

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl '\n'
ll sqr(ll x, ll m){
    return (x%m * x%m)%m;
}
ll power(ll a, ll b, ll m){
    if (b==0) return 1%m;
    if (b%2==0) return sqr(power(a, b/2, m), m)%m;
    return (a%m * sqr(power(a, b/2, m), m)%m)%m;
}
bool test(ll a, ll n, ll k, ll m){
    ll mod = power(a, m, n);

    if (mod==1 || mod==n-1) return true;

    for (int l=1;l<k;l++){
        mod = (mod * mod) % n;
        if (mod==n-1) return true;
    }
    
    return false;
}
bool RabinMiller(ll n){
    if (n==2 || n==3 || n==5 || n==7) return true;
    if (n<11) return false;

    ll k=0, m=n-1;
    while (!(m&1)){
        m >>= 1;
        k++;
    }
    
    vector<int> checkSet = {2, 3, 5, 7};
    for (auto a  : checkSet){
        if (!test(a,n,k,m)) return false;
    }
    
    return true;
}
int main()
{
    int n; cin >> n;
    int cnt=0, id;
    ll max_prime=0;
    for (int i=1;i<=n;i++){
        ll a; cin >> a;
        if (RabinMiller(a)){
            cnt++;
            if (max_prime < a){
                max_prime = a;
                id = i;
            }
        }
    }
    if (cnt==0) cout << "khong co";
    else cout << cnt << " " << max_prime << " " << id;
    return 0;
}

Bài 2. Từ và Xâu đối xứng

Từ là một xâu khác rỗng chỉ gồm các chữ cái. Xâu đối xứng là xâu đọc từ trái sang phải cũng như đọc từ phải sang trái. Cho xâu kí tự $S$ khác rỗng, độ dài không quá $255$, chỉ chứa các chữ cái tiếng Anh viết thường và các dấu cách.

Yêu cầu

Hãy viết hoa chữ cái đầu tiên của tất cả các từ trong xâu $S$ đã cho và chỉ ra các từ là xâu đối xứng trong xâu $S$ ban đầu và số lượng các từ đó.

Dữ liệu

Tệp văn bản WORD.INP gồm 1 dòng chứa xâu $S$.

Kết quả

Ghi ra tệp văn bản WORD.OUT gồm 2 dòng:

• Dòng thứ 1 là xâu $S$ đã viết hoa chữ cái đầu tiên của tất cả các từ trong $S$.
• Dòng thứ 2 chứa các từ (là xâu đối xứng) có trong xâu $S$ ban đầu và số lượng các từ là xâu đối xứng (cách nhau bởi dấu cách), hoặc ghi $khong \ co$ (nếu không có từ nào là xâu đối xứng).

Ví dụ

Lời giải

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl '\n'
bool dx(string s){
    int l=0, r=s.size()-1;
    while (l<=r){
        if (s[l++] != s[r--]) return false;
    }
    return true;
}
int main()
{
    string s;
    getline(cin, s);
    s += ' ';
    int n = s.size();
    vector<string> cs;    
    for (int i=0;i<n;i++){
        if (s[i]==' '){
            cout << s[i]; continue;
        }
        string tmp = "";
        for (int j=i;j<n;j++){
            if (s[j]==' '){
                cs.push_back(tmp);
                if ('a' <= tmp[0] && tmp[0] <= 'z') tmp[0] -= 32;
                cout << tmp;
                i=j-1;
                break;
            }
            else tmp += s[j];
        }
    }
    cout << nl;
    int cnt = 0;
    for (auto i : cs){
        if (dx(i)){
            cout << i << " ";
            cnt++; 
        }
    }
    if (cnt!=0) cout << cnt;
    else cout << "khong co";
    return 0;
}

Bài 3. Lồng thùng

Sau khi xuất vật liệu, trong một kho có $N$ thùng hàng rỗng hình hộp chữ nhật, đánh số từ $1$ đến $N \ (1 < N \le 100)$.

$N$ thùng này sắp thành một hàng từ trái sang phải theo thứ tự sử dụng, thùng có chỉ số lớn được sử dụng trước thùng có chỉ số nhỏ. Thùng thứ $i$ có chiều dài, chiều rộng và chiều cao tương ứng là $l_i,w_i,h_i$.

Vì các thùng hàng đều rỗng nên chúng có thể lồng vào nhau được, chẳng hạn như thùng hàng kích thước $1 \times 2 \times 3$ có thể để trong thùng hàng kích thước $1 \times 2 \times 4$ hay $4 \times 1 \times 2$ và như vậy sẽ tiết kiệm được diện tích của kho hàng. Tuy nhiên, để tiện lợi người ta sẽ không để thùng hàng sử dụng trước vào trong thùng hàng sử dụng sau dù có thể để được.

Để giải phóng chỗ, người chủ kho đã lồng các thùng vào nhau theo quy trình sau: lấy thùng thứ nhất trong dãy ra, tìm thùng gần nhất (chỉ số nhỏ nhất) có thể chứa được nó, bỏ thùng thứ nhất vào thùng đó. Tiếp tục làm như vậy với thùng hàng đã chứa thùng thứ nhất cho đến cuối dãy. Tiếp tục lặp lại quá trình đó từ trái sang phải, cho đến khi không thể lồng thêm thùng nào nữa thì thôi. Như vậy từ dãy $N$ thùng ban đầu, bây giờ chỉ còn có $M$ thùng chiếm chỗ.

Cho số nguyên dương $N$ và 3 dãy số tự nhiên $l_1,l_2,...,l_N, \ w_1,w_2,...,w_N, \ h_1,h_2,...,h_N$ trong đó $l_i,w_i,h_i$ tương ứng là kích thước của thùng rỗng thứ $i \ (1 \le i \le N)$ hiện có trong kho.

Yêu cầu

Hãy xác định số $M$ (số thùng còn chiếm chỗ trong kho sau khi lồng theo cách trên).

Dữ liệu

Vào từ tệp văn bản DONTHUNG.INP gồm 4 dòng:

• Dòng 1 chứa số nguyên dương $N$.
• Dòng 2 chứa $N$ số tự nhiên $l_1,l_2,...,l_N$.
• Dòng 3 chứa $N$ số tự nhiên $w_1,w_2,...,w_N$.
• Dòng 4 chứa $N$ số tự nhiên $h_1,h_2,...,h_N$.

Kết quả

Đưa ra tệp văn bản DONTHUNG.OUT chứa duy nhất một số $M$ (số thùng còn chiếm chỗ trong kho).

Ví dụ

Lời giải

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

int main()
{
    int n; cin >> n;
    ll box[n][3];
    bool marked[n];
    memset(marked, 0, sizeof(marked));

    for (int i=0;i<3;i++){
        for (int j=0;j<n;j++) cin >> box[j][i];
    }
    for (int i=0;i<n;i++) sort(box[i], box[i]+3);

    int ans = 0;
    for (int i=0;i<n;i++){
        if (marked[i]) continue;
        int l=i, r=l+1;
        while (r<n){
            if (box[l][0] <= box[r][0] &&
                box[l][1] <= box[r][1] &&
                box[l][2] <= box[r][2] && !marked[r]){
                marked[l] = marked[r] = 1;
                l = r++;
            }
            else r++;
        }
        ans++;
    }
    cout << ans;
    return 0;
}