集训第一次周赛题目及题解

傷城~ 2022-01-09 15:15 211阅读 0赞

# A. Help Vasilisa the Wise 2 #

##### Time Limit : 4000/2000ms (Java/Other) Memory Limit : 524288/262144K (Java/Other) #####

##### Total Submission(s) : 42 Accepted Submission(s) : 12 #####

Problem Description

Vasilisa the Wise from the Kingdom of Far Far Away got a magic box with a secret as a present from her friend Hellawisa the Wise from the Kingdom of A Little Closer. However, Vasilisa the Wise does not know what the box's secret is, since she cannot open it again. She hopes that you will help her one more time with that.

The box's lock looks as follows: it contains 4 identical deepenings for gems as a 2×2 square, and some integer numbers are written at the lock's edge near the deepenings. The example of a lock is given on the picture below.

![93c8bcc9e87b70a668d8a3b3e996a33265cc940f.png][]

The box is accompanied with 9 gems. Their shapes match the deepenings' shapes and each gem contains one number from 1 to 9 (each number is written on exactly one gem). The box will only open after it is decorated with gems correctly: that is, each deepening in the lock should be filled with exactly one gem. Also, the sums of numbers in the square's rows, columns and two diagonals of the square should match the numbers written at the lock's edge. For example, the above lock will open if we fill the deepenings with gems with numbers as is shown on the picture below.

![18dde523e7a53fa62cd21281733d664a7ae608b6.png][]

Now Vasilisa the Wise wants to define, given the numbers on the box's lock, which gems she should put in the deepenings to open the box. Help Vasilisa to solve this challenging task.

Input

The input contains numbers written on the edges of the lock of the box. The first line contains space-separated integers *r*1 and *r*2 that define the required sums of numbers in the rows of the square. The second line contains space-separated integers *c*1 and *c*2 that define the required sums of numbers in the columns of the square. The third line contains space-separated integers *d*1 and *d*2 that define the required sums of numbers on the main and on the side diagonals of the square (1≤*r*1,*r*2,*c*1,*c*2,*d*1,*d*2≤20). Correspondence between the above 6 variables and places where they are written is shown on the picture below. For more clarifications please look at the second sample test that demonstrates the example given in the problem statement.

![986b79e3875161e9ba76e35e0ceb51da9b971684.png][]

Output

Print the scheme of decorating the box with stones: two lines containing two space-separated integers from 1 to 9. The numbers should be pairwise different. If there is no solution for the given lock, then print the single number "\-1" (without the quotes).

If there are several solutions, output any.

Sample Input

3 7
    4 6
    5 5
    11 10
    13 8
    5 16

Sample Output

1 2
    3 4
    4 7
    9 1

题目意思从图上可以很容易的看懂，注意的是计算的时候从一个方面计算的话可能会漏掉数据，送多个数据进行计算，其次就是考虑计算结果为0的情况。。。。wa了几次。代码：

#include <stdio.h>
    int main()
    {
        int r1,r2,c1,c2,d1,d2;
        double a,b,c,d;
        while(scanf("%d%d%d%d%d%d",&r1,&r2,&c1,&c2,&d1,&d2)==6)
        {
            double aa,bb,cc,dd,aaa,bbb,ccc,ddd;
            if(r1-d1>0)
            {
                b=(r1-d1+c2)/2;
                a=r1-b;
                c=c1-a;
                d=c2-b;
            }
            else
            {
                d=(d1-r1+c2)/2;
                b=c2-d;
                a=r1-b;
                c=r2-d;
            }
            if(d2-c1>0)
            {
                bb=(d2-c1+r1)/2;
                aa=r1-bb;
                dd=c2-bb;
                cc=r2-dd;
            }
            else
            {
                cc=(c1-d2+r1)/2;
                dd=r2-cc;
                aa=c1-cc;
                bb=c2-dd;
            }
            if(r2-c2>0){
                ccc=(r2-c2+d2)/2;
                ddd=r2-ccc;
                aaa=c1-ccc;
                bbb=c2-ddd;
            }
            else
            {
                bbb=(c2-r2+d2)/2;
                aaa=r1-bbb;
                ddd=c2-bbb;
                ccc=r2-ddd;
            }
            if(a==aa&&c==ccc&&d==ddd&&bb==bbb&&a>0&&b>0&&c>0&&d>0)
            {
                    printf("%.0lf %.0lf\n",a,b);
                    printf("%.0lf %.0lf\n",c,d);
            }
            else
                printf("-1\n");
    
        }
        return 0;
    }

[Meeting][]

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65535KB</td> 
   <td>&nbsp;</td> 
   <td><strong>64bit IO Format:</strong>&nbsp;%I64d &amp; %I64u</td> 
  </tr> 
 </tbody> 
</table>

\[[Submit][]\] \[Go Back\] \[[Status][]\]

Description

The Super Duper Secret Meeting of the Super Duper Secret Military Squad takes place in a Super Duper Secret Place. The place is an infinite plane with introduced Cartesian coordinate system. The meeting table is represented as a rectangle whose sides are parallel to the coordinate axes and whose vertexes are located at the integer points of the plane. At each integer point which belongs to the table perimeter there is a chair in which a general sits.

Some points on the plane contain radiators for the generals not to freeze in winter. Each radiator is characterized by the number *r**i* — the radius of the area this radiator can heat. That is, if the distance between some general and the given radiator is less than or equal to *r**i*, than the general feels comfortable and warm. Here distance is defined as Euclidean distance, so the distance between points (*x*1, *y*1) and (*x*2, *y*2) is ![1327020407.png][]

Each general who is located outside the radiators' heating area can get sick. Thus, you should bring him a warm blanket. Your task is to count the number of warm blankets you should bring to the Super Duper Secret Place.

The generals who are already comfortable do not need a blanket. Also the generals never overheat, ever if they are located in the heating area of several radiators. The radiators can be located at any integer points on the plane, even inside the rectangle (under the table) or on the perimeter (directly under some general). Even in this case their radius does not change.

Input

The first input line contains coordinates of two opposite table corners xa, ya, xb, yb (xa ≠ xb, ya ≠ yb). The second line contains integer n — the number of radiators (1 ≤ n ≤ 10^3). Then n lines contain the heaters' coordinates as "xi yi ri", the numbers are separated by spaces. All input data numbers are integers. The absolute value of all coordinates does not exceed 1000, 1 ≤ ri ≤ 1000. Several radiators can be located at the same point.

Output

Print the only number — the number of blankets you should bring.

Sample Input

2 5 4 2
    3
    3 1 2
    5 3 1
    1 3 2
    5 2 6 3
    2
    6 2 2
    6 5 3

Sample Output

4
    0

题意：一个飞机上的座位需要供热，首先给出两点的坐标是矩形的对角点，对这个矩形的每隔1个单位都有一个座位，给出几个供热源的坐标及供热半径，求其有多少个座位供不到热。 用结构体存需要供热的点，加一个判断是否以供热的变量。然后用点到点的距离是否小于半径求出即可。代码：

#include <cstdio>
    #include <cmath>
    #define dis(x1,y1,x2,y2) sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))
    struct Node //存放边上椅子的点
    {
        int x,y;  //点的坐标
        bool ok;   //是否已被覆盖
    };
    Node point[100005];
    
    int main()
    {
        int a,b,c,d;
        while(~scanf("%d%d%d%d",&a,&b,&c,&d))
        {
            if(a>c)
            {
                int t=a;a=c;c=t;
            }
            int j=0;
            for(int i=a;i<=c;i++)
            {
                point[j].x=i;point[j].y=b;point[j++].ok=false;
                point[j].x=i;point[j].y=d;point[j++].ok=false;
            }
            if(b>d)
            {
                int t=b;b=d;d=t;
            }
            for(int i=b+1;i<d;i++)
            {
                point[j].x=a;point[j].y=i;point[j++].ok=false;
                point[j].x=c;point[j].y=i;point[j++].ok=false;
            }
            int n,count=0;
            double ax,ay,r;
            scanf("%d",&n);
            while(n--)
            {
                scanf("%lf%lf%lf",&ax,&ay,&r);
                for(int i=0;i<j;i++)
                {
                  //  printf("%d %d\n",point[i].x,point[i].y);
                   // printf("%lf  ",dis(point[i].x,point[i].y,ax,ay));
                    if(!point[i].ok&&r>=dis(point[i].x,point[i].y,ax,ay))
                    {count++;point[i].ok=true; }
                }
            }
            printf("%d\n",j-count);
        }
        return 0;
    }

# A. Arrival of the General #

##### Time Limit : 4000/2000ms (Java/Other) Memory Limit : 524288/262144K (Java/Other) #####

##### Total Submission(s) : 40 Accepted Submission(s) : 12 #####

Problem Description

A Ministry for Defense sent a general to inspect the Super Secret Military Squad under the command of the Colonel SuperDuper. Having learned the news, the colonel ordered to all *n* squad soldiers to line up on the parade ground.

By the military charter the soldiers should stand in the order of non-increasing of their height. But as there's virtually no time to do that, the soldiers lined up in the arbitrary order. However, the general is rather short-sighted and he thinks that the soldiers lined up correctly if the first soldier in the line has the maximum height and the last soldier has the minimum height. Please note that the way other solders are positioned does not matter, including the case when there are several soldiers whose height is maximum or minimum. Only the heights of the first and the last soldier are important.

For example, the general considers the sequence of heights (4, 3, 4, 2, 1, 1) correct and the sequence (4, 3, 1, 2, 2) wrong.

Within one second the colonel can swap any two neighboring soldiers. Help him count the minimum time needed to form a line-up which the general will consider correct.

Input

The first input line contains the only integer *n* (2≤*n*≤100) which represents the number of soldiers in the line. The second line contains integers *a*1,*a*2,...,*a**n*(1≤*a**i*≤100) the values of the soldiers' heights in the order of soldiers' heights' increasing in the order from the beginning of the line to its end. The numbers are space-separated. Numbers *a*1,*a*2,...,*a**n* are not necessarily different.

Output

Print the only integer the minimum number of seconds the colonel will need to form a line-up the general will like.

Sample Input

4
    33 44 11 22
    7
    10 10 58 31 63 40 76

Sample Output

2
    10

题目意思就是如通过对任意相邻两个数据的交换使得第一个值最大最后一个值最小的移动次数，判断一下就可以，很简单的水题。代码：

#include <stdio.h>
    #include <cstring>
    int a[500];
    int main()
    {
        int n,min,mini,max,maxi,tmp;
        while(~scanf("%d",&n))
        {
            if(0>=n) continue;
            int count;
            memset(a,0,sizeof(a));
            max=-999999;min=999999;
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&tmp);
                a[i]=tmp;
                if(tmp>max)
                {
                    max=tmp;
                    maxi=i;
                }
                if(min>=tmp)
                {
                    min=tmp;
                    mini=i;
                }
            }
            if(mini<maxi)
            {
                count=n-mini+maxi-2;
            }
            else if(mini==maxi)
                count=0;
            else
            {
                if(maxi==1)
                    count=n-mini;
                else if(mini==n)
                    count=maxi-1;
                else
                    count=n-mini+maxi-1;
            }
            printf("%d\n",count);
    
        }
        return 0;
    }

[Help Kingdom of Far Far Away 2][]

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;2000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;262144KB</td> 
   <td>&nbsp;</td> 
   <td><strong>64bit IO Format:</strong>&nbsp;%I64d &amp; %I64u</td> 
  </tr> 
 </tbody> 
</table>

\[[Submit][Submit 1]\] \[Go Back\] \[[Status][Status 1]\]

Description

For some time the program of rounding numbers that had been developed by the Codeforces participants during one of the previous rounds, helped the citizens of Far Far Away to convert numbers into a more easily readable format. However, as time went by, the economy of the Far Far Away developed and the scale of operations grew. So the King ordered to found the Bank of Far Far Away and very soon even the rounding didn't help to quickly determine even the order of the numbers involved in operations. Besides, rounding a number to an integer wasn't very convenient as a bank needed to operate with all numbers with accuracy of up to 0.01, and not up to an integer.

The King issued yet another order: to introduce financial format to represent numbers denoting amounts of money. The formal rules of storing a number in the financial format are as follows:

*  A number contains the integer part and the fractional part. The two parts are separated with a character "." (decimal point).
 *  To make digits in the integer part of a number easier to read, they are split into groups of three digits, starting from the least significant ones. The groups are separated with the character "," (comma). For example, if the integer part of a number equals 12345678, then it will be stored in the financial format as 12,345,678
 *  In the financial format a number's fractional part should contain exactly two digits. So, if the initial number (the number that is converted into the financial format) contains less than two digits in the fractional part (or contains no digits at all), it is complemented with zeros until its length equals 2. If the fractional part contains more than two digits, the extra digits are simply discarded (they are not rounded: see sample tests).
 *  When a number is stored in the financial format, the minus sign is not written. Instead, if the initial number had the minus sign, the result is written in round brackets.
 *  Please keep in mind that the bank of Far Far Away operates using an exotic foreign currency — snakes ($), that's why right before the number in the financial format we should put the sign "$". If the number should be written in the brackets, then the snake sign should also be inside the brackets.

For example, by the above given rules number 2012 will be stored in the financial format as "$2,012.00" and number -12345678.9 will be stored as "($12,345,678.90)".

The merchants of Far Far Away visited you again and expressed much hope that you supply them with the program that can convert arbitrary numbers to the financial format. Can you help them?

Input

The input contains a number that needs to be converted into financial format. The number's notation length does not exceed 100 characters, including (possible) signs "\-" (minus) and "." (decimal point). The number's notation is correct, that is:

*  The number's notation only contains characters from the set \{"0" – "9", "\-", "."\}.
 *  The decimal point (if it is present) is unique and is preceded and followed by a non-zero quantity on decimal digits
 *  A number cannot start with digit 0, except for a case when its whole integer part equals zero (in this case the integer parts is guaranteed to be a single zero: "0").
 *  The minus sign (if it is present) is unique and stands in the very beginning of the number's notation
 *  If a number is identically equal to 0 (that is, if it is written as, for example, "0" or "0.000"), than it is not preceded by the minus sign.
 *  The input data contains no spaces.
 *  The number's notation contains at least one decimal digit.

Output

Print the number given in the input in the financial format by the rules described in the problem statement.

Sample Input

Input

2012

Output

$2,012.00

Input

0.000

Output

$0.00

Input

-0.00987654321

Output

($0.00)

Input

-12345678.9

Output

($12,345,678.90)

Hint

Pay attention to the second and third sample tests. They show that the sign of a number in the financial format (and consequently, the presence or absence of brackets) is determined solely by the sign of the initial number. It does not depend on the sign of the number you got after translating the number to the financial format.

水题一次ac、、、字符串处理题目，先给每个前面加 $ 然后是负的前后加括号，点. 后只保留两位，每三个数中间夹逗号（，）。特殊数据就是第三组，试试。代码：

#include <cstdio>
    #include <iostream>
    #include <string>
    using namespace std;
    int main()
    {
        string s1,s2,s3,s4;
        while(cin>>s1)
        {
            s2=s3=s4="";
            bool ok=false,flag=false,tc=false;
            if(s1[0]=='-') tc=true;
            for(int i=0;i<s1.size();i++)
            {
                if(s1[i]=='.')
                {
                    ok=true;
                }
                if(s1[i]>='0'&&s1[i]<='9')
                {
                    if(s1[i]=='0'&&flag==false&&ok==false){continue;}
                    else
                    {
                        flag=true;
                        if(ok)
                            s3+=s1[i];
                        else
                            s2+=s1[i];
                    }
    
                }
            }
            if(tc)
                cout<<"(";
            cout<<"$";
            if(s2.size()==0)
                cout<<"0";
            else
            {
                for(int i=0;i<s2.size();i++)
                {
    
                    if((s2.size()-i)%3==0){
                        if(i!=0)
                            cout<<",";
                    }
                    cout<<s2[i];
                }
            }
            cout<<".";
            for(int i=0;i<2;i++)
            {
                if(s3[i])
                    cout<<s3[i];
                else
                    cout<<"0";
            }if(tc)
                cout<<")";
            cout<<endl;
        }
    
        return 0;
    }

# Problem A #

##### Time Limit : 1000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other) #####

##### Total Submission(s) : 6 Accepted Submission(s) : 2 #####

#### Font: Times New Roman | Verdana | Georgia ####

#### Font Size: ← → ####

### Problem Description ###

现有公园游船租赁处请你编写一个租船管理系统。当游客租船时，管理员输入船号并按下S键，系统开始计时；当游客还船时，管理员输入船号并按下E键，系统结束计时。船号为不超过100的正整数。当管理员将0作为船号输入时，表示一天租船工作结束，系统应输出当天的游客租船次数和  
平均租船时间。  
注意：由于线路偶尔会有故障，可能出现不完整的纪录，即只有租船没有还船，或者只有还船没有租船的纪录，系统应能自动忽略这种无效纪录。

### Input ###

测试输入包含若干测试用例，每个测试用例为一整天的租船纪录，格式为  
船号（1~100） 键值（S或E） 发生时间（小时:分钟）  
每一天的纪录保证按时间递增的顺序给出。当读到船号为-1时，全部输入结束，相应的结果不要输出。

### Output ###

对每个测试用例输出1行，即当天的游客租船次数和平均租船时间（以分钟为单位的精确到个位的整数时间）。

### Sample Input ###

1 S 08:10
    2 S 08:35
    1 E 10:00
    2 E 13:16
    0 S 17:00
    0 S 17:00
    3 E 08:10
    1 S 08:20
    2 S 09:00
    1 E 09:20
    0 E 17:00
    -1

### Sample Output ###

2 196
    0 0
    1 60

。。题意很清晰，用结构体比较好处理、可以保存时间和是否出租。看代码：

#include <cstdio>
    #include <cstring>
    
    int cnt;
    double sum;
    
    struct BOAT
    {
    	int time;
    	bool status;
    }b[105];
    
    void Init()
    {
    	sum=0;
    	cnt=0;
    }
    
    int main()
    {
    	int ind=0,i,j;
    	int h,m;
    	char t[10];
    	char status;
    	Init();
    	for(i=1;i<=100;i++)
    		b[i].status=false;
    	while(true)
    	{
    		scanf("%d",&ind);
    		if(ind==-1)
    			break;
    		getchar();
    		status=getchar();
    		scanf("%d:%d",&h,&m);
    		if(ind==0)
    		{
    			if(cnt)
    				printf("%d %.0lf\n",cnt,sum/cnt);
    			else
    				printf("0 0\n");
    			Init();
    			continue;
    		}
    		if(status=='S')
    			b[ind].time=h*60+m,b[ind].status=true;
    
    		else
    		{
    			if(b[ind].status)
    			{
    				sum+=h*60+m-b[ind].time;
    				cnt++;
    				b[ind].status=false;
    			}
    		}	
    	}
    }

[93c8bcc9e87b70a668d8a3b3e996a33265cc940f.png]: /images/20220109/defa32113ab24528b801175b136c9f3c.png
[18dde523e7a53fa62cd21281733d664a7ae608b6.png]: /images/20220109/4ba5a1743b944efd901020a7d391118f.png
[986b79e3875161e9ba76e35e0ceb51da9b971684.png]: /images/20220109/5e4cd9a4f24544738ddbc8ce0bd27044.png
[Meeting]: http://cdn.ac.nbutoj.com/Problem/view.xhtml?id=1040
[Submit]: http://acm.hust.edu.cn/vjudge/problem/toSubmit.action?id=29039
[Status]: http://acm.hust.edu.cn/vjudge/problem/status.action?id=29039
[1327020407.png]: http://acm.nbut.cn/ueditor/dialogs/image/uploadfiles/1327020407.png
[Help Kingdom of Far Far Away 2]: http://codeforces.com/problemset/problem/143/B
[Submit 1]: http://acm.hust.edu.cn/vjudge/problem/toSubmit.action?id=27674
[Status 1]: http://acm.hust.edu.cn/vjudge/problem/status.action?id=27674