Fox Jiro likes dice. He wants to make his own dice. Each die he wants to make is a cube. Each of the 6 faces has an integer between 1 and N, inclusive. No two faces have same number. Also the following condition must be satisfied: for all faces, the sum of the numbers on opposite faces must be equal and the sum must be greater than or equal to K.
He realized that there are many ways to make such dice. He wants to know how many ways there are. Please help Jiro to make a program that is given two integers N and K and returns the number of different dice satisfying the condition mentioned above.
Two dice are considered the same if you can rotate one to form the other.
Definition
Class:
FoxMakingDice
Method:
theCount
Parameters:
int, int
Returns:
long long
Method signature:
long long theCount(int N, int K)
(be sure your method is public)
Notes
-
The answer will always fit in a signed 64-bit integer.
Constraints
-
N will be between 1 and 1,000, inclusive.
-
K will be between 1 and 2,000, inclusive.
Examples
0)
6
7
Returns: 2
You can make normal dice. There are two ways to arrange the numbers.
1)
5
7
Returns: 0
You cannot make 6 sided dice with 5 numbers.
2)
1000
1
Returns: 20625666000
3)
456
123
Returns: 879075732
4)
913
1014
Returns: 4506149340
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
주사위에 나올 수 있는 숫자는 1~N 이라고 하고 서로 반대되는 면의 합은 K 이상이 되도록 만들 수 있는 서로 다른 주사위 개수 구하고.. 단, 모든면은 다 다른 숫자가 적혀있어야 한다.. rotate 해서 같은 모양이 되면 같은 주사위로 취급
a + b >= K 가 되는 서로다른 pair (a, b) 의 개수를 구한다.. 그게 n 이라고 한다면
이런 pair 가 3개가 있어야 하므로.. 답은 2 * choose(n, 3) 이 된다
2 를 곱하는 이유는.. (a, b), (c, d), (e, f) 를 rotate 해서 (a, b), (c, d), (f, e) 를 만들 수 없어서 인가..?
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7 //#define min(x, y) ((x) > (y) ? (y) : (x))
8 //#define max(x, y) ((x) > (y) ? (x) : (y))
9 //#define INF 999999999
10 //#define EPS 1e-14
11
12 class FoxMakingDice {
13 public:
14
15 long long theCount(int N, int K)
16 {
17 int i;
18 long long a, b;
19 long long cnt, res;
20 res = 0;
21 for (i = K; i <= N+N; i++) {
22 cnt = 0;
23 for (a = 1; a <= N; a++) {
24 b = i - a;
25 if (b > N || b <= a)
26 continue;
27 cnt++;
28 }
29 res += cnt * (cnt-1) * (cnt-2) / 3;
30 }
31 return res;
32 }
33
34 };
Level2 - PrefixTree
Problem Statement
A prefix tree (also called trie) is a rooted tree data structure used to efficiently store a set of words, S. In a trie every edge has a letter associated with it. Every node in the trie is associated with the string which we get when we read all the edge letters on the path from the root to this node. So the root of the trie is associated with the empty string and every leaf of the trie is associated with some word from S.
A trie is constructed so that from each node at most one child edge is associated with each letter. So not only do all the descendants of a node have a common prefix (which is the string associated with this node) but also every word with this string as prefix is the descendant of this node. It is necessary that for every word from S there is a node in trie with which is this word associated.
An example of a trie for the set of words {"aab", "ca"}:
It is not hard to see that if we change the order of letters in the given words then we will get a different trie (constructed from these different words) which might possibly have fewer nodes.
For example the trie constructed from words {"aab","ca"} would have 6 nodes (see image above), but if we change "ca" to "ac" then the trie would have only 5 nodes:
Given vector <string> words which represents the set of words. You are allowed to permute the letters in each word in any way you like. Find the optimal permutation of the letters of the words so the trie constructed from them would have the minimal number of nodes. Return this number of nodes.
Definition
Class:
PrefixTree
Method:
getNumNodes
Parameters:
vector <string>
Returns:
int
Method signature:
int getNumNodes(vector <string> words)
(be sure your method is public)
Constraints
-
words will contain between 1 and 16 elements, inclusive.
-
Each element of words will contain between 1 and 50 characters.
-
Each element of words will consist of lowercase letters ('a'-'z').
Examples
0)
{"topcoder"}
Returns: 9
With only one word, every permutation gives the same answer.
1)
{"topcoder","topcoder"}
Returns: 9
Words in the input can repeat. The optimal permutation is the one in which the words are equal.
2)
{"aab","ca"}
Returns: 5
Example from the problem statement. The optimum is if we change "ca" to "ac".
3)
{"aab","ca","ba"}
Returns: 5
The optimum is when the words are: "aba", "ac", "ab".
4)
{"ab","cd","ef"}
Returns: 7
Sometimes nothing can be optimized.
5)
{"a","aa","aaa"}
Returns: 4
One word can be also a prefix of another word.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
to be updated..
Level3 - FoxCardGame
Problem Statement
Fox Jiro and Haruko play a game with two piles of cards: pile A and pile B. Pile A and pile B contain same number of cards. Each card contains a real number between 1.0 and 100.0. Initially, the two players have 0 points. Then they repeat following operations exactly k times:
They choose two cards from the piles (one from pile A and another from pile B).
The choosen cards are removed from the piles.
Jiro earns max{a+b, a*b} points and Haruko earns min{a+b, a*b} points (where a and b are the numbers written on the two cards that were removed).
You are given a vector <double> pileA, a vector <double> pileB, and an int k. Return the maximal possible value of (Jiro's points) / (Haruko's points).
Definition
Class:
FoxCardGame
Method:
theMaxProportion
Parameters:
vector <double>, vector <double>, int
Returns:
double
Method signature:
double theMaxProportion(vector <double> pileA, vector <double> pileB, int k)
(be sure your method is public)
Notes
-
The returned value must have an absolute or relative error less than 1e-9.
Constraints
-
pileA and pileB will contain between 1 and 50 elements, inclusive.
-
pileA and pileB will contain the same number of elements.
-
Each element of pileA and pileB will be between 1.0 and 100.0, inclusive.
-
k will be between 1 and the number of elements in pileA, inclusive.
Examples
0)
{1, 2, 3}
{4, 5, 6}
2
Returns: 1.7692307692307692
Choosing cards with numbers 3 and 6, Jiro earns 3*6 = 18 points and Haruko earns 3+6 = 9 points.
Choosing cards with numbers 1 and 4, Jiro earns 1+4 = 5 points and Haruko earns 1*4 = 4 points.
So the solution is (18+5) / (9+4) = 1.769230...
1)
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
