301502: CF283D. Cows and Cool Sequences
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Cows and Cool Sequences
题意翻译
定义一个数对 $(x,y)$ 是好的当且仅当, $x$ 可表示为 $y$ 个连续数的和。 需要注意这些连续数的开头不一定需要是正数,负整数也可以。 比如 $(2,4)$ 是好的因为 $2=-1+0+1+2$ 。 定义一个序列 $a$ 是好的当且仅当对于任意的 $i$ 满足 $1\le i<n$ 有 $(a_i,a_{i+1})$ 是好的。 求将一个给定序列 $a$ 变成好的最少需要修改多少个位置的值,注意,你可以将其改成任意值。 数据范围:$n\le 5000,1\le a_i\le 10^{15}$。 翻译:by EmptySoulist题目描述
Bessie and the cows have recently been playing with "cool" sequences and are trying to construct some. Unfortunately they are bad at arithmetic, so they need your help! A pair $ (x,y) $ of positive integers is "cool" if $ x $ can be expressed as the sum of $ y $ consecutive integers (not necessarily positive). A sequence $ (a_{1},a_{2},...,a_{n}) $ is "cool" if the pairs $ (a_{1},a_{2}),(a_{2},a_{3}),...,(a_{n-1},a_{n}) $ are all cool. The cows have a sequence of $ n $ positive integers, $ a_{1},a_{2},...,a_{n} $ . In one move, they may replace some $ a_{i} $ with any other positive integer (there are no other limits on the new value of $ a_{i} $ ). Determine the smallest number of moves needed to make the resulting sequence cool.输入输出格式
输入格式
The first line contains a single integer, $ n $ ( $ 2<=n<=5000 $ ). The next line contains $ n $ space-separated integers, $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{15} $ ). Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.
输出格式
A single integer, the minimum number of $ a_{i} $ that must be changed to make the sequence cool.
输入输出样例
输入样例 #1
3
6 4 1
输出样例 #1
0
输入样例 #2
4
20 6 3 4
输出样例 #2
2