akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0, i##_len = (int)(n); i < i##_len; i++)
#define reps(i, n) for (int i = 1, i##_len = (int)(n); i <= i##_len; i++)

using Node = pair<int, bool>; // 親ノード番号(1始まり,0は親なし), 探索済みフラグ
using NodeList = vector<Node>;

int rootIndex(int index, NodeList &nodes) { // 根のノード番号を探す
    if (nodes[index].first == 0) // 親がない場合はこれが根
        return index;
    else {
        auto root = rootIndex(nodes[index].first, nodes); // 親がある場合はさらに探索
        nodes[index].first = root; // 親をつなぎ替え
        return root;
    }
}

bool isNewTree(int index, NodeList &nodes) {
    if (nodes[index].second) { // このノード自身が探索済みの場合
        return false;
    } else { // 未探索ノードの場合
        nodes[index].second = true; // 探索済みにする
        auto parent = nodes[index].first;
        if (parent == 0) { // 根の場合は新しい木
            return true;
        } else {
            return isNewTree(parent, nodes); // 根でなければさらに親を探索
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    NodeList nodes(n + 1, make_pair(0, false));
    rep(i, m) {
        int x, y, z;
        cin >> x >> y >> z;
        auto rx = rootIndex(x, nodes);
        auto ry = rootIndex(y, nodes);
        if (rx != ry) { // 根ノードが異なる場合
            nodes[rx].first = y; // xの木の根を y の子に挿して tree を unite
        }
    }
    int ans = 0;
    reps(i, n) {
        if (isNewTree(i, nodes)) ans++; // 新しい木を発見するたびにカウント
    }
    cout << ans << endl;
}


Measured memory_bytes: 1024
c = input()
alph = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
for i in range(len(alph)-1):
  if c == alph[i]:
    print(alph[i+1])

Measured memory_bytes: 3060
#![allow(non_snake_case)]
#![allow(unused_variables)]
#![allow(dead_code)]

fn main() {
    let N: usize = {
        let mut line: String = String::new();
        std::io::stdin().read_line(&mut line).unwrap();
        line.trim().parse().unwrap()
    };
    let p: Vec<i64> = (0..N)
        .map(|_| {
                let mut line: String = String::new();
                std::io::stdin().read_line(&mut line).unwrap();
                line.trim().parse().unwrap()
        })
        .collect();

    let ans = p.iter().sum::<i64>() - p.iter().max().unwrap() / 2;

    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int MOD=1e9+7;
int pw(int n,int k){
  assert(k>=0);
  int res=1;
  while(k){
    if(k&1)(res*=n)%=MOD;
    (n*=n)%=MOD;
    k>>=1;
  }
  return res;
}
std::vector<int> Factorial(5e6),Finverse(5e6);
void Cinit(){// limit is 5e6 /// write pw /// this takes 792ms at AtCoder
  Factorial[0]=1;
  for(int i=1;i<5e6;i++)Factorial[i]=(Factorial[i-1]*i)%MOD;
  for(int i=0;i<5e6;i++)Finverse[i]=pw(Factorial[i],MOD-2);
}
int nCk(int n,int k){
  if(n<k)return 0;if(k<0)return 0;
  if(!Factorial[0])Cinit();
  int res=Factorial[n];
  (res*=Finverse[k])%=MOD;
  (res*=Finverse[n-k])%=MOD;
  return res;
}
int nPk(int n,int k){
  if(n<k)return 0;if(k<0)return 0;
  if(!Factorial[0])Cinit();
  int res=Factorial[n];
  (res*=Finverse[n-k])%=MOD;
  return res;
}

signed main(){
  int n,m;cin>>n>>m;
  Cinit();
  int ans=0;
  for(int k=0;k<=n;k++)(ans+=(k&1?-1:1)*nCk(n,k)*nPk(m-k,n-k))%=MOD;
  (ans*=nPk(m,n))%=MOD;
  if(ans<0)ans+=MOD;
  cout<<ans<<endl;
}


Measured memory_bytes: 81128
c = [1.1,0.6,0.2,0.0]
r = [0,0,0,0,0,0,0,0]
while 1:
    try:
        e = map(float, raw_input().split())
        for i in range(2):
            for j in range(4):
                if e[i] >= c[j]:
                	r[i+2*j] += 1
                	break
    except:
        break
for i in range(0,8,2):
	print r[i],r[i+1]

Measured memory_bytes: 4240
#include <bits/stdc++.h>
using ll = long long;
#define FOR(i, k, n) for(ll i = (k); i < (n); i++)
#define FORe(i, k, n) for(ll i = (k); i <= (n); i++)
#define FORr(i, k, n) for(ll i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(ll i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;

const int INF = 1001001001;

int main(void){
  string s;
  cin >> s;
  s[5] = ' ';
  s[13] = ' ';
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
# define ll int64_t
# define rep(i,n) for(ll i=0;i<n;i++)
# define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define mod 1000000007
# define PI 3.141592653589793
# define vec vector
#define dump(x) cerr<<#x<<"="<<x<<endl
using namespace std;

bool compare_by_b(pair<string,ll> a,pair<string,ll> b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

bool my_compare(pair<string,ll> a,pair<string,ll> b){
    if(a.first != b.first) return a.first<b.first;
    if(a.second != b.second) return a.second>b.second;
    else return true;
}

ll factorial(ll n){
    ll x=1;
    rrep(i,n) (x*=i)%=mod;
    return x;
}

ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b,a%b));
}

ll lcm(ll a,ll b){
   return a/gcd(a,b)*b;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string s;
    ll sum=0;
    cin>>s;
    if(s.size()==1){
        cout<<(ll)(s[0]-'0')<<endl;
        return 0;
    }
    for(ll i=1;i<s.size();i++){
        if(s[i]!='9'){
            sum += (ll)(s[0]-'0'-1);
            for(ll j=1;j<s.size();j++) sum += 9;
            cout<<sum<<endl;
            return 0;
        }
    }
    rep(i,s.size()) sum+=(ll)(s[i]-'0');
    cout<<sum<<endl;
    
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
using namespace std;
using Int = long long;
int main()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << min(a, b) + min(c, d);
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"

#define rep(i, a) for (int i = 0; i < (a); ++i)
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define FORV(a, A) for (auto &a : A)

using namespace std;
using ll = long long;
using P = pair<int, int>;
const ll INF = 1e14;

void Main() {
  int n, r;
  cin >> n >> r;
  if (n < 10) {
    r += 100 * (10 - n);
  }
  cout << r << endl;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int
main(int argc, char *argv[])
{
        int n;
        cin >> n;
        int data[n];
        int i=0;
        while(i<n){
            cin >> data[i];
            i++;
        }

        int counter;
        int answer=1;
        int tmp=data[0];
        for(int x=1;x<n;x++){
            if(data[x-1]<=data[x]&&tmp<=data[x]){
                tmp=data[x];
                answer++;
            }
        }

        cout << answer << endl;

        return 0;
}

Measured memory_bytes: 888
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(), (x).end()
#define dbg(x) cerr << #x << ": " << x << endl

const int MAXX = 100005;
int main() {
  int x;
  cin >> x;
  vector<bool> dp(MAXX);
  dp[0] = true;
  vector<int> item = {100, 101, 102, 103, 104, 105};
  rep(i, MAXX) {
    rep(j, item.size()) {
      if(i - item[j] < 0) continue;
      if(dp[i - item[j]]) dp[i] = true;
    }
  }
  if(dp[x])
    cout << 1 << endl;
  else
    cout << 0 << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
const ll INF = 1LL<<60;
const ll MOD = 1e9+7;


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n; cin>>n;
    vector<vector<int>> xy(n,vector<int>(n,-1));
    rep(i,n){
        int a;cin>>a;
        rep(j,a){
            int x,y;cin>>x>>y;
            xy[i][x-1]=y;
        }
    }
    int ans = 0;
    for(int i=0; i<(1<<n); i++){
        bool flag = true;
        int m = 0;
        for(int j=0; j<n&&flag; j++){
            int sho = (i>>j)&1;
            m+=sho;
            if(!sho)continue;
            for(int k=0; k<n; k++){
                if(xy[j][k]==-1)continue;
                if(xy[j][k]!=(i>>k&1)){flag=false;break;}
            }
        }
        if(flag)ans=max(m,ans);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>

int main(){
  int a,b; std::cin >> a >> b;
  std::string winner;
  
  if (a == b) {
    winner = "Draw";
  } else if ( (a == 1) || (b == 1) ) {
    winner = ( (a < b)? "Alice" : "Bob" );
  } else {
    winner = ( (a < b)? "Bob" : "Alice" );
  }
  
  printf("%s\n", winner.c_str());
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> // {{{
// clang-format off
#define ARG4(_1, _2, _3, _4, ...) _4
#define rep(...) ARG4(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define REP(i, a) FOR(i, 0, a)
#define FOR(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define rrep(...) ARG4(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define RREP(i, a) RFOR(i, 0, a)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (int)(a); --i)
#define ALL(c) (c).begin(), (c).end()
#define pb emplace_back
#define em emplace
#define fi first
#define se second
#define USE1(...) template <typename __VA_ARGS__> inline
#define USE2(T, ...) USE1(T, typename __VA_ARGS__)
#define mygc(c) (c) = getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
 
using ll = long long;
template<typename T> using vec = std::vector<T>;
USE2(T,U)bool chmax(T&x,U a){return x<a&&(x=a,1);}
USE2(T,U)bool chmin(T&x,U a){return a<x&&(x=a,1);}
USE1(T=int)T in(){T x;std::cin>>x;return x;}
USE2(T=int,V=vec<T>)V reserved(int n){V v;v.reserve(n);return v;}
USE1(T=int)vec<T>in(int n){auto v=reserved<T>(n);rep(i,n)v.pb(in<T>());return v;}
USE2(T,U=std::pair<T,int>)vec<U>enume(const vec<T>&x,int s=0){int N=x.size();auto v=reserved<U>(N);rep(i,N)v.pb(x[i],s+i);return v;}
USE1(T)vec<T>ndvec(T v,int n){return vec<T>(n,v);}
USE2(T,...Ts)auto ndvec(T v,int n,Ts...ns)->vec<decltype(ndvec(v,ns...))>{return ndvec(ndvec(v,ns...),n);}
USE1(T)void pr(T x){std::cout<<x<<'\n';}
USE2(T,...Ts)void pr(T x,Ts...xs){std::cout<<x<<' ';pr(xs...);}
USE1(T=int)T rd(){T x=0,m=0,k;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||'9'<k)break;x=x*10+k-'0';}return x;}
USE1(T=int)void wr(T x,char c='\n'){int s=0,m=0;char b[32];if(x<0)m=1,x=-x;for(;x;x/=10)b[s++]=x%10;if(!s)b[s++]=0;if(m)mypc('-');for(;s--;)mypc(b[s]+'0');mypc(c);}
// clang-format on
// }}}
struct IoSetup { // {{{
  IoSetup() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.precision(10);
    std::cerr.precision(10);
  }
} iosetup; //}}}
using namespace std;
const int inf = 1001001001;
const ll infl = 1001001001001001001ll;
const int dd[] = {0, 1, 0, -1, 0};

signed main() {
  const int M = 1000000;
  vec<int> tet;
  rep(i, 1, 1000) {
    int x = i * (i + 1) * (i + 2) / 6;
    if (x >= M) break;
    tet.pb(x);
  }
  vec<int> dp(2 * M, inf), dpo(2 * M, inf);
  dp[0] = dpo[0] = 0;
  REP(i, M) {
    for (int x : tet) {
      chmin(dp[i + x], dp[i] + 1);
      if (x % 2) chmin(dpo[i + x], dpo[i] + 1);
    }
  }
  int N;
  while (N = in(), N) {
    pr(dp[N], dpo[N]);
  }

  return 0;
}

Measured memory_bytes: 18220
#include<bits/stdc++.h>

using namespace std;

int main(void){
    long long x;
    cin >> x;
    long long a = 100;
    long long i;
    for(i = 0; a < x; i++){
        a += (double)a * 0.01;
    }
    cout << i << endl;
}

Measured memory_bytes: 3636
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#include<stack>
#include<cstring>
#include<string>
#include<map>
using namespace std;
int main(){
	int a,b,c,sum,Max;
	cin >> a >> b >> c;
	sum = a + b + c;
	Max = max(a,max(b,c));
	if(sum == Max*2)puts("Yes");
	else puts("No");
	return 0;
	}

Measured memory_bytes: 256
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;

namespace PastQuestions
{
    class Program
    {
        static void Main(string[] args)
        {
            new Program().Solve(new Input(Console.In));
        }

        public void Solve(Input input)
        {
            var a_500 = input.ReadInt;
            var b_100 = input.ReadInt;
            var c_50 = input.ReadInt;
            var total = input.ReadInt;

            var count = 0;
            for (var a = 0; a <= a_500; ++a)
            {
                for (var b = 0; b <= b_100; ++b)
                {
                    for (var c = 0; c <= c_50; ++c)
                    {
                        if (total == 50 * c + 100 * b + 500 * a)
                        {
                            count++;
                        }
                    }
                }
            }

            Console.WriteLine(count);
        }
    }

    public class Input
    {
        private TextReader Stream { get; }
        private char Separator { get; }
        private Queue<string> InputStream { get; }

        public Input(TextReader stream, char separator = ' ')
        {
            Stream = stream;
            Separator = separator;
            InputStream = new Queue<string>();
        }

        public string Read
        {
            get
            {
                if (InputStream.Count != 0) return InputStream.Dequeue();
                string[] tmp = Stream.ReadLine().Split(Separator);
                for (int i = 0; i < tmp.Length; ++i)
                    InputStream.Enqueue(tmp[i]);
                return InputStream.Dequeue();
            }
        }

        public string ReadLine => Stream.ReadLine();
        public int ReadInt => int.Parse(Read);
        public long ReadLong => long.Parse(Read);
        public double ReadDouble => double.Parse(Read);
        public long[] ReadLongArray => Stream.ReadLine().Split(Separator).Select(l => long.Parse(l)).ToArray();
    }
}


Measured memory_bytes: 13268
#include<stdio.h>
main()
{ 
  int A,B;
  scanf("%d",&A);
  scanf("%d",&B);
  
  if((A==1&&B==2)||(A==2&&B==1))
    printf("%d",3);
  if((A==2&&B==3)||(A==3&&B==2))
    printf("%d",1);
  if((A==1&&B==3)||(A==3&&B==1))
    printf("%d",2);
 }


Measured memory_bytes: 128
#include<bits/stdc++.h>
using lint=long long;
void cmx(lint&x,lint y){if(x<y)x=y;}
int main(){
    std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);
    std::cout.setf(std::ios_base::fixed);std::cout.precision(15);
    lint n;std::cin>>n;
    std::vector<lint>a(n);
    for(lint&x:a)std::cin>>x;
    std::sort(a.begin(),a.end());
    std::vector<lint>two,four;
    for(lint i=0,j=1;j<=n;j++){
        if(j==n||a.at(j-1)!=a.at(j)){
            if(2<=j-i)two.push_back(a.at(j-1));
            if(4<=j-i)four.push_back(a.at(j-1));
            i=j;
        }
    }
    std::sort(two.begin(),two.end(),std::greater<>{});
    std::sort(four.begin(),four.end(),std::greater<>{});
    lint ans=0;
    if(2u<=two.size())ans=two.at(0)*two.at(1);
    if(!four.empty())cmx(ans,four.front()*four.front());
    std::cout<<ans<<'\n';
}


Measured memory_bytes: 1660
#include <bits/stdc++.h>
#define rep(i,n) for (long long i = 0; i < (n); ++i)
const int INF = 2147483647;//int max
const long long int MOD = 1000000007;
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

int main() {
    vector<int> v(4,0);
    rep(i,4)cin >> v[i];
    sort(v.begin(),v.end());
    if(v[0] == 1 && v[1] == 4 && v[2] == 7 && v[3] == 9)cout << "YES\n";
    else cout << "NO\n";
    return 0;
}
/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#define N 10000
int main(){
  int i,j,n,count;
  int kazu;

  scanf("%d",&n);
  count = n;

  for(i=0;i<n;i++){
    scanf("%d",&kazu);
    if(kazu == 2){
      continue;
    }
    else if(kazu%2==0){
      count--;
      continue;
    }
    for(j=3;j<=sqrt(kazu);j+=2){
      if(kazu%j==0){
	count--;
	break;
      }
    }
  }

  printf("%d\n",count);

  return 0;
}



Measured memory_bytes: 2140
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {

	int D;
	cin >> D;
	int N = 26;
	vector<int> C(N,0); // C[i]
	vector<vector<int> > S(D,vector<int>(N,0)); // S[d][i]
	for (int i = 0; i < N; i++) {
		cin >> C[i];
	}
	for (int d = 0; d < D; d++) {
		for (int i = 0; i < N; i++) {
			cin >> S[d][i];
		}
	}
	random_device seed_gen;
	mt19937 engine(seed_gen());
	uniform_real_distribution<> dist1(0.0, 1.0);
	for (int d = 0; d < D; d++) {
		cout << int(dist1(engine) * 26) + 1 << endl;
	}

	return(0);
}


Measured memory_bytes: 3688
#include<bits/stdc++.h>
using namespace std;

int main(void)
{
  int k;
  cin >> k;
  int a, b;
  cin >> a >> b;
  if(a % k == 0 || b % k ==0){
  cout << "OK" << endl;
  }
  else if((a / k + 1) * k > b)
  {
    cout << "NG" << endl;
  }else{
    cout << "OK" << endl;
  }
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;

int main(){
	int a[9];
  	for(int i =0; i<9;i++) {
    	cin >> a[i];
    }
  	int t = a[0] -a[1],s=a[1]-a[2];
  	int c = a[0] - a[3],d = a[3] - a[6];
  	if(t==a[3]-a[4] && s == a[4]-a[5] && t==a[6]-a[7] && s == a[7] -a[8])
      	if(c == a[1] - a[4] && d == a[4] - a[7] && c == a[2] - a[5] && d == a[5] - a[8]) {
			cout<<"Yes\n";
          	return 0;
        }
  	cout << "No\n";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ull unsigned long long
#define lowbit(x) ((x)&(-x))
#define dis(p,q) sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y))

#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
typedef double db;
using namespace std;

namespace _{
    bool rEOF = 1;//为0表示文件结尾
    inline char nc(){
        static char buf[100000], *p1 = buf, *p2 = buf;
        return p1 == p2&&rEOF && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? (rEOF = 0, EOF) : *p1++;
    }
    template<class _T>
    inline bool read(_T &num){
        char c = nc(), f = 1; num = 0;
        while (c<'0' || c>'9')c == '-' && (f = -1), c = nc();
        while (c >= '0'&&c <= '9')num = num * 10 + c - '0', c = nc();
        return (bool)(num *= f);
    }
    inline bool need(char &c){ return c >= 'a'&&c <= 'z' || c >= 'A'&&c <= 'Z'; }//读入的字符范围
    inline bool read_str(char *a){
        while ((*a = nc()) && need(*a) && rEOF)++a;
        *a = '\0'; return rEOF;
    }
}using namespace _;

int main()
{
    ll r,d,x;
    scanf("%lld%lld%lld",&r,&d,&x);
    for(int i=1;i<=10;i++)
    {
        x=r*x-d;
        printf("%lld\n",x);
    }
    return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
s = list(map(str, input().split()))
t = list(map(str, input().split()))
MOD = 10**9 + 7

def count_cs(str1, str2, MOD):
    '''
    計算量O(len(str1)*len(str2))
    '''
    dp = [[0]*(len(str2) + 1) for _ in range(len(str1) + 1)]
    for i in range(len(str1)):
        for j in range(len(str2)):
            if str1[i] == str2[j]:
                dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] + 1
            else:
                dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j]
            dp[i+1][j+1] %= MOD
    return (dp[len(str1)][len(str2)] + 1) % MOD

print(count_cs(s, t, MOD))

Measured memory_bytes: 72412
#include "bits/stdc++.h"
using namespace std;

int main() {
	long long N, ANS = 0;
	vector<long long> P;
	cin >> N;
	P.resize(N);
	for (int i = 0; i < N; i++) cin >> P[i];
	for (int i = 0; i < N - 2; i++) {
		if (P[i] < P[i + 1] && P[i + 1] < P[i + 2]) ANS++;
		else if (P[i] > P[i + 1] && P[i + 1] > P[i + 2]) ANS++;
	}
	cout << ANS << endl;
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace ConsoleApp
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = Console.ReadLine().Split().Select(int.Parse).ToArray();
            var N = input[0];
            var K = input[1];
            var H = Console.ReadLine().Split().Select(long.Parse).ToArray();

            Console.WriteLine(N <= K ? 0 : H.OrderBy(i => i).Take(N - K).Sum());
        }
    }
}

Measured memory_bytes: 40196
#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1000000000

using namespace std;
typedef pair<llint, llint> P;

string s;
llint t;
vector<P> vec;

int main(void)
{
  while(1){
    cin >> t >> s;
    if(s=="0" && t==0) break;
    reverse(s.begin(), s.end());
    vec.clear();

    llint n = s.size(), N = 1<<(n-1);
    for(int i = 0; i < N; i++){
      llint sum = 0, mul = 1;
      for(int j = 0; j < n; j++){
        sum += mul*(s[j]-'0');
        mul *= 10;
        if(j < n-1 && (i & (1<<j))) mul = 1;
      }
      vec.push_back(P(sum, i));
    }
    sort(vec.begin(), vec.end());

    /*for(int i = 0; i < vec.size(); i++){
      cout << vec[i].first << " " << vec[i].second << endl;
    }*/

    llint p = upper_bound(vec.begin(), vec.end(), P(t, inf)) - vec.begin();
    p--;
    if(p < 0){
      cout << "error" << endl;
      continue;
    }
    if(p > 0 && vec[p-1].first == vec[p].first){
      cout << "rejected" << endl;
      continue;
    }
    cout << vec[p].first << " ";

    llint cut = vec[p].second, sum = 0, mul = 1;
    vector<llint> ans;
    for(int j = 0; j < n; j++){
      sum += mul*(s[j]-'0');
      mul *= 10;
      if(j < n-1 && (cut & (1<<j))){
        mul = 1;
        ans.push_back(sum);
        sum = 0;
      }
    }
    ans.push_back(sum);

    reverse(ans.begin(), ans.end());
    for(int i = 0; i < ans.size(); i++){
      cout << ans[i];
      if(i < (int)ans.size()-1) cout << " ";
    }
    cout << endl;
  }

  return 0;
}



Measured memory_bytes: 3176
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

signed main(){
	int n;
	while(cin >> n,n){
		int a[65000],b[65000],sum = 0,ma = 0;
		for(int i = 0;i < n;i++) {
			cin >> a[i];
			sum += a[i];
		}
		for(int i = 0;i < n - 1;i++) cin >> b[i];
		sort(b,b + n - 1,greater<int>());
		for(int i = 0;i < n;i++){
			ma = max(ma,sum * (n - i));
			if(i != n - 1) sum += b[i];
		}
		cout << ma << endl;
	}
	return 0;
}

Measured memory_bytes: 4116
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

struct edge
{
    int to;
    int cap;
    int rev;
};
vector<vector<edge>> graph;
vector<bool> check;

void add_edge(int from, int to, int cap)
{
    graph[from].push_back((edge){to, cap, (int)graph[to].size()});
    graph[to].push_back((edge){from, 0, (int)graph[from].size() - 1});
}

int dfs(int from, int to, int flow)
{
    if (from == to)
    {
        return flow;
    }
    check[from] = 1;
    
    for (int i = 0; i < graph[from].size(); ++i)
    {
        edge& e = graph[from][i];
        if (e.cap > 0 && check[e.to] == 0)
        {
            int nflow = min(flow, e.cap);
            int ret = dfs(e.to, to, nflow);
            if (ret > 0)
            {
                e.cap -= ret;
                graph[e.to][e.rev].cap += ret;
                return ret;
            }
        }
    }
    return 0;
}

int main() {
    int n;
    cin >> n;
    
    graph = vector<vector<edge>>(2 * n + 2, vector<edge>());
    
    vector<pair<int, int>> r;
    vector<pair<int, int>> b;
    
    int from = 0;
    int to = 2 * n + 1;
    
    for (int i = 0; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;
        r.push_back(make_pair(a, b));
        add_edge(from, 1 + i, 1);
    }
    for (int i = 0; i < n; ++i)
    {
        int c, d;
        cin >> c >> d;
        b.push_back(make_pair(c, d));
        add_edge(n + 1 + i, to, 1);
    }
    
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (r[i].first < b[j].first && r[i].second < b[j].second)
            {
                add_edge(1 + i, n + 1 + j, 1);
            }
        }
    }
    
    int ret = 0;
    
    while (1)
    {
        check = vector<bool>(2 * n + 2, 0);
        int flow = dfs(from, to, n);
        if (flow > 0)
        {
            ret += flow;
        }
        else
        {
            break;
        }
    }
    
    cout << ret << endl;
    
    
    return 0;
}


