304 North Cardinal St.
Dorchester Center, MA 02124

# Matchsticks CodeChef Solution

## Matchsticks CodeChef Solution in C++17

``````#include<bits/stdc++.h>
using namespace std;
template<typename... T>
void see(T&... args) { ((cin >> args), ...);}
template<typename... T>
void put(T&&... args) { ((cout << args << " "), ...);}
template<typename... T>
void putl(T&&... args) { ((cout << args << " "), ...); cout<<'\n';}
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {cerr << *it << "=" << a << ", "; err(++it, args...);}
// #define int long long
#define pb push_back
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define vc vector
#define L cout<<'\n';
#define E cerr<<'\n';
#define all(x) x.begin(),x.end()
#define rep(i,a,b) for (int i=a; i<b; ++i)
#define rev(i,a,b) for (int i=a; i>b; --i)
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define setpr(x) cout<<setprecision(x)<<fixed
#define sz size()
#define seea(a,x,y) for(int i=x;i<y;i++){cin>>a[i];}
#define seev(v,n) for(int i=0;i<n;i++){int x; cin>>x; v.push_back(x);}
#define sees(s,n) for(int i=0;i<n;i++){int x; cin>>x; s.insert(x);}
const ll inf = INT_MAX;
const ld ep = 0.0000001;
const ld pi = acos(-1.0);
const int M = 1e9 + 7;
const int N = 200020;
const ll modi = 500000004;
int spf[N];
ll Log2[N];
int main(){
IOS
Log2[1] = 0;
rep(i,2,N){
Log2[i] = Log2[i/2] + 1;
}
ll n,q;
see(n);
ll a1[n];
seea(a1,0,n);
see(q);
ll mn[n][Log2[n]+1] = {0};
ll mx[n][Log2[n]+1] = {0};
rep(i,0,n) mn[i][0] = a1[i];
rep(i,0,n) mx[i][0] = a1[i];
rep(j,1,Log2[n]+1){
rep(i,0,n - (1<<j) + 1){
mn[i][j] = min(mn[i][j-1],mn[i + (1<<(j-1))][j-1])  ;
}
}
rep(j,1,Log2[n]+1){
rep(i,0,n - (1<<j) + 1){
mx[i][j] = max(mx[i][j-1],mx[i + (1<<(j-1))][j-1]);
}
}
int cnt = 0;
while(q--){
int a,b;
see(a,b);
int k = b - a + 1;
k = Log2[k];
double mx1,mx2 = 0,mx3 = 0,mx4;
mx1 = max(mx[a][k],mx[b-(1<<k) + 1][k]);
ll mn1 = min(mn[a][k],mn[b-(1<<k) + 1][k]);
if(a!=0){
k = Log2[a];
mx2 = max(mx[0][k],mx[a - (1<<k) ][k]);
}
if(b!=n-1){
k = Log2[n - b - 1];
mx3 = max(mx[b+1][k],mx[n - (1<<k)][k]);
}
mx4 = max(mx3,mx2);
double time = max((mx1+mn1)/2,mx4 + mn1);
setpr(1)<<time<<endl;
}

}``````

## Matchsticks CodeChef Solution in C++14

``````#include <bits/stdc++.h>
#define ll long long
#define llinf LLONG_MAX
#define llminf LLONG_MIN
#define inf INT_MAX
#define minf INT_MIN
const long long mod = 1e9 + 7;

using namespace std;

int tree[2*100005];
int tmx[2*100005];

vector <int> v;

int n = 0;

void buildmin() {
for (int i = 0;i<n;i++) {
tree[i+n]=v[i];
}
for (int i = n-1;i>0;i--) {
tree[i]=min(tree[2*i],tree[2*i+1]);
}
}

int qmin(int l, int r) {
l+=n; r+=n;
int ans = inf;
while (l<=r) {
if (l%2==1) {
ans=min(ans,tree[l++]);
}
if (r%2==0) {
ans=min(ans,tree[r--]);
}
r/=2; l/=2;
}
return ans;
}

void buildmax() {
for (int i = 0;i<n;i++) {
tmx[n+i]=v[i];
}
for (int i = n-1;i>0;i--) {
tmx[i]=max(tmx[2*i],tmx[2*i+1]);
}
}

int qmax(int l, int r) {
l+=n; r+=n;
int ans = 0;
while (l<=r) {
if (l%2==1) {
ans=max(ans,tmx[l++]);
}
if (r%2==0) {
ans=max(ans,tmx[r--]);
}
r/=2; l/=2;
}
return ans;
}

