首页 > 代码库 > 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 }
uva 10344 算23点
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。