Problem od 250 poena: Aliens
Aliens from planet X have difficulties when reading our numbers. They read and write numbers from right to left and they see only one of each digit that is contained in that number and that is the first of each digit that they see reading in their way, from right to left. For example, number 377292887 they will see as 78293. You are given array of strings, each string representing one number, and your task is to return number of how much different numbers one inhabitant from planet X see in that array.
Definition
Class: Aliens
Method: differentNumbers
Parameters: String[]
Returns: int
Method signature: int differentNumbers(string[] numbers)
(be sure your method is public)
Notes:
• Element from names will not have leading zeroes
• Element from names may have trailing zeroes (aliens leading zeros)
Constraints
- numbers will contain between 1 and 5000 elements, inclusive
- Every element from names will be between 1 and 50 characters, inclusive
- Every element from names will contain only digits without leading zeroes
Examples
- String[]: {"111",
"1", "10", "11"}
Returns int:1
- String[]: {"1",
"11", "21", "12",
"2211122", "2"}
Returns int:4
- String[]:
{"12345",
"12234555", "13243545", "1234512345"}
Returns int:1
Problem od 500 poena: Shortest Path
John has started working as a programmer at "Pexim" a month ago. He was so happy when he received the first salary, because he finally could afford a motor bike and avoid the crowded city busses. John is a great programmer, but he came recently to Belgrade and he doesn't know which is the shortest way from home to work, so he asked you to help him.
You are given 1 dimensional array of string which is a map of the city.
Each element of the map can be: '.', '+', 'H' and 'W'.
Notes:
• There will not always be way from Home to Work and the city is always surrounded with '+'. In case when there is no such a path, return -1
'+' – obstacle; John can't trevel through that.
'.' - available place.
'H' – point of his house.
'W' – point of his work place.
Example:
You are given a map with dimensions 5 * 6
+ + + + + +
+ . . . . +
+ H . . W +
+ + . + . +
+ + + + + +
The length of the shortest path from home (H) to work (W) is 3.
Definition
Class: ShortestPath
Method: findShortestPath
Parameters: String[]
Returns: int
Method signature: int findShortestPath(string[] map)
(be sure your method is public)
Constraints
- Width and Height are integers between 1 and 100, inclusive.
- Map elements must contain only '.', '+', 'H' and 'W' characters.
- City described in map must be enclosed with '+' characters.
- There will be one and only one 'H' and 'W' characters in map.
- No diagonal moves are possible.
Examples
- String[]: {"+++++++",
"+H....+", "+..++.+", "+...W.+", "+++++++"}
Returns int:5
- String[]: {"++++++",
"+....+", "+H..W+", "++.+.+",
"++.+.+", "++++++"}
Returns int:3
- String[]:
{"++++",
"+H.+", "+.W+", "++++"}
Returns int:2
Problem od 1000 poena: Candy Sharing
Ana received a box of candies for her birthday. As being a good friend, she decided to share the candies with his friends. Ana has a lot of friends, but she doesn’t want to share the candies with all of them :) and as she is a programmer she want to do the sharing by a specific algorithm. Of course she chose you to help her, knowing that you are a better programmer than her :)
Here is the description of the algorithm:
You are given two positive integers, Candies and friends. Consider all possible ways to express Candies as a sum of exactly friends positive integers. Two ways are considered equal if we can obtain one from the other by changing the order of the summed numbers. For example, 8=3+2+1+1+1 is the same as 8=1+3+1+2+1, but not the same as 8=3+2+2+1. Thus we will only be interested in such summations where the summed integers are in non-increasing order.
For example, if sum=8 and count=3, the possible ways are:
8 = 6+1+1
8 = 3+3+2
8 = 4+2+2
8 = 4+3+1
8 = 5+2+1
We may now order these summations in the following way: Order them according to the first summand in decreasing order. In case of a tie, order them according to the second summand, etc. In general, to compare two summations, look at the first summand where they differ. The one where this summand is larger will be earlier in our order.
For our previous example, the correct order is:
8 = 6+1+1
8 = 5+2+1
8 = 4+3+1
8 = 4+2+2
8 = 3+3+2
You will be given three ints: Candies, friends and index, where index contains a zero-based index of a summation in the order defined above. Your method should return a String containing that summation in the form "SUM=SUMMAND(1)+...+SUMMAND(count)". If index is too large to specify a valid summation, return an empty String.
Definition
Class: CandySharing
Method: kthSharing
Parameters: int, int, int
Returns: String
Method signature: : String kthSharing(int Candies, int friends, int index)
(be sure your method is public)
NOTE: You may assume that the total number of possible summations will never exceed 2,000,000,000.
Constraints
- • Candies is between 1 and 150, inclusive.
- • friends is between 1 and 150, inclusive.
- • index is between 0 and 2,000,000,000, inclusive.
- There will be one and only one 'H' and 'W' characters in map.
- No diagonal moves are possible.
Examples
- int:
8
int: 3
int: 2
Returns int:8=4+3+1
This is the example from the problem statement. Look at the ordered list of possible summations and number them starting with zero.
- int:
13
int: 1
int: 0
Returns int:13=13
There is only one possibility here.
- int:
8
int: 7
int: 10
Returns int:
This is impossible. A sum of 10 positive integers is never equal to 7.
Thes problem statements are the exclusive and proprietary property of Pexim Solutions. Any unauthorized use or reproduction of this information without the prior written consent of Pexim Solutions is strictly prohibited. (C) 2008, Pexim Solutions. All rights reserved.