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

Author Hung Nguyen Tuong

Bài 1. Đa giác lồi

Nhà An có một mảnh đất rộng, nhưng lại không được vuông vắn nên việc xác định diện tích của mảnh đất thật khó khăn. Vì vậy An đã nghĩ ra cách quy về một bài toán, coi mảnh đất là một đa giác đặt trong hệ toạ độ Oxy. Tuy nhiên ngay cả khi biết được toạ độ các đỉnh của đa giác thì việc tính chính xác diện tích mảnh đất cũng không hề đơn giản.

Để nhanh chóng An đã nghĩ ra cách chỉ ước lượng diện tích mảnh đất đó bằng cách tính diện tích hình chữ nhật bao quanh đa giác lồi thoả mãn các điều kiện:

• Các cạnh song song với trục toạ độ.
• Chứa đa giác đã cho.
• Có diện tích nhỏ nhất.

Rõ ràng việc tính diện tích hình chữ nhật này thật sự dễ dàng và nó cũng phần nào giúp An đánh giá đươc diện tích mảnh đất nhà mình.

Yêu cầu

Cho số nguyên $N$ và các toạ độ đỉnh $(x_i,y_i)$ của một đa giác $N$ cạnh ($1 \le i \le N, \ x_i, y_i$ nhận giá trị thực), các đỉnh được liệt kê theo một chiều nào đó. Hãy tính $S$ - diện tích hình chữ nhật bao quanh.

Dữ liệu

Vào từ tệp POLYGON.INP:

• Dòng đầu tiên chứa số nguyên N $(1 \le N \le 40)$.
• Dòng thứ $i$ trong $N$ dòng tiếp theo chứa hai số thực $x_i, y_i$, các số cách nhau một dấu cách.

Kết quả

Đưa ra tệp văn bản POLYGON.OUT số thực $S$ với bốn chữ số sau dấu chấm thập phân.

Ví dụ

Lời giải

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl '\n'
#define inf 1e18
#define fi first
#define se second

int main()
{
    int n; cin >> n;
    pair<double, double> u_r = {-inf, -inf}, d_l = {inf, inf};
    for (int i=0;i<n;i++){
        double x, y; cin >> x >> y;
        u_r.fi = max(u_r.fi, x);
        u_r.se = max(u_r.se, y);

        d_l.fi = min(d_l.fi, x);
        d_l.se = min(d_l.se, y);
    }
    double ans = (u_r.fi - d_l.fi) * (u_r.se - d_l.se);
    cout << fixed << setprecision(4) << ans;
    return 0;
}

Bài 2. Đoạn con dài nhất

Cho dãy $N$ số nguyên $A_1,A_2,...,A_N$.

Yêu cầu

Tìm đoạn dài nhất các phần tử liên tiếp cùng chia hết cho một số nguyên $K$.

Dữ liệu

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

• Dòng đầu tiên chứa hai số nguyên $N,K \ (1 \le N \le 10000, \ k \neq 1)$.
• Dòng thứ 2 chứa $N$ số nguyên $A_1,A_2,...,A_N$ các số cách nhau một dấu cách.

Kết quả

Đưa ra tệp văn bản SUBSEQ.OUT một số nguyên xác định độ dài đoạn lớn nhất 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()
{
    int n; cin >> n;
    ll k; cin >> k;
    int ans = -1, cur = 0;

    for (int i=0;i<n;i++){
        ll a; cin >> a;

        if (a%k==0) cur++;
        else cur = 0;

        ans = max(ans, cur);
    }
    cout << ans;
    return 0;
}

Bài 3. Kim tự tháp số

Kim tự tháp số có dạng như hình vẽ. Mỗi ô của kim tự tháp được điền một số tự nhiên. Quy tắc điền số là điền lần lượt các số tự nhiên bắt đầu từ 1 vào các dòng. Điền hết dòng một rồi tới dòng hai và cứ tiếp tục như vậy… Nếu ở dòng lẻ, điền các số từ phải sang trái. Nếu ở dòng chẵn, điền các số từ trái sang phải.

Yêu cầu

1. Cho một số tự nhiên $N$. Hãy cho biết ô chứa số $N$ nằm ở dòng nào trong kim tự tháp và nằm ở ô thứ mấy (tính từ trái sang phải) của dòng đó.
2. Cho hai số tự nhiên $R, C$. Hãy cho biết ô thứ $C$ (tính từ trái sang phải) của dòng thứ $R$ chứa số tự nhiên nào.

Dữ liệu

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

• Dòng đầu tiên chứa hai số nguyên $N$.
• Dòng thứ hai chứa hai số tự nhiên $R, C \ (1 \le N, R \le 10^9, \ 1 \le C \le 2R)$.

Kết quả

Đưa ra tệp văn bản PYRAMID.OUT gồm hai dòng:

• Dòng đầu tiên ghi đáp số câu hỏi 1.
• Dòng thứ hai ghi đáp số câu hỏi 2.

Ví dụ

Lời giải

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

int main()
{
    ll n, r, c;
    cin >> n >> r >> c;
    
    vector<ll> start = {1};
    ll d = 1;
    while (start.back() <= 1e9+1){
        ll next = start.back() + d;
        start.push_back(next);
        d+=2;
    }

    int i = upper_bound(start.begin(), start.end(), n)-start.begin();
    cout << i << " ";
    if (i%2==0) cout << n - start[i-1] + 1;
    else cout << start[i] - n;

    cout << nl;

    if (r%2==0) cout << start[r-1] + c - 1;
    else cout << start[r] - c;

    return 0;
}