about summary refs log tree commit diff
path: root/12/TP-HN-2009/R1/PS.PAS
blob: 6cf2d09abc78726a1f064a0ba6e84e983a29254f (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
var
  f : text;
  m, n : byte;
  k, i, j, l, gcd0 : integer;
  a, b : array[1..30] of integer;
  c : array[0..1, 1..900] of integer;

function gcd(d, e : integer) : integer;
  var tmp : integer;
  begin
    while d > 0 do
      begin
        tmp := d;
        d := e mod d;
        e := tmp
      end;
    gcd := e
  end;

procedure qsort(b, e: integer);
  var i, j, x, tmp: integer;
  begin
    i := b;
    j := e;
    x := (b + e) div 2;
    repeat
      while c[0, i] * c[1, x] < c[0, x] * c[1, i] do inc(i);
      while c[0, x] * c[1, j] < c[0, j] * c[1, x] do dec(j);
      if i <= j then
        begin
          tmp := c[0, i];
          c[0, i] := c[0, j];
          c[0, j] := tmp;
          tmp := c[1, i];
          c[1, i] := c[1, j];
          c[1, j] := tmp;
          inc(i);
          dec(j)
        end
    until i > j;
    if b < j then qsort(b, j);
    if i < e then qsort(i, e)
  end;

begin
  assign(f, 'PS.INP');
  reset(f);
  read(f, m, n, k);
  for i := 1 to m do read(f, a[i]);
  for i := 1 to n do read(f, b[i]);
  close(f);
  l := 0;
  for i := 1 to m do
    for j := 1 to n do
      begin
        inc(l);
        gcd0 := gcd(a[i], b[j]);
        c[0, l] := a[i] div gcd0;
        c[1, l] := b[j] div gcd0
      end;
  qsort(1, l);
  i := 1;
  while i < l do
    begin
      inc(i);
      if c[0, i] * c[1, i - 1] = c[0, i - 1] * c[1, i] then
        begin
          dec(l);
          for j := i to l do
            begin
              c[0, j] := c[0, j + 1];
              c[1, j] := c[1, j + 1]
            end
        end
    end;
  assign(f, 'PS.OUT');
  rewrite(f);
  writeln(f, c[0, k], ' ', c[1, k]);
  close(f)
end.