## UVA Problem 10432 – Polygon Inside A Circle Solution

UVA Problem 10432 – Polygon Inside A Circle Solution:

Solving Technique:

This is a rather easy geometry / computational geometry problem. Given the radius of a Circumscribed circle and count of sides of a polygon the task is to find the area of the polygon. A Circumscribed circle is a circle that passes through all vertices of a plane figure and contains the entire figure in its interior.

The formula below can be written into a single formula by combining all the formulas. More information and the combined formula can be found here.

##### Visual Explanation:

I have tried to explain the concept below using figures. They are not drawn to scale. The small circles represent intersection point between polygon vertices and the circumscribed circle.

##### Example:

It is an example with radius, r = 2 and sides, n = 8.

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:

2 2000
10 3000


Output:

12.566
314.159


### Code:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 10432 - Polygon Inside A Circle
* Technique: circumcircle Or, Isocele Area calculation.
*/

#include<stdio.h>
#include<string.h>
#include<math.h>

int main(){

//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

double r;
int n;

while( scanf( "%lf%d", &r, &n ) == 2 ){

// Angle between each two points for every point.
double PHI = ( double ) 360 / n ;

// For each Isosceles in the polygon the angle between the base and radius.
double THETA = (double) 90 - ( PHI / 2 );

// Convert Degree angle to Radian to use in code.
double THETA_RADIAN = THETA * M_PI / 180;

//  a is base.
double a = 2 * r * cos( THETA_RADIAN );

// H is the height.
double h = r * sin( THETA_RADIAN );

// S represent Area of a single segment.
double S = (a * h) / 2;

// S * n is the are of complete polygon.
printf("%.3lf\n",  S * n );

}

return 0;
}


## UVA Problem 11716 – Digital Fortress Solution

UVA Problem 11716 – Digital Fortress Solution:

Solving Technique:

This is an easier string problem. The task is to arrange the characters within the string in a certain order.

If the input string length is not square of a number then print INVALID. Ex: “DAVINCICODE” has length of 11. Squaring no number results in 11.

“DTFRIAOEGLRSI TS” has length of 16 including the space character. Square root of 16 is 4 and 4 * 4 is 16. So this is valid input.

Now if the input is valid then next task is to rearrange them. Instead of following given solution technique in the question it can solved much faster in another way. Following instruction in the question gives intuition that first the string must be positioned on 2 dimensional matrix in row major order. Then traverse them column by column.

A better way is find out each group length from square rooting the original string length. Next starting from first group take a character then skip by group length to get next column major character. After its done do this from the next character of first group.

##### Visualization:

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:

3
WECGEWHYAAIORTNU
DAVINCICODE
DTFRIAOEGLRSI TS


Output:

WEAREWATCHINGYOU
INVALID
DIGITAL FORTRESS


### Code:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 11716 - Digital Fortress
* Technique: Square String Traverse from row major
*            to column major by skipping.
*/

#include<stdio.h>
#include<string.h>
#include<math.h>

#define N 10002
static char s[N];
static char output[N];

int main(){

//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

int n;
scanf("%d", &n);
getchar();

while( n-- ){
gets(s);

// Get the length of string and length of each string group.
int len = strlen(s);
int rc = sqrt(len);

// Reset in case there are characters from previous iteration.
memset(output, 0, sizeof output);

// If the string length can be divided into equal parts
// then traverse by skipping certain length.
if( rc * rc == len ){

int k = 0;

for( int j = 0; j < rc; ++j ){
for( int i = j; i < len; i = i + rc ){
output[k++] = s[i];
}
}

puts(output);

}
else{
puts("INVALID");
}

}

return 0;
}


## UVA Problem 12646 – Zero or One Solution

UVA Problem 12646 – Zero or One Solution:

Solving Technique:

The input is all possible combination of 3 bits. If A, B, C are thought as bits then possible binary combination are,

$000 \rightarrow * \\ 001 \rightarrow C \\ 010 \rightarrow B \\ 011 \rightarrow A \\ ---- \\ 100 \rightarrow A \\ 101 \rightarrow B \\ 110 \rightarrow C \\ 111\rightarrow * \\$

This problem can be solved in multiple ways such as using string, checking equality, performing xor equality etc. My code below is exactly same as equality checking but it perform xor operation between them.

XOR Table,

$\begin{tabular}{l*{6}{c}r} X & Y & X XOR Y \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{tabular}$

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:

1 1 0
0 0 0
1 0 0


Output:

C
*
A


### Code:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 12646 - zero or one
* Technique: XOR Bits to check equality.
*/

#include<stdio.h>

int main(){

//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);

int A, B, C;
while( scanf("%d%d%d", &A, &B, &C) == 3 ){

if( !( A ^ B ) && !( A ^ C ) )
putchar('*');
else{
if( A ^ B ){
if( B ^ C )
putchar('B');
else
putchar('A');
}
else
putchar('C');
}
putchar('\n');
}

return 0;
}


## UVA Problem 10008 – What’s Cryptanalysis? Solution

UVA Problem 10008 – What’s Cryptanalysis? Solution:

Solving Technique:

Task for this problem is to find occurrence of each alphabetical character. Uppercase and lowercase are treated as same characters. No other characters except for upper and lower case characters must be counted.

After counting their occurrence print them in most to least order. If multiple characters have same character count then print the characters alphabetically. Ex: If E occurred 2 times, A occurred 2 times then, print A first then E.

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:

3
This is a test.
Count me 1 2 3 4 5.
Wow!!!! Is this question easy?


Output:

S 7
T 6
I 5
E 4
O 3
A 2
H 2
N 2
U 2
W 2
C 1
M 1
Q 1
Y 1


### Code:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 10008 - What's Cryptanalysis
* Technique: Counting character occurrence in string,
*            Lexicographical / alphabetically sort characters,
*/

#include<stdio.h>
#include<string.h>
#include<algorithm>

#define N 256

// Holds each character and its occurrence in string.
struct collection{
char character;
int occurence;
} node[26];

static char s[N];

// Sorts based on occurrence, if occurrence count is same
// then sort using lexicographical / alphabetically first character.
int cmp(collection a, collection b){

if(a.occurence < b.occurence)
return 0;
else if(a.occurence > b.occurence)
return 1;
else
return (a.character <= b.character) ? 1 : 0;

}

int main(){

// O(1)
// Represent character by its ASCII value index.
for(int i = 'A'; i <= 'Z'; ++i)
node[i].character = i;

int n;

scanf("%d", &n);
getchar();

while( n-- ){

gets( s );

// Convert string to uppercase O(n)
for(int i = 0; s[i]; ++i){
if( s[i] >= 'a' && s[i] <= 'z')
s[i] = s[i] - 32;
}

// O(n)
// Counting using character index
for(int i = 0; s[i]; ++i){
if( s[i] >= 'A' && s[i] <= 'Z' )
++node[ s[i] ].occurence;
}

}

// Sorts occurrence most to least and in lexicographic order.
std::sort(node + 'A', node + 'Z', cmp);

// O(1)
// Prints sorted occurrence most to least.
// Also prints characters in lexicographic
// order if two occurrence are same.
for(int i = 'A'; i <= 'Z'; ++i){
if(node[i].occurence)
printf("%c %d\n", node[i].character, node[i].occurence);
}

return 0;
}


## UVA Problem 11713 – Abstract Names Solution

UVA Problem 11713 – Abstract Names Solution:

Solving Technique:

For input of n there will be 2*n lines. Task is to match a pair of lines. The vowels a, e, i, o, u in the strings doesn’t matter. Except these the rest of both strings should match.

That means each character in a index from both strings should match. Their order needs to be same. Except vowels if the match then output is yes. Otherwise the output is no.

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:

5
pele
polo
pele
pola
ronaldo
ronaldino
pele
pelet
pele
bele


Output:

Yes
Yes
No
No
No


### Code:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 11713 - Abstract Names
* Technique: Removing specific characters from string
*            by copying into another string.
*/

#include<stdio.h>
#include<string.h>

#define N 36

static char s[N];
static char t[N];

static char tmpS[N];
static char tmpT[N];

int main(){

int n;

scanf("%d", &n);
getchar();

while( n-- ){

gets(s);
gets(t);

// If their length is not the same then output is no.
if( strlen(s) != strlen(t) ){
printf("No\n");
continue;
}

// Reset memory.
int j = 0, k = 0;
memset(tmpS, 0, sizeof tmpS);
memset(tmpT, 0, sizeof tmpT);

// Remove vowels from the first string.
for(int i = 0; s[i]; ++i){
if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u')
continue;
else
tmpS[j++] = s[i];
}

// Remove vowels from the second the string.
for(int i = 0; t[i]; ++i){
if(t[i] == 'a' || t[i] == 'e' || t[i] == 'i' || t[i] == 'o' || t[i] == 'u')
continue;
else
tmpT[k++] = t[i];
}

// After removing the vowels the strings should match.
if( strcmp(tmpS, tmpT) == 0 )
printf("Yes\n");
else
printf("No\n");

}

return 0;
}


## UVA Problem 1225 – Digit Counting Solution

UVA Problem 1225 – Digit Counting Solution:

Solving Technique:

This problem is very easy. For input N = 13, sequence is 12345678910111213. which are actually numbers from 1 to 13 without spaces.

1 2 3 4 5 6 7 8 9 10 11 12 13


For this problem just calculate how many times a digit appears in the sequence. The digits being 0 to 9.

Use counting sort to easily calculate occurrence of a digit. If a digit is greater than single digit than break it to a single digit and increment count.

Here i have given two solutions. One converts digits to character than counts them. The next one count each digit in the integer without converting to string.

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:

2
3
13


Output:

0 1 1 1 0 0 0 0 0 0
1 6 2 2 1 1 1 1 1 1


### Code Using Character Count:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 1225 - Digit Counting
* Technique: Counting sort characters, Integer to character conversion.
*/

#include<stdio.h>
#include<string.h>

#define N 200000

static char output[N];
static int outputNum[10];

int main() {

int n;

scanf("%d", &n);

while( n-- ){

int num;
scanf("%d", &num);

memset(outputNum, 0, sizeof outputNum);

/**
* Add the numbers to character array for easier counting.
* If number is more then one digit it assign each digit to
* a new location in char array. Although they are actually
* reversed when positioning. But the order does not matter
* in this problem. Just count each digit.
*
* It is possible to count with integers rather than using
* char array. See the next code.
*/
int k = 0;
for(int i = 1; i <= num; ++i){

int num = i;
while(num){
output[k++] = (num % 10) + '0';
num /= 10;
}
}
output[k] = '\0';

/**
* Use counting sort sort technique to position each
* character to its equivalent integer location.
*/
for(int i = 0; output[i]; ++i)
++outputNum[ output[i] - '0' ];

for(int i = 0; i < 10; ++i){
if(i) printf(" ");
printf("%d", outputNum[i]);
}
printf("\n");
}

return 0;
}



### Code Using Integer Count:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 1225 - Digit Counting
* Technique: Counting sort characters, Integer to character conversion.
*/

#include<stdio.h>
#include<string.h>

static int outputNum[10];

int main() {

int n;

scanf("%d", &n);

while( n-- ){

int num;
scanf("%d", &num);

memset(outputNum, 0, sizeof outputNum);

/**
* It is possible to count the digits without convert char array.
* Count each digit using counting sort technique.
*/
int k = 0;
for(int i = 1; i <= num; ++i){

int num = i;
while(num){
++outputNum[num % 10];
num /= 10;
}
}

for(int i = 0; i < 10; ++i){
if(i) printf(" ");
printf("%d", outputNum[i]);
}
printf("\n");
}

return 0;
}


## UVA Problem 10699 – Count the factors Solution

UVA Problem 10699 – Count the factors Solution:

Solving Technique:

The problem requirement is to find the prime factors of a given number. If the input number is divisible by a prime number then that prime number is a prime factor of input.

Similarly do this with all prime numbers less than the input if it is divisible then increase prime factor count. It seems like there is a way to cut down running time in this very code, but I am not able find it.

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:

289384
930887
692778
636916
747794
238336
885387
760493
516650
641422
0


Output:

289384 : 3
930887 : 2
692778 : 5
636916 : 4
747794 : 3
238336 : 3
885387 : 2
760493 : 2
516650 : 3
641422 : 3


### Code:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 10699 - count the factors
* Technique: Efficient Prime Generation, Sieve of Eratosthenes.
*/

#include<stdio.h>
#include<math.h>

/**
* Since value can be up to 1000000
*/

#define N 1000000

int primesTable[N];
int onlyPrimesTable[N];

int k = 0;

