codeforces-scrape

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

1932B.md (2151B)


      1 Source: https://codeforces.com/problemset/problem/1932/B
      2 
      3 B. Chaya Calendar
      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 The Chaya tribe believes that there are $n$ signs of the apocalypse. Over time, it has been found out that the $i$-th sign occurs every $a_i$ years (in years $a_i$, $2 \cdot a_i$, $3 \cdot a_i$, $\dots$).
     22 
     23 According to the legends, for the apocalypse to happen, the signs must occur sequentially. That is, first they wait for the first sign to occur, then strictly after it, the second sign will occur, and so on. That is, if the $i$-th sign occurred in the year $x$, the tribe starts waiting for the occurrence of the $(i+1)$-th sign, starting from the year $x+1$.
     24 
     25 In which year will the $n$-th sign occur and the apocalypse will happen?
     26 
     27 Input
     28 
     29 The first line of the input contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Then follow the descriptions of the test cases.
     30 
     31 The first line of each test case contains a single integer $n$ ($1 \le n \le 100$) — the number of signs.
     32 
     33 The second line of each test case contains $n$ integers $a_1, a_2, a_3, \dots, a_n$ ($1 \le a_i \le 10^6$) — the periodicities of the signs.
     34 
     35 Output
     36 
     37 For each test case, output a single integer — the year in which all $n$ signs will occur.
     38 
     39 Example
     40 
     41 Input
     42 
     43 ```
     44 4
     45 
     46 6
     47 
     48 3 2 4 5 9 18
     49 
     50 5
     51 
     52 1 2 3 4 5
     53 
     54 5
     55 
     56 1 1 1 1 1
     57 
     58 6
     59 
     60 50 30 711 200 503 1006
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 36
     67 5
     68 5
     69 2012
     70 ```
     71 
     72 Note
     73 
     74 In the first set of input data of the example:
     75 
     76 * The tribe will wait for the first sign in the $3$-rd year;
     77 * the tribe will wait for the second sign in the $4$-th year (since year $2$ have already passed);
     78 * the tribe will wait for the third sign in the $8$-th year (since the second sign has already occurred in the $4$-th year);
     79 * the tribe will wait for the fourth sign in the $10$-th year (since year $5$ have already passed);
     80 * the tribe will wait for the fifth sign in the $18$-th year (since year $9$ have already passed);
     81 * the tribe will wait for the sixth sign in the $36$-th year (since the fifth sign has already occurred in the $18$-th year).