어제 밤 12시에 열린 매치..
오랜만에 최악의 퍼포먼스를 보이며 방 최하위 디비젼 630위를 달성하는 기염을 토했다.. -_-
덕분에 rating 이 무려 160점 하락.. 다시 블루로 복귀했다.. ㅠ_ㅠ;;
다시 옐로로 올라가려면 75점이나 올려야하는데.. 당분간은 좀 힘들것같다..
아.. SRM 문제가 갈수록 어려워지는거가터..~~
Level1 - TheNewHouseDivOne
more..
Problem Statement
John is obsessed with security. He has several old houses and he wants to build one new. John is very afraid of thieves, so he will choose the location of the new house using the following method. From each of his old houses, he will measure the Manhattan distance to the new house. He will then take the k-th (1 based) shortest distance. The location that minimizes this distance will be the location of his new house.
You are given the locations of his old houses in vector <int>s x and y. The i-th old house is located at (x[i], y[i]). Return the smallest possible k-th distance.
Definition
Class:
TheNewHouseDivOne
Method:
distance
Parameters:
vector <int>, vector <int>, int
Returns:
double
Method signature:
double distance(vector <int> x, vector <int> y, int k)
(be sure your method is public)
Notes
-
The returned value must be accurate to within a relative or absolute value of 1E-9.
-
The Manhattan distance between two points (x1, y1) and (x2, y2) is |x1 - x2| + |y1 - y2|.
-
Several houses can be located at the same point.
Constraints
-
x will contain between 1 and 50 elements, inclusive.
-
x and y will contain the same number of elements.
-
Each element of x will be between -50 and 50, inclusive.
-
Each element of y will be between -50 and 50, inclusive.
-
k will be between 1 and the number of elements in x, inclusive.
Examples
0)
{-1, -1, 1, 1}
{-1, 1, -1, 1}
3
Returns: 2.0
One of the optimal ways is to build a new house at (0, 0).
1)
{-1, -1, 1, 1}
{-1, 1, -1, 1}
2
Returns: 1.0
And here we have four possible locations for the new house - (-1, 0), (1, 0), (0, -1) and (0, 1).
2)
{4, 4, 4, 4, 4, 3, 3, 5, 5}
{7, 7, 7, 4, 4, 5, 6, 5, 6}
9
Returns: 1.5
Some houses are located at the same point.
3)
{30, -15, 24, -23, 43, -8, -6, -47, 23, -11, 43, 6, -18, 44, -46, 16, 32, 31, 13, 9, 22, 25, 4, -44, 38, -41, -20, 41, -35, 7, 25, 39, -36, -20, -5, -38, -15, -22, 0}
{-45, -7, -33, 31, -8, -33, -20, -14, -50, -48, -31, 35, -24, -31, -11, 41, -41, -11, 46, -1, -5, 5, -39, -26, -40, -9, 16, 38, -30, 34, 46, -17, -27, 33, -38, 28, 46, -16, -46}
13
Returns: 32.0
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.
2차원 좌표계에서 n 개의 점이 이미 있고.. 한개의 점을 더 찍을때 이미 있는 점들과의 거리들중에서 k번째로 짧은 거리를 최소화 하기..
흠.. 생각보다 쉽지않은 문제였다..
나같은경우 임의의 두 점 중간에 놓을때 답이 나올거라고 생각했는데.. 잘못된 가정이었다..
이걸 어떻게 푸나.. 했는데 나중에 남의 코드를 보고 좀 어의가 없었다는.. -_-
scale을 0.5 로 해서 임의의 모든점을 다 체크해보면 된다..
근데 왜 하필 0.5 까지만 하면 될까..? 왜 더 촘촘하게 체크할 필요가 없을까..? 여전히 아리송..
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 #include <cmath>
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 999999999.0
11
12 class TheNewHouseDivOne {
13 public:
14
15 double distance(vector <int> x, vector <int> y, int k)
16 {
17 int n;
18 int i, j, l;
19 double v, w;
20 double sum, min1;
21 n = x.size();
22 min1 = INF;
23 for (v = -50.0; v <= 50.0; v += 0.5) {
24 for (w = -50.0; w <= 50.0; w += 0.5) {
25 vector<double> vt;
26 for (i = 0; i < n; i++) {
27 sum = fabs(x[i]-v) + fabs(y[i]-w);
28 vt.push_back(sum);
29 }
30 sort(vt.begin(), vt.end());
31 min1 = min(vt[k-1], min1);
32 }
33 }
34 printf("min1 = %lf\n", min1);
35 return min1;
36 }
37
38 };
Level2 - TheLockDivOne
more..
Problem Statement
John is obsessed with security. Recently he bought a new electronic lock. It is protected by a password containing n digits, where each digit is either zero or one. John decides to change the password every day. On the first day, the password is all zeroes. On each day that follows, he will select one or more digits that all have the same value and change their values (so zeroes become ones, and ones become zeroes). He must select the digits according to the following rules:
During the first 2^n days, he must never use the same password twice.
Each new password must come as early as possible alphabetically while not violating rule 1.
For example, if n is 2, the password on the first day is "00". The next day, he can change one or both 0's to get "01", "10" or "11". Of these possibilities, "01" comes earliest alphabetically. The next day, he can change either the 0 or the 1 to get "11" or "00". He can't choose "00" because it was already used, so he chooses "11". The next day, he can change one or both 1's to get "10", "01" or "00". He has already used "01" and "00", so he must choose "10".
Given ints n and k, return the password that comes latest alphabetically during the first k days.
Definition
Class:
TheLockDivOne
Method:
password
Parameters:
int, long long
Returns:
string
Method signature:
string password(int n, long long k)
(be sure your method is public)
Notes
-
If A and B are two strings of the same length, then A comes earlier alphabetically than B if it contains a smaller character at the first position where the strings differ.
Constraints
-
n will be between 1 and 50, inclusive.
-
k will be between 1 and 2^n, inclusive.
Examples
0)
2
4
Returns: "11"
This is the example from the statement. The password sequence is the following - "00", "01", "11", "10".
1)
3
8
Returns: "111"
"000", "001", "011", "010", "110", "100", "101", "111".
2)
4
6
Returns: "0110"
3)
10
1
Returns: "0000000000"
4)
7
100
Returns: "1111110"
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 - TheEncryptionDivOne
more..
Problem Statement
John is obsessed with security. He is writing a letter to his friend Brus and he wants nobody else to be able to read it. He uses a simple substitution cipher to encode his message. Each letter in the message is replaced with its corresponding letter in a substitution alphabet. A substitution alphabet is a permutation of all the letters in the original alphabet. In this problem, the alphabet will consist of only lowercase and uppercase letters ('a'-'z', 'A'-'Z').
John wants to be sure that his encryption is safe, so he will not choose a cipher where a letter is encoded to either itself or to its lowercase or uppercase equivalent. For example, he will not choose a cipher where the letter 'j' is encoded to either 'j' or 'J'.
Given the original message msg and encoded message encMsg, determine the number of simple substitution ciphers that fit John's requirements and encode msg to encMsg. Return this number modulo 1234567891.
Definition
Class:
TheEncryptionDivOne
Method:
count
Parameters:
string, string
Returns:
int
Method signature:
int count(string msg, string encMsg)
(be sure your method is public)
Constraints
-
msg will contain between 1 and 50 characters, inclusive.
-
msg and encMsg will contain the same number of characters.
-
msg and encMsg both will contain only lowercase and uppercase letters ('a' - 'z', 'A' - 'Z').
Examples
0)
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWX"
"cdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
Returns: 2
Here we have to choose how to encode to letters 'Y' and 'Z' with two letters 'a' and 'b'. There are two ways to do it.
1)
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWX"
"bcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXY"
Returns: 1
And here John needs to encode 'Y', 'Z' with 'Z' and 'a'. He cannot map 'Z' to itself, so there is only one possible encoding.
2)
"topcoder"
"TOPCODER"
Returns: 0
3)
"thisisaveryhardproblem"
"nobodywillsolveittoday"
Returns: 0
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..
