[Solved] Algorithm Homework3-AWESOME Number

We say a number is AWESOME if it is prime and has 1 in its ones place. You are given a number N and you are asked toanswer how many AWESOME numbers are not greater than N.InputThe input consists of a single integer N (1 <= N <= 20,000,000).OutputYou should print one line containing a single integer, the number of awesome numbers that are no larger than N.Example 1Input:6Output:0Example 2Input:11Output:1Example 3Input:100Output:5Page 1/1Prime GapA prime gap is the difference between two successive prime numbers. The n-th prime gap, denoted g(n) is the differencebetween the (n+1)-th and the n-th prime numbers, i.e.g(n) = p(n+1) – p(n)The first 7 prime numbers are 2, 3, 5, 7, 11, 13, 17, and the first 6 prime gaps are 1, 2, 2, 4, 2, 4.Shinya Yukimura is interested in prime gaps and he need some experimental data to verify his hypothesis. More specifically,given a closed interval [a,b], Shinya wants to find the two adjacent primes p1 and p2 (a <= p1 < p2 <= b) such that the primegap between p1 and p2 is minimized (i.e. p2-p1 is the minimum). If there are multiple prime pairs that have the same primegap, report the first pair. Shinya also wants to find the two adjacent primes p3 and p4 (a <= p3 < p4 <= b) that maximize thegap between p3 and p4 (choose the first pair if there are mote than one such pairs).Please write a program to help Shinya.InputTwo integer values a,b, with a < b. The difference between a and b will not exceed 1,000,000. 1 <= a <= b <=2,147,483,647.OutputIf there are no adjacent primes in the interval [a,b], output -1 followed by a newline.Otherwise the output should be 4 integers: p1,p2,p3,p4 as mentioned above separated by a space.Example 1Input:1 20Output:2 3 7 11Example 2Input:13 16Output:-1In the first example test case, the prime gap between 13 and 17 also has the largest value 4, but the pair (7,11) appearsbefore (13,17), so we output 7 11 instead of 13 17.Page 1/2Reverse Polish notationReverse Polish notation (RPN), also known as Polish postfix notation or simply postfix notation, is a mathematical notationin which operators follow their operands, in contrast to Polish notation (PN), in which operators precede their operands. Itdoes not need any parentheses as long as each operator has a fixed number of operands.You need to write a program that transforms an infix expression to a equivalent RPN according to the followingspecifications.1. The infix expression is in the input file in the format of one character per line, with a maximum of 50 lines. For example,(1+1)*(4*5+1)-4 would be in the form:(1+1)*(4*5+1)–42. There will be only one infix expression in the input file, and it will be an expression with a valid syntax.3. All operators are binary operators +, -, *, / .4. The operands will be one digit numerals: 0, 1, 2, … , 9.5. The operators * and / have the highest precedence. The operators + and – have the lowest precedence.Operators at the same precedence level associate from left to right. Parentheses act as grouping symbols that override the operator precedence.InputThere will be multiple lines in the input file as specified above.OutputThe output file will have a postfix expression all on one line with no whitespace between symbols and a single newlinecharacter at the end.ExampleInput:(1+1)*(4*5+1Page 2/2)–4Output:11+45*1+*4-Page 1/2Stack PuzzleThere are two sequences of stack operations converting the word TROT to TORT:[i i i i o o o oi o i i o o i o]where i and o stands for push and pop operation respectively. In this problem, you are given two words and you areasked to find out all sequences of stack operations converting the first word to the second.InputThe input consists of two lines, the first of which is the source word and the second is the target word.OutputYour program should print a sorted list of valid i/o sequences. The list is delimited by[]and the sequences are sorted in lexicographical order. Within each sequence, i ‘s’ and o ‘s are separated by a singlespace and each sequence is terminated by a new line.ProcessGiven an input word, a valid i/o sequence implies that every character of the word is pushed and popped exactly once,and no attempt is ever made to pop an empty stack. For example, if the word FOO is input, then the sequence:i i o i o o is valid and produces OFFi i o is not valid (too short),i i o o o i is not valid (illegal pop from an empty stack)A valid sequence infers a permutation of the letters in the input word. For example, given the input word FOO, bothsequences i i o i o o and i i i o o o give the word OOF.Example 1Input:madamadammOutput:[i i i i o o o i o oi i i i o o o o i oi i o i o i o i o oi i o i o i o o i o]Example 2Input:bahamabahamaPage 2/2Output:[i o i i i o o i i o o oi o i i i o o o i o i oi o i o i o i i i o o oi o i o i o i o i o i o]Example 3Input:longshortOutput:[]Example 4Input:ericriceOutput:[i i o i o i o o]Page 1/1TrainThis is a figure that shows the structure of a station for train dispatching.In this station, A is the entrance for each train and Bis the exit. S is the switching track. The coaches of atrain can enter the switching track from direction Aand must leave in direction B. Individual coaches canbe disconnected from the rest of the train as theyenter the switching track, so that they can bereorganized before they continue in direction B. If acoach enters the switching track from direction A, itmust leave in direction B (i.e., it cannot returntowards A). If a coach leaves in direction B, it cannot return back to the switching track.Assume that a train consist of n coaches labeled {1, 2, …, n}. A dispatcher wants to know whether these coaches can pullout at B in the order of {a1, a2, …, an}.InputThe 1st line contains an integer n (n <= 1,000) equal to the number of coaches, as described above. In each of the nextlines of the input, except the last one, there is a permutation of 1, 2, . . . , n, this is the sequence {a1, a2, …, an} that thedispatcher would like to achieve as the coaches leave the switching track in direction B. The last line of the block containsjust ‘0’ (to indicate the end of input).OutputYou should output the result for each permutation. If the sequence is feasible, output a “Yes”, followed by a newline. If thesequence is infeasible, output a “No”, followed by a newline.Example 1 (pictured in the figure)Input:43 2 4 10Output:YesExample 2Input:51 2 3 4 54 5 1 3 20Output:YesN