저녁 9시에 열렸던 매치.. 이번에도 간신히 한문제 풀었다.. 250점 같은경우는 매우 쉬운문제인데.. 문제해석이 오래걸려서 고생했다.. 500점도 거의 풀수있었는데.. 막판에 시간이 모잘라서 submit조차 못해보았다.. 덕분에 rating은 하락..! 간신히 2군 강등은 모면했다..
방 17등 전체 468등..
[250] ApproximateDivision
Problem Statement
Division is an expensive operation for a computer to perform, compared to addition, subtraction, and even multiplication. The exception is when dividing by powers of 2, because this can be done either with a bit shift (for a fixed-point value) or by subtracting 1 from the exponent (for a floating-point value). In this problem, we will approximate the quotient of two numbers using only addition, multiplication, and division by powers of 2. Consider the following identity:
1 1 c^0 c^1 c^2 --- = ----- = ----- + ----- + ----- + ... b t-c t^1 t^2 t^3 If t is a power of 2, then the denominator of each term will be a power of 2. Given integers a, b, and terms, approximate a/b by computing the first terms terms of the identity above, and multiplying the result by a. Select t to be the smallest power of 2 greater than or equal to b. Definition
Class: ApproximateDivision Method: quotient Parameters: int, int, int Returns: double Method signature: double quotient(int a, int b, int terms) (be sure your method is public)
Notes - Your return value must have an absolute or relative error less than 1e-9. Constraints - b will be between 1 and 10000, inclusive. - a will be between 0 and b, inclusive. - terms will be between 1 and 20, inclusive. Examples 0)
2 5 2 Returns: 0.34375 In this case t is chosen to be 8, and therefore c is 3. The first two terms are 1/8 and 3/64. 1)
7 8 5 Returns: 0.875 If b is a power of two, the first term is equal to exactly 1/b, and all other terms are zero. 2)
1 3 10 Returns: 0.33333301544189453
3)
1 10000 2 Returns: 8.481740951538086E-5
4)
1 7 20 Returns: 0.14285714285714285
5)
0 4 3 Returns: 0.0
6)
50 50 1 Returns: 0.78125
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.
input으로 a, b, terms 가 주어진다.. a/b를 문제에서 주어진 수식을 통하여 approx 하는데.. terms 만큼의 term으로 나타냈을때 결과가 얼마인지 구하는 문제.. t는 power of 2 중에서 b보다 같거나 큰 수 중 가장 작은수이다..
그냥 시키는데로 하면 되는 문제.. 우선 t를 구하고.. c = t - b 를 이용하여 c를 구하고.. terms 만큼 loop를 돌면서 구하면 된다..
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <vector> 5 #include <string> 6 #include <cmath> 7 using namespace std; 8 9 class ApproximateDivision { 10 public: 11 12 double quotient(int a, int b, int terms) 13 { 14 int t, c, i; 15 double x; 16 for (i = 0; ; i++) { 17 if ((1 << i) >= b) 18 break; 19 } 20 t = (1<<i); 21 c = t-b; 22 x = 0.0; 23 for (i = 1; i <= terms; i++) { 24 x += (pow((double)c, (double)(i-1)) / pow((double)t, (double)i)); 25 } 26 x *= a; 27 printf("x = %lf..\n", x); 28 return x; 29 } 30 31 };
[500] GuitarChords
Problem Statement
Musical notes are are given the following 12 names, in ascending order:
A, A#, B, C, C#, D, D#, E, F, F#, G, G# The names repeat for higher and lower notes, so the note one step higher than "G#" is "A" and the note 5 steps lower than "B" is "F#". Notes that are a multiple of 12 steps apart have the same name, and for our purposes we will consider them equivalent. Guitars have a number of strings, and each string is tuned to sound one of the 12 notes. The note each string sounds is called its "open" note. Underneath the strings are frets, numbered starting at 1, which are used to change the note a string sounds. If you press a string against the i-th fret with your finger, the note will be i steps higher than the string's open note. (i.e., if you press a string tuned to "C#" against the 3rd fret, it will sound the note "E"). Chords are sets of notes played at the same time. To play a chord on a guitar, each string must sound one of the notes in the chord, and each note in the chord must be played on at least one string. There can be many ways to play the same chord. We measure the difficulty of one way to play a chord as the amount you must stretch your fingers to reach the required frets. Calculate this as the lowest fret used subtracted from the highest fret used, plus 1. Only consider the strings which are pressed against frets -- the strings that are not pressed against frets (and, thus, sound their open note) do not affect the difficultly of a chord. If a chord can be played without using any frets at all, its difficulty is zero. You are given a String[] strings, each element of which is the open note of one string on the guitar, and a String[] chord, each element of which is one note in a chord. Return the lowest possible difficulty value necessary to play that chord. Definition
Class: GuitarChords Method: stretch Parameters: vector <string>, vector <string> Returns: int Method signature: int stretch(vector <string> strings, vector <string> chord) (be sure your method is public)
Constraints - strings and chord will each contain between 1 and 6 elements, inclusive. - chord will not contain more elements than strings. - Each element of strings and chord will be one of the 12 note names given in the problem statement. - chord will not contain any duplicate elements. Examples 0)
{ "A", "C", "F" } { "C#", "F#", "A#" } Returns: 1 The three notes in the chord are each one step higher than the notes played by the three strings. So, you can play this chord by putting your finger on the 1st fret on all three strings. The answer is therefore: (1-1)+1. 1)
{ "E", "A", "D", "G", "B", "E" } { "E", "G#", "B" } Returns: 2 The best way to play this chord is with your fingers on the following frets: string 0, "E": no fret, plays note "E" string 1, "A": fret #2, plays note "B" string 2, "D": fret #2, plays note "E" string 3, "G": fret #1, plays note "G#" string 4, "B": no fret, plays note "B" string 5, "E": no fret, plays note "E" All strings are playing a note in the chord, and each note in the chord is played on at least one string. The largest-numbered fret is 2, and the smallest is 1. Therefore the answer is (2-1)+1. 2)
{ "D#" } { "D#" } Returns: 0
3)
{ "E", "F" } { "F#", "D#" } Returns: 3 You can play this chord with the 11th fret of the "E" string (playing the note "D#") and the 13th fret of the "F" string (playing the note "F#"). (13-11)+1 = 3. 4)
{ "C", "C", "C" } { "C", "E", "G" } Returns: 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.
12개의 note가 있고, input으로 string과 chord가 주어진다.. string을 모두 이용하여 chord를 연주해야한다.. i'th fret을 누른상태에서 string을 누르면 해당 string의 i번째 상위 note가 연주된다.. 나올수있는 i의 최대값과 최소값의 차이를 최소화하는 문제..
우선.. 나는 기타를 전혀 모르기때문에.. 문제 해석하느라 열라 짜증났다.. 젠장!!! 이런문제 싫어!!!!
처음에 무슨 matching 문제인가.. 생각하다가 input의 개수가 최대 6인것을 보고.. 그냥 backtracking으로 모든 stirng과 chord의 조합을 다 구했다.. 그 조합에 대해서 high fret과 low fret의 차이를 구하고자 했는데.. 실패했다.. 막판에 거의 다 코딩은했는데.. 케이스하나가 안나와서 고민하다가 끝나버렸다.. 흐미.. 나중에 케이스를 확인해본 결과.. 생각하지못한 부분이 있었다.. 이 문제는 내가 생각했던것보다 tricky한 문제..
to be updated..
[1000] LittleSquares
Problem Statement
Two people are playing a game, taking turns filling in squares on a piece of graph paper. On each turn, they can either fill in a single empty square or fill in a 2x2 block of 4 empty squares. Once all the squares in the grid are filled, the last player to have filled in a square is the winner. The only restriction is that if we number the rows from top to bottom starting at zero, the top half of every 2x2 block that a player fills in during a turn must lie in an even-numbered row. For example, the following moves (in green) are legal:
while the following moves (in red) are illegal:
The current state of the grid will be given as a vector <string> state. Each element of state will be one row of the grid, and each character of each element of state will represent one square in the row. A '.' (period) represents an empty square, and a '#' represents a filled-in square. From this current state, determine who can win the game assuming both people play optimally. If the next player to move can win return the string "first", otherwise, return the string "second" (all quotes for clarity). Definition
Constraints - states will contain an even number of elements, between 2 and 10, inclusive. - The length of each element of states will be even and between 2 and 10, inclusive. - The length of each element of states will be the same. - Each character in states will be '.' (period) or '#'. Examples 0)
{ "..", ".." } Returns: "first" On an empty 2x2 grid, the first player can win the game with a single move. 1)
{ "...#", "..##" } Returns: "first" If the first player draws a 2x2 square on the left side of the grid, she will lose. Likewise if she draws a 1x1 square in the rightmost open space. However if she draws a 1x1 square in any of the other four empty spaces, that will leave 4 empty squares to be filled in and she will be able to move last. 2)
{ "..", "..", "..", ".." } Returns: "second" If the first player draws a 2x2 square on her first move, the second player will draw another 2x2 square and win. If the first player draws a 1x1 square first, the second player will draw another in the other half of the grid, leaving 6 empty spaces that can only be filled in one at a time. 3)
{ "....", "...." } Returns: "first" The first player can draw a 2x2 square in the middle of the grid, leaving 4 empty spaces. 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.
