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

Author Hung Nguyen Tuong

Bài 1. Tổng các số

Yêu cầu

Bạn hãy viết chương trình tính tổng các số nguyên dương nằm trong đoạn $[a;b]$ và chia hết cho số nguyên dương $k$ cho trước.

Dữ liệu

Từ tệp tongso.inp gồm một dòng ghi ba số nguyên dương $a,b,k$ viết cách nhau.

Kết quả

Ghi vào tệp tongso.out một số nguyên dương là tổng các số nằm trong đoạn $[a;b]$ và chia hết cho $k$.

Ví dụ

Ràng buộc

• $50\%$ số test ứng với $50\%$ số điểm của bài có $a < b \le 10^3; \ k \ge 50$.
• $30\%$ số test ứng với $30\%$ số điểm của bài có $a < b \le 10^7; \ k \ge 10^5$.
• $20\%$ số test ứng với $20\%$ số điểm của bài có $a < b \le 10^9; \ k \ge 10^7$.

Lời giải

Giả sử tổng các số trong đoạn $[a,b]$ mà chia hết cho $k$ là:

Ta thấy $x_1,x_2,x_3,\ldots,x_n$ là các số chia hết cho $k$ kề nhau, vậy $\frac{x_1}{k}, \frac{x_2}{k}, \frac{x_3}{k}, \cdots, \frac{x_n}{k}$ sẽ là các số tự nhiên liên tiếp.

Ta áp dụng công thức tổng các số tự nhiên từ $L \to R$:

Độ phức tạp: $O(1)$.

Code

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

int main()
{
    ll a, b, k; cin >> a >> b >> k;
    a = (a + (a%k!=0)*k)/k;
    b /= k;
    ll ans = k * (b-a+1) * (a+b) / 2;
    cout << ans;
    return 0;
}

Bài 2. Xâu kí tự

Cho xâu $S$ gồm các kí tự là chữ số (từ $0$ đến $9$) viết liền nhau. Ta biến đổi xâu $S$ bằng việc chuyển kí tự đầu tiên của nó xuống vị trí cuối cùng, cứ tiếp tục làm như vậy cho đến kí tự cuối cùng.

Ví dụ: nếu $S='345679'$ thì:

• Lần thứ nhất ta được $S_1='456793'$.

• Lần thứ hai ta được $S_2='567934'$.

• Lần thứ ba ta được $S_3='679345'$.

  …

• Lần thứ sáu ta được $S_6='345679'$ và kết thúc.

Yêu cầu

Hãy viết chương trình cho biết khi kết thúc quá trình biến đổi như trên thì có tất cả bao nhiêu xâu đối xứng được tạo ra.

Xâu được gọi là đối xứng nếu đọc nó từ phải sang trái cũng thu được kết quả giống như đọc từ trái sang phải.

Dữ liệu

Từ tệp demxau.inp gồm một dòng chứa xâu $S$.

Kết quả

Ghi vào tệp demxau.out một số tự nhiên là số xâu đối xứng có được khi biến đổi $S$.

Ví dụ

Ràng buộc

• Có $40\%$ số test tương ứng với $40\%$ số điểm của bài với xâu $S$ có độ dài tối đa $255$ kí tự.
• Có $40\%$ số test tương ứng với $40\%$ số điểm của bài với xâu $S$ có độ dài tối đa $500$ kí tự.
• Có $20\%$ số test tương ứng với $20\%$ số điểm của bài với xâu $S$ có độ dài tối đa $10000$ kí tự.

Lời giải

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl '\n'
string s;
bool palindrome(int l, int r){
    while (l <= r){
        if (s[l] != s[r]) return false;
        l++; r--;
    }
    return true;
}
int main()
{
    cin >> s;
    int n = s.size(), ans = 0;
    for (int i=0;i<n;i++){
        if (palindrome(i, i + n - 1)) ans++;
        s += s[i];
    }
    cout << ans;
    return 0;
}

Bài 3. Số may mắn

Tại một cửa hàng thời trang, nhận dịp ngày Phụ nữ Việt Nam - 20/10, cửa hàng tặng cho mỗi khách hàng một phiếu dự thưởng khi mua hàng.

Khách hàng sau khi có phiếu dự thưởng điền đẩy đủ họ tên và Mã số dự thưởng rồi bỏ vào hòm phiếu dự thưởng.

Mã số dự thưởng là một số nguyên từ $1$ đến $1000$ được khách hàng tuỳ ý lựa chọn. Các phiếu dự thưởng được đánh số từ $1$ đến $N$.

Cửa hàng muốn tìm số may mắn để trao thưởng cho khách hàng. Số may mắn là Mã số dự thưởng mà có ít khách hàng lựa chọn nhất.

Yêu cầu

Hãy viết chương trình giúp chủ cửa hàng trên tìm ra số may mắn. Trong trường hợp có nhiều số may mắn thì tìm tất cả các số đó.

Dữ liệu

Từ tệp somayman.inp gồm hai dòng:

• Dòng thứ nhất chứa số nguyên $N \ (1 \le N \le 10^6)$ là số phiếu dự phòng.
• Dòng thứ hai chứa $N$ số nguyên $a_1,a_2,...,a_N \ (1 \le a_i \le 10^3, \ 1 \le i \le N)$ viết cách nhau. Trong đó, $a_i$ là mã số dự phòng của khách hàng thứ $i$.

Kết quả

Ghi vào tệp somayman.out các số may mắn tìm được, mỗi số viết trên một dòng theo thứ tự từ nhỏ đến lớn.

Ví dụ

Ràng buộc

• Có $40\%$ số test ứng với $40\%$ số điểm của bài có $N \le 10^3$ và dãy các số $a_i$ không giảm.
• Có $30\%$ số test ứng với $30\%$ số điểm của bài có $N \le 10^3$ và dãy các số $a_i$ bất kì.
• Có $30\%$ số test ứng với $30\%$ số điểm của bài có $N \le 10^6$ và dãy các số $a_i$ bất kì.

Lời giải

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

int main()
{
    int n; cin >> n;
    map<int,int> mp;
    for (int i=0;i<n;i++){
        int a; cin >> a;
        mp[a]++;
    }
    int freq = n+1;
    for (auto i : mp) freq = min(freq, i.second);
    for (auto i : mp){
        if (i.second == freq) cout << i.first << nl;
    }
    return 0;
}