Kickstart Round A 2018

https://code.google.com/codejam/contest/9234486/dashboard#s=p0&a=2
官方题解：https://code.google.com/codejam/contest/9234486/dashboard#s=a&a=2

Problem A. Even Digits
从高位往低位遍历，遇到第一个奇数就停下来，然后要么这个奇数减一，后面变成888...；要么这个奇数加1，后面变成0000...

#file = 'small'
file = 'large'

ques = 'A'

fp = open('%s-%s-practice.in'%(ques, file), 'r')
#print(fp.read().split('\n'))
cs = list(map(int,fp.read().strip().split('\n')))
n = cs[0]
res = []

def slove(c):
    s=str(c)
    i=0
    while i<len(s):
        if int(s[i])%2!=0: break
        i+=1
    if i==len(s): return 0
    
    tt = str(int(s[i])-1)+str('8'*(len(s)-i-1))
    ret = int(s[i:])-int(tt)
    
    if s[i]=='9':
        tt = str('20')+str('0'*(len(s)-i-1))
        ret = min(ret,int(tt)-int(s[i:]))
    else:
        tt = str(int(s[i])+1)+str('0'*(len(s)-i-1))
        ret = min(ret,int(tt)-int(s[i:]))
    
    return ret
        

for i,c in enumerate(cs[1:]):
    print(i)
    res.append(slove(c))
    
fp = open('%s-%s-practice.out'%(ques, file), 'w')
for i,c in enumerate(res):
    fp.write('Case #%d: %d\n'%(i+1,c))

Problem B. Lucky Dip
DP，dp[i]表示有k次交换机会的情况下的均值，转移方程就要枚举i位置所有可能的值，然后跟dp[i-1]比，去max
大数据情况下，需要对数组先排序，然后二分或者用pointer

import sys
from itertools import accumulate
#file = 'test'
#file = 'small'
file = 'large'

ques = 'B'

res = []

def slove(a,n,k):
    if k==0: return sum(a)/n
    
    # pre-cal sum && BS or two pointers
    a.sort()
    acc = [0]+list(accumulate(a))
    p = 0
    
    dp = [0]*(k+1)
    dp[0] = sum(a)/n
    for i in range(1,k+1):
        while p<n and a[p]<=dp[i-1]: p+=1
        dp[i] = (acc[-1]-acc[p]+dp[i-1]*p)/n
    return dp[-1]
    
sys.stdin = open('%s-%s-practice.in'%(ques, file), 'r')
cases = int(input())
for i_ in range(cases):
    n,k=list(map(int,input().strip().split(' ')))
    a=list(map(int,input().strip().split(' ')))
    res.append(slove(a,n,k))
    
fp = open('%s-%s-practice.out'%(ques, file), 'w')
for i_,c in enumerate(res):
    fp.write('Case #%d: %.7f\n'%(i_+1,c))

Problem C. Scrambled Words
Note: We do not recommend using interpreted/slower languages for the Large dataset of this problem.所以用Python还是不行么？
只用暴力过了小数据

import sys
#file = 'test'
#file = 'small'
file = 'large'

ques = 'C'

res = []

def slove(a,n,s1,s2,N,A,B,C,D):
    s=['']*N
    s[0],s[1]=s1,s2
    x=[0]*N
    x[0],x[1]=ord(s1),ord(s2)
    for i in range(2,N):
        x[i] = (A*x[i-1]+B*x[i-2]+C)%D
        s[i]=chr(97+x[i]%26)
    s=''.join(s)
    
    ret = 0
    for ss in a:
        for i in range(len(s)-len(ss)+1):
            st = s[i:i+len(ss)]
            if st[0]==ss[0] and st[-1]==ss[-1] and (len(ss)<=2 or sorted(ss[1:-1])==sorted(st[1:-1])):
                ret+=1
                break
    return ret
    
sys.stdin = open('%s-%s-practice.in'%(ques, file), 'r')
cases = int(input())
for i_ in range(cases):
    n=int(input())
    a=input().strip().split(' ')
    b=input().strip().split(' ')
    s1,s2,N,A,B,C,D=b[0],b[1],int(b[2]),int(b[3]),int(b[4]),int(b[5]),int(b[6])
    res.append(slove(a,n,s1,s2,N,A,B,C,D))
    
fp = open('%s-%s-practice.out'%(ques, file), 'w')
for i_,c in enumerate(res):
    fp.write('Case #%d: %d\n'%(i_+1,c))

最后编辑于：2018.07.28 13:00:55