POJ 1702가 왜 TLE인가. 첫 번째 독립 완성의 귀환을 기념해 주세요.

2500 단어
한 케이스에 최대 20번을 돌리면 TLE입니다. 돌리는 대가가 그렇게 무서워요?
비귀속으로 바꿀까?
당분간 끈기가 없어...
문제를 분석한 후 마침내 독립적으로 이 귀속적인 해법을 생각해 내어 자신을 칭찬하였다
기념해 주세요. TLE지만.
Eva's Balance
Time Limit: 1000MS
 
Memory Limit: 10000K
Total Submissions: 2616
 
Accepted: 1278
Description
Eva has a balance with 20 poises. The weights of the poises are 1, 3, 9, 27,...,3^19. Eva asserts that she has a way to measure any object whose weight is an integer from 1 to (3^20-1)/2. Assuming that Eva has placed an object with the weight in this range on the left tray of the balance, your task is to place the proper poises on the proper trays so as to weigh the object out.
Input
The first line is an integer T (1 <= T <= 20), which shows the number of the test cases. Each of the following T lines contains an integer W (1 <= W <= (3^20-1)/2), expressing the weight of an object.
Output
For each test case print a line, showing the weights of the poises on the left tray and the right tray. Use a space to separate the left tray and the right tray. The poises on the same tray are arranged in the increasing order, and a comma separates every two of them. If there is no poise on the tray, output "empty".
Sample Input
3
9
5
20

Sample Output
empty 9
1,3 9
1,9 3,27

Source
POJ Monthly--2004.07.18
My TLE Code:
#include using namespace std; int poises[20]={0};//-1은 왼쪽, 0은 놓지 않음, 1은 오른쪽 int cubeof_3[21]; int l[20]={0},r[20]={0}; void weight_it(int wei,int side) { int base = 0; for (;base <= 20;base++) { if ((cube_of_3[base]-1)/20) weight_it(wei-cube_of_3[base],side); else weight_it(-(wei-cube_of_3[base]),-side); } int main() { int count; cin>>count; cube_of_3[0] = 1; for (int i = 1;i < 20;i++) cube_of_3[i] = 3*cube_of_3[i-1]; while (count--) { memset(l,0,sizeof(l)); memset(r,0,sizeof(r)); memset(poises,0,sizeof(poises)); int weight; cin>>weight; weight_it(weight,1); int j = 0,k = 0; for (int i = 0;i < 20;i++) { if (poises[i]==-1) { l[j++]=cube_of_3[i]; } else if(poises[i]==1) { r[k++]=cube_of_3[i]; } } if(j==0) cout<<"empty"; for (int i = 0;i < j;i++) { cout<

좋은 웹페이지 즐겨찾기