首页 > ACM题库 > HDU-杭电 > HDU 4207-Grade School Multiplication-模拟-[解题报告]HOJ
2015
05-23

HDU 4207-Grade School Multiplication-模拟-[解题报告]HOJ

Grade School Multiplication

问题描述 :

An educational software company, All Computer Math (ACM), has a section on multiplication of integers. They want to display the calculations in the traditional grade school format, like the following computation of 432 × 5678:

    432
5678
-------
3456
3024
2592
2160
-------
2452896

Note well that the final product is printed without any leading spaces, but that leading spaces are necessary on some of the other lines to maintain proper alignment. However, as per our regional rules, there should never be any lines with trailing white space. Note that the lines of dashes have length matching the final product.

As a special case, when one of the digits of the second operand is a zero, it generates a single 0 in the partial answers, and the next partial result should be on the same line rather than the next line down. For example, consider the following product of 200001 × 90040:

     200001
90040
-----------
8000040
180000900
-----------
18008090040

The rightmost digit of the second operand is a 0, causing a 0 to be placed in the rightmost column of the first partial product. However, rather than continue to a new line, the partial product of 4 × 200001 is placed on the same line as that 0. The third and fourth least-significant digits of the second operand are zeros, each resulting in a 0 in the second partial product on the same line as the result of 9 × 200001.

As a final special case, if there is only one line in the partial answer, it constitutes a full answer, and so there is no need for computing a sum. For example, a computation of 246 × 70 would be formatted as


246
70
-----
17220

Your job is to generate the solution displays.

输入:

The input contains one or more data sets. Each data set consists of two positive integers on a line, designating the operands in the desired order. Neither number will have more than 6 digits, and neither will have leading zeros. After the last data set is a line containing only 0 0.

输出:

The input contains one or more data sets. Each data set consists of two positive integers on a line, designating the operands in the desired order. Neither number will have more than 6 digits, and neither will have leading zeros. After the last data set is a line containing only 0 0.

样例输入:

432 5678
200001 90040
246 70
0 0

样例输出:

Problem 1
    432
   5678
-------
   3456
  3024
 2592
2160
-------
2452896
Problem 2
     200001
      90040
-----------
    8000040
180000900
-----------
18008090040
Problem 3
  246
   70
-----
17220

MCPC 2011Hdu4207-4214(未完全)题解

第一题:Grade School Multiplication

http://acm.hdu.edu.cn/showproblem.php?pid=4207

题目大意:给你两个数,要求按照题目所讲的规律一步步得出结果。

如:给你两个数432  和 5678,你就要按照下面的规律输出

    432

   5678

——-

   3456

  3024

 2592

2160

——-

2452896

模拟。

因为数据范围不是很大,所以直接用long long型计算每一位然后输出结果就行。

注意:特别要注意0的情况,因为没有考虑这种情况导致了多次wa

代码:

 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
using namespace std;
template <class T> void checkmin(T &t,T x) {if(x < t) t = x;}
template <class T> void checkmax(T &t,T x) {if(x > t) t = x;}
template <class T> void _checkmin(T &t,T x) {if(t==-1) t = x; if(x < t) t = x;}
template <class T> void _checkmax(T &t,T x) {if(t==-1) t = x; if(x > t) t = x;}
typedef pair <int,int> PII;
typedef pair <double,double> PDD;
typedef long long ll;
#define foreach(it,v) for(__typeof((v).begin()) it = (v).begin(); it != (v).end ; it ++)
ll a , b;
int cas = 1;
int wei(ll a) {
    int ans = 0;
    while(a) {
        a /= 10;
        ans ++;
    }
    checkmax(ans , 1);
    return ans;
}
int oowei(ll a) {
    int ans = 0;
    while(a) {
        if(a % 10 != 0) ans ++;
        a /= 10;
    }
    checkmax(ans , 1);
    return ans;
}
int main() {
    while(cin >> a >> b) {
        if(a + b == 0) break;
        printf("Problem %d\n",cas++);
        ll c = a * b;
        int Wa = wei(a) , Wb = wei(b) , Wc = wei(c);
        if(c == 0) {
            int dd = max(Wa , Wb);
            if(a != 0) cout << a << endl;
            else for(int i=1;i<dd;i++) putchar(' ');
            cout << a << endl;
            if(b != 0) cout << b << endl;
            else for(int i=1;i<dd;i++) putchar(' ');
            cout << b << endl;
            for(int i=0;i<dd;i++) putchar('-');
            puts("");
            for(int i=1;i<dd;i++) putchar(' ');
            cout << c << endl;
            continue;
        }
        int oWb = oowei(b);
        for(int i=0;i<Wc-Wa;i++) putchar(' ');
        cout << a << endl;
        for(int i=0;i<Wc-Wb;i++) putchar(' ');
        cout << b << endl;
        for(int i=0;i<Wc;i++) putchar('-');
        puts("");
        int cc = 0;
        ll ad = 0;
        while(b) {
            ll d = b%10;
            b /= 10;
            if(d == 0) { ad +=1; cc++; continue; }
            d *= a;
            ll Wd = wei(d);
            for(int i=0;i<Wc-Wd-cc;i++) putchar(' ');
            cout << d ;
            while(ad > 0) putchar('0') , ad -= 1;
            cout << endl;
            cc ++;
        }
        if(oWb > 1) {
            for(int i=0;i<Wc;i++) putchar('-');
            puts("");
            cout << c << endl;
        }
    }
    return 0;
}

 

