From 7d19f480637e9e880b98dabfbcf8e885b0a2d3b9 Mon Sep 17 00:00:00 2001
From: Raphael McSinyx <vn.mcsinyx@gmail.com>
Date: Tue, 21 Feb 2017 21:09:39 +0700
Subject: Update others/volume1

---
 others/volume1/001.scm  |  3 +--
 others/volume1/077.pas  | 59 ++++++++++++++++++++++++++++++++++++++++++++++++
 others/volume1/078.pas  | 60 +++++++++++++++++++++++++++++++++++++++++++++++++
 others/volume1/080.pas  | 17 ++++++++++++++
 others/volume1/081.pas  | 30 +++++++++++++++++++++++++
 others/volume1/082.pas  | 20 +++++++++++++++++
 others/volume1/086.scm  |  7 ++++++
 others/volume1/092.pas  | 10 +++++++++
 others/volume1/095.pas  | 11 +++++++++
 others/volume1/096.pas  | 34 ++++++++++++++++++++++++++++
 others/volume1/112.pas  | 39 ++++++++++++++++++++++++++++++++
 others/volume1/113.pas  | 28 +++++++++++++++++++++++
 others/volume1/clib.pas | 32 +++++++++++++++++++++++++-
 13 files changed, 347 insertions(+), 3 deletions(-)
 create mode 100644 others/volume1/077.pas
 create mode 100644 others/volume1/078.pas
 create mode 100644 others/volume1/080.pas
 create mode 100644 others/volume1/081.pas
 create mode 100644 others/volume1/082.pas
 create mode 100644 others/volume1/086.scm
 create mode 100644 others/volume1/092.pas
 create mode 100644 others/volume1/095.pas
 create mode 100644 others/volume1/096.pas
 create mode 100644 others/volume1/112.pas
 create mode 100644 others/volume1/113.pas

(limited to 'others')

diff --git a/others/volume1/001.scm b/others/volume1/001.scm
index 4e6573b..93f3f89 100644
--- a/others/volume1/001.scm
+++ b/others/volume1/001.scm
@@ -1,2 +1 @@
-(display (let ((a (read)) (b (read))) (exact->inexact (/ (+ a b) 2))))
-(newline)
+(format #t "~a\n" (exact->inexact (/ (+ (read) (read)) 2)))
diff --git a/others/volume1/077.pas b/others/volume1/077.pas
new file mode 100644
index 0000000..2d13a4d
--- /dev/null
+++ b/others/volume1/077.pas
@@ -0,0 +1,59 @@
+uses clib;
+
+var
+  n, m: int32;
+  a, b, c: array of int64;
+  i, j: int64;
+
+begin
+  readln(n, m);
+  setlength(a, n);
+  repeat
+    dec(n);
+    read(a[n])
+  until n = 0;
+  qsort(a);
+  setlength(b, m);
+  repeat
+    dec(m);
+    read(b[m])
+  until m = 0;
+  qsort(b);
+
+  setlength(c, 0);
+  for i in a do
+    if (bsearch(b, i) > -1) and
+       ((length(c) = 0) or (c[length(c) - 1] < i)) then
+      begin
+        setlength(c, length(c) + 1);
+        c[length(c) - 1] := i
+      end;
+
+  for i in c do
+    begin
+      dec(n, 2);
+      j := bsearch(a, i);
+      for m := j downto 0 do
+        if a[m] = i then
+          inc(n)
+        else
+          break;
+      for m := j to length(a) - 1 do
+        if a[m] = i then
+          inc(n)
+        else
+          break;
+      j := bsearch(b, i);
+      for m := j downto 0 do
+        if b[m] = i then
+          inc(n)
+        else
+          break;
+      for m := j to length(b) - 1 do
+        if b[m] = i then
+          inc(n)
+        else
+          break
+    end;
+  writeln(n)
+end.
diff --git a/others/volume1/078.pas b/others/volume1/078.pas
new file mode 100644
index 0000000..a202c6a
--- /dev/null
+++ b/others/volume1/078.pas
@@ -0,0 +1,60 @@
+uses clib;
+
+var
+  n, i, j: int16;
+  m: int32 = 0;
+  a, b: array of int16;
+
+procedure sort(l, h: int32);
+  var
+    i, j, k: int32;
+    tmp: int16;
+  begin
+    i := l;
+    j := h;
+    k := (l + h) div 2;
+    repeat
+      while a[i] * b[k] < a[k] * b[i] do
+        inc(i);
+      while a[j] * b[k] > a[k] * b[j] do
+        dec(j);
+      if i <= j then
+        begin
+          tmp := a[i];
+          a[i] := a[j];
+          a[j] := tmp;
+          tmp := b[i];
+          b[i] := b[j];
+          b[j] := tmp;
+          inc(i);
+          dec(j)
+        end
+    until i > j;
+
+    if l < j then
+      sort(l, j);
+    if i < h then
+      sort(i, h)
+  end;
+
+begin
+  readln(n);
+  setlength(a, m);
+  setlength(b, m);
+  for i := 1 to n do
+    for j := 1 to n do
+      if gcd(i, j) = 1 then
+        begin
+          inc(m);
+          setlength(a, m);
+          a[m - 1] := i;
+          setlength(b, m);
+          b[m - 1] := j
+        end;
+  sort(0, m - 1);
+  writeln(m);
+  repeat
+    dec(m);
+    writeln(a[m], ' ', b[m])
+  until m = 0;
+end.
diff --git a/others/volume1/080.pas b/others/volume1/080.pas
new file mode 100644
index 0000000..599511a
--- /dev/null
+++ b/others/volume1/080.pas
@@ -0,0 +1,17 @@
+var
+  n, i, j: int32;
+  b: array of boolean;
+
+begin
+  readln(n);
+  setlength(b, n + 1);
+  for i := 2 to n do
+    b[i] := true;
+  for i := 2 to trunc(sqrt(n)) do
+    if b[i] then
+      for j := 2 to n div i do
+        b[i * j] := false;
+  for i := 2 to n do
+    if b[i] then
+      writeln(i)
+end.
diff --git a/others/volume1/081.pas b/others/volume1/081.pas
new file mode 100644
index 0000000..11dce4b
--- /dev/null
+++ b/others/volume1/081.pas
@@ -0,0 +1,30 @@
+var
+  b: array[0..1000001] of boolean;
+  n, a, i, max: int32;
+
+begin
+  for i := 0 to 1000001 do
+    b[i] := false;
+  readln(n);
+  repeat
+    dec(n);
+    read(a);
+    b[a] := true
+  until n = 0;
+  max := 1;
+  while n < 1000000 do
+    if b[n + 1] and not b[n] then
+      for i := n + 1 to 1000001 do
+        begin
+          if not b[i] then
+            begin
+              if i - n > max then
+                max := i - n;
+              n := i;
+              break
+            end
+        end
+    else
+      inc(n);
+  writeln(max - 1)
+end.
diff --git a/others/volume1/082.pas b/others/volume1/082.pas
new file mode 100644
index 0000000..f195aa7
--- /dev/null
+++ b/others/volume1/082.pas
@@ -0,0 +1,20 @@
+uses clib;
+
+var
+  n: int16;
+  a, g, l: int32;
+
+begin
+  read(n, a);
+  g := a;
+  l := a;
+  while n > 1 do
+    begin
+      dec(n);
+      read(a);
+      g := gcd(g, a);
+      l := l * a div gcd(l, a);
+      writeln(a, ' ', g, ' ', l)
+    end;
+  writeln(g, ' ', l)
+end.
diff --git a/others/volume1/086.scm b/others/volume1/086.scm
new file mode 100644
index 0000000..a45a81d
--- /dev/null
+++ b/others/volume1/086.scm
@@ -0,0 +1,7 @@
+(define (collatz n output)
+  (if (> n 1)
+      (if (= (remainder n 2) 0)
+          (collatz (quotient n 2) (append output '("x 2\n")))
+          (collatz (+ (* n 3) 1) (append output '("div 3\n"))))
+      output))
+(for-each display (reverse (collatz (read) '())))
diff --git a/others/volume1/092.pas b/others/volume1/092.pas
new file mode 100644
index 0000000..246d8cf
--- /dev/null
+++ b/others/volume1/092.pas
@@ -0,0 +1,10 @@
+uses strutils;
+
+var
+  s: ansistring;
+
+begin
+  readln(s);
+  s := delspace1(' ' + s + ' ');
+  writeln(copy(s, 2, length(s) - 2))
+end.
diff --git a/others/volume1/095.pas b/others/volume1/095.pas
new file mode 100644
index 0000000..56300d1
--- /dev/null
+++ b/others/volume1/095.pas
@@ -0,0 +1,11 @@
+uses strutils;
+
+var
+  s: ansistring;
+  i: int32;
+
+begin
+  readln(s);
+  s := ' ' + delspace1(s) + ' ';
+  write(replacetext(copy(s, 2, length(s) - 1), ' ', chr(10)))
+end.
diff --git a/others/volume1/096.pas b/others/volume1/096.pas
new file mode 100644
index 0000000..4cb877c
--- /dev/null
+++ b/others/volume1/096.pas
@@ -0,0 +1,34 @@
+uses math, strutils;
+
+var
+  a, b: ansistring;
+  n: int16;
+  remain: boolean = false;
+  d: uint8;
+
+begin
+  readln(a);
+  readln(b);
+  n := max(length(a), length(b)) + 1;
+  a := addchar('0', a, n);
+  b := addchar('0', b, n);
+  repeat
+    if remain then
+      d := ord(a[n]) + ord(b[n]) - 47
+    else
+      d := ord(a[n]) + ord(b[n]) - 48;
+    if d > 57 then
+      begin
+        dec(d, 10);
+        remain := true
+      end
+    else
+      remain := false;
+    a[n] := chr(d);
+    dec(n)
+  until n = 0;
+  if ord(a[1]) = 48 then
+    writeln(copy(a, 2, length(a) - 1))
+  else
+    writeln(a)
+end.
diff --git a/others/volume1/112.pas b/others/volume1/112.pas
new file mode 100644
index 0000000..0dec65e
--- /dev/null
+++ b/others/volume1/112.pas
@@ -0,0 +1,39 @@
+uses clib;
+
+var
+  a, b: int64;
+  i, j: int32;
+  p: array[2..999983] of boolean;
+  primes: intar;
+
+begin
+  for i := 2 to 999983 do
+    p[i] := true;
+  for i := 2 to 997 do
+    for j := 2 to 999983 div i do
+      p[i * j] := false;
+  j := 0;
+  setlength(primes, 78498);
+  for i := 2 to 999983 do
+    if p[i] then
+      begin
+        primes[j] := i;
+        inc(j)
+      end;
+
+  repeat
+    readln(a, b);
+    a := a * b div sqr(gcd(a, b));
+    b := 0;
+    for i := 0 to bisect_left(primes, trunc(sqrt(a))) do
+      while a mod primes[i] = 0 do
+        begin
+          a := a div primes[i];
+          b := b + 1
+        end;
+    if a = 1 then
+      writeln(b)
+    else
+      writeln(b + 1)
+  until eof(input)
+end.
diff --git a/others/volume1/113.pas b/others/volume1/113.pas
new file mode 100644
index 0000000..64d2af5
--- /dev/null
+++ b/others/volume1/113.pas
@@ -0,0 +1,28 @@
+const
+  cond: array[0..2] of set of char = (
+    ['A', 'H', 'I', 'M', 'O', 'T', 'U', 'V', 'W', 'X', 'Y'],
+    ['B', 'C', 'D', 'E', 'H', 'I', 'K', 'O', 'X'],
+    ['H', 'I', 'N', 'O', 'S', 'X', 'Y']
+  );
+
+var
+  s: ansistring;
+  c: char;
+  b: array[0..2] of boolean;
+  i: int8;
+
+begin
+  readln(s);
+  for i := 0 to 2 do
+    b[i] := true;
+  for c in s do
+    for i := 0 to 2 do
+      b[i] := b[i] and (c in cond[i]);
+  for i := 0 to 2 do
+    if b[i] then
+      write('+')
+    else
+      write('-');
+  writeln
+end.
+end.
diff --git a/others/volume1/clib.pas b/others/volume1/clib.pas
index 101bad3..b9037cd 100644
--- a/others/volume1/clib.pas
+++ b/others/volume1/clib.pas
@@ -125,16 +125,21 @@ interface
       12200160415121876738
     );
 
-  procedure qsort(var a : intar);
   function gcd(x, y: int64): int64;
   function isprime(x: int64): boolean;
   function issquare(x: int64): boolean;
   function ispalindrome(s: ansistring): boolean;
   function all(b: array of boolean): boolean;
+
+  procedure qsort(var a : intar);
   function bsearch(
     a: intar;
     x: int64
   ): int64;
+  function bisect_left(
+    a: intar;
+    x: int64
+  ): int64;
 
 
 implementation
@@ -176,6 +181,7 @@ implementation
     end;
 
 
+  (* Translated from Python 3 math module *)
   function gcd(x, y: int64): int64;
     var z: int64;
     begin
@@ -254,4 +260,28 @@ implementation
       bsearch := -1
     end;
 
+
+  (* Translated from Python 3 bisect module *)
+  function bisect_left(
+    a: intar;
+    x: int64
+  ): int64;
+
+    var
+      l, h, m: int64;
+
+    begin
+      l := 0;
+      h := length(a);
+      while l < h do
+        begin
+          m := (l + h) div 2;
+          if a[m] < x then
+            l := m + 1
+          else
+            h := m
+        end;
+      bisect_left := l
+    end;
+
 end.
-- 
cgit 1.4.1