void SieveOfEratosthenes(){

int i = 2;

/**
* Set Every index in the table to be prime.
*/
for(; i <= N; ++i)
primesTable[i] = 1;

/**
* Base case 0 and 1 are not primes.
*/
primesTable[0] = primesTable[1] = 0;

int len = sqrt(N);

/**
* Set all multiples of a number to 0 since primes can't divisible by other than itself.
*/
for(i = 2; i <= len; ++i){
if(primesTable[i]){
for( int k = i << 1; k <= N; k += i )
primesTable[k] = 0;
}
}

/**
* This is not really a part of Sieve of Eratosthenes.
* It checks if a number is prime then it moves primes
* to another array which only contain primes and this
* reduces the number of lookups.
*/
for(i = 0; i <= N; ++i){
if(primesTable[i])
onlyPrimesTable[k++] = i;
}
}

int main() {

/**
* Pre generate primes and isolate them to another array.
*/
SieveOfEratosthenes();

int n;

/**
* Input the number and check if its 0.
*/
while(scanf("%d", &n) && n){

int c = 0;

/**
* If the number is divisible by a prime then,
* increase prime factor count.
*/

for(int i = 0; i < k; ++i){
if( n % onlyPrimesTable[i] == 0)
++c;
}

printf("%d : %d\n", n, c);

}

return 0;
}


## UVA Problem 10851 – 2D Hieroglyphs decoder Solution

UVA Problem 10851 – 2D Hieroglyphs decoder Solution:

Solving Technique:

This problem may look a little hard at first but the problem could be easily reverse engineered from the problem statement. Before starting this if you are familiar with UVA PROBLEM 10878 – DECODE THE TAPE then apply that knowledge. This problem is also very similar.

It is also possible to pre calculate a pattern table based on printable ASCII character then apply a string matching algorithm ( which is harder than this ). This is a reminder for myself and anyone else who wants to implement this method.

Here $\forall$ is called universal quantifier, so $\forall$ can be termed as for all and $\in$ means member of or, element of or, in.

##### Dissecting problem statement to create pattern generator:

H is a 2D array. It is filled following rules below. I have used H as a function to generate the 2D pattern,

$H_{i,j} = \begin{cases} ' \backslash ' & \forall i = 0, j \in (0, 1, ..., M + 1) \\ ' \backslash ' & \forall i = 9, j \in (0, 1, ..., M + 1) \\ ' \backslash ' & \forall j = 0, j \in (0, 1, ..., 9) \\ ' \backslash ' & \forall j = M + 1, i \in (0, 1, ..., 9) \\ b(i - 1, c_{j-1}) & \forall i \in (1, 2, ..., 8) , j \in (1, ..., M) \\ \end{cases}$

Its Helper function,

$b(i, c) = \begin{cases} ' / ' & if, \ \frac{c}{2^i} \ mod \ 2 \ == \ 0 \\ ' \backslash ' & if, \ \frac{c}{2^i} \ mod \ 2 \ == \ 1 \\ \end{cases}$

As described in the problem statement M is the length of the string and their are M + 2 columns ( from 0 to M + 1 columns ). Also there will always be 10 rows of input.

When i is 0 or, i is 9 and j is from 0 to M + 1 print backslash.
Also when j is 0 or, j is M + 1 ( last column ) and i is from 0 to 9 then print backslash.

From above it is clearly visible there are two functions. H function depends on the b function to print slashes when i is 1 to 8 and j is 1 to M ( Length of String ). This means omitting the first, last row and first, last column.

When i is 1 to 8 and j is 1 to M the output depend on $b(i,c)$ function. Which prints a slash based on input. It checks if character ASCII decimal value divided by $2^i$ is even or, odd and based on that prints a slash.

Using these relations the pattern generator can be created.

##### Tracing the output:

It is not possible for me to show the whole string since it will be very large. I will show with String being, $c[M] = bc"$.

When, $i = 1 \ and \ j = 1$ the call to $b(i,c)$ begins with parameter $b(i-1, c[j - 1])$ which is,

$b(1-1, c[1-1]) = b(0,c[0]) = b(0, 'b')$

It loops M (strings) times for each row. Which in this case is 2 times,

$b(1-1, c[2-1]) = b(0, 'c')$

In the b(i,c) function it checks if, character divided by 2^i is even or odd and prints slashes based on that.

for $b(0,'b')$ it is calculated, $(98 / 2^0) % 2$ which is 0 so prints forward slash ‘/’.
for $b(0,'c')$ it is calculated, $(99 / 2^0)% 2$ which is 1 so prints backslash ‘\’.

The $b(i,c)$ is called M times for each row and 8 times for each column and a slash is printed based on that. The rest two times slashes are printed from the condition of $H_{i,j}$ function.