第二题:Laser Tag

http://acm.hdu.edu.cn/showproblem.php?pid=4208

题目大意:有n面镜子( 1 ≤ n ≤ 7),现在我站在(0,0)点发射激光,激光照到镜子上会按照物理规律反射,最后有可能射到我自己;求沿x轴正方向0->359度所有能伤到自己的发射角度。

计算几何。

(题解:暂缺)

 

第三题:Pizza Pricing

http://acm.hdu.edu.cn/showproblem.php?pid=4209

题目大意:简单题。找价值最高的pizza,输出他的直径。

代码:

 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
using namespace std;
template <class T> void checkmin(T &t,T x) {if(x < t) t = x;}
template <class T> void checkmax(T &t,T x) {if(x > t) t = x;}
template <class T> void _checkmin(T &t,T x) {if(t==-1) t = x; if(x < t) t = x;}
template <class T> void _checkmax(T &t,T x) {if(t==-1) t = x; if(x > t) t = x;}
typedef pair <int,int> PII;
typedef pair <double,double> PDD;
typedef long long ll;
#define foreach(it,v) for(__typeof((v).begin()) it = (v).begin(); it != (v).end ; it ++)
int n , a , b , ans , cas = 1;
double tmp;
int main() {
    while(~scanf("%d",&n) && n) {
        tmp = -1.0;
        for(int i=0;i<n;i++) {
            scanf("%d%d",&a,&b);
            double tp = ((double)(a*a)) / ((double)b);
            if(tp > tmp) {ans = a; tmp = tp;}
        }
        printf("Menu %d: %d\n",cas++,ans);
    }
    return 0;
}

 

第四题:Su-domino-ku

http://acm.hdu.edu.cn/showproblem.php?pid=4210

题目大意:数独题目的变形。要求拼出符合如下规律的数独:
Each row must contain each of the digits 1 through 9.
Each column must contain each of the digits 1 through 9.
Each of the indicated three-by-three squares must contain each of the digits 1 through 9.
For a su-domino-ku, nine arbitrary cells are initialized with the numbers 1 to 9. This leaves 72 remaining cells. Those must be filled by making use of the following set of 36 domino tiles. The tile set includes one domino for each possible pair of unique numbers from 1 to 9 (e.g., 1+2, 1+3, 1+4, 1+5, 1+6, 1+7, 1+8, 1+9, 2+3, 2+4, 2+5, …). Note well that there are not separate 1+2 and 2+1 tiles in the set; the single such domino can be rotated to provide either orientation. Also, note that dominos may cross the boundary of the three-by-three squares (as does the 2+9 domino in our coming example).

DLX解决精确覆盖问题。

代码:

 

第五题:Refrigerator Magnets

http://acm.hdu.edu.cn/showproblem.php?pid=4211

题目大意:输入多串数,如果某个串中没有那个字母出现超过一次,则输出。

简单题。直接check一下就行。

代码:

 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
using namespace std;
template <class T> void checkmin(T &t,T x) {if(x < t) t = x;}
template <class T> void checkmax(T &t,T x) {if(x > t) t = x;}
template <class T> void _checkmin(T &t,T x) {if(t==-1) t = x; if(x < t) t = x;}
template <class T> void _checkmax(T &t,T x) {if(t==-1) t = x; if(x > t) t = x;}
typedef pair <int,int> PII;
typedef pair <double,double> PDD;
typedef long long ll;
#define foreach(it,v) for(__typeof((v).begin()) it = (v).begin(); it != (v).end ; it ++)
int main() {
    char ch[100100];
    bool vis[26];
    while(gets(ch)) {
        if(strcmp(ch,"END") == 0) break;
        int ok = 1;
        memset(vis,0,sizeof(vis));
        for(int i=0;ch[i];i++) {
            if(ch[i] == ' ') continue;
            int t = ch[i] - 'A';
            if(vis[t]) { ok=0;break; }
            vis[t] = 1;
        }
        if(ok) puts(ch);
    }
    return 0;
}

 

第六题:Shut the Box

http://acm.hdu.edu.cn/showproblem.php?pid=4212

题目大意:给出一些数的集合S,然后给出一个个数Ai,对于Ai,必须取出S中的一些数使他们的和是Ai。问最多能坚持到第几个数。

题解:(暂缺)。

 

第七题:Sokoban

http://acm.hdu.edu.cn/showproblem.php?pid=4213

题目大意:

题解:(暂缺)

 

第八题:Crash and Go(relians)

http://acm.hdu.edu.cn/showproblem.php?pid=4214

题目大意:平面上有一些圆,对于彼此n个相交的圆,对他们的合并操作是:原来的圆消失,新圆的圆心坐标是n个圆坐标的平均值,新圆的半径是n个圆半径的和。问经过若干次合并操作后平面上一共还剩下几个圆。

模拟。

(暂wa

 

参考:http://www.cnblogs.com/aiiYuu/archive/2013/03/28/2985863.html