8月12号 zenefit OA 3

原帖地址:一亩三分地

版内朋友内推的zenefits。前天接到的zenefit challange III, 似乎就是OA3。今天做了。第二个test case都没全过……估计要挂了

第一题叫sell tickets。火车站有一些买票点(station)。每个买票点有数量不同的存票。而且票的价格和此买票点卖票时的存票量相同。比如:A来点1,有15张票,那么票就卖A 15块。A之后B来了。此时点A只有14张票,就卖B 14块。火车站有个卖票点总指标,卖够了就收摊。问卖完这个指标的最大收益。
输入是如下的两行。
2, 4
5, 2
第一行第一个数是买票点(station)的数量,这里是2个。第二个数是总指标的值。这里是4张。
第二行是各个买票点的最开始的存票数量。这里5张和2张。
最大的收益是14。

这个我觉得还不算难。不过要先想清楚到底是怎么卖票的。首先肯定永远卖票最多那个买票点的票,因为价格最高。而后当票卖到好几个买票点一样多的时候就是这些买票点轮流卖票了。

比如如下情况:

3, 5

10, 8, 5

买票的次序就是:10, 9, 8, 8, 7

所以最开始就把各买票点sort一下。而后一个价格区间一个价格区间的卖。卖到最后收尾。python代码大概如下:
tmp = raw_input().split()
station_num = int(tmp[0])
m = int(tmp[1])

a = sorted([int(t) for t in raw_input().split()])
revenue = 0
sold = 0

for window in range(len(a)):
if window < len(a) - 1: next_window = a[window + 1] else: next_window = 0 stop = (m - sold)/(window + 1) < (a[window] - next_window) if stop: price_step = (m - sold)/(window + 1) else: price_step = a[window] - next_window .鐣欏璁哄潧-涓憨-涓夊垎鍦/span> # 用等差公式求出revenue的增量
revenue += (window+1)*(2*a[window] – price_step + 1)/2
sold += price_step*(window + 1)
if stop:
revenue += (m – sold)*(a[window] – price_step)
sold = m
break

print revenue

输入是从stdin读入的,输出也是输出到stdout。所以io看起来可能有些怪。不过还是蛮快就过了。

第二题叫word rank。首先题里定义了一个word rank。是说一个词在其所有permutation中的排序。比如‘cab’,所有的permutation排序后是’abc’, ‘bac’, ‘bca’, ‘cab’, ‘cba’。其中‘cab’在第4个,所有它的word rank就是3(rank的计数从0开始)。
这个题我觉得想起来不太困难不过就是没过全部的test case。也看不到没有过的case到底是什么。所以我也不知道是逻辑有遗漏还是求阶乘的时候数据有溢出。。。明白人帮帮忙啊。、
这个是file io,parsing的code他给好了。我也就只写中间比较重要的code了。也都是python
def word_num(letters):
#求出对于给定字符集合,所有的permutation的数量
total = 0
div = 1
for c in letters:
total += letters[c]
for i in range(letters[c]):
div *= i + 1
tmp = 1
for i in range(total):
tmp *= i+1
return tmp/div

def get_rank(word):
letters = {}
for c in word:
if c in letters:
letters[c] += 1
else:
letters[c] = 1

rank = 0
for c in word:
#当前位前一样,但当前位比word小的permutation的数量
for lower in letters:
if lower < c and letters[lower] > 0:
letters[lower] -= 1
rank += word_num(letters)
letters[lower] += 1
letters[c] -= 1
#至当前位都一样,但之后比word小的情况
return rank

不知道有没有错,有没有可以优化的地方。出身是EE所以coding可能也不太漂亮。高人们多指正啊。小弟多谢了。