sqrt log sin

sqrt log sin

时间： 1ms        内存：128M

描述：

An evil professor has just assigned you the following problem.

A sequence is defined by the following recurrence:

Determine

x_1000000

.

输入：

Input consists of a number of lines, each containing one integer, a value of i, no less than zero and no greater than one million. Input is followed by a single line containing the integer -1. This last line is not a value of i and should not be processed.

输出：

For each value of i in the input (but not the final -1), output the corresponding value of x_i modulo 1000000.

示例输入：

0
-1

示例输出：

1

提示：

参考答案（内存最优[4596]）：

#include<stdio.h>
#include<math.h>
int main()
{
	int n,a[1000001];
	double i,x,y,z;
	a[0]=1;
	for(i=1;i<=1000000;i++)
	{
		x=i-sqrt(i);
		y=log(i);
		z=i*sin(i)*sin(i);
		a[(int)i]=(a[(int)x]+a[(int)y]+a[(int)z])%1000000;
	}
	while(scanf("%d",&n)!=EOF,n!=-1)
		printf("%d\n",a[n]);
	return 0;
}

参考答案（时间最优[4]）：

#include <cstdio>
#include <cstring>

const int MAXN = 1000100;

int lis1[MAXN], lis2[MAXN];
int n1, n2, i1, i2, ans;

int main() {
  scanf("%d%d", &n1, &n2);
  while(n1 != 0 || n2 != 0) {
    ans = 0;
    for(int i = 0; i < n1; ++i) scanf("%d", &lis1[i]);
    for(int i = 0; i < n2; ++i) scanf("%d", &lis2[i]);
    i1 = i2 = 0;
    while(i1 < n1 && i2 < n2) {
      if(lis1[i1] < lis2[i2]) ++i1;
      else if(lis1[i1] > lis2[i2]) ++ i2;
      else {
        ++i1; ++i2; ++ans;
      }
    }
    printf("%d\n", ans);
    scanf("%d%d", &n1, &n2);
  }
  return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。