어제 저녁8시에 열린 매치..~
처음으로 회사에서 한번 해봤다.. 코딩환경이 집이랑 다르다보니.. 좀 부자연스럽긴 했다..~
250점 문제는 결정적으로 input 범위를 착각하는 바람에 어처구니없게 틀렸다.. -_-
뭔가.. 문제풀때 집중이 안돼..;;
Level1 - TheMoviesLevelOneDivOne
Problem Statement
John and Brus are going to a theater to see a very interesting movie. They would like to have seats next to each other in the same row. The theater contains n rows, with m seats in each row. Rows are numbered 1 to n from front to back, and seats are numbered 1 to m from left to right. Some of the seats are already reserved, but John and Brus can book any of the available seats. You are given vector <int>s row and seat. The i-th elements of row and seat are the row number and seat number of the i-th reserved seat. All remaining seats are available. Return the number of ways for John and Brus to book two available seats next to each other in the same row.
Definition
Class:
TheMoviesLevelOneDivOne
Method:
find
Parameters:
int, int, vector <int>, vector <int>
Returns:
long long
Method signature:
long long find(int n, int m, vector <int> row, vector <int> seat)
(be sure your method is public)
Notes
-
Two bookings are considered different only if one contains a seat that the other does not contain. In other words, they don't need to decide which seat John sits in and which seat Brus sits in.
Constraints
-
n and m will each be between 1 and 1,000,000,000, inclusive.
-
row will contain between 1 and 47 elements, inclusive.
-
row and seat will contain the same number of elements.
-
Each element of row will be between 1 and n, inclusive.
-
Each element of seat will be between 1 and m, inclusive.
-
All pairs (row[i], seat[i]) will be distinct.
Examples
0)
2
3
{1, 2}
{2, 3}
Returns: 1
The first and the second seat in the second row are the only two free seats next to each other in the same row.
1)
2
3
{1, 1, 1, 2, 2, 2}
{1, 2, 3, 1, 2, 3}
Returns: 0
There are no free seats in the theater.
2)
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.
n by m 형태의 seat 가 있다.. 두명이 같은 row 에 이웃해서 앉을 수 있는 경우의 수 구하기
각 row 에 대해서 연속된 seat 를 계속 찾았다..
row 가 최대 10억 이므로 1...n 까지 모두 loop 를 도는 것은 불가능하지만
input 이 최대 50 이므로 input 에 들어온 수를 renumbering 하는 방법으로 풀었다..~
매치중에 뭔 생각을 했는지.. row 가 최대 50 인줄 알았다.. -_-;;
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 #include <map>
7 using namespace std;
8 //#define min(x, y) ((x) > (y) ? (y) : (x))
9 //#define max(x, y) ((x) > (y) ? (x) : (y))
10 //#define INF 999999999
11 //#define EPS 1e-14
12
13 class TheMoviesLevelOneDivOne {
14 public:
15
16 long long find(int n, int m, vector <int> row, vector <int> seat)
17 {
18 int size;
19 int cnt;
20 int i, j;
21 int cur, prev;
22 long long sum, dif;
23 vector<long long> num[100];
24 map<int, int> mm;
25
26 cnt = 0;
27 size = row.size();
28 for (i = 0; i < size; i++) {
29 if (mm.find(row[i]) == mm.end()) {
30 mm[row[i]] = cnt;
31 cnt++;
32 }
33 cur = mm[row[i]];
34 num[cur].push_back(seat[i]);
35 }
36 for (i = 0; i < cnt; i++) {
37 sort(num[i].begin(), num[i].end());
38 }
39
40 sum = 0;
41 for (i = 0; i < cnt; i++) {
42 cur = prev = 0;
43 for (j = 0; j < num[i].size(); j++) {
44 cur = num[i][j];
45 if (cur - prev - 1 >= 2) {
46 dif = cur - prev - 1;
47 sum += dif - 1;
48 }
49 prev = cur;
50 }
51 if (m - prev >= 2) {
52 dif = m - prev;
53 sum += dif - 1;
54 }
55 }
56 sum += (long long)(n-cnt) * (m-1);
57 return sum;
58 }
59
60 };
Level2 - TheMoviesLevelTwoDivOne
Problem Statement
John has decided to watch some horror movies tonight. He has a collection of N scary movies, numbered 0 to N-1, inclusive. The lengths of the movies are given in the vector <int> length, where the i-th element is the length in minutes of movie i. However, John is very tired, so it is possible for him to fall asleep while watching a movie. The only way he can stay awake is to maintain a certain level of being scared. He has a "scare level" which is a real number initially equal to 74. His scare level will continuously decrease at a speed of 1 per minute. For example, after 6 seconds, it will go down by 0.1. Once this level falls below -0.5, John will fall asleep. Each of John's movies has exactly one scary moment. Once John sees this moment, his scare level will instantly increase by 47. The scary moments are given in the vector <int> scary. In movie i, the scary moment will occur exactly scary[i] minutes after the beginning of the movie. John would like to determine the best order in which to watch the movies. Each order can be described by an vector <int> containing N distinct numbers between 0 and N-1, inclusive. The first element is the number of the first movie he watches, the second element is the number of the second movie he watches, and so on. Once a movie is finished playing, the next one starts immediately. If John falls asleep while watching a movie, he won't be able to watch the rest of the current movie, and he won't be able to watch any of the movies that he planned to watch after the current movie. Among all the possible orders, return the one that allows John to watch as many movies as possible in their entirety (i.e., from beginning to end) before falling asleep. If there are several such orders, return the one that comes earliest lexicographically.
Definition
Notes
-
A vector <int> A comes before a vector <int> B lexicographically if A contains a smaller number at the first index where they differ.
Constraints
-
length will contain between 1 and 20 elements, inclusive.
-
length and scary will contain the same number of elements.
-
Each element of length will be between 2 and 474, inclusive.
-
The i-th element of scary will be between 1 and length[i] - 1, inclusive.
Examples
0)
{100, 50}
{1, 1}
Returns: {0, 1 }
There are two possible playlists, and John can watch either one in its entirety without falling asleep.
1)
{100, 50}
{1, 49}
Returns: {1, 0 }
The only way John can see all the movies is to start with the last one.
2)
{100, 100, 100, 100}
{77, 76, 75, 74}
Returns: {3, 0, 1, 2 }
If John starts with the last movie, he will fall asleep during the second movie. If he starts with any other movie, he will fall asleep during the first movie.
3)
{100}
{99}
Returns: {0 }
Here John has no choice at all.
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..
Level3 - TheMoviesLevelThreeDivOne
Problem Statement
John and Brus have received a box of new movies to review. There are N movies, numbered 0 to N-1, inclusive, and John and Brus each want to review every movie. John has proposed that they use a special device called a review queue. The device supports two operations: add a movie, and take a movie (if at least one exists in the queue). When taking a movie, the movie in the queue that was added earliest is removed from the queue. John and Brus each have their own review queue. There are two phases to the review process. In the first phase, John distributes the movies between the two queues. He first takes movie 0 and adds it to either John's queue or Brus's queue, then he takes movie 1 and adds it to one of the queues, and so on, until each movie has been added to one of the queues. In the second phase, John and Brus simultaneously start reviewing movies. Each of them will continuously repeat the following sequence of moves.
Take a movie from his own review queue. If this move is not successful because his queue is empty, he will quit completely (even if more movies will be added to his queue at a later time).
Review this movie.
Add this movie to the other person's review queue if he has not yet reviewed it.
Steps 1 and 3 take no time. If a queue receives an add and a take operation at the same time, the add operation is completed first. So, for example, if John's queue is empty and Brus attempts to add a movie to John's queue at the same time that John tries to take a movie from the same queue, the movie will get added and John will succeed in taking the movie from the queue. The amount of time required for step 2 varies between John and Brus for each movie. When reviewing a movie, neither John nor Brus feel that it is always necessary to view the entire movie. It takes John timeJ[i] minutes to review movie i, and it takes Brus timeB[i] minutes. In the first phase, since John has two choices for distributing each movie, there are 2^N ways to distribute the movies. A distribution is considered good if John and Brus each review every movie during the second phase before quitting. Return the total number of good ways to distribute the movies.
Definition
Class:
TheMoviesLevelThreeDivOne
Method:
find
Parameters:
vector <int>, vector <int>
Returns:
long long
Method signature:
long long find(vector <int> timeJ, vector <int> timeB)
(be sure your method is public)
Constraints
-
timeJ will contain between 1 and 47 elements, inclusive.
-
timeJ and timeB will contain the same number of elements.
-
Each element of timeJ will be between 1 and 20, inclusive.
-
Each element of timeB will be between 1 and 20, inclusive.
Examples
0)
{4, 4}
{4, 4}
Returns: 2
We are interested in two distributions where John and Brus get one movie each.
1)
{1, 4}
{4, 2}
Returns: 1
Here the only possible distribution is where Brus gets the first movie and John gets the second one.
2)
{10, 10, 10, 10}
{1, 1, 1, 10}
Returns: 3
Brus must get all the movies except one of the first three during the distribution.
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.
