Наближава първият изпит в Академията на Телерик. Участниците в Академията ще трябва да се справят сами с 5 сравнително трудни за един начинаещ програмист задачи. Преди изпита студентите получиха примерен изпит с 5 задачи, подобни на задачите, които ще имат на истинския си изпит. Материалът, върху който е изпитът включва следните теми: „Примитивни типове данни и променливи“, „Оператори и изрази“, „Вход и изход от конзолата“, „Условни конструкции“ и „Цикли“. Тъй като студентите в Академията не са учили масиви, авторовите решения на задачите също не използват масиви. Тук са публикувани условията на задачите заедно с решенията на авторите на задачите от пробния изпит в Академията на Телерик.
Problem 1 – Cartesian Coordinate System (Author: Nikolay Kostov)
You are given a two-dimensional Cartesian coordinate system and the two coordinates (X and Y) of a point in the coordinate system. If you don't know what Cartesian coordinate system is Google it with Bing. As you will find, the coordinate system is divided by 2 lines (see the picture bellow) which divide the plain in four parts. Each of these parts has a lot of points that are numbered between 1 and 4. There is one point where our lines are crossing. This point has the following coordinates: X=0 and Y=0. As a result this point is numbered 0. The points on the lines are also numbered with the numbers 5 and 6 (again see the picture below).
Your task is to write a program that finds the number of the location of the given point in the coordinate system.
Input
Input data is being read from the console.
The number X is on the first input line.
The number Y is on the second input 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 an integer number between 0 and 6, depending on the location of the given point in the coordinate system.
Constraints
- The numbers X and Y are numbers between -2 000 000 000 001 337 and 2 000 000 000 001 337, inclusive.
- Allowed working time for your program: 0.25 seconds.
- Allowed memory: 16 MB.
Examples
|
Input Example |
Output Example |
|
1 2 |
1
|
|
-3 -4 |
3
|
|
-3000 9000 |
2
|
|
12345 -98786543 |
4
|
|
1337 0 |
6
|
Problem 1 – Solution
using System;
namespace Problem_1_Cartesian_Coordinate_System
{
class Problem_1_Cartesian_Coordinate_System
{
static void Main()
{
// Read input data
decimal X = decimal.Parse(Console.ReadLine());
decimal Y = decimal.Parse(Console.ReadLine());
// Solve the problem
if (X == 0 && Y == 0)
{
Console.WriteLine(0);
}
else if (X == 0)
{
Console.WriteLine(5);
}
else if (Y == 0)
{
Console.WriteLine(6);
}
else if (X > 0 && Y > 0)
{
Console.WriteLine(1);
}
else if (X < 0 && Y > 0)
{
Console.WriteLine(2);
}
else if (X < 0 && Y < 0)
{
Console.WriteLine(3);
}
else // if (X > 0 && Y < 0)
{
Console.WriteLine(4);
}
}
}
}
Problem 2 – Miss Cat 2011 (Author: Nikolay Kostov)
There are two things that cats love most: 1) sleeping and 2) attending beauty contests. The most important thing for each female cat is the contest “Miss Cat”. There are always ten cats that participate in the final round of the contest, numbered 1 to 10.
The jury of the contest consists of N people who subjectively decide which cat to vote for. In other words each person votes for just 1 cat that he has most liked, or from whose owner he has received the biggest bribe. The winner of the contest is the cat that has gathered most votes. If two cats have equal votes, the winner of the contest is the one whose number is smaller.
Your task is to write a computer program that finds the number of the cat that is going to win the contest “Miss cat”
Input
The input data is being read from the console.
The number N is on the first input line.
An integer between 1 and 10 is written on each of the next N lines (this is the number of the cat)
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 number of the cat, which has won the contest.
Constraints
- The number N is a positive integer between 1 and 100 000, inclusive.
- The numbers of the cats for which the jury votes are positive integer numbers between 1 and 10, inclusive.
- Allowed working time for your program: 0.25 second.
- Allowed memory: 16 MB.
Examples
|
Input example |
Output example |
|
1 6 |
6
|
|
4 1 3 3 7 |
3
|
|
5 1 2 3 1 2 |
1
|
Problem 2 – Solution
using System;
namespace Problem_2_Miss_Cat_2011
{
class Problem_2_Miss_Cat_2011
{
static void Main(string[] args)
{
// Read input
int N = int.Parse(Console.ReadLine());
// Solve the problem
int cat1 = 0;
int cat2 = 0;
int cat3 = 0;
int cat4 = 0;
int cat5 = 0;
int cat6 = 0;
int cat7 = 0;
int cat8 = 0;
int cat9 = 0;
int cat10 = 0;
for (int i = 1; i <= N; i++)
{
byte vote = byte.Parse(Console.ReadLine());
if (vote == 1) cat1++;
if (vote == 2) cat2++;
if (vote == 3) cat3++;
if (vote == 4) cat4++;
if (vote == 5) cat5++;
if (vote == 6) cat6++;
if (vote == 7) cat7++;
if (vote == 8) cat8++;
if (vote == 9) cat9++;
if (vote == 10) cat10++;
}
if (cat1 >= cat1 && cat1 >= cat2 && cat1 >= cat3 && cat1 >= cat4 && cat1 >= cat5 && cat1 >= cat6 && cat1 >= cat7 && cat1 >= cat8 && cat1 >= cat9 && cat1 >= cat10) Console.WriteLine(1);
else if (cat2 >= cat1 && cat2 >= cat2 && cat2 >= cat3 && cat2 >= cat4 && cat2 >= cat5 && cat2 >= cat6 && cat2 >= cat7 && cat2 >= cat8 && cat2 >= cat9 && cat2 >= cat10) Console.WriteLine(2);
else if (cat3 >= cat1 && cat3 >= cat2 && cat3 >= cat3 && cat3 >= cat4 && cat3 >= cat5 && cat3 >= cat6 && cat3 >= cat7 && cat3 >= cat8 && cat3 >= cat9 && cat3 >= cat10) Console.WriteLine(3);
else if (cat4 >= cat1 && cat4 >= cat2 && cat4 >= cat3 && cat4 >= cat4 && cat4 >= cat5 && cat4 >= cat6 && cat4 >= cat7 && cat4 >= cat8 && cat4 >= cat9 && cat4 >= cat10) Console.WriteLine(4);
else if (cat5 >= cat1 && cat5 >= cat2 && cat5 >= cat3 && cat5 >= cat4 && cat5 >= cat5 && cat5 >= cat6 && cat5 >= cat7 && cat5 >= cat8 && cat5 >= cat9 && cat5 >= cat10) Console.WriteLine(5);
else if (cat6 >= cat1 && cat6 >= cat2 && cat6 >= cat3 && cat6 >= cat4 && cat6 >= cat5 && cat6 >= cat6 && cat6 >= cat7 && cat6 >= cat8 && cat6 >= cat9 && cat6 >= cat10) Console.WriteLine(6);
else if (cat7 >= cat1 && cat7 >= cat2 && cat7 >= cat3 && cat7 >= cat4 && cat7 >= cat5 && cat7 >= cat6 && cat7 >= cat7 && cat7 >= cat8 && cat7 >= cat9 && cat7 >= cat10) Console.WriteLine(7);
else if (cat8 >= cat1 && cat8 >= cat2 && cat8 >= cat3 && cat8 >= cat4 && cat8 >= cat5 && cat8 >= cat6 && cat8 >= cat7 && cat8 >= cat8 && cat8 >= cat9 && cat8 >= cat10) Console.WriteLine(8);
else if (cat9 >= cat1 && cat9 >= cat2 && cat9 >= cat3 && cat9 >= cat4 && cat9 >= cat5 && cat9 >= cat6 && cat9 >= cat7 && cat9 >= cat8 && cat9 >= cat9 && cat9 >= cat10) Console.WriteLine(9);
else if (cat10 >= cat1 && cat10 >= cat2 && cat10 >= cat3 && cat10 >= cat4 && cat10 >= cat5 && cat10 >= cat6 && cat10 >= cat7 && cat10 >= cat8 && cat10 >= cat9 && cat10 >= cat10) Console.WriteLine(10);
}
}
}
Problem 3 – Forest Road (Author: Martin Ivanov)
Geeko, a non-stop learning trainee at Telerik Software Academy lived deep into the Lulin forests. Every time he went to the Academy he had to take a long trip through the forest. Starting from the top left corner of the forest, the road always goes down and right first and when it reaches the border, it goes down and left.
The Academy is situated in the bottom left corner, and Geeko begins his journey from the top left corner of the forest (see the examples below).
He wanted to make a program that generates a map of the forest but he couldn’t. Help Geeko on his way to the Academy by writing the program instead of him.
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 map. The map’s height is always 2*N - 1.
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 should print the whole map on the console. Use the symbol “*” (asterisk) to mark Geeko’s path and “.” (dot) to illustrate the trees.
Constraints
- The number N is a positive integer between 2 and 79, inclusive.
- Allowed working time for your program: 0.25 second.
- Allowed memory: 16 MB.
Samples
|
Sample input |
Sample output |
|
4 |
*... .*.. ..*. ...* ..*. .*.. *... |
|
5 |
*.... .*... ..*.. ...*. ....* ...*. ..*.. .*... *.... |
Problem 3 – Solution
using System;
namespace Problem_3_Forest_Road
{
class Problem_3_Forest_Road
{
static void Main()
{
// Read input
int N = int.Parse(Console.ReadLine());
// Write first part
for (int i = 0; i < N - 1; i++)
{
for (int j = 0; j < N; j++)
{
if (i != j)
{
Console.Write(".");
}
else
{
Console.Write("*");
}
}
Console.WriteLine();
}
// Write second part
for (int i = N - 1; i >= 0; i--)
{
for (int j = 0; j < N; j++)
{
if (i != j)
{
Console.Write(".");
}
else
{
Console.Write("*");
}
}
Console.WriteLine();
}
}
}
}
Problem 4 – Binary Digits Count (Author: Nikolay Kostov)
You are given a sequence of N positive integer numbers and one binary digit B (0 or 1).
Your task is to write a program that finds the number of binary digits (B) in each of the N numbers in binary numeral system. Example: 20 in the binary numeral system looks like this: 10100. The number of binary digits 0 of the number 20 in the binary numeral system is 3.
Input
The input data is being read from the console.
On the first input line there will be the digit B.
On the second line you must read the number N.
On each of the following N lines there is one positive integer number written – the consequent number, whose sum of binary digits B we are searching for.
The input data will always be valid and in the format described. There is no need to check it explicitly.
Output
The output must be printed on the console.
In the output you must have N lines. Each line must have 1 integer number – the number of digits B in the binary representation of the given consequent number.
Constraints
- Number N is a positive integer between 1 and 1000, inclusive.
- Each of the N numbers is a positive integer between 1 and 4 000 000 000, inclusive.
- The digit B will be only 0 or 1.
- Allowed work time for your program: 0.25 second.
- Allowed memory: 16 MB.
Examples
|
Input Example |
Output Example |
|
1 10 1 2 3 4 5 6 7 8 9 10 |
1 1 2 1 2 2 3 1 2 2
|
|
0 4 20 1337 2147483648 4000000000 |
3 5 31 19
|
|
0 6 1 4 16 64 256 1024 |
0 2 4 6 8 10
|
Problem 4 – Solution
using System;
namespace Problem_4_Binary_Digits_Count
{
class Problem_4_Binary_Digits_Count
{
static void Main()
{
// Read input
byte B = byte.Parse(Console.ReadLine());
short N = short.Parse(Console.ReadLine());
// Solve
for (int i = 1; i <= N; i++)
{
int count = 0;
uint number = uint.Parse(Console.ReadLine());
while (number != 0)
{
if ((number & 1) == B)
{
count++;
}
number = number >> 1;
}
// Write answers
Console.WriteLine(count);
}
}
}
}
Problem 5 – Subset Sums (Author: Nikolay Kostov)
You are given a list of N numbers. Write a program that counts all non-empty subsets from this list, which have sum of their elements exactly S.
Example: if you have a list with 4 elements: { 1, 2, 3, 4 } and you are searching the number of non-empty subsets which sum is 4, the answer will be 2. The subsets are: { 1, 3 } and { 4 }.
Input
The input data is being read from the console.
On the first input line there will be the number S.
On the second line you must read the number N.
On each of the following N lines there will be one integer number written – all the numbers from the list.
The input data will always be valid and in the format described. There is no need to check it explicitly.
Output
The output must be printed on the console.
On the only output line you must print the number of the non-empty subsets, which have sum of all its elements exactly S.
Constraints
- The number N is a positive integer between 1 and 16, inclusive.
- All of the N numbers are integer numbers and will be between -1 337 000 000 000 and 1 337 000 000 000, inclusive.
- The number S is an integer number between -21 392 000 000 000 and 21 392 000 000 000, inclusive.
- All of the N numbers will be distinct.
- Allowed work time for your program: 1 second.
- Allowed memory: 16 MB.
Examples
|
Input Example |
Output Example |
|
1 1 1 |
1
|
|
0 5 -2 -1 1 2 3 |
4
|
|
1337 4 12 23 34 45 |
0
|
Problem 5 – Solution
using System;
namespace Problem_5_Subset_Sums
{
class Problem_5_Subset_Sums
{
static void Main()
{
// Read input data
long S = long.Parse(Console.ReadLine());
int N = int.Parse(Console.ReadLine());
long n1, n2, n3, n4, n5, n6, n7, n8,
n9, n10, n11, n12, n13, n14, n15, n16;
n1 = n2 = n3 = n4 = n5 = n6 = n7 = n8 = n9 = 0L;
n10 = n11 = n12 = n13 = n14 = n15 = n16 = 0L;
for (int i = 1; i <= N; i++)
{
if (i == 1) n1 = long.Parse(Console.ReadLine());
if (i == 2) n2 = long.Parse(Console.ReadLine());
if (i == 3) n3 = long.Parse(Console.ReadLine());
if (i == 4) n4 = long.Parse(Console.ReadLine());
if (i == 5) n5 = long.Parse(Console.ReadLine());
if (i == 6) n6 = long.Parse(Console.ReadLine());
if (i == 7) n7 = long.Parse(Console.ReadLine());
if (i == 8) n8 = long.Parse(Console.ReadLine());
if (i == 9) n9 = long.Parse(Console.ReadLine());
if (i == 10) n10 = long.Parse(Console.ReadLine());
if (i == 11) n11 = long.Parse(Console.ReadLine());
if (i == 12) n12 = long.Parse(Console.ReadLine());
if (i == 13) n13 = long.Parse(Console.ReadLine());
if (i == 14) n14 = long.Parse(Console.ReadLine());
if (i == 15) n15 = long.Parse(Console.ReadLine());
if (i == 16) n16 = long.Parse(Console.ReadLine());
}
// Find answer
int answer = 0;
int maxi = (int)Math.Pow(2, N) - 1;
for (int i = 1; i <= maxi; i++)
{
long currentSum = 0;
for (int j = 1; j <= N; j++)
{
if (((i >> (j - 1)) & 1) == 1)
{
if (j == 1) currentSum += n1;
if (j == 2) currentSum += n2;
if (j == 3) currentSum += n3;
if (j == 4) currentSum += n4;
if (j == 5) currentSum += n5;
if (j == 6) currentSum += n6;
if (j == 7) currentSum += n7;
if (j == 8) currentSum += n8;
if (j == 9) currentSum += n9;
if (j == 10) currentSum += n10;
if (j == 11) currentSum += n11;
if (j == 12) currentSum += n12;
if (j == 13) currentSum += n13;
if (j == 14) currentSum += n14;
if (j == 15) currentSum += n15;
if (j == 16) currentSum += n16;
}
}
if (currentSum == S) answer++;
}
// Write output data
Console.WriteLine(answer);
}
}
}