Created
March 5, 2016 01:36
-
-
Save jianminchen/d7370b7e73013ee708be to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* code generated by JHelper | |
* More info: https://github.com/AlexeyDmitriev/JHelper | |
* @author RiaD | |
*/ | |
#include <iostream> | |
#include <iostream> | |
#include <vector> | |
#include <iterator> | |
#include <string> | |
#include <stdexcept> | |
#ifndef SPCPPL_ASSERT | |
#ifdef SPCPPL_DEBUG | |
#define SPCPPL_ASSERT(condition) \ | |
if(!(condition)) { \ | |
throw std::runtime_error(std::string() + #condition + " in line " + std::to_string(__LINE__) + " in " + __PRETTY_FUNCTION__); \ | |
} | |
#else | |
#define SPCPPL_ASSERT(condition) | |
#endif | |
#endif | |
/** | |
* Support decrementing and multi-passing, but not declared bidirectional(or even forward) because | |
* it's reference type is not a reference. | |
* | |
* It doesn't return reference because | |
* 1. Anyway it'll not satisfy requirement [forward.iterators]/6 | |
* If a and b are both dereferenceable, then a == b if and only if *a and | |
* b are bound to the same object. | |
* 2. It'll not work with reverse_iterator that returns operator * of temporary which is temporary for this iterator | |
* | |
* Note, reverse_iterator is not guaranteed to work now too since it works only with bidirectional iterators, | |
* but it's seems to work at least on my implementation. | |
* | |
* It's not really useful anywhere except iterating anyway. | |
*/ | |
template <typename T> | |
class IntegerIterator: public std::iterator<std::input_iterator_tag, T, std::ptrdiff_t, T*, T> { | |
public: | |
explicit IntegerIterator(int value): value(value) { | |
} | |
IntegerIterator& operator++() { | |
++value; | |
return *this; | |
} | |
IntegerIterator operator++(int) { | |
IntegerIterator copy = *this; | |
++value; | |
return copy; | |
} | |
IntegerIterator& operator--() { | |
--value; | |
return *this; | |
} | |
IntegerIterator operator--(int) { | |
IntegerIterator copy = *this; | |
--value; | |
return copy; | |
} | |
T operator*() const { | |
return value; | |
} | |
bool operator==(IntegerIterator rhs) { | |
return value == rhs.value; | |
} | |
bool operator!=(IntegerIterator rhs) { | |
return !(*this == rhs); | |
} | |
private: | |
T value; | |
}; | |
template <typename T> | |
class IntegerRange { | |
public: | |
IntegerRange(T begin, T end): begin_(begin), end_(end) { | |
SPCPPL_ASSERT(begin <= end); | |
} | |
IntegerIterator<T> begin() const { | |
return IntegerIterator<T>(begin_); | |
} | |
IntegerIterator<T> end() const { | |
return IntegerIterator<T>(end_); | |
} | |
private: | |
T begin_; | |
T end_; | |
}; | |
template <typename T> | |
class ReversedIntegerRange { | |
typedef std::reverse_iterator<IntegerIterator<T>> IteratorType; | |
public: | |
ReversedIntegerRange(T begin, T end): begin_(begin), end_(end) { | |
SPCPPL_ASSERT(begin >= end); | |
} | |
IteratorType begin() const { | |
return IteratorType(IntegerIterator<T>(begin_)); | |
} | |
IteratorType end() const { | |
return IteratorType(IntegerIterator<T>(end_)); | |
} | |
private: | |
T begin_; | |
T end_; | |
}; | |
template <typename T> | |
IntegerRange<T> range(T to) { | |
return IntegerRange<T>(0, to); | |
} | |
template <typename T> | |
IntegerRange<T> range(T from, T to) { | |
return IntegerRange<T>(from, to); | |
} | |
template <typename T> | |
IntegerRange<T> inclusiveRange(T to) { | |
return IntegerRange<T>(0, to + 1); | |
} | |
template <typename T> | |
IntegerRange<T> inclusiveRange(T from, T to) { | |
return IntegerRange<T>(from, to + 1); | |
} | |
template <typename T> | |
ReversedIntegerRange<T> downrange(T from) { | |
return ReversedIntegerRange<T>(from, 0); | |
} | |
template <typename T> | |
ReversedIntegerRange<T> downrange(T from, T to) { | |
return ReversedIntegerRange<T>(from, to); | |
} | |
template <typename T> | |
ReversedIntegerRange<T> inclusiveDownrange(T from) { | |
return ReversedIntegerRange<T>(from + 1, 0); | |
} | |
template <typename T> | |
ReversedIntegerRange<T> inclusiveDownrange(T from, T to) { | |
return ReversedIntegerRange<T>(from + 1, to); | |
} | |
using namespace std; | |
class BearAndSteadyGene { | |
public: | |
void solve(std::istream& in, std::ostream& out) { | |
int n; | |
in >> n; | |
string s; | |
in >> s; | |
int mx = n / 4; | |
vector<int> cnt(256); | |
for (char c: s) { | |
cnt[c]++; | |
} | |
string t = "ACGT"; | |
bool ok = true; | |
for (char c: t) { | |
if (cnt[c] > mx) { | |
ok = false; | |
} | |
} | |
if (ok) { | |
out << 0; | |
return; | |
} | |
int r = 0; | |
int ans = n; | |
for (int l: range(n)) { | |
while (cnt['A'] > mx || cnt['C'] > mx || cnt['T'] > mx || cnt['G'] > mx) { | |
if (r == n) { | |
out << ans; | |
return; | |
} | |
--cnt[s[r]]; | |
++r; | |
} | |
ans = min(ans, r - l); | |
++cnt[s[l]]; | |
} | |
out << ans << "\n"; | |
} | |
}; | |
int main() { | |
std::ios_base::sync_with_stdio(false); | |
BearAndSteadyGene solver; | |
std::istream& in(std::cin); | |
std::ostream& out(std::cout); | |
in.tie(0); | |
out << std::fixed; | |
out.precision(20); | |
solver.solve(in, out); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment