화 웨 이 oj 소수 배우자
, “ ”, 2 5、6 13, 。 , N(N ) “ ”, , 4 :2,5,6,13, 5 6 “ ”, 2 5、6 13 “ ”, “ ” “ ”, “ ”。
:
N(N≤100), 。 , [2,30000]。
:
K, “ ” “ ” 。
입력
입력 설명 1 짝수 n 2 입력 정수 n 개 입력
출력
구 하 는 '최선 의 방안' 은 '소수 동반자' 의 대 수 를 구성한다.
샘플 입력
4 2 5 6 13
샘플 출력
2
이 문제 에 대해 저 는 제목 의 본 의 는 헝가리 알고리즘 을 사용 하여 가장 일치 하 는 문 제 를 계산 하 는 것 이 라 고 생각 합 니 다. 두 개의 수의 합 이 하나의 소수 라면 반드시 홀수 와 짝수 의 조합 이기 때문에 두 개의 집합 으로 나 누 어 이분 도의 가장 큰 일치 문 제 를 구 할 수 있 습 니 다. 그러나 블 로 거들 은 그 당시 에 도 많은 생각 을 하지 않 았 습 니 다.모든 가능성 을 다 배열 해서 토론 했다.이것 은 가장 직접적인 생각 입 니 다. 다음은 c + + 실 현 된 소수 배우자의 코드 입 니 다.
#include <iostream>
#include <algorithm>
using namespace std;
int maxx = 0;
int main(){
bool sushu(int x,int y);
void permutation(int* str,int length) ;
int n;
cin >> n;
int * pi = new int[n];
for (int i = 0; i < n;i++)
cin >> pi[i];
permutation(pi,n);
cout << maxx << endl;
return 0;
}
bool sushu(int x,int y){
int i,N;
N = x + y;
int flag=true;
if (N==1) return 0;
if (N==2) return 1;
for (i=2;i<=sqrt(N);i++){
if (N%i==0)
{
flag=false;
break;
}
}
return flag;
}
void permutation(int* str,int length)
{
int count = 0;
sort(str,str+length);
do
{
for(int i=0;i<length;i+=2) {
if (sushu(str[i],str[i+1]))
count++;
}
if (maxx < count)
maxx = count;
count = 0;
}while(next_permutation(str,str+length));
}
next_permutation() c++ , , 。
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.