Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:终于不打表AC,282ms,放出代码,求更快的解法……

Posted by purenanya at 2011-04-29 17:21:48 on Problem 1012
In Reply To:终于不打表AC,282ms,放出代码,求更快的解法…… Posted by:alexneko at 2008-07-12 16:14:45
跟你的思路差不多,但是我的执行时间要长一倍,可能是因为G++和STL的缘故、

#include <iostream>
#include <vector>

using namespace std;

int joseph[14];

int Joseph(int k) {
	int m;	
	int NumOfGuys = 2 * k;

	//the kicking-out process
	int starter;
	int i;//index of the kicked out person
	int n = NumOfGuys;//number of persons in the circle
	m = k + 1; 
	while (n > k) {
		n = NumOfGuys;
		starter = 0;
		while (n > k) {
			i = (starter + m - 1) % n;
			//a good guy is kicked out
			if (i < k) {
				m ++;
				break;
			}
			n --;
			starter = i;
		}
	}
	
	return m;
}

int main() {
	int k;
	vector<int> results;
	vector<int>::iterator it;
	
	//pre-store the results
	for (int i = 1; i < 14; i ++) {
		joseph[i] = Joseph(i);
	}
	
	//for (cin >> k; k != 0; N ++) {
	cin >> k;
	while (k != 0) {
		results.push_back(joseph[k]);
		cin >> k;
	}
	
	for (it=results.begin() ; it < results.end(); it++) {
		cout << *it << endl;
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator