[shkola] Zadachi za podgotowka

Zdrawejte!

Kakto wi obeshtah eto wi nqkolko zadachki. Ne sa koj znae kolko trudni, 
no ne sa i straightforward, taka che trqbwa da se setite! Ne sxm si 
igral da prewezhdam zadachite, zatowa sa na anglijski - ako ima 
problemi pitajte!
Preporxchitelno e da napishete zadachite, a ne samo da gi izmislite i da 
kazhete "gotowo". Razpolagam s testowe, taka che mozhe da mi 
izprashtate source-owe.

Pozdrawi,
  Ivo

-- 
"If it happens, it must be possible."

Zadacha 1
========
Some major cities have subway systems in the form of a tree, i.e. 
between any pair of stations, there is one and only one way of going by 
subway. Moreover, most of these cities have a unique central station. 
Imagine you are a tourist in one of these cities and you want to 
explore all of the subway system. You start at the central station and 
pick a subway line at random and jump aboard the subway car. Every time 
you arrive at a station, you pick one of the subway lines you have not 
yet travelled on. If there is none left to explore at your current 
station, you take the subway line back on which you first came to the 
station, until you eventually have travelled along all of the lines 
twice, once for each direction. At that point you are back at the 
central station. Afterwards, all you remember of the order of your 
exploration is whether you went further away from the central station 
or back towards it at any given time, i.e. you could encode your tour 
as a binary string, where 0 encodes taking a subway line getting you 
one station further away from the central station, and 1 encodes 
getting you one station closer to the central station.

Input
On the first line of input is a single positive integer n, telling the 
number of test scenarios to follow. Each test scenario consists of two 
lines, each containing a string of the characters '0' and '1' of length 
at most 3000, both describing a correct exploration tour of a subway 
tree system.

Output
For each test scenario, output one line containing the text "same" if 
the two strings may encode exploration tours of the same subway tree 
system, or the text "different" if the two strings cannot be 
exploration tours of the same subway tree system.

Sample Input
2
0010011101001011
0100011011001011
0100101100100111
0011000111010101

Sample Output
same
different

Zadacha 2
========
In order to lower the risk of riots and escape attempts, the boards of 
two nearby prisons of equal prisoner capacity, have decided to 
rearrange their prisoners among themselves. They want to exchange half 
of the prisoners of one prison, for half of the prisoners of the other. 
However, from the archived information of the prisoners' crime history, 
they know that some pairs of prisoners are dangerous to keep in the 
same prison, and that is why they are separated today, i.e. for every 
such pair of prisoners, one prisoners serves time in the first prison, 
and the other in the second one. The boards agree on the importance of 
keeping these pairs split between the prisons, which makes their 
rearrangement task a bit tricky. In fact, they soon find out that 
sometimes it is impossible to fulfil their wish of swapping half of the 
prisoners. Whenever this is the case, they have to settle for 
exchanging as close to one half of the prisoners as possible.

Input
The input begins with a line containing two non-negative integers m and 
r, 1<m<200 being the number of prisoners in each of the two prisons, 
and r the number of dangerous pairs among the prisoners. Then follow r 
lines each containing a pair xi yi of integers in the range 1 to m, 
which means that prisoner xi of the first prison must not be placed in 
the same prison as prisoner yi of the second prison.

Ouptut
Output one line containing the largest integer k <= m / 2 , such that it 
is possible to exchange k prisoners of the first prison for k prisoners 
of the second prison without getting two prisoners of any dangerous 
pair in the same prison.

Sample Input
8 12
1 1
1 2
1 3
1 4
2 5
3 5
4 5
5 5
6 6
7 6
8 7
8 8

Sample Output
3


Zadacha 3
========
Little Tom is learning how to program. He has just written some programs 
but is afraid to run them, because he does not know if they will ever 
stop. Please write a program to help him.
This task is not as easy as it seem, because Tom's programs may behave 
nondeterministically. Given a program written by Tom, your program 
should tell him whether his program can stop and if so, what is the 
shortest possible time before it stops.
Tom's computer consists of 32 1-bit registers and the program consists 
of n instructions. The registers are numbered from 0 to 31 and the 
instructionsare numbered from 0 to n - 1.
Below MEM[a] stands for the contents of the a-th register, 0 <= a,b < 
32, 0 <= x < n, 0 <= c <= 1.
The instruction set is as follows:
Instruction     <=>             Semantics
----------------------------------
AND a b         <=>             MEM[a] := MEM[a] and MEM[b]
OR a b          <=>             MEM[a] := MEM[a] or MEM[b]
XOR a b         <=>             MEM[a] := MEM[a] xor MEM[b]
NOT a           <=>             MEM[a] := not MEM[a]
MOV a b <=>             MEM[a] := MEM[b]
SET a c         <=>             MEM[a] := c
RANDOM a        <=>             MEM[a] := random value (0 or 1)
JMP x           <=>             jump to the instruction with the number x
JZ x a          <=>             jump to the instruction with the number x if 
MEM[a] = 0
STOP            <=>             stop the program

The last instruction of every program is always STOP (although there can 
be more than one STOP instruction in a program). Every program starts 
with the instruction number 0. Before the start, the contents of the 
registers can be arbitrary values. Each instruction (including STOP) 
takes 1 processor cycle to execute.

Input
The first line of the input file contains an integer n (1 <= n <= 16) 
being the number of instructions of the program. Each of the next n 
lines contains one instruction of the program in the format given 
above. You may assume that the instruction and its arguments are 
separated by single space.

Output
The first and only line of the output should contain the shortest 
possible running time of the program, measured in processor cycles. If 
the program cannot stop, output should contain the word HANGS.

Sample Input
5
SET 0 1
JZ 4 0
RANDOM 0
JMP 1
STOP

Sample Output
6

Sample Input
5
MOV 3 5
NOT 3
AND 3 5
JZ 0 3
STOP

Sample Output
HANGS

Other related posts: