[数据结构与算法]牛客网：Bigger And Bigger

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

????This is a simple question.
????Given you two hexadecimal digits x and y, you should determine whether 2x+102x+102x+10 is greater than 3y+53y+53y+5.

输入描述:

Each test contain multiple test cases. The first line contains the number of test cases t(1≤t≤100)t(1\le t \le 100)t(1≤t≤100). Description of the test cases follow.

The description of each test case consists of two hexadecimal digits x, y separated by spaces.

It's guarantee that x ,y only consists of number '0'-'9' and capital letters 'A'-'F' and there are no leading zeros.

1≤x,y<1610001 \le x, y < 16^{1000}1≤x,y<161000

输出描述:

For each test case, if 2x+10>3y+52x+10 > 3y+52x+10>3y+5, print "Yes", Otherwise print "No".

示例1

输入

复制3 A B F0 E11 FF0123FFFFFFFFFF 01FEA23FFF

3
A B
F0 E11
FF0123FFFFFFFFFF 01FEA23FFF

输出

复制No No Yes

No
No
Yes

//最笨的方法，但思路还算清晰
#include<stdio.h>
#include<string.h>
int turn(char a, int t)
{
	if (a >= '0' && a <= '9') return (a - '0') * t;
	else return (a - 'A' + 10) * t ;
}
char retu(int t)
{
	if (t >= 0 && t <= 9) return t + '0';
	else return 'A' + t - 10;
}
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
    {
		char a[1005] = { 0 }, b[1005] = { 0 };
        char ta[1005] = { 0 }, tb[1005] = { 0 };
        int ia[1005] = { 0 }, ib[1005] = { 0 };//可行域在while内，用完就释放，不用清除
		scanf("%s %s", a, b);
		int loa = strlen(a);
		int lob = strlen(b);
		int lia = 0, lib = 0;//控制存储的位置，同时也可以表示数字长度
		for (int i = loa-1; i >=0; i--) //从最低位处理x
        {
			ia[lia] += turn(a[i], 2);
			if (i == loa - 1)
				ia[lia] += 5;//转成运算后的数字
			ia[lia + 1] += ia[lia] / 16;//看是否有进位，没有也没关系，+0
			ia[lia] %= 16;//进位后原位置的数
			lia++;
		}
		if(ia[lia]>0)//看这个数处理后位数有没有增加（即最高位有没有进位）
			lia++;
        while(ia[lia] >= 16)//如果所乘的数比较大，最高位有可能再进位
        {
			ia[lia + 1] += ia[lia] / 16;
			ia[lia] %= 16;
			lia++;
		}
		while(ia[lia]==0) 
            lia--;//处理前导零
		for (int i = lob-1; i >=0; i--) //处理y
        {
			ib[lib] += turn(b[i], 3);
			ib[lib + 1] += ib[lib] / 16;
			ib[lib] %= 16;
			lib++;
		}
		if(ia[lib]>0)
			lib++;
        while(ib[lib] >= 16) 
        {
			ib[lib + 1] += ib[lib] / 16;
			ib[lib] %= 16;
			lib++;
		}
		while(ib[lib]==0) 
            lib--;
		if (lia > lib)//长度大的必然大
			printf("Yes\n");
		else if (lia < lib)
			printf("No\n");
		else {
			int u;
			for (u = lia - 1; u >= 0; u--)  //由于存的时候是从位置0开始存的，所以位置0是最小位，应从最后一位开始比
            {
				if (ia[u] > ib[u])
				{
					printf("Yes\n");
					break;
				}
                else if(ia[u] < ib[u])
				{
					printf("No\n");
					break;
				}
				else continue;
			}
			if (u == -1)//相等的情况
				printf("No\n");
		}
	}
	return 0;
}