SRM 144 DIV1 550
Problem Statement
|
| |
In most states, gamblers can choose from a wide variety of different lottery games. The rules of a lottery are defined by two integers (choices and blanks) and two boolean variables (sorted and unique). choices represents the highest valid number that you may use on your lottery ticket. (All integers between 1 and choices, inclusive, are valid and can appear on your ticket.) blanks represents the number of spots on your ticket where numbers can be written.
The sorted and unique variables indicate restrictions on the tickets you can create. If sorted is set to true, then the numbers on your ticket must be written in non-descending order. If sorted is set to false, then the numbers may be written in any order. Likewise, if unique is set to true, then each number you write on your ticket must be distinct. If unique is set to false, then repeats are allowed.
Here are some example lottery tickets, where choices = 15 and blanks = 4:
- {3, 7, 12, 14} -- this ticket is unconditionally valid.
- {13, 4, 1, 9} -- because the numbers are not in nondescending order, this ticket is valid only if sorted = false.
- {8, 8, 8, 15} -- because there are repeated numbers, this ticket is valid only if unique = false.
- {11, 6, 2, 6} -- this ticket is valid only if sorted = false and unique = false.
Given a list of lotteries and their corresponding rules, return a list of lottery names sorted by how easy they are to win. The probability that you will win a lottery is equal to (1 / (number of valid lottery tickets for that game)). The easiest lottery to win should appear at the front of the list. Ties should be broken alphabetically (see example 1).
|
Definition
|
| |
| Class: |
Lottery |
| Method: |
sortByOdds |
| Parameters: |
vector <string> |
| Returns: |
vector <string> |
| Method signature: |
vector <string> sortByOdds(vector <string> rules) |
| (be sure your method is public) |
|
| |
|
Constraints
|
| - |
rules will contain between 0 and 50 elements, inclusive. |
| - |
Each element of rules will contain between 11 and 50 characters, inclusive. |
| - |
Each element of rules will be in the format "<NAME>:_<CHOICES>_<BLANKS>_<SORTED>_<UNIQUE>" (quotes for clarity). The underscore character represents exactly one space. The string will have no leading or trailing spaces. |
| - |
<NAME> will contain between 1 and 40 characters, inclusive, and will consist of only uppercase letters ('A'-'Z') and spaces (' '), with no leading or trailing spaces. |
| - |
<CHOICES> will be an integer between 10 and 100, inclusive, with no leading zeroes. |
| - |
<BLANKS> will be an integer between 1 and 8, inclusive, with no leading zeroes. |
| - |
<SORTED> will be either 'T' (true) or 'F' (false). |
| - |
<UNIQUE> will be either 'T' (true) or 'F' (false). |
| - |
No two elements in rules will have the same name. |
主要是运用了排列组合的知识，其中，最难的是，从n个数中找出m个数，要求这m个数必须是排好序的，并且可以重复，可以把它转化为从n+m-1个数中选出m个数，且是排好序的，答案就是C(n+m-1,m)
 // BEGIN CUT HERE
// END CUT HERE
#line 5 "Lottery.cpp"
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <math.h>
#include <sstream>
using namespace std;
typedef long long int64;
class TICKET
   {
 public:
string name;
int64 rate;
 };
bool operator < (const TICKET & t1,const TICKET & t2)
{
if(t1.rate!=t2.rate)
return t1.rate<t2.rate;
else return t1.name<t2.name;
}
vector<TICKET>tickets;
class Lottery
{
private:
int choices,blanks;
bool sorted,unique;
public:
vector <string> sortByOdds(vector <string> rules)
  {
vector<string>::iterator it;
for(it=rules.begin();it!=rules.end();it++)
{
TICKET ticket;
ticket.name=split(*it);
ticket.rate=process();
tickets.push_back(ticket);
 }
sort(tickets.begin(),tickets.end());
vector<string> ans;
for(vector<TICKET>::iterator it=tickets.begin();it!=tickets.end();it++)
ans.push_back(it->name);
return ans;
}
string split(string rule)
{
string::size_type pos,pos2;
pos = rule.find_first_of(':');
string name=rule.substr(0,pos);
char ch1,ch2;
istringstream ist(rule.substr(pos+2,rule.size()));
ist>>choices>>blanks>>ch1>>ch2;
sorted=(ch1=='T'?1:0);
unique=(ch2=='T'?1:0);
//pos+=2; //去掉一个空格
//pos2 = rule.find_first_of(' ',pos);
//choices=0;
//for(string::size_type i=pos;i<pos2;i++)
// choices=choices*10+(rule[i]-'0');
//
//pos2++;
//blanks=rule[pos2]-'0';
//pos2+=2;
//sorted = (rule[pos2]=='T'?1:0);
//pos2+=2;
//unique = (rule[pos2]=='T'?1:0);
return name;
}
int64 process()
{
if(sorted && unique)
return C(choices,blanks);
else if(!sorted && !unique)
return pow((double)choices,blanks);
else if(!sorted && unique)
return A(choices,blanks);
else
{
return C(choices-1+blanks,blanks);
}
}
int64 A(int m,int n)
{
int64 res=1;
for(int i=m;i>=m-n+1;i--)
res*=i;
return res;
}
int64 C(int m,int n)
{
//return A(m,n)/A(n,n);
int64 res=1;
for(int i=m;i>=m-n+1;i--)
res*=i;
for(int i=2;i<=n;i++)
res/=i;
return res;
}
};
// BEGIN CUT HERE
int main()
{
Lottery test;
string Arr0[] = {"INDIGO: 93 8 T F",
"ORANGE: 29 8 F T",
"VIOLET: 76 6 F F",
"BLUE: 100 8 T T",
"RED: 99 8 T T",
"GREEN: 78 6 F T",
"YELLOW: 75 6 F F"};
vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0])));
vector<string> ans = test.sortByOdds(Arg0);
for(vector<string>::iterator it=ans.begin();it!=ans.end();it++)
cout<<*it<<endl;
return 0;
}
// END CUT HERE
|