Tag Archives: topcoder

146,212. Die-game Yahtzee

This task is about the scoring in the first phase of the die-game Yahtzee, where five dice are used. The score is determined by the values on the upward die faces after a roll. The player gets to choose a value, and all dice that show the chosen value are considered active. The score is simply the sum of values on active dice.

Say, for instance, that a player ends up with the die faces showing 2, 2, 3, 5 and 4. Choosing the value two makes the dice showing 2 active and yields a score of 2 + 2 = 4, while choosing 5 makes the one die showing 5 active, yielding a score of 5.

Your method will take as input an int[] toss, where each element represents the upward face of a die, and return the maximum possible score with these values. Read more of this post

Advertisement

203. New Username

When a new member signs up, it is possible that she initially chooses the same username as an existing member. The system must then inform the new member of the conflict and suggest a variant of the chosen name with a number attached to the end.

If an existing member is named “FunkyMonkey”, for example, and a new member wants the same username, the simplest suggestion the system can make is “FunkyMonkey1”. If there is already a member by that name, the system must suggest “FunkyMonkey2”, unless that variant is also taken. If all names from “FunkyMonkey1” through “FunkyMonkey9” are taken as well as the original “FunkyMonkey”, the system moves on to consider “FunkyMonkey10”, and so on. The goal is to use the smallest possible number in the variant. Note that each username consists of letters (the characters from ‘a’ to ‘z’ and from ‘A’ to ‘Z’) and numerals (‘0’ to ‘9’).

You are given a String[], existingNames, containing all usernames that have already been registered in the system. You are also given a single String, newName, containing the username that a new member wants to use. In the event of a conflict, this member will accept the suggestion offered by your system in accordance with the principles above. Return a String containing the username finally assigned to the new member. Read more of this post

191. Betting Money

You run a gambling business in which people place bets on the margin of victory in a football game. At the end of the day, the company would like to know what the day’s net gain has been.   Just as in any other betting system, people place certain amounts as their bets and if they guess correctly, they get their money back plus a pre-specified percentage of their bet; otherwise they lose the money they bet.

You are given a int[], amounts, the ith element of which is the number of dollars people have placed on a victory margin of i (i = 0 refers to the first element). You are also given a int[], centsPerDollar, the ith element of which is the number of cents the company has to pay for every dollar the people bet on a victory margin of i, if the final outcome is a victory margin of i. Finally, you are given an int, finalResult, which is the final margin of victory. You have to determine what the net gain for the day was and return the amount in cents.

For example, if amounts were {10,20,30}, it would mean that people placed $10 on a draw outcome, $20 on a victory margin of 1 and $30 on a victory margin of 2, and if centsPerDollar were {20,30,40}, it would mean the people would win 20 cents per dollar bet if the match were a draw, 30 cents per dollar if the victory margin were 1 and 40 cents per dollar if the victory margin were 2.

Suppose the final result is a victory margin of 1 (i.e., finalResult = 1). Then the people who guessed the outcome as a margin of 0 or 2 were wrong and the company receives the amounts they bet, $10+$30. However, the people who guessed that the outcome would be a margin of 1 were correct, and they receive money from the company according to the amount they bet (20 dollars) and the pre-set payoff percentage (30 cents per dollar) . This amounts to 20*30 = 600 cents. Hence, the day’s net gain is 40 dollars – 600 cents = 3400 cents. You should return 3400. Read more of this post

209. Olympic Medal Table

The results of the disciplines are given as a String[] results, where each element is in the format  “GGG SSS BBB”. GGG, SSS and BBB are the 3-letter country codes (three capital letters from ‘A’ to ‘Z’)  of the countries winning the gold, silver and bronze medal, respectively.

The medal table is a String[] with an element for each country appearing in results. Each element has  to be in the format “CCO G S B” (quotes for clarity), where G, S and B are the number of gold, silver  and bronze medals won by country CCO, e.g. “AUT 1 4 1”. The numbers should not have any extra leading zeros.

Sort the elements by the number of gold medals won in decreasing order. If several countries are tied,  sort the tied countries by the number of silver medals won in decreasing order. If some countries are  still tied, sort the tied countries by the number of bronze medals won in decreasing order. If a tie  still remains, sort the tied countries by their 3-letter code in ascending Read more of this post

