TopCoder SRM 362 Div 2

처음 탑코더를 해보았다.. ㅎㅎ 생각보다 재밌다..
초반부터 삽질에 삽질을 거듭했지만..
같은방에있는 사람들도 다 비슷한 모양이다..;;
결국 3등..~ -_-;;
failed challenge가 하나 있었지만.. 시스템오류로인해 카운트되지않았다.. ;;
근데.. 다들 코드를 이상하게 짜던데.. challenge를 안받을려고하는 고도의 작전인가..;;
 

  
[250] ThrowTheBall

Problem Statement
     
There are N friends sitting in a circle, numbered clockwise in increasing order from 1 to N. At the beginning of the game, player 1 receives a ball. The players take turns passing the ball to each other. At the beginning of the game and before each next pass the following actions are performed. If the player with the ball has already received the ball M times, the game is over. Otherwise, if the player has received the ball p times, he'll pass the ball directly to the person L places to his left if p is even, or L places to his right if p is odd (see examples for clarification). Given N, M and L, return the number of times that the ball is passed.
Definition
    
Class:
ThrowTheBall
Method:
timesThrown
Parameters:
int, int, int
Returns:
int
Method signature:
int timesThrown(int N, int M, int L)
(be sure your method is public)
     
 
Constraints
-
N will be between 3 and 50, inclusive.
-
M will be between 1 and 50, inclusive.
-
L will be between 1 and N-1, inclusive.
Examples
0)
 
     
5
3
2
Returns: 10
First, player 1 gets the ball. Since he has held the ball 1 time, he passes the ball to player 4, who is two places to his right. This is player 4's first time holding the ball, so he gives it to player 2, who passes it to player 5. Player 5 then passes the ball to player 3, who passes it back to player 1. Since player 1 has now held the ball 2 times, he passes it to player 3, who passes it to player 5, who then passes the ball to player 2. Finally, player 2 passes the ball to player 4, who then passes it to player 1. Player 1 has now held the ball 3 times, and the game ends.
1)
 
     
4
1
3
Returns: 0
Here, the ball is never passed.
2)
 
     
10
3
5
Returns: 4
 
3)
 
   
15
4
9
Returns: 15

지금까지 공을 받은 횟수가 홀수이면 오른쪽, 짝수이면 왼쪽으로 공을 L칸만큼 패스..
그러다가 누군가 공을 M번 받으면 끝내고, 몇번 공을 패스했는지 찍어주는 문제..
그냥 simulation 했다..
 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
 
class ThrowTheBall {
public:
 
int timesThrown(int N, int M, int L)
{
    int check[100];
    int cnt, cur;
 
    memset(check, 0, sizeof(check));
    check[0] = 1;
 
    if (M == 1)
        return 0;
    cnt = 0;
    cur = 0;
    while (1) {
        if (check[cur] & 1) {
            cur -= L;
            while (cur < 0)
                cur += N;
        }
        else {
            cur += L;
            cur %= N;
        }
        cnt++;
        check[cur]++;
        if (check[cur] == M)
            break;
    }
    return cnt;
}
 
};

 [500] MaximizeSquares

Problem Statement
     
Consider an arrangement of N points on the cartesian plane. The "square count" of the points is the total number of distinct squares with sides parallel to the coordinate axes which can be built using 4 different points as vertices. Your task is to return the maximum square count, considering all possible arrangements of N points on the plane.
Definition
   
Class:
MaximizeSquares
Method:
squareCount
Parameters:
int
Returns:
int
Method signature:
int squareCount(int N)
(be sure your method is public)
   
 
Notes
-
Two squares are distinct if at least one of their corners is in a different location.
Constraints
-
N will be between 0 and 1000000, inclusive.
Examples
0)
 
     
4
Returns: 1
Clearly, we can only make one square out of 4 points.
1)
 
     
5
Returns: 1
No matter where we place a fifth point, we can't get any extra squares.
2)
 
     
6
Returns: 2
We can get 2 squares by placing the points in the shape of a rectangle.
3)
 
     
16
Returns: 14
 
4)
 
   
115
Returns: 340

N개의 점이 있을때, 임의의 4개의 점을 선택해서 서로 다른 정사각형(단, 네변은 x축, y축과 평행)을 최대 몇개 만들 수 있는지 구하는 문제..
 
우선 모든 점들을 채워서 만들 수 있는 가장 큰 정사각형을 만든다.. 그리고나서 남은 점들을 한쪽 변에 나란히 붙인다.. 그리고 나서 정사각형의 개수를 센다.. -_-;
급한 마음에 막판에 코드가 이상해졌음..;;
 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
 
class MaximizeSquares {
public:
int squareCount(int N) {
    int i;
    int n, cnt;
    int temp, temp2;
    if (N <= 3)
        return 0;
    n = (int)(sqrt((double)N)+0.0000001);
    cnt = 0;
    for (i = 1; i < n; i++) {
        cnt += i*i;
    }
 
    N -= n*n;
 
    temp = N / n;
    temp2 = N % n;
    if (temp == 1) {
        cnt += n * (n-1) / 2;
        cnt += temp2 * (temp2-1) / 2;
    }
    else if (temp == 2) {
        cnt += n * (n-1);
    }
    else {
        cnt += temp2 * (temp2-1) / 2;
    }
 
    return cnt;
}
 
};

 
[1000] SignificanceArithmetic

Problem Statement
   
Significance arithmetic is a set of rules used in scientific calculations, and is used extensively in scientific application software. Specifically, significance arithmetic is used to determine the correct number of significant digits, or measured digits, in a calculation. The significant digits in a number are all its digits except for leading zeros that are two or more places to the left of the decimal point. For instance, 00.30, 0.00 and 0.60 each contain three significant digits, while 5 and 00 each only contain one significant digit.  We need to compute the result of the addition of two numbers. The result must be rounded to n significant digits, where n is determined as follows: First determine the number with the least number of digits to the right of the decimal point (this may be zero). Then the result will not contain any significant digits to the right of this digit, and all other digits are significant (except leading zeros that are two or more places to the left of the decimal point). For example, the result of 1.56 + 1236.1 will have only one significant digit immediately to the right of the decimal point, but all digits to the left of the decimal point will be significant.  There are several cases to consider when rounding a number to n significant digits: 1) If the number has less than n significant digits, the number is padded with trailing zeros. For example, 2.5 rounded to 3 significant digits is 2.50. 2) If the digit immediately to the right of the nth digit is greater than 5, the number is rounded up. For example, 2.56 rounded to 2 significant digits is 2.6. 3) If the digit immediately to the right of the nth digit is less than 5, the number is rounded down. For example, 2.54 rounded to 2 significant digits is 2.5. 4) If the digit immediately to the right of the nth digit is 5 and there are non-zero digits after the 5, the number is rounded up. For example, 2.551 rounded to 2 significant digits is 2.6. 5) If the digit immediately to the right of the nth digit is 5 and there are no subsequent non-zero digits, then the number is rounded whichever way leaves the nth digit even. For example, 2.55 rounded to 2 significant digits is 2.6, but 2.45 rounded to 2 significant digits is 2.4.  You will be given an expression as a String that will contain two numbers that are separated by a '+'. Each number will contain a non-empty integral part, as well as an optional fractional part which, if present, will be preceded by a decimal point. The numbers may contain leading zeros, and will always be positive. Examples of valid numbers are 0.456, 004.0, and 0. However, .025 is invalid because it has no integral part, and 45. is invalid because a fractional part must follow the decimal point.  Your result should be in the same format as described above. However, there should only be a leading zero if the integral part of the number is 0. For example, 0.00450 is a valid result, while 0459.2 is not.
Definition
   
Class:
SignificanceArithmetic
Method:
evaluate
Parameters:
String
Returns:
String
Method signature:
String evaluate(String expression)
(be sure your method is public)
   
 
Notes
-
Numbers in expression may contain leading zeros.
Constraints
-
expression will contain two numbers that are separated by a '+'.
-
Each number in expression will be a real number containing between 1 and 6 digits, inclusive (not including the decimal point).
-
Each number in expression will be formatted exactly as described in the problem statement.
Examples
0)
 
     
"2+2"
Returns: "4"
Two has one significant digit, so the result will as well.
1)
 
   
"1.234+0.000"
Returns: "1.234"
All digits here are significant.
2)
 
   
"1.234+0.006"
Returns: "1.240"
Again, all digits here are significant. Therefore the result will contain the same number of significant digits, and rounding rule #1 is used.
3)
 
   
"12.57+2.6"
Returns: "15.2"
12.45 + 2.6 = 15.17. Rounding rule #2 is used.
4)
 
   
"5.50005+0"
Returns: "6"
The only significant digit here is the one immediately to the left of the decimal point, and rounding rule #4 is used.
5)
 
     
"2.5+2"
Returns: "4"
Again, the only significant digit here is the one immediately to the left of the decimal point. Here, rounding rule #5 is used.
6)
 
     
"0.00+000"
Returns: "0"
 
7)
 
     
"983.17+76.8"
Returns: "1060.0"

1000점짜리는.......
너무 길어서 안읽어봤다.. ㅠ_ㅠ



문제상의 문제로 이번 SRM은 rating에 영향을 주지 않았다..
덕분에 파란색에서 다시 not rated로 빽..~ -_-