??? 總體感覺這次出的題偏數(shù)學,數(shù)學若菜表示果斷被虐.不過看起來由于大家都被虐我2題居然排到331,rating又升了74.
Div2-A
A. The Wall
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Iahub and his friend Floyd have started painting a wall. Iahub is painting the wall red and Floyd is painting it pink. You can consider the wall being made of a very large number of bricks, numbered 1, 2, 3 and so on.
Iahub has the following scheme of painting: he skips x - 1 consecutive bricks, then he paints the x-th one. That is, he'll paint bricks x, 2·x, 3·x and so on red. Similarly, Floyd skips y - 1 consecutive bricks, then he paints the y-th one. Hence he'll paint bricks y, 2·y, 3·y and so on pink.
After painting the wall all day, the boys observed that some bricks are painted both red and pink. Iahub has a lucky number a and Floyd has a lucky number b. Boys wonder how many bricks numbered no less than a and no greater than b are painted both red and pink. This is exactly your task: compute and print the answer to the question.
Input
The input will have a single line containing four integers in this order: x, y, a, b. (1 ≤ x, y ≤ 1000, 1 ≤ a, b ≤ 2·109, a ≤ b).
Output
Output a single integer — the number of bricks numbered no less than a and no greater than b that are painted both red and pink.
Sample test(s)
Input
2 3 6 18
Output
3
Note
Let's look at the bricks from a to b (a = 6, b = 18). The bricks colored in red are numbered 6, 8, 10, 12, 14, 16, 18. The bricks colored in pink are numbered 6, 9, 12, 15, 18. The bricks colored in both red and pink are numbered with 6, 12 and 18.
題意:兩個人刷墻,一個人刷編號是x的倍數(shù)的,另一個刷編號是y倍數(shù)的.求在[a,b]上有多少個墻被兩個人同時刷了.
思路:第一題不水沒道理.被同時刷的墻是x和y最小公倍數(shù)的倍數(shù).

        #include<stdio.h>

        
          int
        
         gcd(
        
          int
        
         a,
        
          int
        
        
           b)
{
 
        
        
          if
        
         (a==
        
          0
        
        ) 
        
          return
        
        
           b;
 
        
        
          return
        
         gcd(b%
        
          a,a);
}

        
        
          int
        
        
           main()
{
 
        
        
          int
        
        
           x,y;
 __int64 a,b;
 scanf(
        
        
          "
        
        
          %d%d%I64d%I64d
        
        
          "
        
        ,&x,&y,&a,&
        
          b);
 
        
        
          int
        
         M=x/gcd(x,y)*
        
          y;
 __int64 l
        
        =a/M,r=b/
        
          M;
 
        
        
          if
        
         (l*M<a) l++
        
          ;
 printf(
        
        
          "
        
        
          %I64d\n
        
        
          "
        
        ,r-l+
        
          1
        
        
          );
 
        
        
          return
        
        
          0
        
        
          ;
}
        
      

View Code

Div2-B
B. Maximal Area Quadrilateral
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Iahub has drawn a set of n points in the cartesian plane which he calls "special points". A quadrilateral is a simple polygon without self-intersections with four sides (also called edges) and four vertices (also called corners). Please note that a quadrilateral doesn't have to be convex. A special quadrilateral is one which has all four vertices in the set of special points. Given the set of special points, please calculate the maximal area of a special quadrilateral.
Input
The first line contains integer n (4 ≤ n ≤ 300). Each of the next n lines contains two integers: xi, yi ( - 1000 ≤ xi, yi ≤ 1000) — the cartesian coordinates of ith special point. It is guaranteed that no three points are on the same line. It is guaranteed that no two points coincide.
Output
Output a single real number — the maximal area of a special quadrilateral. The answer will be considered correct if its absolute or relative error does't exceed 10 - 9.
Sample test(s)
Input
50 00 44 04 42 3
Output
16.000000
Note
In the test example we can choose first 4 points to be the vertices of the quadrilateral. They form a square by side 4, so the area is 4·4 = 16.
題意:給出一些點,從其中找出4個點構成四邊形,求面積最大的四邊形的面積.
思路:一開始被嚇尿了,想dfs發(fā)現(xiàn)那是不可能的事,后來想能不能把四邊形分成兩個三角形來處理.經過觀察發(fā)現(xiàn)不論四個點怎么擺必會發(fā)生這樣的情況:中間一條線段,線段左右兩邊各有一個點.于是思路就有了:先O(N^2)枚舉這樣的線段,然后O(N)枚舉左右兩邊的點.總時間復雜度為O(N^3).不過要特別注意的是有可能出現(xiàn)一條線段某一側沒有點的情況.

        #include<math.h>
        
          
#include
        
        <stdio.h> 

        
          struct
        
        
           vect
{
 
        
        
          int
        
        
           x,y;
};

        
        
          double
        
         x[
        
          500
        
        ],y[
        
          500
        
        
          ];

        
        
          int
        
        
           mult(vect v1,vect v2)
{
 
        
        
          return
        
         v1.x*v2.y-v2.x*
        
          v1.y;
}

        
        
          int
        
        
           main()
{
 
        
        
          int
        
        
           N;
 scanf(
        
        
          "
        
        
          %d
        
        
          "
        
        ,&
        
          N);
 
        
        
          for
        
         (
        
          int
        
         i=
        
          1
        
        ;i<=N;i++) scanf(
        
          "
        
        
          %lf%lf
        
        
          "
        
        ,&x[i],&
        
          y[i]);
 
        
        
          double
        
         Max=
        
          0
        
        
          ;
 
        
        
          for
        
         (
        
          int
        
         i=
        
          1
        
        ;i<=N;i++
        
          )
  
        
        
          for
        
         (
        
          int
        
         j=
        
          1
        
        ;j<=N;j++
        
          )
  
        
        
          if
        
         (i!=
        
          j)
  {
   vect seg,tmp;
   seg.x
        
        =x[i]-
        
          x[j];
   seg.y
        
        =y[i]-
        
          y[j];
   
        
        
          double
        
         l=
        
          0
        
        ,r=
        
          0
        
        
          ;
   
        
        
          for
        
         (
        
          int
        
         k=
        
          1
        
        ;k<=N;k++
        
          )
   
        
        
          if
        
         (k!=i && k!=
        
          j)
   {
    tmp.x
        
        =x[k]-
        
          x[j];
    tmp.y
        
        =y[k]-
        
          y[j];
    
        
        
          int
        
         dir=
        
          mult(seg,tmp);
    
        
        
          if
        
         (dir<
        
          0
        
        
          )
    {
     
        
        
          double
        
         S=
        
          0.5
        
        *fabs(x[i]*y[j]+y[i]*x[k]+x[j]*y[k]-y[j]*x[k]-y[i]*x[j]-x[i]*
        
          y[k]);
    
        
        
          if
        
         (S>l) l=
        
          S;
    }
    
        
        
          else
        
        
           
    {
     
        
        
          double
        
         S=
        
          0.5
        
        *fabs(x[i]*y[j]+y[i]*x[k]+x[j]*y[k]-y[j]*x[k]-y[i]*x[j]-x[i]*
        
          y[k]);
     
        
        
          if
        
         (S>r) r=
        
          S;
    }
   }
   
        
        
          if
        
         (l+r>Max && l>
        
          0
        
         && r>
        
          0
        
        ) Max=l+
        
          r;
  }
 printf(
        
        
          "
        
        
          %.9lf\n
        
        
          "
        
        
          ,Max);
 
        
        
          return
        
        
          0
        
        
          ;
}
        
      

View Code