Measured memory_bytes: 384
#include <stdio.h>

int main(void){

    int x,y;
    scanf("%d %d",&x,&y);

    while(x != 0 || y !=0){
    if( x < y ){
      printf("%d %d\n",x ,y);
    } else {
      printf("%d %d\n",y ,x);
    }
    scanf("%d %d",&x,&y);
}
    return 0;
}

Measured memory_bytes: 600
#include <iostream>
using namespace std;
#include <algorithm>

#define INT int
#define REP(i,a,b) for(INT i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int main(){
int a,b,c;
cin >> a >> b >> c;
if(a+b >= c) cout<< "Yes" <<endl;
else cout << "No"<<endl;

return 0;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
const ll mod=1e9+7;
const int inf=1<<30;

int main(){
  ll n; cin >> n;
  ll ans=(n/500)*1000;
  n%=500;
  ans+=(n/5)*5;
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>

typedef long long LL;
const int Mod = 1000000007;
const int MN = 200005, MM = 200005;

int N, M, K;
char S[MM];
int A[MN], B[MN], Ans;

int main() {
	scanf("%d%d%s", &N, &M, S + 1);
	K = 0x3f3f3f3f;
	int isfirst = 1, len = 0;
	for (int i = 1; i <= M; ++i) {
		if (S[i] != S[1]) {
			if (isfirst || len & 1) K = std::min(K, len / 2 + 1);
			isfirst = len = 0;
		} else ++len;
	}
	if (isfirst) {
		int X1 = 1, X2 = 0;
		for (int i = 1; i <= N; ++i) {
			X2 -= (X2 = X1 + X2) >= Mod ? Mod : 0;
			X1 += (X1 = X2 - X1) < 0 ? Mod : 0;
		}
		printf("%lld\n", (2ll * X1 + X2) % Mod);
		return 0;
	}
	if (N & 1) return puts("0"), 0;
	N /= 2;
	K = std::min(K, N);
	A[0] = B[0] = 1;
	for (int i = 1; i <= N; ++i) {
		A[i] = B[i - 1];
		if (i > K) A[i] += (A[i] -= B[i - K - 1]) < 0 ? Mod : 0;
		B[i] -= (B[i] = B[i - 1] + A[i]) >= Mod ? Mod : 0;
	}
	for (int i = 1; i <= K; ++i)
		Ans = (Ans + 2ll * i * A[N - i]) % Mod;
	printf("%d\n", Ans);
	return 0;
}

Measured memory_bytes: 1152
#include <iostream>

using namespace std;

int main() {
	int N;
	cin >> N;
	bool ok = false;
	for (int i = 0; i <= N; i++) {
		if (N-4*i < 0)
			break;
		if ((N-4*i)%7==0) {
			cout << "Yes";
			return 0;
		}
	}
	cout << "No";

}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#include<map>
#include <bits/stdc++.h>
using namespace std;


int main(){
    long long int a;
    float  b;
    long long int bb;
    long long int ans;
    cin >> a >> b;
    if(a == 0 || b == 0){
        cout << 0 << endl;
        return 0;
    }
    bb = (long long int)(b*100); 
    //cout << bb << " " << b << endl;
    ans = (long long int)a*bb;
    cout << (long long int)(ans/100) << setprecision(18);
    cout << endl;
    
    
    return 0;

}

Measured memory_bytes: 3700
#include<stdio.h>
#include<stdlib.h>

typedef struct box{
	int par;//親の接点番号
	int left;//子（左）
	int right;//子（右）
} Node;

void preorder(Node *node)
{
	
}

int depthsearch(Node *node,int point)//深さを返す
{
	int i,cnt=0,current = point;
	while(node[current].par!=-1){
		current=node[current].par;
		cnt++;
	}
	
	return cnt;
}

int heightsearch(Node *node,int point)//高さを返す
{
	int l=0,r=0;
	if(node[point].right!=-1) r=heightsearch(node,node[point].right)+1;
	if(node[point].left!=-1) l=heightsearch(node,node[point].left)+1;
	
	if(r>l) return r;
	else return l;
}

int siblingsearch(Node *node,int point)//兄弟番号を返す
{
	int box;
	box=node[point].par;
	if(box==-1) return -1;
	if(node[box].left==point) return node[box].right;
	else return node[box].left;
}

int degreesearch(Node *node,int point)//子の個数を返す
{
	int cnt=0;
	if(node[point].left!=-1) cnt++;
	if(node[point].right!=-1) cnt++;
	
	return cnt;
}


int main(void)
{
	int i,j,n;
	int box,s;
	Node *node;
	
	scanf("%d",&n);
	node=(Node*)malloc(sizeof(Node)*n);
	for(i=0;i<n;i++) node[i].par=-1;//親の節点番号を初期化
	for(i=0;i<n;i++){
		scanf("%d",&box);
		scanf("%d",&node[box].left);
		node[node[box].left].par=box;
		scanf("%d",&node[box].right);
		node[node[box].right].par=box;
	}
	
	
	
	for(i=0;i<n;i++){
		printf("node %d: parent = %d, ",i,node[i].par);
		printf("sibling = %d, degree = %d, ",siblingsearch(node,i),degreesearch(node,i));
		printf("depth = %d, height = %d, ",depthsearch(node,i),heightsearch(node,i));
		if(node[i].par==-1) printf("root");
		else if(node[i].left==-1&&node[i].right==-1) printf("leaf");
		else printf("internal node");
		printf("\n");
	}
	
	free(node);
	
	return 0;
}


Measured memory_bytes: 2092
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef long double ld;
const double pi=acos(-1.0);
const ll mod=pow(10,9)+7;
const ll INF=pow(2,31)-1;
using str=string;
typedef pair<int,int> P;
typedef vector<int> vi;

ll gcd(ll a,ll b){
    ll v0=a,v1=b,v2=a%b;
    while(v2!=0){
        v0=v1;
        v1=v2;
        v2=v0%v1;
    }
    return v1;
}

ll lcm(ll a,ll b){
    return (a*b/gcd(a,b));
}

int main(){
    ios::sync_with_stdio(false);
    str s;
    cin >>s;
    if(s=="AAA"||s=="BBB") cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

#define REP(i, n) for (int i=0; i<(n); ++i)
#define RREP(i, n) for (int i=(int)(n)-1; i>=0; --i)
#define FOR(i, a, n) for (int i=(a); i<(n); ++i)
#define RFOR(i, a, n) for (int i=(int)(n)-1; i>=(a); --i)

#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()

#define dump(x) cerr<<#x<<" = "<<(x)<<endl
#define debug(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl;

template<class T>
ostream &operator<<(ostream &os, const vector <T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}

template<class T, class U>
ostream &operator<<(ostream &os, const pair <T, U> &p) {
    return os << "(" << p.first << " " << p.second << ")";
}

template<class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;

const ll MOD = 1e9 + 7;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
const ld eps = 1e-6;


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    int S, W; cin >> S >> W;

    cout << (W >= S ? "unsafe" : "safe") << endl;

    return 0;
}


Measured memory_bytes: 3656
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << endl;
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REVFOR(i, m, n) for (int i = (n - 1); i >= (m); --i)
#define REP(i, n) FOR(i, 0, n)
#define REVREP(i, n) REVFOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

template<typename T>
struct BIT {
    int N;
    vector<T> dat;

    // 0-indexing
    explicit BIT(int n): N(n), dat(N + 1, 0) {}

    T sum(int i) {
        T s = T();
        for(++i; i > 0; i -= i & -i) s += dat[i];
        return s;
    }

    void add(int i, const T& x) {
        for (++i; i <= N; i += i & -i) dat[i] += x;
    }

    // min_x {x | v1 + v2 + ⋯ + vx ≧ w}
    // Assuming v_q >= 0
    int lower_bound(T w) {
        if (w <= 0) return 0;

        int x = 0; T k = 1;
        while (k * 2 <= N) k <<= 1;
        for (; k > 0; k /= 2) {
            if (x + k <= N && dat[x + k] < w) {
                w -= dat[x + k];
                x += k;
            }
        }
        return x + 1;
    }
};

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int N, Q;
    cin >> N >> Q;

    vll c(N);
    REP(i, N) cin >> c[i], c[i]--;

    vector<vector<pair<int, int>>> query(N);
    REP(i, Q) {
        int l, r; cin >> l >> r;
        --l; --r;
        query[r].eb(l, i);
    }

    vector<ll> last(N, -1);
    BIT<ll> bit(N);
    vector<ll> ans(Q);
    REP(i, N) {
        if (last[c[i]] > -1) bit.add(last[c[i]], -1);
        last[c[i]] = i;
        bit.add(i, 1);

        for(auto &p: query[i]) {
            ans[p.se] = bit.sum(i) - bit.sum(p.fi-1);
        }
    }

    for (auto &e: ans) {
        print(e);
    }
    
}


