In this HackerRank Ones and Twos problem solution, You are using at most A number of 1s and at most B number of 2s. How many different evaluation results are possible when they are formed in an expression containing only addition + sign and multiplication * sign are allowed?
Problem solution in Java.
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Solution {
static Solution main;
public class Range implements Comparable<Range> {
int minPower;
int maxPower;
long range;
public Range(int min , int max , long r) {
minPower = min;
maxPower = max;
range = r;
}
public int compareTo(Range r) {
int comp = new Integer(minPower).compareTo(r.minPower);
if(comp!=0) {
return comp;
}
return new Integer(maxPower).compareTo(r.maxPower);
}
}
public static void main(String[] args) {
main = new Solution();
long [][] dp = new long[1001][1001];
long [][] dp1 = new long[1001][1001];
long [][] dpsum = new long[1001][1001];
long sp = 1000000007;
for(int i = 0 ; i < 1001 ; i++) {
Arrays.fill(dp[i], 0);
}
long [] pow2 = new long [32];
pow2[0] = 1;
for(int i = 1 ; i <32 ; i++) {
pow2[i ] = pow2[i-1] * 2;
}
dp[1][1] = 1;
for(int i = 2 ; i < 1001 ; i++) {
for(int j = 1 ; j <= i ; j++) {
long temp = 0;
for(int k = j+1 ; k < i ; k++) {
temp += dp[i-j][k];
if(temp>=sp) {
temp-=sp;
}
}
if(i==j) {
temp++;
if(temp>=sp) {
temp-=sp;
}
}
dp[i][j] = temp ;
}
}
for(int k = 0 ; k < 1001 ; k++) {
Arrays.fill(dp1[k],0);
}
for(int i = 0 ; i < 1001 ; i++) {
dpsum[i][0] = 0;
}
for(int i = 0 ; i < 1001 ; i++) {
for(int j = 1 ; j < 1001 ; j++) {
dpsum[i][j] = dpsum[i][j-1] + dp[i][j];
if(dpsum[i][j]>=sp) {
dpsum[i][j] -= sp;
}
}
}
for(int k = 1 ; k < 1001 ; k++) {
for(int i = k ; i < 1001 ; i++) {
if(i==k) {
dp1[i][k] = 1;
} else {
dp1[i][k] = dp1[i-1][k] + dp[i][k];
if(dp1[i][k] >= sp) {
dp1[i][k] -= sp;
}
}
}
}
long [][][] list = new long[1001][32][32];
long [] all = new long[1001];
for(int i = 0 ; i < 1001 ; i++) {
for(int j = 0 ; j < 32 ; j++) {
for(int k = 0 ; k < 32 ; k++) {
list[i][j][k] = 0;
}
}
all[i] = 0;
for(int j = 1 ; j <= Math.min(i/2, 500) ; j++) {
for(int k = j + 1 ; k <= i-j ; k++) {
long repValue = 0;
if(j+k==i) {
repValue ++;
}
repValue += dpsum[i-j-k][i-j-k] - dpsum[i-j-k][k];
if(repValue<0) {
repValue += sp;
}
if(repValue>=sp) {
repValue -= sp;
}
if(k<32) {
list[i][j][k] = repValue;
} else {
all[i] += repValue;
}
}
}
all[i] %= sp;
}
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedOutputStream bos = new BufferedOutputStream(System.out);
String eol = System.getProperty("line.separator");
byte[] eolb = eol.getBytes();
try {
String str = br.readLine();
int t = Integer.parseInt(str);
for(int i = 0 ; i < t ; i++) {
str = br.readLine();
int blank = str.indexOf(" ");
int a = Integer.parseInt(str.substring(0,blank));
int b = Integer.parseInt(str.substring(blank+1));
long ans = 0;
if(b==0) {
bos.write(new Long(a).toString().getBytes());
}else if (a==0){
for(int d = 0 ; d <= b ; d++) {
long temp = dp1[b][d];
ans += temp;
}
ans %= sp;
bos.write(new Long(ans).toString().getBytes());
} else {
for(int d = 0 ; d < b ; d++) {
long temp = dp1[b-1][d];
long mult = 2;
temp *= mult;
ans += temp;
}
ans %= sp;
for(int d = 0 ; d < 32 ; d++) {
for(int e = d+1 ; e < 32 ; e++ ) {
long repValue = list[b][d][e];
long temp = repValue * Math.min(a+1,pow2[e]-pow2[d]);
ans += temp;
ans %= sp;
}
}
ans %= sp;
long temp = all[b] * (a+1);
ans += temp;
ans+=a+2;
ans %= sp;
bos.write(new Long(ans).toString().getBytes());
}
bos.write(eolb);
}
bos.flush();
} catch(IOException ioe) {
ioe.printStackTrace();
}
}
}Problem solution in C++.
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int MOD = 1e9 + 7;
int dp_sum[1001][1001],dp_bit[1001][1001];
void add(int &x,long long v){
v%=MOD;
x+=v;
if(x>=MOD)x-=MOD;
}
int f_bit(int lv,int B);
int f_sum(int lv,int B){
if(lv>B)return 1;
if(dp_sum[lv][B]!=-1)return dp_sum[lv][B];
int tmp=f_sum(lv+1,B);
add(tmp,f_bit(lv,B));
return dp_sum[lv][B]=tmp;
}
int f_bit(int lv,int B){
if(lv>B)return 0;
if(dp_bit[lv][B]!=-1)return dp_bit[lv][B];
return dp_bit[lv][B]=f_sum(lv+1,B-lv);
}
int main(){
int T,A,B;
scanf("%d",&T);
memset(dp_sum,-1,sizeof(dp_sum));
memset(dp_bit,-1,sizeof(dp_bit));
while(T--){
scanf("%d%d",&A,&B);
int an=0;
if(A==0)an=f_sum(1,B);
else{
int k=1;
while((1LL<<k)<=A)k++;
k++;
add(an,(long long)(A+1)*f_sum(k,B));
long long ha=(1LL<<k)-A-1;
int now=0,i=1;
long long last=0;
while(ha>0){
now++;
if(B<now)break;
add(an,min((1LL<<i)-last,ha)*f_sum(k,B-now));
ha-=(1LL<<i)-last;
last=1LL<<i;
i++;
if(i==k){
last=0;
i=1;
}
}
/*
long long last=A;
for(int i=1;i<=B;i++){
if(last+1>=(1LL<<k))break;
add(an,(min(((long long)A+(1LL<<i)),(1LL<<k)-1)-last)*f_sum(k,B-i));
last=min((long long)A+(1LL<<i),(1LL<<k)-1);
}*/
}
printf("%d\n",(an+MOD-1)%MOD);
}
return 0;
}Problem solution in C.
#include <stdio.h>
#include <stdlib.h>
#define MOD 1000000007
long long dp[1001][1001][31]={0},dp3[1001];
int main(){
int T,A,B,l,i,j,k;
long long t,f;
for(k=0;k<31;k++)
for(i=k+1;i<=1000;i++)
for(j=k+1;j<=1000;j++)
if(i==k+1){
if(j==k+1)
dp[i][j][k]=1;
}
else{
dp[i][j][k]=dp[i-1][j][k];
if(j>i)
dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-i][k])%MOD;
if(i==j)
dp[i][j][k]=(dp[i][j][k]+1)%MOD;
}
scanf("%d",&T);
while(T--){
scanf("%d%d",&A,&B);
i=A;
for(k=0;i;i>>=1,k++);
for(i=0,t=1;i<k+1;i++,t<<=1);
dp3[0]=(A+1)%MOD;
l=1;
for(i=f=1,j=2;i<=k && i<=B;i++,j<<=1,l=i)
if(j+A<t)
dp3[i]=(j+A+1)%MOD;
else{
dp3[i]=t%MOD;
f=0;
l=i+1;
break;
}
if(f){
f=((j>>1)&0x7fffffff);
for(i=1,j=2;i<=k-1 && i+k<=B;i++,j<<=1,l=i+k)
if(j+f+A<t)
dp3[i+k]=(j+f+A+1)%MOD;
else{
dp3[i+k]=t%MOD;
l=i+k+1;
break;
}
}
for(;l<1001;l++)
dp3[l]=dp3[l-1];
for(i=k+1,t=dp3[1000];i<=B;i++)
t=(t+dp[B][i][k]*dp3[B-i])%MOD;
printf("%lld\n",(t-1+MOD)%MOD);
}
return 0;
}
0 Comments