BUPT训练-Codefoces325E Red Button

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

Description

Piegirl found the red button. You have one last chance to change the inevitable end.
The circuit under the button consists of n nodes, numbered from 0 to n - 1. In order to deactivate the button, the n nodes must be disarmed in a particular order. Node 0 must be disarmed first. After disarming node i, the next node to be disarmed must be either node (2·i) modulo n or node (2·i) + 1 modulo n. The last node to be disarmed must be node 0. Node 0 must be disarmed twice, but all other nodes must be disarmed exactly once.
Your task is to find any such order and print it. If there is no such order, print -1.

Input

Input consists of a single integer n (2 ≤ n ≤ 105).

Output

Print an order in which you can to disarm all nodes. If it is impossible, print -1 instead. If there are multiple orders, print any one of them.

Examples

Input

2

Output

0 1 0

Input

3

Output

-1

Input

4

Output

0 1 3 2 0

Input

16

Output

0 1 2 4 9 3 6 13 10 5 11 7 15 14 12 8 0

题目大意

有n个红色按钮,编号0,1,……,n,你需要从0开始按这些红色按钮,要求除0号以外都只能按一次,而且是从0按,最后一次也要按0号。
限制:当按到第i个按钮时,下一个按的按钮只能是2i mod n或者(2i+1) mod n。


题解

A*搜索+贪心

首先限制条件可以看做是有向图的有向边,先将边反向,预处理求出所有点离最后一个要按的0的距离。以这个距离作为A*的估值函数优化搜索。
在搜索的时候,假设当前搜索到编号为now,那么我们看一下它能向下搜索到的点是否被搜索过,若都被搜索过且没有到0,那么我们就可以结束搜索过程,输出impossible,若有未被搜索过的,那么我们选择估值函数较大的那个点作为下一个要搜索的点(这一步就是贪心的思想,我们的目标是在按到最后一个0号按钮之前尽量多的去按其它的所有按钮,而我们的估值函数就是离最终的0号按钮还要按几个这样的距离,所以我们就要选择估值函数较大的那个点作为下一个目标)。当我们再次搜索到0的时候就结束搜索。(每一步搜索都要记录当前搜索的点是哪个)。
最后遍历一遍答案序列,如果搜索过的点的个数正好为n+1,那么我们就输出possible并将答案序列输出,否则就输出impossible。


代码示例

#include 
using namespace std;
const int maxn = 2e5+5;
int mx = 0;
struct edge{
    int fr,to,next1,next2;
}e[maxn<<1];
int h[maxn],d[maxn],pr[maxn];
int vis[maxn];
void init(){
    memset(h,-1,sizeof(h));
    memset(pr,-1,sizeof(pr));
    return;
}
int cnt = 0;
void add(int u,int v){
    e[cnt].fr = u;e[cnt].to = v;e[cnt].next1 = h[u];e[cnt].next2 = pr[v];
    h[u] = pr[v] = cnt++;
    return;
}
int inq[maxn];
int f[maxn];
void a_star_pre(){
    queue<int>q;
    q.push(0);
    f[0] = 0;
    inq[0] = 1;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = pr[x];i != -1;i = e[i].next2){
            if(e[i].fr != 0 && inq[e[i].fr] == 0){
                f[e[i].fr] = f[x] + 1;
                inq[e[i].fr] = 1;
                q.push(e[i].fr);
            }
        }
    }
    return;
}
int ans[maxn];
void find(int x){
    vis[x]++;
    int pos = -1,mxl = 2147483647;
    for(int i = h[x];i != -1;i = e[i].next1){
        if(vis[e[i].to] && e[i].to != 0)continue;
        if(pos == -1){
            pos = e[i].to;
            mxl = f[e[i].to];
        }
        else{
            if(mxl < f[e[i].to]){
                pos = e[i].to;
                mxl = f[e[i].to];
            }
        }
    }
    if(pos == -1)return;
    ans[++cnt] = pos;
    find(pos);
    return;
}
int n;
int main(){
    init();
    cin >> n;
    for(int i = 0;i < n;++i){
        int x = (2*i)%n;
        int y = (2*i+1)%n;
        if(x != i)add(i,x);
        if(y != i)add(i,y);
    }
    a_star_pre();
    cnt = 0;
    ans[++cnt] = 0;
    find(0);
    if(cnt != n+1){
        cout << -1 << endl;
        return 0;
    }
    else{
        for(int i = 1;i <= cnt;++i)
            cout << ans[i] << " ";
        cout << endl;
    }
    return 0;
}​
Next: 三分法
Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00