akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define SORT(c) sort((c).begin(), (c).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
#define ANS(ans) cout << (ans) << endl;
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
typedef vector<int> VI;
typedef pair<int, int> P;

// repetition
//------------------------------------------
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define REP(i, n) for (long long i = 0; i < (n); ++i)

int main() {
  int n;
  cin >> n;

  map<int, ll> mp;
  int tmp;
  ll sum = 0;
  REP(i, n) {
    cin >> tmp;
    sum += tmp;
    auto itr = mp.find(tmp);
    if (itr != mp.end()) {
      mp[tmp]++;
    } else {
      mp[tmp] = 1;
    }
  }

  int Q;
  cin >> Q;

  int b, c;
  REP(i, Q) {
    cin >> b >> c;
    ll count_b = mp[b];
    sum = sum + count_b * c - count_b * b;

    auto itr = mp.find(c);
    if (itr != mp.end()) {
      mp[c] += mp[b];
      mp[b] = 0;
    } else {
      mp[c] = mp[b];
      mp[b] = 0;
    }
    ANS(sum);
  }
  return 0;
}


Measured memory_bytes: 9436
A = int(input())
B = int(input())
C = int(input())
X = int(input())

counter = 0
for a in range(0, A+1):
    for b in range (0, B+1):
        for c in range(0, C+1):
            sum = a*500 + b*100 + c*50
            if sum == X:
                counter += 1

print(counter)

Measured memory_bytes: 3064
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 500000+2
int n,m;
long long g=0;
int jl[MAXN];
int t[MAXN];
void input(){
	cin>>n;
	for(int i=0;i<n;++i){
		cin>>jl[i];
	}
}
void gb(int* A,int x,int y,int* T){
    if(y-x>1){
    	int m=(x+y)/2;
    	int p=x,q=m,i=x;
    	gb(A,x,m,T);
    	gb(A,m,y,T);
    	while(p<m||q<y){
    		if(q>=y||(p<m&&A[p]<=A[q])) T[i++]=A[p++];
    		else T[i++]=A[q++];
    		g++;
    	}
    	for(i=x;i<y;++i){
    	    A[i]=T[i];
	    }
    }
    return;
}
int main(){
	input();
	gb(jl,0,n,t);
	for(int i=0;i<n-1;++i){
		cout<<jl[i]<<" ";
	}
	cout<<jl[n-1]<<endl;
	cout<<g<<endl;
}

Measured memory_bytes: 6884
// Problem : E - Yutori
// Contest : AtCoder Beginner Contest 161
// URL : https://atcoder.jp/contests/abc161/tasks/abc161_e
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//QWsin
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define out(i,u) for(int i=first[u];i!=-1;i=nxt[i])
#define repvc(i,vc) for(int i=0,Sz=vc.size();i<Sz;++i)
using namespace std;
inline int read()
{
	char ch=getchar();int ret=0,f=1;
	while(ch<'0' || ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	for(;ch>='0' && ch<='9';ch=getchar()) ret=ret*10+ch-'0';
	return ret*f;
}

typedef long long ll;
const int INF=1<<30;

const int maxn=400000+10;
char s[maxn];
int pre[maxn],suf[maxn];

int main()
{
	int n,k,c;cin>>n>>k>>c;
	scanf("%s",s+1);
	pre[1]=(s[1]=='o');
	rep(i,2,n) {
		pre[i]=pre[i-1];
		if(s[i]=='o'){
			if(pre[i-1]==0) pre[i]=1;
			else if(i-c-1>=1){
				pre[i]=max(pre[i],pre[i-c-1]+1);	
			}
		}
	}
	suf[n]=(s[n]=='o');
	for(int i=n-1;i>=1;--i){
		suf[i]=suf[i+1];
		if(s[i]=='o'){
			if(suf[i+1]==0) suf[i]=1;
			else if(i+c+1<=n){
				suf[i]=max(suf[i],suf[i+c+1]+1);
			}	
		}
	}
	for(int i=1;i<=n;++i)
		if(pre[i-1]+suf[i+1] < k && s[i]=='o'){
			cout<<i<<endl;
		}
	return 0;
}


Measured memory_bytes: 3328
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    private static Map<Character, Character> table = new HashMap<Character, Character>() {{
        put('A', 'T');
        put('T', 'A');
        put('G', 'C');
        put('C', 'G');
    }};
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.next();
        if(input.length() == 1)
            System.out.println(table.get(input.charAt(0)));
    }
}

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

#include <iostream>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <stdint.h>
#include <string.h>

#define _USE_MATH_DEFINES
#include <math.h>

#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <string>

#include <algorithm>
#include <functional>
#include <bitset>
#include <functional>
#include <chrono>
#include <random>

#define sqr(x) (x) * (x)

typedef unsigned int u32;
typedef int i32;
typedef unsigned long long int u64;
typedef long long int i64;
typedef uint16_t u16;
typedef int16_t i16;
typedef uint8_t u8;
typedef int8_t i8;

using namespace std;
using namespace std::chrono;

const i64 mod = 1'000'000'000ll + 7;
//const i64 smod = 998244353ll;

//const i64 inf = mod;

const long double eps = 1e-8;

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed); cerr.precision(15); cerr.setf(ios::fixed);

    i64 n;
    cin >> n;
    cout << (n + 1) % 2 << endl;

    return 0;
}

Measured memory_bytes: 3588
import functools
import fractions
N,S = map(int,input().split())
x = list(map(int,input().split()))
D = [0]*N
D[0] = S-x[0]

for i in range(1,N):
  D[i] = x[i] - x[i-1]
ddd=functools.reduce(fractions.gcd, D)
if ddd < 0:
  ddd *= -1
