codeforces-scrape

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

891A.md (1511B)


      1 Source: https://codeforces.com/problemset/problem/891/A
      2 
      3 A. Pride
      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 You have an array *a* with length *n*, you can perform operations. Each operation is like this: choose two adjacent elements from *a*, say *x* and *y*, and replace one of them with *gcd*(*x*, *y*), where *gcd* denotes the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor).
     22 
     23 What is the minimum number of operations you need to make all of the elements equal to 1?
     24 
     25 Input
     26 
     27 The first line of the input contains one integer *n* (1 ≤ *n* ≤ 2000) — the number of elements in the array.
     28 
     29 The second line contains *n* space separated integers *a*1, *a*2, ..., *a**n* (1 ≤ *a**i* ≤ 109) — the elements of the array.
     30 
     31 Output
     32 
     33 Print -1, if it is impossible to turn all numbers to 1. Otherwise, print the minimum number of operations needed to make all numbers equal to 1.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 5  
     41 2 2 3 4 6
     42 ```
     43 
     44 Output
     45 
     46 ```
     47 5
     48 ```
     49 
     50 Input
     51 
     52 ```
     53 4  
     54 2 4 6 8
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 -1
     61 ```
     62 
     63 Input
     64 
     65 ```
     66 3  
     67 2 6 9
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 4
     74 ```
     75 
     76 Note
     77 
     78 In the first sample you can turn all numbers to 1 using the following 5 moves:
     79 
     80 * [2, 2, 3, 4, 6].
     81 * [2, 1, 3, 4, 6]
     82 * [2, 1, 3, 1, 6]
     83 * [2, 1, 1, 1, 6]
     84 * [1, 1, 1, 1, 6]
     85 * [1, 1, 1, 1, 1]
     86 
     87 We can prove that in this case it is not possible to make all numbers one using less than 5 moves.