Input Taking Strategies
Judging by some of the submissions we receive most people seem to be getting the programming approach right on many of the problems, but fumble when it comes to handling the sometimes tricky input descriptions that the problems have. Here we shall see methods to handle some of the more common (and uncommon) input specifications of problems.
I. Single test case, number of inputs specified
This is as simple as it can get; a single test case with the number of inputs following specified. Example: Input consists of a single test case, beginning with a number N, specifying the number of inputs to follow. Sample Input: 5 1 2 3 4 5 [C++ Code] int N = 0; cin >> N; for (int i = 0; i < N; i++) { &bsp; int val; cin >> val; }
[C++ Code]
int N = 0; cin >> N; while (N--) { int val; cin >> val; }
[C Code] int N = 0; scanf("%d", &N); for (int i = 0; i < N; i++) { int val; scanf("%d", &val); }
[C Code] int N = 0; scanf("%d", &N); while (N--) { int val; scanf("%d", &N); } Note that cin and scanf ignore whitespace. So the above code would work even if more than one input were on the same line, as follows:
Sample Input 5123 45
II. Multiple test case, number of inputs for each test case specified
In this case, each test case specified the number of inputs in it at the beginning, but there can be multiple test cases, the count of which is not specified. Example: Input consists of a multiple test cases, each beginning with a number N, specifying the number of inputs in that test case. Sample Input: 3 1 2 3 2 4 5 Here, a test case may be followed by either another test case, or EOF (End-Of-File), which is a special character that signals the end of the input (on most implementations it is -1). You can send EOF on the console with Ctrl-Z. So what we have to do here is take input until EOF is encountered. Lets see this in action: [C++ Code] int N = 0; while (cin >> N) { for (int i = 0; i < N; i++) { int val = 0; cin >> val;
} }
[C Code] int N = 0; while (scanf("%d", &N) != EOF) { for (int i = 0; i < N; i++) {
int val = 0;
scanf("%d", &val); } }
III. Inputting strings - whitespace separated words
Handling strings can often be tricky. Lets consider the case where we simply want to input space separated strings (words). Example: Input consists of a number of space separated words. Sample Input: Association for Computing Machinery [C++ Code] char str[64] = { 0 }; while (cin >> str) cout << str << endl;
[C Code]
char str[64] = { 0 }; while (scanf("%s", str)) printf("%s\n", str);
IV. Inputting strings - lines of strings
In this case you have to read each line of text, terminated by '\n'. Example: Input consists of multiple lines of text. Sample Input: Association for Computing Machinery a club dedicated to the promotion of computing as a profession and science [C++ Code] char str[64] = { 0 }; while (cin.getline(str, 64)) cout << str << endl;
[C Code] char str[64] = { 0 }; while (fgets(str, 64, stdin)) // fgets appends the '\n' to the string printf("%s", str); Sometimes you may find it useful to read a line of text one character at a time...
[C++ Code]
char str[64] = { 0 };
int inp = 0;
while ((inp = cin.get()) != EOF) // There is a reason why int is used where there can be a potential EOF // In 99% of the cases using char won't affect your program // But it is good programming practice // The reason is given in Kernighan & Ritchie { int i = 0; str[i] = inp; while ((str[++i] = cin.get()) != '\n'); str[i] = 0; cout << str << endl; }
[C Code] char str[64] = { 0 }; int inp = 0;
while ((inp = getchar()) != EOF) { int i = 0; str[i] = inp; while ((str[++i] = getchar()) != '\n'); str[i] = 0; cout << str << endl;
V. Reading formatted input
Often you get input specifications where the input is given in a particular format. For example, you may have to read a date given in the following format: dd/mm/yyyy C comes in very handy for the above situation. Note that you can use the powerful formatted I/O functions of C in C++ by including <cstdio>. [C/C++ Code] #include <cstdio> #include <stdio.h> ... int d, m, y; scanf("%d/%d/%d", &d, &m, &y); // If you are using C++ // If you are using C
VI. Really Tricky Inputs
Example: Input consists of multiple test cases. Each test case consists of a list of numbers on a single line. The count of numbers per line is not specified and may vary from line to line. Sample Input: 12345 678 9 10 11 23 100 500 600
This one is really tricky. If you are not familiar with some of the less known functions of &t;iostream> or <stdio.h>, your first approach might be to read one character at a time, if it is a digit you have got the beginning of a new number and continue reading characters and appending to the number till you hit whitespace, skip all the whitespace, read next digit, and so on... until you read '\n' which indicates the end of a test case. This really dirty approach might look something like this: [C Code]
int N = 0; int numbers[64] = { 0 }; int current = 0; int temp = 0; while ((current = getchar()) != EOF) { N = 0; do &nbp; { while (!isdigit(current) && current != '\n') current = getchar(); if (current == '\n') break; current -= '0'; while (isdigit(temp = getchar())) current = current * 10 + temp - '0'; numbers[N++] = current; } while (1); } Really ugly, right? Fortunately, C gives us a way to solve this problem very elegantly. Check out the neat code below: [C Code] int numbers[64] = { 0 }; char str[128] = { 0 }; int N = 0; int len = 0; int n = 0;
while (fgets(str, 128, stdin)) { len = 0; N = 0; while (sscanf(str + len, "%d%n", &numbers[N], &n) != EOF) { len += n; N++; } } %n is a little known specifier in scanf that returns the number of bytes read as input till the point where it is specified. sscanf is a function that reads input from a specified string. Its output counterpart is sprintf. The rest should be easy to understand. C++ also gives us a way to do this using streams. It is much more elegant and intuitive but we will not be explaining it here as it is beyond the scope of this tutorial. Look up "string" and "stringstream" classes in the STL (Standard Template Library). The code is as follows: [C++ STL Code] #include <string> #include <sstream> ... string str; int numbers[64] = { 0 }; int N = 0;
while (getline(cin, str)) { N = 0; stringstream in(str);
while (in >> numbers[N]) N++; }
Master these techniques and input taking will no longer be a problem for you. Make sure you practice applying these to as many different types of problems as possible. Good luck!
by Rahul Ramadas
About ACM Copyright 2008, ACM BIT, Mesra. All rights reserved.