208. Tall People

A group of people stands before you arranged in rows and columns. Looking from above, they form an R by C rectangle of people. Your job is to return 2 specific heights – the first is computed by finding the shortest person in each row, and then finding the tallest person among them (the “tallest-of-the-shortest”); and the second is computed by finding the tallest person in each column, and then finding the shortest person among them (the “shortest-of-the-tallest”). Read more of this post

236. Business Tasks

N tasks are written down in the form of a circular list, so the first task is adjacent to the last one. A number n is also given. Starting with the first task, move clockwise (from element 1 in the list to element 2 in the list and so on), counting from 1 to n. When your count reaches n, remove that task from the list and start counting from the next available task. Repeat this procedure until one task remains. Return it. Read more of this post

Maximum cut

Kader only likes to eat eels of length exactly 10, no more, no less. Before she eats, she may cut the eels to prepare pieces of desired length. However, she only has the time to make at most maxCuts cuts. You are given a int[] eelLengths. Each element of eelLengths is the length of one of the eels Kader has at the beginning. You are also given the int maxCuts. Return the maximum number of eels of length exactly 10 she can produce.

Examples
1)i/p={13,20,13}, 2 Returns: 3
Steps are 13 = 13/10 = 1, exactly 10 length 10 is 1.
20 = 20/10 = 2, exactly 10 length is 2, total is 3. (reached maxcuts 2). Total is 3.

2)i/p={5, 5, 5, 5}, 2 Returns: 0
All are less then 10.

3)i/p={34, 10, 48}, 4 Returns: 5
Steps are 34 = 34/10 = 3 = 3 (maxcuts 5-3= 2)
10 = 10/10 = 1 = 4
48 = 48/10 – 4 = 1(exceed maxcuts 4>2)

4)i/p={30, 50, 30, 50}, 350 Returns: 16 Read more of this post

Minimum palindrome cost

A palindrome is a string that reads the same from left to right as it does from right to left.  The length of a input String s is even. Each character of s is either ‘o’, ‘x’, or ‘?’ Your task in this problem is to replace each occurrence of ‘?’ in s with either ‘o’ or ‘x’ so that s becomes a palindrome. You are also given integers oCost and xCost. Replacing ‘?’ with ‘o’ costs oCost, and replacing ‘?’ with ‘x’ costs xCost.     Return the minimum cost of replacing ‘?’s by ‘x’s and ‘o’s that turns s into a palindrome. If it is impossible to obtain a palindrome, return -1 instead.

Examples

1)i/p=”oxo?xox?”, 3, 5 Returns: 8
Steps are   s[7] = ? = > s[7] replace by ‘o’ of s[0]. s[7] = o, so cost is 3.
s[3] = ? = > s[3] replace by ‘x’ of s[4]. s[2] = x, so cost is 5. Total Cost is 8.

2)i/p=”x??x”, 9, 4 Returns: 8
Steps are  s[1] = s[2] = ? > both are replaced by minimum cost 4 is ‘x’. Total Cost is 8.

3)i/p=”ooooxxxx”,12,34 returns: -1
Steps are    No ‘?’ character, and s is not a palindrome. Total Cost is -1.

4)i/p=”oxoxooxxxxooxoxo”,7,4 Returns: 0
Steps are  No ‘?’ character, and s is already a palindrome. Total Cost is 0.

5)i/p=”?o”, 6, 2 Returns: 6
Steps are  s[0] = ? = > s[0] replace by ‘o’ of s[1]. s[0] = o, so cost is 6. Total Cost is 6. Read more of this post

Casket Of Star

The Casket of Star (sic) is a device in the Touhou universe. Its purpose is to generate energy rapidly. Initially it contains n stars in a row. The stars are labeled 0 through n-1 from the left to the right. You are given a int[] weight, where weight[i] is the weight of star i.The following operation can be repeatedly used to generate energy:

Choose a star x other than the very first star and the very last star.  The x-th star disappears.  This generates weight[x-1] * weight[x+1] units of energy.  We decrease n and relabel the stars 0 through n-1 from the left to the right.

Examples
1)i/p={1,2,3,4}   Returns: 12
Steps are
{1,2,3,4}
(3+4){1,3,4} | (8+4) {1,2,4}

