[UVA][數學&窮舉] 10317 - Equating Equations＠Morris' Blog

2013-12-01 11:31:51| 人氣1,567| 回應0 | 上一篇 | 下一篇

[UVA][數學&窮舉] 10317 - Equating Equations

推薦 0 收藏 0 轉貼0 訂閱站台

Problem F

Equating Equations

Input: standard input

Output: standard output

Time Limit: 6 seconds

Memory Limit: 32 MB

Read equations with up to 16 terms and + and – operators (not unary) and reorder the terms (but not the operators) so that the equations hold. For example

   1 + 2 = 4 - 5 + 6

is not a correct equation but the terms can be rearranged thus so it is:

   6 + 2 = 4 - 1 + 5

Input

Standard input consists of several pseudo-equations, one per line. Each pseudo-equation has up to 16 integer terms and each term is less than 100. Adjacent terms are separated by one operator, and spaces always appear surrounding the terms. There is exactly one = operator in the equation

Output

Your output will consist of one line per input line, with the same operators and the same terms. The order of the operators must be preserved, but the terms can be reordered so the equation holds. Any ordering such that the equation holds is correct. If there is more than one ordering any one of the orderings will do. If no ordering exists, a line containing

   no solution

should be printed. One space should appear on either side of each operator and there should be no other spaces.

Sample Input

1 + 2 = 4 - 5 + 6

1 + 5 = 6 + 7

Sample Output

6 + 2 = 4 - 1 + 5

no solution

(The Decider Contest, Source: Waterloo ACM Programming Contest)

題目描述：

只有加減等號和整數，調整整數的位置，使得等號成立。整數個數小於等於 16。

題目解法：

將等號右邊的數字全部搬到左側，藉由加減號將數字可以分成兩堆，若等號成立，則兩堆的總和要相同。
由於不曉得數字有多大，無法使用 DP，藉由窮舉 2^16 找到其中一堆的總和能不能等於全部總和的一半。

#include <stdio.h>
#include <iostream>
#include <sstream>
using namespace std;

int main() {
   char s[1024] = "+ ";
   int i, j, k;
   while(gets(s+2)) {
       stringstream sin(s);
       int x[20], n = 0, eq = -1;
       string token[20];
       while(sin >> token[n] >> x[n]) {
           if(token[n] == "=") {
               eq = n;
               token[n] = "+";
           }
           n++;
       }
       int neg = 0, pos = 0;
       int sum = 0;
       for(i = 0; i < n; i++)
           sum += x[i];
       for(i = 0; i < eq; i++) {
           if(token[i] == "+")
               pos++;
           else
               neg++;
       }
       for(i = eq; i < n; i++) {
           if(token[i] == "+")
               neg++;
           else
               pos++;
       }
       if(sum&1)
           puts("no solution");
       else {
           int ret = -1;
           for(i = (1<<n)-1; i >= 0; i--) {
               int hsum = 0, cnt = 0;
               for(j = 0, k = 0; j < n; j++) {
                   if((i>>j)&1)
                       hsum += x[j], cnt++;
               }
               if(cnt == pos && hsum*2 == sum) {
                   ret = i;
                   i = -1;
               }
           }
           if(ret == -1)
               puts("no solution");
           else {
               int A[20], B[20], Aidx = 0, Bidx = 0;
               for(i = 0; i < n; i++) {
                   if((ret>>i)&1)
                       A[Aidx++] = x[i];
                   else
                       B[Bidx++] = x[i];
               }
               Aidx = 0, Bidx = 0;
               printf("%d", A[Aidx++]);
               for(i = 1; i < eq; i++) {
                   if(token[i] == "+")
                       printf(" + %d", A[Aidx++]);
                   else
                       printf(" - %d", B[Bidx++]);
               }
               printf(" = %d", B[Bidx++]);
               for(i = eq+1; i < n; i++) {
                   if(token[i] == "+")
                       printf(" + %d", B[Bidx++]);
                   else
                       printf(" - %d", A[Aidx++]);
               }
               puts("");
           }
       }
   }
   return 0;
}
/*
1 + 2 = 4 - 5 + 6
1 + 5 = 6 + 7
*/

我要檢舉

#10317#Equating Equations#數學#窮舉

台長： Morris

您可能對以下文章有興趣

[UVA][字串] 126 - The Errant Physicist

d766. 11149 - Power of Matrix

[UVA] 12366 - King's Poker

[UVA] 11393 - Tri-Isomorphism

人氣(1,567) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 教育學習(進修、留學、學術研究、教育概況) | 個人分類: UVA |
此分類下一篇:[UVA][數學] 10329 - Combinatorial Expression
此分類上一篇:[UVA][窮舉] 10396 - Vampire Numbers

回應(0)