SAMPLE QUESTIONS AND ANSWERS 7

Train Swapping

Train Swapping

At an old railway station, you may still encounter one of the last remaining “train swappers”. A train swapper is an employee of the railroad, whose sole job it is to rearrange the carriages of trains.

Once the carriages are arranged in the optimal order, all the train driver has to do, is drop the carriages off, one by one, at the stations for which the load is meant.

The title “train swapper” stems from the first person who performed this task, at a station close to a railway bridge. Instead of opening up vertically, the bridge rotated around a pillar in the center of the river. After rotating the bridge 90 degrees, boats could pass left or right.

The first train swapper had discovered that the bridge could be operated with at most two carriages on it. By rotating the bridge 180 degrees, the carriages switched place, allowing him to rearrange the carriages (as a side effect, the carriages then faced the opposite direction, but train carriages can move either way, so who cares).

Now that almost all train swappers have died out, the railway company would like to automate their operation. Part of the program to be developed, is a routine which decides for a given train the least number of swaps of two adjacent carriages necessary to order the train. Your assignment is to create that routine.


Input Specification

The input contains on the first line the number of test cases (N). Each test case consists of two input lines. The first line of a test case contains an integer L, determining the length of the train ( ). The second line of a test case contains a permutation of the numbers 1 through L, indicating the current order of the carriages. The carriages should be ordered such that carriage 1 comes first, then 2, etc. with carriage L coming last.


Output Specification

For each test case output the sentence: ‘Optimal train swapping takes S swaps.‘ where S is an integer.

Example Input

3
3
1 3 2
4
4 3 2 1
2
2 1

Example Output

Optimal train swapping takes 1 swaps.
Optimal train swapping takes 6 swaps.
Optimal train swapping takes 1 swaps.
_____________________________________________________________
Solution :

#include
#include
#include
#include
#include
#include
using namespace std;