int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cout << setprecision(1) << fixed;
cin >> n;
v.resize(n,0);
for (int i = 0;i<n;i++) {
cin >> v[i];
}
buildmax();
buildmin();
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
int mn = qmin(l,r);
int mx = qmax(l,r);
int ot;
if (l==0 and r==n-1) ot=0;
else if (l==0) {
ot=qmax(r+1,n-1);
}
else if (r==n-1) {
ot=qmax(0,l-1);
}
else {
ot=max(qmax(0,l-1),qmax(r+1,n-1));
}
double ans = max((double)ot,(double)(mx-mn)/2) + mn;
cout << ans << "\n";
}
}``````

## Matchsticks CodeChef Solution in PYTH 3

``````# cook your dish here
import math
n = int(input())
arr=[int(x) for x in input().split()]
k = int(math.log2(n))

#max table
sp = [[0 for i in range(k+1)] for j in range(n)]

for j in range(k+1):
i=0
while i+(1<<j)-1<n:
if j==0:
sp[i][j]=arr[i]
else:
sp[i][j] = max(sp[i][j-1],sp[i+(1<<(j-1))][j-1])
i+=1

#min table
sp1 = [[0 for i in range(k+1)] for j in range(n)]

for j in range(k+1):
i=0
while i+(1<<j)-1<n:
if j==0:
sp1[i][j]=arr[i]
else:
sp1[i][j] = min(sp1[i][j-1],sp1[i+(1<<(j-1))][j-1])
i+=1

def query1(l,r):
k = r-l+1
msb = int(math.log2(k))
return max(sp[l][msb],sp[r-(1<<msb)+1][msb])

def query(l,r):
k = r-l+1
msb = int(math.log2(k))
ans = min(sp1[l][msb],sp1[r-(1<<msb)+1][msb])
m = ans+(query1(l,r)-ans)/2
if l-1>=0:
m = max(m,ans+query1(0,l-1))
if r+1<=n-1:
m = max(m,ans+query1(r+1,n-1))
return float(m)

q = int(input())
for i in range(q):
l,r = map(int,input().split())
print(query(l,r))``````

## Matchsticks CodeChef Solution in C

``````#include<stdio.h>
void buildtree(long int n,long int b[],long int B[])
{
long int i;
for(i=n-1;i>0;i--)
{
b[i]=b[2*i]>b[2*i+1]?b[2*i+1]:b[2*i];
B[i]=B[2*i+1]>B[2*i]?B[2*i+1]:B[2*i];
}
};
long int querymin(long int l,long int r,long int b[])
{
long int res=1000000000;
for(;l<r;l>>=1,r>>=1)
{
if(l&1)
{
res=res>b[l]?b[l]:res;
l++;
}
if(r&1)
{
r--;
res=res>b[r]?b[r]:res;
}
}
return res;
};

long int querymax(long int l,long int r,long int b[])
{
long int res=0;
for(;l<r;l>>=1,r>>=1)
{
if(l&1)
{
res=res<b[l]?b[l]:res;
l++;
}
if(r&1)
{
r--;
res=res<b[r]?b[r]:res;
}
}
return res;
};
int main()
{
long int n,q,i,l,r;
scanf("%ld",&n);
long int b[2*n],B[2*n];
for(i=n;i<2*n;i++)
{
scanf("%ld",&b[i]);
B[i]=b[i];
}
buildtree(n,b,B);
scanf("%ld",&q);
long int min,max1,max2;
long int max;
double m;
for(i=0;i<q;i++)
{
scanf("%ld %ld",&l,&r);
min=querymin(l+n,r+1+n,b);
max=querymax(l+n,r+1+n,B);
max1=querymax(n,l+n,B);
max2=querymax(r+1+n,2*n,B);
m=(max-min)/2.0;
max1=max1>max2?max1:max2;
m=m>max1?m:max1;
m=m+min;
printf("%.1lf\n",m);
}
return 0;
}
``````

## Matchsticks CodeChef Solution in JAVA

``````
import java.io.*;
import java.text.*;
import java.util.*;
import java.util.function.*;

class CodeChef {

public static void main(String[] args) throws java.lang.Exception {
NumberFormat formatter = new DecimalFormat("#0.0", DecimalFormatSymbols.getInstance(Locale.US));
SparseTableInt spiMin = new SparseTableInt(tab, Integer.MAX_VALUE, Math::min);
SparseTableInt spiMax = new SparseTableInt(tab, Integer.MIN_VALUE, Math::max);

Scan.loop(() -> {
int toCenter = spiMin.get(L, R);
int a = toCenter + spiMax.get(0, L-1);
double b = toCenter + (spiMax.get(L, R) - toCenter) / 2.0;
int c = toCenter + spiMax.get(R+1, N-1);
Out.bufln(formatter.format(Math.max(Math.max(a, b), c)));
});

Out.flush();
}
}

class Out {
private static final boolean SYSTEM_OUT = true;
private static final File OUTPUT_FILE = new File("input.txt");

private static final PrintStream stream;
private static StringBuilder sb = new StringBuilder();

static {
if (SYSTEM_OUT) stream = System.out;
else try { stream = new PrintStream(OUTPUT_FILE); }
catch (IOException ex) { throw new Error("Could not write " + OUTPUT_FILE.getAbsolutePath() + ".", ex); }
}

public static void print(Object o) { flush(); stream.print(o); }
public static void println(Object o) { flush(); stream.println(o); }
public static void buf(Object o) { sb.append(o); }
public static void bufln(Object o) { sb.append(o + "\n"); }
public static void flush() { stream.print(sb); sb = new StringBuilder(); }
}

class Scan {
private static final boolean SYSTEM_IN = true;
private static final File INPUT_FILE = new File("input.txt");

private static StringTokenizer st;

static {
catch (IOException ex) { throw new Error("Could not read " + INPUT_FILE.getAbsolutePath() + ".", ex); }
}

public static String next() {
while (st == null || !st.hasMoreElements())
try { st = new StringTokenizer(br.readLine()); }
catch (IOException ex) { throw new Error("Scan reached EOF."); }
return st.nextToken();
}

public static String nextLine() {
try { return st.hasMoreTokens() ? st.nextToken("\n") : br.readLine(); }
catch (IOException e) { throw new Error("Scan reached EOF."); }
}

public static int readInt() { return Integer.parseInt(next()); }

public static long readLong() { return Long.parseLong(next()); }

public static double readDouble() { return Double.parseDouble(next()); }

int[] res = new int[size];
for (int i = 0; i < size; i++) res[i] = readInt();
return res;
}

long[] res = new long[size];
for (int i = 0; i < size; i++) res[i] = readLong();
return res;
}

double[] res = new double[size];
for (int i = 0; i < size; i++) res[i] = readDouble();
return res;
}

public static int[] readIntArray(int size) {
int[] res = new int[size];
for (int i = 0; i < size; i++) res[i] = readInt();
return res;
}

public static long[] readLongArray(int size) {
long[] res = new long[size];
for (int i = 0; i < size; i++) res[i] = readLong();
return res;
}

public static double[] readDoubleArray(int size) {
double[] res = new double[size];
for (int i = 0; i < size; i++) res[i] = readDouble();
return res;
}

public static void loop(Runnable r) {
for (int i = 0; i < loops; i++) r.run();
}

public static void loop0(Consumer<Integer> c) {
for (int i = 0; i < loops; i++) c.accept(i);
}

public static void loop1(Consumer<Integer> c) {
for (int i = 1; i <= loops; i++) c.accept(i);
}
}

class SparseTableInt {

private int defaultValue;
private int[] tab;
private int n;
private BiFunction<Integer, Integer, Integer> func;

public SparseTableInt(int[] vals, BiFunction<Integer, Integer, Integer> f) {
this(vals, 0, f);
}

public SparseTableInt(int[] vals, int def, BiFunction<Integer, Integer, Integer> f) {
defaultValue = def;
func = f;
n = vals.length;
if (n == 0) return;
int log = log2(n) + 1;
tab = new int[n * log];
System.arraycopy(vals, 0, tab, 0, n);
int start = 0;
int prevStart = 0;
int end = 1;
for (int i = 1; i < log; i++) {
start += n;
int limit = n - end;
for (int j = 0; j < n; j++) {
tab[start + j] = j < limit ? f.apply(tab[prevStart + j], tab[prevStart + j + end]) : tab[prevStart + j];
}
prevStart += n;
end *= 2;
}
}

public int get(int a, int b) {
if (a > b) return defaultValue;
if (a == b) return tab[a];
int la = log2(b - a);
return func.apply(tab[la * n + a], tab[la * n + b + 1 - (1<<la)]);
}

private static int log2(int i) { return 31 - Integer.numberOfLeadingZeros(i); }
}``````

## Matchsticks CodeChef Solution in PYPY 3

``````import math

n=int(input())
arr=list(map(int,input().split()))

size=int(math.sqrt(n))+1

