밤 12시에 열린 매치.. 무척 아쉬운 한판이었다.. rating 좀 올릴수 있는 기회였는데.. 통한의 리서밋때문에.. ㅠ_ㅠ 젱장.. 게다가 250은 틀리는사람이 한명도없었다.. 이거 뭥미..;; 안그래도 550 & 950 set 인걸 보고.. 불안했는데.. 역시나..!! rating은 소폭 하락.. 2부리그 추락은 간신히 막았다..
방 16등 전체 499등 .. OTL ㅠ_ㅠ
[250] FIELDDiagrams
Problem Statement
A Ferrers diagram of the partition of positive number n = a1 + a2 + ... + ak, for a list a1, a2, ..., ak of k positive integers with a1 ≥ a2 ≥ ... ≥ ak is an arrangement of n boxes in k rows, such that the boxes are left-justified, the first row is of length a1, the second row is of length a2, and so on, with the kth row of length ak. Let's call a FIELD diagram of order fieldOrder a Ferrers diagram with a1 ≤ fieldOrder, a2 ≤ fieldOrder - 1, ..., ak ≤ fieldOrder - k + 1, so a FIELD diagram can have a number of rows which is less than or equal to fieldOrder. Your method will be given fieldOrder, it should return the total number of FIELD diagrams of order fieldOrder. Definition
Class: FIELDDiagrams Method: countDiagrams Parameters: int Returns: long long Method signature: long long countDiagrams(int fieldOrder) (be sure your method is public)
Constraints - fieldOrder will be between 1 and 30, inclusive Examples 0)
2 Returns: 4
There are four possible FIELD diagrams for fieldOrder equal to 2, corresponding to partitions: (1), (2), (1, 1), (2,1). They are shown in the picture below. There white stands for unused space in a row and red for boxes, corresponding to FIELD diagrams.
1)
3 Returns: 13
2)
5 Returns: 131
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.
문제가 도대체 뭔소린지..;;
문제는 잘 이해를 못했지만.. sample 보고나서 잽싸게 catalan 수 임을 간파.. 비교적 쉽게 풀었다.. 그런데 문제는 수열의 31번째 항까지 구해야하는데 30항까지만 구하고 서밋했다는거.. ㅠ_ㅠ 막판에 발견하고 리서밋.. ㅠ_ㅠ 덕분에 5등을 했어야할 등수가 16등까지 떨어졌다..
이 문제 푼 사람중 상당수는 catalan이라는 것을 모르고 푼 듯 싶다.. 그런데도 240점 넘는사람은 도대체 뭐냐!!!!
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <vector> 5 #include <string> 6 using namespace std; 7 8 class FIELDDiagrams { 9 public: 10 11 long long countDiagrams(int fieldOrder) 12 { 13 int i, j, k; 14 long long c[50]; 15 memset(c, 0, sizeof(c)); 16 c[0] = 1; 17 for (i = 1; i <= 31; i++) { 18 for (j = 0, k = i-1; j <= i-1; j++, k--) { 19 c[i] += c[j] * c[k]; 20 } 21 } 22 return c[fieldOrder+1]-1; 23 } 24 25 };
[550] ParticleCollision
Problem Statement
Particles (which can be considered points in 3D-space for the purposes of the problem) can move in an electro-magnetic field. If a particle is charged, its trajectory can be described as spiral, and if it is uncharged, it is just a straight line. Given two particles (one charged and one uncharged) it should be determined whether they can possibly collide or not. Two particles can possibly collide if and only if their trajectories intersect. Some steps have already been made by the physicist to simplify the problem, so the coordinates of the charged particle are represented as follows: x1 = cos(PI * t) y1 = sin(PI * t) z1 = t and for the uncharged particle: x2 = vx * t + x0 y2 = vy * t + y0 z2 = vz * t + z0 Here t is a parameter which can be chosen arbitrarily and independently for both trajectories. Your method will be given 6 integers - vx, vy, vz, x0, y0 and z0, describing the trajectory of the uncharged particle. It should determine whether the two given trajectories intersect or not. If they do, it should return a vector <double> containing exactly 3 elements x, y and z - the coordinates of the point where a collision can happen. If there is more than one such point, it should return a vector <double> containing exactly three zeroes. If collision of the two particles is impossible it should return an empty vector <double>. Definition
Class: ParticleCollision Method: collision Parameters: int, int, int, int, int, int Returns: vector <double> Method signature: vector <double> collision(int vx, int vy, int vz, int x0, int y0, int z0) (be sure your method is public)
Notes - PI can be considered equal to 3.14159265358979323846. - All return values with either an absolute or relative error of less than 1.0E-9 are considered correct. Constraints - vx, vy and vz will each be between -10 and 10, inclusive. - x0, y0 and z0 will each be between -10 and 10, inclusive. Examples 0)
0 0 0 0 0 0 Returns: { } The second trajectory is a single point (0, 0, 0), which doesn't lie on the first trajectory. 1)
2 4 1 -1 -1 0 Returns: {0.0, 1.0, 0.5 } There is a single intersection point with coordinates (0, 1, 0.5). 2)
4 4 2 5 4 0 Returns: {0.0, 0.0, 0.0 } There are two intersection points. 3)
0 0 1 1 0 0 Returns: {0.0, 0.0, 0.0 } There are infinitely many intersection points. 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 upated..
[950] nCoolPoints
Problem Statement
You are given a convex polygon and you must count the number of N-cool points. A point is N-cool if it is a lattice point covered by the polygon and also an endpoint of some N-cool segment. A line segment is N-cool if it contains at least N lattice points that are covered by the polygon. A point is considered covered by the polygon if it is inside or on the boundary of the polygon. Endpoints of a segment are considered to be inside of it. A lattice point is a point with integer coordinates. Consider the example in the picture below. Here N is equal to 6, and there are 21 6-cool points, marked green. Also two 6-cool segments, which are colored red, are shown.
You are given vector <int>s x and y describing the vertices of the polygon (in no particular order). The coordinates of each vertex are specified by corresponding elements of x and y. Return the number of N-cool points. Definition
Class: NCool Method: nCoolPoints Parameters: vector <int>, vector <int>, int Returns: int Method signature: int nCoolPoints(vector <int> x, vector <int> y, int n) (be sure your method is public)
Notes - A polygon is convex if it contains all the line segments connecting any pair of its points. Constraints - x and y will each contain between 3 and 50 elements, inclusive. - x and y will contain the same number of elements. - All elements of x and y will be between 0 and 10000, inclusive. - The number of lattice points inside or on the boundary of the specified polygon will not be greater than 500000. - N will be between 2 and 500000, inclusive. - The polygon specified by x and y will be convex and will have nonzero area. Examples 0)
{0, 1, 2, 7, 7} {3, 1, 6, 1, 5} 6 Returns: 21 This is the example from the problem statement. 1)
{0, 1, 0} {0, 0, 1} 2 Returns: 3 These three points form a triangle, whose sides are 2-cool segments, so all three vertices are 2-cool. 2)
{0, 0, 1, 2, 2, 1, 0, 0, 2} {0, 1, 2, 2, 1, 0, 0, 0, 2} 3 Returns: 6 One point can be mentioned in the input two or more times. 3)
{0, 1, 1, 2, 2, 3, 3, 4, 4, 5} {1, 0, 2, 0, 2, 0, 2, 0, 2, 1} 5 Returns: 4 There can be 3 points of the polygon, lying on the same line. 4)
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.
