250 대충 빨리 푸니깐 rating 오를꺼같아서.. 나머지는 그냥 접었다.. 챌도 시도했으면 좋은 결과가 있었을텐데..
아.. 새벽 2시 매치는 너무 힘들어.. ㅠㅠ
Problem Statement
Every good encyclopedia has an index. The entries in the index are usually sorted in alphabetic order. However, there are some notable exceptions. In this task we will consider one such exception: the names of kings.
In many countries it was common that kings of the same name received ordinal numbers. This ordinal number was written as a Roman numeral and appended to the actual name of the king. For example, "Louis XIII" (read: Louis the thirteenth) was the thirteenth king of France having the actual name Louis.
In the index of an encyclopedia, kings who share the same name have to be sorted according to their ordinal numbers. For example, Louis the 9th should be listed after Louis the 8th.
You are given a vector <string> kings. Each element of kings is the name of one king. The name of each king consists of his actual name, a single space, and a Roman numeral. Return a vector <string> containing the names rearranged into their proper order: that is, the kings have to be in ascending lexicographic order according to their actual name, and kings with the same name have to be in the correct numerical order.
Definition
Class:
KingSort
Method:
getSortedList
Parameters:
vector <string>
Returns:
vector <string>
Method signature:
vector <string> getSortedList(vector <string> kings)
(be sure your method is public)
Notes
-
The Roman numerals for 1 through 10 are I, II, III, IV, V, VI, VII, VIII, IX, and X.
-
The Roman numerals for 20, 30, 40, and 50 are XX, XXX, XL, and L.
-
The Roman numeral for any other two-digit number less than 50 can be constructed by concatenating the numeral for its tens and the numeral for its ones. For example, 47 is 40 + 7 = "XL" + "VII" = "XLVII".
-
Standard string comparison routines give the correct ordering for the actual names of kings.
-
Formally, given two different strings A and B we say that A is lexicographically smaller than B if either (A is a prefix of B) or (there is at least one index where A and B differ, and for the smallest such index the character in A has a lower ASCII value than the character in B).
Constraints
-
Each actual name of a king will be a string containing between 1 and 20 characters, inclusive.
-
Each actual name will start by an uppercase letter ('A'-'Z').
-
Each other character in each actual name will be a lowercase letter ('a'-'z').
-
kings will contain between 1 and 50 elements, inclusive.
-
Each element of kings will have the form "ACTUALNAME ORDINAL", where ACTUALNAME is an actual name as defined above, and ORDINAL is a valid Roman numeral representing a number between 1 and 50, inclusive.
-
The elements of kings will be pairwise distinct.
Examples
0)
{"Louis IX", "Louis VIII"}
Returns: {"Louis VIII", "Louis IX" }
Louis the 9th should be listed after Louis the 8th.
1)
{"Louis IX", "Philippe II"}
Returns: {"Louis IX", "Philippe II" }
Actual names take precedence over ordinal numbers.
2)
{"Richard III", "Richard I", "Richard II"}
Returns: {"Richard I", "Richard II", "Richard III" }
3)
{"John X", "John I", "John L", "John V"}
Returns: {"John I", "John V", "John X", "John L" }
4)
{"Philippe VI", "Jean II", "Charles V", "Charles VI", "Charles VII", "Louis XI"}
Returns:
{"Charles V",
"Charles VI",
"Charles VII",
"Jean II",
"Louis XI",
"Philippe VI" }
These are the French monarchs who ruled between 1328 and 1483.
5)
{"Philippe II", "Philip II"}
Returns: {"Philip II", "Philippe II" }
"Philippe" and "Philip" are distinct names, and "Philip" is lexicographically smaller than "Philippe".
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.
이문제의 핵심은 Roman digit을 아라비아 숫자로 변환하는데 있다.. 예전에 짜둔게 있어서 그냥 복.붙 했는데..
30% unused 어쩌구 warning 이 나서 한참 삽질했다.. -_-
line 84 를 넣으니깐 warning 이 사라짐.. 이것땜에 시간 엄청 까먹음..
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7 //#define min(x, y) ((x) > (y) ? (y) : (x))
8 //#define max(x, y) ((x) > (y) ? (x) : (y))
9 //#define INF 999999999
10 //#define EPS 1e-14
11
12 typedef struct _n {
13 char name[100];
14 char no[100];
15 int val;
16 } NAME;
17 NAME king[55];
18 int n;
19 int to_arab(char* buf)
20 {
21 int len, sum, temp, i;
22 char ch;
23 len = strlen(buf);
24 sum = 0;
25 for (i = 0; i < len; i++) {
26 ch = buf[i];
27 if (ch == 'L') {
28 sum += 50;
29 }
30 else if (ch == 'X') {
31 temp = 0;
32 for ( ; i < len && buf[i] == 'X'; i++) {
33 temp += 10;
34 }
35 if (buf[i] == 'L' || buf[i] == 'C')
36 sum -= temp;
37 else
38 sum += temp;
39 i--;
40 }
41 else if (ch == 'V') {
42 sum += 5;
43 }
44 else {
45 temp = 0;
46 for ( ; i < len && buf[i] == 'I'; i++) {
47 temp += 1;
48 }
49 if (buf[i] == 'V' || buf[i] == 'X')
50 sum -= temp;
51 else
52 sum += temp;
53 i--;
54 }
55 }
56 return sum;
57 }
58
59
60 int comp(const void* x, const void* y)
61 {
62 int val1, val2;
63 NAME* a = (NAME*)x;
64 NAME* b = (NAME*)y;
65 if (strcmp(a->name, b->name) != 0) {
66 return strcmp(a->name, b->name);
67 }
68 val1 = to_arab(a->no);
69 val2 = to_arab(b->no);
70 return val1 - val2;
71 }
72
73 class KingSort {
74 public:
75
76 vector <string> getSortedList(vector <string> kings)
77 {
78 int i;
79 string temp;
80 vector<string> res;
81 n = kings.size();
82 for (i = 0; i < n; i++) {
83 sscanf(kings[i].c_str(), "%s%s", king[i].name, king[i].no);
84 king[i].val = to_arab(king[i].no);
85 }
86 qsort(king, n, sizeof(NAME), comp);
87 for (i = 0; i < n; i++) {
88 temp = king[i].name;
89 temp = temp + " ";
90 temp = temp + king[i].no;
91 res.push_back(temp);
92 }
93 return res;
94 }
95
96 };
Problem Statement
Consider the following problem:
"In the country of Absurdistan there are N airports. Each airport is either big or small. It is known that for each big airport there are at least B flights leaving it, and for each small airport there are at most S flights leaving it. Each flight is bidirectional and connects exactly two airports. No two flights connect the same pair of airports. It is possible to travel from any airport to any other airport using some sequence of flights. Determine the number of big airports. Find all solutions."
Let A(N,B,S) be the number of solutions the above task has for a given triple N, B, S. You are given six ints: Nlo, Nhi, Blo, Bhi, Slo and Shi. Your method must compute and return the sum of A(N,B,S) over all N, B, S such that all following constraints hold:
Nlo <= N <= Nhi
Blo <= B <= Bhi
Slo <= S <= Shi
S < B
Definition
Class:
BigAndSmallAirports
Method:
solve
Parameters:
int, int, int, int, int, int
Returns:
long long
Method signature:
long long solve(int Nlo, int Nhi, int Blo, int Bhi, int Slo, int Shi)
(be sure your method is public)
Notes
-
It is possible that all airports in the country are of the same kind (all big or all small).
Constraints
-
Nhi will be between 1 and 10,000,000, inclusive.
-
Nlo will be between 1 and Nhi, inclusive.
-
Bhi will be between 1 and 200, inclusive.
-
Blo will be between 1 and Bhi, inclusive.
-
Shi will be between 1 and 200, inclusive.
-
Slo will be between 1 and Shi, inclusive.
Examples
0)
20
20
3
3
2
2
Returns: 21
For N=20, B=3, S=2 each number of big airports (from 0 to N, inclusive) is possible. The image below shows one possible network of airports and flights with 3 big airports (squares) and 17 small airports (circles).
1)
1
1
10
10
2
2
Returns: 1
In the case N=1, B=10, S=2 there is a single airport. It cannot have 10+ outgoing flights, therefore it has to be small. If the airport is small, all conditions are satisfied. Therefore A(N,B,S)=1.
2)
10
10
8
8
3
3
Returns: 6
3)
10
100
13
15
18
22
Returns: 0
There are no triples (N,B,S) such that N, B, S lie within the given ranges and B < S. Therefore the answer is the sum of zero values, which equals 0.
4)
30
32
8
10
6
8
Returns: 768
