UVA Problem 12015 – Google is Feeling Lucky Solution

UVA Problem 12015 – Google is Feeling Lucky Solution:


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

Solving Technique:

This is a sorting problem. In this problem we need to find biggest relevance number ( the second input / parameter). Then print the strings associated with that number. Multiple numbers can have equal relevance in which case print all the matching strings.

Ideas:

This can be solved efficiently by sorting inputs and based on that only print the strings / web addresses with biggest relevance number. Then if a lower relevance number is found stop processing. Since it was sorted ( ascending – start from last index, descending – start from index 0 )  if any lower value is found, further processing won’t yield any large relevance value.

Another method is using priority queue and store elements in key value pair. Then pop the biggest values and print their string.

Here my implementation is simple get the max value. Then brute force search all inputs for that value. If any value match the biggest relevance value print the 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++.


Input:

2
www.youtube.com 1
www.google.com 2
www.google.com.hk 3
www.alibaba.com 10
www.taobao.com 5
www.bad.com 10
www.good.com 7
www.fudan.edu.cn 8
www.university.edu.cn 9
acm.university.edu.cn 10
www.youtube.com 1
www.google.com 2
www.google.com.hk 3
www.alibaba.com 11
www.taobao.com 5
www.bad.com 10
www.good.com 7
www.fudan.edu.cn 8
acm.university.edu.cn 9
acm.university.edu.cn 10

 


Output:

Case #1:
www.alibaba.com
www.bad.com
acm.university.edu.cn
Case #2:
www.alibaba.com

Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 12015 Google is feeling lucky
 */

#include<stdio.h>

static char s[10][100];
static unsigned r[10];

static unsigned c, n, max, i;

int main(){

    scanf("%u", &n);

    while(n--){
        scanf("%s %u", &s[0], &r[0]);
        max = r[0];

        for(i = 1; i < 10; ++i){
            scanf("%s %u", &s[i], &r[i]);
            if(r[i] > max)
                max = r[i];
        }

        printf("Case #%u:\n", ++c);
        for(i = 0; i < 10; ++i){
            if(r[i] == max)
                printf("%s\n", s[i]);
        }
    }
    return 0;
}
Advertisements

UVA Problem 12149 – Feynman Solution

UVA Problem 12149 – Feynman Solution:


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

Solving Technique:

The problem asks given a number n how many squares are there in n by n grid. The relation can be found out by drawing n*n sqares and counting the squares. Since it will be very hard to draw and count more than 4 by 4 grid. We can try 1 by 1, 2 by 2, 3 by 3, 4 by 4 grid and count the number of squares. From there we can try to guess an equation.

For,
1*1 grid =   1 Square = 1
2*2 grid =   5 Square = 1 + 2^2
3*3 grid = 14 Square = 1 + 2^2 + 3^2
4*4 grid = 30 Square = 1 + 2^2 + 3^2 + 4^2

Here the series is,
1^2 + 2^2 + 3^2 + 4^2 + ….. n^2
Which is the sum of first n squares.

Instead of calculating with this formula a simpler formula exists.
1^2 + 2^2 + … + n^2 = n(n + 1)(2n + 1) / 6

The proof for this formula can be found here.

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:

2
1
8
0

Output:

5
1
204

Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 12149 Feynman
 * Type:    Mathematics ( 1^2 + 2^2 + .... + n^2 )
 */

#include<stdio.h>

int main(){
    static unsigned n;

    while(scanf("%u",&n) && n)
        printf("%u\n", n * (n + 1) * (2 * n + 1 ) / 6 );

    return 0;
}

UVA Problem 11727 – Cost Cutting Solution

UVA Problem 11727 – Cost Cutting Solution:


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

Solving Technique:

Very easy problem. We are given 3 numbers in each test case. Among those three numbers we need to print the median value.

Two codes given below one solved with simple if else branching, another one is solved using STL sort algorithm. Can be solved also using stl nth_element  but it is too much for this problem. Use of nth_element shown in UVA Problem 10041 Vito’s Family.

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 written in c and some in c++.


Input:

3
1000 2000 3000
3000 2500 1500
1500 1200 1800

 


Output:

Case 1: 2000
Case 2: 2500
Case 3: 1500

Code C:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 11727 - Cost Cutting
 */

#include<stdio.h>

int main(){
    static unsigned i, n, a, b, c;
    scanf("%u", &n);

    for(i = 1; i <= n; ++i){
        scanf("%u%u%u",&a,&b,&c);

        if(a > b && a > c)
            printf("Case %u: %u\n", i, b > c ? b : c);
        else if(b > c)
            printf("Case %u: %u\n", i, c > a ? c : a);
        else
            printf("Case %u: %u\n", i, a > b ? a : b);
    }
    return 0;
}

Code STL Sort:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 11727 - Cost Cutting
 */

#include<cstdio>
#include<algorithm>

static unsigned a[4];

int main(){
    static unsigned i, j, n;
    scanf("%u", &n);

    for(i = 1; i <= n; ++i){
        for(j = 0; j < 3; ++j)
            scanf("%u", &a[j]);

        std::sort(a, a + 3);
        printf("Case %u: %u\n", i, a[1]);
    }

    return 0;
}