block_min=[1000000000]*size
for index in range(n):
block_min[index//size] = min(block_min[index//size ],arr[index])

block_max=[-1]*size
for index in range(n):
block_max[index//size] = max(block_max[index//size], arr[index])

def minimumFinder(l,r,size) :
index=l
while (index <= r):
if index % size == 0 and index+size-1 <= r:
index+=size
else:
index+=1

def maximumFinder(l,r,size) :
index=l
while (index <= r):
if index % size == 0 and index+size-1 <= r:
index+=size
else:
index+=1

queries=int(input())

for _ in range (queries):
l,r=map(int,input().split())
minInRange=minimumFinder(l, r, size)
maxInRange=maximumFinder(l, r, size)
maxOutLeft =0
maxOutRight=0
if ((l-1)>= 0):
maxOutLeft=maximumFinder(0,l-1, size)
if ((r+1)<n):
maxOutRight=maximumFinder(r+1, n-1, size)
maxOutRange = max (maxOutRight,maxOutLeft)
# print(maxOutRange,maxInRange,minInRange,maxOutRight,maxOutLeft)
ans=minInRange+max(maxOutRange,(maxInRange-minInRange)/2)
print(float (ans))``````

## Matchsticks CodeChef Solution in PYTH

``````def buildS(sp,L,R):
if L == R:
Stree[sp] = A[L]
else:
m = (L+R)/2
buildS(2*sp+1,L,m)
buildS(2*sp+2,m+1,R)
Stree[sp] = min(Stree[2*sp+1],Stree[2*sp+2])
# endif
# end fun
def buildB(sp,L,R):
if L == R:
Btree[sp] = A[L]
else:
m = (L+R)/2
buildB(2*sp+1,L,m)
buildB(2*sp+2,m+1,R)
Btree[sp] = max(Btree[2*sp+1],Btree[2*sp+2])
# endif
# end fun
def getmin(sp,sl,sr,L,R):
if (sl > R) or (sr < L) :
res = 10**9
else:
if  (L <= sl) and (sr <= R):
res = Stree[sp]
else:
m = (sl+sr)/2
res = min(getmin(2*sp+1,sl,m,L,R),getmin(2*sp+2,m+1,sr,L,R))
# endif
# endif
return res
# end fun
def getmax(sp,sl,sr,L,R):
if (sl > R) or (sr < L) :
res = 0
else:
if  (L <= sl) and (sr <= R):
res = Btree[sp]
else:
m = (sl+sr)/2
res = max(getmax(2*sp+1,sl,m,L,R),getmax(2*sp+2,m+1,sr,L,R))
# endif
# endif
return res
# end fun
N = int(raw_input())
size = 1
while size < N:
size = size*2
# endwhile
size = size*2
Stree = [0 for x in range(size)]
Btree = [0 for x in range(size)]
st = raw_input().split()
A = []
for x in st:
A.append(int(x))
# endfor x
buildS(0,0,N-1)
buildB(0,0,N-1)
Q = int(raw_input())
for k in range(Q):
st = raw_input().split()
L = int(st[0])
R = int(st[1])
mi = getmin(0,0,N-1,L,R)
mx = getmax(0,0,N-1,L,R)
mxL = 0
mxR = 0
if L > 0:
mxL = getmax(0,0,N-1,0,L-1)
# endif
if R < N-1:
mxR = getmax(0,0,N-1,R+1,N-1)
# endif
mLR = max(mxL,mxR)
r = max(mi+mx,2*(mi+mLR))
r = 1.0*r/2
print r
# endfor k
``````

## Matchsticks CodeChef Solution in C#

``````using System;
using System.Collections.Specialized;
using System.Linq;
using System.Runtime.CompilerServices;
using Console = System.Console;

namespace CodeForces
{
class Program
{
private static int[] tmax, tmin;

static void build(int k, int l, int r, int[] matchsticks)
{
if (r - l == 1)
{
tmax[k] = tmin[k] = matchsticks[l];
return;
}

int m = (l + r) / 2;
int k1 = k * 2 + 1;
int k2 = k * 2 + 2;
build(k1, l, m, matchsticks);
build(k2, m, r, matchsticks);
tmax[k] = Math.Max(tmax[k1], tmax[k2]);
tmin[k] = Math.Min(tmin[k1], tmin[k2]);
}

static int query(int k, int l, int r, int ql, int qr, bool max)
{
if (qr <= l || r <= ql)
{
return max ? 0 : Int32.MaxValue;
}

if (ql <= l && r <= qr)
{
return max ? tmax[k] : tmin[k];
}

int m = (l + r) / 2;
int k1 = k * 2 + 1;
int k2 = k * 2 + 2;
int t1 = query(k1, l, m, ql, qr, max);
int t2 = query(k2, m, r, ql, qr, max);
return max ? Math.Max(t1, t2) : Math.Min(t1, t2);
}

static void Main(string[] args)
{
int n = Int32.Parse(testCasesString);
string[] matchstickLineSplit = matchstickLine.Split(' ');
int[] matchsticks = new int[n];
for (int i = 0; i < n; i++)
{
matchsticks[i] = Int32.Parse(matchstickLineSplit[i]);
}
int[] matchmod = new int[n];
matchmod[0] = matchsticks[0];
for (int i = 1; i < n; i++)
{
matchmod[i] = Math.Max(matchsticks[i], matchmod[i - 1]);
}
int[] matchmod2 = new int[n];
matchmod2[n - 1] = matchsticks[n - 1];
for (int i = n - 2; i >= 0; i--)
{
matchmod2[i] = Math.Max(matchsticks[i], matchmod2[i + 1]);
}
int nmod = 1;
while (nmod < n)
{
nmod = nmod * 2;
}

tmax = new int[nmod * 2];
tmin = new int[nmod * 2];
build(0, 0, n, matchsticks);
int queryCount = Int32.Parse(queryCasesString);
while (queryCount-- > 0)
{
string[] queryLineSplit = queryLine.Split(' ');
int l = Int32.Parse(queryLineSplit[0]);
int r = Int32.Parse(queryLineSplit[1]) + 1;
int tp = l > 0 ? matchmod[l - 1] : 0;
int tq = r < n ? matchmod2[r] : 0;
int t1 = query(0, 0, n, l, r, false);
int t2 = query(0, 0, n, l, r, true);
double answer = t1 + Math.Max(Math.Max(tp, tq), (t2 - t1) / 2.0);
string result = string.Format("{0:0.0}", Math.Truncate(answer * 10) / 10);
Console.WriteLine(result);
}
}
}
}

``````

## Matchsticks CodeChef Solution in GO

``````package main

import (
"bufio"
"bytes"
"fmt"
"math"
"os"
)

func main() {

Q := make([][]int, m)
for i := 0; i < m; i++ {
}
res := solve(n, B, Q)

var buf bytes.Buffer

for i := 0; i < m; i++ {
buf.WriteString(fmt.Sprintf("%.1f\n", res[i]))
}

fmt.Print(buf.String())
}

func readUint64(bytes []byte, from int, val *uint64) int {
i := from

var tmp uint64
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp

return i
}

func readInt(bytes []byte, from int, val *int) int {
i := from
sign := 1
if bytes[i] == '-' {
sign = -1
i++
}
tmp := 0
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}

for i := 0; i < len(s); i++ {
if s[i] == '\n' {
return s[:i]
}
}
return s
}

return
}

