Đề thực hành số 1

BÀI 1: Lô tô

Mô tả bài toán

An đang tham gia một trò chơi do hội trại của trường tổ chức, được gọi là "Lô Tô". Trò chơi này khá giống với trò chơi lô tô truyền thống, nhưng có một vài thay đổi trong cách chơi và cấu trúc phiếu chơi.

Mỗi người chơi nhận một phiếu chơi có dạng hình vuông NxN, với mỗi ô tại hàng i từ trên xuống và cột j từ trái sang phải chứa số $A_{ij}$ . Những con số này nằm trong khoảng từ 1 đến 100 và không có hai ô nào trong phiếu có số giống nhau.

Sau đó, người dẫn quản trò sẽ lấy ngẫu nhiên trong một hộp kín ra lần lượt các K phiếu có chứa số $b_1$ , $b_2$ ,..., $b_k$ . Nếu phiếu lô tô chứa một số trong những số được lấy lên từ hộp, người chơi sẽ đánh dấu chúng trên phiếu của mình. Người chơi đầu tiên có một hàng, cột hoặc đường chéo gồm ba số đã đánh dấu trên phiếu sẽ là người chiến thắng và nhận được một phần quà rất giá trị.

Nhiệm vụ của bạn là giúp An xác định rằng cậu ấy có thể nhận được phần quà từ trò chơi này sau K lần lấy phiếu hay không?

Input:

1.Trong N dòng đầu tiên, dòng thứ i chứa n số nguyên $A_{i,1}$ , $A_{i,2}$ , $A_{i,3}$ ,..., $A_{i,n}$ . ( 1 ≤ N ≤ 10 ; 1 ≤ $A_{i,n}$ ≤ 100)
2.Dòng thứ N+1 chứa số nguyên $K$ ( 1 ≤ $K$ ≤ 10 ) là số lần lấy phiếu trong hộp kín.
3.K dòng tiếp theo, mỗi dòng là một số nguyên bi, là số trên phiếu ở lần lấy thứ i.

Output:

-Nếu An đạt được giải thưởng thì in ra "Yes", ngược lại in ra "No".

Ví dụ

Input:

Output:

Yes

Giải thích:

Testcase 1:
Có 1 đường chéo {84,89,7}.

Input:

4
84 97 66 56
79 89 11 99
61 59 7 36
25 6 19 18
6
89
7
87
79
84
30

Output:

No

Giải thíc:

Testcase 2:
Không có đường nào thỏa mãn

Hướng dẫn giải:

Dựa vào yêu cầu đề bài, ta dễ dàng hình dung được về nội dung của mảng 2 chiều và kiểm tra giá trị trong mảng.

Tạo một mảng b[k] chứa toàn bộ các số người dùng nhập vào.

Nếu có 3 số 101 nằm trên cùng 1 hàng ngang , đường chéo, đường dọc... thì ngươi chơi thắng trò lô tô

Cuối cùng kiểm tra lại A[i][j].

Kiểm tra bằng 4 cách:

Cách 1: Kiểm tra theo hàng ngang
Cách 2: Kiểm tra theo hàng dọc
Cách 3: Kiểm tra theo đường chéo \
Cách 4: kiểm tra theo đường chéo /

Code mẫu(C++)

#include <iostream>
#include <vector>
#define MAX 100
using namespace std;