Measured memory_bytes: 40984
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define printYes() cout << "Yes" << endl;
#define printNo() cout << "No" << endl;
#define printVector(v) rep(i, v.size()) cout << x << endl;

int main()
{
    int H, N;
    cin >> H >> N;
    vector<pair<int, int>> magic(N);
    rep(i, N)
    {
        int A, B;
        cin >> A >> B;
        magic[i] = make_pair(A, B);
    }
    sort(magic.begin(), magic.end());
    vector<int> dpH(H + 1, INT32_MAX);
    dpH[0] = 0;
    rep(i, H + 1)
    {
        rep(j, N)
        {
            if (i - magic[j].first < 0)
                dpH[i] = min(dpH[i], magic[j].second);
            else
                dpH[i] = min(dpH[i], dpH[i - magic[j].first] + magic[j].second);
        }
    }
    cout << dpH[H] << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define r(i,n) for(int i=0;i<n;i++)
main(){
  string s,t;
  cin>>s>>t;
  vector<int>v1,v2;
  int c1=0,c2=0;
  r(i,s.size()){
    if(s[i]==t[c1]){
      v1.push_back(i);
      c1++;
    }
  }
  reverse(t.begin(),t.end());
  r(i,s.size()){
    if(s[s.size()-i-1]==t[c2]){
      v2.push_back(s.size()-1-i);
      c2++;
    }
  }
  reverse(v1.begin(),v1.end());
  if(v1.size()!=t.size())cout<<"no"<<endl;
  else if(v1!=v2)cout<<"no"<<endl;
  else cout<<"yes"<<endl;
}

Measured memory_bytes: 8968
#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int MAXN=3e5+5;

int len,anc[30][MAXN],S,T,num,nxt[MAXN];
ll l,r;
char s[MAXN];

ll calc(ll lt,int n){
	if(lt<=len)return anc[n][lt];
	if(lt<=2*len)return anc[n][len]+anc[n][lt-len];
	ll f1=anc[n][S],f2=anc[n][len],lenf1=S,lenf2=len;
	while(lt>lenf1+lenf2){
		ll tem2=f2,lentem2=lenf2;
		f2+=f1;lenf2+=lenf1;
		f1=tem2;lenf1=lentem2;
	}
	return f2+calc(lt-lenf2,n);
}

int main(){
	scanf("%s",s+1);
	scanf("%lld%lld",&l,&r);
	len=strlen(s+1)/2;
	nxt[1]=0;
    for(int j=0,i=2;i<=len;i++){
        for(;j&& s[j+1]!=s[i];)j=nxt[j];
        if(s[j + 1]==s[i])j++;
        nxt[i]=j;
    }
	T=nxt[len];
	S=len-T;
	for(int i=1;i<=26;i++){
		for(int j=1;j<=len;j++){
			anc[i][j]=anc[i][j-1];
			if((int)s[j]-96==i)anc[i][j]++;
		}
	}
//	cout<<calc(43200,1);
	for(int i=1;i<=26;i++){
		printf("%lld ",calc(r,i)-calc(l-1,i));
	}
	return 0;
}

Measured memory_bytes: 31616
const main = (input: string) => {
  const lines = input.trim().split("\n")
  const [N, K] = lines[0].split(" ").map(str => parseInt(str))
  let H = lines[1].split(" ").map(str => parseInt(str))
  H.sort((a, b) => a - b)

  if(K > 0) { H.splice(-K) }

  const sum = (arr: number[]) => {
    if(arr.length !== 0) {
      return arr.reduce((a:number , b: number) => a + b)
    }
    return 0
  }

  console.log(sum(H))
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));


