TopCoder SRM 420 Div 2

오늘 저녁 8시에 열린 매치.. 오늘은 문제가 쉬웠는지.. 내가 컨디션을 회복중인지(?).. 성적이 괜찮았다..~
내침김에 1000점까지 도전해보았는데.. 아쉽게도 시간이 조금 모자랐다..;;
500점짜리는 나름 괜찮았는데.. 250은 코딩속도가 남들보다 확실히 떨어지는게 보이는군..
흠.. 가뜩이나 어려운문제도 잘 못푸는데.. 쉬운문제를 코딩하는데 너무 오래걸려서.. 항상 고전한다..

방 1등 전체 15등..~ 이렇게해서 3전4기만에 다시 div1으로 복귀..~

Level1 - DeckRearranging

Problem Statement
     
We have a deck of cards. Each of the cards is either black or red. We will use the character B to represent a black card and the character R for a red card. By listing the cards from top to bottom of the deck we get a string deck.
We now want to insert all the cards into a new deck. Initially, the new deck is empty. We will now process the cards in the old deck from top to bottom. When processing the card that corresponds to character i of deck, take it from the old deck and insert it into the new deck in such a way that exactly above[i] cards are above it after the insertion.
Write a method that takes the string deck and vector <int> above, and returns the new deck encoded as a string in the same way as deck.
Definition
   
Class:
DeckRearranging
Method:
rearrange
Parameters:
string, vector <int>
Returns:
string
Method signature:
string rearrange(string deck, vector <int> above)
(be sure your method is public)
   
 
Constraints
-
deck will contain between 1 and 50 characters, inclusive.
-
Each character in deck will be either 'B' or 'R' (uppercase letter B or R).
-
The number of elements in above will be equal to the number of characters in deck.
-
For each i, element i in above will be between 0 and i, inclusive.
Examples
0)
 
   
"BRBRR"
{0, 0, 1, 0, 3}
Returns: "RRBRB"
The order of cards in the old deck, top to bottom, is: B, R, B, R, R. This is the order in which we will process them.
Below we list the new deck, top to bottom, after each of the insertions. The most recently inserted card is given in uppercase, the other cards are in lowercase.
B
Rb
rBb
Rrbb
rrbRb
Therefore the new deck is RRBRB.
1)
 
   
"RRRRRR"
{0,1,2,0,1,3}
Returns: "RRRRRR"
No matter how you rearrange a deck with 6 red cards, you will always get a deck with 6 red cards.
2)
 
   
"RBRRBRBB"
{0,1,2,3,4,5,6,7}
Returns: "RBRRBRBB"
In this example each card is placed at the bottom of the new deck. The result is the same deck as the old one.
3)
 
   
"RBRRBRBB"
{0,0,0,0,0,0,0,0}
Returns: "BBRBRRBR"
In this example, each card is placed on the top of the new deck. The result is the old deck turned upside down.
4)
 
   
"RBRRBRBB"
{0,1,0,0,4,0,6,7}
Returns: "RRRRBBBB"
In this example, we place each red card on the top, and each black card on the bottom. The result is a deck with all red cards on the top.
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.

B와 R 두가지 종류의 카드가 섞여있다.. 이 카드를 다시 새롭게 섞는데 그 규칙은 top부터 bottom 방향으로 하나씩 보면서 i번째 카드를 다시 새로운 deck에 insert할때 above[i]개 만큼의 카드가 그 위에 오도록 한다. new deck을 출력하기.

그냥 설명하는데로 simulation 했다.. 나는 배열을 써서 insert할때마다 한칸씩 다 밀었는데.. list 같은 자료구조를 쓰면 중간에 삽입이 가능하다보다. 음.. 쉬운문제 푸는데 왜이리 오래걸리지..

  1 #include <iostream>

  2 #include <cstdio>

  3 #include <algorithm>

  4 #include <vector>

  5 #include <string>

  6 using namespace std;

  7

  8 class DeckRearranging {

  9 public:

 10

 11 string rearrange(string deck, vector <int> above)

 12 {

 13     int n, cnt, a;

 14     int i, j;

 15     char buf[100];

 16     char ndeck[100];

 17     string res;

 18     n = above.size();

 19     strcpy(buf, deck.c_str());

 20     cnt = 0;

 21     for (i = 0; i < n; i++) {

 22         a = above[i];

 23         for (j = cnt-1; j >= a; j--) {

 24             ndeck[j+1] = ndeck[j];

 25         }

 26         ndeck[a] = buf[i];

 27         cnt++;

 28     }

 29     ndeck[cnt] = 0;

 30 printf("ndeck = %s\n", ndeck);

 31     return res = ndeck;

 32 }

 33

 34 };

