항 전 "컴퓨터 대학 대학생 프로 그래 밍 경기 (2015 '11)" 문제 풀이 [4 - 6]
11524 단어 알고리즘
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3521 Accepted Submission(s): 1183
Problem Description 샤 오 밍 은 천성적으로 숫자 에 민감 해 3 살 때 원주율 100 위 를 외 울 수 있다.
현재 샤 오 밍 은 점점 자 랐 지만 여전히 숫자 를 좋아한다. 최근 에 그 는 질 수 와 제곱 수 에 빠 졌 고 자신 은 질 수의 제곱 을 '질 방 수' 라 고 명명 했다.현재 그 는 이러한 문 제 를 연구 하고 있다. 정수 N 에서 가장 가 까 운 질 방 수 는 얼마 입 니까?
Input 입력 데이터 의 첫 줄 은 T 조 입력 데이터 가 있 음 을 나타 내 는 정수 T (T < = 20) 이다.다음 T 줄 은 줄 마다 정수 N (1 < = N < = 10 ^ 8) 을 입력 합 니 다.
출력 은 각 그룹의 데이터 에 대해 N 에서 가장 가 까 운 질 방 수 를 출력 하 십시오. 각 그룹의 출력 은 한 줄 을 차지 합 니 다.
Sample Input
2 1 10
Sample Output
4 9
제목 과 뜻 을 개술 하 다.
주어진 n 에서 가장 가 까 운 질량 방 수 를 찾 습 니 다.
제목 분석
n, m 를 소수 로 가정 하고 n
코드
#include
#include
using namespace std;
#define Max 10000
int a[Max+1]={1,1,0};
int main(){
for( int i=2; i<=5000; i++ )
for( int j=i<<1; j1; j+=i ){
a[j]=1;
}
int T;
int N;
cin>>T;
while( T-- ){
cin>>N;
int temp=sqrt(N);
if( temp*temp == N && a[temp]==0 )
cout<else if( temp==1 )
cout<<4<else{
int i, j;
for( i=temp; i>=2; i-- ){
if( a[i]==0 )
break;
}
for( j=temp+1; j<=Max; j++ ){
if( a[j]==0 )
break;
}
if( N-i*i <= j*j-N )
cout<else
cout<
1005 ACM 팀 구성
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 928 Accepted Submission(s): 437
Problem Description ACM 아시아 지역 경기 가 끝 난 것 은 내년 절강성 대학생 프로 그래 밍 경 기 를 준비 하 는 것 을 의미 합 니 다!항 저 우 전자 과 기대 학 ACM 합숙 훈련 대도 팀 구성 을 시작 할 준 비 를 하고 있다.감독 은 모든 n 명의 선 수 를 몇 개의 팀 으로 구성 하려 고 하 는데, 원칙 은 각 팀 이 적어도 한 명, 최대 세 명 이 어야 한 다 는 것 이다.지금 문제 가 생 겼 습 니 다. 합숙 팀 선수 의 수 n 을 알 고 있다 면 가능 한 모든 팀 구성 방안 이 몇 가지 인지 계산 해 주세요.
특히 팀 에 번호 가 없습니다. 즉, A, B, C 세 명 이 있 으 면 {A} {BC} 과 {BC} {A} 은 같은 팀 의 상황 입 니 다.
Input 입력 은 여러 조 의 테스트 데이터 (약 1000 조) 를 포함 하고 각 조 의 데 이 터 는 한 줄 을 차지 하 며 하나의 숫자 n (0 < = n < 20) 을 포함 하여 ACM 합숙 훈련 팀 의 대원 수 를 나타 낸다.n 은 0 으로 입력 이 끝 났 음 을 나타 낸다.
출력 n 개 대원 의 모든 가능 한 파티 방안 수 를 출력 하 십시오. 각 그룹의 출력 은 한 줄 을 차지 합 니 다.
Sample Input
1 2 3 4 5 0
Sample Output
1 2 5 14 46
제목 과 뜻 을 개술 하 다.
n 명 을 정 하여 모든 팀 의 가능 수 를 구하 세 요 (그 중 1 인 1 팀, 2 인 1 팀, 3 인 1 팀)
제목 분석
d [n] 를 n 개인 팀 으로 설정 하 는 모든 가능 한 m 번 째 팀 의 구성 방식 은 다음 과 같은 몇 가지 가 있다. 1 인 1 팀: 모두 d [m - 1] 방식 과 다른 1 인 팀: 모두 d [m - 2] C (n - 1), 1) = d [m - 2] * (n - 1) 방식 과 다른 2 인 팀: 모두 d [m - 3] C ((n - 1), 2) = d [m - 2] (n - 2) (n - 2) / 2 그래서
d[m]=d[m-1]+d[m-2]*(n-1)+d[m-2]*(n-1)*(n-2)/2
코드#include
#include
#include
#include
#include
#include
using namespace std;
#define N 1005
int main(){
int n;
long long f[N]={0,1,2,5};
for(int i=4;i<=20;i++){
f[i]=f[i-1]+(i-1)*f[i-2]+f[i-3]*(i-1)*(i-2)/2;
}
while(scanf("%d",&n),n){
printf("%lld
",f[n]);
}
return 0;
}
1006 역습 지수
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1629 Accepted Submission(s): 314
Problem Description 이것 은 여전히 고부 수 샤 오 밍 에 관 한 이야기 입 니 다.
역경 에 도 불구 하고 샤 오 밍 은 노력 을 포기 하지 않 았 다. 벽돌 을 옮 기 는 것 외 에 샤 오 밍 은 동양 의 팔괘 와 서양의 별 자 리 를 연구 하여 자신 이 역습 할 수 있 는 근 거 를 명리 적 으로 찾 으 려 고 노력 해 왔 다.
이런 것들 이 모두 실패 한 후에 샤 오 밍 은 수학 연구 로 전향 하여 그 중에서 약간의 정 보 를 얻 기 를 희망 했다.어느 날 샤 오 밍 은 이라는 책 을 연구 할 때 소중 한 정 보 를 발견 했다. 그 중에서 모든 사람 에 게 역습 지수 가 존재 하 는데 이 역습 지수 에 대해 연속 적 인 인자 가 존재 할 수 있다. 만약 에 이 연속 인자 가 충분 하 다 면 이 사람 이 역습 할 확률 이 매우 크다!
샤 오 밍 은 자신의 역습 지 수 를 알 고 있 으 니 샤 오 밍 에 게 가장 긴 연속 요 소 를 알려 자신 이 역습 할 수 있 는 지 없 는 지 를 판단 하 게 해 주세요.
Input 입력 은 여러 그룹의 테스트 데 이 터 를 포함 합 니 다.각 조 의 데 이 터 는 한 줄 을 차지 하고 하나의 정수 N 을 포함 하 며 샤 오 밍 의 역습 지 수 를 나타 내 며 N 은 2 ^ 31 보다 작다.
출력 은 각 그룹의 데이터 에 대해 2 줄 을 출력 하 십시오. 첫 번 째 줄 에서 가장 긴 인자 개 수 를 출력 하 십시오.두 번 째 줄 의 출력 최소 인자 서열 은 구체 적 으로 사례 를 참고 하 시기 바 랍 니 다.
특히 샤 오 밍 은 싱글 을 싫어 하기 때문에 1 은 인자 가 아니다.
Sample Input
630 12
Sample Output
3 5*6*7 2 2*3
Hint
630 = 3*5*6*7
제목 분석
n 구 n 의 최 장 연속 인자 (1 제외) 길 이 를 정 하고 (여러 개 있 으 면 첫 번 째 로 가장 작은 것 을 취하 고) 곱 하기 n 인자 입 니 다.
제목 분석
폭력 구 해 는 n 의 모든 가능 한 인자 (2. sqrt (n) 를 옮 겨 다 니 며 가장 긴 연속 요 소 를 찾 습 니 다.
코드
#include
#include
#include
#include
using namespace std;
int main()
{
//cout<
long long m;
while(~scanf("%d",&m)){
long long mult=1;
long long sum=0;
long long last = 0;
long long tempSum = 0;
long long orig = m;
for(long long j=2;j*j<=m;j++){
for(long long i=j;i<=m;i++){
if(orig%i==0){//
mult*=i;
if(orig%mult==0){//
tempSum++;
if(tempSum>sum){//
sum=tempSum;
last = i;
}
}else{// init
tempSum = 0;
mult = 1;
break;
}
}else{//
tempSum = 0;
mult = 1;
break;
}
}
}
if(sum==0){
printf("1
%d
",orig);
}else{
printf("%d
",sum);
for(long long i = sum-1;i>=1;i--){
printf("%d*",last-i);
}
printf("%d
",last);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.