| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
随手写的,竟然一遍过了,连线下debug都没de,附代码//============================================================================
// Name : main2034.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
bool isPrime[9956] = {false};
bool isprime(int n){
if(n%2 == 0) return false;
int Sq = (int)sqrt(n * 1.0);
for(int i = 3; i <= Sq; i += 2){
if(n%i == 0) return false;
}
return true;
}
void getPrimeList(){
for(int i = 3; i < 9956; i++){
isPrime[i] = isprime(i);
}
}
bool exists(int n, int m, int d, int ald, bool* state, int* res){
if(ald == m-n+1) return true;
for(int i = n; i <= m; i++){
if(state[i] == 1) continue;
//int ci = 0;
int sum = i;
bool can = true;
for(int j = ald - 1; j >= 0 && j >= ald-d+1; j--){
sum += res[j];
if(isPrime[sum]){
can = false;
break;
}
}
if(!can) continue;
state[i] = 1;
res[ald] = i;
if(exists(n, m, d, ald+1, state, res)){
return true;
}
state[i] = 0;
}
return false;
}
int main() {
getPrimeList();
//cout << 1 << endl;
int n, m, d;
while(1){
cin >> n >> m >> d;
if(n+m+d == 0) return 0;
bool state[1001] = {false};
int res[1001] = {0};
if(exists(n, m, d, 0, state, res)){
for(int i = 0; i < m-n; i++){
cout << res[i] << ",";
}
cout << res[m-n] << endl;
}
else{
cout << "No anti-prime sequence exists." << endl;
}
}
//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator