列表

详情

NC229243. The Legend of God Flukehn in Eastern

描述

Flukehn is a well-known god in Eastern and he is invincible with 5 ranks in Go. To challenge the legend of god Flukehn in Eastern, you decided to compose a modified Shogi (the Japanese variant of chess) match with Flukehn.

The chess board can be viewed as an infinite two-dimensional plane. Initially you have n Pawns uniquely occupying an integral point on the board, and Flukehn has one Gold general occupying an integral point either.

The game is turn-based. At each turn,
  1. you shall pick a Pawn and move it down one unit. More formally, you can move one Pawn with original coordinate (x,y) to (x,y-1). Noted that you can't have two Pawns on the same point at any moment.
  2. Then Flukehn shall choose his Gold general to move up, down, left, right, up-left or up-right to the nearest integral point. More formally, with original coordinate (x,y), Flukehn shall choose his Gold general to move to , (x,y-1), (x-1,y), , or .


No one can skip his own turn.

At any moment when Gold general and a Pawn are on the same integral point, the Pawn is considered defeated by \textsf{Flukehn} and should be picked out from the board (Even if it is on your turn).

The initial coordinate of Flukehn's Gold general is on (0,0).

There is no limitation on turns of the game.

You aim to minimize the number of defeated Pawns while Flukehn aim to maximize it and you both play optimally in the game.

What is final number of Pawns defeated in finite number of turns?

输入描述

First line contains one integer , denoting the number of test cases.

For every test case, the first line contains one integer  as the number of Pawns you initially own.

In the following n lines, the  line contains two integers  as the coordinates of the  Pawn. It is guaranteed that no two Pawns are on the same point and no Pawn is at (0,0) initially.

The sum of n for all test cases does not exceed .

输出描述

For every test case, output one line containing one integer as the number of Pawns defeated in a finite number of turns.

示例1

输入: 

2
2
1 1
2 4
3
1 1
2 4
-1 -1

输出: 

2
2

说明:

In the second example, the third Pawn can continue to move down allowing it to escape from Gold general.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 374ms, 内存消耗: 2776K, 提交时间: 2022-05-09 21:48:51 

//@Author: ZIMA
#include<bits/stdc++.h>
using namespace std;
#define IOS std::ios_base::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
#define PP pair<int, int>
#define endl '\n'
#define ll long long
#define int long long
#define x first
#define y second
const ll INF=1e16;
void solve() {
    int n;
    cin>>n;
    vector<PP> a(n);
    bool flag=false;
//     map<int,int> cnt;
    for(int i=0;i<n;i++) {
        cin>>a[i].x>>a[i].y;
        if(abs(a[i].x)>a[i].y) flag=true;
//         if(i>1) cnt[a[i].x]++;
    }
    if(flag) {
        cout<<n-1<<endl;
        return;
    }
    sort(a.begin(),a.end(),[&](PP t1,PP t2) {
        if(t1.y==t2.y) return t1.x<t2.x;
        return t1.y<t2.y;
    });
    int pos=-1;
    set<int> st;
    for(int i=n-1;i>=0;i--) {
        if(st.find(a[i].x)==st.end()) {
            if((int)st.size()==2) {
                pos=i;
                break;
            } else if((int)st.size()==1&&abs(*st.begin()-a[i].x)>1) {
                pos=i;
                break;
            }
            st.insert(a[i].x);
        }
    }
    if(pos==-1) {
        cout<<n<<endl;
        return;
    }
    for(int i=0;i<n-1;i++) {
        auto [x1,y1]=a[i];
        auto [x2,y2]=a[i+1];
        if(y2-2*y1<abs(x1-x2)) {
            if(abs(x1-x2)>1) {
                cout<<n-1<<endl;
                return;
            }
            if(abs(x1-x2)==1&&pos>=i) {
                cout<<n-1<<endl;
                return;
            }
        }
        if(i+2<n) {
            auto [x3,y3]=a[i+2];
//             cnt[a[i+2].x]--;
            if(y2==y3) {
                if(y3-2*y1<abs(x1-x3)) {
                    if(abs(x1-x3)>1) {
                        cout<<n-1<<endl;
                        return;
                    }
                    if(abs(x1-x3)==1&&pos>=i) {
                        cout<<n-1<<endl;
                        return;
                    }
                }
            }
        }
    }
    cout<<n<<endl;
}
signed main() {
    IOS;
    int __;
    cin>>__;
    while(__--) solve();
    return 0;
}

上一题

© 2024 nowcoder.com