首页 > ACM题库 > HDU-杭电 > HDU 3352-Tiles of Tetris, NOT![解题报告]HOJ
2014
03-16

HDU 3352-Tiles of Tetris, NOT![解题报告]HOJ

Tiles of Tetris, NOT!

问题描述 :

You’ve really messed up this time. “Go buy some square tiles” your supervisor told you. But as usual, you were either busy reading that message, answering that e-email, or updating your wall status on facebook. “Go buy some tiles” was all that you could remember. Your supervisor is now complaining that the tiles you bought were not squares and you’ll be fired if you don’t fix it!
“Fix it? How am I supposed to fix it?” you say to yourself. “I’m a programmer, The only tiles I know are those of the game Tetris!” There is no way you can afford to be fired either. This is your third job in less than a month. “I have to fix it!” you keep repeating.
You call the store you bought the tiles from, but they won’t take them back or even exchange. “We cannot cancel orders once the merchandise has left the store”, they tell you. You take a look at the tiles, they’re all rectangleshaped and all of the same size. You’d be losing a lot if you cut them, not that you’d be able to cut them into perfect squares in the first place. “Wait a minute!” you say to yourself. You grab a bunch of tiles, put them in some arrangement and Voila, that’s a square. But that won’t convince your boss.
Tiles are supposed to be small, and what you came-up with is rather big. You take another look at your arrangement, and it hits you again. “I’m on a roll today!” you say proudly to yourself.You just figured out how to find the smallest number of tiles needed to form the smallest possible square.
Seinfeld
You rush and bring your supervisor to show him your discovery. He’s not that much impressed. You’re not making sense anyway (given all the blood rushing in your head trying to explain your algorithm.) You know that the calculation is definitely much simpler than what you’re saying, but you just can’t seem to think clearly.
Finally, your supervisor shouts: “First of all, the tiles have to be laid-down in the same orientation. Second, I’m running a construction site here, not a software shop! How do you expect the workers to figure out that number! You either write me a program to do the calculation you’re describing, or you go collect your netbook, your cell, your ipod, and your blackberry, and you get out of here this minute!”
Seinfeld

输入:

Your program will be tested on one or more data sets. Each test set is described on a single line made of two positive numbers: (0 < W,H < 1, 000, 000) which are the width and height of each tile. The last line is made of two zeros.

输出:

Your program will be tested on one or more data sets. Each test set is described on a single line made of two positive numbers: (0 < W,H < 1, 000, 000) which are the width and height of each tile. The last line is made of two zeros.

样例输入:

2 3
1 2
0 0

样例输出:

6
2

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

Tiles of Tetris, NOT!View Code

#include <stdio.h>
int gcd(int a,int b)
{
    return a%b==0?b:gcd(b,a%b);
}
__int64 lcg(int a,int b)
{
    return (__int64)a*(__int64)b/(__int64)gcd(a,b)/(__int64)gcd(a,b);
} 
int main()
{
    int a,b;
    while(scanf("%d%d",&a,&b),(a||b))
        printf("%I64d\n",lcg(a,b));
    return 0;
}

 

参考:http://www.cnblogs.com/xiaohongmao/archive/2012/04/19/2456441.html


  1. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks