RUET: THE SOLUTION OF ACM

100. 3n+1 problem

2009-11-21T14:23:00.000-08:00

Background
Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.

The Problem
Consider the following algorithm:
 

		1. 		 input n



		2. 		 print n



		3. 		 if n = 1 then STOP



		4. 		 		 if n is odd then   



		5. 		 		 else   



		6. 		 GOTO 2
Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n < 1,000,000 (and, in fact, for many more numbers than this.)
Given an input n, it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.
For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.

The Input
The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.
You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.
You can assume that no operation overflows a 32-bit integer.

The Output
For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).

Sample Input
1 10

100 200

201 210

900 1000

Sample Output

1 10 20

100 200 125

201 210 89

900 1000 174

Discussion:
Presented by rizoan toufiq
1. J can less I; i.e j
2. I=j
The order of i and j in output must be the same as the input, even when j is smaller than i.

/*****Optimizations **************
To get the problem in good time you must create an array with size 1000000. Then using recursion with memoization try to not compute any value more than once. This will help you solve it in about 0.200 sec. */

Code: Brut force : RT: 0.700

DOWNLOAD Code :

Download to click

Optimal solution: RT: .064sec[recursion]

DOWNLOAD Code :

Download to click

10055 - Hashmat the Brave Warrior

2009-11-21T14:13:00.000-08:00

Hashmat is a brave warrior who with his group of young soldiers moves from one place to another to fight against his opponents. Before fighting he just calculates one thing, the difference between his soldier number and the opponent's soldier number. From this difference he decides whether to fight or not. Hashmat's soldier number is never greater than his opponent.

Input
The input contains two integer numbers in every line. These two numbers in each line denotes the number of soldiers in Hashmat's army and his opponent's army or vice versa. The input numbers are not greater than 2^32. Input is terminated by End of File.

Output
For each line of input, print the difference of number of soldiers between Hashmat's army and his opponent's army. Each output should be in seperate line.

Sample Input:
10 12
10 14
100 200

Sample Output:
2
4
100

JUST FUN!!!!!
TICS J use Unsigned int
CODE:-D:

#include
int main(){
unsigned long int a,b;
/*freopen("1.in","r",stdin);*/
  while(scanf("%lu %lu",&a,&b)==2){
    if(a>b)
                printf("%lu\n",(a-b));
        else
           printf("%lu\n",b-a);
}
return 0;
}

103 Stacking Boxes

2009-11-21T13:58:00.000-08:00

   Longest Increasing Subsequence
According to Arefin book
Input: Given a sequence
Output: The longest subsequence of the given sequence such that all values in this
longest subsequence is strictly increasing/decreasing.
O(N^2) DP solution for LIS problem (this code check for increasing values):

for i = 1 to total-1
for j = i+1 to total
    if height[j] > height[i] then
      if length[i] + 1 > length[j] then
        length[j] = length[i] + 1
        predecessor[j] = i

Example of LIS
height sequence: 1,6,2,3,5
length initially: [1,1,1,1,1] - because max length is at least 1 rite...
predecessor initially: [nil,nil,nil,nil,nil] - assume no predecessor so far

After first loop of j:
length: [1,2,2,2,2], because 6,2,3,5 are all > 1
predecessor: [nil,1,1,1,1]
After second loop of j: (No change)
length: [1,2,2,2,2], because 2,3,5 are all < 6
predecessor: [nil,1,1,1,1]
After third loop:
length: [1,2,2,3,3], because 3,5 are all > 2
predecessor: [nil,1,1,3,3]
After fourth loop:
length: [1,2,2,3,4], because 5 > 3
predecessor: [nil,1,1,3,4]

DOWNLOAD Code :

Download to click

According to Algorithmist
Algorithm:

function lis_length( a )
    n := a.length
    q := new Array(n)
    for k from 1 to n:
        max := 0;
        for j from 1 to k-1, if a[k] > a[j]:
            if q[j] > max, then set max = q[j].
        q[k] := max + 1;
    max := 0
    for i from 1 to n:
        if q[i] > max, then set max = q[i].
    return max;

DOWNLOAD C CODE:

DOWNLOAD CPP CODE :

Download to click

103 Stacking Boxes

Background
Some concepts in Mathematics and Computer Science are simple in one or two dimensions but become more complex when extended to arbitrary dimensions. Consider solving differential equations in several dimensions and analyzing the topology of an n-dimensional hypercube. The former is much more complicated than its one dimensional relative while the latter bears a remarkable resemblance to its ``lower-class'' cousin.

