F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Array-Gift

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1647    Accepted Submission(s): 361


Problem Description
最近开始流行赠送数组,所以 Beijixing 送给了 Liyishui 一个长度为 $n$ 的**正整数**序列 $a=[a_1,\dots,a_n]$,并附赠了两种操作:

- 操作1:选择不同的下标 $i,j$(即 $1\leq i,j\leq n$,$i \neq j$),且 $a_j\neq 0$,然后将 $a_i $ 修改为 $ a_{i} \bmod a_{j} $
- 操作2:选择某个 $i$ 满足 $1 \leq i \leq n$ 和任意一个 **正整数** $x$ ,将 $a_{i} $ 修改为 $a_{i}+x$.

Liyishui 喜欢倒腾数组,她希望只使用这两种操作让 $a$ 只剩 **恰好一个** 非 $0$ 数,其他的数都变成 $0$。两种操作均可使用任意次。不幸的是Liyishui最近忙着赶ddl,你能帮忙求出**最小操作次数**吗?
 

Input
第一行输入一个正整数 $T$ ,表示一共有 $T$ 组测试用例,$ 1 \leq T \leq 30 $.

接下来每组测试用例由两行构成:其中第一行输入一个正整数 $ n(1 \leq n \leq 100) $ ,表示序列 $ a $ 的长度。第二行输入 $ n $ 个正整数 $ a_1,\dots,a_n $,相邻两数用一个空格隔开,表示序列 $ a $ .
对 $ 1\leq i\leq n $ ,有 $ 1\leq a_i\leq 10^6 $ .
 

Output
对每个测试用例,输出一行一个整数,表示最小操作次数。
 

Sample Input
2 4 2 3 5 7 4 2 4 6 8
 

Sample Output
4 3
 

Hint
对于第一个样例,一种可能操作如下:$[2,3,5,7] \to [2, \mathbf{1},5,7] \to [ \mathbf{0},1,5,7] \to [0,1, \mathbf{0},7] \to [0,1,0, \mathbf{0}]$,
一共用了 $4$ 次操作,可以证明这是最少可能的操作次数。

对于第二个样例,一种可能操作如下:$[2,4,6,8] \to [2,\mathbf{0},6,8] \to [2,0,\mathbf{0},8] \to [2,0,0,\mathbf{0}]$,
一共用了 $3$ 次操作,可以证明这是最少可能的操作次数。
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-22 20:55:39, Gzip enabled