1.Sonya and Exhibition

Description

Sonya decided to organize an exhibition of flowers. Since the girl likes only roses and lilies, she decided that only these two kinds of flowers should be in this exhibition.

There are n flowers in a row in the exhibition. Sonya can put either a rose or a lily in the i-th position. Thus each of n positions should contain exactly one flower: a rose or a lily.

She knows that exactly m people will visit this exhibition. The i-th visitor will visit all flowers from li to ri inclusive. The girl knows that each segment has its own beauty that is equal to the product of the number of roses and the number of lilies.

Sonya wants her exhibition to be liked by a lot of people. That is why she wants to put the flowers in such way that the sum of beauties of all segments would be maximum possible.

Input

The first line contains two integers n and m (1≤n,m≤103) — the number of flowers and visitors respectively.

Each of the next m lines contains two integers li and ri (1≤li≤ri≤n), meaning that i-th visitor will visit all flowers from li to ri inclusive.

Output

Print the string of n characters. The i-th symbol should be «0» if you want to put a rose in the i-th position, otherwise «1» if you want to put a lily.

If there are multiple answers, print any.

Sample Input

Input

5 3

1 3

2 4

2 5

Output

01100

Input

6 3

5 6

1 4

4 6

Output

110010

Hint

In the first example, Sonya can put roses in the first, fourth, and fifth positions, and lilies in the second and third positions;

    in the segment [1…3], there are one rose and two lilies, so the beauty is equal to 1⋅2=2;

    in the segment [2…4], there are one rose and two lilies, so the beauty is equal to 1⋅2=2;

    in the segment [2…5], there are two roses and two lilies, so the beauty is equal to 2⋅2=4.

The total beauty is equal to 2+2+4=8.

In the second example, Sonya can put roses in the third, fourth, and sixth positions, and lilies in the first, second, and fifth positions;

in the segment [5…6], there are one rose and one lily, so the beauty is equal to 1⋅1=1;

in the segment [1…4], there are two roses and two lilies, so the beauty is equal to 2⋅2=4;

in the segment [4…6], there are two roses and one lily, so the beauty is equal to 2⋅1=2 .

The total beauty is equal to 1+4+2=7.

 

题目意思：花园里要展览n棵花，有两种花，一种是玫瑰，一种是百合。有m位游客来参观花展，每一位游客只会观赏【l,r】的花，游客会有对花展的一种满意度，每一区域满意度等于玫瑰的种类×百合的种类，问要怎么样排列两种花才能得到最大的总的满意度。

解题思路：这道题耗费了我太久的时间，主要是样例太坑爹了，虽然知道正确答案不止一种但是样例的答案很有迷惑性，开始我一直在研究区间的覆盖，一直没有头绪，哎啊。

其实正确的思路是这样来想，我们想要得到区间内的最大满意度一定是尽量让两种花的种类尽可能的相等！而每一个区间都尽可能的相等进而就会得到整个区间的尽可能的相等分布，

