CF Educational Codeforces Round 15

A. Maximum Increase

You are given array consisting of n integers. Your task is to find the maximum length of an increasing subarray of the given array.

A subarray is the sequence of consecutive elements of the array. Subarray is called increasing if each element of this subarray strictly greater than previous.

Input

The first line contains single positive integer n ($1 \leq n \leq 10^5$) — the number of integers.

The second line contains n positive integers $a_1$, $a_2$, …, $a_n$ ($1 \leq a_i \leq 10^9$).

OutPut

Print the maximum length of an increasing subarray of the given array.

Examples

input
5
1 7 2 11 15
output
3

input
6
100 100 100 100 100 100
output
1

input
3
1 2 3
output
3

题解

题意大致是最大的连续上升连续子序列长度
简单判断一下连续的子序列长度，然后求一个max就可以了

//author: CHC
//First Edit Time:	2016-07-29 23:04
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1e+5 + 1000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
int A[MAXN],n;
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&A[i]);
        int cnt = 1;
        int mcnt = 1;
        for(int i=1;i<n;i++)
        {
            if(A[i]<A[i+1])
            {
                ++cnt;
            }
            else
            {
                cnt = 1;
            }
            mcnt = max(mcnt,cnt);
        }
        printf("%d\n",mcnt);
    }
    return 0;
}

B. Powers of Two

You are given n integers $a_1$, $a_2$, …, $a_n$. Find the number of pairs of indexes i, j (i < j) that $a_i + a_j$ is a power of 2 (i. e. some integer x exists so that $a_i + a_j = 2^x$).

Input

The first line contains the single positive integer n ($1 \leq n \leq 10^5$) — the number of integers.

The second line contains n positive integers $a_1$, $a_2$, …, $a_n$ ($1 \leq a_i \leq 10^9$).

Output

Print the number of pairs of indexes i, j (i < j) that $a_i$ + $a_j$ is a power of 2.

Examples

input
4
7 3 2 1
output
2

input
3
1 1 1
output
3

题解

题意大致为给一个数列，求这个数列中两数和为2的次方的对数个数。
因为其数列的值范围都在$10^9$，不会超过$2^31$，因此对于第i个数，求在$i+1 \leq j \leq n$之间，有多少个j满足$a_i + a_j$的结果为2的次方
我们首先将数列排序，然后依次枚举判断，加上即可

//author: CHC
//First Edit Time:	2016-07-29 23:11
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1e+5 + 1000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
LL A[MAXN];
int n;
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
            scanf("%I64d",&A[i]);
        sort(A+1,A+1+n);
        LL cnt = 0;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<32;j++)
            {
                if((1LL<<j)>A[i])
                {
                    LL x = (1LL<<j)-A[i];
                    int pos = lower_bound(A+i+1,A+1+n,x) - A;
                    if(pos>=1&&pos<=n&&A[pos]==x)
                    {
                        int pos1 = lower_bound(A+1,A+1+n,x+1) - A;
                        //printf("%d %d %d\n",i,pos,pos1);
                        cnt += (LL)(pos1 - pos);
                    }
                }
            }
        }
        printf("%I64d\n",cnt);
    }
    return 0;
}

C. Cellular Network

You are given n points on the straight line — the positions (x-coordinates) of the cities and m points on the same line — the positions (x-coordinates) of the cellular towers. All towers work in the same way — they provide cellular network for all cities, which are located at the distance which is no more than r from this tower.

Your task is to find minimal r that each city has been provided by cellular network, i.e. for each city there is at least one cellular tower at the distance which is no more than r.

If r = 0 then a tower provides cellular network only for the point where it is located. One tower can provide cellular network for any number of cities, but all these cities must be at the distance which is no more than r from this tower.

Input

The first line contains two positive integers n and m ($1 \leq n,m \leq 10^5$) — the number of cities and the number of cellular towers.

The second line contains a sequence of n integers a1, a2, …, an ($-10^9 \leq a_i \leq 10^9$) — the coordinates of cities. It is allowed that there are any number of cities in the same point. All coordinates ai are given in non-decreasing order.

The third line contains a sequence of m integers b1, b2, …, bm ($-10^9 \leq a_i \leq 10^9$) — the coordinates of cellular towers. It is allowed that there are any number of towers in the same point. All coordinates bj are given in non-decreasing order.

Output

Print minimal r so that each city will be covered by cellular network.

Examples

input
3 2
-2 2 4
-3 0
output
4

input
5 3
1 5 10 14 17
4 11 15
output
3

题解

