codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

523B.md (6326B)


      1 Source: https://codeforces.com/problemset/problem/523/B
      2 
      3 B. Mean Requests
      4 
      5 time limit per test
      6 
      7 4 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 In this problem you will have to deal with a real algorithm that is used in the VK social network.
     22 
     23 As in any other company that creates high-loaded websites, the VK developers have to deal with request statistics regularly. An important indicator reflecting the load of the site is the mean number of requests for a certain period of time of *T* seconds (for example, *T* = 60 *seconds* = 1 *min* and *T* = 86400 *seconds* = 1 *day*). For example, if this value drops dramatically, that shows that the site has access problem. If this value grows, that may be a reason to analyze the cause for the growth and add more servers to the website if it is really needed.
     24 
     25 However, even such a natural problem as counting the mean number of queries for some period of time can be a challenge when you process the amount of data of a huge social network. That's why the developers have to use original techniques to solve problems approximately, but more effectively at the same time.
     26 
     27 Let's consider the following formal model. We have a service that works for *n* seconds. We know the number of queries to this resource *a**t* at each moment of time *t* (1 ≤ *t* ≤ *n*). Let's formulate the following algorithm of calculating the mean with exponential decay. Let *c* be some real number, strictly larger than one.
     28 
     29 ```
     30 // setting this constant value correctly can adjust     
     31 // the time range for which statistics will be calculated  
     32 double c = some constant value;   
     33   
     34 // as the result of the algorithm's performance this variable will contain   
     35 // the mean number of queries for the last   
     36 // T seconds by the current moment of time  
     37 double mean = 0.0;   
     38   
     39 for t = 1..n: // at each second, we do the following:  
     40     // at is the number of queries that came at the last second;  
     41     mean = (mean + at / T) / c;
     42 ```
     43 
     44 Thus, the mean variable is recalculated each second using the number of queries that came at that second. We can make some mathematical calculations and prove that choosing the value of constant *c* correctly will make the value of mean not very different from the real mean value *a**x* at *t* - *T* + 1 ≤ *x* ≤ *t*.
     45 
     46 The advantage of such approach is that it only uses the number of requests at the current moment of time and doesn't require storing the history of requests for a large time range. Also, it considers the recent values with the weight larger than the weight of the old ones, which helps to react to dramatic change in values quicker.
     47 
     48 However before using the new theoretical approach in industrial programming, there is an obligatory step to make, that is, to test its credibility practically on given test data sets. Your task is to compare the data obtained as a result of the work of an approximate algorithm to the real data.
     49 
     50 You are given *n* values *a**t*, integer *T* and real number *c*. Also, you are given *m* moments *p**j* (1 ≤ *j* ≤ *m*), where we are interested in the mean value of the number of queries for the last *T* seconds. Implement two algorithms. The first one should calculate the required value by definition, i.e. by the formula ![](https://espresso.codeforces.com/3b7e6a2a96e83f82fad8d5ae0b0196625482460a.png). The second algorithm should calculate the mean value as is described above. Print both values and calculate the relative error of the second algorithm by the formula ![](https://espresso.codeforces.com/ce00b789c658da21a80813906edd50e449ca0654.png), where *approx* is the approximate value, obtained by the second algorithm, and *real* is the exact value obtained by the first algorithm.
     51 
     52 Input
     53 
     54 The first line contains integer *n* (1 ≤ *n* ≤ 2·105), integer *T* (1 ≤ *T* ≤ *n*) and real number *c* (1 < *c* ≤ 100) — the time range when the resource should work, the length of the time range during which we need the mean number of requests and the coefficient *c* of the work of approximate algorithm. Number *c* is given with exactly six digits after the decimal point.
     55 
     56 The next line contains *n* integers *a**t* (1 ≤ *a**t* ≤ 106) — the number of queries to the service at each moment of time.
     57 
     58 The next line contains integer *m* (1 ≤ *m* ≤ *n*) — the number of moments of time when we are interested in the mean number of queries for the last *T* seconds.
     59 
     60 The next line contains *m* integers *p**j* (*T* ≤ *p**j* ≤ *n*), representing another moment of time for which we need statistics. Moments *p**j* are strictly increasing.
     61 
     62 Output
     63 
     64 Print *m* lines. The *j*-th line must contain three numbers *real*, *approx* and *error*, where:
     65 
     66 * ![](https://espresso.codeforces.com/b658ef1b555d4a43335450db8ab1cfbcf0bfd944.png) is the real mean number of queries for the last *T* seconds;
     67 * *approx* is calculated by the given algorithm and equals *mean* at the moment of time *t* = *p**j* (that is, after implementing the *p**j*-th iteration of the cycle);
     68 * ![](https://espresso.codeforces.com/963758ed5561398191a4d0771088a335fcdcc2d3.png) is the relative error of the approximate algorithm.
     69 
     70 The numbers you printed will be compared to the correct numbers with the relative or absolute error 10- 4. It is recommended to print the numbers with at least five digits after the decimal point.
     71 
     72 Examples
     73 
     74 Input
     75 
     76 ```
     77 1 1 2.000000  
     78 1  
     79 1  
     80 1
     81 ```
     82 
     83 Output
     84 
     85 ```
     86 1.000000 0.500000 0.500000
     87 ```
     88 
     89 Input
     90 
     91 ```
     92 11 4 1.250000  
     93 9 11 7 5 15 6 6 6 6 6 6  
     94 8  
     95 4 5 6 7 8 9 10 11
     96 ```
     97 
     98 Output
     99 
    100 ```
    101 8.000000 4.449600 0.443800  
    102 9.500000 6.559680 0.309507  
    103 8.250000 6.447744 0.218455  
    104 8.000000 6.358195 0.205226  
    105 8.250000 6.286556 0.237993  
    106 6.000000 6.229245 0.038207  
    107 6.000000 6.183396 0.030566  
    108 6.000000 6.146717 0.024453
    109 ```
    110 
    111 Input
    112 
    113 ```
    114 13 4 1.250000  
    115 3 3 3 3 3 20 3 3 3 3 3 3 3  
    116 10  
    117 4 5 6 7 8 9 10 11 12 13
    118 ```
    119 
    120 Output
    121 
    122 ```
    123 3.000000 1.771200 0.409600  
    124 3.000000 2.016960 0.327680  
    125 7.250000 5.613568 0.225715  
    126 7.250000 5.090854 0.297813  
    127 7.250000 4.672684 0.355492  
    128 7.250000 4.338147 0.401635  
    129 3.000000 4.070517 0.356839  
    130 3.000000 3.856414 0.285471  
    131 3.000000 3.685131 0.228377  
    132 3.000000 3.548105 0.182702
    133 ```