Practice Room SRM 181 DIV 2, Problem 550

Here a new problem I´ve solved right now!

Here first check the direction(beginning to the right), then check if start is < or > than combo[i], get the degrees, and continue with the other directions, until no more elements left. Then return the result as a double.

Here the problem statement:

Combination locks are convenient, because of their design. A combination lock consists of a small wheel to input the combination, and a latch to actually lock things together. The wheel contains consecutive numbers equally spaced around its edge, starting from zero and increasing clockwise. The outer casing of the lock has a small notch. To open the lock, you must rotate the wheel and align the numbers on the wheel with the notch in a specific order.

TopLock, a small company manufacturing combination locks, has recently decided to change its lock setup to give more security than the competitors. Many typical combination locks have a set of three numbers which you must input in order. TopLock locks will have a variable combination length which will be no less than three. In addition, they will be changing the number of numbers on the wheel, which will be between 10 and 100, inclusive.

To open a lock, you must follow the algorithm outlined below:

1. Set the current rotation direction to counterclockwise, and set N to the number of numbers in the combination.

2. Rotate the wheel N full turns in the current rotation direction, where a full turn is a 360 degree spin that leaves the notch pointing at the same number.

3. Continue to rotate the wheel in the current rotation direction until the notch is pointing at the next number in the combination, which successfully inputs that number. Note that by rotating the wheel counter-clockwise, the number that the notch points to will increase.

4. If there are no more numbers to input, open the lock, you’re finished! Otherwise, reverse the current rotation direction, decrease N by one, and go back to step 2.

It is guaranteed that no two adjacent numbers in combo will be the same, so as to avoid ambiguity in step 3. Also, the starting position of the lock, start, will not be the same as the first number in combo.

Given a int[] combo, indicating the combination of the lock, an int size, the number of numbers on the wheel, and an int start, indicating the number that the notch starts off pointing at, your method should return a double indicating the total number of degrees turned to open the lock.

For example, if combo = {10,20,30}, size = 40, and start = 6, you would first rotate the wheel three times counterclockwise and then 4 units to the 10, for a total of 3 * 360 + 4 * (360 / 40) = 1116 degrees, and then you would rotate twice clockwise and 30 units to the 20, and then once counterclockwise and 10 units to the 30. Your method would in this case return 1116 + 990 + 450 = 2556.

Here my code:

public class CombinationLock
    {
        public double degreesTurned(int[] combo, int size, int start)
        {
            double res = 0.0;
            bool right = true;
            for (int i = 0; i < combo.Length; i++)
            {
                int temp = 0;
                if (right == true)
                {
                    if (start < combo[i])
                        res += (((double)combo.Length - (double)i) * 360.0) + (((double)combo[i] - (double)start) * (360.0 / (double)size));
                    else
                    {
                        temp = (size - start) + combo[i];
                        res += (((double)combo.Length - (double)i) * 360.0) + ((double)temp * (360.0 / (double)size));
                    }
                    start = combo[i];
                    right = false;
                }
                else
                {
                    if (start < combo[i])
                    {
                        temp = (start + size) - combo[i];
                        res += (((double)combo.Length - (double)i) * 360.0) + ((double)temp * (360.0 / (double)size));
                    }
                    else
                    {
                        temp = start - combo[i];
                        res += (((double)combo.Length - (double)i) * 360.0) + ((double)temp * (360.0 / (double)size));
                    }
                    start = combo[i];
                    right = true;
                }
            }
            return res;
        }
    }

If you have another approach, please share with me in a comment!

Thank you very much

C# – Bubble sort

Hello, i go to explain the sort algorithm Bubble Sort in C#.

The purpose of this sorting algorithm is check each pair, and swap the positions if the first element is > than the second, then continue with the next pair.

First i begin with a for loop, from i to n, then initialize a int variable, called x to 0, and another for loop, from a = x + 1 to n – i.

{ 5, 1, 4, 2, 3, 6, 8, 7 } We will use this array! With this first stepts, we have the following:

a for loop with i = 0, x = 0, and a = 1.  Then begin to check if (input[x] > input[a]) or (input[0] > input[1]), if it is bigger, swap the elements, i have used this:

temp = input[a]; //Store input[a] into temp
input[a] = input[x]; //Change input[a] for input[x]
input[x] = temp; //Change input[x] for the stores value in temp

