Quân tượng thú vị


Submit solution

Points: 2 (partial)
Time limit: 0.1s
Memory limit: 10M

Author:
Problem type

Một bàn cờ vua có kích thước 1000x1000, các hàng được đánh số từ 1 đến 1000 lần lượt từ trên xuống dưới, các cột được đánh số từ 1 đến 1000 lần lượt từ trái sang phải, quân tượng là quân có thể di chuyển theo đường chéo và ăn các quân cờ khác. Giả sử trên bàn cờ có n quân tượng, nhiệm vụ của bạn là hãy đếm số quân tượng có thể ăn nhau trên bàn cờ (Hai quân tượng có thể ăn nhau kể cả giữa chúng có một quân tượng khác).

Input

Dòng đầu tiên chứa số nguyên n là số quân tượng

N dòng tiếp theo, mỗi dòng chứa hai số xi và yi là tọa độ của quân tượng thứ i trên bàn cờ.

Output:

Số quân tượng có thể ăn nhau trên bàn cờ.

Example

Input

3
1 1
5 5
9 9

Output

3

Comments


  • -1
    QuangDuy_CNTTVA1_K62  commented on May 31, 2022, 2:57 p.m. edit 9
    #include <bits/stdc++.h>
    #define SIZE 1000
    #define fir first
    #define sec second
    using namespace std;
    long long subSolve(int **space, int x, int y, int dirx, int diry, int lim){
        long long cou = 0;
        for(int i = 0; i < lim; i++){
            cou += space[x][y];
            x += dirx;
            y += diry;
        }
        return cou;
    }
    
    int main(){
        int N; long long cou = 0; int **board;
        cin >> N;
        board = (int **)malloc(sizeof(int *)*SIZE);
        for(int i = 0; i < SIZE; i++)
            board[i] = (int *)calloc(SIZE, sizeof(int));
        for(int i = 0; i < N; i++){
            pair<int, int> tmp;
            cin >> tmp.fir >> tmp.sec;
            board[tmp.fir - 1][tmp.sec - 1]++;
        }
        for(int i = 0; i < SIZE; i++){
            long long tmp = subSolve(board, 0, i, 1, 1, SIZE - i);
            cou += (tmp*(tmp - 1))/2;
        }
        for(int i = 1; i < SIZE; i++){
            long long tmp = subSolve(board, i, 0, 1, 1, SIZE - i);
            cou += (tmp*(tmp - 1))/2;
        }
        for(int i = 0; i < SIZE; i++){
            long long tmp = subSolve(board, SIZE - 1, i, -1, 1, SIZE - i);
            cou += (tmp*(tmp - 1))/2;
        }
        for(int i = 0; i < SIZE - 1; i++){
            long long tmp = subSolve(board, i, 0, -1, 1, i + 1);
            cou += (tmp*(tmp - 1))/2;
        }
        cout << cou;
        return 0;
    }

    • 4
      QuynhSon_CNTT4_K62  commented on June 1, 2022, 12:33 p.m.

      chắc test đề không được chặt chẽ cho lắm, có vẻ 2 con tượng đứng trên 1 ô :)


      • 1
        QuangDuy_CNTTVA1_K62  commented on June 1, 2022, 11:15 p.m. edit 2

        Đúng r, code mình coi 2 quân tượng đứng cùng 1 ô là 1, xuất kết quả ra luôn nhỏ hơn đáp án một tí - sai số tầm 5% gì gì đấy. Trên codechef nó ghi rõ các quân tượng đứng ở các vị trí khác nhau nên code mình AC bình thường (bỏ qua mấy case ngoài khoảng 1000x1000). Mà chơi cờ thì ai cho 2 quân tượng đúng cùng 1 ô bao giờ, chốt là tại testcase hết :)

        Đã sửa code r nhé