akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    a = LI()
    ans = 3 ** n
    a = sum(map(lambda x: x & 1, a))
    na = n - a
    print(ans - 2 ** na)
    return


#main
if __name__ == '__main__':
    solve()


Measured memory_bytes: 38512
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
    string S;
    cin >> S;
    sort(S.begin(), S.end());
    if (S[0] == S[1] && S[2] == S[3] && S[0] != S[2]) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

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;
}

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------
ll N, M;
ll A[101010];
ll B[101010];
map<ll, ll> m;

int main() {
  cin >> N >> M;
  m[0]++;
  repe(i, 1, N) {
    cin >> A[i];
    B[i] = B[i - 1] + A[i];
    ll bm = B[i] % M;
    m[bm]++;
  }

  ll ans = 0;
  for (auto e : m) {
    ll n = e.second;
    if (n >= 2) {
      ans += n * (n - 1) / 2;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 5760
from collections import deque
from bisect import bisect_left

n = int(input())
arr = deque()

for _ in range(n):
    i = int(input())
    if not arr:
        arr.append(i)
        continue

    if i <= arr[0]:
        arr.appendleft(i)
        continue

    idx = bisect_left(arr, i)
    arr[idx - 1] = i

    while idx < len(arr) and arr[idx - 1] > arr[idx]:
        arr[idx - 1], arr[idx] = arr[idx], arr[idx - 1]
        idx += 1

print(len(arr))


Measured memory_bytes: 7284
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 10e16
#define MOD 1000000007
#define mod 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}
//--------------------------------------------------------------------------

//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????        memset()!!!!!!!!!!!!       ペナを減らせ!!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    int n;cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++)cin>>a[i];
    int sum=0;double ave=0;
    for(int i=0;i<n;i++)sum+=a[i];
    ave=(double)sum/n;

    double minm=INF;
    int ans=0;
    for(int i=0;i<n;i++){
        if(minm>abs(a[i]-ave)){
            minm=abs(a[i]-ave);
            ans=i;
        }
    }
    cout<<ans<<endl;
    return 0;
    for(int i=0;i<n;i++){
        if(abs(a[i]-ave)==minm){
            cout<<i<<endl;
            return 0;
        }
    }
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------









Measured memory_bytes: 256
#include<iostream>
#include<sstream>
#include<iomanip>
#include<bitset>
#include<map>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#define lli long long int
#define uli unsigned long long int
#define inf 999999999999999999
#define rep(i,n,m) for(lli i=(lli)(n);i<(lli)(m);++i)
#define reep(i,n,m) for(int i=(int)(n);i<=(int)(m);++i)
#define per(i,m,n) for(lli i=(int)(m)-1;i>=(int)(n);--i)
#define st(n) sort(n.begin(), n.end())
#define rev(n) reverse(n.begin(),n.end())
#define ou(S) cout << S << endl
#define pb(n) push_back(n)
#define ue(N) N.erase(unique(N.begin(),N.end()),N.end());
#define nou(S) cout << S
#define hou(S) cout << setprecision(30) << S << endl
#define vec(K,L,N,S) vector<L> K(N,S)
#define dv(K,L,N,M,S) vector<vector<L>> K(N,vector<L>(M,S))
#define tv(K,L,N,M,R,S) vector<vector<vector<L>>> K(N,vector<vector<L>>(M,vector<L>(R,S)))
#define pint pair<lli,lli>
#define paf(L,R) pair<L,R>
#define mod 1000000007
#define maxx 5100000
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
using namespace std;
int main(){
  int n,d;cin>>n>>d;
  rep(i,0,8){
    n-=d*2+1;
    if(n<=0){
      cout<<i+1<<endl;
      return 0;
    }
  }
 // cout<<((n/(d*2+d-1)==0)?n/(d*2+d-1):n/(d*2+1)+1)<<endl;
}

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

using namespace std;

int main(){
    int A, B;
    cin >> A >> B;
    int ans = -1;
    for(int i=1; i<=10000; i++){
        if(int(i * 0.08) == A && int(i * 0.10) == B) {
            ans = i;
            break;
        }
    }
    cout << ans << 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 rep2(i, l, r) for (int i = (l); i < (r); i++)
#define ALL(x) (x).begin(), (x).end()     //昇順
#define RALL(x) (x).rbegin(), (x).rend()  // 降順
const long long mod = 1e9 + 7;
typedef long long ll;  // ll とdoubleは違う
typedef priority_queue<int> PQ;
typedef vector<long long> VL;
typedef vector<bool> VB;
typedef vector<int> VI;  // VI a(n);
typedef vector<double> VD;
typedef vector<string> VS;
typedef vector<char> VC;
typedef vector<VS> VSS;
typedef vector<VC> VCC;
typedef vector<VI> VII;  // VII a(n,vector<int>(m)) n * m
typedef vector<VL> VLL;
typedef pair<int, int> PII;
typedef map<int, int> MP;  // MP a;
typedef vector<pair<ll, ll>> PS;

template <class T, class U>  // chmax(max, a);
bool chmax(T &a, U b) {
  if (a <= b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T, class U>  // chmin(min,a)
bool chmin(T &a, U b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename T>  // operator << (cout,a);
ostream &operator<<(ostream &os, vector<T> &v) {
  os << "{";
  rep(i, (int)v.size()) { os << v[i] << (i < v.size() - 1 ? ", " : ""); }
  os << "}";
  return os;
}

// g++ -std=c++11 prac.cpp
     
template<typename T>
T gcd(T a, T b){
	return b != 0 ? gcd(b, a % b) : a;
}    


int main() {
  ll x=0,y=0,z=0,k,n,m,h,w,ans=0,sum=0,Max=-1,Min=1e9+1;
  bool ok = true;
  string s,t,r;
  cin >> n;
  VI a(n-1),b(n);
  rep(i,n-1) {cin >> a[i];}
  rep(i,n-1){
    b[a[i]-1]++;
  }
  rep(i,n){
    cout << b[i] << endl;
  }
  


  return 0;
}

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin>>s;
    if(s[2]==s[3] && s[4]==s[5]){
        cout<<"Yes";
    }
    else{
        cout<<"No";
    }
    return 0;
}

Measured memory_bytes: 256
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,M = map(int, readline().split())

    is_solved = [False] * (N + 1)
    wa_cnt = [0] * (N + 1)
    pena = 0

    for _ in range(M):
        p, s = readline().split()
        p = int(p)
        if s == "WA":
            if is_solved[p]:
                continue
            else:
                wa_cnt[p] += 1
        else:
            if is_solved[p]:
                continue
            else:
                pena += wa_cnt[p]
                is_solved[p] = True

    print(sum(is_solved), pena)


if __name__ == "__main__":
    main()


Measured memory_bytes: 4596
#include <stdio.h>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <iostream>
#include<math.h>
#include<bitset>
#include<iomanip>
using namespace std;

int ans = 0, a[3] = { 3,5,7 };
long long N;
void f(long long x) {
	for (int i = 0; i < 3; i++) {
		long long y = x * 10 + a[i];
		long long z = y;
		if (z > N)break;
		bool k = 0, l = 0, m = 0;
		while (1) {
			if (y % 10 == 3)k++;
			if (y % 10 == 5)l++;
			if (y % 10 == 7)m++;
			y /= 10;
			if (y == 0||(k&&l&&m&&1))break;
		}
		if (N >= z&&k==1&&l==1&&m==1) { ans++;}
		if (N > z)f(z);

	}
}

int main() {
	cin >> N;
	for (int i = 0; i < 3; i++) {
		f(a[i]);
	}
	cout <<ans<< endl;
	
}


Measured memory_bytes: 256
fn main() {
    let _ = read::<i32>();
    let v = read_vec::<f64>();

    println!("{}", 1.0 / v.into_iter().map(|e| 1.0/e).sum::<f64>())
}

// 標準入力より、FromStrを実装した型の値を読み取る
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T  {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().parse::<T>().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
    .map(|e| e.parse().ok().unwrap())
    .collect()
}

Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)

using namespace std;
using ll = long long;
using P = pair<int, int>;
using LP = pair<ll, ll>;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    string s, t;
    cin>>s>>t;

    ll n = s.size();
    map<char, vector<ll>> mp;
    rep(i, n) {
        mp[s[i]].push_back(i);
    }
    ll m = t.size();
    ll cur = -1;
    ll cnt = 0;
    rep(i, m) {
        char c = t[i];
        if (mp[c].size() == 0) {
            cout<<-1<<endl;
            return 0;
        }
        auto it = upper_bound(mp[c].begin(), mp[c].end(), cur);
        if (it == mp[c].end()) {
            cur = mp[c][0];
            cnt += n;
            continue;
        }
        cur = *it;
    }
    cnt += cur + 1;
    cout<<cnt<<endl;
}

Measured memory_bytes: 1736
#include<stdio.h>
#include<string.h>
int main(){
	int i,n,t_point=0,h_point=0,result;
	char t_card[101],h_card[101];
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%s %s",t_card,h_card);
		result=strcmp(t_card,h_card);
		if(result==0){
			t_point++;
			h_point++;
		}else if(result>0){
			t_point+=3;
		}else if(result<0){
			h_point+=3;
		}
	}
	printf("%d %d\n",t_point,h_point);
	return 0;
}


Measured memory_bytes: 1808
N,M = map(int,input().split())
a = []
for i in range(N):
  array = list(map(int, input().strip().split(' ')))
  a.append(array)
ans = 0
sum = [0]*32
tmp = 0
for i in range(N):
  tmp = a[i][0]
  for j in range(tmp):
    sum[a[i][j+1]] = sum[a[i][j+1]] + 1
    
for i in range(32):
  if sum[i] == N:
    ans = ans + 1
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;

int main() {
  int n;
  cin >> n;
  int a = n / 100;
  int b = (n % 100) / 10;
  int c = n % 10;
  if (a == 7 || b == 7 || c == 7) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3628
import java.util.Scanner;
class Main{
    public static void main(String[] args){
		int n;
		String c;
		int a;
		int[][] card=new int[4][14];
		String[] egara={"S","H","C","D"};
		Scanner sc=new Scanner(System.in);
		for(int i=0;i<4;i++){
			for(int j=0;j<14;j++){
				card[i][j]=0;
			}
		}
		n=sc.nextInt();
		for(int i=0;i<n;i++){
			c=sc.next();
			a=sc.nextInt();
			switch(c){
				case "S":
					card[0][a]=a;
					break;
				case "H":
					card[1][a]=a;
					break;
				case "C":
					card[2][a]=a;
					break;
				case "D":
					card[3][a]=a;
					break;
				default:
					break;
			}
		}
		for(int i=0;i<4;i++){
			for(int j=1;j<14;j++){
				if(card[i][j]==0){
					System.out.println(egara[i]+" "+j);
				}
			}
		}
    }
}



Measured memory_bytes: 26260
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#include <iomanip>

#define int long long int

using namespace std;

typedef pair<int, int> P;

const int inf = 1e15;

int h, w;

void bfs(const vector<vector<bool>>& a, vector<vector<int>>& r, queue<pair<P, int>>& q) {
    if(q.empty()){
        return;
    }
    pair<P, int> p = q.front();
    q.pop();
    int x = p.first.first;
    int y = p.first.second;
    if(r[x][y] != 0){
        bfs(a, r, q);
    }
    r[x][y] = p.second+1;

    if(x + 1 < h){
        if(a[x+1][y] && r[x+1][y] == 0){
            q.push(make_pair(make_pair(x+1, y), p.second+1));
        }
    }

    if(x - 1 >= 0){
        if(a[x-1][y] && r[x-1][y] == 0){
            q.push(make_pair(make_pair(x-1, y), p.second+1));
        }
    }

    if(y + 1 < w){
        if(a[x][y+1] && r[x][y+1] == 0){
            q.push(make_pair(make_pair(x, y+1), p.second+1));
        }
    }

    if(y - 1 >= 0){
        if(a[x][y-1] && r[x][y-1] == 0){
            q.push(make_pair(make_pair(x, y-1), p.second+1));
        }
    }
    bfs(a, r, q);
}


signed main(){
    cin >> h >> w;

    vector<vector<bool>> a(h, vector<bool>(w));
    vector<vector<int>> r(h, vector<int>(w));
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            char c;
            cin >> c;
            if(c == '.'){
                a[i][j] = true;
            }else{
                a[i][j] = false;
            }
        }
    }

    queue<pair<P, int>> q;
    r[0][0] = 1;
    if(a[0][1]){
        q.push(make_pair(make_pair(0, 1), 1));
    }
    if(a[1][0]){
        q.push(make_pair(make_pair(1, 0), 1));
    }
    bfs(a, r, q);

    if(r[h-1][w-1] == 0){
        cout << -1 << endl;
        return 0;
    }

    int black = 0;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(!a[i][j]){
                black++;
            }
        }
    }

    cout << h*w - r[h-1][w-1] - black << endl;

    return 0;
}


