Algorithm

problem link- https://www.spoj.com/problems/MINCOUNT/

MINCOUNT - Move To Invert

no tags 

 

A triangle made of coins of height h is as follows
It has h coins at the base and h-1 coins one level above base and so on.(Coins are placed as shown in the figure below)
And at the top most level there will be only one coin
Now given h the task is to invert this triangle by moving minimum number of coins. For example when h=4 triangle is
Invert
For h=4 at least 3 coins must be moved to invert it.

Input

In the first line N will be given and then N lines follow with each line having a integer which is the height of triangle in that test case.00≤h<1010;

Output

For each test case output in a seperate line the minimum number of moves required to invert the triangle. Output fits in long long data type

Example

Inputt:
1
3

Output:
2

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>
#include <list>

using namespace std;

int main(){
	int t=0;
	scanf("%d",&t);
	while(t--){
		unsigned long long height;
		scanf("%llu",&height);
		if(height==0){
			printf("0\n");
			continue;
		}/*
		if(height==1){
			printf("0\n");
			continue;
		}
		if(height==2){
			printf("1\n");
			continue;
		}*/
		unsigned long long int ans=0;
		height-=1;
		long long num=height/3;
		ans+=((num)*(num+1)/2)*3;
		ans+=(num+1)*(height%3);
		printf("%llu\n",ans);
	}
	return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
1
3

Output

x
–
+
cmd
2

#2 Code Example with Java Programming

Code - Java Programming

// Java program to count inversions 
// in an array
class Test 
{
    static int arr[] =
           new int[] {1, 20, 6, 4, 5};
  
    static int getInvCount(int n)
    {
        int inv_count = 0;
        for (int i = 0; i < n - 1; i++)
            for (int j = i + 1; j < n; j++)
                if (arr[i] > arr[j])
                    inv_count++;
  
        return inv_count;
    }
  
    // Driver code
    public static void main(String[] args)
    {
        System.out.println("Number of inversions are " + 
                            getInvCount(arr.length));
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
1
3

Output

x
–
+
cmd
2
Advertisements

Demonstration

SPOJ Solution-MINCOUNT Move To Invert-Solution in C, C++, Java, Python,SPOJ Solution

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python