From this relation, setting 0 for forward slashed and 1 for backward slashed the column wise string looks like its in binary format. Where the top row is Least significant bit (LSB) and bottom row is Most significant bit (MSB). In case of ‘b’ character only first column shown from the above example string,

 row sign binary value 0 / 0 0 1 \ 1 2 2 / 0 0 3 / 0 0 4 / 0 0 5 \ 1 32 6 \ 1 64 7 / 0 0

Their sum is = 2 + 32 + 64 = 98 or, converting the binary to decimal gives a value of 98 which is the ASCII decimal value of ‘b’. Similarly, more characters are calculated if there are more columns.

##### Shortcut Technique:

Basically first, last row and column are useless. A character is decoded based on each column. A forward slash means 0 and a backslash mean 1. Just apply bit wise shift for each row in a column and add the value when backslash is found. From that value print is equivalent ASCII character.

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:

2
///////////
/\/\/\/\/\/
//\\//\\///
////\\\\///
////////\\/
///////////
/\\\\\\\\\/
/\\\\\\\\\/
///////////
///////////

///////////////////////////////////////
//\///\/\\/\//\\/\//\/\\/\/\/\\/\/\//\/
///////\////\/\/\//////\//\////\/\/////
/\//\\\\///\\//\\/\\//\//\\//\///\/\\//
/\//\\//\///\////\\\//////\//\////\\\//
//////\\//////\/\//////\/\/////\/\/////
///\//////\//\///////\//\///\//////////
/\\/\\\\\\/\\/\\\\\\\/\\/\\\/\\\\\\\\\/
///////////////////////////////////////
///////////////////////////////////////


Output:

abcdefghi
LA LLUVIA EN SEVILLA ES UNA MARAVILLA


### Critical Input Generator:

Warning!!!
This is not the solution just input generator for the problem. The Solution code is below this code.

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 10851 - 2D Hieroglyphs Decoder Pattern / Input Generator
*/

#include<stdio.h>
#include<string.h>
#include<math.h>

//static char c[] = "bc";
//static char c[] = "abcdefghi";
static char c[] = "LA LLUVIA EN SEVILLA ES UNA MARAVILLA";

void b(int i, char ch){
// May be do a bitwise shift since power of 2
if( (ch / (long long) pow(2, i) ) % 2 == 0 )
printf("/");
else
printf("\\");
}

void H(int row, int M){
// String length is M and column is M + 2 so from 0 to M - 1
M = M + 2;

for(int i = 0; i < row; ++i ){

// This can be moved outside loop with little adjustment
if(i == 0 || i == row - 1){
for(int j = 0; j < M; ++j)
printf("/");
}

else{
for(int j = 0; j < M; ++j){
// Since M = M + 2 so j is j == (M - 1) = (M + 2 - 1) = (M + 1)
if(j == 0 || j == M - 1)
printf("/");
else
b(i - 1, c[j - 1]);
}
}

printf("\n");
}

}

int main(){

H(10, strlen(c) );

return 0;
}


### Solution Code:

/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 10851 - 2D Hieroglyphs Decoder
* Technique: Binary to Decimal, 2D row wise calculation.
*/

#include<stdio.h>
#include<string.h>

static char c[10][80];

int main(){

int n, i;

scanf("%d", &n);
getchar();

while( n-- ){

/**
* Reset each of the strings ignoring first and last row.
*/
for(i = 1; i < 9; ++i)
memset(c[i], 0, sizeof c[i]);

/**
* Reuse i for taking string inputs.
*/
i = 0;

/**
* Take input of 10 rows.
* Another logic is to discard first and last line when taking input.
* But this method is easier to code.
*/
while(gets(c[i]) && strlen(c[i]))
++i;

/**
* Take count of the column.
* Since input is a rectangle so any column length will work.
*/
int cols = strlen(c[0]);

/**
* Ignore last column.
* Also last row.
*/
cols = cols - 1;
i = i - 1;

/**
* k represents columns and j represents rows.
* k starts from 1 ignoring first column.
*/
for(int k = 1; k < cols; ++k){

// Reset for each column.
int sum = 0;
int shift = 1;

/**
* Ignoring the first and last character.
* i starts from 1 ignoring first row.
*/
for(int j = 1; j < i; ++j){

// Double slash means (for this case) in binary 1 and add that value.
// Otherwise its zero and no need to calculate in that case.
if( c[j][k] == '\\' )
sum = sum + shift;

// Bitwise shift left once for each column.
shift = shift << 1;
}

// Print character wise or use string then print outside this loop.
printf("%c", sum);
}

printf("\n");

}

return 0;
}


