QM8B editorial

editorial
,
1

PROBLEM LINK:

Practice

Contest

Author: Chandan Boruah

Tester: Chandan Boruah

Editorialist: Chandan Boruah

DIFFICULTY:

EASY

PREREQUISITES:

Simple Math, Brute Force.

PROBLEM:

Given natural numbers from 1 to n, find the average of each 2 contiguous numbers ending up with another list of natural numbers. Find the average of 2 contigous numbers ending up with another list. Continue doing this till 1 number is left, print that number.

QUICK EXPLANATION:

Use a linked list to store the new list and continue building new list everytime until 1 number is left.

EXPLANATION:

Find average of 1 and 2 and store in a temporary linked list. Find average of 3 and 4 and store in that same linked list. Do this till the number n is reached. Update the original linked list to this new one and work on it to update the temporary linked list, until one number is left.

AUTHOR’S SOLUTION IN C#:

using System;
using System.Collections.Generic;
class some
{
	public static void Main()
	{
		int n=int.Parse(Console.ReadLine());
		while((n--)>0)
		{
			int p=int.Parse(Console.ReadLine());
			List<int>ll=new List<int>();
			for(int i=1;i<=p;i++)ll.Add(i);
			while(ll.Count>1)
			{
				List<int>temp=new List<int>();
				for(int i=0;i<ll.Count-1;i+=2)
				{
					temp.Add((ll[i]+ll[i+1])/2);
				}
				ll=new List<int>(temp.ToArray());
			}
			Console.WriteLine(ll[0]);
		}
	}
}