HSG THPT TPHCM 2022 - Trội chéo

View as PDF
Submit solution
Points: 0.05 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Author:
bedao
Problem source:
Kỳ thi Học sinh giỏi THPT TPHCM 2022
Problem type
Allowed languages
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

Comments

Please read the guidelines before commenting.


  • 0
    DHQ_29  commented on April 7, 2025, 4:12 a.m.

    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;

    }