bool checkWinConditon(int q){

    if(q!=101){
        return true;
    }
    return false;
}
bool solve(int N, int K, int A[][MAX], int B[]){
    

    for(int i=0;i<K;i++)
    {
        int z=B[i];
        for(int j=0;j<N;j++)
        {
            for(int k=0;k<N;k++)
            {
                if(A[j][k] == z)
                {
                    A[j][k] = 101;
                }
            }
        }
    }

    //Kiểm tra hàng ngang
    for(int i=0;i<N;i++)
    {
        bool q=false;
        for(int j=0;j<N;j++)
        {
            if(q!=checkWinConditon(A[i][j])) return false;
        }
    }
    
    //Kiểm tra hàng dọc
    for(int i=0;i<N;i++)
    {
        q=false;
        for(int j=0;j<N;j++)
        {
            if(q!=checkWinCondition(A[j][i])) return false; 
        }
    }

    //Kiểm tra đường chéo '\'
    bool ans = false;
    for(int i=0;i<N;i++)
    {   
        if(ans!=checkWinCondition(A[i][i])) return false;
    }
    //Kiểm tra đường chéo '/'
    for(int i=0;i<N;i++)
    {
      if(ans!=checkWinCondition(A[i][n-i-1])) return false;
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;

    cin >> N;

	int A[MAX][MAX];

	for(int i=0;i<N;i++)
    {
		for(int j=0;j<N;j++) cin >> A[i][j];
	}
    
	int K; cin >> K;

	int B[K];

	for(int i=0;i<K;i++) cin >> B[i];

	if(solve(N,K,A,B)){
        cout << "Yes";
    }
    else cout << "No";
    return 0;

}

Bài 2

Mô tả bài toán

Trong phim Avatar, các đảo nổi trên hành tinh Pandora có thể lơ lửng nhờ khoáng sản siêu dẫn Unobtanium kết hợp với từ trường mạnh.

Tuy nhiên, trên Trái Đất không tồn tại các điều kiện này, nên khi mất lực nâng, các đảo sẽ rơi thẳng xuống dưới do trọng lực và chồng lên nhau.

Ta mô phỏng hiện tượng này trên một mặt phẳng 2 chiều. Cho một ma trận nhị phân kích thước n×m gồm các số 0 và 1 biểu thị một khối đảo (đá) 0 biểu thị khoảng trống.Khi các đảo rơi xuống:

Mỗi cột hoạt động độc lập. Các khối 1 trong cùng một cột sẽ rơi xuống dưới cùng, giữ nguyên số lượng Thứ tự trong cột không quan trọng, chỉ cần tất cả 1 dồn xuống đáy cột

Viết chương trình mô phỏng trạng thái cuối cùng của ma trận sau khi toàn bộ các khối đảo rơi xuống dưới do trọng lực.

Input:

Dòng 1: Hai số nguyên $n$ , $m$ — số hàng và số cột (1 ≤ $n,m$ ≤ 10)
n dòng tiếp theo, mỗi dòng gồm m số (0 hoặc 1) mô tả trạng thái ban đầu

Output:

In ra ma trận n×m sau khi các khối đảo đã rơi xuống và chồng lên nhau

Ví dụ

Input:

Output:

Hướng dẫn giải:

Đề yêu cầu các hòn đảo nặng sẽ bị rơi dần. Ta chỉ cần kiểm tra từng cột từ trên xuống nếu ở chỗ nào có hòn đảo thì ta thực hiện duyệt từ cuối cột lên trước vị trí đang xét thì chỗ nào bằng 0 thì ta cho bằng 1 rồi vị trí đang kiểm tra cho bằng 0

Code mẫu (C++)

#include<iostream>
#define MAX 100
using namespace std;
void solve(int A[][MAX], int n, int m)
{
    for(int i=0;i<m;i++)
    {
        for(int j=0; j<n;j++){
            if(A[j][i] == 1 )
            {
                for(int k = n-1; k>j;k-- )
                {
                    if(A[k][i] == 0)
                    {
                        A[k][i]=1;
                        A[j][i]=0;
                    }
                }
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cout << A[i][j] << " ";
        }
        cout << endl;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m; cin >> n >> m;

    int A[MAX][MAX];

    for(int i=0;<n;i++)
    {
        for(int j=0;j<m;j++) cin >> A[i][j];
    }

    solve(A,n,m);
}

Bài 3: Hai cậu bé Sun and Moon.

Mô tả bài toán

Tại một ngôi làng, ở cổng ra vào của làng sẽ có 1 đội canh gác theo ca.

Trưởng làng hiện tại muốn phân chia công việc cho 2 đội, mỗi đội chỉ có 1 người để canh cổng trong vòng 1 tháng (30 ngày) may thay có người con quý tử tên là Sun đã pha trò tạt nước sơn lên tượng các cụ trưởng làng tiền nhiệm nên được đặc cách làm người số 1 và người còn lại là bạn thân của Moon. Cả hai sẽ là người canh gác số 2.

Cả hai bắt đầu làm việc từ ngày 1/4. Mỗi người sẽ có 1 ca làm việc và mỗi ngày cả hai phải chọn làm m và n ca:

-Người thứ nhất sẽ được chọn: k giờ làm và m ca.
-Người thứ hai sẽ được chọn: q giờ làm và n ca.

Vì cả hai còn nhỏ nên vào ban đêm từ khoảng 22h-6h sáng không phải làm và luôn bắt đầu ngày làm việc của mình vào lúc 7h (phải luôn đúng giờ).

Biết rằng nếu cả hai không làm đủ được thời gian yêu cầu làm việc là 1 tháng thì sẽ phải làm thêm miễn sao cộng lại số giờ đã làm là đủ 1 tháng.

Trong tháng 4 vào ngày 26/4 thì ở làng có lễ giỗ tổ để tưởng niệm và thể hiện lòng biết ơn đối với các vị trưởng làng đời trước đã sáng lập và phát triển ngôi làng. Vào ngày 30/4 thì lại là ngày quốc tế lao động của cả thế giới. Nên nếu Sun muốn đi chơi thì phải nhờ Moon đi canh và phải có ít nhất một người làm việc. Nghĩa là người được nhờ vẫn phải đi canh nhưng chỉ cần canh đúng số giờ làm mà mình phải nhận. Hôm 30/4 Sun có nghĩa vụ phải đi làm lễ ở dòng họ nên được đặc quyền nghỉ(dòng họ của Sun là dòng họ sáng lập ra ngôi làng này) Moon bắt buộc phải làm thay vào 30/4 và Sun sẽ làm thay cho Moon vào ngày khác trước khi hết thời hạn 1 tháng.

Yêu cầu: Tìm ngày mà Sun và Moon kết thúc hình phạt của trưởng làng.

Lưu ý:

Mỗi ngày tổng số giờ cả hai làm chỉ tối đa 15 tiếng có thể ít hơn.
Tính từ tháng 4 cho tới tháng cuối tháng 12 thì làng chỉ có đúng 1 đợt lễ đó là 26/4 và 30/4.
Lịch ở làng là lịch ở Trái Đất.

Input:

Dòng 1 là k giờ làm của Sun (2 ≤ k ≤ 8, 1 ≤ m ≤ 8)
Dòng 2 là q giờ là Moon (2 ≤ q ≤ 8, 1 ≤ n ≤ 8)
Dòng 3,4,5,6 là các câu hỏi để biết xem Sun hoặc Moon có nghỉ làm hay không.

Output:

Ngày hết án phạt.

Ví dụ

Input:

2 3
5 1
Sun co nghi vao 26/4  khong?:Co
Sun co nghi vao 30/4 khong?:Co
Moon co nghi vao 26/4 khong?:Khong
Moon co nghi vao 30/4 khong?:Khong

Output:

6/6

Giải thích:

Cả hai sẽ đi làm như bình thường từ 1/4 đến 25/4 nhưng mà và0 26/4 Sun đòi nghỉ, Moon đi làm mà Moon chỉ làm 5 tiếng vào đúng 1 ca nên hôm đó chỉ được 5 tiếng tương tự với 30/4. Từ đó về sau cứ mỗi ngày 11 tiếng của cả hai cộng dồn thì tới 6/6 mới đủ giờ làm.

Code mẫu (C++)

#include <iostream>
#define MAX 100
using namespace std;
int checkMonth(int n)
{
    if (n == 5 || n == 8 || n == 7 || n == 10 || n == 12) return 31;
    return 30;
}
int solve(int k, int m, int q, int n)
{
    int days = 720 - (k * m + q * n) * 28; // Chắc chắn phải làm hơn 30 ngày vì mỗi ngày làm cùng lắm 15 tiếng nên 15*28 < 720;

    string answers[4];
    cin.ignore();
    cout << "Sun co nghi vao 26/4  khong?:";
    getline(cin, answers[0]);

    cout << "Sun co nghi vao 30/4  khong?:";
    getline(cin, answers[1]);

    cout << "Moon co nghi vao 26/4  khong?:";
    getline(cin, answers[2]);

    cout << "Moon co nghi vao 30/4  khong?:";
    getline(cin, answers[3]);
    if (answers[0] == "Khong" && answers[1] == "Co" && answers[2] == "Khong" && answers[3] == "Khong")
    {
        days -= ((q * n + k * m) + q * n);
    }

    else if (answers[0] == "Co" && answers[1] == "Co" && answers[2] == "Khong" && answers[3] == "Khong")
    {
        days -= (2 * q * n);
    }

    else if (answers[0] == "Khong" && answers[1] == "Co" && answers[2] == "Co" && answers[3] == "Khong")
    {
        days -= (k * m + q * n);
    }
    // Kiểm tra cần làm bao nhiêu ngày thì xong
    int check = days / (k * m + q * n) + 1;
    int Month = 5;
    while (check > 0)
    {
        check -= checkMonth(Month);
        Month++;
    }
    check += checkMonth(--Month);
    cout << check << '/' << Month;
    return 0;
}
int main()
{
    int k, m;
    cin >> k >> m;

    int q, n;
    cin >> q >> n;

    solve(k, m, q, n);
}

Bài 4: Giao dịch

Mô tả bài toán

Thị trường giao dịch mã cổ phiếu X đang rất sôi động vì sự giao dịch của N cổ đông và M nhà đầu tư. Người chơi trong thị trường này đều có thể tự do đưa ra mức giá riêng mà họ cảm thấy thoải mái để mua hoặc bán. Mỗi cổ đông, với kỹ năng và phân tích của mình, không sẵn lòng nhả cổ phiếu của mình với mức giá dưới $a_i$ đô la. Trong khi đó, mỗi nhà đầu tư, với sự đánh giá và phân tích thị trường của mình, chỉ sẵn lòng mua cổ phiếu với mức giá không vượt quá $b_i$ đô la.

Giả sử bạn là một chuyên gia phân tích tài chính, bạn cần xác định mức giá cổ phiếu tối thiểu X (trong đó $X$ là số nguyên), sao cho số cổ đông có thể bán cổ phiếu với mức giá X đô la không nhỏ hơn số nhà đầu tư sẵn lòng mua cổ phiếu với mức giá X đô la. Mục tiêu của việc này là tạo ra một sự cân bằng giữa cung và cầu trên thị trường cổ phiếu, với hy vọng tối ưu hóa lợi ích kinh tế cho tất cả các bên tham gia thị trường.

Input:

Dòng đầu tiên chứa hai số nguyên $N$ , $M$ (1 $\le$ $N$ , $M$ $\le$ 2x $10^5$ ) là số lượng cổ đông và số lượng nhà đầu tư.
Dòng tiếp theo chứa N số $a_1$ , $a_2$ ,..,, $a_N$ với $a_i$ (1≤ $a_i$ ≤ $10^9$ ) là mức giá tối thiểu của cổ đông thứ $i$ .
Dòng cuối cùng chứa M số $b_1$ , $b_2$ ,..,, $b_N$ với $b_i$ (1≤ $b_i$ ≤ $10^9$ ) là mức giá tối đa mà nhà đầu tư $i$ có thể mua.

Output:

In ra mức giá cổ phiếu tối thiểu để cân bằng sự cung cầu của thị trường

Ví dụ

Input:

4
90 120
80 120 100000

Output:

Giải thích:

110 có 2 người mua và 2 người bán.

120 có 3 người mua và 1 người bán.

Tối thiểu thì chọn 110.

Code mẫu (C++)

#include<iostream>
using namespace std;
void solve(int a[], int b[], int n, int m)
{
    int i=0;

    int value=1e9;

    while(i<n)
    {
        int check=a[i];

        int seller=0;

        int customer=0;

        for(int i=0;i<n;i++)
        {
            if(a[i] <= check) seller++;
        }

        for(int i=0;i<m;i++)
        {
            if(b[i] >= check) customer++;
        }

        if(seller>=customer && check < value)
        {
           value = check;
        }

        i++;
    }

    cout << value << endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n,m;

    cin >> n >> m;

    int a[n];

    int b[m];

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

    for(int i=0;i<m;i++) cin >> b[i];
    
    solve(a,b,n,m);
    
    system("pause");
}

Bài 5

Mô tả bài toán

Câu lạc bộ Manchester United chuẩn bị tham gia C1 (Champion League) vào mùa sau để có thêm lợi thế trong việc thi đấu và giữ thể lực cho các cầu thủ họ đã chuẩn bị một số tiền là $N$ để chồng tiền mua các cầu thủ.

Họ mong muốn mua các cầu thủ ở các vị trí CM, CDM và LW (không bắt buộc phải mua đủ cả 3 vị trí). Họ đã có cho mình list danh sách các thủ đề mua. Nhưng cuộc sống không bao giờ dễ dàng khi họ muốn mua các cầu thủ mình muốn thì phải cạnh tranh với ManCity, Barcelona và Inter Milan. Điều là gã khổng lồ ở thế giới bóng đá. Thế nên để tự tin mình sẽ mua được cầu thủ mình muốn thì họ sẽ phải chồng thêm tiền. Nhưng nếu tổng số tiền họ chi ra quá lớn so với số tiền họ chuẩn bị thì sẽ bị xem là Tax United. Và dĩ nhiên sẽ bị gõ đầu bởi FIFA nếu số tiền tiêu quá 300 triệu. Do mùa trước họ đá rất dở nên bị giới hạn xài tối đa 300 triệu.

Danh sách cầu thủ đã chuẩn bị sẵn.

Các cầu thủ dưới đây chỉ là tin đồn về danh sách các cầu thủ Manchester United muốn mua (nghĩa là tin chưa chuẩn đâu nhé!)

Tier list S-A:

S= ${$

${$ Elliot Anderson, CDM $}$ Note: Có đội khác theo đuổi ~110 triệu
${$ Jude Bellingham, CM $}$ ~100 triệu
${$ Sandro Tonali, CDM $}$ ~80 triệu
${$ Vitinha, CM $}$ Note: Có đội khác theo đuổi ~90 triệu
${$ Kimmich, CDM $}$ ~50 triệu
${$ Khvicha Kvaratskhelia, LW $}$ Note: Có đội khác theo đuổi ~130 triệu
${$ Moises Caicedo $}$ Note: Có đội khác theo đuổi ~120 triệu

$}$

A= ${$

${$ Cody Gakpo, LW}$ ~ 60 triệu
${$ Adam Wharton, CDM $}$ Note: Có đội khác theo đuổi ~ 80 triệu
${$ Carlos Baleba, CDM $}$ Note: Có đội khác theo đuổi* ~ 100 triệu
${$ Iliman Ndiaye, LW $}$ ~ 50 triệu
${$ Kaoru Mitoma, LW $}$ Note: Có đội khác theo đuổi 40 triệu
${$ Adrien Rabiot $}$ ~65 triệu

$}$

Tier S nếu muốn mua thẳng thì bỏ thêm 30 triệu.

Tier A nếu muốn mua thẳng thì bỏ thêm 20 triệu.

Input:

Nhập số nguyên $N$ là số tiền mà câu lạc bộ muốn chi trong kỳ chuyển nhượng này (1 $\le$ $N$ $\le$ 300).
Nhập số nguyên K (1 $\le$ K $\le$ 13) là số cầu thủ muốn mua
Chọn các cầu thủ muốn mua.
Nếu đàm phán thành công theo thứ tự cầu thủ nhập vào thì chọn "Yes", ngược là thì "No". Nếu cầu thủ có đội khác theo dõi chọn "No" thì chắc chắn không mua được nếu không chịu bỏ thêm và mua được 100% nếu chịu chi. Đối với các cầu thủ không ai theo dõi thì không cần bỏ thêm.

Output:

In ra dòng chữ "Thành công" nếu mua được ít nhất 1 cầu thủ mình muốn nhưng số tiền chi ra không quá N.
Nếu mua được ít nhất 1 cầu thủ mình muốn nhưng quá số tiền N thì in ra "Tax United".
Nếu mua được ít nhất 1 cầu thủ mình muốn nhưng quá 300 triệu thì in ra "Ăn phạt"

Ví dụ

Input:

240
3
Elliot Anderson
Adam Wharton
Cody Gakpo
Yes Yes
Yes Yes
No

Output:

Thành công

iải thích:

Elliot Anderson giá gốc 110 có theo dõi và muốn mua thì phải bỏ thêm 30 triệu do ở tier S.

Tương tự, Adam Wharton nhưng ở tier A.

Tổng của hai cầu thủ trên là 240 triệu.

Từ chối Cody Gakpo.

Vậy thành công.

Code mẫu (C++)

#include <iostream>
#include <string>
#include <sstream>

using namespace std;

// Tạo cấu trúc để lưu thông tin 1 cầu thủ
struct Player {
    string name;
    string tier;
    int base_price;
    bool has_competitor;
};

int main() {
    // Tối ưu I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Dữ liệu tĩnh: Mảng chứa 13 cầu thủ
    Player db[13] = {
        {"Elliot Anderson", "S", 110, true},
        {"Jude Bellingham", "S", 100, false},
        {"Sandro Tonali", "S", 80, false},
        {"Vitinha", "S", 90, true},
        {"Kimmich", "S", 50, false},
        {"Khvicha Kvaratskhelia", "S", 130, true},
        {"Moises Caicedo", "S", 120, true},
        {"Cody Gakpo", "A", 60, false},
        {"Adam Wharton", "A", 80, true},
        {"Carlos Baleba", "A", 100, true},
        {"Iliman Ndiaye", "A", 50, false},
        {"Kaoru Mitoma", "A", 40, true},
        {"Adrien Rabiot", "A", 65, false}
    };

    int N, K;
    if (!(cin >> N >> K)) return 0;
    
    // Xóa bộ đệm trước khi dùng getline
    cin.ignore();
    
    // Mảng lưu tên K cầu thủ muốn mua ( K tối đa là 13)
    string chosen[1000];
    for (int i = 0; i < K; ++i) 
    {
        getline(cin, chosen[i]);
    }
    
    int total_cost = 0;
    int bought = 0;
    
    // Bắt đầu đọc kết quả đàm phán cho từng cầu thủ
    for (int i = 0; i < K; ++i) 
    {
        string target_name = chosen[i];

        string line;

        getline(cin, line); // Đọc dòng chữ "Yes No", "Yes", v.v.
        
        // 1. TÌM KIẾM CẦU THỦ TRONG MẢNG (Linear Search)
        int found_idx = -1;

        for (int j = 0; j < 13; ++j) 
        {
            if (db[j].name == target_name) 
            {
                found_idx = j;

                break; // Tìm thấy thì dừng vòng lặp tìm kiếm
            }
        }
        
        // Nếu không tìm thấy tên cầu thủ trong danh sách (phòng hờ)
        if (found_idx == -1) continue; 
        
        Player p = db[found_idx];
        
        // 2. XỬ LÝ KẾT QUẢ ĐÀM PHÁN
        stringstream ss(line);
        string nego, extra = "No";
        ss >> nego; // Lấy chữ Yes/No đầu tiên (Đàm phán)
        
        if (p.has_competitor) 
        {
            ss >> extra; // Lấy chữ Yes/No thứ hai (Chịu chi)
            if (extra == "Yes") 
            {
                int fee = (p.tier == "S") ? 30 : 20;

                total_cost += p.base_price + fee;

                bought++;
            } 
            else if (nego == "Yes") 
            {
                total_cost += p.base_price;
                bought++;
            }
        } 
        else 
        {
            if (nego == "Yes") 
            {
                total_cost += p.base_price;

                bought++;
            }
        }
    }
    
    // 3. IN KẾT QUẢ
    if (bought > 0) 
    {
        if (total_cost > 300) 
        {
            cout << "Ăn phạt\n";
        } 
        else if (total_cost > N) 
        {
            cout << "Tax United\n";
        } 
        else {
            cout << "Thành công\n";
        }
    }
    
    return 0;
}

Bài 6: Cắt bánh

Mô tả bài toán

Vào dịp sinh nhật, An được mẹ mua cho một chiếc bánh kem có kích thước rất lớn. An muốn chia bánh cho mọi người cùng ăn nhưng lại theo phương pháp cắt bánh "ABC” mà cậu ấy mới học được trên mạng.

Phương pháp “ABC” như sau:

Đầu tiên, lấy dao cắt 1 đường từ tâm bánh đến rìa vỏ bánh ở hướng 12 giờ.

Sau đó, thực hiện liên tiếp N thao tác:

Xoay bánh theo chiều kim đồng hồ X độ.

Lấy dao cắt 1 đường từ tâm bánh đến rìa bánh ở hướng 12 giờ.

Có tất cả N + 1 người tham dự vào sinh nhật của An (tính cả An) , vì thế An muốn chia chiếc bánh thành N + 1 bằng thực hiện liên tiếp N thao tác với mỗi lần xoay là Di độ.

An là nhân vật quan trọng trong buổi hôm nay nên cậu ấy muốn biết là sau quá trình cắt bánh này thì An có thể nhận phần bánh lớn nhất với góc bao nhiêu độ?

alt text

Input:

Dòng đầu tiên chứa số nguyên $N$ (1 $\le$ $N$ $\le$ 359) là số các thao tác.
Dòng tiếp theo chứa N số nguyên $D_{1}$ , $D_{2}$ , $D_{3}$ ,... $D_{n}$ (1 $\le$ $D_{i}$ $\le$ 359)

Output :

Một số nguyên là độ lớn của góc mà phần bánh lớn nhất An nhận được.

Lưu ý:

Các bộ test luôn đảm bảo các nhát cắt bánh là phân biệt

Ví dụ

Input:

4
90 180 45 195

Output:

Giải thích:

Nếu chỉ có 1 miếng thì rõ ràng miếng lớn nhất sẽ là góc được chọn hoặc là cái góc còn lại.

Ví dụ: Nếu cắt 1 miếng và chọn 1 độ, thì lớn nhất chính là 360-1. Ngược lại, nếu chọn 359 độ và cắt 1 miếng thì lớn nhất là 359. Kiểm tra thử 360-x (độ) lớn hơn x(độ) hay không nào lớn hơn thì chọn cái đó.

Đối trường hợp cắt lớn hơn 2 miếng ta cứ kiếm tra miếng gần nhất so với góc 12 giờ. Nghĩa là đo theo chiều kim đồng hồ.

Code mẫu (C++)

#include <iostream>
#include <math.h>
using namespace std;
void solve() {}
int main()
{
    int n;
    cin >> n;
    int D[n];
    for (int i = 0; i < n; i++)
    {
        cin >> D[i];
    }
    if (n == 1)
    {
        int k= 360-D[0] > D[0] ? 360 -D[0]:D[0];
        cout << k;
        system("pause");

    }
    int hold[n + 1];
    hold[0] = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j > 0; j--)
        {
            hold[j] = (D[i] + hold[j - 1]) % 360;
        }
    }
    int max = 360;
    for (int i = 0; i < n + 1; i++)
    {
        if (360 - hold[i] <= max)
        {
            max = 360 - hold[i];
        }
    }
    cout << max;
}

Giải thích ý tưởng:

$\bullet$ Ta biết rằng mỗi lần cắt thì sau đó ta sẽ quay góc.
$\bullet$ Tạo 1 mảng chứa các góc đề cho là D[n].
$\bullet$ Tạo 1 mảng chứa các vị trí mà đường cắt đang đứng, giá trị đó chính là độ sao với vị trí 12h lấy theo chiều kim đồng hồ.
Code của tôi sẽ được chay như dưới đây:

$\bullet$ Tôi cho hold[0]=0 tượng trưng cho vị trí 12h.

$\bullet$ Khi thực hiện xoay 90 độ thì đường cắt tiếp theo sẽ hold[1]=90.

$\bullet$ Tương tự cho đến khi hold[3] = 315, lúc này hold[4] sẽ không thể nào bằng 315+195=510 được vì nó nằm ngoài số đo đường tròn, đó là lí do ta thực hiện phép toán chia có dư, nghĩa là sau khi lấy số đo ở D[i] + hold[j-1] để tính vị trí của đường cắt lần lượt thì khi nó quá 360 ta hiển nhiên chia lấy dư cho 360 thì sẽ thu được vị trí của nó lúc này.

Sau đó thực hiện lần lượt đối với các đường cắt còn lại. Rõ ràng trước khi đưa ra đáp án ta sẽ cắt thêm lần nữa nghĩa là góc giữa đường đầu tiên so với 12h và đường gần nhất lúc này so với 12h sẽ là 1 miếng bánh chưa cắt và phải cắt thêm lần nữa. Nhưng nếu có nhiều hơn 1 lần quay thì nó dĩ nhiên bằng khoảng cách của 360 độ so với vị trí đường cuối. Sau đó in ra kết quả
Chạy tay: hold[0] =0 0;

i=1;

hold[1] = ${(}$ D[1]+hold[1-1] ${)}$ % 360; // hold[1] = ${(}$ 90 + hold[0] ${)}$ % 360

i=2;

hold[2] = ${(}$ D[2]+hold[2-1] ${)}$ % 360; // hold[1] = ${(}$ 180 + hold[1] ${)}$ % 360

hold[1] = ${(}$ D[2]+hold[1-1] ${)}$ % 360; // hold[1] = ${(}$ 180 + hold[0] ${)}$ % 360

i=3;

....;

Bài 7

Mô tả bài toán

Cho một đoạn thơ gồm có 4 dòng (Mỗi dòng tối đa 255 kí tự). Nhập vào một số nguyên dương $n$ ( $n$ > 0). Hãy in ra dòng thơ thứ n trong bài thơ. Nếu không có thì xuất ra màn hình "Dong khac”.

Ví dụ

Input:

Nam Quoc Son Ha Nam De Cu
Tiet Nhien Dinh Phan Tai Thien Thu
Nhu Ha Nghich Lo Lai Xam Pham
Nhu Dang Hanh Khang Thu Bai Hu 
3

Ouput:

Nhu Ha Nghich Lo Lai Xam Pham

Nam Quoc Son Ha Nam De Cu
Tiet Nhien Dinh Phan Tai Thien Thu
Nhu Ha Nghich Lo Lai Xam Pham
Nhu Dang Hanh Khang Thu Bai Hu 
5

Dong Khac

Code mẫu (C++)

#include<iostream>
#include<string.h>

using namespace std;
int main()
{
    string a[4];

    for(int i=0;i<4;i++)
    {
        getline(cin,a[i]);
    }

    int n; cin >> n;
    
    for(int i=0;i<4;i++)
    {
        if(i==n-1)
        {
            cout << a[i];
            return 0;
        }
    }

    cout << "Dong khac";

    return 0;
}

Bài 8

Mô tả bài toán

Căn cứ của tổ chức BHTCNPM có $n$ chiếc phi cơ chiến đấu (Boyer), mỗi Boyer được gán mỗi mã số nguyên nhập vào từ bàn phím. Để chuẩn bị cho chiến dịch CodeCity (tiến vào không gian meta field hỗ trợ cho Grin), các Boyer tuân theo qui luật bay theo ngày như sau:

-Boyer có mã chẵn thì chỉ được lưu thông vào ngày chẵn: 2,4,6,8,..30
-Boyer có mã lẻ thì chỉ được lưu thông vào ngày lẻ: 1,3,5,7,9,...31 tra

Hôm nay là một ngày đẹp trời, đội viên Kômn quyết đinh đi kiểm tra tình trạng lưu thông của các Boyer. Anh ấy phát hiện có một số Boyer bay sai ngày. Mỗi chiếc Boyer bay sai sẽ phải đóng một số tiền phạt là fine. Cho ngày anh ấy đi kiểm tra là date, hãy tính số tiền phạt anh ấy phải thu

Input:

Dòng 1: Số nguyên $n$ (1 $\le$ $n$ $\le$ 1e5)

Dòng 2: $n$ số nguyên - mã số của các Boyer bay vào ngày hôm nay.

Dòng 3: Số nguyên $date$ - ngày đi kiểm tra (1 $\le$ $date$ $\le$ 31)

Dòng 4: Số nguyên fine - tiền phạt cho mỗi chiếc Boyer vi pham

Output:

Tổng số tiền phạt phải thu

Ví dụ

Input:

5
12 7 9 20 15
2
100000

Output:

Code mẫu (C++)

int solve(int n, int a[], int dc,int fine)
{

    int cnt=0;
    for(int i=0;i<n;i++)
    {
        if(a[i] % 2 != dc % 2)
        {
            cnt++;
        }
    }

    int k = fine *cnt;

    return k;
}
int main()
{
    int n;

    cin >> n;

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

    int dc; cin >> dc;

    int fine; cin >> fine;
    
    cout << solve(n,a,dc,fine);
    
    return 0;

}

Bài 9: Trạm ga

Mô tả bài toán

Trong một quốc gia nhỏ có tên là XYZ, có bốn thành phố lớn. Những thành phố này được bố trí trên bản đồ theo cấu trúc một lưới 2x2, mỗi thành phố nằm ở một ô riêng. Thông qua hệ thống đường sắt, mỗi thành phố có thể kết nối với nhau. Mỗi thành phố, nếu được xây dựng trạm ga sẽ được đánh dấu trên bản đồ là ký tự "#", còn thành phố không có trạm ga thì sẽ được đánh dấu ký tự là ".".

Quốc gia nhỏ XYZ có tài chính còn eo hẹp nên chỉ xây dựng các tuyến đường sắt giữa hai thành phố có trạm ga và hai thành phố này phải kề nhau (chung cạnh trên bản đồ). Hai thành phố có trạm ga nhưng không kề nhau thì có thể di chuyển qua lại bằng cách di chuyển thông qua những thành phố trung gian khác.

Chính phủ XYZ đã xây dựng một số trạm ga ở trong một số thành phố (có ít nhất 2 thành phố có trạm ga), nhưng không biết là hai thành phố có trạm ga khác nhau có thể di chuyển qua lại với nhau được hay không.

Bạn hãy viết chương trình để kiểm tra thử xem là các thành phố có trạm ga có thể di chuyển qua lại được không nhé!

Input:

Dòng thứ nhất: Gồm 2 ký tự biểu diễn việc có trạm ga hay không ở hai thành phố góc trên bên trái và góc trên bên phải.

Dòng thứ hai: Gồm 2 ký tự biểu diễn việc có trạm ga hay không ở hai thành phố góc dưới bên trái và góc dưới bên phải.

Output:

In ra "Yes" nếu tất cả các trạm ga có thể di chuyển qua lại được.

In ra "No" nếu ngược lại.

Giải thích:

Giải thích có trên 3 trạm ở 2x2 thì đều có thể đi qua lại nhờ trung gian hoặc đi thẳng.

#include<iostream>

using namespace std;

int main(){
    char a[2][2]
    for(int i=0;i<2;i++)
    {
        for(int j=0;j<2;j++) cin >> a[i][j];
    }
    if(a[0][0] == '#' && a[1][1] == '#' && a[0][1] == '.' && a[1][0] == '.' || 
    a[0][1] == '#' && a[1][0] == '#' && a[0][0] == '.' && a[1][1] == '.'  ) 
    {
        cout << "No;
        return 0;
    }
    cout << "Yes";
    return 0;
}

Bài 10: Cặp khóa mã hóa

Mô tả bài toán

An đang làm việc trong một công ty lớn và có trách nhiệm bảo mật dữ liệu quan trọng của công ty. Để đảm bảo an toàn cho dữ liệu cho công ty, An đã tham gia nhóm phát triển hệ thống mã hóa bất đối xứng với việc tạo cặp khóa mã hóa dựa trên những số “đặc biệt” mà nhóm của An mới tìm ra. Số “đặc biệt” là một số nguyên dương không thể chia hết cho bình phương của bất kỳ số nguyên nào lớn hơn 1. Sự phức tạp của những số “đặc biệt” này rất thích hợp cho việc tạo ra những khóa mã hóa mạnh.

Bây giờ, nhóm của An muốn biết có bao nhiêu cặp khóa mã hóa mạnh với mỗi khóa nằm trong khoảng số nguyên nhất định từ L đến R. Một cặp khóa mã hóa (x, y) được xem là mạnh nếu cả khóa x, khóa y và giá trị x*y đều là những số “đặc biệt”, thêm vào đó thì x phải luôn nhỏ hơn y. An chịu trách nhiệm chính cho việc viết chương trình để tính số cặp khóa mạnh này nhưng khổ nỗi là cậu ấy đã quên gần hết việc lập trình. Bạn hãy giúp An viết chương trình này nhé!

Input:

Một dòng chứa hai số nguyên dương $L$ và $R$ ( $1 \le$ L $<$ R $\le 10^9,$ R $-$ L $\le 1000$ ) là 2 giới hạn của khoảng giá trị của các khóa mã hóa.

Output:

Số cặp khóa mã hóa mạnh mà nhóm An muốn biết.

Ví dụ

Input:

3
9

Output:

Giải thích:

Với L = 3, R = 9: Thì có 5 cặp khóa mã hóa là (3, 5), (3, 7), (5, 6), (5, 7), (6, 7).

Code mẫu (C++)

#include <iostream>
using namespace std;
bool gcd_(int n, int m)
{
    int r = 0;
    while (n)
    {
        r = m % n;
        m = n;
        n = r;
    }
    return m == 1;
}

bool check_prime(int n)
{
    if(n==2) return true;
    for (int i = 2; i*i< n; i++)
    {
        if (n % (i*i) == 0)
            return false;
    }
    return n > 1;
}
int main()
{
    int l, r;

    cin >> l >> r;

    int cnt = 0;

    while (l < r)
    {
            for (int i = l; i <= r; i++)
            {
                if (gcd_(i, l) && check_prime(i*l))
                    cnt++;
            }
        l++;
    }
    cout << cnt;
}

Bài 11: Trúng Tuyển

Mô tả bài toán

An mới nhận tin trúng tuyển vào UIT năm nay nhưng niềm đam mê thuật toán của cậu ấy rất lớn. Vì vậy, An quyết tâm luyện thuật toán để tham dự vào đội tuyển ICPC của trường. Qua tìm hiểu để đạt được một trình độ cao về thuật toán thì An phải học ít nhất là M thuật toán. Vì An là sinh viên mới bắt đầu trên con đường thuật toán nên độ hiểu biết về mỗi thuật toán trong M thuật toán cần học của An là 0 (zero).

Để tăng kiến thức thì An quyết định vào thư viện của trường để tìm những cuốn sách có các thuật toán này. An đã chọn ra được N cuốn sách, trong mỗi cuốn sách đều có M thuật toán và nếu An đọc thuật toán j trong cuốn sách thứ i thì độ hiểu biết về thuật toán j sẽ tăng lên là $H_{i,j}$ . Hơn nữa, để thuê cuốn sách thứ i thì phải An trả tiền giá thuê sách là $C_i$ .

Do thời gian ôn luyện có hạn nên để đạt đi mục tiêu thi của mình thì An muốn độ hiểu biết của mình cho mỗi thuật toán trong M thuật toán đều ít nhất là K. Vì chưa có nhiều điều kiện nên An mong muốn số tiền thuê sách là ít nhất nhưng vẫn đạt mục tiêu đề ra.

Bạn hãy giúp An giải quyết vấn đề nan giải này nhé!

Input:

Dòng đầu tiên gồm 3 số nguyên N, M, K ( $1 \le N, M \le 12$ , $1 \le K \le 10^5$ ) là số lượng sách mà An đã chọn, số lượng thuật toán An cần học và độ hiểu biết tối thiểu của mỗi thuật toán.

Trong N dòng tiếp theo, dòng thứ i + 1 chứa M + 1 số nguyên, số đầu tiên là giá tiền để thuê quyển sách thứ i là $C_i$ ( $1 \le C_i \le 10^5$ ) và M số $H_{i,1}, H_{i,2}, \dots, H_{i,M}$ ( $0 \le H_{i,j} \le 10^5$ ) là độ hiểu biết khi đọc thuật toán j trong quyển sách thứ i.

Output:

In ra số tiền thuê sách ít nhất mà an mong muốn, nếu không thể thực hiện được thì in ra -1.

Ví dụ

Input:

Output:

Code mẫu (C++)

#include <iostream>

using namespace std;

int solve(int N, int M, int K, int a[][13])
{

    int cnt[144] = {0};

    int check = 0;

    long long ans = 1e9;

    for (int i = 0; i < N - 1; i++)
    {
        for (int j = i + 1; j < N; j++)
        {
            bool c = false;
            for (int k = 1; k <= M; k++)
            {
                if (a[i][k] + a[j][k] < K)
                {
                    c = true;
                    break;
                    ;
                }
            }
            if (!c)
            {
                cnt[check] = a[i][0] + a[j][0];
                check++;
            }
        }
    }
    if (check == 1)
    {
        ans = cnt[0];
        cout << ans;
        return 0;
    }

    else
    {
        for (int i = 0; cnt[i] != 0; i++)
        {
            if (cnt[i] < ans)
                ans = cnt[i];
        }
    }
    cout << ans;
    return 0;
}

int main()
{
    int N, M, K;

    cin >> N >> M >> K;

    int m = M + 1;

    int a[100][13];

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j <= M; j++)
        {
            cin >> a[i][j];
        }
    }

    solve(N, M, K, a);

    return 0;
}

Bài 12: Mua quà

Mô tả bài toán

Nhân dịp ngày 20/11, ba bạn Hà, Ý, Dương được lớp trưởng phân đi đến cửa hàng lưu niệm để mua quà để tặng thầy/cô, mỗi người phải mua một món quà. Trong cửa hàng có $N$ món quà được sắp theo thứ tự trên kệ từ vị trí 1 đến vị trí $N$ . Món quà ở vị trí thứ $i$ có mã món quà là $a_{i}$ . Vì không muốn bị “đụng hàng” nên ba bạn Hà, Ý, Dương sẽ chọn ra ba món (mỗi người một món) quà khác nhau (hai món quà được xem là khác nhau khi nó có mã khác nhau), hơn nữa, thứ tự chọn quà của ba bạn cũng có chút đặc biệt : vị trí món quà của Hà chọn phải nhỏ hơn vị trí món quà của Ý và vị trí món quà của Ý chọn cũng sẽ nhỏ hơn vị trí món quà của Dương.

Ví dụ: Cửa hàng có 4 món quà có các mã lần lượt là [3, 1, 4, 1]. Nếu Hà chọn món quà ở vị trí 2, Ý chọn món quà ở vị trí 1 và Dương chọn món quà ở vị trí 3 mặc dù là các mã món quà khác nhau nhưng thứ tự chọn quà của Hà, Ý, Dương lại không thỏa mãn nên lần chọn như vậy sẽ không hợp lệ.

Bạn hãy đếm thử Hà, Ý, Dương cần thử tất cả bao nhiêu cách để chọn quà cho thầy/cô.

Input:

Dòng đầu tiên chứa số nguyên $N$ $(3 \le$ N $\le 2 \times 10^{5})$ là số lượng món quà có trong cửa hàng.
Dòng thứ 2 chứa $N$ số nguyên là $a_1, a_2, \dots, a_N$ $(1 \le a_i \le 2 \times 10^{5})$ là mã của các món quà.

Output:

Đưa ra số lượng cách chọn quà của Hà, Ý, Dương.

Ví dụ

Input:

4
3 1 4 1

Output:

#include <iostream>

using namespace std;
#define MAX 200001
int solve(int n, int a[], int ans)
{
    long long check[MAX] = {0};

    int cnt = 0;

    for (int i = 0; i < n; i++)
    {
        check[a[i]] += 1;
    }
    for(int i=0;i<MAX;i++)
    {
        if(check[i]!=0) cnt++;
    }
    for (int i = 0; i < n; i++)
    {
        int k = check[a[i]];
        if (k >= 3)
        {
            ans = ans - k * (k - 1) * (k - 2) / 6  - (cnt-1)*(k*(k-1)/2);

            check[a[i]]=0;
        }
        else if (k == 2)
        {
            ans = ans - (cnt-1);

            check[a[i]] = 0;
        }
    }

    cout << ans;
    return 0;
}

