Kisses & Hugs

Princess Artapoelc greeted her guests by either kissing on the cheek (K) or hugging (H). From the first guest she kisses, she has a compulsion to necessarily kiss every alternate guest from that first kissed guest. That is if the guests are G1, G2, …, Gi, Gi+1, …, Gn and if she first kissed Gi then she must necessarily kiss Gi+2, Gi+4, Gi+6 … till the last possible guest. Your task is to determine in how many ways she can greet N guests.

Input
======
First line of the input contains T (T <= 1000) denoting the number of test cases.
T lines follow each containing a single integer N (1 <= N <= 10^9) denoting the number of guests.

Output
=======
For each case the output should be a single integer representing the number of ways Artapoelc can greet N guests. As the answer can be large print it modulo 1000000007.

Example

Input
3
1
2
3

Output
2
4
6

Explanation:
In the first case the possible ways are
K, H

Second case:
KH, HK, HH, KK

Third case:
HHH, HHK, HKH, HKK, KHK, KKK

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            int stringLength = 5;
            int counter = 0;
            Console.WriteLine("String length = " + stringLength);
            string num = "";
            for (int i = 0; i < stringLength; i++)             
            {                 
                num = num + "1";             
            }             
            for (int i = Convert.ToInt32(num, 2); ; i++)             
            {                 
                int columnNumber = i;                 
                char[] alphabets = { 'K', 'H' };                 
                string columnHeader = "";                 
                if (columnNumber > 0)
                {
                    while (columnNumber > 0)
                    {
                        columnHeader = columnHeader + alphabets[columnNumber % alphabets.Length].ToString();
                        if (columnNumber % alphabets.Length == 0)
                        {
                            columnNumber--;
                        }
                        columnNumber = columnNumber / alphabets.Length;
                    }
                }

                if (columnHeader.Length > stringLength)
                {
                    break;
                }
                else
                {
                    //Check for alternate K positions
                    if (Reverse(columnHeader).Length > 2)
                    {
                        if (CheckAlternateOccurrence(Reverse(columnHeader), 'K'))
                        {
                            Console.WriteLine(i + " - " + Reverse(columnHeader));
                            counter++;
                        }
                    }
                    else
                    {
                        Console.WriteLine(i + " - " + Reverse(columnHeader));
                        counter++;
                    }
                }
            }
            Console.WriteLine("Total number of combinations = " + counter);
        }

        public static string Reverse(string text)
        {
            if (text == null) return null;
            char[] array = text.ToCharArray();
            Array.Reverse(array);
            return new string(array);
        }

        public static bool CheckAlternateOccurrence(string text, char ch)
        {
            int startPos = -1;
            for (int i = 0; i < text.Length; i++)
            {
                if (text[i] == ch)
                {
                    startPos = i;
                    break;
                }
            }
            if (startPos != -1)
            {
                for (int i = startPos; i < text.Length; i = i + 2)
                {
                    if (text[i] != ch)
                    {
                        return false;
                    }
                }
            }
            return true;
        }
    }
}

Output
=======
String length = 5
31 - HHHHH
32 - HHHHK
33 - HHHKH
34 - HHHKK
36 - HHKHK
38 - HHKKK
41 - HKHKH
42 - HKHKK
45 - HKKKH
46 - HKKKK
52 - KHKHK
54 - KHKKK
60 - KKKHK
62 - KKKKK
Total number of combinations = 14
Press any key to continue . . .
Advertisements
This entry was posted in Information Technology. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s