a, b = res[0], res[1]
return
}

a, b, c = res[0], res[1], res[2]
return
}

res := make([]int, n)
x := 0
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
}
return res
}

const INF = 1 << 30

func solve(n int, B []int, Q [][]int) []float64 {

set := func(arr []int, p int, v int, fn func(int, int) int) {
p += n
arr[p] = v
for p > 1 {
arr[p>>1] = fn(arr[p], arr[p^1])
p >>= 1
}
}

get := func(arr []int, l, r int, init_res int, fn func(int, int) int) int {
res := init_res
l += n
r += n
for l < r {
if l&1 == 1 {
res = fn(res, arr[l])
l++
}
if r&1 == 1 {
r--
res = fn(res, arr[r])
}
l >>= 1
r >>= 1
}
return res
}

dp := make([]int, 2*n)
fp := make([]int, 2*n)

for i := 0; i < 2*n; i++ {
dp[i] = INF
fp[i] = -INF
}

for i := 0; i < n; i++ {
set(dp, i, B[i], min)
set(fp, i, B[i], max)
}

res := make([]float64, len(Q))

for i, cur := range Q {
l, r := cur[0], cur[1]
x := get(dp, l, r+1, INF, min)
// first match stick burns outs
var ans float64
if l > 0 {
ans = float64(get(fp, 0, l, 0, max)) + float64(x)
}
if r+1 < n {
ans = math.Max(ans, float64(get(fp, r+1, n, 0, max)+x))
}
y := get(fp, l, r+1, 0, max)
ans = math.Max(ans, float64(y-x)/2+float64(x))
res[i] = ans
}
return res
}

func min(a, b int) int {
if a <= b {
return a
}
return b
}

func max(a, b int) int {
if a >= b {
return a
}
return b
}``````
##### Matchsticks CodeChef Solution Review:

In our experience, we suggest you solve this Matchsticks CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Matchsticks CodeChef Solution.

Find on CodeChef

##### Conclusion:

I hope this Matchsticks CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!