模拟赛 2018 Benelux Algorithm Programming Contest (BAPC 18)（部分题）

A题

After the festive opening of your new store, the Boutique store for Alternative Paramedicine and Cwakhsahlvereigh, to your disappointment you find out that you are not mak- ing as many sales as you had hoped. To remedy this, you decide to run a special offer: you will mark some subset of the n items for sale in your store as participating in the offer, and if people buy exactly two of these items, and the cost of these items is strictly more than X euros, you will give them a free complimentary unicorn horn! Since you recently found out all your unicorn horns are really narwahl tusks, you decide to rig the offer by picking the participating items in such a way that no one can earn a horn anyway. To make sure no one becomes suspicious, you want to mark as many items as possible as participating in the offer. Input • On the first line two integers, 1 ≤ n ≤ 10 5 , the number of items for sale in your store, and 1 ≤ X ≤ 10 9 , the minimum cost specified in the statement. • On the second line n positive integers, each at most 10 9 . These are the prices of the items in the store. Output Print the maximum number of items you can mark as part of your special offer, without anyone actually being able to receive a horn. Sample Input 1 Sample Output 1 5 6 1 2 3 4 5 3 Sample Input 2 Sample Output 2 5 10 4 8 1 9 7 2 Sample Input 3 Sample Output 3 4 10 1 3 1 7 4 4 Problem A: A Prize No One Can Win Sample Input 4 Sample Output 4 1 5 6 1

#include<bits/stdc++.h>

using namespace std;

inline int  read()
{
    long long x=0,f=1;
    char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())
    if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())
    x=x*10+ch-48;
    return x*f;
}
int a[100005];
int main()
{
  int n,m;
  n=read(),m=read();
  for(int i=1;i<=n;i++)
  {
      a[i]=read();
  }
  sort(a+1,a+1+n);
  if(n==1)
  {
      cout<<1<<endl;
      return 0;
  }
  for(int i=n;i>=2;)
  {
      if(a[i]+a[i-1]>m)
      {
          i--;
      }
      else
      {
          cout<<i<<endl;
          return 0;
      }
  }
  cout<<1<<endl;
    return 0;
}

B题

