HackerRank Bricks Game Problem Solution
In this post, we will solve HackerRank Bricks Game Problem Solution. You and your friend decide to play a game using a stack consisting of N bricks. In this game, you can alternatively remove 1, 2 or 3 bricks from the top, and the numbers etched on the removed bricks are added to your score. You have to play so that you obtain the maximum possible score. It is given that your friend will also play optimally and you make the first move.
As an example, bricks are numbered arr = [1, 2, 3, 4, 5]. You can remove either [1]= 1. [1,2] = 3 or [1, 2, 3] = 6. For your friend, your moves would leave the options of 1 to 3 elements from [2, 3, 4] = 9 leaving 5 for you (total score = 6), [3, 4, 5] = 12 or [4,5] = 9. In this case, it will never be optimal for your friend to take fewer than the maximum available number of elements. Your maximum possible score is 6. achievable two ways: 1 first move and 5 the second, or [1, 2, 3] in your first move.
Function Description
Complete the bricks Game function in the editor below. It should return an integer that represents your maximum possible score.
bricksGame has the following parameter(s):
arr: an array of integers
Input Format
The first line will contain an integer t, the number of test cases,
Each of the next t pairs of lines are in the following format: The first line contains an integer n, the number of bricks in arr.
The next line contains n space-separated integers $arr[i].
Output Format
For each test case, print a single line containing your maximum score.
Sample Input
2
5
999 1 1 1 0
5
0 1 1 1 999
Sample Output
1001
999
Explanation
In first test case, you will pick 999,1,1. If you play in any other way, you will not get a score of 1001.
In second case, best option will be to pick up the first brick (with 0 score) at first. Then your friend will choose the next three blocks, and you will get the last brick.
Bricks Game C Solution
#include<stdio.h>
#define HIGH 100005
long long int dp[HIGH],a[HIGH];
int main()
{int i,t,n;
long long int min(long long int a,long long int b,long long int c);
long long int max(long long int a,long long int b,long long int c);
long long int min2(long long int a,long long int b);
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=n;i>=1;i--)
{dp[i]=0;
scanf("%lld",&a[i]);
}
dp[0]=0;
dp[1]=a[1];
dp[2]=a[1]+a[2];
dp[3]=a[1]+a[2]+a[3];
dp[4]=a[2]+a[3]+a[4];
for(i=5;i<=n;i++)
{
if(i==5)
{
dp[i]=max(a[i]+min(dp[i-2],dp[i-3],dp[i-4]),a[i]+a[i-1]+min(dp[i-3],dp[i-4],dp[i-5]),a[i]+a[i-1]+a[i-2]+min2(dp[i-4],dp[i-5]));
}
else
{
dp[i]=max(a[i]+min(dp[i-2],dp[i-3],dp[i-4]),a[i]+a[i-1]+min(dp[i-3],dp[i-4],dp[i-5]),a[i]+a[i-1]+a[i-2]+min(dp[i-4],dp[i-5],dp[i-6]));
}
}
printf("%lld\n",dp[n]);
/*
printf("%lld\n",dp[6]);
printf("%lld\n",dp[7]);
printf("%lld\n",dp[8]);
printf("%lld\n",dp[9]);
printf("%lld\n",dp[10]); */
}
return(0);
}
long long int max(long long int a,long long int b,long long int c)
{
if(a>=b&&a>=c)
return(a);
else if(b>=a&&b>=c)
return(b);
else
return(c);
}
long long int min(long long int a,long long int b,long long int c)
{
if(a<=b&&a<=c)
return(a);
else if(b<=a&&b<=c)
return(b);
else
return(c);
}
long long int min2(long long int a,long long int b)
{
if(a<=b)
return(a);
else
return(b);
}Bricks Game C++ Solution
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator> // std::istream_iterator
#include <vector> // std::vector
#include <array> // std::array
using namespace std;
typedef uint64_t value_type;
typedef uint64_t score_type;
template<class InputIt>
std::pair<score_type, score_type> max_score(InputIt first, InputIt last)
{
if (std::distance(first, last) <= 3) {
return std::make_pair<score_type, score_type>(std::accumulate<InputIt, score_type>(first, last, 0), 0);
}
auto number_of_elements = std::distance(first, last);
std::vector< std::pair<score_type, score_type> > res(number_of_elements);
res[0] = std::make_pair<score_type, score_type>(std::accumulate<InputIt, score_type>(first, first+1, 0), 0);
res[1] = std::make_pair<score_type, score_type>(std::accumulate<InputIt, score_type>(first, first+2, 0), 0);
res[2] = std::make_pair<score_type, score_type>(std::accumulate<InputIt, score_type>(first, first+3, 0), 0);
for (size_t i = 3; i < number_of_elements; ++i) {
std::pair<score_type, score_type> p1(res[i-1].second + *(first+i), res[i-1].first);
std::pair<score_type, score_type> p2(res[i-2].second + *std::next(first, i-1) + *std::next(first, i), res[i-2].first);
std::pair<score_type, score_type> p3(res[i-3].second + *std::next(first, i-2) + *std::next(first, i-1) + *std::next(first, i), res[i-3].first);
res[i] = std::max( std::max(p1, p2), p3);
}
return res[number_of_elements-1];
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
size_t number_of_test_cases;
std::cin >> number_of_test_cases;
while (number_of_test_cases--) {
int number_of_elements;
std::cin >> number_of_elements;
std::vector<value_type> bricks(number_of_elements);
std::copy_n(std::istream_iterator<value_type>(std::cin), number_of_elements, bricks.begin());
std::cout << max_score(bricks.rbegin(), bricks.rend()).first << std::endl;
}
return 0;
}Bricks Game C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
static void Main(String[] args) {
int tests = int.Parse(Console.ReadLine());
for (int q = 0; q < tests; q++)
{
int n = int.Parse(Console.ReadLine());
var parts = Console.ReadLine().Split(' ');
var a = new int[n];
for (int i = 0; i < n; i++)
a[i] = int.Parse(parts[i]);
var h = new long[n];
var s = new long[n];
for (int i = n - 1; i >= 0 && i >= n - 3; i--)
{
h[i] = a[i] + (i < n - 1 ? h[i + 1] : 0);
s[i] = a[i] + (i < n - 1 ? s[i + 1] : 0);
}
for (int i = n - 4; i >= 0; i--)
{
var h1 = a[i] + s[i + 1] - h[i + 1];
var h2 = a[i] + a[i + 1] + s[i + 2] - h[i + 2];
var h3 = a[i] + a[i + 1] + a[i + 2] + s[i + 3] - h[i + 3];
h[i] = new[] { h1, h2, h3 }.Max();
s[i] = a[i] + s[i + 1];
}
Console.WriteLine(h[0]);
}
}
}Bricks Game Java Solution
import java.io.*;
import java.util.*;
public class Solution {
static int max;
static int a[];
static long b[];
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t!=0){
t--;
int n=sc.nextInt();
a=new int[n];
b=new long[n];
int c[]=new int[n];
long dp[]=new long[n];
max=0;
long s=0;
for(int i=0;i<n;i++){
c[i]=sc.nextInt();
}
for(int i=0;i<n;i++){
a[i]=c[n-1-i];
s=s+a[i];
b[i]=s;
if(i<=2)
dp[i]=b[i];
else{
dp[i]=Math.max((a[i]+a[i-1]+a[i-2]+b[i-3]-dp[i-3]),((a[i]+a[i-1]+b[i-2]-dp[i-2])));
dp[i]=Math.max(dp[i],a[i]+b[i-1]-dp[i-1]);
}
}
System.out.println(dp[n-1]);
}
}
}Bricks Game JavaScript Solution
process.stdin.resume();
process.stdin.setEncoding('ascii');
var inputRaw = "";
var inputLines;
var inputLineIdx = 0;
process.stdin.on('data', function(data) {
inputRaw += data;
});
process.stdin.on('end', function() {
inputLines = inputRaw.split("\n");
main();
});
function readLine() {
return inputLines[inputLineIdx++];
}
/////////////// ignore above this line ////////////////////
function main() {
let t = parseInt(readLine());
for (let i = 0; i < t; i++) {
let n = parseInt(readLine());
let bricks = readLine().split(' ').map(Number);
bricks.reverse();
let sum = new Array(n);
sum[0] = bricks[0];
for (let j = 1; j < n; j++) {
sum[j] = sum[j - 1] + bricks[j];
}
let dp = new Array(n);
dp[0] = bricks[0];
dp[1] = bricks[0] + bricks[1];
dp[2] = bricks[0] + bricks[1] + bricks[2];
for (let j = 3; j < n; j++) {
let res1 = sum[j] - dp[j - 1];
let res2 = sum[j] - dp[j - 2];
let res3 = sum[j] - dp[j - 3];
dp[j] = Math.max(res1, res2, res3);
}
console.log(dp[n - 1]);
}
}Bricks Game Python Solution
test_count = int(input())
for test_id in range(0, test_count):
dummy = input()
values = list(reversed(list(map(int, input().split()))))
total = [0] * len(values)
target = [-1] * len(values)
for i in range(0, len(values)):
best_index = -1
max_value = -1
for j in range(1,4):
current_total = sum(values[i-j+1:i+1])
if i-j >= 0 and target[i-j] >= 0:
current_total = current_total + total[target[i-j]]
if current_total > max_value:
max_value = current_total
best_index = j
total[i] = max_value
target[i] = i - best_index
#debug
'''
int_format = '{0: >5} '
for i in range(0, len(values)):
print(int_format.format(i), end='')
print()
for i in range(0, len(values)):
print(int_format.format(values[i]), end='')
print()
for i in range(0, len(values)):
print(int_format.format(total[i]), end='')
print()
for i in range(0, len(values)):
print(int_format.format(target[i]), end='')
print()
'''
print(total[-1])
