Divide and conquer CodeChef Solution

Problem -Divide and conquer CodeChef Solution

“ ”

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

Divide and conquer CodeChef Solution in C++14

“ ”

#include <stdio.h>
#include <math.h>
double vals[5001];
int numbering[5001];
int main() 
{
	int ans,valc,bot,number,top;
	double scale,temp; 
	double sum,next,logscale,log2;
	int i;
	scanf("%lf",&scale);
	temp = 0.00000001;
	scale-=temp;
	logscale = log(scale);
	log2 = log(2);
	ans = (int)(logscale/(log2 - logscale))+1;
	valc = 2;
	vals[0] = 1;
	vals[1] = 1;
	sum = 2;
	for (i=2; i<2*ans; i+=2) 
	{
		next = 2/scale*vals[i-1];
		vals[i] = next;
		vals[i+1] = next;
		sum = sum + 2*next;
		valc = valc + 2;
	}
	for (i=0; i<valc; i++) 
	{
		vals[i] = vals[i]/sum;
	}
	bot = 0;
	top = valc;
	while (top-bot>1)
	{
		vals[top++] = vals[bot] + vals[bot+1];
		bot+=2;
	}
	numbering[top-1]=0;
	printf("%d\n",valc);
	number = 1;
	for (i=0; i<valc-1; i++) 
	{
		printf("%d %.15f\n",numbering[top-1],vals[bot-2]);
		numbering[bot-1]=numbering[top-1];
		numbering[bot-2]=number++;
		bot-=2;
		top--;
	}
	return 0;
}   

Divide and conquer CodeChef Solution in C

“ ”

#include <stdio.h>
#include <math.h>
double val[5001];
int numbering[5001];
int main() 
{
 int ans,valc,bot,number,top;
 double scale,temp; 
 double sum,next,logscale,log2;
 int i;
 scanf("%lf",&scale);
 temp = 0.00000001;
 scale-=temp;
 logscale = log(scale);
 log2 = log(2);
 ans = (int)(logscale/(log2 - logscale))+1;
 valc = 2;
 val[0] = 1;
 val[1] = 1;
 sum = 2;
 for (i=2; i<2*ans; i+=2) 
 {
  next = 2/scale*val[i-1];
  val[i] = next;
  val[i+1] = next;
  sum = sum + 2*next;
  valc = valc + 2;
 }
 for (i=0; i<valc; i++) 
 {
  val[i] = val[i]/sum;
 }
 bot = 0;
 top = valc;
 while (top-bot>1)
 {
  val[top++] = val[bot] + val[bot+1];
  bot+=2;
 }
 numbering[top-1]=0;
 printf("%d\n",valc);
 number = 1;
 for (i=0; i<valc-1; i++) 
 {
  printf("%d %.15f\n",numbering[top-1],val[bot-2]);
  numbering[bot-1]=numbering[top-1];
  numbering[bot-2]=number++;
  bot-=2;
  top--;
 } 
 return 0;
}

Divide and conquer CodeChef Solution in JAVA

“ ”

import java.util.*;
import java.io.*;
import java.math.*;

class Main
{
	public static void main(String ... bobby) throws Exception
	{
		BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
		double r = Double.parseDouble(input.readLine());
		
		int n = (int)(Math.log(r) / Math.log(2 / r));
		int numCuts = 2 * n + 1;
		
		double sum = 0.0;
		for (int i = 0; i <= n; i++)
			sum += Math.pow(2, (double)i / (n + 1));
		double mag = .5 / sum;
		
		PriorityQueue<Double> q = new PriorityQueue<Double>();
		for (int i = 0; i <= n; i++)
		{
			double val = Math.pow(2, (double)i / (n + 1)) * mag;
			q.add(val);
			q.add(val);
		}
		
		double[] cuts = new double[numCuts];
		for (int i = 0; i < numCuts; i++)
		{
			double x = q.poll();
			double y = q.poll();
			q.add(x + y);
			cuts[numCuts - 1 - i] = x;
		}
		
		PriorityQueue<Loaf> q2 = new PriorityQueue<Loaf>(16, new Comparator<Loaf>()
		{
			public int compare(Loaf x, Loaf y)
			{
				if (x.size > y.size)
					return -1;
				else if (x.size < y.size)
					return 1;
				else
					return 0;
			}
		});
		q2.add(new Loaf(0, 1.0));
		int index = 1;
		
		System.out.println(numCuts + 1);
		for (int i = 0; i < numCuts; i++)
		{
			Loaf max = q2.poll();
			q2.add(new Loaf(index++, cuts[i]));
			q2.add(new Loaf(max.index, max.size - cuts[i]));
			System.out.println(max.index + " " + new BigDecimal(cuts[i]));
		}
	}
	