print(ddd)

Measured memory_bytes: 88172
#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define MOD 1e9+7
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=500000+5;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
template<typename T> inline T gcd(T&a,T&b){return b==0?a:gcd(b,a%b);}
template<typename T> inline T lcm(T&a,T&b){return a/gcd(a,b)*b;}
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
int n,k;
int a[1000];
void init(){

}
inline bool cmp(int a,int b){return a>b;}
int main(){
    read(n),read(k);
    for (int i=1;i<=n;i++) read(a[i]);
    sort(a+1,a+n+1,cmp);
    int sum=0;
    for (int i=1;i<=k;i++) sum+=a[i];
    printf("%d\n",sum);
    return 0;
}


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

int main()
{
	ios::sync_with_stdio(false);
	string s;
	long long n;
	cin>>n;

    while(n--)
    {
    	s=char(97+n%26)+s;
    	n/=26;
	}
	
	cout<<s<<endl;
	return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long
#define ull unsigned long long
#define si set <ll>
#define vi vector <ll>
#define popcount(x) __builtin_popcountll(x)
#define mii map <ll,ll>
#define vpi vector <pair <ll,ll> >
#define sz(c) (int)c.size()
#define fr first
#define ll long long
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sc second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define mem0(a) memset(a,0,sizeof(a))
#define rep(i,a,n) for(ll i=a ; i<n ; i++)
#define ld long double
#define rall(a) (a).rbegin(),(a).rend()
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
 
ll power(ll b,ll e,ll m)
{
  if(b==0) return 0;
  if(e==0) return 1;
  if(e&1) return b*power(b*b%m,e/2,m)%m;
  return power(b*b%m,e/2,m);
}
ll power( ll b, ll e)
{
  if(b==0) return 0;
  if(e==0) return 1;
  if(e&1) return b*power(b*b,e/2);
  return power(b*b,e/2);
}  
bool isPowerOfTwo(ll x)
{
    // x will check if x == 0 and !(x & (x - 1)) will check if x is a power of 2 or not
    return (x && !(x & (x - 1)));
}

ll a[2001]={0};

void solve()
{
    ll n;
    cin>>n;
    a[1]=0;
    a[2]=0;
    a[3]=1;
    a[4]=1;
    a[5]=1;
    for(ll i=6;i<=2000;i++)
        a[i]=(a[i-1]+a[i-3])%MOD;
    cout<<a[n];
}

int main()
{
  ll tt=1;
  // cin>>tt;
  while(tt--)
  {
    solve();
    cout<<"\n";
  }
}

Measured memory_bytes: 3628
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdint.h>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-12;
static const double PI = acos(-1.0);
static const ll MOD = 1000000007;

#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(a) (a).begin(), (a).end()
#define DEBUG(x) cout << #x << ": " << x << endl

void solve(long long N, long long M, long long Q, std::vector<long long> a,
           std::vector<long long> b, std::vector<long long> c,
           std::vector<long long> d) {
  vector<bool> v = {};
  REP(i, N) { v.push_back(false); }
  REP(i, M - 1) { v.push_back(true); }
  ll max_ = 0;
  do {
    vector<ll> A;
    ll cur = 1;
    REP(i, v.size()) {
      if (v[i]) {
        cur++;
      } else {
        A.push_back(cur);
      }
    }
    ll sum = 0;
    REP(i, Q) {
      if (A[b[i] - 1] - A[a[i] - 1] == c[i]) {
        sum += d[i];
      }
    }
    max_ = max(max_, sum);
  } while (next_permutation(ALL(v)));
  cout << max_ << endl;
}

int main() {
  long long N;
  scanf("%lld", &N);
  long long M;
  scanf("%lld", &M);
  long long Q;
  scanf("%lld", &Q);
  std::vector<long long> a(Q);
  std::vector<long long> b(Q);
  std::vector<long long> c(Q);
  std::vector<long long> d(Q);
  for (int i = 0; i < Q; i++) {
    scanf("%lld", &a[i]);
    scanf("%lld", &b[i]);
    scanf("%lld", &c[i]);
    scanf("%lld", &d[i]);
  }
  solve(N, M, Q, std::move(a), std::move(b), std::move(c), std::move(d));
  return 0;
}


Measured memory_bytes: 3224
N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]
adjs = [list() for _ in range(N)]

def search(i, mem, a, b):
    if mem[i]:
        return 0
    cnt = 1
    mem[i] = True
    for x in adjs[i]:
        if (i == a and b == x) or (i == b and x == a):
            continue
        cnt += search(x, mem, a,b)
    return cnt

for a, b in edges:
    adjs[a-1].append(b-1)
    adjs[b-1].append(a-1)
