首页 > 代码库 > uva 10344 算23点

uva 10344 算23点

// 题意:输入5个整数,按照某种顺序排列后依次进行+, -或者*,使得最终结果为23。判断是否有解 

// 算法:回溯 

 

 1 #include <cstdio> 2 #include <cstdlib> 3 #include <cctype> 4 #include <cstring> 5 #include <cmath> 6 #include <ctime> 7 #include <string> 8 #include <vector> 9 #include <map>10 #include <set>11 #include <algorithm>12 #include <iostream>13 using namespace std;14 typedef long long ll;15 int a[10];16 int mark[10];17 bool flag;18 19 int Sum( int x, int ans, int m )20 {21     if( x == 0 )22         return ans + m;23     if( x == 1 )24         return ans - m;25     return ans * m;26 }27 28 void dfs( int x, int ans )29 {30     if( flag )31         return;32     if( x == 5 )33     {34         if( ans == 23 )35             flag = true;36         return;37     }38     for( int i = 0; i < 5; ++i )39         if( !mark[i] )40         {41             mark[i] = 1;42             dfs( x+1, Sum( 0, ans, a[i] ) );43             dfs( x+1, Sum( 1, ans, a[i] ) );44             dfs( x+1, Sum( 2, ans, a[i] ) );45             mark[i] = 0;46         }47 }48 49 void solve()50 {51     for( int i = 0; i < 5; ++i )52     {53         memset( mark, 0, sizeof( mark ) );54         mark[i] = 1;55         dfs( 1, a[i] );56     }57 }58 59 int main()60 {61     while( ~scanf( "%d%d%d%d%d", &a[0], &a[1], &a[2], &a[3], &a[4] ) && a[0]+a[1]+a[2]+a[3]+a[4] )62     {63         flag = false;64         solve();65         if( flag )66             puts( "Possible" );67         else68             puts( "Impossible" );69     }70     return 0;71 }
View Code

 

uva 10344 算23点