1103. Integer Factorization (30)

제목 링크:http://www.patest.cn/contests/pat-a-practise/1103
제목:
The K-P factorization of a positive integer N is to write N as the sum of the P-th power of K positive integers. You are supposed to write a program to find the K-P factorization of N for any positive integers N, K and P.
Input Specification:
Each input file contains one test case which gives in a line the three positive integers N (<=400), K (<=N) and P (1Output Specification:
For each case, if the solution exists, output in the format:
N = n1^P + ... nK^P
where ni (i=1, ... K) is the i-th factor. All the factors must be printed in non-increasing order.
Note: the solution may not be unique. For example, the 5-2 factorization of 169 has 9 solutions, such as 122 + 42 + 22 + 22 + 12, or 112 + 62 + 22 + 22 + 22, or more. You must output the one with the maximum sum of the factors. If there is a tie, the largest factor sequence must be chosen -- sequence { a1, a2, ... aK } is said to be larger than { b1, b2, ... bK } if there exists 1<=L<=K such that ai=bi for ibL
If there is no solution, simple output "Impossible".
Sample Input 1:

169 5 2

Sample Output 1:

169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2

Sample Input 2:

169 167 3

Sample Output 2:

Impossible

분석:
DFS + 가지치기
테스트 포인트 1, 4, 7 중 하 나 는 Impossible 일 거 예요.
테스트 포인트 5 는 어 려 운 문제 입 니 다. 저 는 여러 가지 가지치기 로 바 꾸 었 습 니 다. 여러 가지 바 꾸 어도 안 됩 니 다. accumulate 와 비 교 를 모두 제 가 쓴 것 으로 안 됩 니까? 마지막 에 원흉 을 찾 았 습 니 다. 바로...
pow, 자기가 쓴 kpow 로 바 꾸 고 통 과 했 어 요.
pow 는 큰 구덩이 입 니 다. 이 유 는 float, int 와 double, int 만 있 기 때 문 일 수 있 습 니 다. 반환 값 은 float 또는 double 의 과부하 입 니 다. int, int 로 int 를 되 돌려 주면 시간 소모 가 너무 큽 니 다.
AC 코드:

#include <iostream> 
#include<stdio.h> 
#include<algorithm> 
#include<string> 
#include<vector> 
#include<queue> 
#include<numeric>//include accumulate 
using namespace std; 
int aceil[8] = { 0, 0, 20, 7, 4, 3, 2, 2 };//    ，   p=4 ，ceil[4]=4，  4^4<400 5^4>400 
//  4  ans        ，ans[i]   <=aceil[p]，  ceil       ，       aceil 
int n, k, p;//       ，  DFS            
vector<int>v_tmp;//           
vector<vector<int>>ans;//        
int kpow(int x, int y){ 
 int ret = x; 
 while (--y){ 
  ret *= x; 
 } 
 return ret; 
} 
void DFS(int start, int curSum, int count){//         ，   sum    
 for (int i = start; i <= aceil[p]; ++i){ 
  int sum_tmp = curSum + kpow(i, p);//*point，   pow   5   ，       kpow 
  if (sum_tmp > n)return;//  ，       
  if (count == k - 1 && sum_tmp < n)continue;//  ，            
  if(count == k - 1 && sum_tmp == n){ 
   v_tmp.push_back(i); 
   ans.push_back(v_tmp); 
   v_tmp.pop_back(); 
   return; 
  } 
  v_tmp.push_back(i);//   DFS  ：  ，  ，   （  ） 
  DFS(i, sum_tmp, count + 1); 
  v_tmp.pop_back(); 
 } 
 return; 
} 
/*    accumulate     ，        ，      
int vSum(vector<int>Vx){ 
 int ret = 0; 
 for (int i = 0; i < Vx.size(); ++i){ 
  ret += Vx[i]; 
 } 
 return ret; 
} 
*/ 
bool cmp(vector<int>V1, vector<int>V2){ 
 if (accumulate(V1.begin(), V1.end(), 0) != accumulate(V2.begin(), V2.end(), 0))//accumulate 3    init，     0 OK 
  return accumulate(V1.begin(), V1.end(), 0) > accumulate(V2.begin(), V2.end(), 0); 
 else{ 
  return V1 > V2;//vector   <   ，         ，        
 } 
} 
void print(vector<int> Vx){//  vector      ，        
 cout << n << " = "; 
 for (int i = 0; i < Vx.size(); ++i){ 
  if (i) cout << " + " << Vx[i] << "^" << p; 
  else cout << Vx[i]<< "^" << p; 
 } 
} 
int main(){ 
 freopen("F://Temp/input.txt", "r", stdin); 
 cin >> n >> k >> p; 
 /*    p > 1，    p    1  ，        
 if (p == 1){// p 1 ，         
  v_tmp.push_back(n - k + 1); 
  for (int i = 0; i < k - 1; i++){ 
   v_tmp.push_back(1); 
  } 
  print(v_tmp); 
  cout << endl; 
  return 0; 
 } 
 */ 
 DFS(1, 0, 0);//    
 if (ans.size() == 0){//      ，       
  cout << "Impossible" << endl; 
  return 0; 
 } 
 for (int i = 0; i < ans.size(); ++i){ 
  reverse(ans[i].begin(), ans[i].end());//         ，         ，     
 } 
 sort(ans.begin(), ans.end(), cmp);//             ，          
 print(ans[0]); 
 cout << endl; 
 return 0; 
}

캡 처:

P.S:
쌍둥이 의 방법:
코드 가 더 간결 하고 더 좋 습 니 다. 그리고:
그냥 pow 를 쓰 지 않 고 필요 한 모든 숫자 를 먼저 계산 할 수 있 습 니 다.
그리고 마지막 답 도 정렬 하지 않 습 니 다. 수학의 측면 에서 볼 때 마지막 으로 얻 은 답 이 가장 가 깝 기 때 문 입 니 다. 즉, 가장 좋 은 답 입 니 다. 마지막 하 나 를 계속 유지 하면 됩 니 다.
그 중에서 if (n - num [i]) < 0 은 내 위의 aceil [i] 배열 효과 와 원리 가 같다.
-- 에이 피 진 소 욱

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[BOJ] 5568 카드 놓기

아이디어 Level이 0일 때, 즉 아직 카드를 고르지 않았을 때 StringBuilder를 생성하고 sb에 고른 카드를 담도록 하였다. 이후 해당 노드 탐색을 종료하면 sb에 담은 카드를 삭제해 주었다....

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

1103. Integer Factorization (30)

좋은 웹페이지 즐겨찾기