TopCoder竞赛题基础.pdf

1 1)SRM 144 DIV 2,250-point Problem Statement Computers tend to store dates and times as single numbers which represent the number of seconds or milliseconds since a particular date.Your task in this problem is to write a method whatTime,which takes an int,seconds,representing the number of seconds since midnight on some day,and returns a String formatted as:.Here,represents the number of complete hours since midnight,represents the number of complete minutes since the last complete hour ended,and represents the number of seconds since the last complete minute ended.Each of,and should be an integer,with no extra leading 0s.Thus,if seconds is 0,you should return 0:0:0,while if seconds is 3661,you should return 1:1:1.Definition Class:Time Method:whatTime Parameters:int Returns:String Method signature:String whatTime(int seconds)Constraints seconds will be between 0 and 24*60*60-1=86399,inclusive.Examples 0)0 Returns:0:0:0 1)3661 Returns:1:1:1 2)5436 Returns:1:30:36 3)86399 Returns:23:59:59(be sure your method is public)Source code#include using namespace std;2#include class Time public:string whatTime(int seconds)int h=seconds/3600;int m=seconds/60%60;int s=seconds%60;char str64;sprintf(str,%d:%d:%d,h,m,s);string ret=str;/coutstrendl;return ret;void main()Time time;/time.whatTime(0);/time.whatTime(3661);/time.whatTime(5436);time.whatTime(86399);2)SRM 146 DIV 2,250-point Problem Statement This task is about the scoring in the first phase of the die-game Yahtzee,where five dice are used.The score is determined by the values on the upward die faces after a roll.The player gets to choose a value,and all dice that show the chosen value are considered active.The score is simply the sum of values on active dice.Say,for instance,that a player ends up with the die faces showing 2,2,3,5 and 4.Choosing the value two makes the dice showing 2 active and yields a score of 2+2=4,while choosing 5 makes the one die showing 5 active,yielding a score of 5.Your method will take as input a int toss,where each element represents the upward face of a die,and return the maximum possible score with these values.Definition Class:YahtzeeScore Method:maxPoints Parameters:int Returns:int 3 Method signature:int maxPoints(int toss)(be sure your method is public)Constraints toss will contain exactly 5 elements.Each element of toss will be between 1 and 6,inclusive.Examples 0)2,2,3,5,4 Returns:5 The example from the text.1)6,4,1,1,3 Returns:6 Selecting 1 as active yields 1+1=2,selecting 3 yields 3,selecting 4 yields 4 and selecting 6 yields 6,which is the maximum number of points.2)5,3,5,3,3 Returns:10 Source code#include#include using namespace std;class YahtzeeScore public:int maxPoints(vector toss)int count6;memset(count,0,sizeof(count);for(int i=0;i5;i+)counttossi-1+=tossi;int max=0;for(i=0;imax)4 max=counti;return max;void main()YahtzeeScore*ya=new YahtzeeScore;vector v;/test array:2 2 3 5 4/6 4 1 1 3/5 3 5 3 3 v.push_back(5);v.push_back(3);v.push_back(5);v.push_back(3);v.push_back(3);int ret=ya-maxPoints(v);coutretendl;3)SRM 147 DIV 2,250-point Problem Statement Julius Caesar used a system of cryptography,now known as Caesar Cipher,which shifted each letter 2 places further through the alphabet(e.g.A shifts to C,R shifts to T,etc.).At the end of the alphabet we wrap around,that is Y shifts to A.We can,of course,try shifting by any number.Given an encoded text and a number of places to shift,decode it.For example,TOPCODER shifted by 2 places will be encoded as VQREQFGT.In other words,if given(quotes for clarity)VQREQFGT and 2 as input,you will return TOPCODER.See example 0 below.Definition Class:CCipher Method:decode Parameters:string,int Returns:string Method signature:string decode(string cipherText,int shift)(be sure your method is public)Constraints cipherText has between 0 to 50 characters inclusive each character of cipherText is an uppercase letter A-Z 5 shift is between 0 and 25 inclusive Examples 0)VQREQFGT 2 Returns:TOPCODER 1)ABCDEFGHIJKLMNOPQRSTUVWXYZ 10 Returns:QRSTUVWXYZABCDEFGHIJKLMNOP 2)TOPCODER 0 Returns:TOPCODER 3)ZWBGLZ 25 Returns:AXCHMA 4)DBNPCBQ 1 Returns:CAMOBAP 5)LIPPSASVPH 4 Returns:HELLOWORLD Source code#include#include using namespace std;class CCipher public:string decode(string cipherText,int shift)string s=;6 for(int i=0;i(int)cipherText.size();i+)char c=cipherTexti;c=(c-A)-shift+26)%26+A;s+=c;return s;int main()ostream_iterator output(cout,);CCipher cipher;string str=VQREQFGT;string Str=cipher.decode(str,2);copy(Str.begin(),Str.end(),output);coutendl;return 0;4)SRM 148 DIV2,250-point Problem Statement Create a class DivisorDigits containing a method howMany which takes an int number and returns how many digits in number divide evenly into number itself.Definition Class:DivisorDigits Method:howMany Parameters:int Returns:int Method signature:int howMany(int number)(be sure your method is public)Notes No number is divisible by 0.Constraints number will be between 10000 and 999999999.Examples 0)12345 Returns:3 7 12345 is divisible by 1,3,and 5.1)661232 Returns:2 661232 is divisible by 1 and 2(doubled).2)52527 Returns:0 52527 is not divisible by 5,2,or 7.3)730000000 Returns:0 Nothing is divisible by 0.In this case,the number is also not divisible by 7 or 3.Sourece code#include using namespace std;class DivisorDigits public:int howMany(int number)int count=0;int x=number;while(x)int y=x%10;x/=10;if(0=y)continue;if(0=number%y)count+;return count;int main(void)DivisorDigits dd;/int cnt=dd.howMany(12345);/int cnt=dd.howMany(730000000);8 int cnt=dd.howMany(661232);coutcntendl;return 0;5)SRM 149 DIV2,250-point Problem Statement In documents,it is frequently necessary to write monetary amounts in a standard format.We have decided to format amounts as follows:the amount must start with$the amount should have a leading 0 if and only if it is less then 1 dollar.the amount must end with a decimal point and exactly 2 following digits.the digits to the left of the decimal point must be separated into groups of three by commas(a group of one or two digits may appear on the left).Create a class FormatAmt that contains a method amount that takes two ints,dollars and cents,as inputs and returns the properly formatted string.Definition Class:FormatAmt Method:amount Parameters:int,int Returns:string Method signature:string amount(int dollars,int cents)(be sure your method is public)Notes One dollar is equal to 100 cents.Constraints dollars will be between 0 and 2,000,000,000 inclusive cents will be between 0 and 99 inclusive Examples 0)123456 0 Returns:$123,456.00 Note that there is no space between the$and the first digit.1)49734321 9 Returns:$49,734,321.09 9 2)0 99 Returns:$0.99 Note the leading 0.3)249 30 Returns:$249.30 4)1000 1 Returns:$1,000.01 Source code#include#include/#include/#include/#include/#include/#include/#include/#include/#include/#include#include/#include/#include/#include/#include/#include using namespace std;class FormatAmt public:string amount(int,int);string FormatAmt:amount(int dollars,int cents)10 string str=;int n=0;int a100;while(dollars 0)an+=dollars%10;dollars/=10;int count=0;for(int i=0;i 0)an+=cents%10;cents/=10;for(i=1;i=0;i-)str+=char(ai+48);return str;int main(void)FormatAmt amt;coutamt.amount(123456,0)endl;coutamt.amount(49734321,9)endl;coutamt.amount(0,99)endl;coutamt.amount(100,1)endl;return 0;11 6)SRM 150 DIV 2,250-point Problem Statement When a widget breaks,it is sent to the widget repair shop,which is capable of repairing at most numPerDay widgets per day.Given a record of the number of widgets that arrive at the shop each morning,your task is to determine how many days the shop must operate to repair all the widgets,not counting any days the shop spends entirely idle.For example,suppose the shop is capable of repairing at most 8 widgets per day,and over a stretch of 5 days,it receives 10,0,0,4,and 20 widgets,respectively.The shop would operate on days 1 and 2,sit idle on day 3,and operate again on days 4 through 7.In total,the shop would operate for 6 days to repair all the widgets.Create a class WidgetRepairs containing a method days that takes a sequence of arrival counts arrivals(of type vector)and an int numPerDay,and calculates the number of days of operation.Definition Class:WidgetRepairs Method:days Parameters:vector,int Returns:int Method signature:int days(vector arrivals,int numPerDay)(be sure your method is public)Constraints arrivals contains between 1 and 20 elements,inclusive.Each element of arrivals is between 0 and 100,inclusive.numPerDay is between 1 and 50,inclusive.Examples 0)10,0,0,4,20 8 Returns:6 1)0,0,0 10 Returns:0 2)12 100,100 10 Returns:20 3)27,0,0,0,0,9 9 Returns:4 4)6,5,4,3,2,1,0,0,1,2,3,4,5,6 3 Returns:15 Source code#include#include using namespace std;class WidgetRepairs public:int days(vector arrivals,int numPerDay)int rest=0;int num=numPerDay;int count=0;for(int i=0;i 0)count+;rest=restnum?(rest-num):0;while(rest0)count+;rest=restnum?(rest-num):0;return count;13 void main()WidgetRepairs w;/测试数组一/int a=10,0,0,4,20;/vector data(a,a+5);/coutw.days(data,8)endl;/测试数组二/int a=100,100;/vector data(a,a+2);/coutw.days(data,10)endl;/测试数组三/int a=27,0,0,0,9;/vector data(a,a+5);/coutw.days(data,9)endl;/测试数组四int a=6,5,4,3,2,1,0,0,1,2,3,4,5,6;vector data(a,a+14);coutw.days(data,3)endl;