216 човека участваха в най-голямото онлайн състезание по програмиране в България

На 4-ти декември 2011 година от 10:30 до 16:30 се проведе най-голямото онлайн състезание по алгоритмично програмиране правено до сега в България. В него взеха участие 216 човека. Състезанието беше в рамките на подготовката за първия изпит в Софтуерната Академия на Телерик и заради това участниците в състезанието бяха предимно студенти от Академията на Телерик. Състезателите имаха 6 часа да решат 5 задачи по програмиране от първите 6 теми на курса „Основи на програмирането със C#“ в Академията на Телерик. Състезанието се проведе онлайн в новата състезателна система BGCoder.com и на участниците беше разрешен за използване само езикът C#. Всеки може да се пробва да реши задачите като се регистрира в системата и започне да практикува онлайн състезанието. Тук можете да намерите условията на задачите, заедно с техните решения. Решенията са писани от авторите на задачите и използват само изучените от студентите теми (типове данни, оператори, изрази, работа с конзолата, условни оператори и цикли).

Problem 1 – Math Expression

You are given the following mathematical expression:

The sin(x) is a trigonometric function that returns the sine from the angle x (measured in radians).

The mod operator finds the remainder of division of one number by another.

Here are some examples for how the mod operator should work:

• 5 mod 2 = 1
• 5.99 mod 3 = 2
• 6 mod 3 = 0

Your task is to write a computer program that calculates the result from the shown mathematical expression, depending on the values of the variables N, M and P.

Input

The input data is being read from the console.

The input consists of exactly 3 lines. In each line you consequently enter the variables N, M and P.

The separator between the integer and the fractional part of the number is “.” (dot).

The number of digits that follow the decimal point will not be more than 6.

The input data will always be valid and in the format described. There is no need to check it explicitly.

Output

The output data must be printed on the console.

There must be only one line, showing the result from the mathematical expression.

The result must show exactly 6 digits after the “.” (decimal point).

Constraints

• The numbers N, M and P are fractional numbers.
• N, M and P will be between -10 000 000 and 10 000 000, inclusive.
• The numbers M and P will always have values other than 0
• It is guaranteed that none of the combinations of the numbers N, M and P will lead to dividing by zero.
• Allowed working time for your program: 0.10 seconds.
• Allowed memory: 16 MB.

Examples

Problem 1 – Solution

using System;
using System.Threading;
using System.Globalization;
namespace Problem_1_Math_Expression
{
    class Program
    {
        static void Main()
        {
            // Setting invariant culture to avoid
            // problems with floating point
            Thread.CurrentThread.CurrentCulture =
               CultureInfo.InvariantCulture;

            // Read N
            string nAsString = Console.ReadLine();
            decimal N = decimal.Parse(nAsString);

            // Read M
            string mAsString = Console.ReadLine();
            decimal M = decimal.Parse(mAsString);

            // Read P
            string pAsString = Console.ReadLine();
            decimal P = decimal.Parse(pAsString);

            // Calculating expression
            decimal result =
                (N * N + (1 / (M * P)) + 1337) /
                (N - 128.523123123M * P)
                + (decimal)Math.Sin((int)M % 180);

            // Write the result to the console
            Console.WriteLine("{0:0.000000}", result);
        }
    }
}

Problem 2 – Least Majority Multiple

Given five positive integers, their least majority multiple is the smallest positive integer that is divisible by at least three of them.

Your task is to write a program that for given distinct integers a, b, c, d and e, returns their least majority multiple.

For example if we have 1, 2, 3, 4 and 5 the majority multiple of the given five numbers is 4 because it is divisible by 1, 2, and 4.

Another example: if we have 30, 42, 70, 35 and 90 the answer will be 210, because it is divisible by 30, 42, 70, and 35 - four out of five numbers, which is a majority.

Input

The input data is being read from the console.

The input data will consist of 5 lines.

The numbers a, b, c, d and e will each be on a single line.

The input data will always be valid and in the format described. There is no need to check it explicitly.

Output

The output data must be printed on the console.

On the only output line you must print the least majority multiple of the given numbers.

Constraints

• a, b, c, d and e will each be integer numbers between 1 and 100, inclusive.
• a, b, c, d and e will be distinct.
• Allowed working time for your program: 0.25 seconds.
• Allowed memory: 16 MB.

Examples

Problem 2 – Solution

