Header Ads Widget

Matchsticks | codechef solution

Rajnish Tripathi 10:43

Problem

Chef Ceil has some matchsticks in his kitchen.

Detail of matchsticks:

There are � matchsticks in total. They are numbered from to 0 to �−1 inclusive. The ��ℎ matchstick takes �� time to burn when lighted at one end, and it burns at a uniform rate.

If lighted at both ends simultaneously, the matchstick will take only half of the original time to burn down.

Arrangement:

He ties rear end of the all the matchsticks together at one point and the front end is kept free. The matchstick numbered � is adjacent to matchstick numbered �+1 for all 0≤�≤�−2.

Bodies of matchsticks do not touch each other, except at the rear end.

Task:

There are � queries, in each query we ask: If he lights the free end of all matchsticks numbered between � and � inclusive, what will be the time needed for all matchsticks to get completely burnt?

Input

  • First line of input contains a single integer �.
  • The next line contains � space separated integers, the ��ℎ of which is ��
  • The next line contains a single integer �
  • The next � lines each contain two space separated integers - � and �. The ��ℎ line represents the ��ℎ query.

Output

For each query, print the answer on a new line.

Constraints:

  • 1≤�≤105
  • 1≤��≤108
  • 1≤�≤105
  • 0≤�≤�≤�−1

Sample 1:

Input
Output
1
5
1
0 0
5.0

Sample 2:

Input
Output
2
3 5
1
0 1
4.0

Sample 3:

Input
Output
18
3 4 2 1 5 7 9 7 10 5 12 3 1 1 2 1 3 2
1
4 10
9.0

Explanation:

Test Case 3: , in the figure above, yellow colored matches are lighted by a lighter simultaneously.

The numbers indicate the time required to burn that matchstick (if lighted at one end).

Now the first lighted matchstick will completely burn in 5 seconds. Then it will light up all the rest matches from the rear end.

Some matches will have fire at both ends and thus after 5 seconds, they will start burning with twice the original rate.

Thus time taken for matches to burn completely will be : (from left to right): 8.0, 9.0, 7.0, 6.0, 5.0, 6.0, 7.0, 6.0, 7.5, 5.0, 8.5, 8.0, 6.0, 6.0, 7.0, 6.0, 8.0, 7.0. So, the answer will be 9.0 (the maximum among these).

 Code(C++):-

#include <bits/stdc++.h>
#define ll long long
#define inf INT_MAX


using namespace std;

int t[2*100005];
int t2[2*100005];

vector <int> a;

int n = 0;

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

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

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

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

Code(JAVA):-
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

class Codeforces {
static Scanner f = new Scanner(System.in);
static PrintWriter out = new PrintWriter(System.out);
// static int mod = 1000_000_007;
static int mod = 998244353;
static final int MAX = Integer.MAX_VALUE;
static final int MIN = Integer.MIN_VALUE;
static int N = 100005;
static boolean[] isPrime = new boolean[N + 1];
static int parent[] = new int[500001];

static int K = 20;
static int lg[];
static int mn[][];
static int mx[][];


public static void main(String[] args) {

int t;
t = 1;
// t = f.nextInt();
while (t-- > 0) {
solve();
}

}

public static void solve() {

int n = f.nextInt();
int a[] = new int[n];
for (int i = 0; i < n; i++) {
a[i] = f.nextInt();
}

// K = (int) (Math.log(n) / Math.log(2));
mn = new int[N][K + 1];
mx = new int[N][K + 1];
lg = new int[N + 1];
preprocess(a);
int q = f.nextInt();
for (int i = 0; i < q; i++) {
int l = f.nextInt();
int r = f.nextInt();
double min = (double)minQ(l, r);
double max = (double)maxQ(l, r);
double ans = (double)(min + (max - min)/2);
ans = Math.max(ans, min + Math.max(maxQ(0, l - 1), maxQ(r + 1, n - 1)));
// System.out.println(ans);
System.out.println(String.format("%.1f", ans));

}
System.out.println();
// 5 7 9 7 10 5 12



out.flush();
}

static void preprocess(int arr[]) {

for (int i = 2; i <= N; i++) {
lg[i] = lg[i / 2] + 1;
}

for (int i = 0; i < arr.length; i++) {
mx[i][0] = mn[i][0] = arr[i];
}

for (int j = 1; j <= K; j++) {
for (int i = 0; i + (1 << j) <= N; i++) {
mx[i][j] = Math.max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]); // range sum
mn[i][j] = Math.min(mn[i][j - 1] , mn[i + (1 << (j - 1))][j - 1]); // range sum
}
}
}

static int minQ(int l, int r) {
if (l == r)
return mn[l][0];
if (l > r)
return 0;
int x = lg[r - l + 1];
return Math.min(mn[l][x], mn[r - (1<< x) + 1][x]);
}

static int maxQ(int l, int r) {
if(l == r)
return mx[l][0];
if (l > r)
return 0;
int x = lg[r - l + 1];
return Math.max(mx[l][x], mx[r - (1 << x) + 1][x]);
}
// =========== DSU : Start
static int find(int u) {
if (parent[u] == u) {
return u;
}
return parent[u] = find(parent[u]);
}

static void union(int u, int v) {
u = find(u);
v = find(v);
parent[u] = v;
}
// =========== DSU : End



static boolean isPrime(long n) {
if (n <= 1)
return false;

else if (n == 2)
return true;

else if (n % 2 == 0)
return false;

for (long i = 3; i <= Math.sqrt(n); i += 2) {
if (n % i == 0)
return false;
}
return true;
}

static Set<Long> generatePrimes() {

Arrays.fill(isPrime, true);

isPrime[0] = isPrime[1] = false;

for (int i = 2; i <= N; i++) {
if (isPrime[i]) {
for (int j = 2 * i; j <= N; j += i) {
isPrime[j] = false;
}
}
}
Set<Long> set = new HashSet<>();
for (int i = 2; i < N; i++) {
if (isPrime[i]) {
set.add((long) i);
}
}
return set;
}

public static Set<Long> primeFactors(long n) {
Set<Long> set = new HashSet<>();
while (n % 2 == 0) {
set.add(2l);
n /= 2;
}

for (long i = 3; i <= Math.sqrt(n); i += 2) {
while (n % i == 0) {
set.add(i);
n /= i;
}
}

if (n > 2) {
set.add(n);
}
return set;

}

static int highestPowerof2(int n) {

int p = (int) (Math.log(n) /
Math.log(2));
return (int) Math.pow(2, p);
}

static int sumOfSubMatrix(int mat[][], int x1, int y1, int x2, int y2) {
return (mat[x2][y2] - mat[x1 - 1][y2] - mat[x2][y1 - 1]) + mat[x1 - 1][y1 - 1];
}

static void prefixSum2D(int mat[][]) {
int n = mat.length, m = mat[0].length;
for (int i = 0; i < n; i++)
prefixSum(mat[i]);

for (int j = 0; j < m; j++) {
for (int i = 1; i < n; i++) {
mat[i][j] += mat[i - 1][j];
}
}

}

static void prefixSum(int arr[]) {
int n = arr.length;
for (int i = 1; i < n; i++)
arr[i] = arr[i - 1] + arr[i];
}

static class FastReader {

BufferedReader br;
StringTokenizer st;

public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}

String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}

int nextInt() {
return Integer.parseInt(next());
}

long nextLong() {
return Long.parseLong(next());
}

double nextDouble() {
return Double.parseDouble(next());
}

String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Tags:

Post a Comment

0 Comments