codeforces-scrape

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

107B.md (2462B)


      1 Source: https://codeforces.com/problemset/problem/107/B
      2 
      3 B. Basketball Team
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 As a German University in Cairo (GUC) student and a basketball player, Herr Wafa was delighted once he heard the news. GUC is finally participating in the Annual Basketball Competition (ABC).
     22 
     23 A team is to be formed of *n* players, all of which are GUC students. However, the team might have players belonging to different departments. There are *m* departments in GUC, numbered from 1 to *m*. Herr Wafa's department has number *h*. For each department *i*, Herr Wafa knows number *s**i* — how many students who play basketball belong to this department.
     24 
     25 Herr Wafa was also able to guarantee a spot on the team, using his special powers. But since he hates floating-point numbers, he needs your help at finding the probability that he will have at least one teammate belonging to his department.
     26 
     27 Note that every possible team containing Herr Wafa is equally probable. Consider all the students different from each other.
     28 
     29 Input
     30 
     31 The first line contains three integers *n*, *m* and *h* (1 ≤ *n* ≤ 100, 1 ≤ *m* ≤ 1000, 1 ≤ *h* ≤ *m*) — the number of players on the team, the number of departments in GUC and Herr Wafa's department, correspondingly.
     32 
     33 The second line contains a single-space-separated list of *m* integers *s**i* (1 ≤ *s**i* ≤ 100), denoting the number of students in the *i*-th department. Note that *s**h* includes Herr Wafa.
     34 
     35 Output
     36 
     37 Print the probability that Herr Wafa will have at least one teammate from his department. If there is not enough basketball players in GUC to participate in ABC, print -1. The answer will be accepted if it has absolute or relative error not exceeding 10- 6.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 3 2 1  
     45 2 1
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 1
     52 ```
     53 
     54 Input
     55 
     56 ```
     57 3 2 1  
     58 1 1
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 -1
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 3 2 1  
     71 2 2
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 0.666667
     78 ```
     79 
     80 Note
     81 
     82 In the first example all 3 players (2 from department 1 and 1 from department 2) must be chosen for the team. Both players from Wafa's departments will be chosen, so he's guaranteed to have a teammate from his department.
     83 
     84 In the second example, there are not enough players.
     85 
     86 In the third example, there are three possibilities to compose the team containing Herr Wafa. In two of them the other player from Herr Wafa's department is part of the team.