UVa : 10190 (Divide, But Not Quite Conquer!)


Title : Divide, But Not Quite Conquer!

Link : http://uva.onlinejudge.org/external/101/10190.html

Tricky Lines :

  1. When the sequence doesn’t exist we think it’s not fun and, thus, very boring!
  2. Each line will consist of two non-negative integers n,m which are both less than 2000000000.

Analysis :

  1. n and m : two non-negative integer, (n, m) >= 0
    if ( n < 2 || m < 2 || m > n ) output Boring!
  2. Otherwise, simulate the process
    at any point if n % m != 0, output Boring!
    Else print the sequence

Runtime : 0.012s

Solution :

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <sstream>
#include <set>
#include <math.h>
#define N 1000000
using namespace std;

int main ()
{
    int n;
    int m;

    while ( scanf ("%d %d", &n, &m) != EOF ) {

        if ( n < 2 || m < 2 || m > n ) {
            printf ("Boring!\n");
            continue;
        }

        vector <int> output;
        bool boring = false;

        while ( n > 1 ) {
            if ( n % m == 0 ) output.push_back (n);
            else boring = true;
            n /= m;
        }
        output.push_back (1);

        if ( boring == true ) printf ("Boring!\n");
        else {
            bool space = false;
            for ( size_t i = 0; i < output.size (); i++ ) {
                if ( space ) printf (" "); space = true;
                printf ("%d", output [i]);
            }
            printf ("\n");
        }
    }

    return 0;
}

// @END_OF_SOURCE_CODE

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s