HDU-1214 圆桌会议

Problem Description

HDU ACM集训队的队员在暑假集训时经常要讨论自己在做题中遇到的问题.每当面临自己解决不了的问题时,他们就会围坐在一张圆形的桌子旁进行交流,经过大家的讨论后一般没有解决不了的问题,这也只有HDU ACM集训队特有的圆桌会议,有一天你也可以进来体会一下哦:),在一天在讨论的时候,Eddy想出了一个极为古怪的想法,如果他们在每一分钟内,一对相邻的两个ACM队员交换一下位子,那么要多少时间才能得到与原始状态相反的座位顺序呢?(即对于每个队员，原先在他左面的队员后来在他右面，原先在他右面的队员在他左面),这当然难不倒其他的聪明的其他队友们,马上就把这个古怪的问题给解决了,你知道是怎么解决的吗?

Input

对于给定数目N(1<=N<=32767)，表示有N个人,求要多少时间才能得到与原始状态相反的座位顺序(reverse)即对于每个人，原先在他左面的人后来在他右面，原先在他右面的人在他左面。

Output

对每个数据输出一行，表示需要的时间(以分钟为单位)

Sample Input

4
5
6

Sample Output

2
4
6

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int m=n/2;
        int sum=((m-1)*m)/2;
        if(n%2==1)
            sum+=sum+m;
        else
            sum+=sum;
        printf("%d\n",sum);
    }
}

Ehab and the Expected XOR Problem

CodeForces - 1174D

Given two integers n and x, construct an array that satisfies the following conditions:

for any element ai in the array, 1≤ai<2n;
there is no non-empty subsegment with bitwise XOR equal to 0 or x,
its length l should be maximized.
A sequence b is a subsegment of a sequence a if b can be obtained from a by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input

The only line contains two integers n and x (1≤n≤18, 1≤x<218).

Output

The first line should contain the length of the array l.

If l is positive, the second line should contain l space-separated integers a1, a2, …, al (1≤ai<2n) — the elements of the array a.

If there are multiple solutions, print any of them.

Examples

Input

3 5

Output

3
6 1 3

Input

2 4

Output

3
1 3 1

Input

1 1

Output

#include<bits/stdc++.h>
using namespace std;
int s[(1<<19)];
int ex[(1<<19)];
int go=1;
int cnt=1;
int main()
{
    int n,x;
    scanf("%d%d",&n,&x);
    if(x>=(1<<n))
    {
        printf("%d\n",(1<<n)-1);
        for(int i=1;i<=(1<<n)-1;i++)
        {
            printf("%d ",i^(i-1));
        }
        return 0;
    }
    else
    {
        ex[0]=1;
        for(int i=1;i<=(1<<n)-1;i++)
        {
            if(!ex[i^x])
            {
                ex[i]=1;
                s[cnt]=i;
                cnt++;
            }
        }
    }
    printf("%d\n",cnt-1);
    for(int i=1;i<=cnt-1;i++)
    {
        printf("%d ",s[i]^s[i-1]);
    }
    return 0;
}

The LCMs Must be Large

CodeForces - 1166E

Dora the explorer has decided to use her money after several years of juicy royalties to go shopping. What better place to shop than Nlogonia?

There are n stores numbered from 1 to n in Nlogonia. The i-th of these stores offers a positive integer ai.

Each day among the last m days Dora bought a single integer from some of the stores. The same day, Swiper the fox bought a single integer from all the stores that Dora did not buy an integer from on that day.

Dora considers Swiper to be her rival, and she considers that she beat Swiper on day i if and only if the least common multiple of the numbers she bought on day i is strictly greater than the least common multiple of the numbers that Swiper bought on day i.

The least common multiple (LCM) of a collection of integers is the smallest positive integer that is divisible by all the integers in the collection.

However, Dora forgot the values of ai. Help Dora find out if there are positive integer values of ai such that she beat Swiper on every day. You don’t need to find what are the possible values of ai though.

Note that it is possible for some values of ai to coincide in a solution.

Input

The first line contains integers m and n (1≤m≤50, 1≤n≤104) — the number of days and the number of stores.

After this m lines follow, the i-th line starts with an integer si (1≤si≤n−1), the number of integers Dora bought on day i, followed by si distinct integers, the indices of the stores where Dora bought an integer on the i-th day. The indices are between 1 and n.

Output

Output must consist of a single line containing “possible” if there exist positive integers ai such that for each day the least common multiple of the integers bought by Dora is strictly greater than the least common multiple of the integers bought by Swiper on that day. Otherwise, print “impossible”.

