hdu1495

maksyuki 发表于 oj 分类，标签: 基础算法-搜索(DFS\BFS)\记忆化

07 11月 2015

非常可乐

大家一定觉的运动以后喝可乐是一件很惬意的事情，但是seeyou却不这么认为。因为每次当seeyou买了可乐以后，阿牛就要求和seeyou一起分享这一瓶可乐，而且一定要喝的和seeyou一样多。但seeyou的手中只有两个杯子，它们的容量分别是N 毫升和M 毫升可乐的体积为S （S<101）毫升(正好装满一瓶) ，它们三个之间可以相互倒可乐 (都是没有刻度的，且 S==N+M，101＞S＞0，N＞0，M＞0) 。聪明的ACMER你们说他们能平分吗？如果能请输出倒可乐的最少的次数，如果不能输出"NO"。

Input

三个整数 : S 可乐的体积 , N 和 M是两个杯子的容量，以"0 0 0"结束。

Output

如果能平分的话请输出最少要倒的次数，否则输出"NO"。

Sample Input

7 4 3
4 1 3
0 0 0

Sample Output

Author

seeyou

Source

“2006校园文化活动月”之“校庆杯”大学生程序设计竞赛暨杭州电子科技大学第四届大学生程序设计竞赛

题目类型：BFS

算法分析：每个状态定义为一个四元组(a, b, c, cnt)，分别表示可乐瓶、杯子A、杯子B中可乐的体积和步数，最后按照题目的要求进行相应的转移即可

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int S, N, M, all;
bool vis[166][166][166];

struct node
{
    int a, b, c, cnt;
    node (int aa, int bb, int cc, int ccnt) : a (aa), b (bb), c (cc), cnt (ccnt) {}
    node () {}
};

bool bin (int a, int b)
{
    if (a == all / 2 && b == all / 2)
        return true;
    return false;
}

queue <node> qu;

void SS (int a, int b, int c, int cnt)
{
    if (!vis[a][b][c])
    {
        vis[a][b][c] = true;
        qu.push (node (a, b, c, cnt + 1));
    }
}

int bfs ()
{
    memset (vis, false, sizeof (vis));
    vis[S][0][0] = true;
    while (!qu.empty ()) qu.pop ();
    qu.push (node (S, 0, 0, 0));
    while (!qu.empty ())
    {
        node tt = qu.front (); qu.pop ();
        if (bin (tt.a, tt.b) || bin (tt.b, tt.c) || bin (tt.a, tt.c))
        {
            return tt.cnt;
        }

        int tx, ta, tb, tc;
        tx = min (tt.a, N - tt.b);
        ta = tt.a - tx, tb = tt.b + tx, tc = tt.c;
        SS (ta, tb, tc, tt.cnt);


        tx = min (tt.a, M - tt.c);
        ta = tt.a - tx, tb = tt.b, tc = tt.c + tx;
        SS (ta, tb, tc, tt.cnt);

        tx = N - tt.b + M - tt.c;
        if (tt.a >= tx)
        {
            ta = tt.a - tx, tb = N, tc = M;
            SS (ta, tb, tc, tt.cnt);
        }
////////////////////////////////////////
        tx = min (tt.b, S - tt.a);
        ta = tt.a + tx, tb = tt.b - tx, tc = tt.c;
        SS (ta, tb, tc, tt.cnt);


        tx = min (tt.b, M - tt.c);
        ta = tt.a, tb = tt.b - tx, tc = tt.c + tx;
        SS (ta, tb, tc, tt.cnt);

        tx = S - tt.a + M - tt.c;
        if (tt.b >= tx)
        {
            ta = S, tb = tt.b - tx, tc = M;
            SS (ta, tb, tc, tt.cnt);
        }
/////////////////////////////////////////
        tx = min (tt.c, S - tt.a);
        ta = tt.a + tx, tb = tt.b, tc = tt.c - tx;
        SS (ta, tb, tc, tt.cnt);

        tx = min (tt.c, N - tt.b);
        ta = tt.a, tb = tt.b + tx, tc = tt.c - tx;
        SS (ta, tb, tc, tt.cnt);

        tx = S - tt.a + N - tt.b;
        if (tt.c >= tx)
        {
            ta = S, tb = N, tc = tt.c - tx;
            SS (ta, tb, tc, tt.cnt);
        }
    }
    return -1;
}

