codeforces-scrape

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

302B.md (2185B)


      1 Source: https://codeforces.com/problemset/problem/302/B
      2 
      3 B. Eugeny and Play List
      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 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Eugeny loves listening to music. He has *n* songs in his play list. We know that song number *i* has the duration of *t**i* minutes. Eugeny listens to each song, perhaps more than once. He listens to song number *i* *c**i* times. Eugeny's play list is organized as follows: first song number 1 plays *c*1 times, then song number 2 plays *c*2 times, ..., in the end the song number *n* plays *c**n* times.
     22 
     23 Eugeny took a piece of paper and wrote out *m* moments of time when he liked a song. Now for each such moment he wants to know the number of the song that played at that moment. The moment *x* means that Eugeny wants to know which song was playing during the *x*-th minute of his listening to the play list.
     24 
     25 Help Eugeny and calculate the required numbers of songs.
     26 
     27 Input
     28 
     29 The first line contains two integers *n*, *m* (1 ≤ *n*, *m* ≤ 105). The next *n* lines contain pairs of integers. The *i*-th line contains integers *c**i*, *t**i* (1 ≤ *c**i*, *t**i* ≤ 109) — the description of the play list. It is guaranteed that the play list's total duration doesn't exceed 109 ![](https://espresso.codeforces.com/920c79400120d0d4ba526d1d58cb85c98953f1f1.png).
     30 
     31 The next line contains *m* positive integers *v*1, *v*2, ..., *v**m*, that describe the moments Eugeny has written out. It is guaranteed that there isn't such moment of time *v**i*, when the music doesn't play any longer. It is guaranteed that *v**i* < *v**i* + 1 (*i* < *m*).
     32 
     33 The moment of time *v**i* means that Eugeny wants to know which song was playing during the *v**i*-th munite from the start of listening to the playlist.
     34 
     35 Output
     36 
     37 Print *m* integers — the *i*-th number must equal the number of the song that was playing during the *v**i*-th minute after Eugeny started listening to the play list.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 1 2  
     45 2 8  
     46 1 16
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 1  
     53 1
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 4 9  
     60 1 2  
     61 2 1  
     62 1 1  
     63 2 2  
     64 1 2 3 4 5 6 7 8 9
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 1  
     71 1  
     72 2  
     73 2  
     74 3  
     75 4  
     76 4  
     77 4  
     78 4
     79 ```