codeforces-scrape

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

2208C.md (1993B)


      1 Source: https://codeforces.com/problemset/problem/2208/C
      2 
      3 C. Stamina and Tasks
      4 
      5 time limit per test
      6 
      7 2 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 There are $n$ tasks for you. Task $i$ has an integer value of $c_i$ and a difficulty of $p_i$. Also, you have an initial stamina of $1$, which is denoted as $S$. You should process the tasks from task $1$ to task $n$. For each task, you have two choices.
     22 
     23 * Give up the task. This way, nothing will happen.
     24 * Complete the task. This way, you will gain $S\cdot c_i$ points. However, $S$ will drop to $S\cdot (1-\frac{p_i}{100})$ after the task is completed.
     25 
     26 You need to maximize your points after you finish the process.
     27 
     28 Input
     29 
     30 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.
     31 
     32 The first line of each test cases contain an integer $n$ ($1\le n\le10^5$) denoting the number of tasks.
     33 
     34 The following $n$ lines contain two integers each, denoting $c_i$ ($1\le c_i\le 100$) and $p_i$ ($0\le p_i\le 100$).
     35 
     36 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     37 
     38 Output
     39 
     40 For each test case, output a single real number — the maximum possible points you can get. Your answer is considered correct if its absolute or relative error does not exceed $10^{-6}$.
     41 
     42 Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is accepted if and only if $\frac{|a−b|}{\max(1,|b|)}\le 10^{-6}$.
     43 
     44 Example
     45 
     46 Input
     47 
     48 ```
     49 2
     50 
     51 2
     52 
     53 10 0
     54 
     55 20 5
     56 
     57 3
     58 
     59 10 5
     60 
     61 10 80
     62 
     63 20 5
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 30.0000000000
     70 
     71 29.0000000000
     72 ```
     73 
     74 Note
     75 
     76 In the first test case, it's optimal to complete task $1$ and $2$ in order, gaining points of $10+20=30$.
     77 
     78 In the second test case, it's optimal to complete task $1$, give up task $2$, and complete task $3$. Before completing task $3$, your stamina has dropped to $1-\frac{5}{100}=0.95$. So your gain is $10+20\cdot 0.95=29$ points in total.