THPTTD_104 - Số tam giác

View as PDF

Submit solution

Points: 10.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: triangular.inp
Output: triangular.out

Author:
Problem type
Allowed languages
C, C#, C++, Go, Java, JavaScript, Kotlin, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

In case the statement didn't load correctly, you can download the statement here: Statement


Comments

Please read the guidelines before commenting.



  • 3
    lephuochauhungvuong  commented on March 11, 2025, 7:50 a.m.
    #include<bits/stdc++.h>
    using namespace std;
    
    long long a[1000001], n;
    unordered_set<long long> triangularNumbers; // Set lưu trữ các số tam giác
    
    // Hàm tạo các số tam giác và lưu vào set
    void generateTriangularNumbers(long long maxValue) {
        long long k = 1;
        long long triangular = 0;
        while (triangular <= maxValue) {
            triangular = k * (k + 1) / 2;
            triangularNumbers.insert(triangular);
            k++;
        }
    }
    
    int main() {
        ios::sync_with_stdio(false); // Tăng tốc việc đọc/ghi dữ liệu
    
        ifstream fin("triangular.inp");
        ofstream fout("triangular.out");
    
        fin >> n;
        long long maxValue = 0;
    
        // Đọc dữ liệu và xác định giá trị lớn nhất
        for (int i = 1; i <= n; i++) {
            fin >> a[i];
            maxValue = max(maxValue, a[i]);
        }
    
        // Tạo các số tam giác đến giá trị maxValue
        generateTriangularNumbers(maxValue);
    
        // Kiểm tra mỗi số trong mảng có phải số tam giác không
        for (int i = 1; i <= n; i++) {
            if (triangularNumbers.find(a[i]) != triangularNumbers.end()) {
                fout << 1 << endl; // Nếu là số tam giác
            } else {
                fout << 0 << endl; // Nếu không phải số tam giác
            }
        }
    
        return 0;
    }
    

  • 0
    kietjumper  commented on Oct. 30, 2024, 3:27 p.m.

    Ý tưởng: Để kiểm tra một số có phải là số tam giác hay không, ta tính ~x~ = sqrt(~2n~), sau đó kiểm tra xem ~x~ * (~x~ + ~1~) có bằng ~2n~ hay không. Nếu có thì ~n~ là số tam giác và ngược lại!