题意 你有两个容积分别为a,b杯子 你每次可以将某个杯子中的水倒满或者倒掉或者倒到另一个杯子 问能否通过这两个杯子量出c容量的水

和上一个倒可乐问题类似 只是这个操作更多了点 将两个杯子中各含有的水作为状态 每出队列一个状态 将所有可能到达的状态入队 直到有一个杯子里面水的体积为c 打印路径直接递归就行了

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#include <map>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 105;
int a, b, c, t, le, ri, v[N][N];
int x[N * N], p[N * N], op[N * N], d[N * N];
pair<int, int> q[N * N];

void check(int i, int j, int o, int k)
{
    if(v[i][j]) return;
    v[i][j] = 1, p[ri] = le;
    op[ri] = o, x[ri] = k, d[ri] = d[le] + 1;
    q[ri++] = make_pair(i, j);
}

int bfs()
{
    int ca, cb = le = ri = 0;
    q[ri++] = make_pair(0, 0);
    memset(v, 0, sizeof(v)), v[0][0] = 1;

    while(le < ri)
    {
        ca = q[le].first, cb = q[le].second;
        if(ca == c || cb == c) return le;
        check(a, cb, 1, 1);                 //FILL(1);
        check(ca, b, 1, 2);                 //FILL(2);
        check(0, cb, 2, 1);                 //DROP(1);
        check(ca, 0, 2, 2);                 //DROP(2);
        if(ca > b - cb) check(ca - b + cb, b, 3, 1);
        else check(0, ca + cb, 3, 1);       //POUR(1,2);
        if(cb > a - ca) check(a, cb - a + ca, 3, 2);
        else check(ca + cb, 0, 3, 2);       //POUR(2,1);
        ++le;
    }
    return 0;
}

void print(int k)
{
    if(p[k] > 0) print(p[k]);
    if(op[k] == 1) printf("FILL(%d)\n", x[k]);
    if(op[k] == 2) printf("DROP(%d)\n", x[k]);
    if(op[k] == 3) printf("POUR(%d,%d)\n", x[k], 3 - x[k]);
}

int main()
{
    int ans;
    while(~scanf("%d%d%d", &a, &b, &c))
    {
        if(ans = bfs())
            printf("%d\n",d[ans]), print(ans);
        else puts("impossible");
    }
    return 0;
}

Pots

Description
You are given two pots, having the volume of A and B liters respectively. The following operations can be performed:

Write a program to find the shortest possible sequence of these operations that will yield exactly C liters of water in one of the pots.

Input

On the first and only line are the numbers A, B, and C. These are all integers in the range from 1 to 100 and C≤max(A,B).

Output

The first line of the output must contain the length of the sequence of operations K. The following K lines must each describe one operation. If there are several sequences of minimal length, output any one of them. If the desired result can’t be achieved, the first and only line of the file must contain the word ‘impossible’.

Sample Input

3 5 4

Sample Output

6 FILL(2) POUR(2,1) DROP(1) POUR(2,1) FILL(2) POUR(2,1)

题意 给你两个4位素数a, b 你每次可以改变a的一位数但要求改变后仍为素数 求a至少改变多少次才能变成b

基础的bfs 注意数的处理就行了 出队一个数 然后入队所有可以由这个素数经过一次改变而来的素数 知道得到b

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 10000;
int p[N], v[N], d[N], q[N], a, b;

void initPrime()
{
    memset(v, 0 , sizeof(v));
    for(int i = 2; i * i < N; ++i)
        if(!v[i]) for(int j = i; i * j < N; ++j)  v[i * j] = 1;
    for(int i = 2; i < N ; ++i) p[i] = !v[i];
}

int bfs()
{
    int c, t, le = 0, ri = 0;
    memset(v, 0, sizeof(v));
    q[ri++] = a, v[a] = 1, d[a] = 0;
    while(le < ri)
    {
        c = q[le++];
        if( c == b) return d[c];
        for(int i = 1; i < N; i *= 10)
        {
            for(int j = 0; j < 10; ++j)   //把c第i数量级的数改为j
            {
                if(i == 1000 && j == 0) continue;
                t = c / (i * 10) * i * 10 + i * j + c % i;
                if(p[t] && !v[t])
                    v[t] = 1, d[t] = d[c] + 1, q[ri++] = t;
            }
        }
    }
    return -1;
}

int main()
{
    int cas;
    scanf("%d", &cas);
    initPrime();
    while(cas--)
    {
        scanf("%d%d", &a, &b);
        if((a = bfs()) != -1) printf("%d\n", a);
        else puts("Impossible");
    }
    return 0;
}

Prime Path

Description
The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.
— It is a matter of security to change such things every now and then, to keep the enemy in the dark.
— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know!
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door.
— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime!
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds.
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.
Now, the minister of finance, who had been eavesdropping, intervened.
— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound.
— Hmm, in that case I need a computer program to minimize the cost. You don’t know some very cheap software gurus, do you?
— In fact, I do. You see, there is this programming contest going on… Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above.
1033
1733
3733
3739
3779
8779
8179 The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.

Input

One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros).

Output

One line for each case, either with a number stating the minimal cost or containing the word Impossible.

Sample Input

3 1033 8179 1373 8017 1033 1033

Sample Output

6 7 0

题意 给你一个数n 输出一个仅由0，1组成的数m使得m是n的倍数