int main()
{
    int n;

    cin >> n;

    int a[n];

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

    int ans = n * (n - 1) * (n - 2) / 6;

    solve(n, a, ans);
    return 0;
}

Giải thích thuật toán:

Vì ta muốn Hà Ý Dương được xếp theo thứ tự nên ta sẽ chọn công thức tổ hợp nC3 (chỉ việc chọn quà vị trí đã được cố định).

Ở đây ta cần các hộp quà là phải có mã khác nhau nghĩa là ta sẽ trừ đi các trường hợp:

TH1: có 2 hộp giống, 1 hộp khác.

TH2: có 3 hộp giống nhau.

Bây giờ ta giải quyết từng trường hợp.

TH1: Ta tìm chúng bằng việc tính số cách chọn 2 món từ x món quà giống nhau bằng xC2, sau đó nhân với số món quà khác nó (bỏ qua số lượng ta chỉ lấy số lượng món có mặt, như ví dụ là 3 món: 3,1,4) là sẽ ra được số trường hợp cần loại trừ. Tại sao nghĩ ra được hướng này là vì khi sử dụng nC3, các bạn cũng có thể chọn 2 món bất kì từ x món giống nhau và bạn còn lại có thể sẽ chọn món khác.Do là xài tổ hợp, nên chỉ có 1 cách xếp và cách xếp đó chắc chắn thỏa vị trí.

