$30
Algorithm Homework 3 Solved
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 to answer how many AWESOME numbers are not greater than N.
Input
The input consists of a single integer N (1 <= N <= 20,000,000).
Output
You should print one line containing a single integer, the number of awesome numbers that are no larger than N.
Example 1
Example 2
Example 3
Page 1/1
Prime Gap
A prime gap is the difference between two successive prime numbers. The n-th prime gap, denoted g(n) is the difference between 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 prime gap between p1 and p2 is minimized (i.e. p2-p1 is the minimum). If there are multiple prime pairs that have the same prime gap, report the first pair. Shinya also wants to find the two adjacent primes p3 and p4 (a <= p3 < p4 <= b) that maximize the gap between p3 and p4 (choose the first pair if there are mote than one such pairs).
Please write a program to help Shinya.
Input
Two 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.
Output
If 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 1
Example 2
before (13,17), so we output 7 11 instead of 13 17.
Page 1/1
Reverse Polish notation
Reverse Polish notation (RPN), also known as Polish postfix notation or simply postfix notation, is a mathematical notation in which operators follow their operands, in contrast to Polish notation (PN), in which operators precede their operands. It does 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 following specifications.
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:
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.
Input
There will be multiple lines in the input file as specified above.
Output
The output file will have a postfix expression all on one line with no whitespace between symbols and a single newline character at the end.
Example
Input:
(
1
+
1
)
*
(
4
*
5
+
1
Page 1/2
Page 2/2
Stack Puzzle
asked to find out all sequences of stack operations converting the first word to the second.
Input
The input consists of two lines, the first of which is the source word and the second is the target word. Output
space and each sequence is terminated by a new line.
Process
Given 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 OFF i 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, both sequences i i o i o o and i i i o o o give the word OOF.
Example 3
Example 4
Page 2/2
Train
This is a figure that shows the structure of a station for train dispatching.
In this station, A is the entrance for each train and B is the exit. S is the switching track. The coaches of a train can enter the switching track from direction A and must leave in direction B. Individual coaches can be disconnected from the rest of the train as they enter the switching track, so that they can be reorganized before they continue in direction B. If a coach enters the switching track from direction A, it must leave in direction B (i.e., it cannot return towards 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 pull out at B in the order of {a1, a2, …, an}.
Input
The 1st line contains an integer n (n <= 1,000) equal to the number of coaches, as described above. In each of the next lines of the input, except the last one, there is a permutation of 1, 2, . . . , n, this is the sequence {a1, a2, …, an} that the dispatcher would like to achieve as the coaches leave the switching track in direction B. The last line of the block contains just ‘0’ (to indicate the end of input).
Output
You should output the result for each permutation. If the sequence is feasible, output a "Yes", followed by a newline. If the sequence is infeasible, output a "No", followed by a newline.
Example 1 (pictured in the figure)
Example 2
Page 1/1
