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

Author Hung Nguyen Tuong

Bài 1. Độ tuổi

Trong đợt tổng điều tra dân số vừa qua, Nam được tham gia với vai trò là tình nguyện viên. Nam được phân công điều tra dân số của khu 1 phường Bãi Cháy.

Công việc của Nam là đến từng hộ gia đình mà Nam đến sau đó ghi chép lại cẩn thận. Sau khi đến hết tất cả các gia đình trong khu, cuốn sổ ghi chép của Nam đã có đầy đủ thông tin cần thiết.

Nhiệm vụ của Nam bây giờ là thống kê xem độ tuổi nào trong khu là nhiều nhất. Bạn hãy giúp Nam thống kê độ tuổi nào trong khu là nhiều nhất.

Dữ liệu

Dữ liệu vào cho bởi file văn bản DOTUOI.INP có cấu trúc như sau:

• Dòng đầu tiên ghi tổng số người có trong khu $N \ (0 < N \le 40000)$.
• Dòng thứ 2 ghi tuổi của từng người trong khu $t \ (0 < t \le 120)$ cách nhau bằng một dấu cách (space).

Kết quả

Kết quả ghi ra file văn bản DOTUOI.OUT với 1 số là độ tuổi nhiều nhất trong khu. Dữ liệu vào luôn luôn đảm bảo có đúng 1 độ tuổi nhiều nhất trong khu.

Ví dụ

Lời giải

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

int main()
{
    int n, ans, c = 0;
    int cnt[121] = {0};
    cin >> n;
    for (int i=0;i<n;i++){
        int t; cin >> t;
        cnt[t]++;
        if (cnt[t] >= c){
            c = cnt[t];
            ans = t;
        }
    }
    cout << ans;
    return 0;
}

Bài 2. Số may mắn

Công viên $X$ có một điều rất đặc biệt là trên tường bao xung quanh công viên có 1 dãy các chữ số vô hạn được các công nhân xây dựng tạo nên. Đó là các thợ xây đã viết các số tự nhiên $1, 2, 3, 4,...$ liên tiếp nhau tạo thành 1 dãy các chữ số vô hạn. Ví dụ: $1234567891011121314151617181920...$

Nhân kỷ niệm 50 năm xây dựng, Ban điều hành công viên muốn tạo một ấn tượng nên đã nghĩ ra chương trình tặng quà đặc biệt cho các khách thăm quan. Khi khách mua vé thăm quan công viên thì số sê ri của tấm vé $(N)$ chính là căn cứ để khách thăm quan đó sẽ nhận được 1 con số may mắn để từ đó viết trên tường bao quanh của công viên. Bạn hãy giúp Ban điều hành công viên đưa ra con số may mắn của khách hàng thật nhanh.

Dữ liệu

Dữ liệu vào cho bởi file văn bản SOMM.INP có đúng 1 số $N$ là số sê ri của tấm vé thăm quan ($N$ nguyên dương và $N \le 10^6$).

Kết quả

Kết quả ghi ra file văn bản SOMM.OUT với 1 số là con số may mắn của khách thăm quan.

Ví dụ

Lời giải

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

vector<ull> ds(8, 0);

void init()
{
    ull nums = 9;
    for (int i = 1; i <= 7; i++)
    {
        ds[i] = nums * i + ds[i - 1];
        nums *= 10;
    }
}

int solve(ull N)
{
    if (N <= 9)
        return N;

    int k = lower_bound(ds.begin(), ds.end(), N) - ds.begin();
    ull remain = N - ds[k - 1];
    if (remain % k == 0)
        return (ull)(pow(10, k - 1) + remain / k - 1) % 10;
    else
    {
        ull num = pow(10, k - 1) + remain / k;
        for (int i = 0; i < k - remain % k; i++)
            num /= 10;
        return num % 10;
    }
}

int main()
{
    init();
    ull k;
    cin >> k;
    cout << solve(k);
    return 0;
}

Bài 3. Trồng cây

Trước đây những người xây dựng con đường vào khu phố $C$ thuộc phường Hồng Hải đã không trồng cây trên vỉa hè dọc con đường đó, mà họ cho lát toàn bộ gạch lá dừa (loại gạch hình vuông có các khía trên bề mặt giống lá dừa).

Nay chính quyền địa phương muốn trồng cây xanh dọc con đường dẫn vào khu phố $C$ nên đã lựa chọn vài loại cây vừa phù hợp với cảnh quan vừa cũng muốn tái sử dụng những viên gạch lá dừa phải dỡ đi để trồng cây vào đó. Khi một cây được trồng xuống thì người ta xây dựng một hàng gạch hình tròn bao quanh cây đó. Nếu một đường tròn có đường kính $2n-1$ đơn vị thì diện tích cần đặt nó là $2n \times 2n$, tâm đường tròn luôn nằm tại giao điểm của 2 đường chéo hình vuông $2n \times 2n$.

• Ví dụ: với $n=3$ ta có hình minh hoạ như dưới đây:

  

  Bạn hãy giúp chính quyền phường Hồng Hải xác định chính xác xem với mỗi loại cây trồng trên vỉa hè sẽ có bao nhiêu gạch lá dừa sẽ được tái sử dụng (những viên gạch nằm hoàn toàn trong hình tròn).

Dữ liệu

Dữ liệu vào cho bởi file văn bản TRONGCAY.INP có đúng 1 số nguyên $n \ (0<n<150)$.

Kết quả

Kết quả ghi ra file văn bản TRONGCAY.OUT với nội dung là số viên gạch lá dừa được tái sử dụng.

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;
    float r = (float)(n*2-1)/2;
    int ans = 0;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            float d = (float)sqrt(i*i + j*j);
            if (d <= r) ans++;
            else break;
        }
    }
    cout << ans*4;
    return 0;
}