emu in blogjava
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  171 随笔 :: 103 文章 :: 1052 评论 :: 2 Trackbacks
Alphabet(赛前模拟题)

Problem Statement
????
The government of a small but important country has decided that the alphabet needs to be streamlined and reordered. Uppercase letters will be eliminated. They will issue a royal decree in the form of a String of 'B' and 'A' characters. The first character in the decree specifies whether 'a' must come ('B')Before 'b' in the new alphabet or ('A')After 'b'. The second character determines the relative placement of 'b' and 'c', etc. So, for example, "BAA" means that 'a' must come Before 'b', 'b' must come After 'c', and 'c' must come After 'd'.
Any letters beyond these requirements are to be excluded, so if the decree specifies k comparisons then the new alphabet will contain the first k+1 lowercase letters of the current alphabet.
Create a class Alphabet that contains the method choices that takes the decree as input and returns the number of possible new alphabets that conform to the decree. If more than 1,000,000,000 are possible, return -1.
Definition
????
Class:
Alphabet
Method:
choices
Parameters:
string
Returns:
int
Method signature:
int choices(string decree)
(be sure your method is public)
????

Constraints
-
decree contains between 1 and 25 characters inclusive.
-
Each character in decree is the upper case letter 'B' or 'A'.
Examples
0)

????
"BAA"
Returns: 3
a before b, b after c, and c after d have been decreed, so possibilities are adcb, dacb, dcab
1)

????
"AAAA"
Returns: 1
edcba is the only alphabet that conforms
2)

????
"BABABABABABABABABABABABAB"
Returns: -1
More than 1,000,000,000 alphabets conform to this decree
 
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-08-16 09:29 emu 阅读(1216) 评论(4)  编辑  收藏 所属分类: google编程大赛模拟题及入围赛真题

评论

# emu的解法 2005-08-16 09:52 emu
这道比较难，emu写了程序穷举了各种可能性输出后，手工分析了一番数据才终于找到规律。呕血中……


public class Alphabet {
public static void main(String[] args) {
Alphabet a = new Alphabet();
String[] data = new String[]{"BAABABBAABBBAAB:-1","AABBABABABABBA:520259727",
"BAABABAAABBBAAB:969740563","AAABABABABABBA:294939658"};
for (int i = 0; i < data.length; i++) {
String[] sample = data[ i ].split(":");
String decree = sample[0];
int choices = Integer.parseInt(sample[1]);
assertEquals(a.choices(decree), choices);
}
System.out.println("all passed!");
}

private static void assertEquals(int a, int b) {
if (a != b)
throw new RuntimeException("assert failed!! Expected " + b +
" but got " + a);
}

public int choices(String decree) {
int[] oldPosList = new int[3];
int timesCount = 1;
oldPosList[decree.startsWith("A")?1:2]=1;
for (int i = 2; i <= decree.length(); i++) {
timesCount = 0;
int[] newPosList = new int[i + 2];
char ch = decree.charAt(i - 1);
if (ch == 'A') {
for (int j = 1; j <= i; j++) {
int times = oldPosList[j];
if (i < decree.length())
for (int k = 1; k <= j; k++) newPosList[k] += times;
timesCount += j*times;
}
} else {
for (int j = 1; j <= i; j++) {
int times = oldPosList[j];
if (i < decree.length())
for (int k = j + 1; k <= i + 1; k++) newPosList[k] += times;
timesCount += (i-j+1)*times;
}
}
oldPosList = newPosList;
if (timesCount > 1000000000) return -1;
}
return timesCount;
}
}



  回复  更多评论
  

# 秋水无恨的javascript解法 2005-08-16 09:53 emu
<script>
var m=1000000000;//000;