using System;
namespace Problem_2_Least_Majority_Multiple
{
    class Program
    {
        static void Main()
        {
            // Input
            int a = int.Parse(Console.ReadLine());
            int b = int.Parse(Console.ReadLine());
            int c = int.Parse(Console.ReadLine());
            int d = int.Parse(Console.ReadLine());
            int e = int.Parse(Console.ReadLine());

            // Output
            for (int i = 1; true; i++)
            {
                int count = 0;
                if (i % a == 0) count++;
                if (i % b == 0) count++;
                if (i % c == 0) count++;
                if (i % d == 0) count++;
                if (i % e == 0) count++;
                if (count >= 3)
                {
                    Console.WriteLine(i);
                    break;
                }
            }
        }
    }
}

Problem 3 – Trapezoid

Write a program that prints on the console the border of a trapezoid by given number N.

The width of the top side of the trapezoid must be exactly N.

The width of the bottom side of the trapezoid must be exactly 2 * N.

The height of the trapezoid must be exactly N + 1.

Also the top right and the bottom right angle of the trapezoid must be equal to 90 degrees.

See the examples bellow.

Input

The input data is being read from the console.

On the only line in the console you are given an integer number N, showing the width of the smallest trapezoid side.

The input data will always be valid and in the format described. There is no need to check it explicitly.

Output

The output data must be printed on the console.

You must write the border of the described trapezoid on the console.

Use the symbol “*” (asterisk) to mark the border of the trapezoid.

Use the symbol “.” (dot) to illustrate the empty spaces outside and inside the trapezoid.

Constraints

• The number N is a positive integer between 3 and 39, inclusive.
• Allowed working time for your program: 0.25 seconds.
• Allowed memory: 16 MB.

Examples

.....*****
....*....*
...*.....*
..*......*
.*.......*
**********

..........**********
.........*.........*
........*..........*
.......*...........*
......*............*
.....*.............*
....*..............*
...*...............*
..*................*
.*.................*
********************

Problem 3 – Solution

using System;
namespace Problem_3_Trapezoid
{
    class Program
    {
        static void Main()
        {
            // Read input
            string nAsString = Console.ReadLine();
            int N = int.Parse(nAsString);

            // Output first row
            for (int i = 1; i <= N; i++)
            {
                Console.Write('.');
            }
            for (int i = 1; i <= N; i++)
            {
                Console.Write('*');
            }
            Console.WriteLine();

            // Output middle rows
            for (int i = 2; i <= N; i++)
            {
                for (int j = 1; j <= N - i + 1; j++)
                {
                    Console.Write('.');
                }
                Console.Write('*');
                for (int j = 1; j <= i + N - 3; j++)
                {
                    Console.Write('.');
                }
                Console.Write('*');
                Console.WriteLine();
            }

            // Output last row
            for (int i = 1; i <= 2 * N; i++)
            {
                Console.Write('*');
            }
            Console.WriteLine();
        }
    }
}

Problem 4 – Odd Number

You are given a list of N integer numbers all but one of which appears an even number of times.

Write a program to find the one integer which appears an odd number of times.

Input

The input data is being read from the console.

The number N is written on the first input line.

On each of the following N lines there is one integer number written – the consequent number from the given list of numbers.

The input data will always be valid and in the format described. There is no need to check it explicitly.

Output

The output data must be printed on the console.

On the only output line you must print the integer from the list which appears an odd number of times.

Constraints

• N will be positive odd integer number between 1 and 99 999, inclusive.
• All of the numbers in the list will be integer numbers between -9 223 372 036 854 775 808
  and 9 223 372 036 854 775 807, inclusive.
• Always only one answer will exists and will be unambiguous.
• Allowed working time for your program: 0.25 seconds.
• Allowed memory: 16 MB.

Examples

Problem 4 – Solution

using System;
namespace Problem_4_Odd_Number
{
    class Program
    {
        static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            long result = 0;
            for (int i = 1; i <= N; i++)
            {
                long number = long.Parse(Console.ReadLine());
                result ^= number;
            }
            Console.WriteLine(result);
        }
    }
}

Problem 5 – Fall Down

You are given a list of 8 bytes (positive integers in the range [0…255]) n₀, n₁, …, n₇. These numbers represent a square grid consisting of 8 lines and 8 columns. Each cell of the grid could either be empty or full. The first line is represented by the bits of n₀, the second – by the bits of n₁ and so on, and the last line is represented by the bits of n₇. Each bit with value 1 denotes a full cell and each bit with value 0 denotes an empty cell. The lines are numbered from the first (top) to the last (bottom) with the numbers 0, 1, …, 7. The columns are numbered from right to left with the indices 0, 1, …, 7. The figure shows a sample square grid and its representation by a sequence of 8 numbers n₀, n₁, …, n₇:

Suppose the full cells hold squares which can "fall down" by the influence of the gravity. Each full cell in certain row and column falls down to the lowest row possible but stays in the same column and up from any other full cells on the same column that ware initially down from it. At the figure the "fall down" process is illustrated.

Write a program to calculate how the grid will look like after the "fall down" process is applied.

Input

The input data is being read from the console.

There will be exactly 8 lines each holding the integer numbers n₀, n₁, …, n₇.

The input data will always be valid and in the format described. There is no need to check it explicitly.

Output

The output consists of the numbers n₀, n₁, …, n₇ after the "fall down process".

Ouput should be printed on the console, in exactly 8 lines, each holding a single integer.

Constraints

• The numbers n₀, n₁, …, n₇ are positive integers between 0 and 255, inclusive.
• Allowed work time for your program: 0.25 seconds.
• Allowed memory: 16 MB.

Examples

0
64
8
8
0
12
224
0

0
0
0
0
0
8
72
236

255
255
255
255
255
255
255
254

254
255
255
255
255
255
255
255

Problem 5 – Solution

using System;
namespace Problem_5_Fall_Down
{
    class Program
    {
        static void Main()
        {
            // Read the input numbers
            int num0 = int.Parse(Console.ReadLine());
            int num1 = int.Parse(Console.ReadLine());
            int num2 = int.Parse(Console.ReadLine());
            int num3 = int.Parse(Console.ReadLine());
            int num4 = int.Parse(Console.ReadLine());
            int num5 = int.Parse(Console.ReadLine());
            int num6 = int.Parse(Console.ReadLine());
            int num7 = int.Parse(Console.ReadLine());

            for (int count = 1; count <= 7; count++)
            {
                for (int bit = 0; bit <= 7; bit++)
                {
                    if ((num7 >> bit & 1) == 0 &&
                        (num6 >> bit & 1) == 1)
                    {
                        num7 |= (1 << bit);
                        num6 &= ~(1 << bit);
                    }
                }

                for (int bit = 0; bit <= 7; bit++)
                {
                    if ((num6 >> bit & 1) == 0 &&
                        (num5 >> bit & 1) == 1)
                    {
                        num6 |= (1 << bit);
                        num5 &= ~(1 << bit);
                    }
                }

                for (int bit = 0; bit <= 7; bit++)
                {
                    if ((num5 >> bit & 1) == 0 &&
                        (num4 >> bit & 1) == 1)
                    {
                        num5 |= (1 << bit);
                        num4 &= ~(1 << bit);
                    }
                }

                for (int bit = 0; bit <= 7; bit++)
                {
                    if ((num4 >> bit & 1) == 0 &&
                        (num3 >> bit & 1) == 1)
                    {
                        num4 |= (1 << bit);
                        num3 &= ~(1 << bit);
                    }
                }

                for (int bit = 0; bit <= 7; bit++)
                {
                    if ((num3 >> bit & 1) == 0 &&
                        (num2 >> bit & 1) == 1)
                    {
                        num3 |= (1 << bit);
                        num2 &= ~(1 << bit);
                    }
                }

                for (int bit = 0; bit <= 7; bit++)
                {
                    if ((num2 >> bit & 1) == 0 &&
                        (num1 >> bit & 1) == 1)
                    {
                        num2 |= (1 << bit);
                        num1 &= ~(1 << bit);
                    }
                }

                for (int bit = 0; bit <= 7; bit++)
                {
                    if ((num1 >> bit & 1) == 0 &&
                        (num0 >> bit & 1) == 1)
                    {
                        num1 |= (1 << bit);
                        num0 &= ~(1 << bit);
                    }
                }
            }

            Console.WriteLine(num0);
            Console.WriteLine(num1);
            Console.WriteLine(num2);
            Console.WriteLine(num3);
            Console.WriteLine(num4);
            Console.WriteLine(num5);
            Console.WriteLine(num6);
            Console.WriteLine(num7);
        }
    }
}