emu in blogjava
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  171 随笔 :: 103 文章 :: 1052 评论 :: 2 Trackbacks
SecretSum (code jam china round2 500分真题)

Problem Statement

    

We can substitute each digit of a number with a unique letter from 'A' to 'Z'. This way we can write groups of numbers in a single representation. For example "ABA" can represent any of the following: 101, 151, 343, 767, 929. However, "ABA" cannot mean 555 because each letter must stand for a distinct digit. Furthermore, numbers cannot begin with 0 and thus 'A' cannot be replaced by 0.

Given two such representations num1 and num2 and the result of their summation return the total number of possible combinations of numbers for which the equation holds. If no combinations are possible then return 0.

Definition

    
Class: SecretSum
Method: countPossible
Parameters: String, String, String
Returns: int
Method signature: int countPossible(String num1, String num2, String result)
(be sure your method is public)
    

Constraints

- num1, num2, and result will each contain exactly 3 uppercase letters ('A' - 'Z').

Examples

0)
     
"AAA"
"BBB"
"CCC"
Returns: 32
1)
     
"ABB"
"DEE"
"TTT"
Returns: 112
2)
     
"ABC"
"ABA"
"ACC"
Returns: 0
Leading zeroes are not allowed.
3)
     
"AAA"
"CDD"
"BAA"
Returns: 32
4)
     
"TEF"
"FET"
"AAA"
Returns: 12
5)
     
"ABC"
"ABC"
"BCE"
Returns: 5
We can have the following 5 sums: 
124 + 124 = 248
125 + 125 = 250
249 + 249 = 498
374 + 374 = 748
375 + 375 = 750
6)
     
"AAA"
"AAA"
"BBB"
Returns: 4
We can have the following 4 sums: 
111 + 111 = 222
222 + 222 = 444
333 + 333 = 666
444 + 444 = 888

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

posted on 2005-12-23 10:28 emu 阅读(2220) 评论(6)  编辑  收藏 所属分类: google编程大赛模拟题及入围赛真题

评论

# re: SecretSum (code jam china round2 500分真题) 2005-12-23 15:15 Tendy
我的解法。
用的是笨笨的穷举法~~
ps: Java的String 不能用[]，真不方便~~~
public class SecretSum
{
public int countPossible (String num1, String num2, String result)
{
int total = 0;
String s = num1 + num2 + result;
int i;
String uniqueChars = "";
char ch;
for (i = 0; i < s.length(); ++i)
{
ch = s.charAt(i);
if (uniqueChars.indexOf(ch) < 0)
uniqueChars += ch;
}

if (uniqueChars.length() > 10) // 10个以上不同的字母，出错
return 0;

int maxTotal = 1; // 穷举次数
for (i = 0; i < uniqueChars.length(); ++i)
maxTotal *= 10;

int numberMinValue = 1; // 每个数字最小值（用于限制最高位不能为0）
for (i = 1; i < num1.length(); ++i)
numberMinValue *= 10;

String temp; // 临时变量
String s1, s2, s3; // 分别对应num1, num2, result，用于将字母替换成数字
int n1, n2, n3; // 替换后数字
boolean validNumber;
// 穷举
for (int counter = maxTotal / 10; counter < maxTotal; ++counter)
{
temp = String.valueOf(counter);
if (temp.length() < uniqueChars.length())
continue;

validNumber = true;
for (i = 0; i < temp.length(); ++i)
{
if (temp.lastIndexOf(temp.charAt(i)) != i) // 计算每个数字是否只出现一次
validNumber = false;
}

if (validNumber)
{
s1 = num1;
s2 = num2;
s3 = result;
for (i = 0; i < temp.length(); ++i)
{
s1 = s1.replace(uniqueChars.charAt(i), temp.charAt(i));
s2 = s2.replace(uniqueChars.charAt(i), temp.charAt(i));
s3 = s3.replace(uniqueChars.charAt(i), temp.charAt(i));
}
n1 = Integer.valueOf(s1);
n2 = Integer.valueOf(s2);
n3 = Integer.valueOf(s3);
if (n1 >= numberMinValue && n2 >= numberMinValue && n1 + n2 == n3)
++total; // found 1
}
}
return total;
}

public static void main(String[] args)
{
SecretSum ss = new SecretSum();
System.out.println(ss.countPossible("AAA", "BBB", "CCC"));
System.out.println(ss.countPossible("ABB", "DEE", "TTT"));
System.out.println(ss.countPossible("ABC", "ABA", "ACC"));
System.out.println(ss.countPossible("AAA", "CDD", "BAA"));
System.out.println(ss.countPossible("TEF", "FET", "AAA"));
System.out.println(ss.countPossible("ABC", "ABC", "BCE"));
System.out.println(ss.countPossible("AAA", "AAA", "BBB"));
}
}  回复  更多评论
  

# re: SecretSum (code jam china round2 500分真题) 2005-12-23 15:17 Tendy
if (temp.lastIndexOf(temp.charAt(i)) != i) validNumber = false;
这句忘了加个 break;
不影响结果，不过效率高点点..  回复  更多评论
  

# re: SecretSum (code jam china round2 500分真题) 2006-01-13 16:48 akang
很不错的算法,楼主厉害啊  回复  更多评论
  

# re: SecretSum (code jam china round2 500分真题) 2006-07-21 22:09 清风剑
如果有更多朋友写答案上来就更好了。  回复  更多评论
  

# re: SecretSum (code jam china round2 500分真题) 2006-07-25 23:54 yuyou
@Tendy
  回复  更多评论
  

# re: SecretSum (code jam china round2 500分真题) 2009-07-24 12:37 Jamers
"AAA"
"CDD"
"BAA"

Returns: 32

我编的算法，做出来怎 么是31？指点下…看看有什么疏忽…
111+300=411
111+400=511
111+500=611
111+600=711
111+700=811
111+800=911
222+100=322
222+300=522
222+400=622
222+500=722
222+600=822
222+700=922
333+100=433
333+200=533
333+400=733
333+500=833
333+600=933
444+100=544
444+200=644
444+300=744
444+500=944
555+100=655
555+200=755
555+300=855
555+400=955
666+100=766
666+200=866
666+300=966
777+100=877
777+200=977
888+100=988
  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: