emu in blogjava

:: 管理 ::

171 隨筆 :: 103 文章 :: 1052 評論 :: 2 Trackbacks

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 閱讀(1236) 評論(4) 編輯收藏所屬分類: google編程大賽模擬題及入圍賽真題

這道比較難，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

# 秋水無恨說要突破題目的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;
}
}

回復更多評論

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 沒忍住手癢做了一道題，結果還沒作對。差點被燕潘考倒了 1000分模擬題CraneWork 500分模擬題 MaximalPalindromeSubstrings 250分模擬題 SalesRouting SecretSum (code jam china round2 500分真題) FactorialSystem (code jam china round2 300分真題) RecurringNumbers (code jam china 1000分真題) google中國編程挑戰賽入圍賽真題 -- HardDuplicateRemover(1000分) google中國編程挑戰賽入圍賽真題 -- BlockStructure(500分)

emu in blogjava

公告

常用鏈接

留言簿(92)

隨筆分類(20)

隨筆檔案(171)

文章分類(89)

文章檔案(103)

相冊

收藏夾(46)

友情連接

收藏

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

評論