NEW RDSP MODE I

NEW RDSP MODE I

时间: 1ms        内存:128M

描述:

Little A has became fascinated with the game Dota recently, but he is not a good player. In all the modes, the rdsp Mode is popular on online, in this mode, little A always loses games if he gets strange heroes, because, the heroes are distributed randomly.

Little A wants to win the game, so he cracks the code of the rdsp mode with his talent on programming. The following description is about the rdsp mode:

There are N heroes in the game, and they all have a unique number between 1 and N. At the beginning of game, all heroes will be sorted by the number in ascending order. So, all heroes form a sequence One.

These heroes will be operated by the following stages M times:

1.Get out the heroes in odd position of sequence One to form a new sequence Two;

2.Let the remaining heroes in even position to form a new sequence Three;

3.Add the sequence Two to the back of sequence Three to form a new sequence One.

After M times' operation, the X heroes in the front of new sequence One will be chosen to be Little A's heroes. The problem for you is to tell little A the numbers of his heroes.

输入:

There are several test cases.

Each case contains three integers N (1<=N<1,000,000), M (1<=M<100,000,000), X(1<=X<=20).

Proceed to the end of file.

输出:

For each test case, output X integers indicate the number of heroes. There is a space between two numbers. The output of one test case occupied exactly one line.

示例输入:

5 1 2
5 2 2

示例输出:

2 4
4 3

提示:

参考答案(内存最优[800]):

#include <stdio.h>

#include <math.h>

#define __int64 long long

long long done(int m, int n)

{

	if(n == 0)

	{

		return 1;

	}

	if(n == 1)

	{

		return 2;

	}

	__int64 t = done(m, n/2);

	t = t*t;

	if(n%2 == 0)

	{

		return (long long)(((t%m)==0)?m:t%m);

	}

	else

	{

		return (long long)(((2*t%m)==0) ? m : t%m*2);

	}

}



int main()

{

//	freopen("in.in","r",stdin);

	//freopen("test.out","w",stdout);

	//printf("%I64d", ((__int64)(pow(2,59))%1223411) );

	int m,n,x;

	long long t;

	int i;

	while(scanf("%d %d %d",&m, &n, &x)!=EOF)

	{

		if(m % 2 == 0)

		 	m +=1;

		t = done(m, n);

		t = t == 0?m:t;

		//printf("%d\n",t);

		for(i=1; i<=x; ++i)

		{

			if(i != 1)

			{

				printf(" ");

			}

			printf("%lld", t*i%m == 0?m: t*i%m);

		}

		printf("\n");

	}

}

参考答案(时间最优[0]):

#include<iostream>
using namespace std;

int r[] = {0, 0, 1, -1};
int c[] = {1, -1, 0, 0};

int maxi(int a, int b) {
	if(a > b) return a;
	return b;
}

int dfs(char graph[][100], int row, int col, int maxRow, int maxCol) {
	if(row < 0 || row >= maxRow) return 0;
	if(col < 0 || col >= maxCol) return 0;
	if(graph[row][col] != '*') return 0;
	
	graph[row][col] = '#';
	int ret = 1;

	for(int i=0; i<4; i++) ret += dfs(graph, row+r[i], col+c[i], maxRow, maxCol);

	return ret;
}


int main(void) {
	int row, col;
	while(cin >> col >> row) {
		int answer = 0;
		char graph[1100][100];
		for(int i=0; i<row; i++)
			for(int j=0; j<col; j++) cin >> graph[i][j];
		for(int i=0; i<row; i++) {
			for(int j=0; j<col; j++) {
				if(graph[i][j] == '*') {
					answer = maxi(answer, dfs(graph, i, j, row, col));
				}
			}
		}
		cout << answer << endl;
	}
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注