Measured memory_bytes: 37380
#include<iostream>
#include<stdio.h>
#include<cmath>
using namespace std ;

int arr[100005];
int main(){
int n ;
scanf("%d",&n) ; 
long long sum=0 ; 
long long ans=0  ; 
arr[0]=0 ; 
arr[n+1]=0 ; 
for(int i=1 ; i<=n ;i++){
 scanf("%d",&arr[i]) ;  
}
for(int i=0 ; i<=n ; i++){
   sum+=abs(arr[i]-arr[i+1]) ;

} 
for(int j=1 ; j<=n ; j++){
   ans=sum -(abs(arr[j-1]-arr[j])+ abs(arr[j]-arr[j+1])) + abs(arr[j-1]-arr[j+1]);    
   printf("%lld\n",ans) ;  
   
}



return 0 ; 
}

Measured memory_bytes: 1664
n = gets.to_i

dic = {}

(1..n).each do |num|
  str = num.to_s
  if dic.include?([str[0], str[-1]])
    dic[[str[0], str[-1]]] += 1
  else
    dic[[str[0], str[-1]]] = 1
  end
end

#print dic

res = 0
(1..n).each do |num|
  str = num.to_s
  if dic.include?([str[-1], str[0]])
    res += dic[[str[-1],str[0]]]
  end
