Contest2073 Contest2073 - 湖南多校对抗赛(2015.04.06)

Contest2073
Contest2073 - 湖南多校对抗赛(2015.04.06)

Problem A: (More) Multiplication

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 85  Solved: 47
[Submit][Status][Web Board]

Description

Educators are always coming up with new ways to teach math to students. In 2011, an educational software company, All Computer Math (ACM), developed an application to display products in a traditional grade school math format. ACM is now working on an updated version of the software that will display results in a lattice format that some students find to be easier when multiplying larger numbers.

An example would be when multiplying 345 * 56 = 19320 as given below, using a lattice grid with 2 rows and 3 columns, which appears inside a surrounding frame:

Contest2073
Contest2073 - 湖南多校对抗赛(2015.04.06)
The first operand, 345, is displayed above the top of the grid with each digit centered horizontally above its column of the grid, and the second operand, 56, is displayed along the righthand side with each digit centered vertically at the center of its row in the grid. A single cell of the grid, such as
Contest2073
Contest2073 - 湖南多校对抗赛(2015.04.06)
represents the product of the digit of the first operand that is above its column and the digit of the second operand that is to the right of its row. In our example, this cell represents the product 5 times 6 = 30 that results when multiplying the 5 in 345 and the 6 in 56. Note that the 10's digit of that product is placed in the upper left portion of this cell and the 1's digit in the lower right.

The overall product is then computed by summing along the diagonals in the lattice that represent the same place values in the result. For example, in our first problem the product 19320 was computed as:

 
1's digit = 0
10's digit = 5 + 3 + 4 = 12, thus 2 with a carry of 1
100's digit = (1 carry) + 2 + 0 + 2 + 8 = 13, thus 3 with a carry of 1
1000's digit = (1 carry) + 2 + 5 + 1 = 9
10000's digit = 1
The resulting product is placed with the one's digit below the grid at the far right and, depending on its length, with the most significant digits wrapped around the left side of the grid. Each digit of the final product appears perfectly aligned with the corresponding diagonal summands.
To provide an aesthetic view, we use a series of minus (-) characters for horizontal lines, pipe (|) characters for vertical lines, and slash (/) characters for diagonal lines. Furthermore, we use a plus (+) character wherever a horizontal and vertical line meet. Each multiplication lattice is subsequently "boxed" by an outer border. There is a row containing the first operand which is between the topmost border and the top line of the grid, and a row between the bottom of the grid and the bottom border, which contains some portion of the resulting product. There is one column between the leading | and the left edge of the inner grid, which may contain a portion of the resulting product, and one column after the right edge of the inner grid but before the rightmost | border, which contains the second operand. If the product is not long enough to wrap around the bottom-left corner, the column between the left border and the left edge of the grid will containing only spaces. (See the later example of 3 x 3.)

Leading zeros should be displayed within lattice grid cells, but leading zeros should never be displayed in the product, nor should there ever be a slash (/) character prior to the leading digit of the product. For example, consider the product of 12 * 27 = 324 below:

Contest2073
Contest2073 - 湖南多校对抗赛(2015.04.06)
 
Note that in the top-right grid of the lattice, the product 2 * 2 = 04 is displayed with the zero for the tens digit. However, there is no thousands digit displayed in the product 324, nor is there any slash displayed above the digit 3 in that product.

Input

 The input contains one or more tests. Each test contains two positive integers, A and B, such that 1 ≤ A ≤ 9999 and 1 ≤ B ≤ 9999. The last data set will be followed by a line containing 0 0.

Output

 For each data set, produce the grid that illustrates how to multiply the two numbers using the lattice multiplication technique.

Sample Input

345 56
12 27
1 68
9999 7
3 3
0 0

Sample Output

+---------------+
|   3   4   5   |
| +---+---+---+ |
| |1 /|2 /|2 /| |
| | / | / | / |5|
|1|/ 5|/ 0|/ 5| |
| +---+---+---+ |
|/|1 /|2 /|3 /| |
| | / | / | / |6|
|9|/ 8|/ 4|/ 0| |
| +---+---+---+ |
|/ 3 / 2 / 0    |
+---------------+
+-----------+
|   1   2   |
| +---+---+ |
| |0 /|0 /| |
| | / | / |2|
| |/ 2|/ 4| |
| +---+---+ |
| |0 /|1 /| |
| | / | / |7|
|3|/ 7|/ 4| |
| +---+---+ |
|/ 2 / 4    |
+-----------+
+-------+
|   1   |
| +---+ |
| |0 /| |
| | / |6|
| |/ 6| |
| +---+ |
| |0 /| |
| | / |8|
|6|/ 8| |
| +---+ |
|/ 8    |
+-------+
+-------------------+
|   9   9   9   9   |
| +---+---+---+---+ |
| |6 /|6 /|6 /|6 /| |
| | / | / | / | / |7|
|6|/ 3|/ 3|/ 3|/ 3| |
| +---+---+---+---+ |
|/ 9 / 9 / 9 / 3    |
+-------------------+
+-------+
|   3   |
| +---+ |
| |0 /| |
| | / |3|
| |/ 9| |
| +---+ |
|  9    |
+-------+

HINT

 The tables must be formatted precisely as outlined by the rules and examples provided. Mistakes that involve solely errant whitespace will be categorized as Presentation Error; all other errors will be reported as Wrong Answer.

模拟题:格式就行!

转载请注明出处:寻找&星空の孩子

题目链接:http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1561

#include<stdio.h>
const int N =100;

int main()
{
    int A,B,C,a[N],b[N],c[N],lenA,lenB,lenC,flag;
    while(scanf("%d%d",&A,&B)>0)
    {
        if(A==0&&B==0)
            break;
        C=A*B;
        lenA=lenB=lenC=0;
        while(A)
        {
            a[++lenA]=A%10; A/=10;
        }
        while(B)
        {
            b[++lenB]=B%10; B/=10;
        }
        while(C)
        {
            c[++lenC]=C%10; C/=10;
        }
        for(int i=1,j=lenA;i<j;i++,j--)
        {
            A=a[i];a[i]=a[j];a[j]=A;
        }
        flag=lenC;
        printf("+-");
        for(int i=1;i<=lenA;i++)
            printf("----");
        printf("--+
");
        printf("| ");
        for(int i=1;i<=lenA;i++)
            printf("  %d ",a[i]);
        printf("  |
");

        for(int i=lenB;i>0;i--)
        for(int j=1;j<=4;j++)
        {
            printf("|");
            if(j!=2)
            {
                if(j!=4||lenC-lenA<i)
                printf(" ");
                else printf("%d",c[lenC--]);
            }
            else
            {
                if(flag-lenA>i)printf("/");
                else printf(" ");
            }

            if(j==1)
            {
                printf("+");
                for(int e=1;e<=lenA;e++)
                    printf("---+");
                printf(" |
");
            }
            else if(j==2)
            {
                for(int e=1;e<=lenA;e++)
                    printf("|%d /",(a[e]*b[i])/10);
                printf("| |
");
            }
            else if(j==3)
            {
                for(int e=1;e<=lenA;e++)
                    printf("| / ");
                printf("|%d|
",b[i]);
            }
            else
            {
                for(int e=1;e<=lenA;e++)
                    printf("|/ %d",(a[e]*b[i])%10);
                printf("| |
");
            }
        }
        printf("| +");
        for(int e=1;e<=lenA;e++)
            printf("---+");
                printf(" |
");
        printf("|");
        if(flag>lenA)
            printf("/");
        else printf(" ");
        while(lenC)
        {
            printf(" %d ",c[lenC--]);
            if(lenC)
                printf("/");
        }

        printf("   |
");

        printf("+-");
        for(int i=1;i<=lenA;i++)
            printf("----");
        printf("--+
");

    }
}

/**************************************************************
    Problem: 1561
    User: aking2015
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:968 kb
****************************************************************/

Problem B: Fun House

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 169  Solved: 65
[Submit][Status][Web Board]

Description

American Carnival Makers Inc. (ACM) has a long history of designing rides and attractions. One of their more popular attractions is a fun house that includes a room of mirrors. Their trademark is to set up the room so that when looking forward from the entry door, the exit door appears to be directly ahead. However, the room has double-sided mirrors placed throughout at 45 degree angles. So, the exit door can be on any of the walls of the room. The set designer always places the entry and mirrors, but can never seem to be bothered to place the exit door. One of your jobs as part of the construction crew is to determine the placement of the exit door for the room given an original design.

The final diagram for a sample room is given below. The asterisk (*) marks the entry way, lower case x's mark the walls, the mirrors are given by the forward and backward slash characters (/ and ), open spaces with no visual obstructions are marked by periods (.), and the desired placement of the exit is marked with an ampersand (&). In the input diagram, there is an 'x' in place of the '&', since the exit has not yet been located. You need to alter the input diagram by replacing the proper 'x' with an '&' to identify the exit. Note that entrances and exits can appear on any of the walls (although never a corner), and that it is physically impossible for the exit to be the same as the entrance. (You don't need to understand why this is so, although it may be fun to think about.)

Contest2073
Contest2073 - 湖南多校对抗赛(2015.04.06)

Input

Each room will be preceded by two integers, W and L, where 5 ≤ W ≤ 20 is the width of the room including the border walls and 5 ≤ L ≤ 20 is the length of the room including the border walls. Following the specification of W and L are L additional lines containing the room diagram, with each line having W characters from the alphabet: { * , x , . , / , }. The perimeter will always be comprised of walls, except for one asterisk (*) which marks the entrance; the exit is not (yet) marked. A line with two zeros indicates the end of input data.

Output

For each test case, the first line will contain the word, HOUSE, followed by a space and then an integer that identifies the given fun house sequentially. Following that should be a room diagram which includes the proper placement of the exit door, as marked by an ampersand (&).

Sample Input

11 6
xxxxxxxxxxx
x../.....x
x..../....x
*../......x
x.........x
xxxxxxxxxxx
5 5
xxxxx
*...x
x...x
x...x
xxxxx
5 5
xxxxx
x./x
*./.x
x..x
xxxxx
6 6
xxx*xx
x/...x
x....x
x/./.x
x./.x
xxxxxx
10 10
xxxxxxxxxx
x.../...x
x........x
x........x
x.../..x
*.../../x
x........x
x........x
x.../...x
xxxxxxxxxx
0 0

Sample Output

HOUSE 1
xxxxxxxxxxx
x../.....x
x..../....x
*../......x
x.........x
xxxxxx&xxxx
HOUSE 2
xxxxx
*...&
x...x
x...x
xxxxx
HOUSE 3
xxxxx
x./x
*./.x
x..&
xxxxx
HOUSE 4
xxx*xx
x/...x
x....x
x/./.&
x./.x
xxxxxx
HOUSE 5
xxxxxxxxxx
x.../...x
x........x
x........x
&.../..x
*.../../x
x........x
x........x
x.../...x
xxxxxxxxxx

HINT

In both Java and C++ the backslash character () has special meaning as an escape character within character and string literals. You must use the combination \ to express a single backslash within a character or string literal within source code.

DFS;模拟转向;注意下细节即可!

转载请注明出处:寻找&星空の孩子

题目链接:http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1562

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
#define ls 2*i
#define rs 2*i+1
#define up(i,x,y) for(i=x;i<=y;i++)
#define down(i,x,y) for(i=x;i>=y;i--)
#define mem(a,x) memset(a,x,sizeof(a))
#define w(a) while(a)
#define LL __int64
const double pi = acos(-1.0);
#define Len 100005

int n,m,cas = 1,sx,sy;
char str[25][25];

struct point
{
    int x,y;
    point() {}
    point(int _x,int _y):x(_x),y(_y) {}
} ans;

point dfs(int x,int y,int d)
{
    int tx = x,ty = y;
    if(d==1) tx--;
    if(d==2) tx++;
    if(d==3) ty--;
    if(d==4) ty++;
    if(d==1)
    {
        w(1)
        {
            if(str[tx][ty]=='/') return dfs(tx,ty,4);
            if(str[tx][ty]=='\') return dfs(tx,ty,3);
            if(tx==1 || str[tx][ty]=='x') return point(tx,ty);
            tx--;
        }
    }
    if(d==2)
    {
        while(1)
        {
            if(str[tx][ty]=='/') return dfs(tx,ty,3);
            if(str[tx][ty]=='\') return dfs(tx,ty,4);
            if(tx==n || str[tx][ty]=='x') return point(tx,ty);
            tx++;
        }
    }
    if(d==3)
    {
        while(1)
        {
            if(str[tx][ty]=='/') return dfs(tx,ty,2);
            if(str[tx][ty]=='\') return dfs(tx,ty,1);
            if(ty==1|| str[tx][ty]=='x') return point(tx,ty);
            ty--;
        }
    }
    if(d==4)
    {
        while(1)
        {
            if(str[tx][ty]=='/') return dfs(tx,ty,1);
            if(str[tx][ty]=='\') return dfs(tx,ty,2);
            if(ty==m|| str[tx][ty]=='x') return point(tx,ty);
            ty++;
        }
    }
}

int main()
{
    int i,j;
    w(~scanf("%d%d",&m,&n))
    {
        if(m+n==0)
        break;
        up(i,1,n)
        {
            scanf("%s",str[i]+1);
            up(j,1,m)
            {
                if(str[i][j]=='*')
                {
                    sx = i;
                    sy = j;
                }
            }
        }
        if(sx == 1) ans = dfs(sx,sy,2);
        else if(sx == n) ans = dfs(sx,sy,1);
        else if(sy == 1) ans = dfs(sx,sy,4);
        else ans = dfs(sx,sy,3);
        printf("HOUSE %d
",cas++);
        up(i,1,n)
        {
            up(j,1,m)
            {
                if(ans.x == i && ans.y == j)
                {
                    printf("&");
                    continue;
                }
                printf("%c",str[i][j]);
            }
            puts("");
        }

    }

    return 0;
}

/**************************************************************
    Problem: 1562
    User: aking2015
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1484 kb
****************************************************************/


/*
10 10
xxxxxxxxxx
x.../...x
x........x
x........x
x..//..x
*..//../x
x........x
x........x
x.../...x
xxxxxxxxxx
*/

Problem C: Lexicography

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 138  Solved: 42
[Submit][Status][Web Board]

Description

An anagram of a string is any string that can be formed using the same letters as the original. (We consider the original string an anagram of itself as well.) For example, the string ACM has the following 6 anagrams, as given in alphabetical order:

ACM
AMC
CAM
CMA
MAC
MCA
As another example, the string ICPC has the following 12 anagrams (in alphabetical order):

CCIP
CCPI
CICP
CIPC
CPCI
CPIC
ICCP
ICPC
IPCC
PCCI
PCIC
PICC
Given a string and a rank K, you are to determine the Kth such anagram according to alphabetical order.

Input

Each test case will be designated on a single line containing the original word followed by the desired rank K. Words will use uppercase letters (i.e., A through Z) and will have length at most 16. The value of K will be in the range from 1 to the number of distinct anagrams of the given word. A line of the form "# 0" designates the end of the input.

Output

For each test, display the Kth anagram of the original string.

Sample Input

ACM 5
ICPC 12
REGION 274
# 0

Sample Output

MAC
PICC
IGNORE

HINT

The value of K could be almost 245 in the largest tests, so you should use type long in Java, or type long long in C++ to store K.

 用到了一个组合数学的结论:n个a,m个b,o个c,全排的个数为:(n+m+o)!/n!/m!/o! ;对原先的字母排序,定首位依次往后全排;

转载请注明出处:寻找&星空の孩子

题目链接:http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1563

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
#define ls 2*i
#define rs 2*i+1
#define up(i,x,y) for(i=x;i<=y;i++)
#define down(i,x,y) for(i=x;i>=y;i--)
#define mem(a,x) memset(a,x,sizeof(a))
#define w(a) while(a)
#define LL long long
const double pi = acos(-1.0);
#define Len 100005

char str[50],ans[50];
LL f[50],m;

int main()
{
    int i,j,k,len1,len2,cnt[50];
    f[0] = 1;
    up(i,1,16)
    f[i]=f[i-1]*i;
    w(~scanf("%s%lld",str,&m))
    {
        if(str[0]=='#'&&m==0)
            break;
        mem(cnt,0);
        len1 = strlen(str);
        sort(str,str+len1);
        up(i,0,len1-1)
        cnt[str[i]-'A']++;
        up(i,0,len1-1)
        {
            LL last = 0,res;
            up(j,0,25)
            {
                if(cnt[j])
                {
                    res = f[len1-i-1];
                    up(k,0,25)
                    {
                        if(k==j) res/=f[cnt[k]-1];
                        else res/=f[cnt[k]];
                    }
                    if(last+res>=m)
                    {
                        ans[i] = j+'A';
                        m-=last;
                        cnt[j]--;
                        break;
                    }
                    else
                        last+=res;
                }
            }
        }
        ans[len1]='