Measured memory_bytes: 512
// https://onlinejudge.u-aizu.ac.jp/courses/lesson/2/ITP1/9/ITP1_9_A

#include <iostream>
#include <algorithm>

int main()
{
    std::string W, T;
    int cnt = 0;

    std::cin >> W;
    while (std::cin >> T && T != "END_OF_TEXT")
    {
        std::transform(T.begin(), T.end(), T.begin(), tolower);
        if (T == W)
        {
            cnt++;
        }
    }
    std::cout << cnt << std::endl;
}


Measured memory_bytes: 3140
function Main(input) {
    var S = input[0].toString();

    var reverseS = S.split('').reverse().join('');

    var WORDS = ['dream', 'dreamer', 'erase', 'eraser']
        .map(s => {
            return s.split('').reverse().join('');
        })

    var stringNum = 0;

    while(stringNum < reverseS.length) {
        var word = WORDS.find(w => {
            return reverseS.startsWith(w, stringNum);
        })
        if (!word) {
            return console.log('NO');
        } else {
            stringNum += word.length;
        }
    }

    console.log('YES');
}

Main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\n|\s/));

Measured memory_bytes: 9628
//04, 11, 2018, 10:01:17 Rafaelcs cpp
#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int x, y;

    cin >> x >> y;

    cout << x + (y / 2) << endl;
    
    return 0;
}