int main(){
freopen("299.txt","r",stdin);
freopen("299O.txt","w",stdout);
int T,n,l,tp,i,j;
int count=0;
vector la;

cin>>T;
for(int z=0;zcin>>n;
for(int x=0;xcin>>tp;
la.push_back(tp);
}
count=0;
for(i=0;i
while(la[i] != i+1){
for(j=0;jif(i==j)
continue;
if(i+1==la[j])
break;
}
tp=la[j];
la[j] = la[j-1];
la[j-1] = tp;
count++;
// cout<}

//cout<}

cout<<"Optimal train swapping takes "<la.clear();
}

return 0;
}

SAMPLE QUESTIONS AND ANSWERS 6

TEX Quotes

TeX is a typesetting language developed by Donald Knuth. It takes source text together with a few typesetting instructions and produces, one hopes, a beautiful document. Beautiful documents use “ and ” to delimit quotations, rather than the mundane " which is what is provided by most keyboards. Keyboards typically do not have an oriented double-quote, but they do have a left-single-quote ` and a right-single-quote '. Check your keyboard now to locate the left-single-quote key ` (sometimes called the “backquote key”) and the right-single-quote key ' (sometimes called the “apostrophe” or just “quote”). Be careful not to confuse the left-single-quote ` with the “backslash” key \. TeX lets the user type two left-single-quotes `` to create a left-double-quote “ and two right-single-quotes '' to create a right-double-quote ”. Most typists, however, are accustomed to delimiting their quotations with the un-oriented double-quote ".

If the source contained
"To be or not to be," quoth the bard, "that is the question."
then the typeset document produced by TeX would not contain the desired form:


“To be or not to be,” quoth the bard, “that is the question.”

In order to produce the desired form, the source file must contain the sequence:
``To be or not to be,'' quoth the bard, ``that is the question.''

You are to write a program which converts text containing double-quote (") characters into text that is identical except that double-quotes have been replaced by the two-character sequences required by TeX for delimiting quotations with oriented double-quotes. The double-quote (") characters should be replaced appropriately by either `` if the " opens a quotation and by '' if the " closes a quotation. Notice that the question of nested quotations does not arise: The first " must be replaced by ``, the next by '', the next by ``, the next by '', the next by ``, the next by '', and so on.


Input and Output

Input will consist of several lines of text containing an even number of double-quote (") characters. Input is ended with an end-of-file character. The text must be output exactly as it was input except that:

• the first " in each pair is replaced by two ` characters: `` and
• the second " in each pair is replaced by two ' characters: ''.

Sample Input

"To be or not to be," quoth the Bard, "that
is the question".
The programming contestant replied: "I must disagree.
To `C' or not to `C', that is The Question!"

Sample Output

``To be or not to be,'' quoth the Bard, ``that
is the question''.
The programming contestant replied: ``I must disagree.
To `C' or not to `C', that is The Question!''
_____________________________________________________________________

Solution :

#include
#include
#include
#include
#include
#include
//#include
using namespace std;

int main(){
freopen("272.txt","r",stdin);
freopen("272O.txt","w",stdout);
string line;
bool first = true;
char c;
while(1){
c = getchar();
if(c==EOF)
break;
if(c != '\n'){
if(c == '"'){
if(first){
cout<<"``";
first = first ^ 1;
}
else {
cout<<"''";
first = first ^ 1;
}
}
else {
cout<}
}
else {
cout<// getchar();
}
}

//getch();
return 0;
}

SAMPLE QUESTIONS AND ANSWERS 5

Euclid Problem

The Problem

From Euclid it is known that for any positive integers A and B there exist such integers X and Y that AX+BY=D, where D is the greatest common divisor of A and B. The problem is to find for given A and B corresponding X, Y and D.

The Input

The input will consist of a set of lines with the integer numbers A and B, separated with space (A,B<1000000001).

The Output

For each input line the output line should consist of three integers X, Y and D, separated with space. If there are several such X and Y, you should output that pair for which |X|+|Y| is the minimal (primarily) and X<=Y (secondarily).

Sample Input

4 6
17 17

Sample Output

-1 1 2
0 1 17
_______________________________________________________________
Solution :

#include
long d,x,y;

void extend(long a,long b){
long x1;
if(b>a){
x1=a;
a=b;Q
b=x1;
}

if(b==0){
d=a;
x=1;
y=0;
return;
}

extend(b,a%b);
// d=a;
x1=x-(a/b)*y;
x=y;
y=x1;
}

int main(){
long q,w,e;

while(scanf("%ld %ld", &q, &w)==2){
extend(q,w);
if(w>q){
e=x;
x=y;
y=e;
}
printf("%ld %ld %ld\n",x,y,d);
}
return 0;
}

SAMPLE QUESTIONS AND ANSWERS 4

Hashmat the Brave Warrior

Problem A

Hashmat the brave warrior
Input: standard input
Output: standard output

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
__________________________________________________________________
the challenge is in how getting the input and handling int size..otherwise it is just a simple substraction

Solution :
#include
using namespace std;
int main(){
//freopen(“10055I.txt”,”r”,stdin);
//freopen(“10055IO.txt”,”w”,stdout);
long long x,y,z;
while(cin>>x>>y){
if(x>y){
cout<} else {
cout<}
}
}

SAMPLE QUESTIONS AND ANSWERS 3

What’s Cryptanalysis?

Cryptanalysis is the process of breaking someone else’s cryptographic writing. This sometimes involves some kind of statistical analysis of a passage of (encrypted) text. Your task is to write a program which performs a simple analysis of a given text.

Input

The first line of input contains a single positive decimal integer n. This is the number of lines which follow in the input. The next n lines will contain zero or more characters (possibly including whitespace). This is the text which must be analyzed.

Output

Each line of output contains a single uppercase letter, followed by a single space, then followed by a positive decimal integer. The integer indicates how many times the corresponding letter appears in the input text. Upper and lower case letters in the input are to be considered the same. No other characters must be counted. The output must be sorted in descending count order; that is, the most frequent letter is on the first output line, and the last line of output indicates the least frequent letter. If two letters have the same frequency, then the letter which comes first in the alphabet must appear first in the output. If a letter does not appear in the text, then that letter must not appear in the output.


Sample Input
3
This is a test.
Count me 1 2 3 4 5.
Wow!!!! Is this question easy?
Sample Output
S 7
T 6
I 5
E 4
O 3
A 2
H 2
N 2
U 2
W 2
C 1
M 1
Q 1
Y 1

________________________________________________________________________
Solution :

#include
#include

SAMPLE QUESTIONS AND ANSWERS 2

Powers Et Al.

Problem G
Power et al.
Input: Standard Input
Output: Standard Output

Finding the exponent of any number can be very troublesome as it grows exponentially J. But in this problem you will have to do a very simple task. Given two non-negative numbers m and n, you will have to find the last digit of mn in decimal number system.

Input
The input file contains less than 100000 lines. Each line contains two integers m and n (Less than 10^101). Input is terminated by a line containing two zeroes. This line should not be processed.

Output
For each set of input you must produce one line of output which contains a single digit. This digit is the last digit of mn.
Sample Input Output for Sample Input

2 2 4
2 5 2
0 0

_______________________________________________________________________________________
Solution :

#include
#include
#include
#include
#include
#include
using namespace std;

long square(long n){ return n*n; }
long fastexp (long base, long power){
if(power ==0)
cout<<"1"<else if (power%2 == 0)
cout<else
cout<
}
long m,n,r,last;
long ary[4] = {4,1,2,3};
int main(){
//freopen("inputA6.txt","r",stdin);
//freopen("inputA6Out.txt","w",stdout);

cin>>m;
cin>>n;
while(m !=0 || n !=0){

// if(n==0)
// cout<<"1"<
// else if(n==1)
// cout<// else{
r = n %4;
fastexp(m,ary[r]);
//}
cin>>m;
cin>>n;
}

return 0;
}

SAMPLE QUESTIONS AND ANSWERS 1

Problem C: WERTYU

A common typing error is to place the hands on the keyboard one row to the right of the correct position. So “Q” is typed as “W” and “J” is typed as “K” and so on. You are to decode a message typed in this manner.

Input consists of several lines of text. Each line may contain digits, spaces, upper case letters (except Q, A, Z), or punctuation shown above [except back-quote (`)]. Keys labelled with words [Tab, BackSp, Control, etc.] are not represented in the input. You are to replace each letter or punction symbol by the one immediately to its left on the QWERTY keyboard shown above. Spaces in the input should be echoed in the output.

Sample Input
O S, GOMR YPFSU/
Output for Sample Input
I AM FINE TODAY.
____________________________________________________________________

Solution :

#include
#include
#include
#include
#include
#include