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

namespace DP
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");

            //Урал делал:
            //FiboNumbers(Convert.ToInt32(Console.ReadLine()));
            //IsNumberFibo(Convert.ToInt32(Console.ReadLine()));

            //-----------

            //Райнур делал
            ////5ая задача Снова Фибоначчи
            //var number = Convert.ToInt32(Console.ReadLine());
            //Console.WriteLine(FibonachiLastNumber(number));
            ////4ая задача Слово
            //var str = Console.ReadLine();
            //Console.WriteLine(FibonachiWord(str));

        }


        //3 и 5 задача
        public static int FibonachiLastNumber(int count)
        {
            if (count < 0) return -1;

            //1 1 2 3 5
            var a = 1;
            var b = 1;
            var c = 1;

            for (int i = 2; i <= count; i++)
            {
                c = a + b;
                a = b;
                b = c;

            }

            return c;

        }

        //задача 4 Слово
        public static string FibonachiWord(string str)
        {
            var count = str.Length;

            StringBuilder sb = new StringBuilder();

            //1 1 2 3 5
            var a = 0;
            var b = 1;
            var c = 1;


            var listOfFibonachi = new List<int>();
            for (int i = 1; i <= count; i++)
            {
                c = a + b;
                a = b;
                b = c;
                if (c > count) break;
                listOfFibonachi.Add(c);
            }

            foreach (var index in listOfFibonachi)
            {
                sb.Append(str[index-1]);
            }



            return sb.ToString();

        }

        //числа фибоначи
        public static void FiboNumbers(int index)
        {
            if (index == 0)
            {
                Console.WriteLine(0);
            }

            if (index <= 2)
            {
                Console.WriteLine(1);
            }

            if (index > 2)
            {
                List<int> listOfFiboNumbers = new List<int>();
                listOfFiboNumbers.Add(1);
                listOfFiboNumbers.Add(1);

                for (int i = 2; i < index; i++)
                {
                    listOfFiboNumbers.Add(listOfFiboNumbers[i - 2] + listOfFiboNumbers[i - 1]);
                }
                Console.WriteLine(listOfFiboNumbers[index - 1]);
            }
        }

        //Числа Фибоначчи - 2
        public static void IsNumberFibo(int number)
        {
            int lastNumber = 0;
            int place = 0;
            int a = 0, b = 1;

            while (lastNumber < number)
            {
                a = b;
                b = lastNumber;
                lastNumber = a + b;
                place++;
            }

            if (lastNumber == number)
            {
                Console.WriteLine(1);
                Console.WriteLine(place);
            }
            else Console.WriteLine(0);
        }

        //3 и 4 задача
        public static void LastFiboNumber(int index)
        {
            if (index <= 1)
            {
                Console.WriteLine(1);
            }

            if (index > 2)
            {
                List<int> listOfFiboNumbers = new List<int>();
                string lastNumber;
                listOfFiboNumbers.Add(1);
                listOfFiboNumbers.Add(1);

                for (int i = 2; i < index; i++)
                {
                    listOfFiboNumbers.Add(listOfFiboNumbers[i - 2] + listOfFiboNumbers[i - 1]);
                }

                lastNumber = listOfFiboNumbers[index - 1].ToString();

                Console.WriteLine(lastNumber[lastNumber.Length - 1]);
            }
        }

    }
}