## UVA Problem 865 – Substitution Cypher Solution

UVA Problem 865 – Substitution Cypher Solution:

Solving Technique:

Similar problems to this problem, UVA Problem 10082 – WERTYU Solution and also UVA Problem 11278 – One Handed Typist Solution.

In this problem we are given two strings one of which is plain text and the next one is its substitution. In the plain text string there are characters that are to be mapped to its substitution characters from the substitution string.

Next comes several lines of text in which plain characters that match the required substitution characters should be replaced to its substitution character equivalent. The characters that don’t match the substitution requirement should stay the same.

The hardest part of this problem is newlines. There is a new line after number of cases, so make sure to discard that. Also an empty line marks the end of text inputs for a test case. Last thing is there is a new line between test cases, so for the last output there shouldn’t be an extra new line.

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:

1

abcdefghijklmnopqrstuvwxyz
zyxwvutsrqponmlkjihgfedcba
Shar's Birthday:
The birthday is October 6th, but the party will be Saturday,
October 5.  It's my 24th birthday and the first one in some
years for which I've been employed.  Plus, I have new clothes.
So I have cause to celebrate.  More importantly, though,
we've cleaned the house!  The address is 506-D Albert Street.
Extra enticement for CS geeks:  there are several systems in
the house, and the party is conveniently scheduled for 3 hours
after the second CSC programming contest ends (not to mention,
within easy walking distance)!


Output:

zyxwvutsrqponmlkjihgfedcba
abcdefghijklmnopqrstuvwxyz
Sszi'h Brigswzb:
Tsv yrigswzb rh Oxglyvi 6gs, yfg gsv kzigb droo yv Szgfiwzb,
Oxglyvi 5.  Ig'h nb 24gs yrigswzb zmw gsv urihg lmv rm hlnv
bvzih uli dsrxs I'ev yvvm vnkolbvw.  Pofh, I szev mvd xolgsvh.
Sl I szev xzfhv gl xvovyizgv.  Mliv rnkligzmgob, gslfts,
dv'ev xovzmvw gsv slfhv!  Tsv zwwivhh rh 506-D Aoyvig Sgivvg.
Ecgiz vmgrxvnvmg uli CS tvvph:  gsviv ziv hvevizo hbhgvnh rm
gsv slfhv, zmw gsv kzigb rh xlmevmrvmgob hxsvwfovw uli 3 slfih
zugvi gsv hvxlmw CSC kiltiznnrmt xlmgvhg vmwh (mlg gl nvmgrlm,
drgsrm vzhb dzoprmt wrhgzmxv)!


### Code:

/**
* Author:    Quickgrid ( Asif Ahmed )
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 865 - Substitution Cypher
* Technique: Character Mapping, Array Mapping
*/

#include<stdio.h>
#include<string.h>

#define N 256

static char text[N];
static char plaintext[N];
static char substitution[N];

static char newLayout[N];

static char output[N];

int main(){

int n;

/**
* Input an integer.
* discard new line character for enter.
*/
scanf("%d", &n);
getchar();
getchar();

for(int j = 0; j < n; ++j){

/**
* Print spaces between test cases.
*/
if(j)
printf("\n");

/**
* Input plain text and cipher text.
*/
gets(plaintext);
gets(substitution);

/**
* Map each character to its ASCII decimal value.
* In other words map the same character to itself.
*
* This is done because not all characters are changed by
* substitution cipher so rest of the characters map to itself.
*/
for(int i = 0; i < 256; ++i)
newLayout[i] = i;

/**
* Since plain text and cipher text will equal size any of them
* can be used to check termination condition.
*
* Inside the loop map plain text characters to its substitution.
*/
for(int i = 0; plaintext[i]; ++i)
newLayout[ plaintext[i] ] = substitution[i];

/**
* Print substitution string first and plain text as per requirement.
*/
puts(substitution);
puts(plaintext);

/**
* Now take input and scramble until a blank line is found.
*
* Here i have used string to output each line but character
* by character output will also work.
*/
while(gets(text) && strlen(text)){

memset(output, 0, sizeof output);

for( int i = 0; i < strlen( text ); ++i )
output[i] = newLayout[ text[i] ];

puts(output);

}

}

return 0;
}