ans = 0
for a, b in edges:
    mem = [False for _ in range(N)]
    if search(0, mem, a-1, b-1) < N:
        ans += 1
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	long long N, M;
	cin >> N >> M;
	vector<pair<long long, long long>>Prices(N);
	for (int i = 0; i < N; i++) cin >> Prices[i].first >> Prices[i].second;
	sort(Prices.begin(), Prices.end());
	long long ans = 0;
	int num = 0;
	for (int i = 0; i < N; i++) {
		if (num + Prices[i].second < M) {
			ans += Prices[i].first * Prices[i].second;
			num += Prices[i].second;
		}
		else {
			ans += Prices[i].first * (M - num);
			break;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string cal_p(string str) {
	vector<int> ns;
	for (int i = 0; i < str.length(); ++i) {
		if (str[i] != ' ') {
			int len = 0;
			while (str[i+len] != ' ') {
				++len;
			}
			ns.push_back(stoi(str.substr(i,len)));
			i += len;
		}
	}
	sort(ns.begin(),ns.end());
	int sum = 0;
	for (int i = 0; i < (ns.size()+1)/2; ++i) {
		sum += ns[i];
	}
	return to_string(sum);
}

int main(void) {
	int n;
	cin >> n;
	for (int q = 0; q < n; ++q) {
		string str;
		cin >> str;
		string norm = "";
		int deep = 0;
		for (int i = 0; i < str.length(); ++i) {
			if (str[i] == '[') {
				deep = 0;
				continue;
			}
			else if (str[i] == ']') {
				norm += " ";
				++deep;
			}
			else {
				deep = 0;
				int len = 0;
				while (str[i+len] != ']') {
					++len;
				}
				norm += to_string((stoi(str.substr(i,len))/2)+1);
				i += len-1;
			}
		}

		for (int time = 0; time < deep-1; ++time) {
			int ind = 0;
			int len = 0;
			bool sp = false;
			string next = "";
			string temp = "";
			while (ind < norm.length()) {
				if (norm[ind] == ' ') {
					if (sp) {
						len = 0;
						next += cal_p(temp);
						while (ind < norm.length() && norm[ind] == ' ') {
							next += norm[ind];
							++ind;
						}
						--ind;
						temp = "";
						sp = false;
					}
					else {
						temp += norm[ind];
						++len;
						sp = true;
					}
				}
				else {
					sp = false;
					temp += norm[ind];
					++len;
				}
				++ind;
			}
			norm = next + " ";
		}
		string res = "";
		for (int i = 0; norm[i] != ' '; ++i) {
			res += norm[i];
		}
		cout << res << endl;
	}
	return 0;
}



Measured memory_bytes: 3300
/*=======================
Author    : Shounak Dey
Filename  : b.cpp
=======================	*/

#include<bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;

#define PB push_back
#define MK make_pair 
#define SZ(a) (int)(sizeof(a))
#define F first
#define S second
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,n) for(int i=0;i<n;i++)
#define read(n) scanf("%d",&n)
#define readl(n) scanf("%lld",&n)
#define readul(n) scanf("%llu",&n);


#define SORTV(a) sort(a.begin(),a.end())
#define TEST int Test;cin >> Test;while(Test--)
#define gcd(a,b) __gcd(a,b)
#define ffs(a) __builtin_ffs(a) // find first set
#define clz(a) __builtin_clz(a) // count leading zeroes
#define ctz(a) __builtin_ctz(a) // count trailing zeroes
#define popc(a) __builtin_popcount(a) // count set bits
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)


#define error(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }

vector<string> split(const string& s, char c) {
	vector<string> v;
	stringstream ss(s);
	string x;
	while (getline(ss, x, c))
		v.emplace_back(x);
	return move(v);
}

void err(vector<string>::iterator it) {}
template<typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
	cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n';
	err(++it, args...);
}

int main()
{
	fast_io;
	string a;
	cin >> a;
	ll l=0,r=a.length()-1;
	ll c=0;
	while(l<=r){
		c += (a[l]!=a[r]);
		l++;
		r--;
	}	
	cout << c << endl;
	return 0;
}

Measured memory_bytes: 256
def slove():
    import sys
    input = sys.stdin.readline
    d, n = list(map(int, input().rstrip('\n').split()))
    m = 100 ** d
    t = m
    cnt = 0
    while True:
        tt = t // m
        if tt % 100 != 0:
            cnt += 1
        if cnt == n:
            print(t)
            exit()
        t += m


if __name__ == '__main__':
    slove()


Measured memory_bytes: 38384
n,m,x,y=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
a.sort()
b.sort()
if a[-1]>=b[0]:
  print("War")
  exit()
if x<b[0]<=y:
  print("No War")
else:
  print("War")

Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include <cmath>
#include <limits>
#include <utility>
#include <map>

#define rep(p,q) for(int i = p;i < q;i++)

using namespace std;

const int cons = 1e9 + 7;
/*
//B

int main(void) {
	int a, b, c, d, e;
	cin >> a >> b >> c >> d >> e;
}
*/


//A

int main(void) {
	string ans = "Yay!";
	int a, b, c, d, e,k;
	int n[5];
	cin >> n[0] >> n[1] >> n[2] >> n[3] >> n[4] >>k;

	rep(0, 4) {
		for (int j = i + 1; j < 5; j++) {
			if (abs(n[i] - n[j]) > k) {
				ans = ":(";
				break;
			}
		}
		if (ans == ":(") break;
	}
	cout << ans << endl;



}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
using namespace std;
using ll = long long;
using P = pair<int, int>;


int main(){
    string s;
    cin >> s;
    int n = s.size();
    vector<int> v(n);
    rep(i, n-1){
        if(s[i] == 'R' && s[i+1] == 'L'){
            v[i] = 1;
            v[i+1] = 1;
        }
    }

    int r = 0;
    rep(i, n){
        if(v[i] != 0){
            v[i] += r;
            r = 0;
        }
        else if(s[i] == 'R') r++;
    }

    int l = 0;
    rep(i, n){
        if(v[n-i-1] != 0){
            v[n-i-1] += l;
            l = 0;
        }
        else if(s[n-i-1] == 'L') l++;
    }

    for(int i=0; i<n-1; i++){
        if(v[i] != 0 && v[i+1] != 0 && v[i]%2 == v[i+1]%2){
            int s = v[i] + v[i+1];
            v[i] = s/2;
            v[i+1] = s/2;
            i++;
        }
        else if(v[i] != 0 && v[i+1] != 0 && v[i]%2 != v[i+1]%2){
            int ma = max(v[i]-1, v[i+1]-1);
            int s = v[i] + v[i+1];
            if(v[i] < v[i+1]){
                v[i] = s/2;
                v[i+1] = s/2 + 1;
            }
            else {
                v[i] = s/2 + 1;
                v[i+1] = s/2;
            }
            if(ma%2 == 1) swap(v[i], v[i+1]);
            i++;
        }
    }


    rep(i, n) cout << v[i] << " ";
    cout << endl;


}

