Add 12/QG-2008/seqgame.cpp

2 files changed, 95 insertions, 0 deletions

diff --git a/12/QG-2008/README.md b/12/QG-2008/README.md
new file mode 100644
index 0000000..4327b5d
--- /dev/null
+++ b/12/QG-2008/README.md
@@ -0,0 +1,36 @@
+# KÌ THI CHỌN HỌC SINH GIỎI QUỐC GIA THPT NĂM 2008
+
+## Trò chơi với dãy số
+
+Hai bạn học sinh trong lúc nhàn rỗi nghĩ ra trò chơi sau đây. Mỗi bạn chọn
+trước một dãy số gồm n số nguyên. Giả sử dãy số mà bạn thứ nhất chọn là:
+b<sub>1</sub>, b<sub>2</sub>, …, b<sub>n</sub>; còn dãy số mà bạn thứ hai chọn
+là: c<sub>1</sub>, c<sub>2</sub>, …, c<sub>n</sub>. Mỗi lượt chơi mỗi bạn đưa
+ra một số hạng trong dãy số của mình. Nếu bạn thứ nhất đưa ra số hạng
+b<sub>i</sub> (1 ≤ i ≤ n), còn bạn thứ hai đưa ra số hạng c<sub>j</sub> (1 ≤ j
+≤ n) thì giá của lượt chơi đó sẽ là |b<sub>i</sub> + c<sub>j</sub>|.
+
+### Yêu cầu
+
+Hãy xác định giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể.
+
+### Dữ liệu
+
+* Dòng đầu tiên chứa số nguyên dương n (n ≤ 10000);
+* Dòng thứ hai chứa dãy số nguyên b<sub>1</sub>, b<sub>2</sub>, …,
+  b<sub>n</sub> (|b<sub>i</sub>| ≤ 10<sup>9</sup>, i = 1, 2, …, n);
+* Dòng thứ ba chứa dãy số nguyên c<sub>1</sub>, c<sub>2</sub>, …,
+  c<sub>n</sub> (|c<sub>i</sub>| ≤ 10<sup>9</sup>, i = 1, 2, …, n);
+* Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách.
+
+### Kết quả
+
+Ghi ra giá nhỏ nhất tìm được.
+
+### Ví dụ
+
+|   SEQGAME.INP    | SEQGAME.OUT |
+| ---------------- | :---------: |
+| 2<br>1 -2<br>2 3 |      0      |
+
+*60% số tests ứng với 60% số điểm của bài có 1 ≤ n ≤ 1000.*
diff --git a/12/QG-2008/seqgame.cpp b/12/QG-2008/seqgame.cpp
new file mode 100644
index 0000000..b1751c7
--- /dev/null
+++ b/12/QG-2008/seqgame.cpp
@@ -0,0 +1,59 @@
+#include <iostream>
+#include <fstream>
+#include <set>
+
+#define ABS(x) ((x < 0) ? -x : x)
+
+using namespace std;
+
+int
+main()
+{
+  ifstream infile;
+  ofstream outfile;
+  short n;
+  long i, c, min = 2e9, a;
+  set<long> b;
+  std::set<long>::iterator k;
+
+  infile.open("SEQGAME.INP");
+  infile >> n;
+  for (i = 0; i < n; i++)
+    {
+      infile >> c;
+      b.insert(c);
+    }
+
+  for (; n--;)
+    {
+      infile >> c;
+      k = b.lower_bound(-c);
+      if (*k == -c)
+        {
+          min = 0;
+          break;
+        }
+
+      if (k != b.end())
+        {
+          i = ABS(*k + c);
+          if (a < min)
+            min = i;
+        }
+
+      if (k != b.begin())
+        {
+          k--;
+          i = ABS(*k + c);
+          if (a < min)
+            min = i;
+        }
+    }
+  infile.close();
+
+  outfile.open("SEQGAME.OUT");
+  outfile << min << endl;
+  outfile.close();
+
+  return 0;
+}