Note that you don’t have to restore the integers themselves.

Examples

Input

2 5
3 1 2 3
3 3 4 5

Output

possible

Input

10 10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

Output

impossible

Note

In the first sample, a possible choice for the values of the ai is 3,4,3,5,2. On the first day, Dora buys the integers 3,4 and 3, whose LCM is 12, while Swiper buys integers 5 and 2, whose LCM is 10. On the second day, Dora buys 3,5 and 2, whose LCM is 30, and Swiper buys integers 3 and 4, whose LCM is 12.

#include<bits/stdc++.h>
using namespace std;
bitset<11111> b[55],t;
int main()
{
    int i,j,n,m,k,x;
    cin>>n>>m;
    for(i=0; i<n; ++i)
    {
        cin>>k;
        for(j=0; j<k; ++j)
            cin>>x,b[i][x]=1;
    }
    for(i=0; i<n; ++i)
        for(j=i+1; j<n; ++j)
        {
            t=b[i]&b[j];
            if(t.count()==0)
            {
                printf("impossible");
                return 0;
            }
        }
    printf("possible");
    return 0;
}

Frog and Portal

HihoCoder - 1873

A small frog wants to get to the other side of a river. The frog is initially located at one bank of the river (position 0) and wants to get to the other bank (position 200). Luckily, there are 199 leaves (from position 1 to position 199) on the river, and the frog can jump between the leaves. When at position p, the frog can jump to position p+1 or position p+2.

How many different ways can the small frog get to the bank at position 200? This is a classical problem. The solution is the 201st number of Fibonacci sequence. The Fibonacci sequence is constructed as follows: F1=F2=1;Fn=Fn-1+Fn-2.

Now you can build some portals on the leaves. For each leaf, you can choose whether to build a portal on it. And you should set a destination for each portal. When the frog gets to a leaf with a portal, it will be teleported to the corresponding destination immediately. If there is a portal at the destination, the frog will be teleported again immediately. If some portal destinations form a cycle, the frog will be permanently trapped inside. Note that You cannot build two portals on the same leaf.

Can you build the portals such that the number of different ways that the small frog gets to position 200 from position 0 is M?

Input

There are no more than 100 test cases.

Each test case consists of an integer M, indicating the number of ways that the small frog gets to position 200 from position 0. (0 ≤ M < 232)

Output

For each test case:

The first line contains a number K, indicating the number of portals.

Then K lines follow. Each line has two numbers ai and bi, indicating that you place a portal at position ai and it teleports the frog to position bi.

You should guarantee that 1 ≤ K, ai, bi ≤ 199, and ai ≠ aj if i ≠ j. If there are multiple solutions, any one of them is acceptable.

Sample Input

0
1
5

Sample Output

2
1 1
2 1
2
1 199
2 2
2
4 199
5 5

#include<bits/stdc++.h>
#define ll long long
int main()
{
    ll n;
    while(scanf("%lld",&n)!=EOF)
    {
        printf("65\n");
        if(n&(1ll<<0)) printf("1 199\n");
        else
            printf("1 1\n");
        for(ll i=1; i<32; i++)
        {
            printf("%lld %lld\n",5+(i-1)*6,5+(i-1)*6);
            if(n&(1ll<<i))
                printf("%lld 199\n",7+(i-1)*6);
            else
                printf("%lld %lld\n",7+(i-1)*6,7+(i-1)*6);
        }
        printf("197 197\n");//no
        printf("198 198\n");
    }
}

Snake Carpet UVALive - 7269

题目链接

