Everybody knows - if not how to play chess - at least how the queen moves on the chessboard .Let's imagine we have a chessboard shaped like a hexagon. Lower down there is such a chessboard of size 3, where on each side there are 3 wholes(marked with 'x') .
x x x
x x x x
x x x x x
x x x x
x x x
Then a queen- marked with Q - will controle the fields marked with 'o':
x o x
o o x x
o Q o o o
o o x x
x o x
It seems easy: here the queen can controle 3 diagonals (it can't act on the
vertical), as a difference from the classic chessboard, where it can
controle
up to 4 diagonals.
p_1 q_1 p_2 q_2 .. p_k q_k
Example: For input
3a possible output:
3 1 1 2 3 3 2Time for test: 5" for test (for a computer PC 386 40 MHz).
Observations:
Through every point of the board exactly 3 diagonals pass.
Every two diagonals that pass through a point make a 120 degrees angle
between them.
According to Erdos' theorem, for any n>1, between n and 2n there is
at least one prime number.
Having a positive integer number k , k<=1300, find out the smallest
number
n having the property that in the open interval (n,2n) there are exactly k
prime numbers.
Input(from the keyboard):
kOutput(on the screen):
nRequest: The program must solve the problem in maximum 60" for each test. (PC-386, 40 MHz}
An information service caught a messenger who was sending the following encripted text:
alzfx mmdrw mmzff kuefi ttThe agents who were following him are warned to find out everything they can, without letting know that they discovered an information leak (otherwise the opponent would know that he is traced and he would change his tactic). They are doing their job and succeed in finding the incripting program, which codified a message using a key word (the same one or a different one for each text). They even found the key which encripted the text from above : that is the word 'march'. This is the encription program:
uses crt;
var
ii,o:text;
text,key:string;
i,j,k,k1,n,m,p:integer;
begin
clrscr;
assign(ii,'vig_in'); assign(o,'vig_out');
reset(ii);rewrite(o);
readln(ii,text);
{The text is written with small letters, without spaces; after a blank line ,
the key is
given}
readln(ii); readln(ii,key);
n:=length(text); m:=length(key);
for j:=1 to n do begin
i:=ord(text[j])-97;
k1:=j mod m;
if k1=0 then k1:=m;
k:=ord(key[k1])-97;
p:=(i+k) mod 26;
write(o,char(p+97));
if (j mod 5)=0 then write(o,' ');
if (j mod 55)=0 then writeln(o)
end;
close(ii); close(o)
end.
At these informations, the service can make a decription program .
This way , the following messages have been decripted:
1) alzfx mmdrw mmzff kuefi tt.....................................key 'march' 2) oayfr zuanm rfytu hnjyb juatu qyjnc uadya......................key 'one' 3) rzqpd qdrig sqqtw uaiww kdtic onlbi ooddt qoobl aqvci uo.......key 'two' 4) befik rkigj ikncx qorgm evqib dezbw izbxm lbepc fv.............key 'three' 5) cumfn ressi prtjy bagrh ralzh jthkw tsxdu cagtu obhrl p........key 'four'Now you try.
Requested: ONLY the initial messages and the corresponding decripted messages.