Measured memory_bytes: 1024
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n = I()
        if n == 0:
            break
        a = LS()
        r = 'TIE'
        d = collections.defaultdict(int)
        for i in range(n):
            d[a[i]] += 1
            s = sorted(list(d.items()) + [('-', 0)], key=lambda x: [-x[1]])
            if s[0][1] - s[1][1] > n - i - 1:
                r = '{} {}'.format(s[0][0], i+1)
                break

        rr.append(r)

    return '\n'.join(map(str, rr))


print(main())




Measured memory_bytes: 9128
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define poi 500000
#define inf 0x3f3f3f3f
using namespace std;
inline int re()
{
	char c=(char)getchar();
	int x=0,k=1;
	while(c<'0'||c>'9')
	{if(c=='-')k=-1;c=(char)getchar();}
	while(c>='0'&&c<='9')
	{x=(x<<1)+(x<<3)+c-'0';c=(char)getchar();}
	return k<0?-x:x;
}
void wr(int x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) wr(x/10);
	putchar(x%10+'0');
}
int main()
{
	int n=re(),ans=0;
	while(n)
	{
		if(n%10==2) ans++;
		n/=10;
	}
	wr(ans);
	return 0;
}
/*

*/

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        long b = scan.nextLong();
        long n = scan.nextLong();
        long x = Math.min(n, b - 1);
        System.out.println((a * x / b) - a * (x / b));
    }
}

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

using ll = long long;
#define ld long double
#define ull unsigned long long int

#define rep(i, n) for (int i = 0; i < (int)(n); i++)  // (i, 10) i=0～i=9まで
#define repr(i, n) for (int i = n; i >= 0; i--)   // (i, 10) i=10～i=0まで
#define FOR(i, m, n) for (int i = m; i < n; i++)  // (i, 3, 10) i=3～i=9まで
#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define ret return

typedef pair<int, int>    pii;
typedef vector<int>       vi;
typedef vector<vi>        vii;
typedef vector<long long> vl;

// 総数を1000000007で割った余り
const long long mod = 1e9 + 7;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

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

    // 入力
    int n;
    cin >> n;
    int a[n];
    rep(i, n) { cin >> a[i]; }

    // 処理
    sort(a, a + n, greater<int>());
    // check
    // rep(i, n) {
    //     if (i > 0) cout << " ";
    //     cout << a[i];
    // }
    int cnt = 0;
    rep(i, n - 1) {
        if (a[i] > a[i + 1]) {
            cnt++;
        }
    }

    // 出力
    cout << cnt + 1 << endl;

    return 0;
}


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

int main(){
    long long ans=0,sum=0;
    string s;
    cin >>s;

    for (int i = s.length()-1; i >= 0; --i){
        if(s[i]=='W')sum++;
        else ans += sum;
    }

    //cout <<fixed<<setprecision(16)<< << endl;
    cout << ans << endl;

    //if(flag==1)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 640
#include <cstdio>
#include <cmath>

using namespace std;

int main()
{
	int n,t,a;
	scanf("%d %d %d",&n,&t,&a);

	double min=1000;

	int h,ans;
	for(int i=0;i<n;i++){
		scanf("%d",&h);
		if(abs(t-0.006*h-a)<min){
			min=abs(t-0.006*h-a);
			ans=i+1;
		}
	}

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

	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i=0;i<=n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define double long double
using namespace std;
signed main(){
  int a,b;
  cin>>a>>b;
  int d=0;
  rep(i,a){
  rep(j,a){
    int c=b-i-j;
  if(0<=c&&c<=a)
    d++;
  }
  }
  cout<<d<<endl;
}

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

using namespace std;

int main()
{
  int n;
  double r, s, t, a[2];
  bool f = false;

  while(1){
    a[0] = a[1] = 0;
    for(int j = 0; j <= 1; j++){
      cin >> n;
      if(n == 0){
	f = true;
	break;
      }
      s = 360.0;
      for(int i = 0; i < n-1; i++){
	cin >> r;
	s -= r;
	a[j] += sin(r/180.0*M_PI);
      }
      a[j] += sin(s/180.0*M_PI);
    }
    if(f){
      break;
    }
    if(a[0] == a[1]){
      t = 0;
    } else if(a[0] > a[1]){
      t = 1;
    } else {
      t = 2;
    }
    cout << t << endl;
  }


  return 0;
}

Measured memory_bytes: 0
#include<stdio.h>

int main(void)
{
	int a,b,d,r;
	double f;

	scanf("%d %d", &a,&b);
	d = a / b, r = a%b, f = (double)a / b;
	printf("%d %d %lf\n",d,r,f );

	return 0;
}


Measured memory_bytes: 2100
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
constexpr int MOD = 1000000007;
constexpr int INF = numeric_limits<int>::max() / 2;
typedef pair<int,int> P;
using Graph = vector<vector<int>>;


signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	string S, T;
	cin >> S >> T;
	rep(i,N){
		int ans = 0;
		rep(j,N){
			if(S[j+i] == T[j]){
				++ans;
			}
			else break;
			if(i+j == N-1){
				cout << 2*N-ans << endl;
				return 0;
			} 
		}
	}
	cout << 2*N << endl;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)
#define REPi(i, a, b) for(int i=int(a); i<int(b); i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll MOD = 1e9+7;

const int MAX_N = 2000000;

ll fact[MAX_N+100];
ll frev[MAX_N+100];

ll rev(ll a, ll p){
    if(p == 0) return 1;
    ll tmp = rev(a, p/2);
    tmp = tmp * tmp % MOD;
    if(p % 2 == 1) tmp = tmp * a % MOD;
    return tmp;
}


void calc_fact(){
    fact[0] = frev[0] = 1;
    for(int i = 1; i <= MAX_N; i++){
        fact[i] = (fact[i-1] * i) % MOD;
        frev[i] = rev(fact[i], MOD-2);
    }
}


ll comb(int n, int k){
    if(n < 0 || k < 0 || n < k) return 0;
    if(n == 0 || k == 0) return 1;
    return fact[n] * frev[k] % MOD * frev[n-k] % MOD;
}


int main(){
    ll X, Y;
    cin >> X >> Y;

    if((2*Y - X) % 3 != 0){
        cout << 0 << endl;
        return 0;
    }
    if((2*X - Y) % 3 != 0){
        cout << 0 << endl;
        return 0;
    }

    ll A = (2*Y - X)/3;
    ll B = (2*X - Y)/3;

    fact[0] = frev[0] = 1;
    for(int i = 1; i <= MAX_N; i++){
        fact[i] = (fact[i-1] * i) % MOD;
        frev[i] = rev(fact[i], MOD-2);
    }

    ll ans = comb(A+B, A);

    cout << ans%MOD << endl;
    return 0;
}


Measured memory_bytes: 31616
#include <bits/stdc++.h>
using namespace std;
using P=pair<int64_t,int64_t>;

vector<int64_t> ds(vector<int64_t>dis,vector<vector<pair<int64_t,int64_t>>> g,int start,int goal){
    int n=dis.size();
    priority_queue<pair<int64_t,int64_t>,vector<pair<int64_t,int64_t>>,greater<pair<int64_t,int64_t>>> Q;
    dis[start]=0;
    Q.push(make_pair(0,start));

    while(!Q.empty()){
        int pos=Q.top().second;Q.pop();
        for(int i=0;i<g.at(pos).size();i++){
            int to=g.at(pos).at(i).first;
            int cost=g.at(pos).at(i).second;
            if(dis[to]==-1 || dis[to]>dis[pos]+cost){
                dis[to]=dis[pos]+cost;
                Q.push(make_pair(dis[to],to));
            }
        }
    }
    return dis;
}

int main(){
    int x,y; cin>>x>>y;

    int b=y-2*x;
    if(b<0){
        cout<<"No"<<endl;
        return 0;
    }

    if(b%2==1){
        cout<<"No"<<endl;
        return 0;
    }

    b/=2;
    int a=x-b;

    if(a<0){
        cout<<"No"<<endl;
        return 0;
    }

    cout<<"Yes"<<endl;
}

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

int N, K;
int W[100001]; //W[i] : i番目の荷物の重さ( 0-origin )

int check( long long p ){
  int i = 0;
  for( int j = 0; j < K; j++ ){   //1台のトラックにp以下の荷物を積んでいく
    long long sum = 0;
    while( sum + W[i] <= p ){
      sum += W[i];
      i++;
      if( i >= N )  return true;
    }
  }
  return false;
}

long long solve(){
  //2分法( left, right ] : left:okの境界，right:ngの境界
  //0～100000*10000(制約内での最大積載量)で検査する

  long long left = 0, right = 100000*10000+1;
  long long mid;

  while( left < right ){
    mid = (left + right)/2;
    if( check(mid) ){
      //ok
      right = mid;
    } else {
      //ng
      left = mid+1;
    }
  }
  return left;
}

int main()
{
  std::cin >> N >> K;
  for( int i = 0; i < N; i++ ){
    std::cin >> W[i];
  }

  long long ans = solve();
  std::cout << ans << std::endl;

  return 0;
}


Measured memory_bytes: 3488
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
const double PI = acos(-1);
const double EPS = 1e-9;
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 (a > b) { a = b; return true; } return false; }

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, M; cin >> N >> M;
	vector<int>v(N, 0);
	rep(i, 0, M) {
		int a, b; cin >> a >> b;
		a--, b--;
		v[a]++, v[b]++;
	}
	rep(i, 0, N)cout << v[i] << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = (int)1e9 + 7;
const int INF = (int)100100100;

int main() {
    ll N; cin >> N;
    //ll N,M; cin >> N >> M;
    //string S; cin >> S;
    //ll H,W; cin >> H >> W;
    int max=0;
    int mab;
    for(int i=0;i<N;i++){
        int a,b;
        cin >> a >> b;
        if(a>max){
            max=a;
            mab=b;
        }
    }
    


    cout << max+mab << endl;
}

/*



 */


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

#define ms(a,b) memset(a, b, sizeof(a))
#define rep(a,b,c) for(int a = (int)(b); a < (int)(c); a++)
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define m_p(a,b) make_pair(a, b)
#define lson l,mid,o << 1
#define rson mid + 1,r,o << 1 | 1
#define ls o << 1
#define rs o << 1 | 1
#define inf 0x3f3f3f3f

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

inline bool isdigit(char& ch) {
	return ch >= '0' && ch <= '9';
}
template<class T>
void read(T &x) {
	x = 0;
	ll f = 1;char ch = getchar();
	for (;!isdigit(ch);ch = getchar()) 
		if (ch == '-') f = -1;
	for (; isdigit(ch);ch = getchar())
		x = (x << 1) + (x << 3) + ch - '0';
	x *= f;
}
template<class T>
inline void write(T x) {
	if (x == 0) {putchar('0');return ;}
	if (x < 0) {putchar('-');x = -x;}
	int _stk[65],_top = 0;
	for (;x;x /= 10) _stk[++_top] = x % 10 + 48;
	for (;_top;_top--)putchar(_stk[_top]);
}


int main () {
	long double s, t;
	cin >> s >> t;
	s *= t;
	ll sum = (ll)s;
	cout << sum;
	return 0;
}

Measured memory_bytes: 3792
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int compare_int(const void *a, const void *b)
{
  return *(int *)a - *(int *)b;
}

int main(void)
{
  int i, j;
  //  dic_t dic[200000];
  int min, max;
  int len, flg;
  int cnt, maxcnt;
  int  aa,bb,cc,dd,ee;
  scanf("%d %d", &aa,&bb);
//  printf("%d %d\n", aa,bb);

  if(bb == 0){
    printf("0\n");
    return 0;
  }
  for(i=1;i<1000000;i++){
    cc = i*0.08;
    dd = i*0.1;
//    printf("cc%d dd%d\n", cc,dd);
    if((aa == cc) && (bb == dd)){
      printf("%d\n",i);
      return 0;
    }
  }
  printf("-1\n");
  return 0;


}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();

        int ans = 0;
        for (int a = 1; a <= k; a++) {
            for (int b = 1; b <= k; b++) {
                for (int c = 1; c <= k; c++) {
                    ans += gcd(a, b, c);
                }
            }
        }

        System.out.println(ans);
    }

    public static int gcd(int a, int b, int c) {
        return gcd(a, gcd(b, c));
    }

    public static int gcd(int x, int y) {
        int ret = 0;
        if (x % y == 0) return y;
        else {
            int z = x % y;
            ret = gcd(y, z);
        }
        return ret;
    }
}

Measured memory_bytes: 35744
#include <bits/stdc++.h>
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
#define e_b emplace_back
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
using namespace std;
using ll = long long;
using ld = long double;
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}

int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int a,b,c,k;
  cin >> a >> b >> c >> k;

  int cnt=0;
  while(b<=a){
    b*=2;
    cnt++;
  }
  while(c<=b){
    c*=2;
    cnt++;
  }
  if(cnt<=k)  cout << "Yes" << endl;
  else  cout << "No" << endl;

  return 0;
}

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

using namespace std;

using int64 = long long;

namespace FastFourierTransform
{
  using C = complex< double >;

  void DiscreteFourierTransform(vector< C > &F, bool rev)
  {
    const int N = (int) F.size();
    const double PI = (rev ? -1 : 1) * acos(-1);
    for(int i = 0, j = 1; j + 1 < N; j++) {
      for(int k = N >> 1; k > (i ^= k); k >>= 1);
      if(i > j) swap(F[i], F[j]);
    }
    C w, s, t;
    for(int i = 1; i < N; i <<= 1) {
      for(int k = 0; k < i; k++) {
        w = std::polar(1.0, 2 * PI / (i * 2) * k);
        for(int j = 0; j < N; j += i * 2) {
          s = F[j + k], t = F[j + k + i] * w;
          F[j + k] = s + t, F[j + k + i] = s - t;
        }
      }
    }
    if(rev) {
      double temp = 1.0 / N;
      for(int i = 0; i < N; i++) F[i] *= temp;
    }
  }

  vector< int64 > Multiply(const vector< int > &A, const vector< int > &B)
  {
    int sz = 1;
    while(sz <= A.size() + B.size()) sz <<= 1;
    vector< C > F(sz), G(sz);
    for(int i = 0; i < A.size(); i++) F[i] = A[i];
    for(int i = 0; i < B.size(); i++) G[i] = B[i];
    DiscreteFourierTransform(F, false);
    DiscreteFourierTransform(G, false);
    for(int i = 0; i < sz; i++) F[i] *= G[i];
    DiscreteFourierTransform(F, true);
    vector< int64 > X(A.size() + B.size() - 1);
    for(int i = 0; i < A.size() + B.size() - 1; i++) X[i] = F[i].real() + 0.5;
    return (X);
  }
};

int main()
{
  int N, M, Q, A[40001], B[40001], C[100000];
  vector< int > F(200001), G(200001);

  scanf("%d %d %d", &N, &M, &Q);
  for(int i = 0; i < N; i++) scanf("%d", &A[i + 1]), A[i + 1] += A[i];
  for(int i = 0; i < M; i++) scanf("%d", &B[i + 1]), B[i + 1] += B[i];
  for(int i = 0; i < Q; i++) scanf("%d", &C[i]);

  for(int i = 1; i <= N; i++) {
    for(int j = 0; j < i; j++) {
      ++F[A[i] - A[j]];
    }
  }
  for(int i = 1; i <= M; i++) {
    for(int j = 0; j < i; j++) {
      ++G[B[i] - B[j]];
    }
  }
  reverse(begin(G), end(G));
  auto X = FastFourierTransform::Multiply(F, G);
  for(int i = 0; i < Q; i++) {
    if(C[i] == 0) printf("%lld\n", X[200000]);
    else printf("%lld\n", X[200000 - C[i]] + X[200000 + C[i]]);
  }
}

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

using namespace std;

#define int long long
#define INT int
#define MOD 1000000007

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
template <typename T>
void print(T x)
{
    std::cout << x << '\n';
}
typedef long long ll;