那么最好的两种花间隔排列。

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 int main() 6 { 7     int n,m,i,l,r; 8     scanf("%d%d",&n,&m); 9     for(i=0;i
       
      
     

 

2.Sonya and Hotels

Description

Sonya decided that having her own hotel business is the best way of earning money because she can profit and rest wherever she wants.

The country where Sonya lives is an endless line(没有尽头的线). There is a city in each integer coordinate on this line. She has n hotels, where the i-th hotel is located in the city with coordinate x. Sonya is a smart girl, so she does not open two or more hotels in the same city.Sonya understands that her business needs to be expanded by opening new hotels, so she decides to build one more. She wants to make the minimum distance from this hotel to all others to be equal to d. The girl understands that there are many possible locations to construct such a hotel. Thus she wants to know the number of possible coordinates of the cities where she can build a new hotel.Because Sonya is lounging in a jacuzzi in one of her hotels, she is asking you to find the number of cities where she can build a new hotel so that the minimum distance from the original n hotels to the new one is equal to d.

Input

The first line contains two integers n and d (1≤n≤100, 1≤d≤109) — the number of Sonya's hotels and the needed minimum distance from a new hotel to all others.

The second line contains n different integers in strictly increasing order（严格递增序列） x1,x2,…,xn (−109≤xi≤109) — coordinates of Sonya's hotels.

Output

Print the number of cities where Sonya can build a new hotel so that the minimum distance from this hotel to all others is equal to d.

Sample Input

Input

4 3

-3 2 9 16

Output

6

Input

5 2

4 8 11 18 19

Output

5

Hint

In the first example, there are 6 possible cities where Sonya can build a hotel. These cities have coordinates −6, 5, 6, 12, 13, and 19.

In the second example, there are 5 possible cities where Sonya can build a hotel. These cities have coordinates 2, 6, 13, 16, and 21.

 

题目意思：要在已有的n家酒店的基础上还要再新建一些酒店，原有的酒店是按照递增序列排布在坐标轴上，新建的酒店要与原来的酒店的最小距离为d，问你最多能够新建多少家酒店

解题思路：我们知道在这些原来酒店序列上，开头和结尾的位置一定能够各新建一家酒店，这样就有两家了，这样我们再看中间那些酒店之间能否新建酒店，中间的那些酒店最多还可以在其左边或者右边新建酒店，那么我们只要去判断其左边或者右边能否新建酒店就可以了，同时要注意防止某一点被重复计算，这是我们使用等于号将可能重复的点划归为一类。

 

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 int a[110]; 6 int main() 7 { 8     int n,d,i,ans; 9     scanf("%d%d",&n,&d);10     ans=2;11     for(i=0; i
        
         a[i-1]+d)18         {19             ans++;20         }21     }22     for(i=0; i
        
       
      
     

 

 

3.If at first you don't succeed...（简单容斥原理）

Description

Each student eagerly awaits the day he would pass the exams successfully. Thus, Vasya was ready to celebrate, but, alas, he didn't pass it. However, many of Vasya's fellow students from the same group were more successful and celebrated after the exam.

Some of them celebrated in the BugDonalds restaurant, some of them — in the BeaverKing restaurant, the most successful ones were fast enough to celebrate in both of restaurants. Students which didn't pass the exam didn't celebrate in any of those restaurants and elected to stay home to prepare for their reexamination. However, this quickly bored Vasya and he started checking celebration photos on the Kilogramm. He found out that, in total, BugDonalds was visited by A students, BeaverKing — by B students and C students visited both restaurants. Vasya also knows that there are N students in his group.

Based on this info, Vasya wants to determine either if his data contradicts itself or, if it doesn't, how many students in his group didn't pass the exam. Can you help him so he won't waste his valuable preparation time?

Input

The first line contains four integers — A, B, C and N (0≤A,B,C,N≤100).

Output

If a distribution of N students exists in which A students visited BugDonalds, B — BeaverKing, C— both of the restaurants and at least one student is left home (it is known that Vasya didn't pass the exam and stayed at home), output one integer — amount of students (including Vasya) who did not pass the exam.

If such a distribution does not exist and Vasya made a mistake while determining the numbers A, B, C or N (as in samples 2 and 3), output −1.

Sample Input

Input

10 10 5 20

Output

5

Input

2 2 0 4

Output

-1

Input

2 2 2 1

Output

-1

Hint

The first sample describes following situation: 5 only visited BugDonalds, 5 students only visited BeaverKing, 5 visited both of them and 5 students (including Vasya) didn't pass the exam.

In the second sample 2 students only visited BugDonalds and 2 only visited BeaverKing, but that means all 4 students in group passed the exam which contradicts the fact that Vasya didn't pass meaning that this situation is impossible.

The third sample describes a situation where 2 students visited BugDonalds but the group has only 1 which makes it clearly impossible.

 

题目意思：一个有n个人。考试过后，考试通过的学生要到餐馆去庆祝，有去A餐馆的a人，去B餐馆的b人，那些考的最好的c人两个餐馆都去，但是那些考试不及格的人要待在家里继续复习不去餐馆，我们知道故事的主人公考试不及格一定是没有去的，问没有去的总共有多少人。

解题思路：简单的容斥原理，我们画一个ven图就能找出不去的人n-（a+b-c），但是要注意一下特判去两个餐厅都去的人一定要小于等于只去一个餐厅的，去餐厅的人数一定要小于总人数（我们可怜的主人公一定是不去餐厅庆祝的！）

 

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 int main() 6 { 7     int a,b,c,n,ans; 8     scanf("%d%d%d%d",&a,&b,&c,&n); 9     ans=0;10     if((a+b-c>=n)||c>a||c>b)11     {12         ans=-1;13     }14     else15     {16         ans=n-(a+b-c);17     }18     printf("%d\n",ans);19     return 0;20 }