We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
# Enter your code here. Read input from STDIN. Print output to STDOUTimportmathfromcollectionsimportdequen,k,l=map(int,input().split())last_d=['1','3','7','9']primes=[0foriinrange(2,1+10**n)]foriinrange(2,int(math.sqrt(10**n))):ifprimes[i]:continueforjinrange(i*2,len(primes),i):primes[j]=1defmain():ifk==n:#solutions can only be 1*, 3*, 7* and 9* and not l > 4print(11)else:soln,soln_space=[],deque(map(lambdax:'0'*(n-len(x))+x,[bin(i)[2:]foriinrange(2**n-1,-1,-1)ifbin(i).count('1')==k]))T,minval=1,10**7whilesoln_space:N=soln_space.popleft()ifT%2==1elsesoln_space.pop()T+=1if(N[0]=='1'andN[-1]=='1')orN[-1]=='1':v=last_delifN[0]=='1':v=range(1,10)else:v=range(10)N=N.replace('1','-')c,end_val=[0for_inrange(n)],1for_inrange(n):ifN[_]=='0':if_==0:c[_],end_val=deque(range(1,10)),end_val*9elif_==n-1:c[_],end_val=deque(last_d),end_val*4else:c[_],end_val=deque(range(10)),end_val*10else:c[_]=N[_]z_c=0#print(N)whilez_c<end_val:r_c,N=1,''for_inrange(len(c)-1,-1,-1):ifnotc[_]=='-':ifr_c==1andz_c!=0:c[_].rotate(-1)elifz_c>0andz_c%r_c==0:c[_].rotate(-1)N=str(c[_][0])+Nr_c*=len(c[_])else:N='-'+Nz_c+=1ifint(N.replace('-',str(v[0])))>minval:breaktmp,ll=[],len(v)iflen(v)<l:breakforjinrange(ll):val=N.replace('-',str(v[j]))if(j==0andint(val)>minval):breakifprimes[int(val)]==0:tmp.append(val)iflen(tmp)>=l:ifminval>int(tmp[0]):minval=int(tmp[0])soln.append(tmp)breakiflen(tmp)+ll-(j+1)<l:break#print(soln)soln.sort()print(*soln[0][:l])if__name__=='__main__':main()
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Project Euler #51: Prime digit replacements
You are viewing a single comment's thread. Return to all comments →
100% python3