Ducci Sequence解题报告
A Ducci sequence is a sequence of n-tuples of integers. Given an n-tuple of integers (a1, a2, ... , an), the next n-tuple in the sequence is formed by taking the absolute differences of neighboring integers:
Ducci sequences either reach a tuple of zeros or fall into a periodic loop. For example, the 4-tuple sequence starting with 8,11,2,7 takes 5 steps to reach the zeros tuple:
The 5-tuple sequence starting with 4,2,0,2,0 enters a loop after 2 steps:
Given an n-tuple of integers, write a program to decide if the sequence is reaching to a zeros tuple or a periodic loop.
Input
Your program is to read the input from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing an integer n(3n15), which represents the size of a tuple in the Ducci sequences. In the following line, n integers are given which represents the n-tuple of integers. The range of integers are from 0 to 1,000. You may assume that the maximum number of steps of a Ducci sequence reaching zeros tuple or making a loop does not exceed 1,000.
Output
Your program is to write to standard output. Print exactly one line for each test case. Print `LOOP' if the Ducci sequence falls into a periodic loop, print `ZERO' if the Ducci sequence reaches to a zeros tuple.
The following shows sample input and output for four test cases.
Sample Input
4
4
8 11 2 7
5
4 2 0 2 0
7
0 0 0 0 0 0 0
6
1 2 3 1 2 3
Sample Output
ZERO
LOOP
ZERO
LOOP 题意:给你一个数组,相邻数相加(最后一个数应该加第一个数),然后又可以得到一个新的数组,反复进行这样的步骤,结果会有两种,数组每个成员都是零,或者在这样的过程中出现了周期,即出现了和以前已经出现过的相同的项。
最后要求判断是哪一种情况 思路:
如果按照一般的解题思想,每得到一个新的数组都去判断是zero,还是loop。zero还好说,如果判断loop那就要每次遍历一遍数组,程序肯定会超时。、
所以~~~
反正结果只有两种可能,不是loop,就是zero,只判断zero就好了 代码:
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=;
int a[][maxn];
int n;
int iszero; void Init()
{
cin>>n;
for(int i=;i<n;i++)
cin>>a[][i];
} bool judge()
{
iszero=;
int now,form;
for(int i=;i<=;i++)
{
if(i%==) now=,form=;
else now=,form=;
for(int j=;j<n;j++)
{
if(j==n-)
{
a[now][j]=a[form][j]+a[form][];
}
else
a[now][j]=a[form][j]+a[form][j+];
}
int flag=;
for(int k=;k<n;k++)
if(a[now][k]!=) {flag=;break;}
if(!flag) {iszero=;break;}
}
if(iszero) return true;
else return false;
} int main()
{
int T;
cin>>T;
while(T--)
{
Init();
if(judge()) cout<<"ZERO"<<endl;
else cout<<"LOOP"<<endl;
}
return ;
}
最新文章
- 关于ie11 的开发者工具
- <;<;<; java异常The import java.util cannot be resolved
- JQuery 遍历子元素+ each函数的跳出+提取字符串中的数字
- Sprint(第六天11.19)
- javascript中||和&;&;代替if
- discuz安装与学习资料
- 【转载】PHP运行模式的深入理解
- w3c_html_study_note_5.26
- 第二百八十一、二、三天 how can I 坚持
- [Oralce]Oralce格式化日期
- list和数组之间相互的转化
- 关于 self 和 super 在oc 中 的疑惑 与 分析
- GCDAsyncUdpSocket的使用
- Tomcat详细用法学习(一)
- hdu 5833 Zhu and 772002 异或方程组高斯消元
- 《JS中的面向对象技术》
- linux的pvtrace环境配置
- 使用U盘在Mac机上装win8.1系统
- python 练完这些,你的函数编程就ok了
- Ocelot中文文档-委托处理程序
热门文章
- Access 中case when then else end不支持使用switch代替
- BFS HDOJ 1242 Rescue
- 什么是Servlet容器?(分析很到位)
- 当不知道基本数据类型的取值范围时,可以通过max_value等来查询
- 477 Total Hamming Distance 汉明距离总和
- linux/centos系统如何使用yum安装vi/vim?
- php Try Catch多层级异常测试
- How `delete’ works ?
- swift版本拼图游戏项目源码
- (转)Spring如何装配各种集合类型的属性