	static class Loaf
	{
		int index;
		double size;
		
		Loaf(int index, double size)
		{
			this.index = index;
			this.size = size;
		}
	}
}

Divide and conquer CodeChef Solution in PYTH

“ ”

import sys
from math import log

k = float(sys.stdin.readline())
answer = int(log(2.0, 2.0/k))
print 2*answer

m = 2 ** (1.0/answer)
# m = 2.0/k
thesum = 0
for i in xrange(answer):
    thesum += m**i
# print [m**i/thesum for i in xrange(answer)]
loaves = [1]

def maxIndex(list):
    max = -1
    mi = -1
    for i, x in enumerate(list):
        if x > max:
            max = x
            mi = i
    return mi

desired = [m**i/thesum for i in xrange(answer)]
desired.reverse()
# print desired
cuts = []
while len(desired) > 1:
    cuts.append(desired[-1])
    lastsum = desired[-1] + desired[-2]
    del desired[-2:]
    desired[0:0] = [lastsum]

# print cuts

while cuts:
    length = cuts.pop()
    i = maxIndex(loaves)
    print i, length
    loaves[i] -= length
    loaves.append(length)
    # print loaves

# print loaves
for i in xrange(answer):
    i = maxIndex(loaves[:answer])
    x = loaves[i]/2.0
    print i, x
    loaves.append(x)
    loaves[i] -= x
# print loaves

Divide and conquer CodeChef Solution in C#

“ ”

using System;
using System.Collections;
class Tree {
	public Tree(double val) {
		v = val;
	}
	public Tree left, right;
	public double v, idx;
	public int print(int depth, ref int next, double div) {
		if (depth == 0) {
			if (left != null) left.idx = idx;
			if (right == null) return 1;
			Console.WriteLine(idx+" "+(right.v/div));
			right.idx = next++;
			return 2;
		} else {
			int ct = 0;
			if (left != null) ct += left.print(depth-1, ref next, div);
			if (right != null) ct += right.print(depth-1, ref next, div);
			return ct;
		}
	}
}
class Program {
	static void Main(string[] args) {
		double d = Double.Parse(Console.ReadLine());
		if (d > 1.0) d -= 1e-6;
		ArrayList set = new ArrayList();

		double mx = 2.0*d;
		double c = 1.0;
		while (c*2 <= mx) {
			set.Add(new Tree(c));
			set.Add(new Tree(c));
			c = c*2/d;
		}
//		Console.WriteLine("set.Count = "+set.Count);
		Console.WriteLine(set.Count);
//		string spc = "";
		while (set.Count > 1) {
			ArrayList sset = new ArrayList();
			if ((set.Count&1) > 0) {
				Tree v = (Tree)set[set.Count-1];
//				Console.WriteLine(spc+"{0,0:F3}       -> {1,0:F3}", v.v, v.v);
				sset.Add(v);
			}
			for (int i = 0; i+1 < set.Count; i += 2) {
				Tree a = (Tree)set[i], b = (Tree)set[i+1];
//				Console.WriteLine(spc+"{0,0:F3} {1,0:F3} -> {2,0:F3}", a.v, b.v, t.v);
				Tree t = new Tree(a.v+b.v);
				t.left = b;
				t.right = a;
				sset.Add(t);
			}
			set = sset;
//			spc = spc+"  ";
		}
		Tree root = (Tree)set[0];
		root.idx = 0;
		int depth = 0, ct = 1, next = 1;
		while (ct > 0) {
			ct = root.print(depth, ref next, root.v);
			depth++;
		}
	}
}

Divide and conquer CodeChef Solution Review:

In our experience, we suggest you solve this Divide and conquer 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 Divide and conquer CodeChef Solution.

Find on CodeChef

“ ”

Conclusion:

I hope this Divide and conquer 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!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn