UVA Problem 488 – Triangle Wave Solution

UVA Problem 488 – Triangle Wave Solution:


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

Solving Technique:

This is one of the easiest problems but requires some thinking. But getting accepted in not enough we also need to optimize the code to improve timing, memory, ranking.

Here I have solved this problem in two ways. The first took 0.042 s ( 42 ms ) and ranked 254 at the time of writing. The second solution took 0.122 s ( 122 ms ). Both codes take a different approach. The first one is a little bit cheating. Since running the second code I have found out that amplitude input is never greater than 9. Why? because running the second code it outputs garbage for any amplitude greater than 9 and it got accepted.

I will explain the first code logic here. The second ( slower ) code is commented for easier understanding. Please refer below for the solutions.

Since I know amplitude is never greater than 9 so I created constant string array in C. Also possible in C++ by using

const std::string a[] = {"1", "22", .....}

Now just print the predefined string array amplitude times and print in reverse order amplitude minus one times. That’s it. Please note, you should not print a blank line after last wave form. It quite easy,

if(times || n){
    printf("\n");
}

This works because both times and n variables are decremented and for the last loop when they become 0, the if condition does not execute. So for last waveform there is no newline.

Time to write a better solution and get that 1st rank :).

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:

2

4
5

3
2

Output:

1
22
333
4444
333
22
1

1
22
333
4444
333
22
1

1
22
333
4444
333
22
1

1
22
333
4444
333
22
1

1
22
333
4444
333
22
1

1
22
333
22
1

1
22
333
22
1

Code ( Faster ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 488 ( Triangle Wave )
 */
#include<stdio.h>

/* For this problem amplitude does not exceed 9, so you can cheat <span class="wp-smiley wp-emoji wp-emoji-smile" title=":)">:)</span> */
const char *a[] = {"", "1", "22", "333", "4444", "55555", "666666", "7777777", "88888888", "999999999"};

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

    while(n--){
        unsigned amp, times;
        scanf("%u%u", &amp, &times);

        while(times--){
            for(i = 1; i < amp; ++i)
                /* Just print the predefined strings */
                printf("%s\n", a[i]);

            for(k = i; k; --k)
                printf("%s\n", a[k]);

            if(times || n)
                printf("\n");
        }
    }
    return 0;
}

Another Solution ( Slower ):

This code also solves the problem but relatively slower. It took 0.122 s for my run. Still have look to learn something new. Please refer to this code for a better explanation of C array of strings.

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 488 ( Triangle Wave )
 */

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

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

    while(n--){
        unsigned amp, times;
        scanf("%u%u", &amp, &times);

        while(times--){
            /* Allocate memory for string array, allocates memory for string count */
            char **a = new char*[amp + 1];

            for(i = 1; i <= amp; ++i){
                /* Allocate memory for the string */
                a[i] = new char[i + 1];
                /* Reset the array */
                memset(a[i], 0, sizeof a[i]);

                for(j = 0; j < i; ++j)
                    /* Populate the string with numbers */
                    a[i][j] = i + 48;

                /* Print the generated strings */
                printf("%s\n", a[i]);
            }

            for(k = amp - 1; k > 0; --k)
                /* Print the rest in reverse */
                printf("%s\n", a[k]);

            if(times || n)
                /* For the last loop do not print new line */
                printf("\n");
        }
    }
    return 0;
}

Another using C++:

This one is also accepted but slower. Here instead of printing i keep adding all things to one string and only print when program is terminated. Although this works and will work but it is not a very good idea.

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 * Problem: UVA 488 ( Triangle Wave )
 */
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const string a[] = {"", "1", "22", "333", "4444", "55555", "666666", "7777777", "88888888", "999999999"};

int main(){
    register unsigned n, i, j, k;
    string output, total = "";
    scanf("%u", &n);

    while(n--){
        unsigned amp, times;
        scanf("%u%u", &amp, &times);
        output = "";

        while(times--){
            for(i = 1; i < amp; ++i)
                output += a[i] + "\n";
            for(k = i; k; --k)
                output += a[k] + "\n";
            if(times || n)
                output += "\n";
        }
        total += output;
    }

    cout << total;
    return 0;
}

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s