UVA Problem 417 – Word Index Solution:
Click here to go to this problem in uva Online Judge.
Solving Technique:
This one of the worst code I have ever written. It is both slow and wastes huge amount of memory, but still works. I am sharing this code as an example 5 dimensional re-sizable (vector) array. There are far far far better solution than this, so I won’t explain it.
If the input is thought of as string, then for each position the character right to current character is at least current character plus one. Since there are 5 length classes 1,2,3,4,5. So for each of them I applied this logic.
Important: Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.
More Inputs of This Problem on uDebug.
Input:
26 1 0 83681
Output:
z a cat vwxyz
Code:
/**
* Author: Asif Ahmed
* site: quickgrid.wordpress.com
* Problem: UVA 417 - word index
* Technique: Very Slow and worst possible solution.
* 5 (five) dimensioanl vector integer array. 1, 2
* 3, 4 (four) dimensional integer array.
*/
#include <vector>
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 26
int main() {
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
vector<vector<vector<vector<vector<int> > > > > array5d;
array5d.resize(N);
for (int i = 0; i < N; ++i) {
array5d[i].resize(N);
for (int j = 0; j < N; ++j){
array5d[i][j].resize(N);
for (int k = 0; k < N; ++k){
array5d[i][j][k].resize(N);
for (int m = 0; m < N; ++m){
array5d[i][j][k][m].resize(N);
}
}
}
}
int s1[N];
int s2[N][N];
int s3[N][N][N];
int s4[N][N][N][N];
int n = 0;
for(int i = 0; i < N; ++i)
s1[i] = ++n;
for(int i = 0; i < N; ++i){
for(int j = i + 1; j < N; ++j){
s2[i][j] = ++n;
}
}
for(int i = 0; i < N; ++i){
for(int j = i + 1; j < N; ++j){
for(int k = j + 1; k < N; ++k){
s3[i][j][k] = ++n;
}
}
}
for(int i = 0; i < N; ++i){
for(int j = i + 1; j < N; ++j){
for(int k = j + 1; k < N; ++k){
for(int m = k + 1; m < N; ++m){
s4[i][j][k][m] = ++n;
}
}
}
}
for(int i = 0; i < N; ++i){
for(int j = i + 1; j < N; ++j){
for(int k = j + 1; k < N; ++k){
for(int m = k + 1; m < N; ++m){
for(int t = m + 1; t < N; ++t){
array5d[i][j][k][m][t] = ++n;
}
}
}
}
}
char input[N];
while( gets(input) ){
int len = strlen(input);
switch(len){
case 1:
printf("%d\n", s1[ input[0] - 'a' ] );
break;
case 2:
printf("%d\n", s2[ input[0] - 'a' ][ input[1] - 'a' ] );
break;
case 3:
printf("%d\n", s3[ input[0] - 'a' ][ input[1] - 'a' ][ input[2] - 'a' ] );
break;
case 4:
printf("%d\n", s4[ input[0] - 'a' ][ input[1] - 'a' ][ input[2] - 'a' ][ input[3] - 'a' ] );
break;
case 5:
printf("%d\n", array5d[ input[0] - 'a' ][ input[1] - 'a' ][ input[2] - 'a' ][ input[3] - 'a' ][ input[4] - 'a' ] );
break;
}
}
return 0;
}
Quickgrid 