UVA Problem 12708 – GCD The Largest Solution

UVA Problem 12708 – GCD The Largest Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

This problem can be solved just by looking at the output. But we must understand the problem.

For this problem we are given an input N and expected find GCD of all pairs of numbers between 1 to N. If we look at the given table we can see that we can’t understand the table :).

The table shows pairs of numbers between 1 to N. The First COLUMN represents N ( the input ) and the First ROW represents number from 1 to N-1. Why? because the first column already represents N. We can’t make pair of the same number.

This way if we draw the table for bigger number we can see an important pattern that is the biggest GCD of 1 to N is FLOOR of N/2 ( N divided by two ).

One more thing keep an eye on the range 2 <= N <= 10^18. I didn’t look at it ( used unsigned int ) and ate a WA. I hope you know the data type to handle this range.

Lets get coding :).

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.


Input:

6
0
1
2
3
4
5

Output:

0
0
1
1
2
2

Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: 12708 - GCD The Largest
 */
#include<stdio.h>
int main(){
	unsigned long long n,m;
	scanf("%llu", &n);
	while(n--){
        scanf("%llu", &m);
        printf("%llu\n", m>>1);
	}
	return 0;
}

Another One(Faster):

using c++,

#include<iostream>
int main(){
    std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	register unsigned int n;
	unsigned long ago;
	std::cin >> n;
	while(n--){
        std::cin >> ago;
        std::cout << (ago>>1) << "\n";
	}
	return 0;
}
Advertisements

UVA Problem 499 – What’s The Frequency, Kenneth Solution

UVA Problem 499 – What’s The Frequency, Kenneth Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

This problem is quite easy. Just avoid the gibberish on top and read the Input Output section.

At first glance looking at the input and output doesn’t make much sense. But if we read carefully or take a look at the instructions carefully we see they have print the frequency for upper and lower case letter.

Your mission should you choose to accept it is regardless of a letter being uppercase or lowercase find the maximum frequency ( occurrence ) of a letter. Then if multiple letters have the same maximum frequency print the uppercase letters with max frequency first. Next print the lowercase letters with max frequency. Now separated by a space print the maximum frequency ( occurrence ) count.

Avoid any characters other than uppercase and lowercase letters. We only work with uppercase and lowercase letters for this problem. 

Happy coding 🙂

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.


Input:

When riding your bicycle backwards down a one-way street, if the
wheel falls of a canoe, how many ball bearings does it take to fill
up a water buffalo?
Hello Howard.

Output:

e 6
al 7
a 3
Hlo 2

Code:

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: uva 499 ( What's The Frequency, Kenneth )
 */

#include<stdio.h>

static char s[256];

int main(){
    register unsigned i;
    while(gets(s)){
        /*
         * Declare array for counting upper and lower case letters
         */
        unsigned upcase[32] = {0}, lowcase[32] = {0};

        for (i = 0; s[i]; ++i){
            /*
             * Check if upper case letter as the input may contain other characters
             */
            if (s[i] >= 'A' && s[i] <= 'Z')
                /*
                 * Subtracting a character ASCII ( upper and lower case ) from its base ASCII will give us an index from 0 to 26
                 */
                ++upcase[s[i] - 'A'];
            else if (s[i] >= 'a' && s[i] <= 'z')
                ++lowcase[s[i] - 'a'];
        }

        /*
         * Set the first index as max then compare against all array to find maximum occurrence of a letter
         */
        unsigned max = upcase[0];

        for (i = 0; i < 26; ++i){
            if (upcase[i] > max)
                max = upcase[i];
            if (lowcase[i] > max)
                max = lowcase[i];
        }

        for (i = 0; i < 26; ++i){
            if (upcase[i] == max)
                 /*
                  * Print the uppercase letters first since it was specified in the problem
                  */
                printf("%c", 'A'+i);
        }
        for (i = 0; i < 26; ++i){
            if (lowcase[i] == max)
                /*
                 * Now print the uppercase letters
                 */
                printf("%c", 'a'+i);
        }

        /*
         * Now print their frequency which is the max frequency
         */
        printf(" %u\n", max);
    }
    return 0;
}