int main()
{
//    CFF;
    while (scanf ("%d %d %d", &S, &N, &M) != EOF)
    {
        if (S == 0 && N == 0 && M == 0)
            break;

        if (S & 1)
        {
            puts ("NO");
            continue;
        }

        all = S;
        int tt = bfs ();
        if (tt == -1) puts ("NO");
        else printf ("%d\n", tt);
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7FFFFFFF;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

const int dx[] = {-1, 1, 0, 0};

const int dy[] = {0, 0, -1, 1};

int S, N, M, all;

bool vis[166][166][166];

struct node

{

int a, b, c, cnt;

node (int aa, int bb, int cc, int ccnt) : a (aa), b (bb), c (cc), cnt (ccnt) {}

node () {}

};

bool bin (int a, int b)

{

if (a == all / 2 && b == all / 2)

return true;

return false;

}

queue <node> qu;

void SS (int a, int b, int c, int cnt)

{

if (!vis[a][b][c])

{

vis[a][b][c] = true;

qu.push (node (a, b, c, cnt + 1));

}

int bfs ()

{

memset (vis, false, sizeof (vis));

vis[S][0][0] = true;

while (!qu.empty ()) qu.pop ();

qu.push (node (S, 0, 0, 0));

while (!qu.empty ())

{

node tt = qu.front (); qu.pop ();

if (bin (tt.a, tt.b) || bin (tt.b, tt.c) || bin (tt.a, tt.c))

{

return tt.cnt;

}

int tx, ta, tb, tc;

tx = min (tt.a, N - tt.b);

ta = tt.a - tx, tb = tt.b + tx, tc = tt.c;

SS (ta, tb, tc, tt.cnt);

tx = min (tt.a, M - tt.c);

ta = tt.a - tx, tb = tt.b, tc = tt.c + tx;

SS (ta, tb, tc, tt.cnt);

tx = N - tt.b + M - tt.c;

if (tt.a >= tx)

{

ta = tt.a - tx, tb = N, tc = M;

SS (ta, tb, tc, tt.cnt);

}

////////////////////////////////////////

tx = min (tt.b, S - tt.a);

ta = tt.a + tx, tb = tt.b - tx, tc = tt.c;

SS (ta, tb, tc, tt.cnt);

tx = min (tt.b, M - tt.c);

ta = tt.a, tb = tt.b - tx, tc = tt.c + tx;

SS (ta, tb, tc, tt.cnt);

tx = S - tt.a + M - tt.c;

if (tt.b >= tx)

{

ta = S, tb = tt.b - tx, tc = M;

SS (ta, tb, tc, tt.cnt);

}

/////////////////////////////////////////

tx = min (tt.c, S - tt.a);

ta = tt.a + tx, tb = tt.b, tc = tt.c - tx;

SS (ta, tb, tc, tt.cnt);

tx = min (tt.c, N - tt.b);

ta = tt.a, tb = tt.b + tx, tc = tt.c - tx;

SS (ta, tb, tc, tt.cnt);

tx = S - tt.a + N - tt.b;

if (tt.c >= tx)

{

ta = S, tb = N, tc = tt.c - tx;

SS (ta, tb, tc, tt.cnt);

}

return -1;

}

int main()

{

// CFF;

while (scanf ("%d %d %d", &S, &N, &M) != EOF)

{

if (S == 0 && N == 0 && M == 0)

break;

if (S & 1)

{

puts ("NO");

continue;

}

all = S;

int tt = bfs ();

if (tt == -1) puts ("NO");

else printf ("%d\n", tt);

}

return 0;

}

hdu2612

poj3279

超客的水墨烟雨

hdu1495

非常可乐

分类目录

标签云

书签

近期评论

2024年12月
一	二	三	四	五	六	日
« 6月
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31