Red John is Back
Problem Statement :
Red John has committed another murder. This time, he doesn't leave a red smiley behind. Instead he leaves a puzzle for Patrick Jane to solve. He also texts Teresa Lisbon that if Patrick is successful, he will turn himself in. The puzzle begins as follows. There is a wall of size 4xn in the victim's house. The victim has an infinite supply of bricks of size 4x1 and 1x4 in her house. There is a hidden safe which can only be opened by a particular configuration of bricks. First we must calculate the total number of ways in which the bricks can be arranged so that the entire wall is covered. The following diagram shows how bricks might be arranged to cover walls where 1 <= n <= 4: image There is one more step to the puzzle. Call the number of possible arrangements M. Patrick must calculate the number of prime numbers P in the inclusive range 0-M. As an example, assume n=3. From the diagram above, we determine that there is only one configuration that will cover the wall properly. 1 is not a prime number, so P=0. A more complex example is n = 5. The bricks can be oriented in total configurations that cover the wall. The two primes 2 and 3 are less than or equal to 3, so P =2. image Function Description Complete the redJohn function in the editor below. It should return the number of primes determined, as an integer. redJohn has the following parameter(s): n: an integer that denotes the length of the wall Input Format The first line contains the integer t, the number of test cases. Each of the next t lines contains an integer n, the length of the 4*n wall. Constraints 1 <= t <= 20 1 <= n <= 40 Output Format Print the integer P on a separate line for each test case.
Solution :
Solution in C :
In C++ :
#include <iostream>
#define FOR(i,a) for(int i = 0;i < (a);i++)
#define REP(i,a,b) for(int i = (a);i < (b);i++)
#define SZ(a) ((signed)a.size())
#define PB(a) push_back(a)
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cstdio>
using namespace std;
int l[1000001],k = 0;
bool prime[1000001] = {0};
void preprocess(){
for(long long i = 2;i < 1000001;i++){
if(!prime[i]){
l[k++] = i;
for(long long j = i*i ; j <= 1000000;j += i) prime[j] = 1;
}
}
}
void solve(){
long long arr[101];
arr[1] = 1,arr[2] = 1,arr[3] = 1,arr[4] = 2;
arr[0] = 1;
REP(i,5,41) arr[i] = (arr[i - 1] + arr[i - 4]);
int c = 0;
int v;
cin>>v;
FOR(i,k){
if(l[i] <= arr[v]) c++;
else break;
}
cout<<c<<"\n";
}
int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int t;
preprocess();
cin >> t;
FOR(i,t) solve();
return 0;
}
In Java :
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
/**
* Created with IntelliJ IDEA.
* User: Sandesh
* Date: 7/27/13
* Time: 10:47 PM
* To change this template use File | Settings | File Templates.
*/
public class Solution {
static long dp[];
static HashSet<Integer> hs;
public static void main(String arg[]){
hs=new HashSet<Integer>();
dp=new long[41];
Arrays.fill(dp,-1);
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
setPrime();
for (int j=0;j<N;j++){
int val=sc.nextInt();
int x=(int)(new Solution().get(val));
int ans=0;
for (int i=2;i<=x;i++){
if(hs.contains(i))
ans++;
}
System.out.println(ans);
}
}
public long get(int N){
if(dp[N]!=-1)
return dp[N];
long ans=1;
if(N<=3)
ans=1;
else {
ans=get(N-1)+get(N-4);
}
dp[N]=ans;
return ans;
}
static boolean isPrime(int a){
for (int i=2;i*i<=a;i++){
if(a%i==0)
return false;
}
return true;
}
static void setPrime(){
for (int i=2;i<=217286;i++){
if(isPrime(i))
hs.add(i);
}
}
}
In C :
#include<stdio.h>
#include<stdlib.h>
int sieve[300000][2];
int main()
{
int t,i,j,k,n;
int a[41],x;
a[1]=1;
a[0]=0;
a[2]=1;
a[3]=1;
a[4]=2;
for(i=5;i<=40;i++)
{
a[i]=a[i-1]+a[i-4];
}
// printf("%d\n",a[40]);
for(i=0;i<300000;i++)
{
for(j=0;j<2;j++)
sieve[i][j]=0;
}
for(i=2;i<300000;i++)
{
if(sieve[i][0]==0)
{
sieve[i][1]=sieve[i-1][1]+1;
}
else
{
sieve[i][1]=sieve[i-1][1];
continue;
}
for(j=2*i;j<300000;j=j+i)
{
sieve[j][0]=1;
}
}
scanf("%d",&t);
for(i=0;i<t;i++)
{
scanf("%d",&n);
printf("%d\n",sieve[a[n]][1]);
}
return(0);
}
In Python3 :
nbCombMem = ([],[])
def nbComb(N) :
if N in nbCombMem[0] :
return nbCombMem[1][nbCombMem[0].index(N)]
if N < 0 : return 0
c = 1
for i in range(0,N-3) :
c += nbComb(N-4-i)
nbCombMem[0].append(N)
nbCombMem[1].append(c)
return c
# return the primes (strictly) under n. Use a sieve of erathostene.
def getPrimesUnder(n) :
r = [2]
n2 = n // 2
l = list(True for i in range(0,n2))
l[0] = False
for i in range(1,n2) :
if l[i] :
r.append(2*i+1)
for m in range(2*i*(i+1),n2,2*i+1) :
l[m] = False
return r
# main
T = int(input())
Cs = [nbComb(int(input())) for t in range(0,T)]
Ps = getPrimesUnder(max(Cs)+1)
for t in range(0,T) :
c = 0
while c < len(Ps) and Ps[c] <= Cs[t] : c += 1
print(c)
View More Similar Problems
Pair Sums
Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v
View Solution →Lazy White Falcon
White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi
View Solution →Ticket to Ride
Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n - 1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if o
View Solution →Heavy Light White Falcon
Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem. You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries: "1 u x" assign x to the value of the node . "2 u v" print the maxim
View Solution →Number Game on a Tree
Andy and Lily love playing games with numbers and trees. Today they have a tree consisting of n nodes and n -1 edges. Each edge i has an integer weight, wi. Before the game starts, Andy chooses an unordered pair of distinct nodes, ( u , v ), and uses all the edge weights present on the unique path from node u to node v to construct a list of numbers. For example, in the diagram below, Andy
View Solution →Heavy Light 2 White Falcon
White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment. You are given a tree with N nodes and each node's value Vi is initially 0. Let's denote the path fr
View Solution →