2)i/p={100,2,1,3,100} Returns: 10400

3)i/p={2,2,7,6,90,5,9} Returns: 1818

4)i/p={477,744,474,777,447,747,777,474} Returns: 2937951

4)i/p={3, 1, 4, 10, 3} Returns: 51
{3, 4, 10, 3} = 12 (12+30+9=>51, 12+12+9=>33)
{3, 10, 3} = 30 | {3, 4, 3} = 12 = 9 | = 9
{3, 1, 10, 3} = 10 (10+30+9=>49, 10+3+9=>22)
{3, 10, 3} = 30 | {3, 1, 3} = 3 = 9 | = 9
{3, 1, 4, 3} = 12 (12+12+9=>33, 12+3+9=>24)
{3, 4, 3} = 12 | {3, 1, 3} = 3 = 9 | = 9 Read more of this post

Pokemon Pikachu

Pikachu is a well-known character in the Pokemon anime series. Pikachu can speak, but only 3 syllables: “pi”, “ka”, and “chu”. Therefore Pikachu can only pronounce strings that can be created as a concatenation of one or more syllables he can pronounce. For example, he can pronounce the words “pikapi” and “pikachu”.
Examples
1)i/p=”pikapi”    Returns: “YES”   = >   “pikapi” = “pi” + “ka” + “pi”

2)i/p=”pipikachu”    Returns: “YES”    =>   “pipikachu” = “pi” + “pi” + “ka” + “chu”

3)i/p=”pikaqiu”      Returns: “NO”    => since ‘q’ does not appear in “pi”, “ka”, or “chu”.

4)i/p=”daynight”     Returns: “NO”

5)i/p=”piika”  Returns: “NO” Read more of this post

Checker Winner

Elly and Kriss play a game. The game is played on a single row that consists of N cells; we will call it the board. The cells of the board are numbered 0 through N-1, from the left to the right. Each cell of the board is either empty or occupied by a single checker. The girls take alternating turns, until one of them cannot make a move. The girl who is unable to make a move loses the game.

In each move the current player selects a cell containing a checker and performs one of the following two types of moves:A step, in which the checker is moved one cell to the right. The step can only be made if the target cell is empty.

A jump, in which the checker jumps three cells to the right. The jump can only be made if the target cell is empty and the cells it jumped over contain two other checkers.

Once a checker reaches the rightmost cell, it disappears immediately and no longer plays any role in the game.

The initial layout of the board will be given as a String board. The i-th character of board will be ‘.’ (a period) if the i-th cell is empty at the beginning, and it will be ‘o’ (lowercase letter o) if the i-th cell initially contains a checker. Assume that both girls play optimally. Return “YES” (quotes for clarity) if the first player wins the game and “NO” otherwise. Read more of this post

File Directory

Elly wants to write a program that lists all the files in a given directory. She already has the list of all the files. You will be given this list as a String[] files. In addition to the names of files, the variable files will contain exactly two additional elements: the current directory (the String “.”), and the parent directory (the String “..”). These two elements may be anywhere in files. However, Elly wants them to be the last two elements. In order to move the two directories to the last two positions in files, she wants you to perform the following steps:If “.” and “..” are the last two elements of files (in any order), you are done.

Find the first element of files that is either “.” or “..”. Swap it with the last element of files.

If “.” and “..” are now the last two elements of files (in any order), you are done.

Find the first element of files that is either “.” or “..”. Swap it with the element of files that is one position before the last one.

Your method must perform the above steps and return a String[] containing the modified order of elements in files.

Read more of this post

Maximum cut

Kader only likes to eat eels of length exactly 10, no more, no less. Before she eats, she may cut the eels to prepare pieces of desired length. However, she only has the time to make at most maxCuts cuts. You are given a int[] eelLengths. Each element of eelLengths is the length of one of the eels Kader has at the beginning. You are also given the int maxCuts. Return the maximum number of eels of length exactly 10 she can produce. Read more of this post

Minimum Palindrome Cost

A palindrome is a string that reads the same from left to right as it does from right to left.

The length of a input String s is even. Each character of s is either ‘o’, ‘x’, or ‘?’ Your task in this problem is to replace each occurrence of ‘?’ in s with either ‘o’ or ‘x’ so that s becomes a palindrome. You are also given integers oCost and xCost. Replacing ‘?’ with ‘o’ costs oCost, and replacing ‘?’ with ‘x’ costs xCost.

Return the minimum cost of replacing ‘?’s by ‘x’s and ‘o’s that turns s into a palindrome. If it is impossible to obtain a palindrome, return -1 instead.

Method: public int getMinimum(String s, int oCost, int xCost)

Read more of this post

Total Card Flip

Kader has a set of 64 cards: for each x between 0 and 63, he has a card that is blank on one side and has 2^x dots on the other side. Kader’s cards are placed on a table. At any moment, the cards show some integer between 0 and (2^64)-1, inclusive. To read the number, you just count all the dots you see. Kader is using the cards to count from A to B. That is, he is flipping some of the cards in such a way that the numbers A, A+1, …, B appear in this order.Kader is using the shortest possible sequence of flips. Additionally, he always flips the cards one at a time. Sometimes, changing the number from some Z to Z+1 requires Kader to flip more than one card. In that case, he flips the necessary cards ordered by the number of dots they have, starting with the one with the most dots.For example, if A=6 and B=8, the following will happen:

In the beginning, the card with 4 dots and the card with 2 dots are showing the dots, all other cards are blank side up. This shows the number 6.

He flips the card with 1 dot. Now the number 7 is shown. He flips the card with 8 dots. He flips the card with 4 dots. He flips the card with 2 dots. He flips the card with 1 dot. Now the number 8 is shown and he is done.

Given are longs A and B. Your method must return the largest number that will be shown at any moment during his counting. Read more of this post

Missed day of the week

This week there will be an important delivery of your entire team. You clearly remember your team manger telling you about it. The only thing you forgot is the day of the week when the delivery will take place.You asked six of your team members about the delivery. None of them knew the day when it will take place, but each of them remembered one day when it will not take place. The days they remembered were distinct. For a clever coder like you, this was enough to determine the day of the meeting.You are given a String[] notOnThisDay containing six weekdays when the meeting will not take place. Return the weekday of the meeting.

Method: public String getDay(String[] notOnThisDay)

Examples
1)i/p=>{“Sunday”, “Monday”, “Tuesday”, “Wednesday”, “Thursday”, “Friday”}, o/p=> “Saturday”.

2)i/p=>{“Sunday”, “Monday”, “Tuesday”, “Wednesday”, “Friday”, “Thursday”}, o/p=> “Saturday”.

3)i/p=>{“Sunday”, “Monday”, “Tuesday”, “Thursday”, “Friday”, “Saturday”}, o/p=> “Wednesday”.

4)i/p=>{“Sunday”, “Friday”, “Tuesday”, “Wednesday”, “Monday”, “Saturday”}, o/p=> “Thursday”.

Read more of this post

Short Time

Reach from (x,y) points to (x1,y1) points. There are two ways in which you can travel.

Option 1 is jumping: if you are at (x,y), you can jump to one of the four neighboring grid points: (x+1,y), (x-1,y), (x,y+1), or (x,y-1). Each jump takes one second.

Option 2 is using a port. There are three ports. Each of them connects two different grid points. If you are at one of the endpoints, you may activate the port and travel to its other endpoint. Traveling by port takes 10 seconds.

Find out the the shortest time in which you can reach (x1,y1) points.

Method: public int shortestTime(int x, int y, int x1, int y1, String[] ports)

Examples

1)i/p=>3 3 4 5, {“1000 1001 1000 1002”, “1000 1003 1000 1004”, “1000 1005 1000 1006”}  Returns: 3
Steps are
(3,3) to (3,4) = 1 second
(3,4) to (3,5) = 2 second
(3,5) to (4,5) = 3 second

2)i/p=>0 0 20 20, {“1 1 18 20”, “1000 1003 1000 1004”, “1000 1005 1000 1006”}  Returns: 14
Steps are
(0,0) to (0,1) = 1 second
(0,1) to (1,1) = 2 second
(1,1) to (18,1) = 10 second (used port)
(18,1) to (18,20) = 10 second (used port)

3)i/p=>0 0 20 20 {“1000 1003 1000 1004”, “18 20 1 1”, “1000 1005 1000 1006”} Returns: 14
Same the above steps, but the ports may be used in either direction, and in any order.

