Problem Statement
9 numbers need to be arranged in a magic number square. A magic number square is a square of numbers that is arranged such that every row and column has the same sum. For example:
1 2 3
3 2 1
2 2 2
Create a class MNS containing a method combos which takes as an argument a int[] numbers and returns the number of distinct ways those numbers can be arranged in a magic number square. Two magic number squares are distinct if they differ in value at one or more positions. For example, there is only one magic number square that can be made of 9 instances of the same number.
Showing posts with label TopCoder. Show all posts
Showing posts with label TopCoder. Show all posts
Thursday, February 10, 2011
TopCoder SRM 148, DIV II, DivisorDigits
Problem Statement
Create a class DivDigits containing a method howMany which takes as an argument an int number and returns how many digits in number that number itself is divisible by. Count all occurences of such digits in the number, not just the first. See examples for more information.
Create a class DivDigits containing a method howMany which takes as an argument an int number and returns how many digits in number that number itself is divisible by. Count all occurences of such digits in the number, not just the first. See examples for more information.
TopCoder SRM 148, DIV II, CeyKaps
Problem Statement
The keycaps on a keyboard have been switched around, and the user is now trying to remember what he was trying to type.
Create a class CeyKaps containing the method decipher that takes a String typed, representing the visible message on the screen, and a String[] switched, representing the keycap switches. The method should return the original intended message (what keys the user thought he was pressing).
A keycap can be switched around more than once. For example, if someone switched around 'A' and 'S', then switched around 'S' and 'D', then 'D' would be where 'A' originally was, 'S' where 'D' was, and 'A' where 'S' was.
The elements of switches will be formatted as (quotes added for clarity) "*:*", where the *'s represent the keycaps to be switched. The above example would be represented as: {"A:S","S:D","D:A"}, or alternately as {"S:A","D:S","A:D"} or any other such combination. The order of the keycaps doesn't matter, but the order of the switches does.
The keycaps on a keyboard have been switched around, and the user is now trying to remember what he was trying to type.
Create a class CeyKaps containing the method decipher that takes a String typed, representing the visible message on the screen, and a String[] switched, representing the keycap switches. The method should return the original intended message (what keys the user thought he was pressing).
A keycap can be switched around more than once. For example, if someone switched around 'A' and 'S', then switched around 'S' and 'D', then 'D' would be where 'A' originally was, 'S' where 'D' was, and 'A' where 'S' was.
The elements of switches will be formatted as (quotes added for clarity) "*:*", where the *'s represent the keycaps to be switched. The above example would be represented as: {"A:S","S:D","D:A"}, or alternately as {"S:A","D:S","A:D"} or any other such combination. The order of the keycaps doesn't matter, but the order of the switches does.
Tuesday, February 8, 2011
TopCoder SRM 147, DIV II, PeopleCircle
Problem Statement
There are numMales males and numFemales females arranged in a circle. Starting from a given point, you count clockwise and remove the K'th person from the circle (where K=1 is the person at the current point, K=2 is the next person in the clockwise direction, etc...). After removing that person, the next person in the clockwise direction becomes the new starting point. After repeating this procedure numFemales times, there are no females left in the circle.
Given numMales, numFemales and K, your task is to return what the initial arrangement of people in the circle must have been, starting from the starting point and in clockwise order.
For example, if there are 5 males and 3 females and you remove every second person, your return String will be "MFMFMFMM".
There are numMales males and numFemales females arranged in a circle. Starting from a given point, you count clockwise and remove the K'th person from the circle (where K=1 is the person at the current point, K=2 is the next person in the clockwise direction, etc...). After removing that person, the next person in the clockwise direction becomes the new starting point. After repeating this procedure numFemales times, there are no females left in the circle.
Given numMales, numFemales and K, your task is to return what the initial arrangement of people in the circle must have been, starting from the starting point and in clockwise order.
For example, if there are 5 males and 3 females and you remove every second person, your return String will be "MFMFMFMM".
TopCoder SRM 147, DIV II, CCipher
Problem Statement
Julius Caesar used a system of cryptography, now known as Caesar Cipher, which shifted each letter 2 places further through the alphabet (e.g. 'A' shifts to 'C', 'R' shifts to 'T', etc.). At the end of the alphabet we wrap around, that is 'Y' shifts to 'A'.
We can, of course, try shifting by any number. Given an encoded text and a number of places to shift, decode it.
For example, "TOPCODER" shifted by 2 places will be encoded as "VQREQFGT". In other words, if given (quotes for clarity) "VQREQFGT" and 2 as input, you will return "TOPCODER". See example 0 below.
Julius Caesar used a system of cryptography, now known as Caesar Cipher, which shifted each letter 2 places further through the alphabet (e.g. 'A' shifts to 'C', 'R' shifts to 'T', etc.). At the end of the alphabet we wrap around, that is 'Y' shifts to 'A'.
We can, of course, try shifting by any number. Given an encoded text and a number of places to shift, decode it.
For example, "TOPCODER" shifted by 2 places will be encoded as "VQREQFGT". In other words, if given (quotes for clarity) "VQREQFGT" and 2 as input, you will return "TOPCODER". See example 0 below.
Monday, February 7, 2011
TopCoder SRM 192, DIV II, BoxLoader
Problem Statement
Your company has a new box loading robot. It is your job to program it to pack items into the shipping boxes. The robot does not have a very large program memory so you are restricted to placing all the items into the boxes in the same orientation. Each item is a rectangular solid with dimensions itemX by itemY by itemZ. The box is also rectangular with the dimensions boxX by boxY by boxZ. The items can be placed in the box in any orthogonal orientation (ie. the sides of the items must be parallel to the sides of the box), but only whole items can be placed in the box. Your task here is to determine the greatest number of items that can be packed into the box (with all the items in the same orientation).
For example, if the box is 100x98x81 units and the items are 3x5x7 units, then orienting the items so they are 5x7x3, allows them to fit in the box in a 20x14x27 grid, filling the entire box, which is optimal: 7560 items.
Your company has a new box loading robot. It is your job to program it to pack items into the shipping boxes. The robot does not have a very large program memory so you are restricted to placing all the items into the boxes in the same orientation. Each item is a rectangular solid with dimensions itemX by itemY by itemZ. The box is also rectangular with the dimensions boxX by boxY by boxZ. The items can be placed in the box in any orthogonal orientation (ie. the sides of the items must be parallel to the sides of the box), but only whole items can be placed in the box. Your task here is to determine the greatest number of items that can be packed into the box (with all the items in the same orientation).
For example, if the box is 100x98x81 units and the items are 3x5x7 units, then orienting the items so they are 5x7x3, allows them to fit in the box in a 20x14x27 grid, filling the entire box, which is optimal: 7560 items.
TopCoder SRM 293, DIV II, Aquarium
Problem Statement
You have a fish aquarium. You are given a int[] fishSizes, denoting the size of each fish in the aquarium. They've been getting along pretty well so far, but you would now like to add a new fish (called Bob). You know that fish sometimes eat each other. You estimate that a fish might eat another fish if and only if it is at least two times larger, but no more than ten times larger, than that other fish.
Considering this, you would like to choose Bob's size such that:
- Bob is not in danger of being eaten by any other fish (i.e., its size is not between 1/10 and 1/2, inclusive, the size of any other fish).
- Bob is not tempted to eat any other fish (i.e., no other fish in the aquarium has a size between 1/10 and 1/2, inclusive, of Bob's size).
Your task is to return the number of different integer sizes for Bob between minSize and maxSize, inclusive, that won't cause any eating "conflicts" with other fish.
You have a fish aquarium. You are given a int[] fishSizes, denoting the size of each fish in the aquarium. They've been getting along pretty well so far, but you would now like to add a new fish (called Bob). You know that fish sometimes eat each other. You estimate that a fish might eat another fish if and only if it is at least two times larger, but no more than ten times larger, than that other fish.
Considering this, you would like to choose Bob's size such that:
- Bob is not in danger of being eaten by any other fish (i.e., its size is not between 1/10 and 1/2, inclusive, the size of any other fish).
- Bob is not tempted to eat any other fish (i.e., no other fish in the aquarium has a size between 1/10 and 1/2, inclusive, of Bob's size).
Your task is to return the number of different integer sizes for Bob between minSize and maxSize, inclusive, that won't cause any eating "conflicts" with other fish.
TopCoder SRM 337, DIV II, AnagramList
Problem Statement
An anagram of a string is any string that contains the same characters in any order. For example, the anagrams of "tree" are, in alphabetical order: "eert", "eetr", "eret", "erte", "eter", "etre", "reet", "rete", "rtee", "teer", "tere" and "tree".
You will be given a String s and an int i. Return the ith (0-based) anagram of s when listed in alphabetical order. If there is no such anagram, return an empty String.
An anagram of a string is any string that contains the same characters in any order. For example, the anagrams of "tree" are, in alphabetical order: "eert", "eetr", "eret", "erte", "eter", "etre", "reet", "rete", "rtee", "teer", "tere" and "tree".
You will be given a String s and an int i. Return the ith (0-based) anagram of s when listed in alphabetical order. If there is no such anagram, return an empty String.
TopCoder SRM 496, DIV II, Anagram Free
Problem Statement
A string X is an anagram of string Y if X can be obtained by arranging all characters of Y in some order, without removing any characters and without adding new characters. For example, each of the strings "baba", "abab", "aabb" and "abba" is an anagram of "aabb", and strings "aaab", "aab" and "aabc" are not anagrams of "aabb".
A set of strings is anagram-free if it contains no pair of strings which are anagrams of each other. Given a set of strings S, return the size of its largest anagram-free subset. Note that the entire set is considered a subset of itself.
A string X is an anagram of string Y if X can be obtained by arranging all characters of Y in some order, without removing any characters and without adding new characters. For example, each of the strings "baba", "abab", "aabb" and "abba" is an anagram of "aabb", and strings "aaab", "aab" and "aabc" are not anagrams of "aabb".
A set of strings is anagram-free if it contains no pair of strings which are anagrams of each other. Given a set of strings S, return the size of its largest anagram-free subset. Note that the entire set is considered a subset of itself.
Subscribe to:
Posts (Atom)