TH2: Ta làm tương tư, nhưng vì bạn chọn quà y chang nên chỉ cần xài xC3.

Bây giờ giải quyết bài toán.

1 món quà có 2 trường hợp:

TH1: k>=3

Nếu k>=3 thì nó sẽ chứa cả 2 trường hợp 3 hộp giống nhau và 2 hộp giống, 1 hộp khác. Nên ta phải tính rồi trừ ra.

TH2: k==2

Ta sẽ xài công thức như ta đã nói trước là xC2, nhưng mà x==2 thì 2C2=1, sau đó nhân với số món quà còn lại khác cái đang xét là OK.

BÀI 1: Lô tô​

Mô tả bài toán​

Input:​

Output:​

Ví dụ​

Input:​

Output:​

Giải thích:​

Input:​

Output:​

Giải thíc:​

Hướng dẫn giải:​

Code mẫu(C++)​

Bài 2​

Mô tả bài toán​

Input:​

Output:​

Ví dụ​

Input:​

Output:​

Hướng dẫn giải:​

Code mẫu (C++)​

Bài 3: Hai cậu bé Sun and Moon.​

Mô tả bài toán​

Input:​

Output:​

Ví dụ​

Input:​

Output:​

Giải thích:​

Code mẫu (C++)​

Bài 4: Giao dịch​