找到一个m 是m%n==0 就行了 初始让m=1 然后bfs扩展m的位数 只有两种情况m = m /* 10 或 m = m/*10 + 1;

同余模定理**(a+b) % c = (a%c + b%c) % c, (a/b)%c = (a%c / b%c) % c;**

运用同余模定理 可以只记录余数 这样就可以避免处理大数了 因为余数不会超过n 而n是小于两百的

对于已经得到过的余数 是可以跳过的 可以考虑下为什么

于是只用保存每一位选的是0还是1 只要保证最后余数为0就行了

*1. 选0 m = m/10 % n;

*2. 选1 m = (m/10 + 1) % n;

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
32
33
34
35
36
37
38
39

#include <cstdio>
using namespace std;
const int N = 205;
int q[N], p[N], d[N], n;

int bfs()
{
    int le = 0, ri = 0, r = 1, cr;
    int v[N] = {0};
    v[q[ri++] = r % n] = d[0] = 1;
    p[0] = -1;
    while(le < ri)
    {
        cr = q[le];
        if(cr == 0)  return le;
        if(!v[r = cr * 10 % n])
            v[r] = 1, p[ri] = le, d[ri] = 0, q[ri++] = r;
        if(!v[r = (cr * 10 + 1) % n])
            v[r] = 1, p[ri] = le, d[ri] = 1, q[ri++] = r;
        ++le;
    }
    return -1;
}

void print(int k)
{
    if(p[k] >= 0) print(p[k]);
    printf("%d", d[k]);
}

int main()
{
    while(scanf("%d", &n), n)
    {
        print(bfs());
        puts("");
    }
    return 0;
}

Find The Multiple

Description
Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.

Input

The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.

Output

For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.

Sample Input

2 6 19 0

Sample Output

10 100100100100100100 111111111111111111

题意 将体积为s的可乐 利用容积分别为n和m的两个杯子平均分为两份 至少需要倒多少次可乐

可以把容器s,n,m中装的可乐量看成一种状态

容器都是没有刻度的 所以每次倒可乐要么把自己倒完 要么把对方倒满

每种状态可以通过一次倒水到达哪些状态 于是可以通过bfs判断到达每种状态需要倒多少次

3个容器中有一个装的可乐为s/2的状态就是答案了 s是奇数时明显不可能平分的 可以直接忽略

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 105;
int v[N][N][N], n, m, s, le, ri;

struct state {
    int a, b, c, d;
    state() {}
    state(int e, int f, int g, int h)
        : a(e), b(f), c(g), d(h) {}
} q[N * N * N];

void pour(int a, int b, int c, int d)
{
    if(!v[a][b][c])
    {
        v[a][b][c] = 1;
        q[ri++] = state(a, b, c, d + 1);
    }
}

int bfs()
{
    int a, b, c, d;
    le = ri = 0;
    q[ri++] = state(s, 0, 0, 0);
    memset(v, 0, sizeof(v));
    v[s][0][0] = 1;
    while(le < ri)
    {
        a = q[le].a, b = q[le].b, c = q[le].c, d = q[le++].d;
        if(a == s / 2 || b == s / 2 || c == s / 2)
            return d + (a && b && c != 0);
        pour(a - n + b, n, c, d);		    //s->n:
        pour(a - m + c, b, m, d);		    //s->m;
        pour(a + b, 0, c, d);			    //n->s;
        pour(a + c, b, 0, d);                       //m->s;
        if(b > m - c) pour(a, b - m + c, m, d);     //n->m
        else pour(a, 0, b + c, d);
        if(c > n - b) pour(a, n, c - n + b, d);     //m->n
        else pour(a, b + c, 0, d);
    }
    return 0;
}

int main()
{
    int ans;
    while(scanf("%d%d%d", &s, &n, &m), n)
    {
        ans = 0;
        if (s % 2 == 0) ans = bfs();
        if(!ans) puts("NO");
        else printf("%d\n", ans);
    }
    return 0;
}

非常可乐

Problem Description

大家一定觉的运动以后喝可乐是一件很惬意的事情，但是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

NO 3

题意 在n/*m的地图中 ‘Y’和’M’两个人到某一家KFC(在地图上用”@’表示) 所需的最小时间和是多少 他们每走一步都要11分钟

可以分别以y和m为起点进行一遍bfs 把到每个KFC的时间都存起来 最后看哪家KFC的时间和最小就行了

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <map>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 205;
int x[] = {0, 0, -1, 1};
int y[] = { -1, 1, 0, 0};
pair<int, int> q[N * N];
int dy[N][N], dm[N][N], ans, n, m;
char g[N][N];

void bfs(int r, int c, char k)
{
    int (&d)[N][N] = (k == 'Y' ? dy : dm); //d为指向dy或dm的引用
    int v[N][N] = {0}, le = 0, ri = 0, cr, cc;
    q[ri++] = make_pair(r, c), v[r][c] = 1, d[r][c] = 0;

    while(le < ri)
    {
        r = q[le].first, c = q[le++].second;
        for(int i = 0; i < 4; ++i)
        {
            cr = r + x[i], cc = c + y[i];
            if(cr >= 0 && cr < n && cc >= 0 && cc < m
                    && v[cr][cc] == 0 && g[cr][cc] != '#')
                q[ri++] = make_pair(cr, cc), d[cr][cc] = d[r][c] + 1, v[cr][cc] = 1;
        }
    }
}

int main()
{
    while(~scanf("%d%d", &n , &m))
    {
        ans = N * N;
        for(int i = 0; i < n; ++i)
            scanf("%s", g[i]);
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                if(g[i][j] == 'Y' || g[i][j] == 'M')  bfs(i, j, g[i][j]);

        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                if(g[i][j] == '@') ans = min(ans, dy[i][j] + dm[i][j]);

        printf("%d\n", ans * 11);
    }
    return 0;
}

Find a way

Problem Description

Pass a year learning in Hangzhou, yifenfei arrival hometown Ningbo at finally. Leave Ningbo one year, yifenfei have many people to meet. Especially a good friend Merceki.
Yifenfei’s home is at the countryside, but Merceki’s home is in the center of city. So yifenfei made arrangements with Merceki to meet at a KFC. There are many KFC in Ningbo, they want to choose one that let the total time to it be most smallest.
Now give you a Ningbo map, Both yifenfei and Merceki can move up, down ,left, right to the adjacent road by cost 11 minutes.
Input

The input contains multiple test cases.
Each test case include, first two integers n, m. (2<=n,m<=200).
Next n lines, each line included m character.
‘Y’ express yifenfei initial position.
‘M’ express Merceki initial position.
‘/#’ forbid road;
‘.’ Road.
‘@’ KCF
Output

For each test case output the minimum total time that both yifenfei and Merceki to arrival one of KFC.You may sure there is always have a KFC that can let them meet.
Sample Input

4 4 Y./#@ …. ./#.. @..M 4 4 Y./#@ …. ./#.. @/#.M 5 5 Y..@. ./#… ./#… @..M. /#…/#
Sample Output

66 88 66

题意 把一个n/*m矩阵中的1全部变成0所需的最少步数 改变某个格子时其相邻的4个格子也一起改变

只要知道第一行改变了哪些后面的就都确定了 因为上一行对应位置是1的位置必须改变 上一行是0的一定不能改变

所以可以根据第一行的状态推出后面所有行的状态 直到最后一行结束 如果最后一行不是全0的话 这种状态就是不可行的

那么我们只用枚举第一行的所有状态就够了 m<=16 用二进制可以比较方便的枚举 对应位是1就表示改变状态 0就不改变 最后打印改变状态次数最少的可行结果就行了

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 16;
int g[N][N], t[N][N], f[N][N];
int cnt, n, m;
int x[4] = {0, 0, -1, 1};
int y[4] = { -1, 1, 0, 0};

void flip(int i, int j)
{
    ++cnt, f[i][j] = 1;
    t[i][j] = !t[i][j];
    for(int k = 0; k < 4; ++k)
        if(i + x[k] > -1 && j + y[k] > -1)
            t[i + x[k]][j + y[k]] ^= 1;
}

bool ok(int k)
{
    cnt = 0;
    memcpy(t, g, sizeof(t));
    for(int j = 0; j < m; ++j)
        if(k & (1 << (m - 1 - j))) flip(0, j);

    for(int i = 1; i < n; ++i)
        for(int j = 0; j < m; ++j)
            if(t[i - 1][j]) flip(i, j);

    for(int j = 0; j < m; ++j)
        if(t[n - 1][j]) return false;
    return true;
}

int main()
{
    int ans, p;
    while(~scanf("%d%d", &n, &m))
    {
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < m; ++j)
                scanf("%d", &g[i][j]);
        ans = n * m + 1, p = -1;
        for(int i = 0; i < (1 << m); ++i)
            if(ok(i) && cnt < ans) ans = cnt, p = i;

        memset(f, 0, sizeof(f));
        if(p >= 0)
        {
            ok(p);
            for(int i = 0; i < n; ++i)
                for(int j = 0; j < m; ++j)
                    printf("%d%c", f[i][j], j < m - 1 ? ' ' : '\n');
        }
        else puts("IMPOSSIBLE");
    }
    return 0;
}

Fliptile

Description
Farmer John knows that an intellectually satisfied cow is a happy cow who will give more milk. He has arranged a brainy activity for cows in which they manipulate an M × N grid (1 ≤ M ≤ 15; 1 ≤ N ≤ 15) of square tiles, each of which is colored black on one side and white on the other side.

As one would guess, when a single white tile is flipped, it changes to black; when a single black tile is flipped, it changes to white. The cows are rewarded when they flip the tiles so that each tile has the white side face up. However, the cows have rather large hooves and when they try to flip a certain tile, they also flip all the adjacent tiles (tiles that share a full edge with the flipped tile). Since the flips are tiring, the cows want to minimize the number of flips they have to make.

Help the cows determine the minimum number of flips required, and the locations to flip to achieve that minimum. If there are multiple ways to achieve the task with the minimum amount of flips, return the one with the least lexicographical ordering in the output when considered as a string. If the task is impossible, print one line with the word “IMPOSSIBLE”.

Input

Line 1: Two space-separated integers: M and N
Lines 2..M+1: Line i+1 describes the colors (left to right) of row i of the grid with N space-separated integers which are 1 for black and 0 for white

Output

Lines 1..M: Each line contains N space-separated integers, each specifying how many times to flip that particular location.

Sample Input

4 4 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1

Sample Output

0 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0

题意 中文

简单的搜索题 标记列是否已经有子进行深搜即可 k可能小于n 所以每行都有放子或不放子两种选择

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

#include <cstdio>
using namespace std;
const int N = 10;
int n, k, ans, v[N];
char g[N][N];

void dfs(int r, int cnt)
{
    if(cnt >= k) ++ans;
    if(r >= n || cnt >= k) return;
    for(int c = 0; c < n; ++c)   //第r行c列放一个子
        if((!v[c]) && g[r][c] == '#')
            v[c] = 1, dfs(r + 1, cnt + 1), v[c] = 0;
    dfs(r + 1, cnt);   //第r行不放子
}

int main()
{
    while(~scanf("%d%d", &n, &k), n + 1)
    {
        for(int i = 0; i < n; ++i)
            scanf("%s", g[i]);
        dfs(ans = 0, 0);
        printf("%d\n", ans);
    }
    return 0;
}

棋盘问题

Description
在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。

Input

输入含有多组测试数据。
每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n/*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n
当为-1 -1时表示输入结束。
随后的n行描述了棋盘的形状：每行有n个字符，其中 /# 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。

Output

对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）。

Sample Input

2 1 /#. ./# 4 4 …/# ../#. ./#.. /#… -1 -1

Sample Output

2 1

题意 有n个互相连通的长方体水箱 给出每个水箱的位置和长宽高 判断放v体积的水时水面的高度 精确到两位小数

可以把每个水箱的位置 底面积 和高存起来 然用体积v二分高度 就是要注意精度的处理 最好转换成整数运算

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45

import java.util.*;
public class Main {
	static int N = 50005;
	static long[] b = new long[N];
	static long[] h = new long[N];
	static long[] s = new long[N];
	static int n;

	static long getv(long k) {
		long v = 0;
		for (int i = 0; i < n; ++i) {
			if (b[i] + h[i] <= k) v += s[i] * h[i];
			else if (b[i] < k) v += (k - b[i]) * s[i];
		}
		return v;
	}

	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		int cas = in.nextInt();
		while (cas-- > 0) {
			n = in.nextInt();
			long l = 0, r = 0, f = 0, mid = 0, v;
			for (int i = 0; i < n; ++i) {
				b[i] = in.nextLong() * 1000;
				h[i] = in.nextLong() * 1000;
				s[i] = in.nextLong() * in.nextLong();
				f += s[i] * h[i];
				if (b[i] + h[i] > r)  r = b[i] + h[i];
			}
			if ((v = in.nextLong() * 1000) > f)
				System.out.println("OVERFLOW");
			else {
				while (r >= l) {
					mid = (r + l) / 2;
					if (getv(mid) < v) l = mid + 1;
					else r = mid - 1;		
				}
				double ans = l / 1000.0;
				System.out.println(String.format("%.2f", ans));
			}
		}
		in.close();
	}
}

Fill the Cisterns!

Description
During the next century certain regions on earth will experience severe water shortages. The old town of Uqbar has already started to prepare itself for the worst. Recently they created a network of pipes connecting the cisterns that distribute water in each neighbourhood, making it easier to fill them at once from a single source of water. But in case of water shortage the cisterns above a certain level will be empty since the water will to the cisterns below.
You have been asked to write a program to compute the level to which cisterns will be lled with a certain volume of water, given the dimensions and position of each cistern. To simplify we will neglect the volume of water in the pipes.
Task
Write a program which for each data set:
reads the description of cisterns and the volume of water,
computes the level to which the cisterns will be filled with the given amount of water,
writes the result.

Input

The first line of the input contains the number of data sets k, 1 <= k <= 30. The data sets follow.
The first line of each data set contains one integer n, the number of cisterns, 1 <= n <= 50 000. Each of the following n lines consists of 4 nonnegative integers, separated by single spaces: b, h, w, d - the base level of the cistern, its height, width and depth in meters, respectively. The integers satisfy 0 <= b <= 10^6 and 1 <= h /* w /* d <= 40 000. The last line of the data set contains an integer V - the volume of water in cubic meters to be injected into the network. Integer V satisfies 1 <= V <= 2 /* 10^9.

Output

The output should consist of exactly d lines, one line for each data set.
Line i, 1 <= i <= d, should contain the level that the water will reach, in meters, rounded up to two fractional digits, or the word ‘OVERFLOW’, if the volume of water exceeds the total capacity of the cisterns.

Sample Input

3 2 0 1 1 1 2 1 1 1 1 4 11 7 5 1 15 6 2 2 5 8 5 1 19 4 8 1 132 4 11 7 5 1 15 6 2 2 5 8 5 1 19 4 8 1 78

Sample Output

1.00 OVERFLOW 17.00

题意 一块w/*h的玻璃 对其进行n次切割 每次切割都是垂直或者水平的 输出每次切割后最大单块玻璃的面积

用两个set存储每次切割的位置 就可以比较方便的把每次切割产生和消失的长宽存下来 每次切割后剩下的最大长宽的积就是答案了

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
32
33
34
35
36
37
38
39

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
typedef long long LL;
set<int>::iterator i, j;
set<int> ve, ho;  //记录所有边的位置
int wi[N], hi[N];  //记录存在的边长值

void cut(set<int> &s, int *a, int p)
{
    s.insert(p), i = j = s.find(p);
    --i, ++j, --a[*j - *i];  //除掉被分开的长宽
    ++a[p - *i], ++a[*j - p];  //新产生了两个长宽
}

int main()
{
    int w, n, h, p, mw, mh;
    char s[10];
    while(~scanf("%d%d%d", &w, &h, &n))
    {
        memset(wi, 0, sizeof(wi)), memset(hi, 0, sizeof(hi));
        ve.clear(), ho.clear();
        ve.insert(0), ho.insert(0);
        ve.insert(w), ho.insert(h);
        wi[w] = hi[h] = 1;
        mw = w , mh = h;
        while(n--)
        {
            scanf("%s%d", s, &p);
            if(s[0] == 'V') cut(ve, wi, p);
            else cut(ho, hi, p);
            while(!wi[mw]) --mw;
            while(!hi[mh]) --mh;
            printf("%lld\n", LL(mw)*LL(mh));
        }
    }
    return 0;
}

C. Glass Carving

Leonid wants to become a glass carver (the person who creates beautiful artworks by cutting the glass). He already has a rectangular wmm ×  h mm sheet of glass, a diamond glass cutter and lots of enthusiasm. What he lacks is understanding of what to carve and how.

In order not to waste time, he decided to practice the technique of carving. To do this, he makes vertical and horizontal cuts through the entire sheet. This process results in making smaller rectangular fragments of glass. Leonid does not move the newly made glass fragments. In particular, a cut divides each fragment of glass that it goes through into smaller fragments.

After each cut Leonid tries to determine what area the largest of the currently available glass fragments has. Since there appear more and more fragments, this question takes him more and more time and distracts him from the fascinating process.

Leonid offers to divide the labor — he will cut glass, and you will calculate the area of the maximum fragment after each cut. Do you agree?
Input

The first line contains three integers w, h, n (2 ≤ w, h ≤ 200 000, 1 ≤ n ≤ 200 000).

Next n lines contain the descriptions of the cuts. Each description has the form H y or V x. In the first case Leonid makes the horizontal cut at the distance y millimeters (1 ≤ y ≤ h - 1) from the lower edge of the original sheet of glass. In the second case Leonid makes a vertical cut at distance x (1 ≤ x ≤ w - 1) millimeters from the left edge of the original sheet of glass. It is guaranteed that Leonid won’t make two identical cuts.

Output

After each cut print on a single line the area of the maximum available glass fragment in mm2.
Sample test(s)

input 4 3 4 H 2 V 2 V 3 V 1

output 8 4 4 2
input 7 6 5 H 4 V 3 V 5 H 2 V 1

output 28 16 12 6 4

Note

Picture for the first sample test:

Picture for the second sample test:

题意 两个长度为n的只由小写字母组成的字符串a.b 问能否同时交换两个串两个对应位置的字符 使得两个串相同位置字符不相同的数目最小

因为只能交换一次 所以只可能减少0,1或2个 用p[i][j]记录a串字符i对应位置b串字符为j的位置 不存在的为0 那么有

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

#include <bits/stdc++.h>
using namespace std;
const int N = 200005, M = 26;
char a[N], b[N];
int p[M][M];
int main()
{
    int n, d, u, v, flag;
    while(~scanf("%d", &n))
    {
        memset(p, 0, sizeof(p));
        scanf("%s%s", a, b);
        for(int i = d = flag = 0; i < n; ++i)
            if(a[i] != b[i]) ++d, p[a[i] - 'a'][b[i] - 'a'] = i + 1;

        for(int i = 0; i < M; ++i)
            for(int j = 0; j < M; ++j)
                if((u = p[i][j]) && (v = p[j][i])) flag = 2, i = j = M;

        if(!flag) for(int i = 0; i < M; ++i) for(int j = 0; j < M; ++j) for(int k = 0; k < M; ++k)
                      if((u = p[i][j]) && (v = p[j][k])) flag = 1, i = j = k = M;
        if(!flag) u = v = -1;

        printf("%d\n%d %d\n", d - flag, u, v);
    }
    return 0;
}

B. Error Correct System

Ford Prefect got a job as a web developer for a small company that makes towels. His current work task is to create a search engine for the website of the company. During the development process, he needs to write a subroutine for comparing strings S and T of equal length to be “similar”. After a brief search on the Internet, he learned about the Hamming distance between two strings S and T of the same length, which is defined as the number of positions in which S and T have different characters. For example, the Hamming distance between words “permanent” and “pergament” is two, as these words differ in the fourth and sixth letters.

Moreover, as he was searching for information, he also noticed that modern search engines have powerful mechanisms to correct errors in the request to improve the quality of search. Ford doesn’t know much about human beings, so he assumed that the most common mistake in a request is swapping two arbitrary letters of the string (not necessarily adjacent). Now he wants to write a function that determines which two letters should be swapped in string S, so that the Hamming distance between a new string S and string T would be as small as possible, or otherwise, determine that such a replacement cannot reduce the distance between the strings.

Help him do this!
Input

The first line contains integer n (1 ≤ n ≤ 200 000) — the length of strings S and T.

The second line contains string S.

The third line contains string T.

Each of the lines only contains lowercase Latin letters.

Output

In the first line, print number x — the minimum possible Hamming distance between strings S and T if you swap at most one pair of letters in S.

In the second line, either print the indexes i and j (1 ≤ i, j ≤ n, i ≠ j), if reaching the minimum possible distance is possible by swapping letters on positions i and j, or print “-1 -1”, if it is not necessary to swap characters.

If there are multiple possible answers, print any of them.
Sample test(s)

input 9 pergament permanent

output 1 4 6
input 6 wookie cookie

output 1 -1 -1
input 4 petr egor

output 2 1 2
input 6 double bundle

output 2 4 1