Codeforces Round #339 (Div. 2)-CSDN博客

本文链接：https://blog.csdn.net/acm_fighting/article/details/50608842

Programmer Rostislav got seriously interested in the Link/Cut Tree data structure, which is based on Splay trees. Specifically, he is now studying the expose procedure.

Unfortunately, Rostislav is unable to understand the definition of this procedure, so he decided to ask programmer Serezha to help him. Serezha agreed to help if Rostislav solves a simple task (and if he doesn't, then why would he need Splay trees anyway?)

Given integers l, r and k, you need to print all powers of number k within range from l to r inclusive. However, Rostislav doesn't want to spent time doing this, as he got interested in playing a network game called Agar with Gleb. Help him!

Input

The first line of the input contains three space-separated integers l, r and k (1 ≤ l ≤ r ≤ 1018, 2 ≤ k ≤ 109).

Output

Print all powers of number k, that lie within range from l to r in the increasing order. If there are no such numbers, print "-1" (without the quotes).

   Sample test(s) 
 
     input 
   
1 10 2

     output 
   
1 2 4 8 

     input 
   
2 4 5

     output 
   
-1

Note

Note to the first sample: numbers 20 = 1, 21 = 2, 22 = 4, 23 = 8 lie within the specified range. The number 24 = 16 is greater then 10, thus it shouldn't be printed.

题意:给出l,r,k,输出k的i次幂(i=0,1,2,3,...)在[l,r]之间的数,如果不存在,输出-1

思路:暴力枚举k的几次方,同时注意输出-1的情况和k的n次方在long long范围内,k的n+1次方超过long long范围的情况。

#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include<set>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define inf -0x3f3f3f3f
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;

int main(){
    __int64 l,r,k;
    scanf("%I64d%I64d%I64d",&l,&r,&k);
    __int64 ans=1;
    int flag=0;
    while(ans<=r){
        if(ans>=l){
            if(flag==0){
                flag=1;
                printf("%I64d",ans);
            }
            else
                printf(" %I64d",ans);
        }
        if(r/ans>=k)
            ans*=k;
        else
            break;
    }
    if(flag==0)
        printf("-1\n");
    else
        printf("\n");
    return 0;
}

It's the year 4527 and the tanks game that we all know and love still exists. There also exists Great Gena's code, written in 2016. The problem this code solves is: given the number of tanks that go into the battle from each country, find their product. If it is turns to be too large, then the servers might have not enough time to assign tanks into teams and the whole game will collapse!

There are exactly n distinct countries in the world and the i-th country added ai tanks to the game. As the developers of the game are perfectionists, the number of tanks from each country is beautiful. A beautiful number, according to the developers, is such number that its decimal representation consists only of digits '1' and '0', moreover it contains at most one digit '1'. However, due to complaints from players, some number of tanks of one country was removed from the game, hence the number of tanks of this country may not remain beautiful.

Your task is to write the program that solves exactly the same problem in order to verify Gena's code correctness. Just in case.

Input

The first line of the input contains the number of countries n (1 ≤ n ≤ 100 000). The second line contains n non-negative integers aiwithout leading zeroes — the number of tanks of the i-th country.

It is guaranteed that the second line contains at least n - 1 beautiful numbers and the total length of all these number's representations doesn't exceed 100 000.

Output

Print a single number without leading zeroes — the product of the number of tanks presented by each country.

    Sample test(s) 
  
      input 
    
3
5 10 1

      output 
    
50

      input 
    
4
1 1 10 11

      output 
    
110

      input 
    
5
0 3 1 100 1

      output 
    
0

Note

In sample 1 numbers 10 and 1 are beautiful, number 5 is not not.

In sample 2 number 11 is not beautiful (contains two '1's), all others are beautiful.

In sample 3 number 3 is not beautiful, all others are beautiful.

题意:输入n,接下来输入n个数,这n个数的特征是其中至少有n-1个数最多一个1且其余全为0，而且这些数没有前导0.

输出这n个数相乘之后的结构。

思路：分析可知,如果这n个数中有数为0，则答案输出0.否则,因为n-1个数的输入情况一定是一个1,后面一串0，所以这n-1个数相乘结果为1000....后面一串0，0的个数很容易计算,然后便是一个数和这10000....相乘，这里要注意可能是n个数都是一个1,后面一串0的情况。

#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include<set>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define inf -0x3f3f3f3f
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
char s[1101000],s1[1101000];

int main(){
    int n,len,flag=0;
    int ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",s);
        len=strlen(s);
        if(len==1&&s[0]=='0')
            flag=1;
        else{
            int count_num1=0,count_num2=0;
            for(int j=0;j<len;j++){
                if(s[j]=='1')
                    count_num1++;
                else if(s[j]=='0')
                    count_num2++;
                else
                    count_num1+=2;
            }
            if(count_num1<=1)
                ans+=count_num2;
            else
                strcpy(s1,s);
        }
    }
    if(flag==1)
        printf("0\n");
    else{
        printf("%s",s1);
        if(s1[0]=='\0')
            printf("1");
        for(int i=1;i<=ans;i++)
            printf("0");
        printf("\n");
    }
    return 0;
}

Peter got a new snow blower as a New Year present. Of course, Peter decided to try it immediately. After reading the instructions he realized that it does not work like regular snow blowing machines. In order to make it work, you need to tie it to some point that it does not cover, and then switch it on. As a result it will go along a circle around this point and will remove all the snow from its path.

Formally, we assume that Peter's machine is a polygon on a plane. Then, after the machine is switched on, it will make a circle around the point to which Peter tied it (this point lies strictly outside the polygon). That is, each of the points lying within or on the border of the polygon will move along the circular trajectory, with the center of the circle at the point to which Peter tied his machine.

Peter decided to tie his car to point P and now he is wondering what is the area of the region that will be cleared from snow. Help him.

Input

The first line of the input contains three integers — the number of vertices of the polygon n ( $\text{[math]}$ ), and coordinates of point P.

Each of the next n lines contains two integers — coordinates of the vertices of the polygon in the clockwise or counterclockwise order. It is guaranteed that no three consecutive vertices lie on a common straight line.

All the numbers in the input are integers that do not exceed 1 000 000 in their absolute value.

Output

Print a single real value number — the area of the region that will be cleared. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $\text{[math]}$ .

     Sample test(s) 
   

       input 
     
3 0 0
0 1
-1 2
1 2

       output 
     
12.566370614359172464

       input 
     
4 1 -1
0 0
1 2
2 0
1 1

       output 
     
21.991148575128551812

Note

In the first sample snow will be removed from that area:

$\text{[math]}$

题意:给出n个点组成的多边形(n个点是顺时针或者逆时针),再给出一个中心点坐标,求这个多边形绕中心点旋转一圈所形成的面积。

思路：只要求出多边形中到中心点距离最大和最小的两个距离,面积便是两个半径所形成的圆面积相减。

#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include<set>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define inf -0x3f3f3f3f
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
#define eps 1e-8
#define PI acos(-1.0)

struct point
{
    double x;
    double y;
};

point intersection(point u1,point u2,point v1,point v2)
{
    point ret=u1;
    double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
    /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
    ret.x+=(u2.x-u1.x)*t;
    ret.y+=(u2.y-u1.y)*t;
    return ret;
}

double xmult(double x1,double y1,double x2,double y2,double x0,double y0)
{
    return (x1-x0)*(y2-y0)-(x2-x0)*(y1-y0);
}

double distance1(point p1,point p2)
{
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}

point ptoseg(point p,point l1,point l2)
{
    point t=p;
    t.x+=l1.y-l2.y,t.y+=l2.x-l1.x;
    if(xmult(l1.x,l1.y,t.x,t.y,p.x,p.y)*xmult(l2.x,l2.y,t.x,t.y,p.x,p.y)>eps)
        return distance1(p,l1)<distance1(p,l2) ? l1:l2;
    return intersection(p,t,l1,l2);
}

point s[200000];

int main(){
    point a;
    int n;
    scanf("%d%lf%lf",&n,&a.x,&a.y);
    double maxv=0,minv=99999999999.0;
    for(int i=1;i<=n;i++){
        scanf("%lf%lf",&s[i].x,&s[i].y);
        maxv=max(distance1(a,s[i]),maxv);
        if(i!=1){
            point b=ptoseg(a,s[i],s[i-1]);
            minv=min(distance1(b,a),minv);
        }
    }
    point b=ptoseg(a,s[1],s[n]);
    minv=min(minv,distance1(b,a));
    printf("%.8lf\n",maxv*maxv*PI-minv*minv*PI);
    return 0;
}

Lesha plays the recently published new version of the legendary game hacknet. In this version character skill mechanism was introduced. Now, each player character has exactly n skills. Each skill is represented by a non-negative integer ai — the current skill level. All skills have the same maximum level A.

Along with the skills, global ranking of all players was added. Players are ranked according to the so-called Force. The Force of a player is the sum of the following values:

The number of skills that a character has perfected (i.e., such that ai = A), multiplied by coefficient cf.
The minimum skill level among all skills (min ai), multiplied by coefficient cm.

Now Lesha has m hacknetian currency units, which he is willing to spend. Each currency unit can increase the current level of any skill by 1 (if it's not equal to A yet). Help him spend his money in order to achieve the maximum possible value of the Force.

Input

The first line of the input contains five space-separated integers n, A, cf, cm and m (1 ≤ n ≤ 100 000, 1 ≤ A ≤ 109, 0 ≤ cf, cm ≤ 1000,0 ≤ m ≤ 1015).

The second line contains exactly n integers ai (0 ≤ ai ≤ A), separated by spaces, — the current levels of skills.

Output

On the first line print the maximum value of the Force that the character can achieve using no more than m currency units.

On the second line print n integers a'i (ai ≤ a'i ≤ A), skill levels which one must achieve in order to reach the specified value of the Force, while using no more than m currency units. Numbers should be separated by spaces.

         Sample test(s) 
       

           input 
         
3 5 10 1 5
1 3 1

           output 
         
12
2 5 2 

           input 
         
3 5 10 1 339
1 3 1

           output 
         
35
5 5 5 

Note

In the first test the optimal strategy is to increase the second skill to its maximum, and increase the two others by 1.

In the second test one should increase all skills to maximum.

题意:给出n(有多少个技能),A(每个技能的最大值),cf,cm,m(总共的技能点数)，接下来n个技能的初始值。

求满技能的个数*cf+最小技能的点数*cm。

思路:枚举满技能的个数有多少个,接下来便是二分最小技能的值。

#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include<set>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
#define inf -0x3f3f3f3f
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
const int maxn=200100;
__int64 pre_sum[maxn],ans[maxn];
__int64 b[maxn];
struct node{
    __int64 num,id;
}a[maxn];

bool cmp1(node x,node y){
    return x.num<y.num;
}

bool cmp2(node x,node y){
    return x.id<y.id;
}

int main(){
    __int64 n,A,cf,cm;
    __int64 m;
    scanf("%I64d%I64d%I64d%I64d%I64d",&n,&A,&cf,&cm,&m);
    for(int i=1;i<=n;i++){
        scanf("%I64d",&a[i].num);
        ans[i]=a[i].num;
        a[i].id=i;
    }
    sort(a+1,a+n+1,cmp1);
    for(int i=1;i<=n;i++){
        pre_sum[i]=pre_sum[i-1]+a[i].num;   //前缀和
        b[i]=a[i].num;
    }
    b[0]=-1;
    __int64 maxv=0,ans1,ans2;
    for(int i=0;i<=n;i++){  //达到最大值的有几个
        __int64 another_m=m,another_maxv=0;
        another_m=another_m-(i*A-(pre_sum[n]-pre_sum[n-i]));//把最后几个化为最大值
        if(another_m<0)
            break;
        __int64 low=0,high=A,ans_mid=0;
        while(high>=low){   //最小值最大是多少
            __int64 mid=(low+high)/2;
            int count_num=lower_bound(b+1,b+n+1,mid)-b;
            if(count_num>=n-i+1)
                count_num=n-i+1;
            if(mid*(count_num-1)-pre_sum[count_num-1]<=another_m){
                ans_mid=mid;
                low=mid+1;
            }
            else
                high=mid-1;
        }
        if(cf*i+ans_mid*cm>=maxv){
            maxv=cf*i+ans_mid*cm;
            ans1=i;     //有几个最大值
            ans2=ans_mid;   //最小值为多少
        }
    }
    printf("%I64d\n",maxv);
    m=m-(ans1*A-(pre_sum[n]-pre_sum[n-ans1]));
    for(int i=n-ans1+1;i<=n;i++)
        a[i].num=A;
    for(int i=1;a[i].num<ans2;i++){
        m=m-(ans2-a[i].num);
        a[i].num=ans2;
    }
    if(m>0)
        a[1].num=min(a[1].num+m,A);
    sort(a+1,a+n+1,cmp2);
    printf("%d",a[1].num);
    for(int i=2;i<=n;i++)
        printf(" %d",a[i].num);
    printf("\n");
    return 0;
}