Level2 - YearProgressbar

Problem Statement
     
You are a big fan of New Year's Eve parties. The next one is not too far away, and you are already looking forward to it.
Then, one day, you wake up with a question: "Wait a moment, exactly how far away is it?"
To answer this question, you decided to implement a simple application: a year progress bar that will always show how much of the current year has already passed.
In this problem, your goal is to implement the most important part of this application: a function that gets a string currentDate, and returns the elapsed part of the year, as a percentage.
The variable currentDate will be of the form "Month DD, YYYY HH:MM" (quotes for clarity). Here, "Month" is the name of the current month, "YYYY" is a four-digit number representing the current year, and "DD", "HH", and "MM" are two-digit numbers (possibly with a leading zero) that represent the current day, hour and minute.
Definition
   
Class:
YearProgressbar
Method:
percentage
Parameters:
string
Returns:
double
Method signature:
double percentage(string currentDate)
(be sure your method is public)
   
 
Notes
-
The months of a normal year have 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, and 31 days.
-
In leap years, the second month (February) has 29 days.
-
A year is a leap year if (it is divisible by 400) or (it is divisible by 4, but not by 100).
-
Ignore location-dependent changes to time flow such as daylight saving time.
-
Your return value must have a relative or absolute error less than 1e-9.
Constraints
-
currentDate will be of the form given in the problem statement.
-
Month will be one of January, February, March, April, May, June, July, August, September, October, November, and December.
-
YYYY will be between 1800 and 2600, inclusive.
-
DD will be between 01 and the number of days in the given month (in the given year), inclusive.
-
HH will be between 00 and 23, inclusive.
-
MM will be between 00 and 59, inclusive.
Examples
0)
 
   
"January 01, 2008 00:00"
Returns: 0.0
This is the exact beginning of the year 2008; no time has elapsed yet.
1)
 
   
"December 31, 2007 23:59"
Returns: 99.99980974124807
One last minute of the year 2007 is remaining.
2)
 
   
"July 02, 2007 12:00"
Returns: 50.0
The exact half of a normal year is at noon on the second day of July.
3)
 
   
"July 02, 2008 00:00"
Returns: 50.0
On a leap year, the exact half of the year is the midnight between the first and the second of July.
4)
 
   
"May 10, 1981 00:31"
Returns: 35.348363774733635
The date and time when the problem setter was born :-)
5)
 
   
"January 31, 1900 00:47"
Returns: 8.228120243531203
Note that 1900 is not a leap year.
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.

1년중에 날짜와 시간이 주어지고 그 시점이 1년중 정확히 몇 percent가 지났는지 구하는 문제..

1년이 총 몇분인지 구하고 현재까지 몇분이 지났는지 계산해서 비율을 구했다.. 단순 날짜 계산 노가다 문제.. 이런문제는 너무 싫다.. ㅠ_ㅠ