## UVA Problem 11278 – One-Handed Typist Solution

UVA Problem 11278 – One-Handed Typist Solution:

Solving Technique:

Before starting this you can check out a similar problem UVA Problem 10082 – WERTYU Solution. That problem is very similar to this and also somewhat similar to a Caesar Cipher with right shift of 1.

The problem deals with two keyboard layouts. The author typed dovrak key layout keys in standard keyboard layout by mistake. So he was actually pressing standard keys and now his output ( input in this problem ) looks scrambled. The task is to convert all typed standard key inputs to equivalent dvorak keys.

There are a few ways to solve this problem. One ways is to painstakingly map each standard key to a dvorak key.

Another way is to map ASCII table characters from Decimal 32 to 126 as standard keys. This can be done with a loop and another array with equivalent dvorak keys. This method is easier that is eliminates one array but then creating the dvorak array becomes time consuming.

The third way which which i used here is create two arrays containing standard and dvorak keys. Then map each standard key to a dvorak key.

The code below is explained with comments.

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++.

Input:

Hg66t Mty6k!
Jhg 4ibl; pytmn 8tc 5i79urrr
t,gy jhg 6fxo kt.r

Output:

Hello World!
The quick brown fox jumps...
over the lazy dog.

### Code Output as Characters:

/*
* Author:     Quickgrid ( Asif Ahmed )
* Site:       https://quickgrid.wordpress.com
* Problem:    UVA 11278 - One Handed Typist
* Techniques: Array mapping, Character mapping
*/

#include<stdio.h>

#define N  128
#define IO 1001

/**
* Heart of the problem. Be careful with mapping, one typo in mapping and the verdict is wrong.
* Here standard contains all the characters in standard keyboard including capital and small.
* dvorak contains all the characters in dvorak keyboard including capital and small.
*/
static const char standard[N] = "1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./~!@#$%^&*()_+QWERTYUIOP{}|ASDFGHJKL:\"ZXCVBNM<>? "; static const char dvorak[N] = "123qjlmfp/[]456.orsuyb;=\\789aehtdck-0zx,inwvg'~!@#QJLMFP?{}$%^>ORSUYB:+|&*(AEHTDCK_)ZX<INWVG\" ";

/**
* This is the mapping array. It holds mappings of dvorak to standard keyboard.
*/
static char mappingKB[N];

static char input[IO];

int main(){

/**
* Although mapping "mappingKB[ standard[i] ] = dvorak[i]" seems wrong and
* mapping from "mappingKB[ dvorak[i] ] = standard[i]" seems correct.
*
* But its wrong remember the coach was typing dvorak in standard keyboard keys
* instead of dvorak key mappings. Since the input was in standard keyboard and we should convert it to dvorak otherwise it looks
* scrambled.
*
* So the keys of standard keyboard maps to dvorak keys.
*/
for(int i = 0; dvorak[i]; ++i)
mappingKB[ standard[i] ] = dvorak[i];

while(gets(input)){

/**
* Convert standard keys to dvorak using pre-mapped array
*/
for(int i = 0; input[i]; ++i)
printf("%c", mappingKB[ input[i] ] );

printf("\n");

}

return 0;
}


### Code Output as String:

/*
* Author:     Quickgrid ( Asif Ahmed )
* Site:       https://quickgrid.wordpress.com
* Problem:    UVA 11278 - One Handed Typist
* Techniques: Array mapping, Character mapping
*/

#include<stdio.h>
#include<string.h>

#define N  128
#define IO 1001

static const char standard[N] = "1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./~!@#$%^&*()_+QWERTYUIOP{}|ASDFGHJKL:\"ZXCVBNM<>? "; static const char dvorak[N] = "123qjlmfp/[]456.orsuyb;=\\789aehtdck-0zx,inwvg'~!@#QJLMFP?{}$%^>ORSUYB:+|&*(AEHTDCK_)ZX<INWVG\" ";

static char mappingKB[N];

static char input[IO];
static char output[IO];

int main(){

for(int i = 0; dvorak[i]; ++i)
mappingKB[ standard[i] ] = dvorak[i];

while(gets(input)){

// Reset memory otherwise character form previous input will be shown along with new
memset(output, 0, sizeof output);

for(int i = 0; input[i]; ++i)
output[i] = mappingKB[ input[i] ];

puts(output);

}

return 0;
}