B Birthday Boy Time limit: 1s Bobby has just joined a new company, and human resources has asked him to note his birthday on the office calendar. Bobby the Birthday Boy wants to feel special! Also, Bobby the Birthday Boy does not mind lying for attention. He notices that the longer people have not celebrated a birthday or eaten cake, the more they like it when a new one comes around. So he wants to pick his birthday in such a way that the longest period of time without a birthday possible has just passed. Of course he does not want to share his birthday with any colleague, either. Can you help him make up a fake birthday to make him feel as special as possible? Bobby does not care about leap years: you can assume every year is not a leap year, and that no one has a birthday on the 29th of February. In case of a tie, Bobby decides to fill in the date that is soonest (strictly) after the current date, the 27th of October, because that means he will get to celebrate his birthday as soon as possible. Figure 1: Sample case 2. Calendar is from http://printablecalendarholidays.com. Input • One line with a number 1 ≤ n ≤ 100, the number of colleagues Bobby has in his new office. • Then follow n lines, each line corresponding to one coworker. Each line gives the name of the colleague (using at most 20 upper or lower case letters) separated from their birthday date by a space. The date is in format mm-dd. 6 Problem B: Birthday Boy Output Print the fake birthday date (format: mm-dd) chosen by Bobby. Sample Input 1 Sample Output 1 3 Henk 01-09 Roos 09-20 Pietje 11-11 09-19 Sample Input 2 Sample Output 2 16 Henk 01-09 Luc 12-31 Jan 03-22 Roos 09-20 Pietje 11-11 Anne 02-28 Pierre 09-25 Dan 12-15 Lieze 11-17 Charlotte 05-01 Lenny 08-02 Marc 04-25 Martha 06-12 John 03-26 Matthew 01-20 John 01-20 08-01 Sample Input 3 Sample Output 3 3 JohnIII 04-29 JohnVI 10-28 JohnIIX 04-28 04-27 Sample Input 4 Sample Output 4 3 CharlesII 04-30 CharlesV 10-29 CharlesVII 04-29 10-28

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int N=105;
struct node
{
    int m;
    int d;
    int day;
} getdays[N];
string name;
int sto[N];
int a[N];
int month[14]= {31,28,31,30,31,30,31,31,30,31,30,31};
bool cmp(node a,node b)
{
    return a.day<b.day;
}
int getsum(int mon,int day)
{
    int ans=0;
    for(int i=0; i<mon-1; i++) ans+=month[i];
    ans+=day;
    return ans;
}
int main()
{
    int n;
    char u;
    scanf("%d",&n);
    if(n==1)
    {
        cin>>name;
        cin>>getdays[1].m>>u>>getdays[1].d;
        int  i,sum=getsum(getdays[1].m,getdays[1].d)-1;
        for( i=0; i<12; i++)
        {
            if(sum-month[i]>=0) sum-=month[i];
            else break;
        }
        if(sum==0)
        {
            i--;
            if(i==-1) i=11;
            sum=month[i];
        }
        printf("%02d-%02d\n",i+1,sum);
        return 0;
    }
    for(int i=1; i<=n; i++)
    {
        cin>>name;
        cin>>getdays[i].m>>u>>getdays[i].d;
        getdays[i].day=getsum(getdays[i].m,getdays[i].d);
    }
    sort(getdays+1,getdays+n+1,cmp);
    sto[1]=365-getdays[n].day+getdays[1].day;
    for(int i=2; i<=n; i++) sto[i]=getdays[i].day-getdays[i-1].day;
    int maxx=0;
    for(int i=1; i<=n; i++) maxx=max(maxx,sto[i]);
    int cnt=0;
    for(int i=1; i<=n; i++) if(maxx==sto[i]) a[++cnt]=i;
    if(cnt==1)
    {
        int i,sum=sto[a[1]]+getdays[a[1]-1].day-1;
        if(a[1]==1) sum=getdays[1].day-1;
        sum=(sum+365)%365;
        for(i=0; i<12; i++)
        {
            if(sum-month[i]>=0) sum-=month[i];
            else break;
        }
        if(sum==0)
        {
            i--;
            if(i==-1) i=11;
            sum=month[i];
        }
        printf("%02d-%02d\n",i+1,sum);
    }
    else
    {
        int flag=0,minn1=inf,minn2=inf,pos;
        for(int i=1; i<=cnt; i++)
        {
            int tmp=sto[a[i]]+getdays[a[i]-1].day-1;
            if(tmp>365) tmp-=365;
            if(tmp>getsum(10,27))
            {
                if(tmp-getsum(10,27)<minn1)
                {
                    minn1=tmp-getsum(10,27);
                    flag=i;
                }
            }
            else
            {
                if((tmp-getsum(10,27))<minn2)
                {
                    minn2=tmp-getsum(10,27);
                    pos=i;
                }
            }
        }
        int i,sum;
        if(minn1!=inf)
        {
            i,sum=(sto[a[flag]]+getdays[a[flag]-1].day)-1;
            sum=(sum+365)%365;
            for( i=0; i<12; i++)
            {
                if(sum-month[i]>=0) sum-=month[i];
                else break;
            }
        }
        else
        {
            sum=getdays[pos].day-1;
            sum=(sum+365)%365;
            for( i=0; i<12; i++)
            {
                if(sum-month[i]>=0) sum-=month[i];
                else break;
            }
        }
        if(sum==0)
        {
            i--;
            if(i==-1) i=11;
            sum=month[i];
        }
        printf("%02d-%02d\n",i+1,sum);
    }
    return 0;
}

C题

Problem C: Cardboard Container 7 C Cardboard Container Time limit: 1s Fidget spinners are so 2017; this years’ rage are fidget cubes. A fidget cube is a cube with unit side lengths, which you hold in your hand and fidget with. Kids these days, right? You work in the planning department for a company that creates and ships fidget cubes. Having done some market analysis, you found that your customers want to receive shipments of exactly V fidget cubes. This means you have to design a container that will hold exactly V fidget cubes. Since fidget cubes are very fragile, you cannot have any empty space in your container. If there is empty space, they might move around, bump into each other and get damaged. Because of this, you decide to ship the fidget cubes in a rectangular cardboard box. The cost of a cardboard box is proportional to its surface area, costing exactly one unit of money per square unit of surface area. Of course you want to spend as little money as possible. Subject to the above constraints, how much money do you have to spend on a box for V fidget cubes? Input The input contains a single integer, 1 ≤ V ≤ 10 6 , the number of fidget cubes for which you need to build a box. Output Print the cost of the cheapest rectangular box as specified in the statement. Sample Input 1 Sample Output 1 1 6 Sample Input 2 Sample Output 2 4 16 Sample Input 3 Sample Output 3 3 14 Sample Input 4 Sample Output 4 5913 2790

#include<bits/stdc++.h>

using namespace std;

inline int  read()
{
    long long x=0,f=1;
    char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())
    if(ch=='-')f=-1;
    for(;ch>='0'&&ch<='9';ch=getchar())
    x=x*10+ch-48;
    return x*f;
}
int v;
int main()
{
    v=read();
    int temp=0;
    for(int i=1;i*i*i<=v;i++)
    {

        if(i*i*i==v)
        {
            cout<<(6*i*i)<<endl;
            return 0;
        }
       else  if(i*i*i>v)
        {
            temp=i;
            break;
        }
    }
    int ans=99999999;
    for(int i=1;i<=v;i++)
    {
        for(int j=1;j<=v;j++)
        {
            if(i*j>v)break;
            for(int k=1;k<=v;k++)
            {
                if(i*j*k>v)break;
                if(i*j*k==v)
                {
                    ans=min(ans,2*(i*j+i*k+j*k));
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

F题

F Financial Planning Time limit: 3s Being a responsible young adult, you have decided to start planning for retirement. Doing some back-of-the-envelope calculations, you figured out you need at least M euros to retire comfortably. You are currently broke, but fortunately a generous gazil- lionaire friend has offered to lend you an arbitrary amount of money (as much as you need), without interest, to invest in the stock market. After mak- ing some profits you will then return the original sum to your friend, leaving you with the remainder. Available to you are n investment opportunities, the i-th of which costs c i euros. You also used your computer science skills to predict that the i-th investment will earn you p i euros per day. What is the minimum number of days you need before you can pay back your friend and retire? You can only invest once in each investment opportunity, but you can invest in as many different investment opportunities as you like. For example, consider the first sample. If you buy only the second investment (which costs 15 euros) you will earn p 2 = 10 euros per day. After two days you will have earned 20 euros, exactly enough to pay off your friend (from whom you borrowed 15 euros) and retire with the remaining profits (5 euros). There is no way to make a net amount of 5 euros in a single day, so two days is the fastest possible. Input • The first line contains the number of investment options 1 ≤ n ≤ 10 5 and the minimum amount of money you need to retire 1 ≤ M ≤ 10 9 . • Then, n lines follow. Each line i has two integers: the daily profits of this investment 1 ≤ p i ≤ 10 9 and its initial cost 1 ≤ c i ≤ 10 9 . Output Print the minimum number of days needed to recoup your investments and retire with at least M euros, if you follow an optimal investment strategy. Sample Input 1 Sample Output 1 2 5 4 10 10 15 2 Problem F: Financial Planning 13 Sample Input 2 Sample Output 2 4 10 1 8 3 12 4 17 10 100 6 Sample Input 3 Sample Output 3 3 5 4 1 9 10 6 3 1

#include <bits/stdc++.h>
#define ll long long
const int maxn=100010;
using namespace std;
ll n,t;
ll a[maxn],w[maxn];
bool judge(ll T)
{
	ll pro=0;
	ll o[maxn]={0};
	for (int i=1;i<=n;++i)
	 o[i]=(a[i]*T-w[i]);
	for (int i=1;i<=n;++i)
	 if (o[i]>0) pro+=o[i];
	 if (pro>=t) return true;
	     else return false;
}
int main()
{
    cin>>n>>t;
    ll ret=-999;
    for (int i=1;i<=n;++i)
     {
         cin>>a[i]>>w[i];
         ret=max(ret,(t+w[i])/a[i]+1);
     }
     ll l=1,r=0,mid;
      r=ret;
	 while (l<=r)
	 {
     	 mid=(l+r)/2;
		 if (judge(mid))
			{
                r=mid-1;
		    }
		  else l=mid+1;
	 }
	 cout<<r+1<<endl;
	return 0;
}

J题

J Janitor Troubles Time limit: 1s While working a night shift at the university as a jani- tor, you absent-mindedly erase a blackboard covered with equations, only to realize afterwards that these were no ordinary equations! They were the notes of the venerable Professor E. I. N. Stein who earlier in the day solved the elusive maximum quadrilateral problem! Quick, you have to redo his work so no one noticed what happened. The maximum quadrilateral problem is quite easy to state: given four side lengths s 1 ,s 2 ,s 3 and s 4 , find the maxiumum area of any quadrilateral that can be constructed using these lengths. A quadrilateral is a polygon with four vertices. Input The input consists of a single line with four positive integers, the four side lengths s 1 , s 2 , s 3 , and s 4 . It is guaranteed that 2s i < P 4 j=1 s j , for all i, and that 1 ≤ s i ≤ 1000. Output Output a single floating point number, the maximal area as described above. Your answer must be accurate to an absolute or relative error of at most 10 −6 . Sample Input 1 Sample Output 1 3 3 3 3 9 Sample Input 2 Sample Output 2 1 2 1 1 1.299038105676658 Sample Input 3 Sample Output 3 2 2 1 4 3.307189138830738

#include<bits/stdc++.h>

using namespace std;


int main()
{
    double a,b,c,d;
    cin>>a>>b>>c>>d;
    double k=(a*b+c*d)/2.000;
    double ans=0;
    double f=1-(a*a+b*b-c*c-d*d)*(a*a+b*b-c*c-d*d)/((2*a*b+2*c*d)*(2*a*b+2*c*d));
    f=sqrt(f);
    ans=f*k;
    cout<<setiosflags(ios::fixed)<<setprecision(15)<<ans<<endl;
    return 0;
}