챌린지 타임때 혹시 month 스펠링 틀린사람 없나 뚤어지게 봤는데.. 스펠링 틀린사람은 없었다..;; 그대신 윤년을 구하는걸 틀린사람 하나 발견.. 챌 하나 성공했다..

  1 #include <iostream>

  2 #include <cstdio>

  3 #include <algorithm>

  4 #include <vector>

  5 #include <string>

  6 using namespace std;

  7

  8 int DAY[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

  9

 10 int get_mon(char* str)

 11 {

 12     if (!strcmp(str, "January"))

 13         return 1;

 14     if (!strcmp(str, "February"))

 15         return 2;

 16     if (!strcmp(str, "March"))

 17         return 3;

 18     if (!strcmp(str, "April"))

 19         return 4;

 20     if (!strcmp(str, "May"))

 21         return 5;

 22     if (!strcmp(str, "June"))

 23         return 6;

 24     if (!strcmp(str, "July"))

 25         return 7;

 26     if (!strcmp(str, "August"))

 27         return 8;

 28     if (!strcmp(str, "September"))

 29         return 9;

 30     if (!strcmp(str, "October"))

 31         return 10;

 32     if (!strcmp(str, "November"))

 33         return 11;

 34     return 12;

 35 }

 36

 37 class YearProgressbar {

 38 public:

 39

 40 double percentage(string currentDate)

 41 {

 42     char buf[100];

 43     char* ptr;

 44     int year, mon, day, mm, hh;

 45     int is_leap, i;

 46     int day_sum;

 47     double tot, cur;

 48     strcpy(buf, currentDate.c_str());

 49     ptr = strtok(buf, " ");

 50     mon = get_mon(ptr);

 51     ptr = strtok(NULL, " ");

 52     day = atoi(ptr);

 53     ptr = strtok(NULL, " ");

 54     year = atoi(ptr);

 55     ptr = strtok(NULL, " ");

 56     sscanf(ptr, "%02d:%02d", &hh, &mm);

 57

 58     is_leap = 0;

 59     if (year % 400 == 0) {

 60         is_leap = 1;

 61     }

 62     else if (year % 4 == 0 && year % 100 != 0) {

 63         is_leap = 1;

 64     }

 65     if (is_leap) {

 66         tot = 366.0 * 1440.0;

 67     }

 68     else {

 69         tot = 365.0 * 1440.0;

 70     }

 71     day_sum = 0;

 72     for (i = 1; i < mon; i++) {

 73         day_sum += DAY[i];

 74         if (i == 2 && is_leap == 1) {

 75             day_sum++;

 76         }

 77     }

 78     day_sum += day-1;

 79     cur = day_sum * 1440.0;

 80     cur += hh * 60.0 + mm;

 81

 82 printf("%lf / %lf\n", cur, tot);

 83

 84     return cur / tot * 100.0;

 85 }

 86

 87 };

Level3 - PrettyPrintingProduct

Problem Statement
     
You will be given two positive ints A and B.
Let C be the product of all integers between A and B, inclusive.
The number C has a unique representation of the form C = D * 10^E, where D and E are non-negative integers and the last digit of D is non-zero.
Write a method that will return the value of C formatted as a string of the form "D * 10^E" (quotes for clarity only). Substitute the actual values of D and E into the output. If D has more than 10 digits, only output the first five and the last five digits of D, and separate them by three periods.
Definition
   
Class:
PrettyPrintingProduct
Method:
prettyPrint
Parameters:
int, int
Returns:
string
Method signature:
string prettyPrint(int A, int B)
(be sure your method is public)
   
 
Notes
-
The purpose of the last constraint is to disallow inputs where precision problems could arise.
Constraints
-
A will be between 1 and 1,000,000, inclusive.
-
B will be between A and 1,000,000, inclusive.
-
If C has more than 10 digits, then the sixth most significant digit of C will be neither 0 nor 9.
Examples
0)
 
   
1
10
Returns: "36288 * 10^2"
1 * 2 * ... * 10 = 3628800 = 36288 * 10^2
1)
 
   
7
7
Returns: "7 * 10^0"
The product of all numbers between 7 and 7, inclusive, is obviously 7.
2)
 
   
211
214
Returns: "2038974024 * 10^0"
For this input D has 10 digits.
3)
 
   
411
414
Returns: "28952...24024 * 10^0"
For this input D has 11 digits. Note that we output three dots even if just one digit is missing in the output.
4)
 
   
412
415
Returns: "2923450236 * 10^1"
The actual value of C is larger than in the previous example. However, C ends in a zero and therefore D only has 10 digits.
5)
 
   
47
4700
Returns: "14806...28928 * 10^1163"
 
6)
 
   
1
19
Returns: "12164...08832 * 10^3"
Note that the last five digits of D can start with a zero.
7)
 
   
13
25
Returns: "32382...26624 * 10^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.

A와 B가 주어질때, C = A * (A+1) * (A+2) * ... * (B-1) * B 일때 C = D * 10^E 꼴로 나타낼때 C, D, E를 구하기.. C가 10자리가 넘어가면 앞에 5자리와 뒤의 5자리 구하기..

매치때 삽질하다가 결국 서밋을 못했다.. E는 min(getpow(2), getpow(5)) 일듯 싶고, 앞의 5자리는 logarithm, 뒤의 5자리는 modulo로 풀려고 했는데.. 시간이 모자랐다..

우리방에서 2명이 이 문제를 submit 했는데.. log를 안쓰고 풀었길래.. 그냥 챌 해보았다.. 근데 둘다 성공..;; 사실 pass 한사람들도 log를 안썼던데.. 어떻게 푼거지..;;

to be updated..