HSG THPT TPHCM 2022 - Trội chéo

Xem dạng PDF

Gửi bài giải


Điểm: 0,05 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Nguồn bài:
Kỳ thi Học sinh giỏi THPT TPHCM 2022
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Ma trận ~A~ kích thước ~n \times n~ được gọi là trội chéo nếu thoả mãn các điều kiện sau:

  1. ~\forall \ i, j \in [1,n],\ A_{ij} \ge 0~.

  2. ~\forall \ i \in [1,n],\ A_{ii} \ge \sum_{j=1,\ j \ne i}^n\ A_{ij}~.

  3. ~\exists \ i \in [1,n],\ A_{ii} \gt \sum_{j=1,\ j \ne i}^n\ A_{ij}~.

Phần tử ~\ A_{ii} \gt \sum_{j=1,\ j \ne i}^n\ A_{ij}~ được gọi là phần tử trội.

Yêu cầu: Cho ~n~ và ma trận ~A~, các phần tử của ma trận ~A~ là số nguyên ~(0 \le A_{ij} \leq 1000,\ 2 \le n \le 1000)~. Viết chương trình xác định xem ~A~ có phải là ma trận trội chéo hay không, nếu có thì đưa ra số lượng phần tử trội.

Input

  • Dòng đầu tiên chứa số nguyên ~n~.

  • Trên ~n~ dòng tiếp theo, dòng thứ ~i~ có ~n~ số nguyên xác định dòng thứ ~i~ của ma trận.

Các số trên một dòng cách nhau bởi ít nhất một dấu khoảng trắng.

Output

  • Dòng đầu tiên chứa thông báo YES hoặc NO.

  • Nếu kết quả là YES, dòng thứ ~2~ chứa một số nguyên cho biết số phần tử trội.

Sample Input 1

3
10 5 5
0 1 0
2 2 5

Sample Output 1

YES
2

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    DHQ_29  đã bình luận lúc 7, Tháng 4, 2025, 4:12

    include <bits/stdc++.h>

    using namespace std; void init() { iosbase::syncwith_stdio(0);cin.tie(0);cout.tie(0); } int n; const int maxn =1005; int A[maxn][maxn];int strictCount = 0; void giai() {

    cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> A[i][j];
    
    for (int i = 0; i < n; ++i) 
    {
        int diag = A[i][i];
        int sumRow = 0;
        for (int j = 0; j < n; ++j)
            if (j != i) sumRow += A[i][j];
    
        if (diag < sumRow) 
        {
    
            cout << "NO\n";  
           return;
        }
        if (diag > sumRow) strictCount++;
    }
    
    if (strictCount >= 1) 
    {
        cout << "YES\n" << strictCount << endl;
    } else {
        cout << "NO\n";
    }
    

    } int main() { init(); giai();

    return 0;
    

    }