Hi I'm here to ask some C++ programming question
I get these question recently from my friend, and I only managed to do two of them ,so I would like to discuss the way to do it in C++ .(some question making me confuse)
There are total of nine question below:
Q1 . Request For Proposal
When government ,military ,or commercial agencies wish to make a major purchase ,they first issue a Request for Proposal(RFP) when lists a number of requirements that must be met by a successful proposal .Competing supplier issue Proposals ,indicating which of the requirements are met ,and a price that will be charged should the proposal be accepted by the agency issuing the RFP.
Because the agencies are staffed by bureaucrats and are accountable to other agencies staffed by bureaucrats ,it is necessary to remove all human judgement from the selection process .To this end ,those evaluating the proposals are given feature sheets , which have one column for each requirement and additional column for price ,and one row for each proposal. The evaluator reads each proposal and identifies each requirement that is met; for each such requirement a check mark is placed in the corresponding row (for the proposal) and column (for each requirement). After all proposals have been evaluated, the number of check marks in each row is added. Any proposal that has the same number of check marks as the number of requirement is said to be compliant; otherwise the proposal is said to be partially compliant. Many agencies award the contract to the lowest compliant proposal; that is the compliant proposal with the lowest price. If there is no compliant proposal, many agencies evaluate partial compliance according to the following formula:
Compliance = number_of_requirements_met/number_of_requirements
Your job is to select to the Proposal with the highest compliance; if several proposals have the same compliance you are to select from the proposals the one with the lowest price. If several proposals have the same compliance and price you are to select the first one in the input.
Standard Input:
Your input will consist of the information for a number of RFPs and associated proposals.The information for each RFP will be consist of:
• A line containing two integers: 0<n<=1000, the number of requirements, and p the number of proposals. The line 0 0 indicates there are no more RFPs.
• N lines naming the requirements. Each requirement is a string up to 80 characters long. Terminated by the end of line. All strings are case sensitive.
• For each of the p proposals:
i) A line naming the proposal (up to 80 characters terminated by end of line)
ii) A line containing a floating point number d and an integer 0 <= r <= n: d is the price; r is the number of met requirement lines to follow.
iii) For each met requirement, the name of the requirement, each on a separate line. All requirements are from the RFP requirement list, andno requirements are duplicated.
Standard Output:
For each RFP, give the number of the RFP followed by the name of the best proposal, optimizing the criteria given above. Leave a blank between the output for each pair of RFPs.
Sample Input:
6 4
engine
brakes
tires
ashtray
vinyl roof
trip computer
Chevrolet
20000.00 3
engine
tires
brakes
Cadillac
70000.00 4
ashtray
vinyl roof
trip computer
engine
Hyundai
10000.00 3
engine
tires
ashtray
Lada
6000.00 1
tires
1 1
coffee
Startbucks
1.50 1
coffee
0 0
Output for Sample Input:
RFP #1
Cadillac
RFP #2
Starbucks
Q2. Compound Words
You are to find all the two-word compound words in a dictionary. A two-word compound word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.
Standard Input
Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 120,000 words.
Standard output
Your output should contain all compound words, one per line, in alphabetical order.
Sample Input
a
lien
alien
born
less
never
nevertheless
new
newborn
the
zebra
Sample Output
alien
newborn
Q3 It Can't Get Any Bigger Than This
take two lines of input and produce a sorted list of all the maximal common substrings. That is to say, if the input strings are X and Y (drawn from the set Sigma*), produce a list of all x such that x is a substring of both X and Y, but for all s in Sigma, neither sx nor xs is a substring of both X and Y.
Sample Input
hi,_how_are_you_today?
fine,_thank-you_very_much.
Sample Output
,_
_t
a
e
h
i
r
you_
Q4 CD Titles
A keen photographer, I found my hard disk quickly filling up with snapshots and videos. I decided to offload a lot of the files to CD. Each CD is in its own plastic case, and the contents are clearly described on the front of the case. As the number of CDs increased, I built myself a shelf on which the CDs stand vertically.
I need your help! I have written a title for each CD into a text file, but I need the titles to appear vertically so that I can put them in the spine of the CD cases and be able to read them easily from the shelf. I want you to write a program that will output my titles vertically. I need lines between each title so that, when I print them, I can easily cut along the lines.
I have worked out that I can fit 36 characters into the available space, so all output titles must be 36 characters long, padded with spaces at the end of where necessary. If I accidentally make a title too long, only output the first 36 characters.
Standard Input
Input will be at most 50 titles, one to a line. Each title consists of 1 to 100 arbitrary characters. A single ‘#’ on a line by itself indicates the end of input.
Standard Output
Output will be same titles presented vertically, where the left to right order will be the same as the order of the input. There will be a column of bar (‘|’) characters at each end, and separating each title, and a row of minus (‘-‘) characters (1 per column)at the beginning and end.
Sample Input
012345678901234567890123456789012345
David and Jane’s wedding, March 2002,
Bahamas Holiday August 2001
#
Sample Output
|0|D|B|
|1|a|a|
|2|v|h|
|3|i|a|
|4|d|m|
|5| |a|
|6|a|s|
|7|n| |
|8|d|H|
|9| |o|
|0|J|l|
|1|a|i|
|2|n|d|
|3|e|a|
|4|’|y|
|5|s| |
|6| |A|
|7|w|u|
|8|e|g|
|9|d|u|
|0|d|s|
|1|i|t|
|2|n| |
|3|g|2|
|4|,|0|
|5| |0|
|6|M|1|
|7|a| |
|8|r| |
|9|c| |
|0|h| |
|1| | |
|2|2| |
|3|0| |
|4|0| |
|5|2| |
There are total of nine question below:
Q1 . Request For Proposal
When government ,military ,or commercial agencies wish to make a major purchase ,they first issue a Request for Proposal(RFP) when lists a number of requirements that must be met by a successful proposal .Competing supplier issue Proposals ,indicating which of the requirements are met ,and a price that will be charged should the proposal be accepted by the agency issuing the RFP.
Because the agencies are staffed by bureaucrats and are accountable to other agencies staffed by bureaucrats ,it is necessary to remove all human judgement from the selection process .To this end ,those evaluating the proposals are given feature sheets , which have one column for each requirement and additional column for price ,and one row for each proposal. The evaluator reads each proposal and identifies each requirement that is met; for each such requirement a check mark is placed in the corresponding row (for the proposal) and column (for each requirement). After all proposals have been evaluated, the number of check marks in each row is added. Any proposal that has the same number of check marks as the number of requirement is said to be compliant; otherwise the proposal is said to be partially compliant. Many agencies award the contract to the lowest compliant proposal; that is the compliant proposal with the lowest price. If there is no compliant proposal, many agencies evaluate partial compliance according to the following formula:
Compliance = number_of_requirements_met/number_of_requirements
Your job is to select to the Proposal with the highest compliance; if several proposals have the same compliance you are to select from the proposals the one with the lowest price. If several proposals have the same compliance and price you are to select the first one in the input.
Standard Input:
Your input will consist of the information for a number of RFPs and associated proposals.The information for each RFP will be consist of:
• A line containing two integers: 0<n<=1000, the number of requirements, and p the number of proposals. The line 0 0 indicates there are no more RFPs.
• N lines naming the requirements. Each requirement is a string up to 80 characters long. Terminated by the end of line. All strings are case sensitive.
• For each of the p proposals:
i) A line naming the proposal (up to 80 characters terminated by end of line)
ii) A line containing a floating point number d and an integer 0 <= r <= n: d is the price; r is the number of met requirement lines to follow.
iii) For each met requirement, the name of the requirement, each on a separate line. All requirements are from the RFP requirement list, andno requirements are duplicated.
Standard Output:
For each RFP, give the number of the RFP followed by the name of the best proposal, optimizing the criteria given above. Leave a blank between the output for each pair of RFPs.
Sample Input:
6 4
engine
brakes
tires
ashtray
vinyl roof
trip computer
Chevrolet
20000.00 3
engine
tires
brakes
Cadillac
70000.00 4
ashtray
vinyl roof
trip computer
engine
Hyundai
10000.00 3
engine
tires
ashtray
Lada
6000.00 1
tires
1 1
coffee
Startbucks
1.50 1
coffee
0 0
Output for Sample Input:
RFP #1
Cadillac
RFP #2
Starbucks
Q2. Compound Words
You are to find all the two-word compound words in a dictionary. A two-word compound word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.
Standard Input
Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 120,000 words.
Standard output
Your output should contain all compound words, one per line, in alphabetical order.
Sample Input
a
lien
alien
born
less
never
nevertheless
new
newborn
the
zebra
Sample Output
alien
newborn
Q3 It Can't Get Any Bigger Than This
take two lines of input and produce a sorted list of all the maximal common substrings. That is to say, if the input strings are X and Y (drawn from the set Sigma*), produce a list of all x such that x is a substring of both X and Y, but for all s in Sigma, neither sx nor xs is a substring of both X and Y.
Sample Input
hi,_how_are_you_today?
fine,_thank-you_very_much.
Sample Output
,_
_t
a
e
h
i
r
you_
Q4 CD Titles
A keen photographer, I found my hard disk quickly filling up with snapshots and videos. I decided to offload a lot of the files to CD. Each CD is in its own plastic case, and the contents are clearly described on the front of the case. As the number of CDs increased, I built myself a shelf on which the CDs stand vertically.
I need your help! I have written a title for each CD into a text file, but I need the titles to appear vertically so that I can put them in the spine of the CD cases and be able to read them easily from the shelf. I want you to write a program that will output my titles vertically. I need lines between each title so that, when I print them, I can easily cut along the lines.
I have worked out that I can fit 36 characters into the available space, so all output titles must be 36 characters long, padded with spaces at the end of where necessary. If I accidentally make a title too long, only output the first 36 characters.
Standard Input
Input will be at most 50 titles, one to a line. Each title consists of 1 to 100 arbitrary characters. A single ‘#’ on a line by itself indicates the end of input.
Standard Output
Output will be same titles presented vertically, where the left to right order will be the same as the order of the input. There will be a column of bar (‘|’) characters at each end, and separating each title, and a row of minus (‘-‘) characters (1 per column)at the beginning and end.
Sample Input
012345678901234567890123456789012345
David and Jane’s wedding, March 2002,
Bahamas Holiday August 2001
#
Sample Output
|0|D|B|
|1|a|a|
|2|v|h|
|3|i|a|
|4|d|m|
|5| |a|
|6|a|s|
|7|n| |
|8|d|H|
|9| |o|
|0|J|l|
|1|a|i|
|2|n|d|
|3|e|a|
|4|’|y|
|5|s| |
|6| |A|
|7|w|u|
|8|e|g|
|9|d|u|
|0|d|s|
|1|i|t|
|2|n| |
|3|g|2|
|4|,|0|
|5| |0|
|6|M|1|
|7|a| |
|8|r| |
|9|c| |
|0|h| |
|1| | |
|2|2| |
|3|0| |
|4|0| |
|5|2| |
Last edited on
Q5 Soundex
Soundex coding groups together words that appear to sound alike based on their spelling. For example, “can” and “khawn”, “con” and “gone” would be equivalent under Soundex coding. Soundex coding involves translating each word into a series of digits in which each digit represents a letter:
1 represents B, F, P, or V
2 represents C, G, J, K, Q, S, X, or Z
3 represents D or T
4 represents L
5 represents M or N
6 represents R
The letter A, E, I, O, U, H, W, and Y are not represented in Soundex coding, and repeated letter with the same code digit are represented by a single instance of that digit. Words with the same Soundex coding are considered equivalent.
Each line of input contains a single word, all upper case, less than 20 letterslong. For each line of input, produce a line of output giving the Soundex code.
Example 1
Sample Input
KHAWN
Sample output
25
Example 2
Sample Input
BOBBY
Sample output
1
Q6 Number Speller
Create a program that is able to spell out numbers from 1 to 9999 that are entered in alphabetic form.
Example 1
Sample Input
Forty
Sample Output
40
Example 2
Sample Input
Two thousand seven
Sample Output
2007
Q7 Power Strings
Given two strings a and b we define a*b to be their concatenation. For example, if a = “abc” and b = “def” then a*b = “abcdef”. If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = “” (the empty string) and a^(n+1) = a*(a^n).
Each test case is a line of input representing s, a string of printable characters. For each s you should print the largest n such that s = a^n for some string a. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.
Example 1
Sample Input
abcd
Sample Output
1
Example 2
Sample Input
abcabcabcabc
Sample Output
4
Q8 Perfect Number Checker
A positive integer is said to be a perfect number if it is equal to the sum of ist positive divisors less than itself.
For example, 28 is perfect, because
28 = 1 + 2 + 4 + 7 + 14
On the other hand, 12 is not perfect, because
12 != 1 + 2 + 3 + 4 + 6
You are to write a program that prompts the user to enter a positive integer and responds by reporting whether or not the given number is perfect.
Example 1
Sample Input
Enter a positive integer: 12
Sample Output
12 IS NOT perfect.
Example 2
Sample Input
Enter a positive integer: 28
Sample Output
28 IS perfect
Q9 Fibonacci
A Fibonacci sequence is calculated by adding the previous two members of the sequence, with the first two members being both 1.
f(1) = 1,f(2) = 1,f(n > 2) = f(n - 1) + f(n - 2)
Your task is to take a number as input and print that Fibonacci number.
Sample Input
7
Sample Output
13
Soundex coding groups together words that appear to sound alike based on their spelling. For example, “can” and “khawn”, “con” and “gone” would be equivalent under Soundex coding. Soundex coding involves translating each word into a series of digits in which each digit represents a letter:
1 represents B, F, P, or V
2 represents C, G, J, K, Q, S, X, or Z
3 represents D or T
4 represents L
5 represents M or N
6 represents R
The letter A, E, I, O, U, H, W, and Y are not represented in Soundex coding, and repeated letter with the same code digit are represented by a single instance of that digit. Words with the same Soundex coding are considered equivalent.
Each line of input contains a single word, all upper case, less than 20 letterslong. For each line of input, produce a line of output giving the Soundex code.
Example 1
Sample Input
KHAWN
Sample output
25
Example 2
Sample Input
BOBBY
Sample output
1
Q6 Number Speller
Create a program that is able to spell out numbers from 1 to 9999 that are entered in alphabetic form.
Example 1
Sample Input
Forty
Sample Output
40
Example 2
Sample Input
Two thousand seven
Sample Output
2007
Q7 Power Strings
Given two strings a and b we define a*b to be their concatenation. For example, if a = “abc” and b = “def” then a*b = “abcdef”. If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = “” (the empty string) and a^(n+1) = a*(a^n).
Each test case is a line of input representing s, a string of printable characters. For each s you should print the largest n such that s = a^n for some string a. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.
Example 1
Sample Input
abcd
Sample Output
1
Example 2
Sample Input
abcabcabcabc
Sample Output
4
Q8 Perfect Number Checker
A positive integer is said to be a perfect number if it is equal to the sum of ist positive divisors less than itself.
For example, 28 is perfect, because
28 = 1 + 2 + 4 + 7 + 14
On the other hand, 12 is not perfect, because
12 != 1 + 2 + 3 + 4 + 6
You are to write a program that prompts the user to enter a positive integer and responds by reporting whether or not the given number is perfect.
Example 1
Sample Input
Enter a positive integer: 12
Sample Output
12 IS NOT perfect.
Example 2
Sample Input
Enter a positive integer: 28
Sample Output
28 IS perfect
Q9 Fibonacci
A Fibonacci sequence is calculated by adding the previous two members of the sequence, with the first two members being both 1.
f(1) = 1,f(2) = 1,f(n > 2) = f(n - 1) + f(n - 2)
Your task is to take a number as input and print that Fibonacci number.
Sample Input
7
Sample Output
13
For the first question , I totally don't get the idea , and the second question there i have some problem of using c-string to do it
Don't ask about all of them at once.
Q1. I'll read the input file for you, maybe that will make things more clear..
For the first "RFP", there are 6 requirements : engine, brakes, tires, ashtray, vinyl roof and trip computer. There are 4 proposals : Chevrolet, Cadillac, Hyundai and Lada. The line under each of those shows their price and the number of requirements they meet. It doesn't even matter what those requirements are. The number is important. After you've read all the proposals, there is another pair of numbers, for the second RPF, which has one requirement and one proposal which meets that requirement. After that, a pair of 0s means that there are no more RPFs to read.
Your task is, for each RPF, to find a proposal which meets the most requirements. If some proposals meet the same number of requirements, choose the cheaper one. This is simply a problem of finding the maximum value in the array.
Q1. I'll read the input file for you, maybe that will make things more clear..
For the first "RFP", there are 6 requirements : engine, brakes, tires, ashtray, vinyl roof and trip computer. There are 4 proposals : Chevrolet, Cadillac, Hyundai and Lada. The line under each of those shows their price and the number of requirements they meet. It doesn't even matter what those requirements are. The number is important. After you've read all the proposals, there is another pair of numbers, for the second RPF, which has one requirement and one proposal which meets that requirement. After that, a pair of 0s means that there are no more RPFs to read.
Your task is, for each RPF, to find a proposal which meets the most requirements. If some proposals meet the same number of requirements, choose the cheaper one. This is simply a problem of finding the maximum value in the array.
Thank you very much , i think i can work it up with your explanation .Cause my english no so good so some of the question just like a wall for me.
Well actually these question are from a programming contest of my friend , and my friend and i have difficulty on it , so i just try to post in on the forum see whether can get some reply or not .
Well actually these question are from a programming contest of my friend , and my friend and i have difficulty on it , so i just try to post in on the forum see whether can get some reply or not .
And about the 4th question there , i'm using struct and a array to do it , but there are some problem when it when to looping .
but i guess using 2 dimension array will be better ?
but i guess using 2 dimension array will be better ?
For 4 you need an array of strings. Since strings can be plain arrays themselves, you end up with a 50x37 array. It could also be std::vector< std::string >, though that is not necessary.
Topic archived. No new replies allowed.