[UVA] 598 - Bundling Newspapers
Bundling Newspapers
| Bundling Newspapers |
A statistical research company needs a program to produce instructions for an existing application that creates questionnaires about newspapers. The application requires instructions that are comma- delimited lists of newspapers, each list consisting of a subset of the set of newspapers in some metropolitan area. Your program will read a list of newspapers and produce this output in a particular order, and for subsets of some range of sizes.
Input
The first line of the input is an integer M, then a blank line followed by M datasets. There is a blank line between datasets.Each dataset consists of a first line describing the sizes of subsets to be output, followed by the names of the newspapers, one per line. Each line is terminated by an end-of-line marker. The newspaper names will contain at most 30 characters each, and there will be a maximum of 12 newspaper names.
The first line will contain either a single asterisk in column one, one positive integer, or two positive
integers, the first less than the second. Any integers in this line will be no greater than the number of
newspapers to follow. The meaning of these is as follows:
* means show all subset sizes from 1 to the number of newspapers in the listmeans show all subset sizes from a to b, inclusive n means show only subsets of size n
Output
The output for each dataset should consist of the comma-delimited subsets of papers, one subset per line, grouped by subset size, and with a header line above each subset size group indicating the size. Print a blank line after each subset size group. Within a subset size group, the order of the lines of output should be listed in such a way that if the names of the first, second and third newspapers listed in the input file were A, B, C, etc., respectively, the output lines would be in lexicographic order (in the example above, A, B; A, C; A, D; B, C; ...).
Print a blank line between datasets.
Sample Input
1 2 3 Times Herald-Tribune Post New Advocate
Sample Output
Size 2 Times, Herald-Tribune Times, Post Times, New Advocate Herald-Tribune, Post Herald-Tribune, New Advocate Post, New Advocate Size 3 Times, Herald-Tribune, Post Times, Herald-Tribune, New Advocate Times, Post, New Advocate Herald-Tribune, Post, New Advocate
Miguel A. Revilla
1999-01-11
覺得還是有必須讓大家認識一下 sscanf 好用的地方。
#include <stdio.h>
#include <iostream>
#include <sstream>
using namespace std;
char word[20][50], line[50];
int n, path[20];
void dfs(int idx, int m, int i) {
if(idx == m) {
for(i = 0; i < idx; i++) {
if(i) printf(", ");
printf("%s", word[path[i]]);
}
puts("");
return;
}
for(; i < n; i++) {
path[idx] = i;
dfs(idx+1, m, i+1);
}
}
int main() {
int testcase;
int a, b, i;
scanf("%d", &testcase);
while(getchar() != '\n');
while(getchar() != '\n');
while(testcase--) {
gets(line);
n = 0;
while(gets(word[n])) {
if(word[n][0] == '\0') break;
n++;
}
if(line[0] == '*') {
a = 1, b = n;
} else {
if(sscanf(line, "%d %d", &a, &b) == 2) {}
else sscanf(line, "%d", &a), b = a;
}
for(i = a; i <= b; i++) {
printf("Size %d\n", i);
dfs(0, i, 0);
puts("");
}
if(testcase) puts("");
}
return 0;
}
/*
3
2 3
Times
Herald-Tribune
Post
New Advocate
1
Times
Herald-Tribune
*
Chinese Times
Union Times
Free Post
*/