In this example, first check if 5 > 1, if it is, swap the elements

{ 1, 5, 4, 2, 3, 6, 8, 7 } Then check if 5 > 4, if it is, swap and add +1 to x, to get the next pair

{ 1, 4, 5, 2, 3, 6, 8, 7 } And continue doing this.. then we finish the first iteration with:

{ 1, 4, 2, 3, 5, 6, 7, 8 } Then the first iteratation is over.

Then now our values are: i = 1 (next iteration of the first loop), x = 0 again, and a = 1 again (to check the fiest pair). But notice than the second loop was from a = x + 1 yo n - i. This means that in this iteration, we will only check until n – 1 (because the last element is already sorted, 8 in this example), and inthe next until n – 2, and continue until no more pairs left.

Then when i = 1, check if (1 > 4), how is not bigger, add +1 to x and check if (4 > 2), here it is bigger, then swap:

{ 1, 2, 4, 3, 5, 6, 7, 8 } And then add +1 to x, and check the next pair, 4 > 3, how it is, swap the elements.

{ 1, 2, 3, 4, 5, 6, 7, 8 } … and so on…

In each iteration of the first loop, we will check n – i elements, and when the first for loop ends, we have sorted all the elements.

Here my code:

public class BubbleSort
    {
        public int[] bubbleSort(int[] input)
        {
            int temp = 0;
            int x = 0;
            for (int i = 0; i < input.Length; i++)
            {
                x = 0;
                for (int a = x + 1; a < input.Length - i; a++)
                {
                    if (input[x] > input[a])
                    {
                        temp = input[a]; 
                        input[a] = input[x]; 
                        input[x] = temp; 
                    }
                    x++;
                }
            }
            return input;
        }
    }

Here some outputs:

Thanks for read, i hope you enjoy!

SRM 579 DIV 2, Problem 250

Here a new problem from today´s SRM! This round +105 points! 

Here only need to sort the array, then begiining at i = 0, check if initial > array[i], if it is, initial += array[i] / 2, and result + 1. When the for loop ends, return the result.

Here the problem statement:

The Primal Grez are ferocious creatures. They constantly fight each other. When a Grez wins a battle against another Grez, the winner captures the loser’s essence, thus becoming stronger. More formally:

• The power level of each Grez is a positive integer.
• A Grez can only defeat creatures that have a strictly smaller power level.
• When a Grez of power level X defeats a Grez of power level Y, the first Grez’s power level is increased to X + Y/2. Note that Y/2 represents integer division, i.e., the fractional part is discarded. For example, for Y=3 we have Y/2 = 1.

Your goal is to help a Grez that currently has power level equal to int initialLevel battle against a set of other Grez. For each i, Grez number i (0-based index) has a power level equal to grezPower[i]. Your Grez can challenge the other creatures in any order.

You are given the int initialLevel and the int[] grezPower. Return the maximum number of creatures your Grez can defeat, one after another. 

Here my code:

public class PrimalUnlicensedCreatures
    {
        public int maxWins(int initialLevel, int[] grezPower)
        {
            int res = 0;
            Array.Sort(grezPower);
            for (int i = 0; i < grezPower.Length; i++)
            {
                if (initialLevel > grezPower[i])
                {
                    initialLevel += (grezPower[i] / 2);
                    res++;
                }
            }
            return res;
        }
    }

If you have another approach, please share with me in a comment!

Thank you very much

Practice Room SRM 179 DIV 2, Problem 550 Rep

here a new problem I´ve solved right now!

Here first need to work with people and small packages, if people is 0, then only small packages, substracting -2 if people is > 0, else -3. Then check if x == -2, if it is, substract -1 to y. And then continue working with y (large packages). If people > 0, substract 1, else, 2 large. Then return the result as an int.

Here the problem statement:

We have p people, x small packs, and y large packs. A packhorse can carry one of the following loads. It is not possible to have a horse carry a mixture of small and large packs.

• 3 or fewer small packs
• 2 or fewer large packs
• a person and 2 or fewer small packs
• a person and 1 large pack

We need to know the fewest horses that we can use to handle our people and packs. Create a class Packhorse that contains a method horses that is given p, x, and y and returns the smallest number of horses that can carry the load. 

Here my code:

public class Packhorses
    {
        public int horses(int p, int x, int y)
        {
            int horses = 0;
            while (x > 0)
            {
                if (p > 0)
                {
                    p--;
                    x -= 2;
                }
                else
                    x -= 3;
                horses++;
            }
            if (x < 0 && Math.Abs(x) % 2 == 0)
                y--;
            while (y > 0)
            {
                if (p > 0)
                {
                    p--;
                    y--;
                }
                else
                    y -= 2;
                horses++;
            }
            horses += p;
            return horses;
        }
    }

If you have another approach, please share with me in a comment!

Thank you very much

Practice Room SRM 177 DIV 2, Problem 500 Rep

Here a new problem I´ve solved right now!

Here i decided a for loop, in each iteration use regular expression to get the first index of the first digit, then, extract the name, and then extract the next 3 elements in the element, and eliminate the white spaces if exist, then, check if is bigger than the maximum previously stored. When the for loop ends, remove the white spaces in the beginning of the result and at the end, and then return the result.

Here the problem statement:

Our student data is a mess! Each student is described with one string. At least a student’s data always starts with her name, then her age, and then her address, and none of these is ever missing. The name and age are separated by one or more spaces and the age is separated from the address by one or more spaces. There may be leading and trailing spaces in a student’s data.

A student’s name always consists only of uppercase letters ‘A’-'Z’ and embedded (not leading or trailing) spaces. A student’s age always consists of exactly 1, 2, or 3 digits, and its leading digit is not a zero. A student’s address always contains at least one non-space character.

We need to find the name of the oldest student. If there are several, we want the one that appears earliest in the data. The name should include its embedded spaces (even if there are several consecutive embedded spaces), but no leading spaces and no trailing spaces.

Create a class OldestOne that contains a method oldest that is given a string[] data where each element is the data for a student, and that returns the name of the oldest student. 

Here my code:

public class OldestOne
    {
        public string oldest(string[] data)
        {
            string pattern = "[1234567890]";
            string res = "";
            int max = 0;
            for (int i = 0; i < data.Length; i++)
            {
                Regex r = new Regex(pattern);
                string name = data[i].Substring(0, r.Match(data[i]).Index - 1);
                string age = data[i].Substring(r.Match(data[i]).Index, 3);
                if (age[2] == ' ')
                    age = age.Remove(2, 1);
                if (age[1] == ' ')
                {
                    if(age.Length > 2)
                        age = age.Remove(1, 2);
                    else
                        age = age.Remove(1, 1);
                }
                if (int.Parse(age) > max)
                {
                    max = int.Parse(age);
                    res = name;
                }
            }
            while (res[0] == ' ')
                res = res.Remove(0, 1);
            while(res[res.Length - 1] == ' ')
                res = res.Remove(res.Length - 1,1);
            return res;
        }
    }

If you have another approach, please share with me in a comment!

Thank you very much

Practice Room SRM 176 DIV 2, Problem 500 Rep

Here a new problem I´ve solved right now!

Here i decided to create an array with all the possibilities and use a counter to go throught them, then with a for loop, check if the first[i] and second[i] are equal, if they are, then put in the result the same, and if not check if the elements in the array are != to first[i] and second[i], then add the other possibilitie to the result. At the end of each iteration of the for loop, increment the counter +3.

Here the problem statement:

You are playing a game in which you have to find sets of three cards that share certain characteristics. Each card has some symbols on it. Each symbol is either a circle, a squiggle, or a diamond. Each symbol is either colored blue, red, or green. Each symbol is either solid, striped, or empty. And finally each card has either one, two, or three occurrences of the same symbol. A set is formed by three cards, and each characteristic is either the same on all three cards or different on all three cards.

For example, a card with one solid blue diamond, a card with two solid green diamonds, and a card with three solid red diamonds all form a set. The symbols on each card have the same shape and the same shading, and none of the cards has the same number or the same color. Any two cards will form a set with exactly one other card. You want to know, given two cards, what is the other card that completes the set. Create a class Matching with a method findMatch that takes two string[]s, first and second, representing the characteristics of two cards, and returns a string[] representing the characteristics of the third card.

first and second will both contain exactly four elements. The first element of each will denote the shape of the symbols on the card and will be either “CIRCLE”, “SQUIGGLE”, or “DIAMOND”. The second element will denote the color and will be either “RED”, “BLUE”, or “GREEN”. The third element of each will denote the shading and will be either “SOLID”, “STRIPED”, or “EMPTY”. The fourth element of each will denote the number of symbols, and will be either “ONE”, “TWO”, or “THREE”. The return element should contain exactly four elements, and should follow the same format as the input. 

Here my code:

public class Matching
    {
        public string[] findMatch(string[] first, string[] second)
        {
            string[] temp1 = { "DIAMOND", "CIRCLE", "SQUIGGLE", "GREEN", "BLUE", "RED", "SOLID", "EMPTY", "STRIPED", "ONE", "TWO", "THREE" };
            string[] res = new string[4];
            int index = 0;
            for (int i = 0; i < first.Length; i++)
            {
                if (first[i] == second[i])
                    res[i] = first[i];
                else
                {
                    for (int a = index; a < temp1.Length; a++)
                    {
                        if (temp1[a] != first[i] && temp1[a] != second[i])
                        {
                            res[i] = temp1[a];
                            break;
                        }
                    }
                }
                index += 3;
            }
            return res;
        }
    }

If you have another approach, please share with me in a comment!

Thank you very much

Practice Room SRM 175 DIV 2, Problem 250 Rep

Here a new problem I´ve solved right now!

First i get all the times each letter is repeated, then get the maximum.. then check foreach time the maximum is repeated, and then go removing all the letters from candidates and from each element in ballots.

Here the problem statement:

Many elections are decided by plurality voting, which means that the winning candidate is the one who earns more votes than any other candidate. Such elections are susceptible to the phenomenon of vote splitting. Several candidates with similar views may draw support from the same voting base, thereby losing to a single candidate who holds less popular views. One remedy for vote splitting is a runoff election, where the field of candidates is narrowed down through successive rounds of voting until one candidate wins a majority of the vote.

The scheme known as instant runoff voting, or IRV, is intended to accomplish the same result as a runoff election without incurring the expense of multiple voting rounds. In an IRV election, each voter uses a slip of paper called a ballot to rank the slate of n candidates from 1 to n. The ballots are tallied as follows.

1. If one candidate is ranked first on more than half of all ballots, this candidate is declared the winner.

2. Otherwise, the candidate with the fewest number-one rankings is eliminated from all ballots, and each voter’s ranking is adjusted as necessary. If a voter ranked this candidate first, for instance, the number-one rank on her ballot is now reallocated to her second-ranked candidate, and so on down the line. If several candidates are tied for fewest number-one rankings, all of them are eliminated in this fashion.

3. If no candidates remain, the election is declared void. Otherwise, return to step 1.

For an election with n candidates, you are given a string containing n distinct upper-case letters, each of which represents a candidate. You are also given a string[] encoding all ballots cast by the voting public. Each ballot ranks the candidates from most favored to least favored. If n is 5, for example, the candidates might be encoded as “PQRST”, and some voter may rank them on her ballot as “SRTQP”, signifying that she ranks candidate S first and candidate P fifth.

Tally the ballots as described above to determine the outcome of the election. If the election is void, return an empty string. Otherwise, return a single-character string containing the candidate’s code. 

Here my code:

public class InstantRunoff
    {
        public string outcome(string candidates, string[] ballots)
        {
            if (candidates.Length == 1)
                return candidates;
            while(candidates.Length > 1)
            {
                int[] abc = new int[candidates.Length];
                for (int a = 0; a < ballots.Length; a++)
                {
                    if (ballots[a].Length > 0)
                    {
                        if (candidates.Contains(ballots[a][0].ToString()))
                            abc[candidates.IndexOf(ballots[a][0].ToString())]++;
                    }
                }
                int indexMin = 99;
                int index = 0;
                for (int c = 0; c < abc.Length; c++)
                {
                    if (abc[c] < indexMin)
                    {
                        indexMin = abc[c];
                        index = c;
                    }
                }
                for (int d = abc.Length - 1; d >= 0; d--)
                {
                    if (abc[d] == indexMin)
                    {
                        string letter = candidates[d].ToString();
                        candidates = candidates.Remove(d, 1);
                        for (int j = 0; j < ballots.Length; j++)
                        {
                            if (ballots[j].Contains(letter))
                                ballots[j] = ballots[j].Remove(ballots[j].IndexOf(letter), 1);
                        }
                    }
                }
                if (candidates.Length == 0)
                    return "";
            }
            return candidates;
        }
    }

If you have another approach, please share with me in a comment!

Thank you very much