2011-11-12 06:46:36Morris
a274. 友誼的數字
a274. 友誼的數字
/**********************************************************************************/
/* Problem: a274 "友誼的數字" from */
/* Language: C (915 Bytes) */
/* Result: AC(4ms, 312KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-11-11 11:42:29 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int cmp(const void *i, const void *j) {
return *(long long *)i - *(long long *)j;
}
long long A[11], Way[11];
int flag, Used[11], N;
void DFS(int idx, int n) {
int i;
long long x, y;
if(n == 0) {
for(i = 0; i < idx; i++)
printf("%lld ", Way[i]);
puts("");
flag = 1;return;
}
if(idx >= 2) x = Way[idx-1]+Way[idx-2], y = Way[idx-1]*Way[idx-2];
for(i = 0; i < N; i++) {
if(!Used[i]) {
if(idx < 2 || (idx >= 2 && (x%A[i] == 0 || y%A[i] == 0))) {
Used[i] = 1;
Way[idx] = A[i];
DFS(idx+1, n-1);
Used[i] = 0;
}
if(flag) return;
}
}
}
int main() {
int i, j;
while(scanf("%d", &N) == 1) {
for(i = 0; i < N; i++)
scanf("%lld", &A[i]);
qsort(A, N, sizeof(long long), cmp);
memset(Used, 0, sizeof(Used));
flag = 0, DFS(0, N);
if(!flag)
puts("No");
}
return 0;
}
內容 ：
你相信數字之間也是有友誼存在嗎？
不管你信不信，反正我是信了
你想要讓他們乖乖的排成一個橫列，但是顯然他們不太聽話，會活蹦亂跳
在你仔細觀察之後你發現一個現象，最左邊的那個數字就像班長一樣身負重責大任
一指定了就也不會再動了，左邊第二個，他覺得站在班長旁邊於有榮焉，
所以也很安分的站著。
接著，剩下的就麻煩了，他們都會覺得站在他們左邊的人
必須有足夠的能力能夠領導他們，他們才會安分，而且還要很合他們的個性
所以在你嘗試多次之後發現，這些數字會希望左邊兩位數字的 "和" 或者 "乘積"
是他們的倍數，這樣他們才會安分的站著
你的任務就是給定 N 個數字後，幫他們找到適當的位置排好
輸入說明
：
多組輸入，以EOF作為結束
每組第一行為一個正整數 N ，第二行會有 N 個數字 Ai
1 <= N <= 10
1 <= Ai <= 10,000,000
輸出說明
：
輸出一個符合題目要求的數列，如果有多組解，輸出字典序最小的數列
無解請輸出 No
範例輸入 ：
5 1 1 1 1 1 4 5 3 3 2 3 5 7 9
範例輸出 ：
1 1 1 1 1 2 3 5 3 5 9 7
提示
：
出處
：
/**********************************************************************************/
/* Problem: a274 "友誼的數字" from */
/* Language: C (915 Bytes) */
/* Result: AC(4ms, 312KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-11-11 11:42:29 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int cmp(const void *i, const void *j) {
return *(long long *)i - *(long long *)j;
}
long long A[11], Way[11];
int flag, Used[11], N;
void DFS(int idx, int n) {
int i;
long long x, y;
if(n == 0) {
for(i = 0; i < idx; i++)
printf("%lld ", Way[i]);
puts("");
flag = 1;return;
}
if(idx >= 2) x = Way[idx-1]+Way[idx-2], y = Way[idx-1]*Way[idx-2];
for(i = 0; i < N; i++) {
if(!Used[i]) {
if(idx < 2 || (idx >= 2 && (x%A[i] == 0 || y%A[i] == 0))) {
Used[i] = 1;
Way[idx] = A[i];
DFS(idx+1, n-1);
Used[i] = 0;
}
if(flag) return;
}
}
}
int main() {
int i, j;
while(scanf("%d", &N) == 1) {
for(i = 0; i < N; i++)
scanf("%lld", &A[i]);
qsort(A, N, sizeof(long long), cmp);
memset(Used, 0, sizeof(Used));
flag = 0, DFS(0, N);
if(!flag)
puts("No");
}
return 0;
}