end

puts res

Measured memory_bytes: 1788
#include <iostream>
//#include <set>
//#include <map>
//#include <iomanip>
//#include <algorithm>
//#include <numeric>
//#include <queue>
//#include <stack>
//#include <math.h>
//#include <vector>
//#include <string>
//#include <list>
//#include <deque>
//#include <unordered_map>
typedef long long LL;
//typedef long double LD;
using namespace std;
 
//#define MOD 1000000007
//#define MAX 100100
//#define NIL -1

int main() {
    LL n;
    LL ans=0;

    cin >> n;
    for(int i=1; i<=n; i++){
        if(i%3!=0 && i%5!=0){
            ans += i;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3636
# -*- coding: utf-8 -*-
"""
Created on Mon Sep 14 00:57:13 2020

@author: liang
"""

N, Q = map(int, input().split())
S = input()
S += "a"
d = [0]*(N+1)
count = 0
for i in range(len(S)-1):
    if S[i:i+2] == "AC":
        count += 1
    #print(i)
    d[i+1] = count
#print(lis)
#print(d)
for i in range(Q):
    l, r = map(int, input().split())
    ans = d[r-1] - d[l-1]
    print(ans)


Measured memory_bytes: 11464
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}
const ll INF = 1LL<<60;
const ll M = pow(10,9)+7;
/*template*/


int main()
{
  ll a;cin>>a;
  cout<<(a+1)/2<<endl;
  return 0;
}


Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.Closeable;
import java.io.IOException;
import java.util.NoSuchElementException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author HBonsai
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CColoringColorfully solver = new CColoringColorfully();
        solver.solve(1, in, out);
        out.close();
    }

    static class CColoringColorfully {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            String s = in.next();
//        int oddZero = 0;
//        int evenZero = 0;
//        int oddOne = 0;
//        int evenOne = 0;
            int cnt1 = 0;
            int cnt2 = 0;
            for (int i = 0; i < s.length(); i++) {
                if (i % 2 == 0) {
                    if (s.charAt(i) == '0') cnt1++;
                    if (s.charAt(i) == '1') cnt2++;
                } else {
                    if (s.charAt(i) == '0') cnt2++;
                    if (s.charAt(i) == '1') cnt1++;
                }
            }
            out.println(Math.min(cnt1, cnt2));

        }

    }

    static class FastScanner implements Closeable {
        private final InputStream in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;

        public FastScanner(InputStream in) {
            this.in = in;
        }

        private boolean hasNextByte() {
            if (ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (buflen <= 0) {
                    return false;
                }
            }
            return true;
        }

        private int readByte() {
            if (hasNextByte()) return buffer[ptr++];
            else return -1;
        }

        private static boolean isPrintableChar(int c) {
            return 33 <= c && c <= 126;
        }

        public boolean hasNext() {
            while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
            return hasNextByte();
        }

        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while (isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public void close() {
            try {
                in.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

    }
}



Measured memory_bytes: 22868
#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int main() {
	int H, W;
	cin >> H >> W;
	vector<vector<char>> a(H, vector<char>(W));
	vector <vector<int>>b(H, vector<int>(W));
	for (size_t i = 0; i < H; i++)
	{
		for (size_t j = 0; j < W; j++)
		{
			cin >> a.at(i).at(j);
		}
	}
	for (size_t i = 0; i < H; i++)
	{
		if (a.at(i).at(0) == '.')b.at(i).at(0)++;
		else break;
	}
	for (size_t i = 0; i < W; i++)
	{
		if (a.at(0).at(i) == '.')b.at(0).at(i)++;
		else break;
	}
	for (size_t i = 1; i < H; i++)
	{
		for (size_t j = 1; j < W; j++)
		{
			if (a.at(i).at(j) == '.')b.at(i).at(j) += b.at(i - 1).at(j) + b.at(i).at(j - 1);
			b.at(i).at(j) %= mod;
		}
	}
	cout << b.at(H - 1).at(W - 1);
}

Measured memory_bytes: 5248
import sys
N=input()
a={}
for i in raw_input().split():
	#print i
	if i in a:
		a[i]=a[i]+1
	else:
		a[i]=1
#print a


M=input()
for j in raw_input().split():
	#print j
	if j in a:
		a[j]=a[j]-1
		if a[j]<0:
			print "NO"
			sys.exit()
	else:
			print "NO"
			sys.exit()		

print "YES"

Measured memory_bytes: 37456
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func main() {
	N, M := ReadInt(), ReadInt()
	X := ReadInts(M)
	sort.Ints(X)
	d := make([]int, 0)
	for i := 0; i < M-1; i++ {
		d = append(d, X[i+1]-X[i])
	}
	sort.Ints(d)
	ans := 0
	for i := 0; i < M-1-(N-1); i++ {
		ans += d[i]
	}
	fmt.Println(ans)
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int)       { Scan(&i); return }
func ReadString() (s string) { Scan(&s); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


Measured memory_bytes: 6488
import collections
cd = collections.defaultdict
dp = cd(lambda: cd(int))
dp[0][1] = 1

H, W, K = [int(_) for _ in input().split()]
mod = 10**9 + 7

fib = [1, 1, 2, 3, 5, 8, 13, 21] + [1] * 8

for h in range(1, H + 1):
    for w in range(1, W + 1):
        dp[h][w] = dp[h - 1][w] * fib[w - 1] * fib[W - w]
        dp[h][w] += dp[h - 1][w - 1] * fib[w - 2] * fib[W - w]
        dp[h][w] += dp[h - 1][w + 1] * fib[w - 1] * fib[W - w - 1]
        dp[h][w] %= mod

print(dp[H][K])


Measured memory_bytes: 3316
/* 
	Author: ankrypt
*/
#include <bits/stdc++.h>

using namespace std;

int combine(int a, int b) {
   int times = 1;
   while (times <= b)
      times *= 10;
   return a*times + b;
} 

int perfect_square(int n)
{
    int sqr=1;
    int counter=1;
    for(int i=1; i<=n; i++)
    {
        sqr = i*i;
		 if(sqr==n)
            return 1;
     }
           return 2;
}

int main()
{
	int A, B;
	scanf("%d %d", &A, &B);
	int finalAns = combine(A, B);
	 // cout << finalAns;
	if(perfect_square(finalAns) == 1)
	{
		cout << "Yes" << "\n";
	}
	else
	{
		cout << "No" << "\n";
	}

	
	return 0;
}
/*
	Powered by Buggy Plugin
*/


Measured memory_bytes: 256
#include "bits/stdc++.h"

#define REP(i,n) for(ll i=0;i<n;++i)
#define RREP(i,n) for(ll i=n-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<n;++i)
#define RFOR(i,m,n) for(ll i=n-1;i>=m;--i)
#define ALL(v) (v).begin(),(v).end()
#define PB(a) push_back(a)
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define DUMP(v) REP(i, (v).size()) { cout << v[i]; if (i != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

const int dx[8] = { 1,1,0,-1,-1,-1,0,1 };
const int dy[8] = { 0,1,1,1,0,-1,-1,-1 };


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll max(ll a, int b) { return max(a, ll(b)); }
ll max(int a, ll b) { return max(ll(a), b); }
///(?´????????`)(?´????????`)(?´????????`)(?´????????`)(?´????????`)(?´????????`)///
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	while (1) {
		int n, m;
		cin >> n >> m;
		if (!n)break;
		vi v(n, 0);
		v[0] = 1;
		vector<pair<int, pii>> p(m);
		REP(i, m) {
			cin >> p[i].first >> p[i].second.first >> p[i].second.second;
		}
		sort(ALL(p));
		REP(i, m) {
			if (v[p[i].second.first - 1])v[p[i].second.second - 1] = 1;
		}
		int cnt = 0;
		REP(i, n)if (v[i])cnt++;
		cout << cnt << endl;
	}
	return 0;
}

Measured memory_bytes: 3392
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <cmath>
#define ll long long
#define LINF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define PI 3.14159265
using namespace std;
const int MAX = 1e5 + 10;
const ll MOD = 1e9 + 7;
int N, M, K, Q;
int cnt[MAX];
vector<string> vec;

int main()
{
	int i, j, k;
	string s;
	cin >> s;
	for (i = 0; i < s.size(); ++i) {
		cnt[s[i] - 'a']++;
		for (j = (int)(s[i] - 'a') + 1; j < 26; ++j) {
			if (cnt[j] == 0) {
				string t = s.substr(0, i + 1);
				t[i] = 'a' + j;
				vec.push_back(t);
				break;
			}
		}
	}
	for (j = 0; j < 26; ++j) {
		if (cnt[j] == 0) {
			s.push_back('a' + j);
			vec.push_back(s);
			break;
		}
	}
	if (vec.empty()) {
		printf("-1");
		return 0;
	}
	sort(vec.begin(), vec.end());
	cout << vec[0];
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	// Code for B - 105
	var N int
	fmt.Scanf("%d", &N)
	flag := make(map[int]int, N+1)

	for i := 1; i <= N; i++ {
		for j := 1; j <= N; j++ {
			if j%i == 0 {
				flag[j]++
			}
		}
	}

	var count int
	for i := 1; i <= N; i++ {
		if flag[i] == 8 && i%2 != 0 {
			count++
		}
	}

	fmt.Println(count)
}


Measured memory_bytes: 1840