Div2-C/Div1-A
C. Tourist Problem
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
Iahub is a big fan of tourists. He wants to become a tourist himself, so he planned a trip. There are n destinations on a straight road that Iahub wants to visit. Iahub starts the excursion from kilometer 0. The n destinations are described by a non-negative integers sequence a1, a2, ..., an. The number ak represents that the kth destination is at distance ak kilometers from the starting point. No two destinations are located in the same place.
Iahub wants to visit each destination only once. Note that, crossing through a destination is not considered visiting, unless Iahub explicitly wants to visit it at that point. Also, after Iahub visits his last destination, he doesn't come back to kilometer 0, as he stops his trip at the last destination.
The distance between destination located at kilometer x and next destination, located at kilometer y, is |x?-?y| kilometers. We call a "route" an order of visiting the destinations. Iahub can visit destinations in any order he wants, as long as he visits all n destinations and he doesn't visit a destination more than once.
Iahub starts writing out on a paper all possible routes and for each of them, he notes the total distance he would walk. He's interested in the average number of kilometers he would walk by choosing a route. As he got bored of writing out all the routes, he asks you to help him.
Input
The first line contains integer n (2?≤?n?≤?105). Next line contains n distinct integers a1, a2, ..., an (1?≤?ai?≤?107).
Output
Output two integers — the numerator and denominator of a fraction which is equal to the wanted average number. The fraction must be irreducible.
Sample test(s)
Input
32 3 5Output
22 3Note
Consider 6 possible routes:
[2, 3, 5]: total distance traveled: |2 – 0| + |3 – 2| + |5 – 3| = 5;
[2, 5, 3]: |2 – 0| + |5 – 2| + |3 – 5| = 7;
[3, 2, 5]: |3 – 0| + |2 – 3| + |5 – 2| = 7;
[3, 5, 2]: |3 – 0| + |5 – 3| + |2 – 5| = 8;
[5, 2, 3]: |5 – 0| + |2 – 5| + |3 – 2| = 9;
[5, 3, 2]: |5 – 0| + |3 – 5| + |2 – 3| = 8.
The average travel distance is? =? = .
題意:一條路上n個景點,可以按任意順序全部訪問一遍,求走路的平均長度.
思路:這是官方題解
Despite this is a math task, the only math formula we'll use is that number of permutations with n elements is n!. From this one, we can deduce the whole task.
The average formula is sum_of_all_routes / number_of_routes. As each route is a permutation with n elements, number_of_routes is n!. Next suppose you have a permutation of a: p1, p2, …, pn. The sum for it will be p1 + |p2 – p1| + … + |pn – pn-1|. The sum of routes will be the sum for each possible permutation.
We can calculate sum_of_all routes in two steps: first time we calculate sums like “p1” and then we calculate sums like “|p2 – p1| + … + |pn – pn-1|” for every existing permutation.
First step Each element of a1, a2, …, an can appear on the first position on the routes and needs to be added as much as it appears. Suppose I fixed an element X for the first position. I can fill positions 2, 3, .., n – 1 in (n – 1)! ways. Why? It is equivalent to permuting n – 1 elements (all elements except X). So sum_of_all = a1 * (n – 1)! + a2 * (n – 1)! + … * an * (n – 1)! = (n – 1)! * (a1 + a2 + … + an).
Second step For each permutation, for each position j between 1 and n – 1 we need to compute |pj — p(j?+?1)|. Similarly to first step, we observe that only elements from a can appear on consecutive positions. We fix 2 indices i and j. We’re interested in how many permutations do ai appear before aj. We fix k such as on a permutation p, ai appears on position k and aj appears on a position k + 1. In how many ways can we fix this? n – 1 ways (1, 2, …, n – 1). What’s left? A sequence of (n – 2) elements which can be permuted independently. So the sum of second step is |ai?-?aj| * (n – 1) * (n – 2)!, for each i != j. If I note (a1 + a2 + … + an) by S1 and |ai?-?aj| for each i != j by S2, the answer is (N – 1)! * S1 + (N – 1)! * S2 / N!. By a simplification, the answer is (S1 + S2) / N.
The only problem remained is how to calculate S2. Simple iteration won’t enter in time limit. Let’s think different. For each element, I need to make sum of differences between it and all smaller elements in the array a. As well, I need to make sum of all different between bigger elements than it and it. I’ll focus on the first part. I sort increasing array a. Suppose I’m at position i. I know that (i – 1) elements are smaller than ai. The difference is simply (i — 1) * ai — sum_of_elements_before_position_i. Sum of elements before position i can be computed when iterating i. Let’s call the obtained sum Sleft. I need to calculate now sum of all differences between an element and bigger elements than it. This sum is equal to Sleft. As a proof, for an element ai, calculating the difference aj — ai when aj > ai is equivalent to calculating differences between aj and a smaller element of it (in this case ai). That’s why Sleft = Sright.
As a conclusion, the answer is (S1 + 2 * Sleft) / N. For make fraction irreducible, you can use Euclid's algorithm. The complexity of the presented algorithm is O(N?*?logN), necessary due of sorting. Sorting can be implemented by count sort as well, having a complexity of O(maximalValue), but this is not necessary.

        #include<stdio.h>
        
          
#include
        
        <stdlib.h>
        
          
#include
        
        <math.h>
        
          
#include
        
        <
        
          string
        
        .h>

        
          #define
        
         N 100005

        
          long
        
        
          long
        
        
           a[N];

        
        
          long
        
        
          long
        
         gcd(
        
          long
        
        
          long
        
         a,
        
          long
        
        
          long
        
        
           b)
{
    
        
        
          return
        
         b gcd(b,a%
        
          b):a;
}

        
        
          int
        
         cmp(
        
          const
        
        
          void
        
         *a,
        
          const
        
        
          void
        
         *
        
          b)
{
    
        
        
          return
        
         *(
        
          long
        
        
          long
        
        *)a-*(
        
          long
        
        
          long
        
         *
        
          )b;
}

        
        
          int
        
        
           main()
{
    
        
        
          long
        
        
          long
        
         n,sum=
        
          0
        
        
          ,p,q,d,tot;
    
        
        
          while
        
        (~scanf(
        
          "
        
        
          %I64d
        
        
          "
        
        ,&
        
          n))
    {
        
        
        
          for
        
        (
        
          int
        
         i=
        
          0
        
        ;i<n;i++
        
          )
            scanf(
        
        
          "
        
        
          %I64d
        
        
          "
        
        ,a+
        
          i);
        
        
        
          for
        
        (
        
          int
        
         i=
        
          0
        
        ;i<n;i++
        
          )
            sum
        
        +=
        
          a[i];
        qsort(a,n,
        
        
          sizeof
        
        (a[
        
          0
        
        
          ]),cmp);
        p
        
        =
        
          0
        
        ;q=n-
        
          1
        
        
          ;
        tot
        
        =
        
          n;
        
        
        
          while
        
        (p<
        
          q)
        {
            sum
        
        +=
        
          2
        
        *(tot-
        
          1
        
        )*(a[q]-
        
          a[p]);
            p
        
        ++
        
          ;
            q
        
        --
        
          ;
            tot
        
        -=
        
          2
        
        
          ;
        }
        d
        
        =
        
          gcd(sum,n);
        sum
        
        /=d,n/=
        
          d;
        printf(
        
        
          "
        
        
          %I64d %I64d\n
        
        
          "
        
        
          ,sum,n);
    }
    
        
        
          return
        
        
          0
        
        
          ;
}
        
      

View Code

?

CodeForces Round 198