Coding Exercise – Timus 1785. Lost in Localization – C++ solution – Online Judge

The problem is from Timus Online Judge

It is a simple and easy exercise, you should output correct word depending on the input integer. No much thing to mess around.

However, I have seen solutions like this:

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin>>n;
    if(n>=1 && n<=4)
        cout<<"few"<<endl;     
    if(n>=5 && n<=9)
        cout<<"several"<<endl;     
    if(n>=10 && n<=19)
        cout<<"pack"<<endl;     
    if(n>=20 && n<=49)
        cout<<"lots"<<endl;     
    if(n>=50 && n<=99)
        cout<<"horde"<<endl;     
    if(n>=100 && n<=249)
        cout<<"throng"<<endl;     
    if(n>=250 && n<=499)
        cout<<"swarm"<<endl;     
    if(n>=500 && n<=999)
        cout<<"zounds"<<endl;     
    if(n>=1000)
        cout<<"legion"<<endl;
    return 0;
}

This is not good.. Try the following comparison starting with the upper bound. In this case, only one condition check each time.

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    if (n >= 1000) {
        cout << "legion";     
    }      
    else if (n >= 500) {
        cout << "zounds";     
    }      
    else if (n >= 250) {
        cout << "swarm";     
    }     
    else if (n >= 100) {
        cout << "throng";     
    }     
    else if (n >= 50) {
        cout << "horde";     
    }     
    else if (n >= 20) {
        cout << "lots";     
    }     
    else if (n >= 10) {
        cout << "pack";     
    }      
    else if (n >= 5) {
        cout << "several";
    }
    else {
        cout << "few";
    }
    return 0;
}

Because of the distribution of the input, it is always better to check for most-likely inputs, in this case, there are 1001 legions, 499 zounds and so on… Therefore, checking the most branch first shortens the test time.

–EOF (The Ultimate Computing & Technology Blog) —