The Problem
Consider an n-dimensional ``box'' given by its dimensions. In two dimensions the box (2,3) might represent a box with length 2 units and width 3 units. In three dimensions the box (4,8,9) can represent a box (length, width, and height). In 6 dimensions it is, perhaps, unclear what the box (4,5,6,7,8,9) represents; but we can analyze properties of the box such as the sum of its dimensions.
In this problem you will analyze a property of a group of n-dimensional boxes. You are to determine the longest nesting string of boxes, that is a sequence of boxes such that each box nests in box ( .
A box D = ( ) nests in a box E = ( ) if there is some rearrangement of the such that when rearranged each dimension is less than the corresponding dimension in box E. This loosely corresponds to turning box D to see if it will fit in box E. However, since any rearrangement suffices, box D can be contorted, not just turned (see examples below).
For example, the box D = (2,6) nests in the box E = (7,3) since D can be rearranged as (6,2) so that each dimension is less than the corresponding dimension in E. The box D = (9,5,7,3) does NOT nest in the box E = (2,10,6,8) since no rearrangement of D results in a box that satisfies the nesting property, but F = (9,5,7,1) does nest in box E since F can be rearranged as (1,9,5,7) which nests in E.
Formally, we define nesting as follows: box D = ( ) nests in box E = ( ) if there is a permutation of such that ( ) ``fits'' in ( ) i.e., if for all .

The Input
The input consists of a series of box sequences. Each box sequence begins with a line consisting of the the number of boxes k in the sequence followed by the dimensionality of the boxes, n (on the same line.)
This line is followed by k lines, one line per box with the n measurements of each box on one line separated by one or more spaces. The line in the sequence ( ) gives the measurements for the box.
There may be several box sequences in the input file. Your program should process all of them and determine, for each sequence, which of the k boxes determine the longest nesting string and the length of that nesting string (the number of boxes in the string).
In this problem the maximum dimensionality is 10 and the minimum dimensionality is 1. The maximum number of boxes in a sequence is 30.

The Output
For each box sequence in the input file, output the length of the longest nesting string on one line followed on the next line by a list of the boxes that comprise this string in order. The ``smallest'' or ``innermost'' box of the nesting string should be listed first, the next box (if there is one) should be listed second, etc.
The boxes should be numbered according to the order in which they appeared in the input file (first box is box 1, etc.).
If there is more than one longest nesting string then any one of them can be output.

Sample Input

5 2

3 7

8 10

5 2

9 11

21 18

8 6

5 2 20 1 30 10

23 15 7 9 11 3

40 50 34 24 14 4

9 10 11 12 13 14

31 4 18 8 27 17

44 32 13 19 41 19

1 2 3 4 5 6

80 37 47 18 21 9

10 2

1 1

1 2

1 3

1 4

1 5

1 6

1 7

1 8

1 9

1 10

6 1

6

8

10

4

5

4

30 10

1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

1 2 3 4 5 6 7 8 9 10

11 12 13 14 15 16 17 18 19 20

21 22 23 24 25 26 27 28 29 30

31 32 33 34 35 36 37 38 39 40

41 42 43 44 45 46 47 48 49 50

200 201 202 203 204 205 206 207 208 209 

100 101 102 103 104 105 106 107 108 109 

300 301 302 303 304 305 306 307 308 309 

200 201 202 203 204 205 206 207 208 209 

100 101 102 103 104 105 106 107 108 109 

300 301 302 303 304 305 306 307 308 309 

400 401 402 403 404 405 406 407 408 409 

500 501 502 503 504 505 506 507 508 509 

411 412 413 414 415 416 417 418 419 420 

521 522 523 524 525 526 527 528 529 530

50 60 70 80 90 50 60 70 80 90

20 30 40 50 60 70 80 90 10 99

10 9 8 7 6 5 4 3 2 1

19 29 39 49 59 69 79 89 95 9

15 35 25 45 65 55 85 75 93 5

50 60 70 80 90 50 60 70 80 90

20 30 40 50 60 70 80 90 10 99

10 9 8 7 6 5 4 3 2 1

19 29 39 49 59 69 79 89 95 9

15 35 25 45 65 55 85 75 93 5

Sample Output

5

3 1 2 4 5 

4

7 2 5 6 

1

1 

5

4 5 1 2 3 

13

1 2 3 4 5 21 12 11 13 17 19 18 20

Discussion: Algorithm described by rizoan toufiq
First Sort dimensions for each box.

Then sort the individual box, corresponding sorting the position of that box.

Now apply the LIS[least Increasing Sequence]. In LIS, the parent box is save in parent[] array.

From the Maximum value of inside[] array we find last box which is include Large box sequence.

Then By applying Backtracing algorithm we find reverse large sequence in an arr[].

Reverse the array

Then we find the corresponding box number.

If we use 0 index , then print the box number adding 1 to show the output.

To read it, You will be in trouble…..
So try yourself.
Or download the code in Cpp & java both

More details: described by rizoan Toufiq

Input:
8 6
5 2 20 1 30 10
23 15 7 9 11 3
40 50 34 24 14 4
9 10 11 12 13 14
31 4 18 8 27 17
44 32 13 19 41 19
1 2 3 4 5 6
80 37 47 18 21 9
Step 1:
Sort each box Dimension :data[i][0…5] [i=0…7]
1 2 5 10 20 30 --àBox no -1
3 7 9 11 15 23 
4 14 24 34 40 50 
9 10 11 12 13 14 
4 8 17 18 27 31 
13 19 19 32 41 44 
1 2 3 4 5 6 
9 18 21 37 47 80  --àbox No 8
 
Step 2:
Sort each box:
Position--à box sorted dimension 
6-->1 2 3 4 5 6 
0-->1 2 5 10 20 30 
1-->3 7 9 11 15 23 
4-->4 8 17 18 27 31 
2-->4 14 24 34 40 50 
3-->9 10 11 12 13 14 
7-->9 18 21 37 47 80 
5-->13 19 19 32 41 44
Position[]={6,0,1,4,2,3,7,5}
Step3
Now LIS Algorithm:
Do Yourself…
Note: parent help us to determin when increase the value of inside [] element value….
Let you find
Inside[]= 1 1 2 3 3 2 4 4
Par[]= -1 -1 0 2 2 0 3 3

So max 4 which position 7 or 6
7-> parent of 7 is 3 -> parent of 3 is 2 -> parent of 2 is 0 -> parent of 0 is unknown -1 break
Reverse Sequence: 7->3->2->0
Sequence: 0->2->3->7
We now from position array: position[0]+1 ->position[2]+1->position[3]+1->position[7]+1
RESEULT: 7->2->5->6

Any Way: Is It easy? I don’t know
Rizoan toufiq

DOWNLOAD NETCODE :RUN TIME: 0.012 sec

Download to click

DOWNLOAD MY CODE : run time: .008

Download to click

DOWNLOAD Java CODE:

Download to click

440 Eeny Meeny Moo

2009-11-18T08:32:00.000-08:00

Surely you have made the experience that when too many people use the Internet simultaneously, the net becomes very, very slow.

To put an end to this problem, the University of Ulm has developed a contingency scheme for times of peak load to cut off net access for some cities of the country in a systematic, totally fair manner. Germany's cities were enumerated randomly from 1 to n. Freiburg was number 1, Ulm was number 2, Karlsruhe was number 3, and so on in a purely random order.

Then a number m would be picked at random, and Internet access would first be cut off in city 1 (clearly the fairest starting point) and then in every mth city after that, wrapping around to 1 after n, and ignoring cities already cut off. For example, if n=17 and m=5, net access would be cut off to the cities in the order [1,6,11,16,5,12,2,9,17,10,4,15,14,3,8,13,7]. The problem is that it is clearly fairest to cut off Ulm last (after all, this is where the best programmers come from), so for a given n, the random number m needs to be carefully chosen so that city 2 is the last city selected.

Your job is to write a program that will read in a number of cities n and then determine the smallest integer m that will ensure that Ulm can surf the net while the rest of the country is cut off.

Input Specification
The input file will contain one or more lines, each line containing one integer n with , representing the number of cities in the country.
Input is terminated by a value of zero (0) for n.

Output Specification
For each line of the input, print one line containing the integer m fulfilling the requirement specified above.

Sample Input
3

4

5

6

7

8

9

10

11

12

0
Sample Output
2

5

2

4

3

11

2

3

8

16

Description : presented by rizoan toufiq

ACM problem 151 & 440: (Solved by Josephus):Flavius Josephus was a famous historian of the first century. Legend has it that Josephus wouldn't have lived to become famous without his mathematical talents. During the Jewish-Roman war, he was among a band of 41 Jewish rebels trapped in cave by the Romans. Preferring suicide to capture, the rebels decided to form a circle and, proceeding around it, to kill every third remaining person until no one was left. But Josephus, along with an unindicted co-conspirator, wanted none of this suicide nonsense; so he quickly calculated where he and his friend stand in the vicious circle.
Algorithm:
       Given A Circular queue: 1,2,3,4,5,6,7,8,9,10,11,12,13,14
      If(total_ele>1){
§ pop();
§ element--;
§ front moves;
o    }
       i.e _,2,3,4,5,6,7,8,9,10,11,12,13,14
      if difference =2 ,then next two element push into the back.
       While(i!=diff) it pop()data from front and then push it back.ie, _,_,_,4,5,6,7,8,9,10,11,12,13,14,2,3. Now front is on 4 data and rear is on 3 data. Element decrease by 2(i.e 12). Now Follow above step until number element 1;
      7,8,9,10,11,12,13,14,2,3,5,6 [4 die]
      10,11,12,13,14,2,3,5,6,8,9 [7 die]
      13,14,2,3,5,6,8,9,11,12 [10 die]
       3,5,6,8,9,11,12,14,2 [13 die]
      8,9,11,12,14,2,5,6 [3 die]
      12,14,2,5,6,9,11 [8 die]
      5,6,9,11,14,2 [12 die]
      11,14,2,6,9 [5 die]
      6,9,14,2 [11 die]
      2,9,14 [6 die]
      9,14 [2 die]
      14 [9 die]

DOWNLOAD DOCUMENT FILE :

Download to click

151 power crisis

2009-11-18T08:27:00.000-08:00

During the power crisis in New Zealand this winter (caused by a shortage of rain and hence low levels in the hydro dams), a contingency scheme was developed to turn off the power to areas of the country in a systematic, totally fair, manner. The country was divided up into N regions (Auckland was region number 1, and Wellington number 13). A number, m, would be picked `at random', and the power would first be turned off in region 1 (clearly the fairest starting point) and then in every m'th region after that, wrapping around to 1 after N, and ignoring regions already turned off. For example, if N = 17 and m = 5, power would be turned off to the regions in the order:1,6,11,16,5,12,2,9,17,10,4,15,14,3,8,13,7.

The problem is that it is clearly fairest to turn off Wellington last (after all, that is where the Electricity headquarters are), so for a given N, the `random' number m needs to be carefully chosen so that region 13 is the last region selected.

Write a program that will read in the number of regions and then determine the smallest number m that will ensure that Wellington (region 13) can function while the rest of the country is blacked out.

Input and Output
Input will consist of a series of lines, each line containing the number of regions (N) with . The file will be terminated by a line consisting of a single 0.

Output will consist of a series of lines, one for each line of the input. Each line will consist of the number m according to the above scheme.

Sample input
17

0
Sample output
7

Description : presented by rizoan toufiq

ACM problem 151 & 440: (Solved by Josephus):Flavius Josephus was a famous historian of the first century. Legend has it that Josephus wouldn't have lived to become famous without his mathematical talents. During the Jewish-Roman war, he was among a band of 41 Jewish rebels trapped in cave by the Romans. Preferring suicide to capture, the rebels decided to form a circle and, proceeding around it, to kill every third remaining person until no one was left. But Josephus, along with an unindicted co-conspirator, wanted none of this suicide nonsense; so he quickly calculated where he and his friend stand in the vicious circle.
Algorithm:
       Given A Circular queue: 1,2,3,4,5,6,7,8,9,10,11,12,13,14
      If(total_ele>1){
§ pop();
§ element--;
§ front moves;
o    }
       i.e _,2,3,4,5,6,7,8,9,10,11,12,13,14
      if difference =2 ,then next two element push into the back.
       While(i!=diff) it pop()data from front and then push it back.ie, _,_,_,4,5,6,7,8,9,10,11,12,13,14,2,3. Now front is on 4 data and rear is on 3 data. Element decrease by 2(i.e 12). Now Follow above step until number element 1;
      7,8,9,10,11,12,13,14,2,3,5,6 [4 die]
      10,11,12,13,14,2,3,5,6,8,9 [7 die]
      13,14,2,3,5,6,8,9,11,12 [10 die]
       3,5,6,8,9,11,12,14,2 [13 die]
      8,9,11,12,14,2,5,6 [3 die]
      12,14,2,5,6,9,11 [8 die]
      5,6,9,11,14,2 [12 die]
      11,14,2,6,9 [5 die]
      6,9,14,2 [11 die]
      2,9,14 [6 die]
      9,14 [2 die]
      14 [9 die]

DOWNLOAD DOCUMENT FILE :

Download to click

136-ugly number

2009-11-18T07:48:00.001-08:00

Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
shows the first 11 ugly numbers. By convention, 1 is included.
Write a program to find and print the 1500'th ugly number.
Input and Output
There is no input to this program. Output should consist of a single line as shown below, with replaced by the number computed.
Sample output
The 1500'th ugly number is .

Main procedure:
      let p2=2,p3=3,p5=5
          we know ,firt ugly number =1 ;
so ,next ugly number = min(p2*1,p3*1,p5*1)=2
       note: 1 represent the first ugly number
next ugly number = min (p2*2,p3*1,p3*1)=3
        note: 2 is second U.G & 1 first U.G
next ugly number = min(p2*2,p3*2,p3*1)=min(4,6,5)=4
next ugly number = min(p2*3,p3*2,p3*1)=min(6,6,5)=5
        note: 3 is third U.G
***next ugly number =min(p2*3,p3*2,p5*2)=min(6,6,10)[control double 6 by taking next
          uglynumber & if necessary loop i decrease, i.e * 6 is not selected in ugly number]

next ugly number= min(p2*4,p3*2,p5*2)=min(8,6,10)=6
       note : 4 is fourth ug number
next ugly number= min(p2*4,p3*3,p5*2)=min(8,9,10)=8
next ugly number= min(p2*5,p3*3,p5*2)=min(10,9,10)=9
       note : 5 is fifth ug number
next ugly number= min(p2*5,p3*4,p5*2)=min(10,12,10)[above note]
next ugly number= min(p2*6,p3*4,p5*2)=min(12,12,10)=10
       note : 6 is sixth ug number
next ugly number= min(p2*6,p3*4,p5*3)=min(12,12,15)[abov note]
next ugly number= min(p2*8,p3*4,p5*3)=min(16,12,15)=12
      **** note : 8 is sevrnth ug number

Algorithm:
   ug[1]=p2=p3=p5=1;//p2=1,p3=1,p5=1 because the represent the index nub. of ug[]array
   For i=2 to 1500   {
     if(2*p2 min) then p2++;
     else if(3*p3 min) then p3++;
     else if(5*p5 min) then p5++;
     else if(2*p2==3*p3) then { p2++; i--;}
     else if(2*p2==5*p5) then { p2++;i--;}
     else if(3*p3==5*p5) then { p3++;i--;}
   }

DOWNLOAD DOCUMENT FILE :

Download to click

10254.the priest mathematician

2009-11-18T06:02:00.000-08:00

The ancient folklore behind the "Towers of Hanoi" puzzle invented by E. Lucas in 1883 is quite well known to us. One more recent legend tells us that the Brahmin monks from Benares never believed that the world could vanish at the moment they finished to transfer the 64 discs from the needle on which they were to one of the other needles, and they decided to finish the task as soon as possible.

Fig: The Four Needle (Peg) Tower of Hanoi

One of the priests at the Benares temple (who loved the mathematics) assured their colleagues to achieve the transfer in the afternoon (the rhythm they had thought was a disc-per-second) by using an additional needle. They couldn't believe him, but he proposed them the following strategy:

-- First move the topmost discs (say the top k discs) to one of the spare needles.

-- Then use the standard three needles strategy to move the remaining n-k discs (for a general case with n discs) to their destination.

-- Finally, move the top k discs into their final destination using the four needles.
He calculated the value to k in order to minimize the number of movements and get a total of 18433 transfers, so they spent just 5 hours, 7 minutes and 13 seconds against the more than 500000 millions years without the additional needle (as they would have to do 2^64-1 disc transfers. Can you believe it?)

Try to follow the clever priest's strategy and calculate the number of transfer using four needles but according with the fixed and immutable laws of Brahma, which require that the priest on duty must not move more than one disc at a time and that he must place this disc on a needle so that there is no smaller disc below it. Of course, the main goal is to calculate the k that minimize the number of transfers (even thought it is not know for sure that this is always the optimal number of movements).

Input
The input file contains several lines of input. Each line contains a single integer N, which is the number of disks to be transferred. Here 0<=N<=10000. Input is terminated by end of file.

Output
For each line of input produce one line of output which indicates the number of movements required to transfer the N disks to the final needle.

Sample Input:
1
2
28
64

Sample Output:
1
3
769
18433

Interesting matter:
1. First I submit this code in CPP: Runtime: .068 s Ranking: 17
2. Second time, I submit this code in JAVA: Runtime: 1.024 Ranking: Can’t see, because CPP code is better

3. Third time ,I submit this code in ANSI C: Runtime: 0.008 Ranking : 2 (What !)

Description:

1.       If number of disk is 0, then move 0.
2.       If number of disk is 1, then move 1.
3.       If number of disk is 2, then move 3.
4.       If number of disk is 3, then move 5.
5.       If number of disk is 4, then move 9.
6.       If number of disk is 5, then move 13.
7.       If number of disk is 6, then move 17.
8.       If number of disk is 7, then move 25.

9.       If number of disk is 8, then move 33.
10.    If number of disk is 9, then move 41.
11.    If number of disk is 10, then move 49.
12.    If number of disk is 11 then move 65.
13.    If number of disk is 12, then move 81.
14.    If number of disk is 13, then move 97.
15.    If number of disk is 14, then move 113.
16.    If number of disk is 15, then move 129.

So from disk number 2, we find a series,
3,5,9,13,17,25,33,41,49,65,81,97,113,129………………………………………………………………………………………………..
Algorithm:

f(n)=f(n-1)+2^i, where f(0)=0,f(1)=1,i=2,3,4,5
i=1, then loop = i+1=2, diff=2^1=2
   loop:
       1. f(2)=f(1)+2=1+2=3
       2.f(3)=f(2)+2=3+2=5
i=2,then loop=i+1=3,diff=2^2=4
     1.f[4]=f[3]+4=5+4=9
     2.f[5]=f[4]+4=9+4=13
     3.f[6]=f[5]+4=13+4=17

……
******Use Big Number

f[0]=0,f[1]=1;
i=2;
loop_c;
int j=1;
diff=1;
while(i<=max_disk){
          loop_c=j+1;
          diff=diff+diff;
         for(int p=1;p<=loop_c;p++){
                      f[i]=f[i-1]+diff;
                      i++;
                     if(i>max_disk)
                                break;
          }
         j++;
}

Now try yourself…..
Or download code:

DOWNLOAD DOCUMENT FILE :

Download to click

10258.Contest Scoreboard

2009-11-18T05:52:00.000-08:00

Think the contest score boards are wrong? Here's your chance to come up with the right rankings.Contestants are ranked first by the number of problems solved (the more the better), then by decreasing amounts of penalty time. If two or more contestants are tied in both problems solved and penalty time, they are displayed in order of increasing team numbers.
A problem is considered solved by a contestant if any of the submissions for that problem was judged correct. Penalty time is computed as the number of minutes it took for the first correct submission for a problem to be received plus 20 minutes for each incorrect submission received prior to the correct solution. Unsolved problems incur no time penalties.

Input:
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.Input consists of a snapshot of the judging queue, containing entries from some or all of contestants 1 through 100 solving problems 1 through 9. Each line of input will consist of three numbers and a letter in the format contestant problem time L
where L can be C, I, R, U or E. These stand for Correct, Incorrect, clarification Request, Unjudged and Erroneous submission. The last three cases do not affect scoring.Lines of input are in the order in which submissions were received.

Output:
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.Output will consist of a scoreboard sorted as previously described. Each line of output will contain a contestant number, the number of problems solved by the contestant and the time penalty accumulated by the contestant. Since not all of contestants 1-100 are actually participating, display only the contestants that have made a submission.

Sample Input:
5

1 1 20 C
1 1 25 C

1 2 10 I
3 1 11 C
1 2 19 R
1 2 21 C
1 1 25 C

1 2 10 I
3 1 11 C
1 2 19 R
1 2 21 C
1 1 25 C
1 3 20 I
5 1 30 I
3 2 10 C
4 1 30 I

38 1 0 C
48 1 1 R
83 1 2 E
89 9 3 R
7 5 4 R
68 1 5 U
61 1 6 U
27 1 7 R
21 7 8 R
55 2 9 I
54 1 10 U
69 1 11 C
59 2 12 I
43 3 13 I
7 9 14 R
84 6 15 R
52 8 16 C
32 7 17 C
87 7 18 U
44 1 19 I
87 6 20 I
21 6 21 U
6 4 22 E
44 8 23 I
72 5 24 R
35 1 25 E
57 4 26 E
24 5 27 C
30 3 28 I
85 9 29 I
72 5 30 U
30 7 31 U
8 5 32 R
88 1 33 I
61 2 34 C
35 6 35 R
77 4 36 C
46 8 37 I
21 9 38 E
74 3 39 R
7 4 40 U
25 4 41 R
48 1 42 I
87 1 43 C
84 3 44 U
96 9 45 U
60 5 46 R
75 2 47 I
29 4 48 E
3 7 49 I

1 2 10 I
3 1 11 C
1 2 19 R
1 2 21 C
1 1 25 C
1 3 20 I
1 4 40 I
8 4 50 I

Sample Output:
1 1 20

1 2 66
3 1 11

3 2 21
1 2 66
4 0 0
5 0 0

38 1 0
69 1 11
52 1 16
32 1 17
24 1 27
61 1 34
77 1 36
87 1 43
3 0 0
6 0 0
7 0 0
8 0 0
21 0 0
25 0 0
27 0 0
29 0 0
30 0 0
35 0 0
43 0 0
44 0 0
46 0 0
48 0 0
54 0 0
55 0 0
57 0 0
59 0 0
60 0 0
68 0 0
72 0 0
74 0 0
75 0 0
83 0 0
84 0 0
85 0 0
88 0 0
89 0 0
96 0 0

1 2 66
3 1 11
8 0 0

Hinds:
Big problem is to take input:
Solution:

gets(str);
if(strlen(str)==0)
                 break;
sscanf(str,”%d %d %d %c”,&tn,&pn,&rt,&ch);

1.       Remember, when a solution is accepted then penalty time is added .otherwise not.
2.       First sort descending order according to total solved problem, if equal , then sort ascending order according to penalty time, if equal ,then sort ascending order according to team number
3.       Same problem can accept twice; take only first time, other is ignored (see first input).
4.       Use structure & use qsort function.
5.       Initialize the data correctly.
6.       The outputs of two consecutive cases will be separated by a blank line.
7.       Last has no newline…Be Careful.

Try owning ….
If can’t, take the code….

DOWNLOAD DOCUMENT FILE :

Download to click

10252.common permutation

2009-11-18T05:42:00.000-08:00

Given two strings of lowercase letters, a and b, print the longest string x of lowercase letters such that there is a permutation of x that is a subsequence of a and there is a permutation of x that is a subsequence of b.

Input
Input file contains several lines of input. Consecutive two lines make a set of input. That means in the input file line 1 and 2 is a set of input, line 3 and 4 is a set of input and so on. The first line of a pair contains a and the second contains b. Each string is on a separate line and consists of at most 1000 lowercase letters.

Output
For each set of input, output a line containing x. If several x satisfy the criteria above, choose the first one in alphabetical order.

Sample Input:

icky
pretty
women
walking
down
the
street
meningitis
frontal
yelp

verbatim
greater
prettywoman
walkingdown
inging
singing
ab
ba
ab
cd
cat
bat

Sample Output:

e
nw
et
nt

aert
anow
ggiinn
ab

at

!Be careful: here may be empty lines in the input.
Discussion:
You can use straightforward algorithm or the following:
1. First take two array A[],B[],sort two input by using qsort() function.
2. Each char of two string is convert into integer n then A[n]++ for A[] and B[n]++ for B[].
3. Then from i=97 to 122  a to z element of A[] & B[] check, if both have value greater than 0 then take m=min(A[i],B[i]). Convert I to char ch. Ch print m times
4. Print newline.

DOWNLOAD DOCUMENT FILE :

Download to click

10213.How many pieces of land

2009-11-18T05:29:00.000-08:00

You are given an elliptical shaped land and you are asked to choose n arbitrary points on its boundary. Then you connect all these points with one another with straight lines (that’s n*(n-1)/2 connections for n points). What is the maximum number of pieces of land you will get by choosing the points on the boundary carefully?

Fig: When the value of n is 6.

Input
The first line of the input file contains one integer S (0 < S < 3500), which indicates how many sets of input are there. The next S lines contain S sets of input. Each input contains one integer N (0<=N<2^31).

Output
For each set of input you should output in a single line the maximum number pieces of land possible to get for the value of N.

Sample Input:
4
1
2
3
4 Sample Output:
1
2
4
8

Description: presented by rizoan toufiq

F(N) = ( N * (N-1) * (N*N-5*N+18) / 24 ) + 1
proof:
oh......that is quite difficult to tell you the proof by text......hope you will understand what I say:Let P(n) be the number of lands when n points are drawn on circle…. Now assume knowing P(n-1), want to know P(n) by adding the n-th point
when the n-th point draw a line to the k-th point (1 <= k <= n-1)on the LHS on k-th point, there is k-1 points between k-th and n-th point on the RHS on k-th point, there is (n-1)-k+1 points between k-th and n-th point the points in these 2 sets(LHS, RHS) are completely connected,so there are (k-1)*(n-k) lines crossed by the newly drawn line,creating (k-1)*(n-k)+1 new lands......
So, drawing lines from newly added n-th point to all n-1 old points,
will create summation[(k-1)(j-k)+1] {k = 1..j (j = n-1)} new lands
let says the summation be F(j)
P(n)= P(n-1) + F(n-1)
= P(n-2) + F(n-2) + F(n-1)
.....
= P(0) + F(1) + F(2) + ....... + F(n-1)
= 1 + summation(F(i)) {i = 1..n-1}

by using formula of summation to simplify the equatoin(what a difficult job.....)
I get answer = (i - 1) * i * (i * i - 5 * i + 18) / 24 + 1;

DOWNLOAD DOCUMENT FILE :

Download to click

10137.the trip

2009-11-17T23:27:00.000-08:00

A number of students are members of a club that travels annually to exotic locations. Their destinations in the past have included Indianapolis, Phoenix, Nashville, Philadelphia, San Jose, and Atlanta. This spring they are planning a trip to Eindhoven.
The group agrees in advance to share expenses equally, but it is not practical to have them share every expense as it occurs. So individuals in the group pay for particular things, like meals, hotels, taxi rides, plane tickets, etc. After the trip, each student's expenses are tallied and money is exchanged so that the net cost to each is the same, to within one cent. In the past, this money exchange has been tedious and time consuming. Your job is to compute, from a list of expenses, the minimum amount of money that must change hands in order to equalize (within a cent) all the students' costs.

The Input
Standard input will contain the information for several trips. The information for each trip consists of a line containing a positive integer, n, the number of students on the trip, followed by n lines of input, each containing the amount, in dollars and cents, spent by a student. There are no more than 1000 students and no student spent more than $10,000.00. A single line containing 0 follows the information for the last trip.

The Output
For each trip, output a line stating the total amount of money, in dollars and cents, that must be exchanged to equalize the students' costs.

Sample Input
3
10.00
20.00
30.00
4
15.00
15.01
3.00
3.01
0

Output for Sample Input
$10.00
$11.99

Tips:
1.
If (currentStudentPayment > averagePayment)
positiveDifference += currentStudentPayment - averagePayment;
Else
negativeDifference += averagePayment - currentStudentPayment;

if(negativeDifference > positiveDifference)
return negativeDifference
else
return positiveDifference

2. Here negative or positive difference must be int which is the tic of this problem

More Specific hinds:
he problem with this problem may be related to precision error. Here is solution by Neilor:
double highx = (int)((total/n+0.0099)*100);
double lowx = (int)((total/n)*100);
highx /= 100;
lowx /= 100;
Where total is the total sum of the money and n is the number of students.

Then, test each student money if is > than highx or < than lowx, accumulate (student[i]-highx) or (lowx-students[i]), respectively.
Then, output the variable that have the bigger value.

DOWNLOAD DOCUMENT FILE :

Download to click

10116.robot motion

2009-11-17T23:20:00.000-08:00

A robot has been programmed to follow the instructions in its path. Instructions for the next direction the robot is to move are laid down in a grid. The possible instructions are
N north (up the page)
S south (down the page)
E east (to the right on the page)
W west (to the left on the page)
For example, suppose the robot starts on the north (top) side of Grid 1 and starts south (down). The path the robot follows is shown. The robot goes through 10 instructions in the grid before leaving the grid.
Compare what happens in Grid 2: the robot goes through 3 instructions only once, and then starts a loop through 8 instructions, and never exits.
You are to write a program that determines how long it takes a robot to get out of the grid or how the robot loops around.
There will be one or more grids for robots to navigate. The data for each is in the following form. On the first line are three integers separated by blanks: the number of rows in the grid, the number of columns in the grid, and the number of the column in which the robot enters from the north. The possible entry columns are numbered starting with one at the left. Then come the rows of the direction instructions. Each grid will have at least one and at most 10 rows and columns of instructions. The lines of instructions contain only the characters N, S, E, or W with no blanks. The end of input is indicated by a row containing 0 0 0.
For each grid in the input there is one line of output. Either the robot follows a certain number of instructions and exits the grid on any one the four sides or else the robot follows the instructions on a certain number of locations once, and then the instructions on some number of locations repeatedly. The sample input below corresponds to the two grids above and illustrates the two forms of output. The word "step" is always immediately followed by "(s)" whether or not the number before it is 1.

Example input:
3 6 5
NEESWE
WWWESS
SNWWWW
4 5 1
SESWE
EESNW
NWEEN
EWSEN
0 0 0

Example output:
10 step(s) to exit
3 step(s) before a loop of 8 step(s)

Tips:
1. First you have to input correctly.
2. Take two array on is indicate input array other array element represent movement number.
3. If out of col or row then only print count step
4. Otherwise count -arry count current position value -1
5. And count= count-loop count;
6. End

DOWNLOAD DOCUMENT FILE :

Download to click

10062.Tell me the frequencies!

2009-11-17T23:13:00.000-08:00

Given a line of text you will have to find out the frequencies of the ASCII characters present in it. The given lines will contain none of the first 32 or last 128 ASCII characters. Of course lines may end with ‘\n’ and ‘\r’ but always keep those out of consideration.

Input
Several lines of text are given as input. Each line of text is considered as a single input. Maximum length of each line is 1000.

Output
Print the ASCII value of the ASCII characters which are present and their frequency according to the given format below. A blank line should separate each set of output. Print the ASCII characters in the ascending order of their frequencies. If two characters are present the same time print the information of the ASCII character with higher ASCII value first. Input is terminated by end of file.

Sample Input:
AAABBC
122333

Sample Output:
67 1
66 2
65 3

49 1
50 2
51 3

Tics:
1. Declear a structure like: struct arra{ int ascii,int fre} a[128];
2. Store a[m].ascii=m and a[m].fre++
3. Sort frequency wise and if both fre. Are equal the first large ascii
4. Loop is continue from 32 to 127
5. Print newline exactly. No etra new line at the end of the output.

DOWNLOAD DOCUMENT FILE :

Download to click

10042.Smith Numbers

2009-11-17T23:05:00.000-08:00

Background
While skimming his phone directory in 1982, Albert Wilansky, a mathematician of Lehigh University , noticed that the telephone number of his brother-in-law H. Smith had the following peculiar property: The sum of the digits of that number was equal to the sum of the digits of the prime factors of that number. Got it? Smith's telephone number was 493-7775. This number can be written as the product of its prime factors in the following way:

The sum of all digits of the telephone number is 4+9+3+7+7+7+5=42, and the sum of the digits of its prime factors is equally 3+5+5+6+5+8+3+7=42. Wilansky was so amazed by his discovery that he named this type of numbers after his brother-in-law: Smith numbers.
As this observation is also true for every prime number, Wilansky decided later that a (simple and unsophisticated) prime number is not worth being a Smith number and he excluded them from the definition.

Problem
Wilansky published an article about Smith numbers in the Two Year College Mathematics Journal and was able to present a whole collection of different Smith numbers: For example, 9985 is a Smith number and so is 6036. However, Wilansky was not able to give a Smith number which was larger than the telephone number of his brother-in-law. It is your task to find Smith numbers which are larger than 4937775.

Input
The input consists of several test cases, the number of which you are given in the first line of the input.
Each test case consists of one line containing a single positive integer smaller than 109.

Output
For every input value n, you are to compute the smallest Smith number which is larger than n and print each number on a single line. You can assume that such a number exists.

Sample Input
1
4937774
Sample Output
4937775

Tips:
1. First initialize prime number , in special way

How we generate prime number:
Let: p[]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; ie p[ele]=1 means ele is a prime.
Take i=2 which is prime, Now p[2]=0,p[4]=0,p[6]=0,p[8]=0,p[10]=0;p[12]=0;p[14]=0;
So now p[]={1,1,1,1,0,0,1,0,1,0,1,0,1,0,1}
Take i=3 which is prime, Now p[6]=0,p[9]=0;p[12]=0;p[15]=0;
So now p[]={1,1,1,1,0,1,0,1,0,0,0,1,0,1,0,0}
For i=4 , i<=sqrt(16) false so end
P[0]=1 ;p[1]=1,p[2]=1;p[3]=1;p[5]=1,p[7]=1;p[11]=1;p[13]=1;
Move a[0]=0,a[1]=1;a[2]=2;a[3]=3;a[4]=5;a[5]=7;a[6]=11;a[7]=13

2. Then sum each digit
3. Find per factor, find sum of digit of that factor, then add it with total sum
4. Check it not prime and totals are equal.

DOWNLOAD DOCUMENT FILE :

Download to click

10041 -Vito's Family

2009-11-17T09:48:00.000-08:00

Background
The world-known gangster Vito Deadstone is moving to New York. He has a very big family there, all of them living in Lamafia Avenue. Since he will visit all his relatives very often, he is trying to find a house close to them.

Problem
Vito wants to minimize the total distance to all of them and has blackmailed you to write a program that solves his problem.

Input
The input consists of several test cases. The first line contains the number of test cases.
For each test case you will be given the integer number of relatives r ( 0 < r < 500) and the street numbers (also integers) where they live ( 0 < si < 30000 ). Note that several relatives could live in the same street number.

Output
For each test case your program must write the minimal sum of distances from the optimal Vito's house to each one of his relatives. The distance between two street numbers si and sj is dij= |si-sj|.

Sample Input
2
2 2 4
3 2 4 6
Sample Output
2
4

Tics:
1. Sort the street number
2. Find median
3. Find summation of distance from median to street number i.e dis+=|median-s_i|
DOWNLOAD DOCUMENT FILE :

Download to click

10035- Primary Arithmetic

2009-11-17T07:18:00.000-08:00

Children are taught to add multi-digit numbers from right-to-left one digit at a time. Many find the "carry" operation - in which a 1 is carried from one digit position to be added to the next - to be a significant challenge. Your job is to count the number of carry operations for each of a set of addition problems so that educators may assess their difficulty.

Input
Each line of input contains two unsigned integers less than 10 digits. The last line of input contains 0 0.

Output
For each line of input except the last you should compute and print the number of carry operations that would result from adding the two numbers, in the format shown below.

Sample Input
123 456
555 555
123 594
0 0

Sample Output
No carry operation.
3 carry operations.
1 carry operation.

Tics:
1. Number separate 10 time only , this make solution easy.
2. Every loop, a%10+b%10+carry>9 then carry_counter++
3.(note, if total carry>1 you must output ''operations" instead of "operation").

DOWNLOAD DOCUMENT FILE :

Download to click

10013 - Super long sums

2009-11-17T06:14:00.000-08:00

The Problem
The creators of a new programming language D++ have found out that whatever limit for SuperLongInt type they make, sometimes programmers need to operate even larger numbers. A limit of 1000 digits is so small... You have to find the sum of two numbers with maximal size of 1.000.000 digits.

The Input
The first line of a input file is an integer N, then a blank line followed by N input blocks. The first line of an each input block contains a single number M (1<=M<=1000000) — the length of the integers (in order to make their lengths equal, some leading zeroes can be added). It is followed by these integers written in columns. That is, the next M lines contain two digits each, divided by a space. Each of the two given integers is not less than 1, and the length of their sum does not exceed M.
There is a blank line between input blocks.

The Output
Each output block should contain exactly M digits in a single line representing the sum of these two integers.
There is a blank line between output blocks.

Sample Input

Sample Output
4750



470

  

Discussion: presented by rizoan toufiq
Need a[100001] & b[1000001] character type array. Because the value of the array not more than 9.

Must print the last carry & be careful to print last newline

Each case: take input from 1 no array index. so that you can put last carry in 0 index.

For example:

       A[][2][3][4][5]
      B[][9][4][3][5] so here last index=4
Add:
I=4, (a[4]+b[4])%10+carry[initially it zero]=0 =reault[4=i]
         Carry=(a[4]+b[4])/10
I=3,similarly, result[i]=8 carry=0
I=2 ,similarly result[i]=7 carry=0
I=1,similarly result[i]=1 carry=1
I=0 ,result[i]=carry

*** I think it is helped you

DOWNLOAD DOCUMENT FILE :

Download to click

102 Ecological Bin Packing

2009-11-17T02:20:00.000-08:00

Background
Bin packing, or the placement of objects of certain weights into different bins subject to certain constraints, is an historically interesting problem. Some bin packing problems are NP-complete but are amenable to dynamic programming solutions or to approximately optimal heuristic solutions.
In this problem you will be solving a bin packing problem that deals with recycling glass.

The Problem
Recycling glass requires that the glass be separated by color into one of three categories: brown glass, green glass, and clear glass. In this problem you will be given three recycling bins, each containing a specified number of brown, green and clear bottles. In order to be recycled, the bottles will need to be moved so that each bin contains bottles of only one color.
The problem is to minimize the number of bottles that are moved. You may assume that the only problem is to minimize the number of movements between boxes.
For the purposes of this problem, each bin has infinite capacity and the only constraint is moving the bottles so that each bin contains bottles of a single color. The total number of bottles will never exceed 2^31.

The Input
The input consists of a series of lines with each line containing 9 integers. The first three integers on a line represent the number of brown, green, and clear bottles (respectively) in bin number 1, the second three represent the number of brown, green and clear bottles (respectively) in bin number 2, and the last three integers represent the number of brown, green, and clear bottles (respectively) in bin number 3. For example, the line 10 15 20 30 12 8 15 8 31
indicates that there are 20 clear bottles in bin 1, 12 green bottles in bin 2, and 15 brown bottles in bin 3.
Integers on a line will be separated by one or more spaces. Your program should process all lines in the input file.

The Output
For each line of input there will be one line of output indicating what color bottles go in what bin to minimize the number of bottle movements. You should also print the minimum number of bottle movements.
The output should consist of a string of the three upper case characters 'G', 'B', 'C' (representing the colors green, brown, and clear) representing the color associated with each bin.
The first character of the string represents the color associated with the first bin, the second character of the string represents the color associated with the second bin, and the third character represents the color associated with the third bin.
The integer indicating the minimum number of bottle movements should follow the string.
If more than one order of brown, green, and clear bins yields the minimum number of movements then the alphabetically first string representing a minimal configuration should be printed.

Sample Input
1 2 3 4 5 6 7 8 9
5 10 5 20 10 5 10 20 10
Sample Output
BCG 30
CBG 50

Discussion: presented by rizoan toufiq
There three bin:
1. first three integer represent the number of brown ,Green and clean glass in bin1
2. second three integer represent the number of brown ,Green and clean glass in bin2
3. third three integer represent the number of brown ,Green and clean glass in bin3
Now our task , minimum move to same colored glass in one bin.
We discuss only one case: 1 2 3 4 5 6 7 8 9
Bin1 : 1+2+3=6; Bin2: 4+5+6=15 Bin3: 7+8+9=24 [note: total=45]
You have to calculate below sequence [it is must, because more minimum combination will find. So combination of color glass in Bin: BCG,BGC,CBG,CGB,GBC,GCB]
1.If we want to take brown glass in bin1, clean in bin2 & green in bin3[BCG]
Bin1: We have to move 3 clean & 2 green glass from bin1; so move=2+3=5
Bin2: We have to move 4 brown & 5 green glass from bin2 ;so move=4+5=9
Bin3: We have to move 7 brown & 9 clean glass from bin3 ; so move=7+9=16
Total move=5+9+16=30 [note: 45-1-6-8=30]
2.If we want to take brown glass in bin1, green in bin2 & clean in bin3[BGC]
Bin1: We have to move 3 clean & 2 green glass from bin1; so move=2+3=5
Bin2: We have to move 4 brown & 6 clean glass from bin2 ;so move=4+6=10
Bin3: We have to move 7 brown & 8 green glass from bin3 ; so move=7+8=15
Total move=5+10+15=30 [note: 45-1-5-9=30]
3. CBG: bin1: move=1+2=3, bin2: move=11; bin3: 16 total move: 30 [note…]
4.CGB: bin1: move:3 ,bin2: move=10 ,bin3: move=17 ,total move= 30   [note …]
5.GBC: bin1: move:4 ,bin2: move=11 ,bin3: move=15,total move= 30   [note …]
6.GCB: bin1: move:4 ,bin2: move=9 ,bin3:17 move= ,total move= 30   [note …]

So minimum move =30 for each combination of color glass in the bin
So Answer: BCG 30 [BCG is alphabetically first]

DOWNLOAD DOCUMENT FILE :

Download to click

583.Prime Factors

2009-11-02T21:11:00.000-08:00

The most relevant definition for this problem is 2a: An integer g>1 is said to be prime if and only if its only positive divisors are itself and one (otherwise it is said to be composite). For example, the number 21 is composite; the number 23 is prime. Note that the decompositon of a positive number g into its prime factors, i.e., is unique if we assert that fi > 1 for all i and for i
One interesting class of prime numbers are the so-called Mersenne primes which are of the form 2^p- 1. Euler proved that 2³¹ - 1 is prime in 1772 -- all without the aid of a computer.

Input
The input will consist of a sequence of numbers. Each line of input will contain one number g in the range -231 < g <231, but different of -1 and 1. The end of input will be indicated by an input line having a value of zero.

Output
For each line of input, your program should print a line of output consisting of the input number and its prime factors. For an input number , where each f_i is a prime number greater than unity (with for i<j), the format of the output line should be

When g < 0, if , the format of the output line should be

Sample Input

-190

-191

-192

-193

-194

195

196

197

198

199

200

Sample Output

-190 = -1 x 2 x 5 x 19

-191 = -1 x 191

-192 = -1 x 2 x 2 x 2 x 2 x 2 x 2 x 3

-193 = -1 x 193

-194 = -1 x 2 x 97

195 = 3 x 5 x 13

196 = 2 x 2 x 7 x 7

197 = 197

198 = 2 x 3 x 3 x 11

199 = 199

200 = 2 x 2 x 2 x 5 x 5

Discussion

Algorithm:
Generate prime number in a array.

Divide the given number by the array element until arr[ele]<=sqrt(input). print arr[ele].

Print output carefully.

How we generate prime number:
Let: p[]={1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}; ie p[ele]=1 means ele is a prime.
Take i=2 which is prime, Now p[2]=0,p[4]=0,p[6]=0,p[8]=0,p[10]=0;p[12]=0;p[14]=0;
So now p[]={1,1,1,1,0,0,1,0,1,0,1,0,1,0,1}
Take i=3 which is prime, Now p[6]=0,p[9]=0;p[12]=0;p[15]=0;
So now p[]={1,1,1,1,0,1,0,1,0,0,0,1,0,1,0,0}
For i=4 , i<=sqrt(16) false so end
P[0]=1 ;p[1]=1,p[2]=1;p[3]=1;p[5]=1,p[7]=1;p[11]=1;p[13]=1;
Move a[0]=0,a[1]=1;a[2]=2;a[3]=3;a[4]=5;a[5]=7;a[6]=11;a[7]=13

DOWNLOAD DOCUMENT FILE :

Download to click