어제 새벽에 열린 매치..~
이번에도 쉬운문제를 못풀면서.. 어려운 매치가 됐다.. 젠장..
그래도 다행히 챌 하나를 성공시켜서 rating 은 소폭 하락에 그쳤다..
요즘들어서 계속 250 을 못푸는데.. 이거 좀 공부좀 해야겠는데..
Level1 - LotteryCheating
Problem Statement
Bob likes to play the lottery, but it's so hard to win without cheating. Each lottery ticket has an identifier which contains exactly n decimal digits. If an identifier contains only '0's, it is considered a winning ticket. Otherwise, the identifier is interpreted as a positive integer X written in decimal notation (possibly with leading zeros). If X has an odd number of positive integer divisors, it is a winning ticket, otherwise, it is not. A positive integer is a divisor of X if it divides X evenly. Unfortunately, Bob only has enough money to buy one ticket, and he cannot see the identifier before buying a ticket. Therefore, he decides to cheat by buying a ticket and modifying its identifier to make it a winning ticket. In a single change operation, he can choose one digit, erase it, and print some other digit in the same position. No other types of modifications are allowed. He can perform any number of these change operations, but he wants to perform as few as possible to minimize the risk of getting caught. You are given a string ID, the initial identifier on Bob's ticket. Return the minimal number of change operations necessary to transform the identifier into a winning one. If the initial identifier is already a winner, return 0.
Definition
Class:
LotteryCheating
Method:
minimalChange
Parameters:
string
Returns:
int
Method signature:
int minimalChange(string ID)
(be sure your method is public)
Constraints
-
ID will contain between 1 and 10 characters, inclusive.
-
Each character in ID will be between '0' and '9', inclusive.
Examples
0)
"1"
Returns: 0
1 is the only divisor of this identifier. Since there are an odd number of divisors, it is already a winning ticket, and no changes are necessary.
1)
"1234"
Returns: 2
One possible solution is to transform "1234" into "1024". As 1024 is 2^10, it has 11 divisors: 2^0, 2^1, ..., 2^10.
2)
"9000000000"
Returns: 1
Bob can change the '9' into a '0'. The resulting identifier "0000000000" contains only '0's, so it is a winning ticket.
3)
"4294967296"
Returns: 0
The initial identifier represents the integer 2^32, so it has 33 divisors.
4)
"7654321"
Returns: 3
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.
임의의 숫자가 주어질때 약수의 개수가 홀수개가되도록 바꾸고 싶다.. digit 을 최소 몇개를 바꿔야 할까..?
약수의 개수가 홀수개가 되려면 n^2 꼴인 수만 가능하다.. -_-;;
이 사실을 코딩시간 종료 직전에 눈치채는바람에 결국 못풀었다..
왜 그렇게 되는지는 약수의 개수 구하는 공식을 생각해보면 된다..
어떤수를 소인수분해했을때 p1^a1 * p2^a2 * ... * pn^an 일때
약수의 개수 = (a1 + 1) * (a2 + 1) * ... * (an + 1) 가 되는걸 초등학교때 배운것같다.. -_-
따라서 약수의 개수가 홀수가 되려면 a1, a2, ..., an 이 모두 짝수이어야 한다..
위 사실을 알았으면..
일단 미리 n^2 꼴의 수를 모두 저장 해놓고.. input 과 가장 비슷한 수를 brute force 로 찾으면 되겠다..
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 #include <set>
7 using namespace std;
8 //#define min(x, y) ((x) > (y) ? (y) : (x))
9 //#define max(x, y) ((x) > (y) ? (x) : (y))
10 //#define INF 100
11 //#define EPS 1e-14
12
13 class LotteryCheating {
14 public:
15
16 int minimalChange(string ID)
17 {
18 int res;
19 int i, j, k;
20 int len;
21 char buf[100];
22 long long x;
23
24 len = ID.size();
25 res = 10;
26 for (x = 0; x < 100000; x++) {
27 string str;
28 sprintf(buf, "%lld", x*x);
29 str = buf;
30 if (str.size() > len)
31 continue;
32 while (str.size() < len) {
33 str = '0' + str;
34 }
35 k = 0;
36 for (j = 0; j < len; j++) {
37 if (ID[j] != str[j])
38 k++;
39 }
40 if (k < res)
41 res = k;
42 }
43 printf("res = %d\n", res);
44 return res;
45 }
46
47 };
Level2 - LotteryPyaterochka
Problem Statement
Alice likes lotteries. Her favorite lottery is Pyaterochka, which is very popular in Belarus. Each ticket in this lottery is a rectangular grid with N rows and 5 columns, where each cell contains an integer between 1 and 5*N, inclusive. All integers within a single ticket are distinct. After the tickets are distributed, the lottery organizers randomly choose 5 distinct integers, each between 1 and 5*N, inclusive. Each possible subset of 5 integers has the same probability of being chosen. These integers are called the winning numbers. A ticket is considered a winner if and only if it has a row which contains at least 3 winning numbers. Alice will buy a single ticket. Each possible ticket has the same probability of being sold. Return the probability that she will buy a winning ticket.
Definition
Class:
LotteryPyaterochka
Method:
chanceToWin
Parameters:
int
Returns:
double
Method signature:
double chanceToWin(int N)
(be sure your method is public)
Notes
-
Your return value must have an absolute or relative error less than 1e-9.
Constraints
-
N will be between 1 and 100, inclusive.
Examples
0)
1
Returns: 1.0
Any ticket contains just one line with some permutation of numbers 1, 2, 3, 4, 5. Ony one set of winning numbers is possible - {1, 2, 3, 4, 5}. So the only line of any ticket contains all 5 winning numbers, and therefore each ticket is a winner.
1)
2
Returns: 1.0
For any set of winning numbers chosen, there's exactly one line in any ticket that contains at least 3 winning numbers.
2)
3
Returns: 0.5004995004995004
3)
6
Returns: 0.13161551092585574
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.
n by 5 짜리 board 에 1 ~ 5*n 까지 번호가 적혀있다..
random 하게 5개 수를 뽑았을 때, 그 중 3개의 숫가 임의의 한 row 에 있으면 win 이다..
win 할 확률 구하기..
임의의 숫자 5개를 뽑았을 때, 임의의 row 에 3개의 숫자가 걸릴 확률 =
정답중에 3개를 뽑는 가지수 * 정답 아닌거중에 2개를 뽑는 가지수 / 전체중에 임의의 5개 뽑는 가지수
가 된다..
이런걸 조건부 확률 이라는거 같음..
위에 식을 기본으로.. 3개뿐만 아니라, 4개, 5개가 걸릴 경우의 수도 더해주면 된다..
그리고 각 row 에 대해서 확률이 같으므로.. 모든 row 의 개수 n 을 곱해준다..
역시.. 확률은 어렵구만.. ㅠ_ㅠ
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 #define MAXN 502
13 /* combi[n][r] = n C r */
14 long long combi[MAXN][MAXN];
15 void get_combi()
16 {
17 int i, j;
18 for (i = 0; i < MAXN; i++) {
19 combi[i][i] = 1;
20 combi[i][0] = 1;
21 }
22 for (i = 0; i < MAXN; i++) {
23 for (j = 1; j < i; j++) {
24 combi[i][j] = combi[i-1][j-1] + combi[i-1][j];
25 }
26 }
27 }
28
29 class LotteryPyaterochka {
30 public:
31
32 double chanceToWin(int N)
33 {
34 double res;
35 if (N == 1)
36 return 1.0;
37 get_combi();
38
39 res = (double)(N * (combi[5][3]*combi[5*N-5][2] + combi[5][4]*combi[5*N-5][1] + combi[5][5]*combi[5*N-5][0])) / (double)combi[5*N][5];
40 return res;
41 }
42
43 };
Level3 - DrawingBlackCrosses
Problem Statement
Pavel likes puzzles. One of his favorite puzzles is DrawingBlackCrosses. In this puzzle, the player starts with a rectangular grid of cells, where each cell is either white or black, and at most 8 of the cells are black. The player's goal is to achieve the state where all of the cells in the grid are black. To achieve this goal, a sequence of moves must be performed. In each move, a single white cell is selected and all white cells located in the same row and all white cells located in the same column as the selected cell, including the selected cell itself, are colored black. The moves are performed until there are no more white cells. Each solution to this puzzle can be written as a sequence of cells, where the i-th cell in the sequence is the cell that was selected on the player's i-th move. Two solutions are considered to be different if these sequences have different lengths or if there's an index i such that the i-th cells in these sequences are different. You are given a vector <string> field representing the initial state of the grid. The j-th character in the i-th element of field is '.' if the cell in row i, column j of the grid is initially white and 'B' if this cell is initially black. Return the number of different solutions that exist for the given grid, modulo 1000000007.
Definition
Class:
DrawingBlackCrosses
Method:
count
Parameters:
vector <string>
Returns:
int
Method signature:
int count(vector <string> field)
(be sure your method is public)
Constraints
-
field will contain between 1 and 20 elements, inclusive.
-
Each element of field will contain between 1 and 20 characters, inclusive.
-
All elements of field will have the same length.
-
Each character in field will be either 'B' or '.'.
-
field will contain no more than 8 'B' characters.
Examples
0)
{"."}
Returns: 1
Only one possible move.
1)
{"BBB",
"BBB"}
Returns: 1
No moves are necessary here since all the cells are already black.
2)
{"...",
"BB."}
Returns: 5
Let's number rows and columns of the grid as follows:
012
0 ...
1 BB.
The following sequences of moves are possible (the first coordinate of each cell is its row number, the second coordinate is column number): 1. (0, 0), (1, 2); 2. (0, 1), (1, 2); 3. (0, 2); 4. (1, 2), (0, 0); 5. (1, 2), (0, 1).
3)
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.
