2015年7月27日 星期一

[C][瘋狂程設][CPE考題20140527] 14C2.UVA10190 : Divide, But Not Quite Conquer! :

Problem C: Divide, But Not Quite Conquer!

Your goal in this problem is to divide a certain integer n by another integer m until n = 1, obtaining a sequence of numbers. Lets call a[i] each number of this sequence, and let's say it has k numbers (i.e. you must do k-1 succesive divisions to reach n = 1). You can only have this sequence if the following restrictions are met:
a[1] = n, a[i] = a[i-1] div m, for all 1 < i <= k 
a[i] is divisible by m (that is, a[i] mod m = 0) for all 1 <= i < k 
a[1] > a[2] > a[3] ... > a[k] 
For instance, if n = 125 and m = 5, you have 125, 25, 5 and 1 (you did 3 divisions: 125/5, 25/5 and 5/5). So, k = 4, a[1] = 125, a[2] = 25, a[3] = 5 and a[4] = 1. If n = 30 and m = 3, you have 30, 10, 3 and 1. But a[2] = 10, and 10 mod 3 = 1, so there is no sequence because it violates restriction 2. When the sequence doesn't exist we think it's not fun and, thus, very boring!

input

The input will consist on an arbitrary number of lines. Each line will consist of two non-negative integers n,m which are both less than 2000000000. You must read until you reach the end of file.
125 5
30 3
80 2
81 3

output

For each pair n,m you must print the correpondent sequence a (as defined above) in a single line, with each adjacent numbers of the sequence separated by a single space. In the case the sequence doesn't exist because it violates some restriction, just print the phrase "Boring!" in a single line (without the quotes).
125 25 5 1
Boring!
Boring!
81 27 9 3 1

notes:


1.利用題目給定輸入的最大值"2000000000",設定array的大小

The input will consist on an arbitrary number of lines. 
Each line will consist of two non-negative integers n,m which are both less than 2000000000.

#define MAX 2000000000>>20


2.計算divide的答案。必須要排除除數為0的狀態,所以加上一個bool值"pass",協助判斷是否具有商數array

 while(scanf("%ld %ld",÷nd,&divisor)!=EOF){
   
  int number[MAX],i=1,pass=0;
  number[i]=dividend;
  
  //calculate the array
  while(number[i]>1&&divisor>1){
   i++;
   pass=1;
   number[i]=number[i-1]/divisor;
   if((number[i-1]%divisor)!=0){
    pass=0;
    break;
   }
  }
                .
                .
                . 
        }
  

Code:

#include <stdio.h>

#define MAX 2000000000>>20

int main(void){

 long int dividend,divisor;
 
 while(scanf("%ld %ld",÷nd,&divisor)!=EOF){
   
  int number[MAX],i=1,pass=0;
  number[i]=dividend;
  
  //calculate the array
  while(number[i]>1&&divisor>1){
   i++;
   pass=1;
   number[i]=number[i-1]/divisor;
   if((number[i-1]%divisor)!=0){
    pass=0;
    break;
   }
  }
  
  //show the result
  if(pass==1)
   for(int j=1;j≤i;j++)
    (number[j]==1)?printf("%d\n",number[j]):printf("%d ",number[j]);
  else
   printf("Boring!\n");
  
 }
 return 0;
}

2 則留言: