UVA Problem 11636 – Hello World! Solution

UVA Problem 11636 – Hello World! Solution:


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

Solving Technique:

Here i have given Three solution one is Hybrid ( pre-calculated values with little calculations, Rank 1821 ) , another is with pre-caculated values stored in table ( see Memoization and Look up table ) ,last one is pure calculation. For this problem i have found out all answer combinations. So you can use your logic to get your code faster.

The problem requires us to find minimum number of copy commands to reach input lines.

For example, if there is 1 line and we copy whats on-screen 4 times we get 16 lines. How?

1 line copy paste 2 lines (since there was 1 line and we copied 1 more line)
2 line copy paste 4 lines (since there was 2 line and we copied 2 more line)
4 line copy paste 8 lines (since there was 4 line and we copied 4 more line)
8 line copy paste 16 lines (since there was 8 line and we copied 8 more line)

As we can what we copy is twice ( 2 times ) the amount of original.

Now we can use this knowledge to find the copy commands required. We can just loop until we find that our line number exceeds the given line. Now as many times as we looped is the copy command required.

Because we can copy 11 lines, 10 lines or 9 lines in 4 commands. We weren’t given any restriction on this. Just looping until our copy lines for the loop exceed the given line is enough.

Also Critical thing is input can be 0, 1 both for these the output is 0. For 1 the answer is 0 because. There is already a line so it takes 0 command to get 1 line.

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.


Critical Inputs:

21
99
0
1
1001
101
11
-1

Output:

Case 1: 5
Case 2: 7
Case 3: 0
Case 4: 0
Case 5: 10
Case 6: 7
Case 7: 4

Code Easier:

/**
 * @author Quickgrid ( Asif Ahmed )
 * @link https://quickgrid.wordpress.com
 */

#include<stdio.h>

int main(){
    int n;
    register unsigned c = 1;
    while(scanf("%d", &n) && n>-1){
        register unsigned i = 1, p = 0;
        while(i < n){
            /*
             * In the equation 2^p > n, for which value is greater than input, Here p is the answer
             */
            i <<= 1;
            ++p;
        }
        printf("Case %u: %u\n", c, p);
        ++c;
    }
    return 0;
}

Faster Solution ( Rank: 1821, Run time: 9 ms  ):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 */
#include<stdio.h>
int main(){
    int n;
    register unsigned int c = 1;
	while(scanf("%d", &n) && n>-1){
        if(n>1){
            if(n > 8192)
                printf("Case %u: 14\n", c);
            else if(n >= 4097)
                printf("Case %u: 13\n", c);
            else if(n >= 2049)
                printf("Case %u: 12\n", c);
            else if(n >= 1025)
                printf("Case %u: 11\n", c);
            else{
                register unsigned int i = 1, lines = 1;
                for(; i<=n; ++i){
                    lines <<= 1;
                    if(lines >= n){
                        break;
                    }
                }
                printf("Case %u: %u\n", c, i);
            }
        }else printf("Case %u: 0\n", c);
        ++c;
	}
	return 0;
}

Another Solution ( with Look Up Table ):

/*
 * @author Quickgrid ( Asif Ahmed )
 * @link   https://quickgrid.wordpress.com
 */

#include<stdio.h>
static unsigned arr[10010];

void precalculate(){
    register unsigned n = 10001;
    arr[0] = 0;
    arr[1] = 0;
    arr[2] = 1;
    arr[3] = 2;
    arr[4] = 2;
    arr[5] = 3;
    arr[6] = 3;
    arr[7] = 3;
    arr[8] = 3;

    /**
     * If you look carefully there is a nice pattern here
     * This code can be shorted with a nested loop
     * 2^N <= Loop <= 2^(N-1) + 1
     */
    for(; n >= 8193; --n)
        arr[n] = 14;
    for(; n >= 4097; --n)
        arr[n] = 13;
    for(; n >= 2049; --n)
        arr[n] = 12;
    for(; n >= 1025; --n)
        arr[n] = 11;
    for(; n >=  513; --n)
        arr[n] = 10;
    for(; n >=  257; --n)
        arr[n] = 9;
    for(; n >=  129; --n)
        arr[n] = 8;
    for(; n >=   65; --n)
        arr[n] = 7;
    for(; n >=   33; --n)
        arr[n] = 6;
    for(; n >=   17; --n)
        arr[n] = 5;
    for(; n >=    9; --n)
        arr[n] = 4;
}

int main(){
    precalculate();
    int n;
    register unsigned c = 1;

    while (scanf("%d", &n) && n > -1){
        printf("Case %u: %u\n", c, arr[n]);
        ++c;
    }

    return 0;
}

One thought on “UVA Problem 11636 – Hello World! Solution

  1. #include <bits/stdc++.h>

    using namespace std;

    int main()
    {
    int t, i = 0;
    while(scanf(“%d”, &t) != EOF && t >= 0){
    double re = (log10(t)) / (log10(2));
    re = ceil(re);
    printf(“Case %d: %0.0lf\n”, ++i, re);
    }
    return 0;
    }

    Like

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