새벽 2시에 열림 매치.. 문제 열라 어렵다.. ㅠ_ㅠ; 숫자 문제를 주로 다룬 문제셋.. 문제자체는 참 괜찮았던거같은데.. 흠.. -_-;; 첫번째 문제를 비교적 빨리 풀어서 시간이 많이 남았는데.. 아쉽게도 삽질만하다가 끝났다.. 오늘 매치는 한국사람들이 대체로 다 고전한것같다.. 한국 극강의 코더들(astein, lewha0, ...)도 다 fail했으니.. 뭐 문제가 어렵다는 것에 위안을 삼자.. 근데.. rating은 무려 90점이나 상승~!!! 역시 새벽2시는 날 저버리지 않는다!
이번 매치에는 한국사람이 무려 30명이나 참가했다.. 새벽 2시매치임에도 불구하고.. 헐.. 훼인들 (나를 비롯해서).. -_-; 그리고보니 rated event에 참가해본 한국사람이 120명에 육박하고있다.. 내가 처음 시작했을때만해도 60여명이었는데..
방 6등 전체 300등..
방 6등.. 첫번째 문제는 젤 빨리풀었는데.. 결과는 좀 아쉽다.. 챌 시도만 안했어도 방 2등인데.. ㅠ_ㅠ 정말 살벌하다.. 1000은 아무도 submit조차 못하고.. 500은 다 challenge fail ㅋㅋㅋ
[250] ConcatenateNumber
Problem Statement
Given a positive integer number, concatenate one or more copies of number to create an integer that is divisible by k. Do not add any leading zeroes. Return the least number of copies needed, or -1 if it is impossible. Definition
Class: ConcatenateNumber Method: getSmallest Parameters: int, int Returns: int Method signature: int getSmallest(int number, int k) (be sure your method is public)
Constraints - number will be between 1 and 1,000,000,000, inclusive. - k will be between 1 and 100,000, inclusive. Examples 0)
2 9 Returns: 9 At least 9 copies are needed, since 222222222 is divisible by 9. 1)
121 11 Returns: 1 121 is divisible by 11. 2)
1 2 Returns: -1 You can never get an even number by concatenating only 1's. 3)
35 98765 Returns: 9876 The resulting integer could be really big. 4)
1000000000 3 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.
input으로 number와 k가 주어진다.. number를 계속 옆에 붙여서 새로운 수를 만들때 최소한 몇개의 number를 붙여야 k로 나누어지는지 구하는 문제..
이러한 류의 문제는 이미 많이 풀어서 익숙하다.. 우선 숫자를 계속해서 붙이되 수가 너무 커지므로 modular 연산을 계속 수행하면서 붙인다.. 그러던 중 이미 나왔던 수가 다시 나오면 cycle이 존재하게 되므로 영원히 k로 나누어지지 않는다.. 이런 경우 -1을 리턴..
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <vector> 5 #include <string> 6 #include <set> 7 using namespace std; 8 9 class ConcatenateNumber { 10 public: 11 12 int getSmallest(int number, int k) 13 { 14 int cnt; 15 long long a, b; 16 char buf[100]; 17 set<long long> s; 18 a = number; 19 b = k; 20 cnt = 1; 21 s.insert(a); 22 while (1) { 23 if (a % b== 0) { 24 break; 25 } 26 a %= b; 27 sprintf(buf, "%lld%d", a, number); 28 sscanf(buf, "%lld", &a); 29 if (s.find(a) != s.end()) { 30 cnt = -1; 31 break; 32 } 33 s.insert(a); 34 cnt++; 35 } 36 return cnt; 37 } 38 39 };
[500] PaintingBoards
Problem Statement
There are several boards arranged side by side in a straight line. Boards go in order and you can't change the order of boards. The length of the i-th board in the line is boardLength[i] inches. There are also several painters. The i-th painter can paint a one inch length of board in 1/painterSpeed[i] seconds. You can assign jobs to some of painters (not necessarily to all of them). Each painter can be assigned at most a single block of one or more consecutive boards. All the painters start at the same time and work simultaneously. Return the minimal number of seconds needed to paint all the boards. Definition
Notes - Painters do not have to be assigned to boards in any particular order. For example, painter 2 can be assigned to boards 1 to 3, while painter 1 is assigned to boards 4 to 5, etc. - The returned value must be accurate to within a relative or absolute value of 1E-9. Constraints - boardLength will contain between 1 and 50 elements, inclusive. - Each element of boardLength will be between 1 and 10000, inclusive. - painterSpeed will contain between 1 and 15 elements, inclusive. - Each element of painterSpeed will be between 1 and 10000, inclusive. Examples 0)
{5,3,2} {2,3,5} Returns: 1.0 Assign painter 3 (1-indexed) to the board of length 5, painter 2 to the board of length 3, and painter 1 to the board of length 2. Each painter will finish in exactly one second. 1)
{1,2,1,4,2,1,1} {1,2,3} Returns: 2.0 Assign painter 2 (1-indexed) to the first three boards {1, 2, 1}, painter 3 to the next two boards {4, 2}, and painter 1 to the last two boards {1, 1}. Each painter will finish in exactly 2 seconds. 2)
{3,3,20} {9,1} Returns: 2.888888888888889 It's better to assign everything to the fast painter and not assign anything to the slow painter.
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..
[1000] BuildCircuit
Problem Statement
A serial-parallel resistor circuit is either a single resistor. The resistance of such circuit is equal to the resistance of the resistor. Or several circuits R1,R2,...,Rn combined in serial. The resistance is equal to R1+R2+...+Rn. Or several circuits R1,R2,...,Rn combined in parallel. The resistance is equal to 1/((1/R1)+(1/R2)+...+(1/Rn)). Given two positive integers a and b, your task is to build a serial-parallel resistor circuit that has resistance equal to a/b. You are only allowed to use two kinds of resistors: R=1 and R=2. Return the minimal number of resistors needed. If the circuit cannot be built with 16 or less resistors, return -1. Definition
Class: BuildCircuit Method: minimalCount Parameters: int, int Returns: int Method signature: int minimalCount(int a, int b) (be sure your method is public)
Constraints - a and b will each be between 1 and 50000, inclusive. Examples 0)
1 1 Returns: 1 One unit resistor is enough. 1)
2 3 Returns: 2 Combine R=1 and R=2 in parallel. 2)
6 5 Returns: 3 Combine R=1 and R=2 in serial, then with R=2 in parallel. 3)
42 47 Returns: 7
4)
1 20 Returns: -1
5)
756 874 Returns: 10
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.