4)i/p=>10 10 10000 20000, {“1000 1003 1000 1004”, “3 3 10004 20002”, “1000 1005 1000 1006”} Returns: 30
Steps are
(10,10) to (3,3) = (10-3)7+(10-3)7 = 14 seconds
(3,3) to (10004 20002) = 10+10 = 20 seconds (used port)
(10004 20002) to (10000 20000) = (10004-4)4+(20000-2)2 = 6 seconds

5)i/p=>3 7 10000 30000, {“3 10 5200 4900”, “12212 8699 9999 30011”, “12200 8701 5203 4845”} Returns: 117
Steps are
(3,7) to (3,10) = 3 seconds
(5200,4900) to (5203,4845) = 10+3+55 = 68 seconds (used port)
(12200,8701) to (12212,8699) = 10+12+2 = 24 seconds (used port)
(9999,30011) to (10000,30000) = 10+1+11 = 22 seconds (used port)

6)i/p=>0 0 1000000000 1000000000, {“0 1 0 999999999”, “1 1000000000 999999999 0”, “1000000000 1 1000000000 999999999”}  Returns: 36
Steps are
(0 ,0) to (0, 1) = 1 second
(0, 999999999) to (1, 1000000000) = 10 +1+1= 12 seconds (used port)
(999999999 0) to (1000000000 1) = 10 +1+1= 12 seconds (used port)
(1000000000 999999999) to (1000000000 1) = 10 + 1= 11 seconds (used port)

Read more of this post

Numbers With Lucky Last Digit

DNS believes that the digits end with 4 and 7 are lucky, and all other digits are unlucky. For example, 4, 14 and 207 are lucky numbers, while 40, 741 and 3 are not lucky numbers. DNS would like to represent the int n as a sum of only lucky numbers, and he would like to do this using the minimal possible number of summands. Return the number of summands in the representation, or -1 if it is impossible to achieve the goal.

input => int n, sum of lucky numbers
output => int n , minimal possible number of summands
Examples
1)i/p: 99 o/p: 4 => 14+24+27+34
2)i/p: 11 o/p: 2
3)i/p: 13 o/p: -1
4)i/p: 1234567 100 o/p: 1
5)i/p: 1 o/p: -1
6)i/p: 2 o/p: -1
7)i/p: 3 o/p: -1
8)i/p: 4 o/p: 1

Read more of this post

Share Money

DNS decided to share moeny with his friends instead. He knows how much money each of his friends has. While he still has money left, he will repeat the following steps: Choose the poorest friend. If there are multiple poorest friends, choose one of them randomly. Give 1 dollar to the chosen friend. The return value must contain the number of dollars owned by each friend after DNS has performed the above distribution, sorted in non-decreasing order.
input => int[] friendmoney, int moneyshare
output => int[] friendmoney (distributed sorted in non-decreasing order)
Examples
1)i/p: {1, 2, 3, 4} 2 o/p: {2, 3, 3, 4 }
2)i/p: {4, 7} 1 o/p: {5, 7}
3)i/p: {1} 100 o/p: 101
4)i/p: {21, 85, 6, 54, 70, 100, 91, 60, 71} 15 100 o/p: {21, 21, 54, 60, 70, 71, 85, 91, 100 }
5)i/p: {68, 30, 5, 66, 69, 25, 58}, 55 o/p: {38, 38, 39, 58, 66, 68, 69}
6)i/p: {45, 44, 24, 92, 29, 94}, 45 o/p: {46, 47, 47, 47, 92, 94}

Read more of this post

Slime Rancher

You are playing a game titled Slime Rancher 2. You will be training slimes in this game. You have a slime-in-training. Associated with the slime are N attributes, numbered 0 through N-1, each represented by a positive integer. You are given int[] attributes containing N integers : the i-th integer is the initial value of the i-th attribute for the slime. After the training is complete, each of the slime’s attributes will either stay the same or increase to some positive integer less than or equal to 999. None of the attributes will decrease in value. The weight of the training is defined as the sum of the differences between the final and initial values of all the attributes for the slime.
You are a master slime breeder, and you’re able to obtain any possible final values for a slime’s attributes. This time, you would like to create a well-balanced slime. A slime is well-balanced if all of its attributes have equal values. What is the minimum possible weight of the training? Read more of this post