## UVA Problem 147 – Dollars Solution

UVA Problem 147 – Dollars Solution:

Solving Technique:

This problem is very very very very similar to uva 674 ( Coin Change ) and uva 357 ( Let me count the ways ). These problems can be used as hint or template for this problem. So if you want to solve on your own don’t look down.

##### In this problem a few key points are,
1. The amount doesn’t exceed \$300.00
2. Exit / terminate program for the input of 0.00
3. Amount can be / is a floating point number
4. There are different values that can be used make up the decimal and the fractional portion
5. Output should be justified with width 6 before printing input amount and width 17 afterwards then the number of ways the amount is made up of.

#### Solution Technique:

Instead of calculating the decimal and the fractional portion separately we can use one method to calculate the count. Since a Dollar can be made up of coins that is, \$1 = 100 cents. So we can just calculate how many ways the coins can be made and that will be the answer.

###### For example,
• \$4.70      =      470 cents
• \$2.00      =      200 cents
• \$6.75      =      675 cents
• \$300.00  =  30000 cents

So we can put all the ways the coins can be divided to an array. Then use that calculate the count. Now whenever we can divide the amount with a specific coin we increase the count. We need calculate for all the specific coins.

Here I have given two codes, they are essentially the same. Only difference is in the second code instead of using an array to calculate the count, I have split the loop to show the calculations.

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. Compile with C++ to be safe from compile errors although some codes do work with C compiler.

Input:

0.20
2.00
4.90
6.70
8.45
0.00

Output:

0.20                4
2.00              293
4.90             5698
6.70            19187
8.45            49007

## Code:

/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 147 - Dollars
*/

#include<stdio.h>

#define N 30002

static long long c[N];
static const unsigned coins[] = {5, 10, 20, 50, 100, 200, 500, 1000, 2000, 5000, 10000};

int main(){
unsigned i, j;
float n;

c[0] = 1;
for(i = 0; i < 11; ++i){
for(j = coins[i]; j < N; ++j)
c[j] += c[j - coins[i]];
}

while(scanf("%f", &n) == 1 && n){
// Rounding error fix
unsigned coin = (unsigned)((n + 0.001) * 100);

// 6 width justified including the input amount and 17 width afterwards including count
printf("%6.2f%17lld\n", n, c[coin]);
}
return 0;
}

## Code (Loop Split):

/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 147 - Dollars ( Loop Split )
*/

#include<stdio.h>

#define N 30002

static long long c[N];

int main(){
unsigned i, j;
float n;

c[0] = 1;

/*
* Loop Split
*/

for(j = 5; j < N; ++j)
c[j] += c[j - 5];

for(j = 10; j < N; ++j)
c[j] += c[j - 10];

for(j = 20; j < N; ++j)
c[j] += c[j - 20];

for(j = 50; j < N; ++j)
c[j] += c[j - 50];

for(j = 100; j < N; ++j)
c[j] += c[j - 100];

for(j = 200; j < N; ++j)
c[j] += c[j - 200];

for(j = 500; j < N; ++j)
c[j] += c[j - 500];

for(j = 1000; j < N; ++j)
c[j] += c[j - 1000];

for(j = 2000; j < N; ++j)
c[j] += c[j - 2000];

for(j = 5000; j < N; ++j)
c[j] += c[j - 5000];

for(j = 10000; j < N; ++j)
c[j] += c[j - 10000];

while(scanf("%f", &n) == 1 && n){
// Rounding error fix
unsigned coin = (unsigned)((n + 0.001) * 100);

// 6 width justified including the input amount and 17 width afterwards including count
printf("%6.2f%17lld\n", n, c[coin]);
}
return 0;
}

## UVA Problem 10327 – Flip Sort Solution

UVA Problem 10327 – Flip Sort Solution:

Solving Technique:

Another sorting problem that requires us to “exchange two adjacent terms”. Use any stable sort to count the number of swaps. That is the output.

Here among three code the first one is a hybrid distribution between insertion sort and merge sort to count inversions / swaps. The next two codes are merge sort and bubble sort.

This merge sort also be made to work with selection sort. Please see Introduction to Algorithms book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein for more detail.

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.

Input:

3
1 2 3
3
2 3 1

Output:

Minimum exchange operations : 0
Minimum exchange operations : 2

### Hybrid Merge Sort and Insertion Sort Distribution:

/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 10327 Flip Sort
*/

#include<stdio.h>
#include<limits.h>

#define INSERTION_SORT_THERSHOLD 20

static int A[1024], c;

void Merge(int front, int mid, int rear){
int n1 = mid - front + 1;
int n2 = rear - mid;

int *L = new int[n1 + 1];
int *R = new int[n2 + 1];

register unsigned i = 0;
for(; i < n1; ++i)
L[i] = A[front + i];

register unsigned j = 0;
for(; j < n2; ++j)
R[j] = A[mid + 1 + j];

L[n1] = INT_MAX;
R[n2] = INT_MAX;
i = j = 0;

/**
* Might work without swaps by just incrementing index counters
*/
register unsigned k = front;
for(; k <= rear; ++k){
if(L[i] <= R[j]){
A[k] = L[i++];
c += j;
}
else
A[k] = R[j++];
}
}

void insertionSort(int front, int rear) {
register int i, j;
int key;

for (i = front + 1; i <= rear; ++i) {
key = A[i];
j = i - 1;
while (j >= front && A[j] > key) {
A[j + 1] = A[j];
++c;
--j;
}
A[j + 1] = key;
}
}

/**
* Hybrid distribution between insertion sort and merge sort
* Performs slower than regular merge sort for this small input range
* Such distribution also works with selection sort
* Please refer to book introduction to algorithm for more
*/
void HybridMergesort(int front, int rear){
if(rear - front < INSERTION_SORT_THERSHOLD)
insertionSort(front, rear);
if(front < rear){
int mid = (rear + front) >> 1;
HybridMergesort(front, mid);
HybridMergesort(mid + 1, rear);
Merge(front, mid, rear);
}
}

int main(){
register unsigned int i, j, n;
unsigned key;
while(scanf("%u", &n) == 1){
for(i = c = 0; i < n; ++i)
scanf("%u", &A[i]);

HybridMergesort(0, n - 1);

printf("Minimum exchange operations : %u\n", c);
}
return 0;
}

### Merge Sort Inversion Count:

/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 10327 Flip Sort
*/

#include<stdio.h>
#include<limits.h>

static int A[1024], c;

void Merge(int front, int mid, int rear){
int n1 = mid-front+1;
int n2 = rear - mid;

int *L = new int[n1 + 1];
int *R = new int[n2 + 1];

register unsigned i = 0;
for(; i < n1; ++i)
L[i] = A[front + i];

register unsigned j = 0;
for(; j < n2; ++j)
R[j] = A[mid + 1 + j];

L[n1] = INT_MAX;
R[n2] = INT_MAX;
i = j = 0;

/**
* Might work without swaps by just incrementing index counters
*/
register unsigned k = front;
for(; k <= rear; ++k){
if(L[i] <= R[j]){
A[k] = L[i++];
c += j;
}
else
A[k] = R[j++];
}
}

void Mergesort(int front, int rear){
if(front < rear){
int mid = (rear + front) >> 1;
Mergesort(front, mid);
Mergesort(mid + 1, rear);
Merge(front, mid, rear);
}
}

int main(){
register unsigned int i, j, n;
unsigned key;
while(scanf("%u", &n) == 1){
for(i = c = 0; i < n; ++i)
scanf("%u", &A[i]);
Mergesort(0, n - 1);

printf("Minimum exchange operations : %u\n", c);
}
return 0;
}

### Bubble Sort Inversion Count:

/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 10327 Flip Sort
*/

#include<cstdio>
#include<iostream>

static unsigned a[1024];

int main(){
register unsigned int i, j, k, n;
while(scanf("%u", &n) == 1){
for(i = 0; i < n; ++i)
scanf("%u", &a[i]);

/**
* Bubble Sort
*/
for(k = j = 0; j < n; ++j){
for(i = 0; i < n - j - 1; ++i){
if(a[i] > a[i + 1]){
std::swap(a[i], a[i + 1]);
++k;
}
}
}

printf("Minimum exchange operations : %u\n", k);
}
return 0;
}

## UVA Problem 10079 – Pizza Cutting Solution

UVA Problem 10079 – Pizza Cutting Solution:

Solving Technique:

This is a very simple mathematics problem. It can be solved with Gauss‘es arithmetic series formula. Which is the sum 1 to nth number. The formula is,

#### n * ( n + 1 )/2

The problem just requires us find the number of maximum possible pieces for given the number of cuts. At first the pattern may not be visible. Use pencil and paper draw and verify outputs.

We need add 1 since doing 1 cut in pizza makes two pieces. So the arithmetic series formula is 1 less. Again if we make two cuts using arithmetic progression formula it is 1 less again. It happens for all inputs. So we can add 1 with result of this formula and that is the answer.

This problem can also be solved using simple loop and sum from 1 to n.

A corner case may be that the number may not fit int range.

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.

Input:

5
10
-100

Output:

16
56

Code:

/**
* @author  Quickgrid ( Asif Ahmed )
* Problem: UVA 10079 Pizza Cutting
*/

#include<stdio.h>

int main(){
long long n;
while(scanf("%lld", &n)){
if(n < 0)
return 0;

/**
* Arithmetic series 1 to n with extra 1
*/
printf("%lld\n", 1 + n * (n + 1) / 2);
}
return 0;
}

## UVA Problem 12289 ( One Two Three ) Solution

UVA Problem 12289 ( One Two Three ) Solution:

Solving Technique:

Very very easy problem. It requires us to only print 1 or 2 or 3 based on input.

There are only 3 types of string (one, two, three) input and among them only one character is changed for each input. Also Their length is always the same.

So the very basic idea that comes to mind is any input with length of five must be three ( since length doesn’t change ). Now if that is not true it can either be one or two.

Code Explanation:

I took a different approach for my code. Instead of including another header file and calling a function to get the string length, I simply checked if the third position in the array ( array starts from zero ) is not a NULL character. If there is no NULL character in that position then I simply outputted 3. Why? because the string three does not contain a NULL character in position 3.

Now above is not true then I check if the string is one or two. If i only check for sub-strings ( part of strings ) in one and find any two characters of ‘o’, ‘n’, ‘e’ then it is definitely one. Then print 1. Else simply print 2.

Input:

3
owe
too
theee

Output:

1
2
3

Code:

/**
* @author  Quickgrid ( Asif Ahmed )
*/

#include<stdio.h>

#define O 111
#define N 110
#define E 101

static char s[8];

int main(){
register unsigned n;
scanf("%u", &n);

while (n--){
scanf("%s", s);
if (s[3]){
printf("3\n");
}else{
unsigned s0 = s[0];
unsigned s1 = s[1];
unsigned s2 = s[2];
if ((s0 == O && s1 == N) || (s1 == N && s2 == E) || (s0 == O && s2 == E))
printf("1\n");
else
printf("2\n");
}
}
return 0;
}

## UVA Problem 11172 ( Relation Operator ) Solution

UVA Problem 11172 ( Relation Operator ) Solution:

Some off topic ideas:

Aimed at absolute beginners. This is an ad hoc problem and one of the problems easiest on uva online judge. I don’t know if it’s a good practice but first the first thing I do when given a problem I look at the inputs and outputs. After solving some problems how inputs for some problems are given we can see a pattern. Among them some problems run until they find EOF, some run until they find a given input and some take an input first for the number of input sets to come.

Solving Technique:

First if we just look at the input and output even without looking at the problem set we can see it takes the number 3 and followed by 3 lines of input. So from this we can identify the first line of input will take the number of inputs to come and the next line will iterate that many times.

Now if we look at the input style given for the problem it says the first input will less than 15 so we can safely use an integer to store this variable. For example we call this stored variable t.

Now the next lines of inputs will be given t times. And there are two integers per input. For example, we denote the first one a and the second one b. Both will be ranged within 1000000001 and this number safely fits in 4 byte integer so we can use an int data type to store this variables.

Finally, the problem’s statement asks us to find the comparison relations between two given inputs. Check to see if the

First one is greater than the second. In this case output ” > ” without the quotes.

or,

First one is less than the second. In this case output ” < ” without the quotes.

or,

First and second one is equal. In this case output ” = ” without the quotes

Important:  Be sure to add or print a new line after each output. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.

Code Explanation:

Just like other problems there are many better ways and faster to solve this. Here I scan the first line of input. Now I use a while loop. In the condition for while loop I used i – – this basically subtracts 1 from i for each completed loop. This way after some loops value of i will be. So the condition of while loop will be while(0) and it means false and the loop will exit.

Now for each loop I input two numbers. Next thing I use ternary operator to compare and put this as the output parameter of print. So the value that will be true according to conditions will get printed.

Input:

3
10 20
20 10
10 10

Output:

<
>
=

### C Code:

/*
* Author: Quickgrid ( Asif Ahmed )
* Site: https://quickgrid.wordpress.com
*/

#include<stdio.h>

int main(){
register unsigned i;
unsigned a, b;

scanf("%u", &i);
while (i--){
scanf("%u%u", &a, &b);
printf("%c\n", a > b ? '>' : a < b ? '<' : '=');
}

return 0;
}

### In C++:

/*
* Author: Quickgrid ( Asif Ahmed )
* Site: https://quickgrid.wordpress.com
*/

#include<iostream>

int main(){
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);

register unsigned i;
unsigned a,b;

std::cin >> i;
while(i--){
std::cin >> a >> b;
std::cout << (a > b ? '>' : a < b ? '<' : '=') << "\n";
}

return 0;
}

## UVA Problem 12468 ( Zapping ) Solution

UVA Problem 12468 ( Zapping ) Solution:

Solving Technique:

Another easy problem. The problem mainly deals with changing channel in tv using only up and down button. So there are only 2 directions. We are to find the least key press from given channel (Input 1) to Channel (Input 2) in any direction up or down. The output should be the least number of key pressed to move from given channel to another given channel.

The program will keep running until it find two -1. It will mark the end of input. There will be two input per line. Both inputs will be a channel ranging within 0 to and including 99 ( 0<= a,b <=99 ).First we can easily see from 0 to 99 there are 100 channels. So the most key press either using up or down button will be 50. It is always same for this range.

For example, If input is:

10 90

here if we press the up button on remote it will take 80 press to reach but if we keep pressing down key it will only take 20 press. Why? because it is mentioned in the problem that we can reach to 0 from channel 99 also the inverse is true we can reach 99 from channel 0. So our answer should be 20 because the problems wants the least number of key presses.

Important:

The most key press in any direction is 50 for range 0 to 99 ( try to think ).

Solving Technique:

We can easily find the distance ( or number of key press ) between two channels by subtracting one from another. Here I have used abs() absolute function so even if subtract the larger number from the smaller I’ll always get a positive value. Now i check if the subtraction result is smaller than 50 then it is the least number of key press in any direction. But if its greater than 50 then we are going the wrong direction. We subtract the result from the total number of channels ( here total 100 ) to find the least number of key presses in the opposite direction.

Input:

3 9
0 99
12 27
-1 -1

Output:

6
1
15

Code:

/*
* Author: Quickgrid ( Asif Ahmed )
* Site: https://quickgrid.wordpress.com
*/

#include<stdio.h>
#include<stdlib.h>

int main(){
int a, b, i, s;
while (scanf("%d%d", &a, &b) == 2 && (a != -1 && b != -1)){
s = abs(a - b);

if(s > 50)
s = 100 - s;

printf("%d\n", s);
}
return 0;
}

## Stack Queue Array Hybrid (Data Structure)

Description: Here i combined my knowledge of stack and queue array into a single code. Firstly we are working with Queue. We can enqueue items in a queue. But when we dequeue the dequeued item is pushed to the stack ( We push the dequeued item in stack ) . The items pushed in stack are in the same order as they were in queue  since Queue is FIFO ( First In First Out ) data structure. We can also pop items from that stack. Now when we pop them they are enqueued back to the queue. The interesting thing is when they are popped they fill up the queue in reverse order since Stack is LIFO ( Last In First Out ) data structure.

Stack Functions: pop(), push(), displayStack(), searchStack()

Queue Functions: enqueue(), dequeue(), displayQueue(), searchQueue()

Code:

/**
* @author  Quickgrid ( Asif Ahmed )
*/

#include<stdio.h>

#define size 100

int q[size+1], f = 0, r = 0;
int s[size], top = -1;

{
printf("1.Enqueue\n");
printf("2.Dequeue\n");
printf("3.Show Queue\n");
printf("4.Search Queue\n");
printf("5.Show Stack\n");
printf("6.Search Stack\n");
printf("7.Pop stack\n");
printf("8.Exit\n");
}

void push(int item)
{
if(top+1 >= size)
{
printf("stack Overflow.\n");
return;
}
s[++top] = item;
}

void displayQueue()
{
int i = (f+1) % (size+1);
for(int j=i; j!=r+1; ++j)
{
if(j>size)
{
j = 0;
}
if(f != r)
{
printf("%d ", q[j]);
}
}
printf("\n");
}

void enqueue(int num)
{
int s = (r+1) % (size+1);
if(s == f)
{
printf("Queue Full.\n");
return;
}
q[s] = num;
r = s;
}

void dequeue()
{
if(f == r)
{
printf("Queue empty.\n");
return;
}
f = (f+1) % (size+1);
printf("%d\n", q[f]);
push(q[f]);
q[f] = 0;
}

void searchQueue(int item)
{
int i = (f+1) % (size+1);
for(int j=i; j!=r+1; ++j)
{
if(j > size)
{
j = 0;
}
if(f!=r)
{
if(q[j] == item)
{
printf("%d found in queue\n", item);
}
}
}
}

void searchStack(int item)
{
for(int i=0; i<=top; ++i)
{
if(s[i] == item)
{
printf("%d found at index: %d\n", item, i);
}
}
}

void displayStack()
{
for(int i=0; i<=top; ++i)
{
printf("%d ", s[i]);
}
printf("\n");
}

void pop()
{
if(top == -1)
{
printf("Stack Underflow.\n");
return;
}
printf("%d\n", s[top]);
enqueue(s[top]);
s[top--] = 0;
}

int main()
{
int choice, exitcode = 1, item;

do
{
printf("Enter choice:\n");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter item to enqueue:\n");
scanf("%d", &item);
enqueue(item);
printf("Stack: ");
displayStack();
printf("Queue: ");
displayQueue();
break;
case 2:
dequeue();
printf("Stack: ");
displayStack();
printf("Queue: ");
displayQueue();
break;
case 3:
displayQueue();
break;
case 4:
printf("Enter item to search:\n");
scanf("%d", &item);
searchQueue(item);
printf("Stack: ");
displayStack();
printf("Queue: ");
displayQueue();
break;
case 5:
displayStack();
break;
case 6:
printf("Enter item to search:\n");
scanf("%d", &item);
searchStack(item);
printf("Stack: ");
displayStack();
printf("Queue: ");
displayQueue();
break;
case 7:
pop();
printf("Stack: ");
displayStack();
printf("Queue: ");
displayQueue();
break;
case 8:
exitcode = 0;
break;
}
}
while(exitcode == 1);