Mô tả bài toán​

Input:​

Output:​

Ví dụ​

Input:​

Output:​

Giải thích:​

Code mẫu (C++)​

Bài 5​

Mô tả bài toán​

Input:​

Output:​

Ví dụ​

Input:​

Output:​

iải thích:​

Code mẫu (C++)​

Bài 6: Cắt bánh​

Mô tả bài toán​

Input:​

Output :​

Lưu ý:​

Ví dụ​

Input:​

Output:​

Giải thích:​

Code mẫu (C++)​

Giải thích ý tưởng:​

Bài 7​

Mô tả bài toán​

Ví dụ​

Input:​

Ouput:​

Code mẫu (C++)​

Bài 8​

Mô tả bài toán​

Input:​

Output:​

Ví dụ​

Input:​

Output:​

Code mẫu (C++)​

Bài 9: Trạm ga​

Mô tả bài toán​

Input:​

Output:​

Giải thích:​

Bài 10: Cặp khóa mã hóa​

BÀI 1: Lô tô

Mô tả bài toán

Input:

Output:

Ví dụ

Input:

Output:

Giải thích:

Input:

Output:

Giải thíc:

Hướng dẫn giải:

Code mẫu(C++)

Bài 2

Mô tả bài toán

Input:

Output:

Ví dụ

Input:

Output:

Hướng dẫn giải:

Code mẫu (C++)

Bài 3: Hai cậu bé Sun and Moon.

Mô tả bài toán

Input:

Output:

Ví dụ

Input:

Output:

Giải thích:

Code mẫu (C++)

Bài 4: Giao dịch

Mô tả bài toán

Input:

Output:

Ví dụ

Input:

Output:

Giải thích:

Code mẫu (C++)

Bài 5

Mô tả bài toán

Input:

Output:

Ví dụ

Input:

Output:

iải thích:

Code mẫu (C++)

Bài 6: Cắt bánh

Mô tả bài toán

Input:

Output :

Lưu ý:

Ví dụ

Input:

Output:

Giải thích:

Code mẫu (C++)

Giải thích ý tưởng:

Bài 7

Mô tả bài toán

Ví dụ

Input:

Ouput:

Code mẫu (C++)

Bài 8

Mô tả bài toán

Input:

Output:

Ví dụ

Input:

Output:

Code mẫu (C++)

Bài 9: Trạm ga

Mô tả bài toán

Input:

Output:

Giải thích:

Bài 10: Cặp khóa mã hóa