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

Author Hung Nguyen Tuong

Bài 1. CONTAINER

Hãng vận tải hàng hoá nhận được đơn đặt hàng vận chuyển hai thùng hàng dễ vỡ. Để đảm bảo an toàn, hãng quyết định dùng container hiện có vận chuyển.

Các thùng hàng có hình khối hộp chữ nhật, với các chiều dài, rộng, cao tương ứng là $l_1,w_1,h_1$ và $l_2,w_2,h_2$. Container cũng có hình khối hộp chữ nhật kích thước $l_c,w_c,h_c$.

Các thùng hàng phải được xếp vào Container để có thể dễ dàng chèn chặt. Các thùng hàng được xoay theo trục đứng một góc là bội của $90 \degree$. Hai thùng hàng có thể để cạnh nhau hoặc nằm trước/sau, không được đè lên nhau. Đương nhiên, các thùng hàng phải nằm gọn trong Container.

Yêu cầu

Hãy xác định, có thể đóng các thùng hàng vào Container hay không.

Dữ liệu

Vào từ tệp văn bản CONTAINE.INP:

• Dòng thứ nhất chứa 3 số nguyên dương $l_1,w_1,h_1$.
• Dòng thứ hai chứa 3 số nguyên dương $l_2,w_2,h_2$.
• Dòng thứ ba chứa 3 số nguyên dương $l_c,w_c,h_c$.

Kết quả

Đưa ra file văn bản CONTAINE.OUT thông báo $YES$ hoặc $NO$.

Ví dụ

Lời giải

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl '\n'
ll l1,w1,h1;
ll l2,w2,h2;
ll lc,wc,hc;
bool check(ll l, ll w){
    return (l <= lc && w <= wc) || (l <= wc && w <= lc);
}
string solve(){
    cin>>l1>>w1>>h1>>l2>>w2>>h2>>lc>>wc>>hc;
    if (h1 > hc || h2 > hc) return "NO";
    if (check(l1+l2,max(w1,w2)) ||
        check(w1+w2,max(l1,l2)) ||
        check(l1+w2,max(l2,w1)) ||
        check(l2+w1,max(l1,w2))
    ) return "YES";
    return "NO";
}
int main()
{
    cout << solve();
    return 0;
}

Bài 2. Giải nén xâu GNEN

Trong máy tính, để tiết kiệm bộ nhớ, người ta thường tìm cách nén dữ liệu. Trong việc nén văn bản, ta sử dụng một phương pháp đơn giản được mô tả thông qua ví dụ sau:

Ví dụ:

• Với xâu kí tự $'aaabbbb'$ sẽ được nén lại thành xâu $'3a4b'$.
• Với xâu kí tự $'bbbbbk'$ sẽ được nén lại thành xâu $'5bk'$.

Cho một xâu kí tự $S_{t1}$ gồm các kí tự thuộc tập $'a'...'z'$.

Gọi $S_t$ là xâu nén của xâu $S_{t1}$ theo phương pháp được mô tả như trên.

Xâu $S_t$ gồm $N \ (1 \le N \le 255)$ kí tự thuộc tập các kí tự: $'a'...'z', \ '0'...'9'$.

Yêu cầu

Hãy giải nén xâu $S_t$ để được xâu gốc $S_{t1}$.

Dữ liệu

Vào từ file văn bản GNEN.INP gồm đúng một dòng chứa xâu kí tự $S_t$.

Kết quả

Đưa ra file GNEN.OUT gồm duy nhất một dòng chứa xâu $S_{t1}$ là xâu sau khi đã được giải nén.

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;
    for (int i=0;i<s.size();i++){
        if ('a' <= s[i] && s[i] <= 'z'){
            int j=i-1;
            string snum = "";
            while (j>=0 && '0' <= s[j] && s[j] <= '9'){
                snum += s[j--];
            }
            ll num = 0;
            if (snum=="") num=1;
            else{
                for (int j=snum.size()-1;j>=0;j--){
                    num = num*10 + (int)snum[j]-48;
                }
            }
            cout << string(num, s[i]);
        }
    }
    return 0;
}

Bài 3. Thu nhập gấp đôi

Một đơn vị thống kê trong khi điều tra về tổng thu nhập của các hộ dân (có thu nhập thấp) ở địa phương được giao phụ trách, kết quả được ghi lại dưới dạng một dãy số $A$ gồm $n \ (n \le 2500000)$ số nguyên dương $A_1,A_2,...,A_n \ (300 \le A_i \le 32000)$. Trong đó $A_i$ là tổng thu nhập của hộ thứ $i$.

Dựa vào kết quả dãy số này, đơn vị đó muốn biết số hộ có tổng thu nhập gấp đôi thu nhập của một hộ khác trong số $n$ hộ đã được điều tra.

Ví dụ: Với dãy $1000, 1050, 4000, 3100, 2000, 21070, 9000, 7060, 18000, 22500$ thì sẽ có 3 hộ như vậy.

Yêu cầu

Bạn hãy giúp đơn vị thống kê đó xác định số $s$ - số hộ có tổng thu nhập như vậy và số $m$ - tổng thu nhập thấp nhất so với tổng thu nhập của những hộ trong số các hộ này.

Dữ liệu

Vào từ file văn bản GAPDOI.INP:

• Dòng đầu tiên chứa số tự nhiên $n$.
• Dòng thứ $i$ trong $n$ dòng tiếp theo mỗi dòng chứa một số nguyên dương $A_i$.

Kết quả

Ghi ra file văn bản GAPDOI.OUT: gồm 2 số tự nhiên $s,m$ viết cách nhau trên một dòng (Trong đó $s$ là số hộ có tổng thu nhập gấp đôi tổng thu nhập của một hộ khác trong số những hộ được điều tra và $m$ là tổng thu nhập thấp nhất so với tổng nhu nhập của $s$ hộ này).

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;
    int a[n];
    bool marked[32005];

    for (int i=0;i<n;i++) cin >> a[i];

    memset(marked, 0, sizeof(marked));
    sort(a, a + n);
    
    int cnt = 0, mn = 1e9;

    for (int i=0;i<n;i++){
        if (!(a[i]&1) && marked[a[i]/2]){
            cnt++;
            mn = min(mn, a[i]);
        }
        marked[a[i]] = 1;
    }

    cout << cnt << " " << mn;
    return 0;
}