Commit: 4857168a1f0df3cf09be0ebb9e3f40b339e54a2a - VSPRAC (git)

練習用です。いろんなものがごちゃまぜです。

Commit MetaInfo

• Revision: 4857168a1f0df3cf09be0ebb9e3f40b339e54a2a (tree)
• Time: 2017-03-15 19:42:08
• Author: bellyoshi <tccwas@gmai...>
• Commiter: bellyoshi

Log Message

profit

Change Summary

• modified: CPP/ALDS1_1/prime.cpp
• add: CPP/ALDS1_1/profit.cpp

Incremental Difference

--- a/CPP/ALDS1_1/prime.cpp
+++ b/CPP/ALDS1_1/prime.cpp
@@ -1,36 +1,139 @@
 #include <iostream>
 #include <cmath>
+#include <cassert>
+
 using namespace std;
 
-bool isprime(int number){
-  if (number == 1){
-    return false;
-  }
+typedef unsigned int MEMTYPE;
 
-  if (number == 2){
-    return true;
+class mybitset {
+  MEMTYPE *mem;
+  int size;
+  bool ismemfree;
+public:
+  int bitlen(){
+    return sizeof(MEMTYPE) * 8;
+  }
+  mybitset(){
+    ismemfree = true;
+  }
+  void setsize(int size){
+    this->size = size;
+    mem = new MEMTYPE[size / bitlen() + 1];
+    ismemfree = false;
   }
-  if (number % 2 == 0){
-    return false;
+  ~mybitset(){
+    if (!ismemfree){
+      delete [] mem;
+    }
+  }
+  bool get(int pos){
+    MEMTYPE bit = 1 << (pos % bitlen());
+    return (mem[pos / bitlen()] & bit) != 0;
+  };
+  void set(int pos){
+    MEMTYPE bit = 1 << (pos % bitlen());
+    mem[pos / bitlen()] |= bit;
+  };
+  void reset(int pos){
+    MEMTYPE bit = ~(1 << (pos % bitlen()));
+    mem[pos / bitlen()] &= bit;
   }
+};
 
-  for(int i = 3; i < number; i+=2){
-    if(number % i == 0)return false;
+class primer {
+  mybitset isprime;
+  int max;
+public:
+  bool getPrime(int number);
+  primer(int max);
+};
+
+bool primer::getPrime(int number){
+  assert(max > number);
+  if (max > number){
+    return isprime.get(number);
   }
+  //assert(max * max > number);
+  //for(int i = 0; i < max ; i++){
+  //  if (isprime.get(i)){
+  //    if (number % i == 0){
+  //      return false;
+  //    }
+  //  }
+  //}
   return true;
 }
+primer::primer(int max){
+  this->max = max;
+  isprime.setsize(max + 1);
+  //エラトステネスの篩で素数かどうかの判定
+  isprime.reset(0);
+  isprime.reset(1);
+  for(int i = 2; i < max; i++){
+    isprime.set(i);
+  }
+  for(int i = 2; i < sqrt(max); i++){
+    if(isprime.get(i)){
+      for(int j = 2; i * j < max; j++){
+        isprime.reset(i * j);
+      }
+    }
+  }
+}
+
+
+int main(int argc, char const *argv[]) {
+  int count;
+  cin >> count;
+  int prime_count = 0;
+  primer p = primer(100000000);
+  for (int i = 0; i < count; i++) {
+    int number;
+    cin >> number;
+    if (p.getPrime(number)){
+      prime_count++;
+    }
+  }
+  cout << prime_count << endl;
+  return 0;
+}
 
+/* test code
 int main(int argc, char const *argv[]) {
   int count;
   cin >> count;
   int prime_count = 0;
+  primer p = primer(20);
+  mybitset b;
+  b.setsize(100);
+  cout << "b.bitlen() = " << b.bitlen() << endl;
+  for(int i = 0; i < 20; i++){
+    b.set(i);
+    if(!b.get(i)){
+      cout << "set error "<< i << endl;
+    }
+  }
+  for(int i = 0; i < 20; i++){
+    b.reset(i);
+    if(b.get(i)){
+      cout << "reset error"<< i << endl;
+    }
+  }
+  for(int i = 20; i >= 0; i--){
+    b.set(i);
+    if(!b.get(i)){
+      cout << "set error" << i << endl;
+    }
+  }
   for (int i = 0; i < count; i++) {
     int number;
     cin >> number;
-    if (isprime(number)){
+    if (p.getPrime(number)){
       prime_count++;
     }
   }
   cout << prime_count << endl;
   return 0;
 }
+*/

--- /dev/null
+++ b/CPP/ALDS1_1/profit.cpp
@@ -0,0 +1,33 @@
+#include <iostream>
+#include <cassert>
+
+using namespace std;
+
+int main(int argc, char const *argv[]) {
+  int count;
+  cin >> count;
+  int *nums = new int[count];
+  for (int i = 0; i < count; i++) {
+    cin >> nums[i];
+  }
+
+  assert(count >= 2);
+  if (count < 2) {
+    return 1;
+  }
+
+  int maxprofit = nums[1] - nums[0];
+
+  for(int i = 0; i < count - 1; i++){
+    for(int j = i + 1; j < count; j++){
+      int profit = nums[j] - nums[i];
+      if (maxprofit < profit){
+        maxprofit = profit;
+      }
+    }
+  }
+  cout << maxprofit << endl;
+
+  delete [] nums;
+  return 0;
+}