HDU 4791 Alice's Print Service
从后往前预处理打印纸的最小花费。然后在询问时通过upper_bound找到位置p，比较当前打印纸张花费与相邻临界点最小花费即可。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
int T;
const int maxn = 100010;
const int INF = 0x3f3f3f3f;
typedef long long LL;
LL x[maxn], y[maxn];
LL cost[maxn];
int main()
{
int T;
for(scanf("%d", &T); T > 0; T--)
{
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++)
{
scanf("%I64d%I64d", &x[i], &y[i]);
cost[i] = x[i]*y[i];
}
LL pre = cost[n-1];
for(int i = n-1; i >= 0; i--)
{
if(pre < cost[i])
{
cost[i] = pre;
pre = cost[i];
}
}
while(m--)
{
LL q; scanf("%I64d", &q);
if(q >= x[n-1]) { printf("%I64d\n", q*y[n-1]); continue ; }
LL p = upper_bound(x, x+n, q)-x;
LL ans = q*y[p-1];
ans = min(ans, cost[p]);
printf("%I64d\n", ans);
}
}
return 0;
}
2014 ACM/ICPC Asia Regional 广州网赛 | HDU 5023 & HDU 5024 & HDU 5025
HDU 5203：给定一段区间，初始颜色为2，你可以将一整段区间涂成某一种颜色，询问一段区间上的颜色数。
线段树操作。由于颜色最多只有30种，我们可以利用一个int来处理所有的颜色，向下用&运算，向上用|运算来合并所有颜色即可。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000100;
#define lc o<<1
#define rc o<<1|1
struct SegmentTree
{
int color[maxn<<2];
int setv[maxn<<2];
int n;
void init(int n)
{
this->n = n;
}
void pushup(int o)
{
color[o] = color[lc] | color[rc];
}
void build(int o, int L, int R)
{
color[o] = (1<<1); setv[o] = 2;
if(L == R) return ;
int M = L+(R-L)/2;
build(lc, L, M);
build(rc, M+1, R);
pushup(o);
}
void pushdown(int o, int L, int R)
{
if(setv[o])
{
color[lc] = (1<<(setv[o]-1));
color[rc] = (1<<(setv[o]-1));
setv[lc] = setv[rc] = setv[o];
setv[o] = 0;
}
}
void update(int o, int L, int R, int y1, int y2, int v)
{
if(y1 <= L && y2 >= R)
{
color[o] = (1<<(v-1));
setv[o] = v;
return ;
}
int M = L+(R-L)/2;
pushdown(o, L, R);
if(y1 <= M) update(lc, L, M, y1, y2, v);
if(y2 > M) update(rc, M+1, R, y1, y2, v);
pushup(o);
}
int query(int o, int L, int R, int y1, int y2)
{
if(y1 <= L && y2 >= R) return color[o];
int M = L+(R-L)/2;
pushdown(o, L, R);
int ans = 0;
if(y1 <= M) ans |= query(lc, L, M, y1 ,y2);
if(y2 > M) ans |= query(rc, M+1, R, y1, y2);
return ans;
}
void print(int o, int L, int R)
{
printf("%d ", color[o]);
if(L == R) return ;
int M = L+(R-L)/2;
print(lc, L, M); print(rc, M+1, R);
}
};
////////////////
void readint(int &x)
{
char c = getchar();
while(!isdigit(c)) c = getchar();
x = 0;
while(isdigit(c))
{
x = x*10+c-'0';
c = getchar();
}
}
void writeint(int x)
{
if(x > 9) writeint(x/10);
printf("%d", x%10);
}
SegmentTree g;
int n, m, c;
int main()
{
while(~scanf("%d%d", &n, &m))
{
if(n == 0 && m == 0) break;
g.init(n+10);
g.build(1, 1, n);
while(m--)
{
char cmd[10]; int x, y, z;
scanf("%s", cmd);
if(cmd[0] == 'P')
{
readint(x), readint(y), readint(z);
if(x > y)
swap(x, y);
g.update(1, 1, n, x, y, z);
}
else if(cmd[0] == 'Q')
{
readint(x), readint(y);
if(x > y)
swap(x, y);
int tmp = g.query(1, 1, n, x, y);
int ans = 1;
while(tmp)
{
if(tmp & 1 && tmp/2 != 0) writeint(ans), putchar(' ');
else if(tmp & 1) writeint(ans), puts("");
tmp >>= 1;
ans++;
}
}
}
}
return 0;
}
HDU 5204：给定一个迷宫，求最长的一条路径，该路径上任意一点都可以通过最多不超过一次的转弯到达。
HDU 4970 Killing Monsters
比赛时线段树超时，然后用树状数组暴力过了。
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
typedef long long LL;
void readint(LL &x)
{
char c = getchar();
while(!isdigit(c)) c = getchar();
x = 0;
while(isdigit(c))
{
x = x*10+c-'0';
c = getchar();
}
}
void writeint(LL x)
{
if(x > 9) writeint(x/10);
putchar(x%10+'0');
}
/////////////////////////////////
const LL maxn = 100000 + 10;
LL n, m;
LL C[maxn];
LL lowbit(LL x)
{
return x & -x;
}
void add(LL x, LL d)
{
while(x > 0)
{
C[x] += d; x -= lowbit(x);
}
}
LL sum(LL x)
{
LL ans = 0;
while(x <= n)
{
ans += C[x]; x += lowbit(x);
}
return ans;
}
LL f[maxn];
int main()
{
for(;;)
{
readint(n);
if(!n) break;
for(int i = 0; i <= n; i++)
C[i] = f[i] = 0;
readint(m);
for(int i = 1; i <= m; i++)
{
LL x, y, z; readint(x), readint(y), readint(z);
add(y, z), add(x-1, -z);
}
f[n] = sum(n);
for(int i = n-1; i >= 1; i--)
{
f[i] = sum(i)+f[i+1];
}
LL k; readint(k);
LL ans = 0;
for(int i = 1; i <= k; i++)
{
LL h, x; readint(h), readint(x);
if(h > f[x]) ans++;
}
writeint(ans), puts("");
}
return 0;
}
HDU 4950 Monster & HDU 4952 Number Transformation
多校第八场，做比赛还是不够稳呐！(=@__@=)！
4950：给定一个怪物，初始HP为h，战士攻击力为a，每次回合结束后怪物能回复b的血量，如果怪物的血量<1时，判负。战士经过K轮战斗必须休息一轮，问是否能杀死怪物。
贪心即可，首先判断一次杀死的情况，在判断a<=b，永远杀不死的情况，然后再在a>b的情况里分类判断，注意int越界。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <cmath>
#include <stack>
using namespace std;
typedef long long LL;
LL h, a, b, k;
int main()
{
int kase = 0;
while(~scanf("%I64d%I64d%I64d%I64d", &h, &a, &b, &k))
{
if(h == 0 && a == 0 && b == 0 && k == 0) break;
printf("Case #%d: ", ++kase);
if(a >= h)
{
printf("YES\n");
continue ;
}
if(a <= b) printf("NO\n");
else
{
LL T = h-a*k+b*(k-1);
if(T <= 0) printf("YES\n");
else
{
LL M = h-a*k+b*(k+1);
if(M >= h) printf("NO\n");
else printf("YES\n");
}
}
}
return 0;
}
4952：打表找规律，我找到的规律大约是在sqrt(n)左右后面的项与前面的项是等差数列，而且差值=等差数列的首项x/i（i-th operation），时间复杂度大约在O(sqrt(n))，对10^10次方左右的数据足够了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <cmath>
#include <stack>
using namespace std;
typedef long long LL;
LL work(LL x, LL i)
{
if(x%i == 0) return x;
LL q = x/i*i+i;
return q;
}
LL n, k;
int main()
{
int kase = 0;
while(~scanf("%I64d%I64d", &n, &k) && (n+k))
{
LL x, y;
x = n;
LL i, a;
LL b;
for(i = 2; i <= k; i++)
{
y = x;
x = work(x, i);
a = x-y;
b = x/i;
if(x%i == 0 && a == b) break;
}
if(i <= k) x += (k-i)*b;
printf("Case #%d: %I64d\n", ++kase, x);
}
return 0;
}
HDU 4961 Magical Forest
大意：虚拟出一个2*10^9 * 2*10^9的数组内存空间，现在这个内存空间初始化为0，并且对其中的某些元素进行赋初值。后接着一系列的操作使得这个数组的行和列得以交换，中间还对某一行或者是某一列元素的值进行询问。
前段时间写过一个类似的题，二哥的内存。没想到在多校遇到了这道题，只不过数据范围改一下，但是有一个限制条件，即交换的两行（列）必须都有水果或者都没水果，注意这一点，用map映射一下值就可以了。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <map>
using namespace std;
map<long long int, int> mp;
map<int, int> r, c;
int n, m, k;
void swap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
int main()
{
int T, kase = 0;
for(scanf("%d", &T); T > 0; T--)
{
scanf("%d%d%d", &n, &m, &k);
mp.clear();
r.clear();
c.clear();
for(int i = 0; i < k; i++)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
mp[1LL*x*2000000005+y] = z;
r[x] = x, c[y] = y;
}
int q; scanf("%d", &q);
printf("Case #%d:\n", ++kase);
while(q--)
{
int cmd, x, y;
scanf("%d%d%d", &cmd, &x, &y);
if(cmd == 1)
{
if(r.count(x) && r.count(y))
{
swap(r[x], r[y]);
}
if(!r.count(x) && !r.count(y))
{
r[x] = x, r[y] = y;
swap(r[x], r[y]);
}
}
else if(cmd == 2)
{
if(c.count(x) && c.count(y))
{
swap(c[x], c[y]);
}
if((!c.count(x) && !c.count(y)))
{
c[x] = x, c[y] = y;
swap(c[x], c[y]);
}
}
else
{
if(mp[1LL*r[x]*2000000005+c[y]] != 0)
{
printf("%d\n", mp[1LL*r[x]*2000000005+c[y]]);
}
else printf("0\n");
}
}
}
return 0;
}
HDU 4930 Fighting the Landlords
给定斗地主的规则以及两幅手牌，然后判断是否在这一轮内你不会输给对手或者出完了全部手牌。
在比赛中我判断所有的情况，这样比较麻烦。其实可以把Bomb、Tri、Pair拆开分别去判断，有很多细节需要注意。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
int x[20], y[20];
int Win(int n)
{
if(n == 4 || n == 6) //炸弹带
{
for(int i = 17; i >= 3; i--)
{
if(x[i] == 4) return 1;
}
}
if(n == 5) //3带2
{
int Tri = 0, Dou = 0;
for(int i = 17; i >= 3; i--)
{
if(x[i] == 3) Tri = 1;
if(x[i] == 2) Dou = 1;
}
if(Tri && Dou) return 1;
}
if(n == 4) //3带1
{
for(int i = 17; i >= 3; i--)
{
if(x[i] == 3) return 1;
}
}
if(n == 3) //三个
{
for(int i = 17; i >= 3; i--)
{
if(x[i] == 3) return 1;
}
}
if(n == 2) //Double
{
for(int i = 17; i >= 3; i--)
{
if(x[i] == 2) return 1;
}
}
if(n == 1) return 1; //一个
return 0;
}
int main()
{
int T;
for(scanf("%d", &T); T > 0; T--)
{
char s[20];
scanf("%s", s);
memset(x, 0, sizeof(x));
memset(y, 0, sizeof(y));
for(int i = 0; s[i]; i++)
{
int t;
if(s[i] == 'T') t = 10;
else if(s[i] == 'J') t = 11;
else if(s[i] == 'Q') t = 12;
else if(s[i] == 'K') t = 13;
else if(s[i] == 'A') t = 14;
else if(s[i] == '2') t = 15;
else if(s[i] == 'X') t = 16;
else if(s[i] == 'Y') t = 17;
else t = s[i]-'0';
x[t]++;
}
int len = strlen(s);
scanf("%s", s);
for(int i = 0; s[i]; i++)
{
int t;
if(s[i] == 'T') t = 10;
else if(s[i] == 'J') t = 11;
else if(s[i] == 'Q') t = 12;
else if(s[i] == 'K') t = 13;
else if(s[i] == 'A') t = 14;
else if(s[i] == '2') t = 15;
else if(s[i] == 'X') t = 16;
else if(s[i] == 'Y') t = 17;
else t = s[i]-'0';
y[t]++;
}
if(x[16] == 1 && x[17] == 1) //有大小王
{
printf("Yes\n");
continue;
}
if(Win(len)) { printf("Yes\n"); continue ; } //出完的情况
if(y[16] == 1 && y[17] == 1) //有大小王
{
printf("No\n");
continue;
}
int bomb = -1, p;
for(int i = 17; i >= 3; i--) //炸弹
{
if(x[i] == 4)
{
bomb = 1;
p = i;
break;
}
}
int win = 1;
if(bomb == 1)
{
for(int i = 17; i > p; i--)
{
if(y[i] == 4)
{
win = 0; break;
}
}
}
if(bomb == 1 && win) { printf("Yes\n"); continue; } //有炸弹且最大
else if(!win) { printf("No\n"); continue ;} //有炸弹，但输了。
for(int i = 3; i <= 17; i++) if(y[i] == 4) { bomb = 2; break; }
if(bomb == 2) { printf("No\n"); continue ; } //对手有炸弹，我没有。
win = 1;
int Tri = -1;
for(int i = 17; i >= 3; i--) //三个
{
if(x[i] == 3)
{
Tri = 1;
p = i;
break;
}
}
if(Tri == 1)
{
for(int i = 17; i > p; i--)
{
if(y[i] == 3)
{
Tri = 0;
break;
}
}
}
if(Tri == 1) { printf("Yes\n"); continue ;}
else if(Tri == 0) win = 0;
int Dou = -1;
for(int i = 17; i >= 3; i--) //两个
{
if(x[i] == 2)
{
Dou = 1;
p = i;
break;
}
}
if(Dou == 1)
{
for(int i = 17; i > p; i--)
{
if(y[i] == 2 || y[i] == 3)
{
Dou = 0;
break;
}
}
}
if(Dou == 1) { printf("Yes\n"); continue ; }
else if(Dou == 0) win = 0;
int solo = -1;
for(int i = 17; i >= 3; i--) //一个
{
if(x[i] == 1)
{
solo = 1;
p = i;
break;
}
}
if(solo == 1)
{
if(win == 0) win = 1;
for(int i = 17; i > p; i--)
{
if(y[i] == 1 || y[i] == 2 || y[i] == 3) { win = 0; break; }
}
}
if(win == 1) printf("Yes\n");
else if(win == 0) printf("No\n");
}
return 0;
}
HDU 4861 Couple doubi
前天刚到学校，很久没刷题，需要一段时间寻找状态。
这是22号的多校，我没赶上，现在重新写一下来帮助自己找回状态。
由于p一定是素数，打表可知循环节为p-1，并且只有p-1号球有价值。一开始题意理解错，以为必须从第一号球开始轮流拿，其实是任意顺序拿的。这样，求出总共可以拿到几次有价值的球k，如果k为奇数则代表doubiNan可以多拿一次，输出"YES"，如果为偶数，那么他们拿的次数相等，输出"NO"。
#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
int k, p;
int main()
{
while(~scanf("%d%d", &k, &p))
{
int n = k/(p-1);
if(n & 1) printf("YES\n");
else printf("NO\n");
}
return 0;
}
用自定义类模板实现的二叉堆
最近在复习数据结构，从各种数据结构的发明不得感叹人类真的很聪明，创造了各种方式来组织数据，使得人们可以快速的获得某一想要的数据。
二叉堆具有的堆序性质就是如此。
#include <iostream>
#include <stack>
#include <cmath>
#include <vector>
using namespace std;
#define readint(T) scanf("%d", &T)
const int INF = 0x3f3f3f3f;
template<typename Comparable>
class BHeap
{
private:
int currentSize;
vector<Comparable> array;
void buildHeap();
void percolateDown(int hole);
public:
explicit BHeap(int capacity = 100);
explicit BHeap(const vector<Comparable> &items);
bool isEmpty() const;
Comparable findMin() const;
void decreaseKey(int p, Comparable delta);
void increaseKey(int p, Comparable delta);
void insert(const Comparable &x);
Comparable deleteMin();
void makeEmpty();
void print();
};
template<typename Comparable>
void BHeap<Comparable>::insert(const Comparable &x)
{
if(currentSize == array.size() -1)
array.resize(array.size()*2);
int hole = ++currentSize;
for(; hole > 1 && x < array[hole/2]; hole /=2)
array[hole] = array[hole/2];
array[hole] = x;
}
template<typename Comparable>
Comparable BHeap<Comparable>::deleteMin()
{
Comparable ERROR = -1;
if(isEmpty())
{
printf("already Empty\n");
return ERROR;
}
Comparable minItem = array[1];
array[1] = array[currentSize--];
percolateDown(1);
return minItem;
}
template<typename Comparable>
void BHeap<Comparable>::percolateDown(int hole)
{
int child;
Comparable tmp = array[hole];
for(; hole*2 <= currentSize; hole = child)
{
child = hole*2;
if(child != currentSize && array[child+1] < array[child])
child++;
if(array[child] < tmp)
array[hole] = array[child];
else break;
}
array[hole] = tmp;
}
template<typename Comparable>
void BHeap<Comparable>::decreaseKey(int p, Comparable delta)
{
Comparable tmp = array[p]-delta;
if(tmp > array[p])
printf("The new Key is larger than current Key!!!\n");
else
{
array[p] = tmp;
int hole;
for(hole = p; hole > 1 && array[tmp] < array[hole/2]; hole /= 2)
array[hole] = array[hole/2];
array[hole] = tmp;
}
}
template<typename Comparable>
void BHeap<Comparable>::increaseKey(int p, Comparable delta)
{
Comparable tmp = array[p]+delta;
if(tmp < array[p])
printf("The new Key is smaller than current Key!!!\n");
else
{
array[p] = tmp;
percolateDown(p);
}
}
template<typename Comparable>
BHeap<Comparable>::BHeap(const vector<Comparable> &items):array(items.size()+10), currentSize(items.size())
{
for(int i = 0; i < items.size(); i++)
array[i+1] = items[i];
buildHeap();
}
template<typename Comparable>
void BHeap<Comparable>::buildHeap() //建堆只考虑有子节点的节点
{
for(int i = currentSize/2; i > 0; i--)
percolateDown(i);
}
template<typename Comparable>
bool BHeap<Comparable>::isEmpty() const
{
if(currentSize == 0) return 1;
return 0;
}
template<typename Comparable>
void BHeap<Comparable>::makeEmpty()
{
currentSize = 0;
}
template<typename Comparable>
Comparable BHeap<Comparable>::findMin() const
{
Comparable minItem = array[1];
return minItem;
}
template<typename Comparable>
void BHeap<Comparable>::print()
{
for(int i = 1; i <= currentSize; i++) printf(i != currentSize?"%d ":"%d\n", array[i]);
}
int main()
{
////////////////////////////test
vector<int> ar;
int minItem, x;
for(int i = 0; i < 10; i++)
{
readint(x);
ar.push_back(x);
}
BHeap<int> Heap(ar);
printf("findMin: %d\n", Heap.findMin());
Heap.print();
printf("Please input a digit:\n");
readint(x);
printf("after insert a digit\n");
Heap.insert(x);
Heap.print();
printf("position 1 increase 10 and percolateDown\n");
Heap.increaseKey(1, 10);
Heap.print();
printf("position 1 decrease 15 and percolateUp\n");
Heap.decreaseKey(1, 15);
Heap.print();
printf("deleteMin:\n");
Heap.deleteMin();
Heap.print();
system("pause");
}
POJ 2949 Word Rings
题意：给你一些单词，如果一个单词的后两个字母和另外一个单词的前两个字母一样，那么这两个单词就可以连在一起，然后让你求单词成环之后，最大的平均权值。
解法：求平均权值最大的环路？ 记得一本书上说过，假如所有的边都在环中，其实就是:E1+E2+E3+E4+....+En = mid*n;转换一下即为：E1-mid+E2-mid+...En-mid = 0;这是权值相等的时候。 要使得mid最大，那么我们可以把E1-mid做为原先图的边。如果有正环存在，说明权值可以继续增大。 二分枚举mid即可。
要用stack来进行入队、出队操作才可以过，要不是会TLE。原因在一篇论文集上有所说明，我认为只需掌握怎么写就行了。
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
using namespace std;
int k, n, m;
const int maxn = 2010;
const int maxm = 1010*1010*2;
const int INF = 0x3f3f3f3f;
double d[maxn];
struct Edge
{
int u, v;
double w;
int next;
}edge[maxm];
int cnt;
int first[maxn];
void read_graph(int u, int v, double w)
{
edge[cnt].v = v, edge[cnt].w = w;
edge[cnt].next = first[u], first[u] = cnt++;
}
bool inq[maxn];
double L, R;
int spfa(double mid)
{
stack<int> Q;
for(int i = 1; i <= k; i++)
{
d[i] = 0;
Q.push(i);
inq[i] = 1;
}
int CNT[maxn] = {0};
while(!Q.empty())
{
int x = Q.top(); Q.pop();
inq[x] = 0;
for(int e = first[x]; e != -1; e = edge[e].next)
{
int v = edge[e].v;
double w = edge[e].w;
if(d[v] < d[x]+w)
{
d[v] = d[x]+w;
if(!inq[v])
{
inq[v] = 1;
if(++CNT[v] > k) return 1;
Q.push(v);
}
}
}
}
return 0;
}
void init()
{
cnt = 0;
memset(first, -1, sizeof(first));
}
int ord(char x, char y)
{
return (x-'a')*26+y-'a'+1;
}
int have_cycle(double mid)
{
for(int i = 0; i < m; i++) edge[i].w -= mid;
int flag = 0;
if(spfa(mid)) flag = 1;
for(int i = 0; i < m; i++) edge[i].w += mid;
return flag;
}
const double eps = 1e-2;
char word[1010];
int vis[3010];
int main()
{
while(scanf("%d", &m))
{
if(!m) break;
init();
memset(vis, 0, sizeof(vis));
L = 0, R = 0;
k = 0;
for(int i = 0; i < m; i++)
{
scanf("%s", word);
int len = strlen(word);
int a = ord(word[0], word[1]);
int b = ord(word[len-2], word[len-1]);
if(!vis[a]) vis[a] = ++k;
if(!vis[b]) vis[b] = ++k;
R = max(R, len*1.0);
read_graph(vis[a], vis[b], len*1.0);
}
double ans = -1;
while(R-L >= eps)
{
double mid = L+(R-L)/2.0;
if(have_cycle(mid))
{
ans = mid;
L = mid;
}
else R = mid;
}
if(ans == -1) printf("No solution.\n");
else printf("%.2f\n", ans);
}
return 0;
}
POJ 3414 Pots
好久没发关于ACM的文章了，以前的博客几个月没用了。今天随便水了一题，顺便发第一篇在这博客上的ACM的文章。
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
//fill 1 0
//drop 1 1
//fill 2 2
//drop 2 3
//pour(1, 2) 4
//pour(2, 1) 5
struct node
{
int v[2];
string step;
int ans;
};
int A, B, C;
bool vis[110][110];
node bfs()
{
memset(vis, 0, sizeof(vis));
node cur, next;
cur.v[0] = 0, cur.v[1] = 0, cur.step = "", cur.ans = 0;
vis[0][0] = 1;
queue<node> Q;
Q.push(cur);
while(!Q.empty())
{
cur = Q.front(); Q.pop();
int a = cur.v[0], b = cur.v[1];
if(a == C || b == C) return cur;
if(a != A && !vis[A][b]) //fill 1
{
next = cur;
next.v[0] = A;
vis[A][b] = 1;
next.step += '0', next.ans++;
Q.push(next);
}
if(a > 0 && !vis[0][b]) //drop 1
{
next = cur;
next.v[0] = 0;
vis[0][b] = 1;
next.step += '1', next.ans++;
Q.push(next);
}
if(b != B && !vis[a][B]) //fill 2
{
next = cur;
next.v[1] = B;
vis[a][B] = 1;
next.step += '2', next.ans++;
Q.push(next);
}
if(b > 0 && !vis[a][0]) //drop 2
{
next = cur;
next.v[1] = 0;
vis[a][0] = 1;
next.step += '3', next.ans++;
Q.push(next);
}
if(b != B && a+b < B && !vis[0][a+b]) //pour(1, 2)
{
next = cur;
next.v[0] = 0, next.v[1] = a+b;
vis[0][a+b] = 1;
next.step += '4', next.ans++;
Q.push(next);
}
if(b != B && a+b > B && !vis[a-B+b][B])
{
next = cur;
next.v[0] = a-B+b, next.v[1] = B;
vis[a-B+b][B] = 1;
next.step += '4', next.ans++;
Q.push(next);
}
if(a != A && a+b < A && !vis[a+b][0]) //pour(2, 1)
{
next = cur;
next.v[0] = a+b, next.v[1] = 0;
vis[a+b][0] = 1;
next.step += '5', next.ans++;
Q.push(next);
}
if(a != A && a+b > A && !vis[A][b-A+a])
{
next = cur;
next.v[0] = A, next.v[1] = b-A+a;
vis[A][b-A+a] = 1;
next.step += '5', next.ans++;
Q.push(next);
}
}
node b;
b.ans = -1;
return b;
}
void print(node a)
{
int n = a.step.length();
printf("%d\n", a.ans);
for(int i = 0; i < n; i++)
{
char c = a.step[i];
switch(c)
{
case '0': printf("FILL(1)\n"); break;
case '1': printf("DROP(1)\n"); break;
case '2': printf("FILL(2)\n"); break;
case '3': printf("DROP(2)\n"); break;
case '4': printf("POUR(1,2)\n"); break;
case '5': printf("POUR(2,1)\n"); break;
default: break;
}
}
}
int main()
{
while(~scanf("%d%d%d", &A, &B, &C))
{
node ans = bfs();
if(ans.ans == -1) { printf("impossible\n"); continue ; }
print(ans);
}
return 0;
}