signed main()
{
    int n;
    cin >> n;

    int n1 = n % 10;

    if (n1 == 3)
    {
        cout << "bon" << endl;
    }
    else if (n1 == 0 || n1 == 1 || n1 == 6 || n1 == 8)
    {
        cout << "pon" << endl;
    }
    else
    {
        cout << "hon" << endl;
    }

    return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <iomanip>
#include <map>

#define REP(i, n ,N) for(ll i = (n); i < (N); i++)
//#define RREP(i, n ,N) for(ll i = (N-1); i >= (n); i--)
#define p(s) cout<<(s)<<endl
#define p2(a, b) cout<<(a)<<" "<<(b)<<endl

using namespace std;
typedef long long  ll;

const long long MOD = 1e9+7;

int main(){
    string s, t, u;
    int a, b;

    cin >> s >> t >> a >> b >> u;
    if(s == u){
        p2(a-1,b);
    } else {
        p2(a, b- 1);
    }
    return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
  private static class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;

    public FastScanner(InputStream in) {
      reader = new BufferedReader(new InputStreamReader(in));
      tokenizer = null;
    }

    public String next() {
      if (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public String nextLine() {
      if (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          return reader.readLine();
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }

      return tokenizer.nextToken("\n");
    }

    public long nextLong() {
      return Long.parseLong(next());
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }

    public double nextDouble() {
      return Double.parseDouble(next());
    }

    public int[] nextIntArray(int n) {
      int[] a = new int[n];
      for (int i = 0; i < n; i++)
        a[i] = nextInt();
      return a;
    }

    public long[] nextLongArray(int n) {
      long[] a = new long[n];
      for (int i = 0; i < n; i++)
        a[i] = nextLong();
      return a;
    }
  }

  public static void main(String[] args) {
    FastScanner sc = new FastScanner(System.in);
    int n = sc.nextInt();
    System.out.println(n % 2 == 1 ? n / 2 + 1 : n / 2);
  }
}

Measured memory_bytes: 21204
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

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 LIST(): return list(map(str, input().split()))
# def LIST(): return list(input())

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()


L = [0] * (86 + 1)
L[0] = 2
L[1] = 1
for i in range(2, N + 1):
    L[i] = L[i-1] + L[i-2]

print(L[N])

    

Measured memory_bytes: 5156
#include <bits/stdc++.h>
#define inp_out_work ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define testCase    int T; cin>>T; while(T--)
#define fr(i,n) for(int i=0;i<n;i++)
#define fro(i,s,e) for(int i=s;i<=e;i++)
#define endl '\n'
#define debug(P) cout<<#P<<" = "<<P<<endl;
#define pb push_back
#define FILE freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);


using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;
const int NAX = 100001;

vector<int> adj[NAX];
vector<ll> pref[NAX], suff[NAX];
int n, M;

ll dp1[NAX]; // no. of subtrees starting from this node toward downward
ll dp2[NAX]; // no. of subtrees starting from this node toward upward

// calculate dp1
void dfs1(int x, int p){
    dp1[x] = 1;
    for(int c : adj[x]){
        if(c!=p){
            dfs1(c, x);
            dp1[x] = (dp1[x]*(1+dp1[c]))%M;
            suff[x].pb(1+dp1[c]);
            pref[x].pb(dp1[x]);
        }
    }
    for(int i = suff[x].size()-2; i >= 0; i--){
        suff[x][i] = (suff[x][i] * suff[x][i+1])%M;
    }
}

void dfs2(int x, int p){
    int j = 0;
    for(int c : adj[x]){
        if(c != p){
            ll val = 1;
            if(j>0)val = (val * pref[x][j-1])%M;
            if(j+1<suff[x].size())val = (val * suff[x][j+1])%M;
            ++j;
            dp2[c] = (1 + dp2[x]*val)%M;
            dfs2(c,x);
        }
    }

}

int main(){
    cin>>n>>M;
    fr(i,n-1){
        int u, v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    dfs1(1, 0);
    dp2[1] = 1;
    dfs2(1,0);

    fro(i,1,n){
        cout<< dp1[i]*dp2[i]%M << endl;
    }

}


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

int main() {
	int n,i;
	cin>>n;
	int arr[n+1],dp[n+1]={0};
	for(i=1;i<=n;i++)
	cin>>arr[i];
	dp[2]=max(arr[2],arr[1])-min(arr[2],arr[1]);
	for(i=3;i<n+1;i++)
	dp[i]+=min(dp[i-1]+max(arr[i],arr[i-1])-min(arr[i],arr[i-1]),dp[i-2]+max(arr[i],arr[i-2])-min(arr[i],arr[i-2]));
	cout<<dp[n];
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 998244353;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef pair<ll, ll> LP;
typedef vector<int> vec;
typedef vector<string> svec;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-8;

#define int long long

const int mn = 100000;
bool isok[mn + 1];
int ans[mn + 1];
void init() {
	rep1(i, mn) {
		int k = sqrt(i + 0.01);
		int pro = 1;
		rep1(j, k) {
			if (i%j == 0) {
				if (j == (i / j)) {
					if (j != i) {
						pro = pro * j;
						if (pro > 2 * mn)pro = 2 * mn + 1;
					}
				}
				else {
					if (j != i) {
						pro = pro * j;
						if (pro > 2 * mn)pro = 2 * mn + 1;
					}
					if ((i / j) != i) {
						pro = pro * (i/j);
						if (pro > 2 * mn)pro = 2 * mn + 1;
					}
				}
			}
		}
		isok[i] = (pro >= 2 * i);
	}
	rep1(i, mn) {
		ans[i] = ans[i - 1];
		if (isok[i])ans[i]++;
	}
}
void solve() {
	init();
	int q; cin >> q;
	rep(i, q) {
		int n; cin >> n; cout << ans[n] << endl;
	}
}

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

	//cout << fixed << setprecision(10);
	//init();
	solve();
	//stop
	return 0;
}



Measured memory_bytes: 4080
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#define lowbit(x) x & (-x)
using namespace std;

inline int read() {
	int f = 1, x = 0;
	char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-')	f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * f;
}

int n, x, a[100007], c[200007], s[100007], l, r;

inline void update(int x, int v) {
	for(; x <= 200006; x += lowbit(x))
		c[x] += v;
}
inline int sum(int x) {
	int res = 0;
	for(; x; x -= lowbit(x))
		res += c[x];
	return res;
}
inline bool check(int x) {
	memset(c, 0, sizeof(c));
	s[0] = 0;
	for(int i = 1; i <= n; ++i)
		s[i] = s[i - 1] + (a[i] >= x ? 1 : -1);
	long long su = 0;
	for(int i = 0; i <= n; ++i) {
		su += sum(s[i] + 100000);
		update(s[i] + 100000, 1);
	} 
	return su >= 1ll * n * (n + 1) / 4;
}

int main() {
	n = read();
	for(int i = 1; i <= n; ++i) {
		a[i] = read();
		r = max(r, a[i]);
	}
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(check(mid))	l = mid + 1;
		else	r = mid - 1;
	}
	printf("%d", r);
}

Measured memory_bytes: 1792
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <iomanip>	
#include <deque>
#include <set>
#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
#define fore(i,a) for(auto &i:a)
#define INF INT_MAX/2;
typedef long long ll;
using namespace std;
using vi = vector<int>;
using vll = vector<ll>;
ll mod = 1e9 + 7;
//ll llmax = 10000000000000000000ll;
using namespace std;
using Graph = vector<vector<int>>;


int cnt_digit(ll N)
{
	int digit = 0;

	while (N > 0)
	{
		N /= 10;
		digit++;
	}
	return digit;
}


 // 最大公約数計算
 
ll gcd(ll a, ll b)
{
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b);
	}
}
// 最小公倍数の計算