Measured memory_bytes: 256
/*The woods are lovely, dark and deep,
But I have promises to keep,
And miles to go before I sleep,
And miles to go before I sleep.*/

//PRABHJOT SINGH A.K.A. PRABHI
//~~~~~conquizztador~~~~~


#include<bits/stdc++.h>
using namespace std;
using lli = long long int;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
const int MOD = 1000000007;
const int MOD1 = 998244353;
const int maxn = 100010;
const int lim = (int)1e9;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	string s, t;
	cin >> s;
	cin >> t;
	int n = s.length() - t.length();
	int ct = 0, res = INT_MAX;
	for (int i = 0; i <= n; ++i)
	{
		for (int j = 0; j < t.length(); ++j)
			if (s[i + j] != t[j])
				++ct;
		res = min(res, ct); ct = 0;
	}
	cout << res << endl;
}

Measured memory_bytes: 3660
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#include <map>
using namespace std;

void solve(){
  int n, k; cin >> n >> k;
  vector<int> v(n);
  int index;
  for(int i = 0; i < n; i++){
    cin >> v[i];
    if(v[i] == 1) index = i;
  }
  //cout << index << endl;
  long long int ans = 0, x;
  if(index % (k - 1) == 0){
    ans += index / (k - 1);
    x = n - index - 1;
  }
  else{
    ans += index / (k - 1) + 1;
    x = n - index - 1 - ((k - 1) - (index % (k - 1)));
  }
  //cout << (double)index / (k - 1) << endl;
  //cout << (double)(n - index - 1) / (k - 1) << endl;
  if(x % (k - 1) == 0) ans += x / (k - 1);
  else ans += x / (k - 1) + 1;
  cout << ans << endl;
  return;
}

void solve2(){
  int n, k; cin >> n >> k;
  vector<int> v(n);
  for(int i = 0; i < n; i++){
    cin >> v[i];
  }
  if((n - 1) % (k - 1) == 0) cout << (n - 1) / (k - 1) << endl;
  else cout << (n - 1) / (k - 1) + 1 << endl;

}
int main(){
  //solve();
  solve2();
  return 0;
}


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

int ans;

int main() {
	string s;
	cin >> s;
	for (int i = 0; i < s.size() - 1; i++) {
		if(s[i] != s[i + 1])ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
using namespace std;
int n,m;
const int maxn = 1e5 + 5;
int a[maxn];
vector<int> G[maxn];
int cnt[maxn],now_cnt;
bool vis[maxn];
void dfs(int index)
{
	vis[index] = 1;
	cnt[index] = now_cnt;
	for(int i = 0;i < G[index].size(); ++i)
	{
		int v = G[index][i];
		if(!vis[v])
		{
			dfs(v);
		}
	}
}
int main(int argc, char const *argv[])
{
	cin>>n>>m;
	for(int i = 1;i <= n; ++i)
	{
		cin>>a[i];
	}
	while(m--)
	{
		int x,y;
		cin>>x>>y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	for(int i = 1;i <= n; ++i)
	{
		if(!vis[i])
		{
			now_cnt++;
			dfs(i);
		}
	}
	int res = 0;
	for(int i = 1;i <= n; ++i)
	{
		if(cnt[i] == cnt[a[i]])
		{
			res++;
		}
	}
	cout<<res<<endl;
	return 0;
}

Measured memory_bytes: 8576
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N = I()
    S = ST()+"//"
    i=0
    ans =0
    while i < N:
        if S[i:i+2] in ("OX","XO"):
            ans += 1
            i +=1
        i+=1
    print(ans)
if __name__ == '__main__':
    main()


Measured memory_bytes: 6584
#include <cstdio>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <climits>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <set>
#include <map>
#include <list>
#include <deque>
#include <vector>
#include <string>
#include <bitset>
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define next asdnext
#define prev asdprev
#define INF 1000000001
#define endl "\n"
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP_R(i,n) for(int i=((int)(n)-1);i>=0;--i)
#define FOR(i,m,n) for(int i=((int)(m));i<(int)(n);++i)
#define FOR_R(i,m,n) for(int i=((int)(m)-1);i>=(int)(n);--i)
#define ALL(v) (v).begin(),(v).end()
#define SIZ(x) ((int)(x).size())
typedef long long int lli;
using namespace std;

int main()
{
  char ch;
  cin >> ch ;
  if( ch == 'A' )
    {
      cout << 'T' << endl;
      
    }
  else if( ch == 'T' )
    {
      cout << 'A' << endl;
      
    }
  else if( ch == 'C' )
    {
      cout << 'G' << endl;
      
    }
  else //if( ch == 'G' )
    {
      cout << 'C' << endl;
      
    }
  

}


Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
S = input()
cnt = 0

for i in range(N-2):
  if S[i] == "A" and S[i+1] == "B" and S[i+2] == "C":
    cnt += 1
    
print(cnt)
    

Measured memory_bytes: 5200
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x;
int main()
{
	cin>>x;
	vector<ll>v;
	for(int i=2;i<=x/i;i++)
	{
		ll res=0;
		if(x%i==0)
		{
			while(x%i==0) x/=i,res++;
			v.push_back(res);
		}
	
	
		
	 } 
	 if(x>1)  v.push_back(1);
	 ll sum=0;
	 for(int i=0;i<v.size();i++)
	 {
	 //	cout<<v[i]<<endl;
	 	ll ans=0;
	 	int j=1;
	 	while(ans+j<=v[i])
	 	{
	 		ans+=j;
	 		sum++;
	 		j++;
		 }
	 }
	 cout<<sum<<endl;
}

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

int main() {
  string S; cin >> S;
  long long ans = 0, left, right, d;
  for (int i = S.size()-1; i>=0; i--) {
    d = S[i] - '0';
    left = pow(2,i);
    if(i==S.size()-1) ans += left * d;
    else {
      right = pow(10, S.size()-1-i);
      for  (int j =0 ; j<S.size()-1-i; j++) right += pow(10, j)*pow(2,S.size()-2-i-j);
      ans += left*d*right;
    }
  }
  cout << ans;
}

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

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<vvd> vvvd;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

#define LL long long;
#define REP(i,s,N) for (int i=s; i<N; i++)

int main() {
	string O, E;
	cin >> O >> E;
	int N = E.length();
	if(O.size() == N) {
		REP(i, 0, N) {
			cout << O[i] << E[i];
		}
		cout << endl;
	}
	else {
		REP(i, 0, N) {
			cout << O[i] << E[i];
		}
		cout << O[N] << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define itn int
#define REP(i, n) for (ll i = 0; i < n; i++)
#define IREP(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i < b + 1; i++)
#define all(v) v.begin(), v.end()
#define SENTINEL 2000000000
#define NIL -1
using namespace std;
typedef long long ll;

const ll MAX = 510000;
const ll INF = 1LL << 60;
const ll MOD = 998244353;
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()
{
    int n;
    cin >> n;
    vector<int> a(n);
    map<int,int> m;
    ll sum=0;
    REP(i,n){
        cin >> a[i];
        m[a[i]]++;
        sum+=a[i];
    }
    int q;
    cin >> q;
    REP(i,q){
        int b,c;
        cin >> b >> c;
        cout << sum+(c-b)*m[b] << endl;
        sum = sum + (c - b) * m[b];
        m[c]=m[c]+m[b];
        m[b]=0;
    }
}


Measured memory_bytes: 8052
n = int(input())
p = list(map(int, input().split()))
count = 0

for i in range(1,n-1):
    if max(p[i-1],p[i],p[i+1]) != p[i] and min(p[i-1],p[i],p[i+1]) != p[i]:
        count += 1
print(count)

Measured memory_bytes: 38256
import sys
n, x = map(int, input().split())
l = list(map(int, input().split()))
count = 1
d = 0

for i in range(1, n+1):
    if d + l[i-1] <= x:
        d = d + l[i-1]
        count = count + 1
    else:
        print(count)
        sys.exit()
print(count)


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

int main(){
	string s;
	cin>>s;
	vector<int> cnt[26];
	for(int i=0;i<s.size();i++){
		cnt[s[i]-'a'].push_back(i);
	}
	for(int i=0;i<26;i++){
		if(cnt[i].size()<2)continue;
		for(int j=0;j<s.size();j++){
			int k=j+1;
			while(k-j<=2&&k<s.size()){
				if(s[j]==s[k]){
					cout<<j+1<<" "<<k+1<<endl;
					return 0;
				}
				k++;
			}
		}
	}
	cout<<"-1 -1"<<endl;
	return 0;
}

Measured memory_bytes: 1148
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <cmath>
#include <numeric>
#include <iomanip>
#include <deque>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <sstream>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>

#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define FOR(i, a, done) for (int i = (a); i < (done); ++i)
#define all(a) (a).begin(), (a).end()
#define F first
#define S second
#define x first
#define y second
#define pb push_back
#define pf push_front

namespace mp = boost::multiprecision;
using cpp_int = mp::cpp_int;
using ll = long long;
using namespace std;

ll M = 1000000007;
typedef pair<int, int> P;

int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    int sum=a+b+c;
    if(sum>21){
        cout<<"bust"<<endl;
    }else{
        cout<<"win"<<endl;
    }
}


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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplece_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define Edge pair< i_i, int>
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; scanf("%lld", &x);
#define int2(x, y) int x, y; scanf("%lld %lld", &x, &y);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Endl endl
 
//int dxy[5] = {0, 1, 0, -1, 0};
// assign
 
signed main()
{
    int2(a, b);
    Int(c);

    cout << ( ( (a * 100 + b * 10 + c) % 4 ) ?
        "NO" : "YES" ) << endl;

    return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        
        int a = scan.nextInt();
        int b = scan.nextInt();
        int c = scan.nextInt();
        int t = 0;
        
        for(int i = 0; i < b-a+1; i++){
            if(c%(a+i) == 0)
            t++;
        }
        System.out.println(t);
    }
}


Measured memory_bytes: 26308
#include <bits/stdc++.h>
#define N 100550
#define pb push_back
#define fi first
#define se second
#define si size()
#define ll long long
#define mp make_pair
#define iter ::iterator
#define all(v) v.begin(), v.end()
#define pp pop_back
#define mapiter map<int, int>::iterator
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forn1(i, n) for(int i = 1; i <= n; ++i)
#define forr(i, n)  for(int i = n - 1; i >= 0; --i)
#define forr1(i, n) for(int i = n; i >= 1; --i)
#define form(l, r, i)   for(int i = l; i <= r; ++i)
#define forv(r, l, i)   for(int i = r; i >= l; --i)
#define r0 return 0
#define barnarnar ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lld long double
#define elif else if
  
const int inf = 1e9 + 7;
const lld EPS = 0.00000001;
const ll modw = 1e9 + 9;
  
using namespace std;



int main()
{
    barnarnar
    string s;
    cin >> s;
	if(s[2] == s[3] && s[4] == s[5])	cout << "Yes";
	else	cout << "No";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long int;
using namespace std;

int main()
{
    int N, W;
    cin >> N >> W;
    vector<int> w(N, 0), v(N, 0);
    for (int i = 0; i < N; i++)
    {
        cin >> w[i] >> v[i];
    }
    vector<vector<ll>> dp(N + 1, vector<ll>(W + 1, 0));
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= W; j++)
        {
            if (w[i - 1] <= j)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
            }
            else
            {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    cout << dp[N][W] << endl;

    return 0;
}

Measured memory_bytes: 80256
import java.util.*;
public class Main{
    public static void main(String[] args){
	new Main().run();
    }
    Scanner sc = new Scanner(System.in);

    int[] tetra = new int[200];
    int[] Otetra = new int[200];
    int[] ans = new int[1000000];
    int[] odd = new int[1000000];

    void run(){
	setTetra();
	solve();
	while(sc.hasNext()){
	    int x = sc.nextInt();
	    if(x!=0)
		System.out.println(ans[x]+" "+odd[x]);
	}
    }

    void setTetra(){
	int o = 0;
	for(int i=0; i<tetra.length; i++){
	    tetra[i] = (i*(i+1)*(i+2))/6;
	    if(tetra[i]%2==1)
		Otetra[o++] = tetra[i];
	}
    }

    void solve(){
	int max = Integer.MAX_VALUE;
	Arrays.fill(ans, max);
	Arrays.fill(odd, max);

	ans[0] = 0;
	for(int i=0; i<tetra.length; i++){
	    int a = tetra[i];
	    for(int j=a; j<ans.length; j++){
		if(ans[j-a] != max){
		    int newAns = ans[j-a]+1;
		    if(newAns < ans[j]) {
			ans[j] = newAns;	
		    }
		}
	    }
	}

	odd[0] = 0;
	for(int i=0; i<Otetra.length; i++){
	    int a = Otetra[i];
	    for(int j=a; j<odd.length; j++){
		if(odd[j-a] != max){
		    int newOdd = odd[j-a]+1;
		    if(newOdd < odd[j]) {
			odd[j] = newOdd;	
		    }
		}
	    }
	}
    }
}

Measured memory_bytes: 29324
from queue import deque

N = int(input())

A = []
B = [[]for i in range(N)]

for i in range(N-1):
    a, b = map(int, input().split())
    A.append([a, b])
    
for i, j in A:
    B[i-1].append(j-1)

q = deque([0])
color = [-1]*N
ans = {}
saidai = 0
while q:
    nord = q.popleft()
    c = 0
    for i, v in enumerate(B[nord]):
        if color[nord] == i:
            c += 1
        color[v] = c + i 
        ans[(nord, v)] = c + i
        q.append(v)
        saidai = max(saidai,i+c+1)

print(saidai)

for i, j in A:
    print(1+ans[(i-1, j-1)])

Measured memory_bytes: 48896
n = int(input())
T_point = 0
H_point = 0
for i in range(n):
    Taro, Hanako = input().split()
    if Taro > Hanako:
        T_point += 3
    elif Hanako > Taro:
        H_point += 3
    else:
        T_point += 1
        H_point += 1
print(T_point, H_point)

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

int main()
{
	int i,j,k;
	int count=0;
	int a,b,c,x;

	cin >> a >> b >> c >> x;

	for(i=0;i<=a;i++){
		for(j=0;j<=b;j++){
			for(k=0;k<=c;k++){
				if(x == (i*500+j*100+k*50)){
					count++;
				}
				//cout << i << j << k << endl;
			}
		}
	}

	cout << count << endl;

return 0;
}




Measured memory_bytes: 256
use std::io;
use std::io::Read;

fn main() {
    let mut stdin = io::stdin();
    let mut lines = String::new();
    let _ = stdin.read_to_string(&mut lines);
    let vec = lines.lines().collect::<Vec<&str>>();
    let n :usize = vec[0].trim().parse().unwrap();
    let vec2 = vec[1].split(' ').collect::<Vec<&str>>();
    let mut a :Vec<usize> = Vec::new();
    for i in 0..n {
        a.push(vec2[i].trim().parse::<usize>().unwrap());
    }
    a.sort();
    let a = a;
    
    let mut nownumber :usize = 0;
    let mut nowncount :usize = 0;
    let mut paircount :usize = 0;
    let mut numbercount :usize = 0;
    for b in a {
        if b == nownumber {
            nowncount += 1;
        } else {
            if nownumber != 0 {
                if nowncount % 2 == 0 {
                    paircount += 1;
                }
            }
            numbercount += 1;
            nownumber = b;
            nowncount = 1;
        }
    }
    if nowncount % 2 == 0 {
        paircount += 1;
    }

    let ans = if paircount % 2 == 0 {
        numbercount
    } else {
        numbercount - 1
    };
    println!("{}", ans);
}


Measured memory_bytes: 6652
#include <bit>
#include <bitset>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>
#include <iomanip>

typedef long double ld;
typedef long long ll;

using namespace std;


/* TEMPLATE ENDS HERE */

int main() {
	cout << fixed << setprecision(12);	
	int a, b;
	cin >> a >> b;
	b--;
	cout << (b + (a - 2)) / (a - 1) << endl;
	return 0;
}


ll MOD = ((ll)1e9 + 7);

struct mod {
	ll x;

	mod(ll tx = 0) {
		x = tx;
		x %= MOD;
	}
	
	mod& operator=(const ll & tx) {
		x = tx % MOD;
		return *this;
	}
	
	mod& operator=(const mod & m2) {
		x = m2.x;
		return *this;
	}

	mod operator+(const mod& m2) const {
		return mod((x + m2.x) % MOD);
	}

	mod& operator+=(const mod& m2) {
		x += m2.x;
		x %= MOD;
		return *this;
	}

	mod operator-(const mod & m2) const {
		return mod((x - m2.x + MOD) % MOD);
	}

	mod& operator-=(const mod & m2) {
		x -= m2.x;
		x = (x + MOD) % MOD;
		return *this;
	}

	mod operator*(const mod & m2) const {
		return mod((x * m2.x) % MOD);
	}

	mod& operator*=(const mod & m2) {
		x *= m2.x;
		x %= MOD;
		return *this;
	}

	mod mypow(ll k) const {
		mod ret = 1;
		mod cur = x;
		while (k) {
			if (k & 1) {
				ret *= cur;
			}
			cur *= cur;
			k >>= 1;
		}
		return ret;
	}

	mod inv() const {
		return mypow(MOD - 2);
	}

	mod operator/(const mod & m2) const {
		return (*this) * m2.inv();
	}

	mod& operator/=(const mod & m2) {
		x *= m2.inv().x;
		x %= MOD;
		return *this;
	}

	bool operator<(const mod & m2) const {
		return x < m2.x;
	}
};

ostream &operator<<(ostream & os, const mod & m) {
	return os << m.x;
}



Measured memory_bytes: 3596
A,B,C,D=map(int,list(input()))

if A+B+C+D==7:
    print('{}+{}+{}+{}=7'.format(A,B,C,D))
elif A-B+C+D==7:
    print('{}-{}+{}+{}=7'.format(A,B,C,D))
elif A+B-C+D==7:
    print('{}+{}-{}+{}=7'.format(A,B,C,D))
elif A+B+C-D==7:
    print('{}+{}+{}-{}=7'.format(A,B,C,D))
elif A-B-C+D==7:
    print('{}-{}-{}+{}=7'.format(A,B,C,D))
elif A+B-C-D==7:
    print('{}+{}-{}-{}=7'.format(A,B,C,D))
elif A-B+C-D==7:
    print('{}-{}+{}-{}=7'.format(A,B,C,D))
elif A-B-C-D==7:
    print('{}-{}-{}-{}=7'.format(A,B,C,D))


Measured memory_bytes: 3064
#include<iostream>
using namespace std;
bool b[110];
int main(){
	int n;
	b[0]=1;
	cin>>n;
	for(int i=0;i<=n;i++){
		if(b[i]){
			b[i+4]=1;
			b[i+7]=1;
		}
	}
	if(b[n])
		cout<<"Yes";
	else
		cout<<"No";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pil = pair<pii,int>;


int main(){
    ll a,b,n;
    cin >> a >> b >> n;
    ll s = b-1;
    int ans;
    bool ok = true;
    while(ok){
        if(s <= n){
            int x = (a*s)/b;
            int y = (s/b);
            ans = x - a * y;
            ok = false;
        }
        else s--;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3624
#include <stdio.h>
int main(){
  int a,b;
  scanf("%d %d",&a,&b);
  if(a < b){printf("a < b\n");}
  if(a > b){printf("a > b\n");}
  if(a == b){printf("a == b\n");}
  
  return 0;
}

Measured memory_bytes: 580
#include<iostream>
using namespace std;
int main(){
  int N,K;
  cin>>N>>K;
  int count =0;
  for(int i=0;i<N;i++){
    int h;
    cin>>h;
    if(h>=K){
      count++;
    }
  }
  cout<<count<<endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n, cnt=0;
    cin >> n;
    for(long long i=1;i<=n;i++){
        if(i%3==0 || i%5==0) continue;
        cnt += i;
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define SSTR( x ) static_cast< std::ostringstream & >( \
        ( std::ostringstream() << std::dec << x ) ).str()
#define ALL(s) (s).begin(), (s).end()
using namespace std;
typedef long long unsigned int llu;
typedef long long ll;

const string D_blue    = "\x1b[36m";
const string D_green   = "\x1b[32m";
const string D_red     = "\x1b[31m";
const string D_yellow  = "\x1b[33m";
const string Db_red    = "\x1b[41m";
const string Db_yellow = "\x1b[43m";
const string D_end     = "\x1b[39m";
const string Db_end    = "\x1b[49m";

int main (){
  int n;
  string s;
  while (cin >> n >> s ){
    int cnt1[n];
    int ans = INT_MAX;
    if(s[0] == 'W'){
      cnt1[0] = 1;
    }else{
      cnt1[0] = 0;
    }
    FOR(i,1,n){
      if(s[i] == 'W'){
	cnt1[i] = cnt1[i-1] + 1;
      }else{
	cnt1[i] = cnt1[i-1];
      }
    }
      //cnt[i] =>i人目までで西を向いている人の数
    ans = n-1 - (cnt1[n-1] - cnt1[0]);
    FOR(i,1,n){
      //n-i-1 => 残り人数
      //east => (n-i)-(cnt[n-1] - cnt[i])
      int result = cnt1[i-1] + (n-i-1)-(cnt1[n-1] - cnt1[i]);
      ans = min(ans,result);
    }
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 1796
T = int(input())
NABCD = [[int(_) for _ in input().split()] for _ in range(T)]
for n, a, b, c, d in NABCD:

    memo = {}
    memo[0] = 0
    memo[1] = d

    def solve(n):
        if n in memo:
            return memo[n]
        ans = n * d
        q, r = divmod(n, 2)
        if r == 0:
            ans = min(ans, a + solve(q))
        else:
            ans = min(ans, a + d + solve(q))
            ans = min(ans, a + d + solve(q + 1))
        q, r = divmod(n, 3)
        if r == 0:
            ans = min(ans, b + solve(q))
        else:
            ans = min(ans, b + r * d + solve(q))
            ans = min(ans, b + (3 - r) * d + solve(q + 1))
        q, r = divmod(n, 5)
        if r == 0:
            ans = min(ans, c + solve(q))
        else:
            ans = min(ans, c + r * d + solve(q))
            ans = min(ans, c + (5 - r) * d + solve(q + 1))
        memo[n] = ans
        return ans

    print(solve(n))


Measured memory_bytes: 10912
n,m,x = map(int,input().split())
a = list(map(int,input().split()))
i = x
ans = 0
while i > 0:
    i -= 1
    if i in a:
        ans += 1
c = 0
i = x
while i < n:
    i += 1
    if i in a:
        c += 1
ans = min(ans,c)
print(ans)

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

using namespace std;
using int64 = long long;

constexpr int DEBUG = 0;

constexpr int64 P = 1000000007;

struct FiniteField {
 private:
  int64 x;
  static inline int64 Normalize(int64 x) {
    if (0 <= x && x < P) return x; x %= P; if (x < 0) x += P; return x;
  }
 public:
  FiniteField(int64 x) : x(Normalize(x)) {}
  FiniteField() : x(0) {}
  int64 Value() const { return x; }
  inline FiniteField operator+(FiniteField o) const {
    FiniteField r(*this); r += o; return r;
  }
  inline FiniteField operator-(FiniteField o) const {
    FiniteField r(*this); r -= o; return r;
  }
  inline FiniteField operator* (FiniteField o) const {
    FiniteField r(*this); r *= o; return r;
  }
  inline FiniteField operator/ (FiniteField o) const {
    FiniteField r(*this); r /= o; return r;
  }
  inline void operator+= (FiniteField o) { x = (x + o.x) % P; }
  inline void operator-= (FiniteField o) { x = (x + P - o.x) % P; }
  inline void operator*= (FiniteField o) { x = (x * o.x) % P; }
  void operator/=(FiniteField o) {
    int64 p = P - 2; while (p) { if (p % 2) { *this *= o; } o *= o; p /= 2; }
  }
};

ostream& operator<<(ostream& s, const FiniteField& v) { s << v.Value(); return s; }

struct Edge {
  const int from, to;
  Edge(int from, int to) : from(from), to(to) {}
};

vector<vector<Edge>> ReadUndirectedGraph(
    int n, int m, bool is_one_indexed=false) {
  vector<vector<Edge>> graph(n);
  for (int i = 0; i < m; i++) {
    int v1, v2;
    cin >> v1 >> v2;
    if (is_one_indexed) {
      v1--;
      v2--;
    }
    graph[v1].push_back(Edge(v1, v2));
    graph[v2].push_back(Edge(v2, v1));
  }
  return graph;
}

int Sum(const vector<int>& xs) {
  int r = 0;
  for (int x : xs) r += x;
  return r;
}

FiniteField Power(FiniteField x, int p) {
  if (p < 0) return FiniteField(1) / Power(x, -p);
  FiniteField value = 1;
  while (p) {
    if (p % 2) value *= x;
    x *= x;
    p /= 2;
  }
  return value;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n;
  cin >> n;

  auto graph = ReadUndirectedGraph(n, n - 1, true);
  vector<int> sizes(n);
  function<void(int, int)> dfs_fn = [&](int v, int p) {
    int size = 1;
    for (const auto& e : graph[v]) {
      if (e.to == p) continue;
      dfs_fn(e.to, v);
      size += sizes[e.to];
    }
    sizes[v] = size;
  };
  dfs_fn(0, -1);

  FiniteField sum = 0;
  for (int v = 0; v < n; v++) {
    vector<int> cs;
    for (const auto& e : graph[v]) {
      if (sizes[e.to] < sizes[v]) {
        cs.push_back(sizes[e.to]);
      }
    }
    
    if (Sum(cs) < n - 1) {
      cs.push_back(n - 1 - Sum(cs));
    }

    FiniteField a = 0;
    for (int c : cs) {
      a += Power(2, c) - 1;
    }
    a += 1;
    sum += Power(2, n - 1) - a;
  }
  cout << sum / Power(2, n) << endl;
}

Measured memory_bytes: 25728
#include<iostream>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<bitset>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<long long, int> ll_i;

#define PI 3.141592653589793238462643383279
#define mod 1000000007LL
#define rep(i, n) for(i = 0;i < n;++i)
#define rep1(i, n) for(i = 1;i < n;++i)
#define per(i, n) for(i = n - 1;i > -1;--i)
#define int(x) int x; scanf("%d",&x)
#define int2(x, y) int x, y; scanf("%d%d",&x, &y)
#define int3(x, y, z) int x, y, z; scanf("%d%d%d",&x, &y, &z)
#define int4(v, x, y, z) int v, x, y, z; scanf("%d%d%d%d", &v, &x, &y, &z)
#define int5(v, w, x, y, z) int v, w, x, y, z; scanf("%d%d%d%d%d", &v, &w, &x, &y, &z)
#define pri(x) cout << (x) << "\n"
#define pri2(x, y) cout << (x) << " " << (y) << "\n"
#define pri3(x, y, z) cout << (x) << " " << (y) << " " << (z) << "\n"
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define kabe puts("---------------------------")
#define kara puts("")
#define debug(x) cout << " --- " << (x) << "\n"
#define debug2(x, y) cout << " --- " << (x) << " " << (y) << "\n"
#define debug3(x, y, z) cout << " --- " << (x) << " " << (y) << " " << (z) << "\n"
#define X first
#define Y second
#define eps 0.0001
#define prid(x) printf("%.15lf\n", x)

int a[1000];

signed main(void){
  int i, j;
  for(int testcase = 0;testcase >= 0;testcase++){
    int(n);
    rep(i, n)scanf("%d", a+i);
    sort(a, a + n);
    double res = 0.0;
    rep1(i, n){
      int t, b = a[i] - a[i - 1];
      if(i == n - 1)t = a[n - 3] + a[n - 4];
      else if(i == n - 2)t = a[n - 1] + a[n - 4];
      else t = a[n - 1] + a[n - 2];
      res = max(res, (double)t / (double)b);
    }
    prid(res);

/*/

//*/ break;
  }
  return 0;
}

Measured memory_bytes: 3272
#include<cmath>
#include<cstdio>
using namespace std;
int main() {
	int Q;
	scanf("%d",&Q);
	while(Q--){
		long long a,b,pr,t,ans;
		scanf("%lld %lld",&a,&b);
		pr=a*b;
		t=sqrt(pr);
		if(t*t+t<pr)
			ans=t*2-1;
		else if(t*t==pr) {
			ans=(t-1)*2;
			if(a!=b) ans--;
		} else
			ans=(t-1)*2;
		printf("%lld\n",ans);
	}
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>

int main() {
  int city, road, temp1, temp2;
  
  std::cin >> city >> road;
  
  std::vector<int> x(city, 0);
  
  for(int i = 0; i < road; i++) {
    std::cin >> temp1 >> temp2;
    x.at(temp1 - 1)++;
    x.at(temp2 - 1)++;
  }
  
  for (int i = 0; i < city; i++) {
    std::cout << x.at(i) << std::endl;
  }
  
  return 0;
}


Measured memory_bytes: 256