#include<bits/stdc++.h>
#define ll long long
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int wide1,height1,wide2,height2;
        if(n%2==1) height1=wide1=n/2+1;
        else height1=wide1=n/2;
        if(n/2%2==0)
        {
            wide2=n/2;
            height2=n/2+1;
        }
        else {wide2=n/2+1;height2=n/2;}
        if(wide1==height2)
        {
            int newheight=wide1,newwide=wide1+wide2;
            printf("%d %d\n",newheight,newwide);
            for(int i=1;i<=n;i++)
            {
                if(i%2==1)//left
                {
                    for(int t=1;t<=(i+1)/2;t++)
                    {
                        printf("%d %d ",t,(i+1)/2);
                    }
                    for(int t=(i+1)/2-1;t>=1;t--)
                    {
                        printf("%d %d ",(i+1)/2,t);
                    }
                    printf("\n");
                }
                else if(i%2==0)//right
                {
                     if(i/2%2==1)
                     {
                         for(int t=1;t<=i/2;t++)
                         {
                             printf("%d %d ",t,i/2+wide1);
                         }
                         for(int t=i/2;t>=1;t--)
                         {
                             printf("%d %d ",t,i/2+1+wide1);
                         }
                         printf("\n");
                     }
                     else
                     {
                         for(int t=1;t<=i/2;t++)
                         {
                             printf("%d %d ",i/2,t+wide1);
                         }
                         for(int t=i/2;t>=1;t--)
                         {
                             printf("%d %d ",i/2+1,t+wide1);
                         }
                         printf("\n");
                     }
                }
            }
        }
        else
        {
            int newheight=wide1+height2,newwide=wide1;
            printf("%d %d\n",newheight,newwide);
            for(int i=1;i<=n;i++)
            {
                if(i%2==1)//left
                {
                    for(int t=1;t<=(i+1)/2;t++)
                    {
                        printf("%d %d ",t,(i+1)/2);
                    }
                    for(int t=(i+1)/2-1;t>=1;t--)
                    {
                        printf("%d %d ",(i+1)/2,t);
                    }
                    printf("\n");
                }
                else if(i%2==0)//right
                {
                     if(i/2%2==1)
                     {
                         for(int t=1;t<=i/2;t++)
                         {
                             printf("%d %d ",t+wide1,i/2);
                         }
                         for(int t=i/2;t>=1;t--)
                         {
                             printf("%d %d ",t+wide1,i/2+1);
                         }
                         printf("\n");
                     }
                     else
                     {
                         for(int t=1;t<=i/2;t++)
                         {
                             printf("%d %d ",i/2+wide1,t);
                         }
                         for(int t=i/2;t>=1;t--)
                         {
                             printf("%d %d ",i/2+1+wide1,t);
                         }
                         printf("\n");
                     }
                }
            }
        }
    }
    return 0;
}

The minimal unique substring

CodeForces - 1158B

Let s be some string consisting of symbols “0” or “1”. Let’s call a string t a substring of string s, if there exists such number 1≤l≤|s|−|t|+1 that t=slsl+1…sl+|t|−1. Let’s call a substring t of string s unique, if there exist only one such l.

For example, let s=”1010111”. A string t=”010” is an unique substring of s, because l=2 is the only one suitable number. But, for example t=”10” isn’t a unique substring of s, because l=1 and l=3 are suitable. And for example t=”00” at all isn’t a substring of s, because there is no suitable l.

Today Vasya solved the following problem at the informatics lesson: given a string consisting of symbols “0” and “1”, the task is to find the length of its minimal unique substring. He has written a solution to this problem and wants to test it. He is asking you to help him.

You are given 2 positive integers n and k, such that (nmod2)=(kmod2), where (xmod2) is operation of taking remainder of x by dividing on 2. Find any string s consisting of n symbols “0” or “1”, such that the length of its minimal unique substring is equal to k.

Input

The first line contains two integers n and k, separated by spaces (1≤k≤n≤100000, (kmod2)=(nmod2)).

Output

Print a string s of length n, consisting of symbols “0” and “1”. Minimal length of the unique substring of s should be equal to k. You can find any suitable string. It is guaranteed, that there exists at least one such string.

Examples

Input

4 4

Output

1111

Input

5 3

Output

01010

Input

7 3

Output

1011011

Note

In the first test, it’s easy to see, that the only unique substring of string s=”1111” is all string s, which has length 4.

In the second test a string s=”01010” has minimal unique substring t=”101”, which has length 3.

In the third test a string s=”1011011” has minimal unique substring t=”110”, which has length 3.

详细题解

#include<bits/stdc++.h>
using namespace std;
int n,k;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		printf("%d",(i%((n-k)/2+1)>0));
	}
	return 0;
}

ACM-构造

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

2019牛客暑假多校训练（第一场）题解上一篇

ACM-思维构造题（2019暑假集训）

HDU-1214 圆桌会议

Problem Description

Input

Output

Sample Input

Sample Output

Ehab and the Expected XOR Problem

CodeForces - 1174D

Input

Output

Examples

Input

Output

Input

Output

Input

Output

The LCMs Must be Large

CodeForces - 1166E

Input

Output

Examples

Input

Output

Input

Output

Note

Frog and Portal

HihoCoder - 1873

Input

Output

Sample Input

Sample Output

Snake Carpet UVALive - 7269

The minimal unique substring

CodeForces - 1158B

Input

Output

Examples

Input

Output

Input

Output

Input

Output

Note