ll lcm(ll a, ll b)
{
	ll g = gcd(a, b);

	return a / g * b;
}

struct union_find
{
	vector<int> par, r;
	union_find(int n)
	{
		par.resize(n);
		r.resize(n);
		init(n);
	}


	void init(int n)
	{
		for (int i = 0; i < n; i++) par[i] = i;
		for (int i = 0; i < n; i++) r[i] = 0;
	}

	int find(int x)
	{
		if (par[x] == x)return x;
		else return find(par[x]);
	}

	void unite(int x, int y)
	{
		x = find(x);
		y = find(y);

		if (r[x] < r[y])
		{
			par[x] = y;
		}
		else
		{
			par[y] = x;
			if (r[x] == r[y])
			{
				r[x]++;
			}
		}
	}
};



int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
#define N 1000;
	int n, m;
	cin >> n >> m;
	vector<int> h(n), ma(n);
	rep(i, 0, n) {
		cin >> h[i];
		ma[i] = 0;
		
	}

	rep(i, 0, m) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		ma[a] = max(ma[a], h[b]);
		ma[b] = max(ma[b], h[a]);

	}

	int ans = 0;
	rep(i, 0, n) {
		ans += h[i] > ma[i];
	}
	
	cout << ans << endl;


	
	return 0;
}

Measured memory_bytes: 3980
fun main(args: Array<String>) {
  val n = readLine()!!.toInt()
  val r = IntArray(200000)

  for (i in 0 until n) {
    r[i] = readLine()!!.toInt()
  }

  var maxv = -2000000000
  var minv = r[0]

  for (i in 1 until n) {
    maxv = Math.max(maxv, r[i] - minv)
    minv = Math.min(minv, r[i])
  }

  println(maxv)
}



Measured memory_bytes: 45332
#include <bits/stdc++.h>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,a,b) for(int i=int(a);i>int(b);--i)
using namespace std;
using ll = long long;

int main()
{
  string S;
  cin >> S;
  int a;
  if(S=="SUN") a=7;
  else if(S=="MON") a=6;
  else if(S=="TUE") a=5;
  else if(S=="WED") a=4;
  else if(S=="THU") a=3;
  else if(S=="FRI") a=2;
  else if(S=="SAT") a=1;

  cout << a << "\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007, INF=(1LL<<60);
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int x, n;
    cin >> x >> n;
    int p[n];
    bool a[300];
    memset(a, 0, sizeof(a));
    for(int i=0;i<n;i++){
    	cin >> p[i];
        a[p[i] - x + 100] = true;
    }
    int idx = 0;
    while(1){
    	if(a[-idx+100]==false){
    		cout << x - idx << endl;
    		return 0;
    	}
    	if(a[idx+100]==false){
    		cout << x +idx << endl;
    		return 0; 
    	}
    	idx++;
    }
    return 0;
}


Measured memory_bytes: 3636
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T

main :: IO ()
main = do
  s <- T.getLine :: IO T.Text
  t <- T.getLine :: IO T.Text
  putStrLn $ if s `T.isPrefixOf` t && T.length s == T.length t - 1 then "Yes" else "No"


Measured memory_bytes: 3692
ls = [[int(x) for x in input().split()] for _ in range(3)]

flg = "Yes"

for i in range(2):
    if ls[0][i]-ls[0][i+1] == ls[1][i]-ls[1][i+1] and ls[0][i]-ls[0][i+1] == ls[2][i]-ls[2][i+1]:
        pass
    else:
        flg = "No"
print(flg)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <iomanip>
#include <math.h>
using namespace std;

int main(){
    int n,k;
    cin>>n>>k;
    int i,z,a,b,ans=0;
    for(i=0;i<n;i++){
        cin>>z;
        a=z*2;
        if(k>=z){
            b=(k-z)*2;
        }else{
            b=(z-k)*2;
        }
        if(a>=b){
            ans+=b;
        }else{
            ans+=a;
        }
    }
    cout<<ans<<endl;
        
    return 0;
}

Measured memory_bytes: 256