function choices(decree)
{
    var i,j,n=1;
    var arrSum=new Array(26);//最后一个字母在每个位置的总合
    for(j=0;j<arrSum.length;++j)arrSum[j]=0;
    for(i=1;i<=decree.length;++i)
    {
        var tmpSum=new Array(26);
        for(j=0;j<26;++j)tmpSum[j]=0;

        if('A'==decree.charAt(i-1))
        {
            if(1==i)
            {
                arrSum[0]=1;
            }
            else
            {
                n=0;
                for(j=i-1;j>=0;--j)//向前分散，如123->6530
                {
                    n+=arrSum[j];
                    tmpSum[j]=n;
                }
                n = 0
                for(j=0;j<=i;++j)
                {//保存到arrSum
                    arrSum[j]=tmpSum[j];
                    n+=arrSum[j];
                }

            }
        }
        else
        {
            if(1==i)
            {
                arrSum[1]=1;
            }
            else
            {
                n=0;
                for(j=0;j<i;++j)//向后分散，如123->0136
                {
                    n+=arrSum[j];
                    tmpSum[j+1]=n;
                }
                n = 0
                for(j=0;j<=i;++j)
                {//保存到arrSum
                    arrSum[j]=tmpSum[j];
                    n+=arrSum[j];
                }
            }
        }
        document.write(decree.substr(0,i),"=",n,"<br>");
        //if(n>m)return -1;
    }

    return n;
}
document.write("BAA","=",choices("BAA"),"<br>");
document.write("AAAA","=",choices("AAAA"),"<br>");
document.write("BABABABABABABABABABABABAB","=",choices("BABABABABABABABABABABABAB"),"<br>");
</script>

  回复  更多评论
  

# 秋水无恨说要突破题目的1000000000的上限，于是改成这样 2005-08-16 09:59 emu
改用BigInteger，decree就可以无限增大了。

import java.math.BigInteger;
public class Alphabet {
public static void main(String[] args) {
long timeMillis = System.currentTimeMillis();
Alphabet a = new Alphabet();
String st = "BABABABABABABABABABABABABABABABABABABABABABABABAB";
System.out.println(st+" = "+a.choices(st));
}

private static void assertEquals(int a, int b) {
if (a != b)
throw new RuntimeException("assert failed!! Expected " + b +
" but got " + a);
}

public BigInteger choices(String decree) {
BigInteger[] oldPosList = new BigInteger[3];
BigInteger timesCount = BigInteger.ONE;
oldPosList[decree.startsWith("A")?1:2]=BigInteger.ONE;
for (int i = 2; i <= decree.length(); i++) {
timesCount = BigInteger.ZERO;
BigInteger[] newPosList = new BigInteger[i + 2];
char ch = decree.charAt(i - 1);
if (ch == 'A') {
for (int j = 1; j <= i; j++) {
BigInteger times = oldPosList[j];
if (times == null) times = BigInteger.ZERO;
if (i < decree.length())
for (int k = 1; k <= j; k++)
newPosList[k] = (newPosList[k]==null)?times:newPosList[k].add(times);
// timesCount += j*times;
timesCount = timesCount.add(new BigInteger(j+"").multiply(times));
}
} else {
for (int j = 1; j <= i; j++) {
BigInteger times = oldPosList[j];
if (times == null) times = BigInteger.ZERO;
if (i < decree.length())
for (int k = j + 1; k <= i + 1; k++)
newPosList[k] = (newPosList[k]==null)?times:newPosList[k].add(times);
// timesCount += (i-j+1)*times;
timesCount = timesCount.add(new BigInteger((i-j+1)+"").multiply(times));
}
}
oldPosList = newPosList;
// if (timesCount > 1000000000) return -1;
}
return timesCount;
}
}
  回复  更多评论
  

# re: Alphabet(赛前模拟题) 2005-12-03 01:58 朱星星的C#解法
using System;
using System.Collections.Generic;

class Alphabet
{
public int choices(string decree)
{
int N = decree.Length + 1;
int[,] m = new int[N+1, N+1];
m[0,0] = 1;
m[1, 0] = 1;
for (int i = 2; i <= N; ++i)
for (int j = 0; j < i; ++j)
{
if (decree[i - 2] == 'A')
for (int k = 0; k < j; ++k)
m[i, j] += m[i - 1, k];
else
for (int k = j; k < i - 1; ++k)
m[i, j] += m[i - 1, k];
if (m[i, j] >= 1000000000) return -1;
}
int ret = 0;
for (int i = 0; i < N; ++i)
ret += m[N, i];
if (ret >= 1000000000) return -1;
return ret;
}
}

  回复  更多评论
  


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