return 0;
}

## UVA Problem 458 (The Decoder) Solution

UVA Problem 458 (The  Decoder) Solution:

Solving Technique:

Run time 15 ms ( 0.015 s ), Rank 377

This problem is really easy. The description is quite straight forward. The codes are scrambled based on simple arithmetic manipulation in ASCII value. From comparing input and output we can find the value of how much we need to shift ( add or subtract ) the ASCII value to match the output. In this problem if we subtract all character of given sentence by 7 then we get the correct output. Here I have first modified all the character of the string with 7 less than given character ASCII value.

Here I have modified the string inline in the for loop increment portion. It is rather short.

Important: No extra space or blank lines. Also one can modify and keep printing characters one by one. But that process is really slow.

Input:

1JKJ'pz'{ol'{yhklthyr'vm'{ol'Jvu{yvs'Kh{h'Jvywvyh{pvu5
1PIT'pz'h'{yhklthyr'vm'{ol'Pu{lyuh{pvuhs'I|zpulzz'Thjopul'Jvywvyh{pvu5
1KLJ'pz'{ol'{yhklthyr'vm'{ol'Kpnp{hs'Lx|pwtlu{'Jvywvyh{pvu5

Output:

*CDC is the trademark of the Control Data Corporation.
*DEC is the trademark of the Digital Equipment Corporation.

### Code:

/*
* @author Quickgrid ( Asif Ahmed )
* Problem: UVA 458 ( The Decoder )
*/

#include<stdio.h>

static char t[1024];

int main(){
register unsigned i;
while(gets(t)){
for(i = 0; t[i]; t[i] -= 7, ++i);
puts(t);
}
return 0;
}

## UVA Problem 272 (TEX QUOTES) Solution

UVA Problem 272 (TEX QUOTES) Solution:

Solving Technique:

This problem is relatively easy. In this problem we are asked to replace a pair of quotes. The first quote replaced with two ( ` ) character and next quote replaced with two ( ‘ ) character. Besides testing with given inputs we should also test with other inputs such as inputs given below before submission.

We can also solve this problem by printing characters one by one when they are found. But that process is really slow. We should consider first creating a string for the things we want to print then print them altogether using only one printf.

Also consider making loop counter variables register. This doesn’t guarantee that variables will be stored on register but if they are then our program runs a lot faster.

Another thing is we need some kind of ON OFF switch, or Flip Flop to check when we get Grave Caret ( ` ) or when we get a single quote ( ). Here in my code the variable ( c ) is doing that job.

' 39     /* Single Quote */
` 96     /* Grave Caret */
" 34     /* Double Quote */

Important: The quotes should be considered for the whole input not line by line.

Critical Input:

""
"""
""""

Critical Output:

``''
``''``
''``''``

Code:

#include<stdio.h>

static char t[256];

int main(){
register unsigned i, k, c = 0;

while(gets(t)){
char inp[256] = {'\0'};

for (i = k = 0; t[i]; ++i){
/*
* ASCII decimal value of " (Double Quotes) is 34
*/
if (t[i] == 34 && !c){
/*
* ASCII decimal value of ` (Grave Caret) is 96
*/
inp[k] = inp[k+1] = 96;
/*
*/
k += 2;
/*
* Flag or ON OFF
*/
c = 1;
}else if(c && t[i] == 34){
/*
* ASCII decimal value of ' (Single Quote) is 39
*/
inp[k] = inp[k+1] = 39;
k += 2;
c = 0;
}else{
/*
* If neither single or Double Quote found
*/
inp[k] = t[i];
++k;
}
}
printf("%s\n", inp);
}
return 0;
}