题目大意为在一条直线上，有n个城市和m个能量塔，每个能量塔可以保护距离在r之内的城市，然后给出n个城市的x坐标和m个能量塔的x坐标，然后求能够覆盖所有城市的最小的r
因为其范围比较大，并且，r是单调的，若r可以覆盖所有的城市的话，那么r+1一定可以覆盖所有的城市，因此我们可以确定一个区间(最大r和最小l的区间)，然后在这个区间内，确定一个点mid，判断r=mid时能否覆盖所有的城市
判断的方法非常重要，问题转化为求 给定一个r，n个城市和m个能量塔，这m个能量塔能否覆盖完所有的城市
我们可以枚举这n个城市，然后判断这n个城市在r的范围内有没有能量塔，若在r的范围内没有能量塔，那么就一定不行，若所有的城市在r范围内都有能量塔，那么一定可行

//author: CHC
//First Edit Time:	2016-07-29 23:28
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1e+5 + 1000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
int n,m;
LL A[MAXN],B[MAXN];
LL abss(LL x)
{
    if(x<0) return -x;
    else return x;
}
bool check(LL ans)
{
    for(int i=1;i<=n;i++)
    {
        int pos = lower_bound(B+1,B+1+m,A[i]-ans) - B;
        if(1<=pos&&pos<=m&&abss(B[pos]-A[i])<=ans);
        else return false;
    }
    return true;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%I64d",&A[i]);
    for(int i=1;i<=m;i++)
        scanf("%I64d",&B[i]);
    sort(A+1,A+1+n);
    sort(B+1,B+1+m);
    LL l=0,r=(1LL<<36),ans=0;
    while(l<=r)
    {
        LL mid=(l+r)>>1;
        if(check(mid))
        {
            ans=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%I64d\n",ans);
    return 0;
}

D. Road to Post Office

Vasiliy has a car and he wants to get from home to the post office. The distance which he needs to pass equals to d kilometers.

Vasiliy’s car is not new — it breaks after driven every k kilometers and Vasiliy needs t seconds to repair it. After repairing his car Vasiliy can drive again (but after k kilometers it will break again, and so on). In the beginning of the trip the car is just from repair station.

To drive one kilometer on car Vasiliy spends a seconds, to walk one kilometer on foot he needs b seconds (a < b).

Your task is to find minimal time after which Vasiliy will be able to reach the post office. Consider that in every moment of time Vasiliy can left his car and start to go on foot.

Input

The first line contains 5 positive integers d, k, a, b, t ($1 \leq d \leq 10^12$; $1 \leq k, a, b, t \leq 10^6$ ; a < b), where:

d — the distance from home to the post office;
k — the distance, which car is able to drive before breaking;
a — the time, which Vasiliy spends to drive 1 kilometer on his car;
b — the time, which Vasiliy spends to walk 1 kilometer on foot;
t — the time, which Vasiliy spends to repair his car.

Output

Print the minimal time after which Vasiliy will be able to reach the post office.

Examples

input
5 2 1 4 10
output
14

input
5 2 1 4 5
output
13

题解

题目大意为Vas想去d公里以外的邮局，然后它有一辆车，但这辆车有问题，它每走k公里就必须要修t秒才能继续走
车每走1公里需要话费a秒时间，它也可以走路，走路每走1公里需要b秒的时间
问它到达邮局最少的时间，车在起点的时候是好的
$1 \leq d \leq 10^12$; $1 \leq k, a, b, t \leq 10^6$ ; a < b

一开始一定用车走k公里，然后走了k公里之后，需要判断在(d-k)/k*k的路程里，车走比较划算还是人走比较划算，然后再判断最后的(d-k)%k这段路人走还是车走，然后就可以计算出了

//author: CHC
//First Edit Time:	2016-07-30 00:24
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=1e+4;
const int MAXM=1e+5;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
LL d,k,a,b,t;
int main()
{
    scanf("%I64d%I64d%I64d%I64d%I64d",&d,&k,&a,&b,&t);
    LL ans = k*a;
    if(k>d)
    {
        ans = d*a;
    }
    //printf("%I64d\n",ans);
    if(k*a+t>b*k)
    {
        ans += (d-k)/k*k*b;
    }
    else
    {
        ans += (d-k)/k*(k*a+t);
    }
    //printf("%I64d\n",ans);
    if((d-k)>0&&(d-k)%k!=0)
    {
        if(t+(d-k)%k*a > (d-k)%k*b)
        {
            ans += (d-k)%k*b;
        }
        else
        {
            ans += t+(d-k)%k*a;
        }
    }
    printf("%I64d\n",ans);
    return 0;
}