ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

3394: 数字根

内存限制：128 MB 时间限制：1 S
题面：传统 评测方式：文本比较 上传者：
提交：1 通过：1
提交提交记录统计Web Board

题目描述

一个数字的数字根定义为:这个数字每一位的数字加起来求和,反复这个过程直到和小于10。例如,64357的数字跟为7,因为6+4+3+5+7=25,2+5=7个区间的数字根定义为这个区间所有数字和的数字根。 

给定一个序列A1,A2,A3,…,An,你需要回答一些询问。每一个询问给定个区间[L,R],求出这个区间所有连续子区间里最大的前5个不同的数字根，不够5个的用-1补全 

输入格式

第一行一个整数N,表示序列的长度。第二行是N个整数Ai(0≤Ai<10^9)。第三行是一个整数Q表示询问次数。接下来Q行,每一行两个正整数1,r,表示询问区间。(1≤l≤r≤N)

输出格式

Q行,表示每一个查询区间所有连续子区间里最大的前5个不同的数字根,按降序输出,输出用空格隔开。 

输入输出样例

输入样例#1：
5 
101 240 331 4 52
3
1 3
4 5
1 5
输出样例#1：  
8 7 6 4 2
7 4 2 -1 -1
9 8 7 6 4

说明

样例解释

第一个查询区间[1,3],它的连续子区间有[1,1],[2,2],[3,3],[1,2],[2,3],[1,3].可对应的数字根分别为2,6,7,8,4,6。所以最大的5个是8,7,6,4,2。

数据范围

30%的数据，N ≤ 1000; Q ≤ 1000

100%的数据，N ≤ 100000; Q ≤ 100000

输入样例 复制 

5
101 240 331 4 52
3
1 3
4 5
1 5

输出样例 复制 

8 7 6 4 2
7 4 2 -1 -1
9 8 7 6 4

数据范围与提示



注意 输入较大，C++建议使用scanf()进行输入。
 数据范围
 30%的数据，N ≤ 1000, Q ≤ 1000 
100%的数据，N ≤ 100000, Q ≤ 100000

分类标签