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

ll gcd(ll m, ll n){
    ll tmp;
    while(m%n){
        tmp = n;
        n = m % n;
        m = tmp;
    }
    return n;
}

ll lcm(ll m, ll n){
    return m / gcd(m, n) * n;
}

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

    int n;
    ll res;
    cin >> n >> res;

    rep1(i, n){
        ll t;
        cin >> t;
        res = lcm(res, t);
    }
    cout << res << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct state{
	int cur,mod,bef;
	state(int a,int b,int c){
		cur = a;
		mod = b;
		bef = c;
	}
};
const int INF = 100000000;
int fin;
vector<int>dist;
vector<int>graph[100005];
bool visited[3][100005];
void bfs(int curr,int mod,int before){
	visited[mod][curr] = true;
	queue<state>q;
	q.push(state(curr,mod,before));
	while(!q.empty()){
		int c = q.front().cur;
		int m = q.front().mod;
		int be = q.front().bef;
		q.pop();
		if(m==0) dist[c] = min(dist[c],dist[be]+1);
		for(int i=0; i<graph[c].size(); i++){
			int nxt = graph[c][i];
			int mm = (m+1)%3;
			if(!visited[mm][nxt]){
				visited[mm][nxt] = true;
				q.push(state(nxt,mm,(m?be:c)));
			}
		}
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	dist = vector<int>(n+1,INF);
	while(m--){
		int a,b;
		cin>>a>>b;
		graph[a].push_back(b);
	}
	int s;
	cin>>s>>fin;
	dist[s] = 0;
	bfs(s,0,s);
	if(dist[fin]==INF) cout<<-1;
	else cout<<dist[fin];
}

Measured memory_bytes: 9348
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPI(i,f,n) for(int i=(f);i<(n);++i)
using namespace std;
typedef long long ll;

// ソートして端から順に処理していく。
// 左端を対処する場合には、その端の位置+D に爆弾を置くのが最適。それより左の位置に
// おいてもいいことはないし、それより右の位置に置くと、左端に当たらなくなる。
// 置く個数は、左端モンスターの倒す回数分。
// 置いた爆弾の位置と個数を管理しておいて、左端から順にモンスターを見ていく。
// 爆弾の範囲内で、その個数で倒れるなら、何もする必要なし。
// 爆弾の範囲内で、その個数で倒れないなら、+D 位置に倒れる個数の爆弾を置く。
// 爆弾の範囲外なら、爆弾の情報を削除し、+D 位置に倒れる個数の爆弾を置く。
// 爆弾は queue で管理する？
// 	D = 2
// 	0 1 2 3 4 5 6 7 8
// 	H 
// 	----B----
// 
// 全モンスターのループが O(N) で、その中で毎回爆弾のキューを全部回しているので
// 最悪 O(N^2) になっているっぽい。
// 体力が0以下になったら、キューの探索を止めたら？
//  → TLE
//     多少減るんだろうけど、(2*10^5)^2 から多少減って1/10とか1/100になっても、
//     まだ間に合わないってことらしい。
// ちゃんと、ダメージを尺取りしないとダメか・・・
// 爆弾を置いたら、その個数をトータル個数に加算。
// 位置が爆弾範囲を超えてたら、その超えた爆弾の個数をトータルから引く。

int main() {
  ll N,D,A;
  cin >> N >> D >> A;
  vector< pair<ll,ll> > mon(N);
  REP(i,N) {
    cin >> mon[i].first >> mon[i].second;
    mon[i].second = (mon[i].second+A-1) / A;
  }
  sort( mon.begin(), mon.end() );
  deque< pair<ll,ll> > q;
  ll ans = 0;
  ll total = 0;
  REP(i,N) {
    while ( !q.empty() ) {
      auto nq = q.front();
      if ( nq.first < mon[i].first ) {
        total -= nq.second;
        q.pop_front();
      } else {
        break;
      }
    }
    mon[i].second -= total;
    if ( mon[i].second > 0 ) {
      q.emplace_back( mon[i].first + 2 * D, mon[i].second );
      ans += mon[i].second;
      total += mon[i].second;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 4992
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<map>
#include<queue>
#include<cmath>
#include<stack>
#include<vector>
#include<cstdio>
#define MAXN 33000
#define INF 0x3f3f3f3f
#define lmid l,m,rt<<1
#define rmid m+1,r,rt<<1|1
#define ls rt<<1
#define rs rt<<1|1
#define Mod 1000000007
#define i64 __int64
#define LIMIT_ULL 100000000000000000
#define LL long long
using namespace std;
typedef pair<long long,int>P;
struct node
{
     int v,w,next;
}s[200005];
int head[100005];
int cnt=1;
void add(int u,int v,int w)
{
     s[cnt].v=v;
     s[cnt].w=w;
     s[cnt].next=head[u];
     head[u]=cnt++;
}
long long dis[100005];
int vis[100005];
void dfs(int x)
{
     for(int i=head[x];~i;i=s[i].next)
     {
          int v=s[i].v,w=s[i].w;
          if(!vis[v])
          {
               dis[v]=min(dis[v],dis[x]+w);
               //cout<<dis[v]<<" "<<dis[x]<<" "<<w<<endl;
               vis[v]=1;
               dfs(v);
          }
     }
}
int main()
{
     memset(head,-1,sizeof(head));
     memset(vis,0,sizeof(vis));
     int n;
     scanf("%d",&n);
     for(int i=0;i<n-1;i++)
     {
          long long x,y,z;
          scanf("%lld %lld %lld",&x,&y,&z);
          add(x,y,z);
          add(y,x,z);
     }
     int q,k;
     scanf("%d%d",&q,&k);
     for(int i=1;i<=n;i++)
          dis[i]=100000000000000;
     dis[k]=0;
     dfs(k);
     for(int i=0;i<q;i++)
     {
          int a,b;
          scanf("%d%d",&a,&b);
          cout<<dis[a]+dis[b]<<endl;
     }
     return 0;
}


Measured memory_bytes: 8832
import string

count = {x: 0 for x in string.ascii_lowercase}
lines =''
while True:
    try:
        lines += input().lower()
    except EOFError:
        break

for c in lines:
    if 'a' <= c <= 'z':
        count[c] += 1

for key in string.ascii_lowercase:
    print("{0} : {1}".format(key,count[key]))

Measured memory_bytes: 8096
#include <bits/stdc++.h>
using namespace std;
//typedef long long ll;
int main() {
    int N;
    cin >> N;
    set<string> s;
    for (int i = 0; i < N; i++) {
        string S;
        cin >> S;
        s.insert(S);
    }
    cout << s.size() << "\n";
    return 0;
}

Measured memory_bytes: 19248
fn main(){
  let nm: Vec<usize> = read_vec();
  let n = nm[0];
  let m = nm[1];

  let mut sv: Vec<Vec<usize>> = vec![Vec::new(); m];
  
  for i in 0 .. m {
    let tv: Vec<usize> = read_vec();
    for j in 0 .. tv[0] {
      sv[i].push(tv[j+1]-1);
    }
  }

  let pv: Vec<usize> = read_vec();

  let mut ans: usize = 0;
  
  for l in 0 .. (1 << n) {
    let mut f: bool = true;
    for i in 0 .. m {
      let mut p = 0;
      for j in 0 .. sv[i].len() {
        if l & (1 << sv[i][j]) != 0 { p += 1; }
      }
      if p % 2 != pv[i] { f = false; break; }
    }
    if f {ans += 1;}
  }
  
  println!("{}", ans);
}

fn read_vec<T>() -> Vec<T>
  where T: std::str::FromStr,
        T::Err: std::fmt::Debug
{
  let mut buf = String::new();
  std::io::stdin().read_line(&mut buf).expect("failed to read");
  buf.split_whitespace().map(|e| e.parse().unwrap()).collect()
}


Measured memory_bytes: 4352
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)

int main() {
	ll n; cin >> n;
	string s; cin >> s;
	string t;

	ll cnt = 0;
	rep(i, 0, s.size()) {
		if (s[i] == '(') {
			t += s[i];
			cnt++;
		}
		else if (s[i] == ')') {
			t += s[i];
			cnt--;
		}
		if (cnt < 0) {
			t = '(' + t;
			cnt++;
		}
	}
	rep(i, 0, cnt) {
		t = t + ')';
	}
	cout << t << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
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;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;

vector<int> min_factor, prime;

void sieve(int n){
    min_factor.resize(n+1, 0);
    For(i, 2, n+1){
        if(min_factor[i] == 0){
            min_factor[i] = i;
            prime.push_back(i);
        }
        for(int x: prime){
            if(x*i > n || x > i) break;
            min_factor[x*i] = x;
        }
    }
}

bool is_prime(int x){
    return x > 1 && min_factor[x] == x;
}

vector<pii> prime_f(int n){
    vector<pii> ret;
    while(n > 1){
        if(ret.empty() || ret.rbegin()->fi != min_factor[n]){
            ret.emplace_back(min_factor[n], 1);
        }
        else ++ret.rbegin()->se;
        n /= min_factor[n];
    }
    return ret;
}

int main(){
    int n, m, s, t;
    scanf("%d%d%d%d", &n, &m, &s, &t);
    --s; --t;
    vector<int> G[n];
    rep(i, m){
        int a, b;
        scanf("%d%d", &a, &b);
        --a; --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    int d[n][2];
    rep(i, n)rep(j, 2) d[i][j] = mod;
    d[s][0] = 0;
    queue<pii> que;
    que.emplace(s, 0);
    while(!que.empty()){
        int v, p;
        tie(v, p) = que.front();
        que.pop();
        for(int nv: G[v])if(chmin(d[nv][p^1], d[v][p]+1)){
            que.emplace(nv, p^1);
        }
    }

    if(d[t][0] == 2){
        printf("%d\n", 2);
    }
    else if(d[t][1] == mod){
        printf("%d\n", -1);
    }
    else{
        sieve(MAX);
        for(int i=d[t][1]; i<MAX; i+=2){
            if(is_prime(i)){
                printf("%d\n", i);
                return 0;
            }
        }
    }
}


Measured memory_bytes: 10144
#include "bits/stdc++.h"
#define int long long
#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(obj) begin(obj), end(obj)
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define sqr(x) (x) * (x)
#define cube(x) (z) * (z) * (x)
#define LOWER_BOUND(A, key) distance(A.begin(), lower_bound(ALL(A), key))
#define UPPER_BOUND(A, key) distance(A.begin(), upper_bound(ALL(A), key))
#define itn int

using namespace std;
using ll      = long long;
const int MOD = (int)(1e9 + 7);
const int INF = (int)(1e13 + 7);

template <class T = int>
int in() {
  T x;
  cin >> x;
  return x;
}
unordered_map<int, int> element_num; //change type if you need
template <class T>
void counter(T container) {
  for (int i = 0; i < container.size(); i++) {
    element_num[container[i]] += 1;
  }
}
signed main() {
  int N = in();
  vector<int> A(N - 1);
  rep(i, N - 1) {
    cin >> A[i];
  }
  counter(A);
  rep(i, N) {
    cout << element_num[i + 1] << endl;
  }
}


Measured memory_bytes: 14536
from math import sqrt
n, d = map(int, input().split())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
sol = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        dist = 0
        for k in range(d):
            dist += pow(a[i][k] - a[j][k], 2)
        if sqrt(dist) == int(sqrt(dist)):
            sol += 1
print(sol)


Measured memory_bytes: 3064
#include <stdio.h>
int min(int a,int b);
int main(void) {
	int M,N,i,j,D[1001],C[1001],DP[1001][1001];
	scanf("%d %d",&N,&M);
	for(j=1;j<=N;j++) scanf("%d",&D[j]);
	
	for(i=0;i<=M;i++){
		for(j=0;j<=N;j++){
			DP[i][j] = 1000000001;
		}
	}
	
	for(i=1;i<=M;i++){
		scanf("%d",&C[i]);	
	}
	for(i=0;i<=M;i++){	
		DP[i][0]=0;
	}
	
	for(i=1;i<=M;i++){
		for(j=1;j<=N;j++){
			DP[i][j]=min(DP[i-1][j-1]+C[i]*D[j],DP[i-1][j]);
		}
	}
	printf("%d\n",DP[M][N]);

	return 0;
}

int min(int a,int b){
	if (a<b) return a;
	else return b;
}

Measured memory_bytes: 6568
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,s,n) for(int i=(s); i<(n); i++)
#define all(v) v.begin(),v.end()
#define outve(v) for(auto i : v) cout << i << " ";cout << endl
#define outmat(v) for(auto i : v){for(auto j : i) cout << j << " ";cout << endl;}
#define in(n,v) for(int i=0; i<(n); i++){cin >> v[i];}
#define out(n) cout << (n) << endl
#define fi first
#define se second
#define pb push_back
#define mod 1000000007
#define infi 1900000000
#define infl 1100000000000000000
#define cyes cout << "Yes" << endl
#define cno cout << "No" << endl
#define csp << " " <<
#define outset(n) cout << fixed << setprecision(n);
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T> using ve = vector<T>;
template<typename T> using pq2 = priority_queue<T>;
template<typename T> using pq1 = priority_queue<T,vector<T>,greater<T>>;




int main()
{
    int a,b;
    cin >> a >> b;
    cout << ((a+b>=10) ? "error" : to_string(a+b))<< endl;

    
    
    
    

    return 0;
}


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

typedef long long ll;

bool func(string s){
  for(int i=0; i<s.length()-1; i++){
    if(s[i]!=s[i+1]) return false;
  }
  return true;
}


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

  for(int i=N; i<=999; i++){
    if(func(to_string(i))){
      cout << i << endl;
      return 0;
    }
  }

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000 * 1000 * 1000 + 7;
const int INF = MOD;
const int N = 101;
int mod(int n) {
    return (n % MOD + MOD) % MOD;
}   
int fp(int a, int p) {
    int ans = 1, cur = a;
    for (int i = 0; (1ll << i) <= p; ++i) {
        if ((p >> i) & 1) ans = mod(ans * cur);
        cur = mod(cur * cur);
    }
    return ans;
}   
int mdiv(int a, int b) {
    return mod(a * fp(b, MOD - 2));
}   
void add(int &a, int b) {
    a = mod(a + b);
}
int h[N];
int dp[N][N];
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> h[i];
    vector <int> c;
    for (int i = 0; i < n; ++i) c.push_back(h[i]);
    sort(c.begin(), c.end()); 
    c.resize(unique(c.begin(), c.end()) - c.begin());
    int r = c.size();
    c.push_back(INF);
    dp[0][r] = 2;
    int p = 2;
    for (int i = r - 1; i >= 0; --i) {
        if (c[i] <= h[0] && c[i] > 1) {
            int down = 1;
            if (i) down = c[i - 1];
            dp[0][i] = mod(fp(2, h[0] - down + 1) - p);
            add(p, dp[0][i]);
        }   
    }   
    for (int i = 0; i + 1 < n; ++i) {
        for (int j = 0; j <= r; ++j) {
            if (dp[i][j]) {
                if (h[i + 1] <= h[i]) {
                    if (c[j] <= h[i + 1]) {
                        add(dp[i + 1][j], dp[i][j]);
                    }
                    else {
                        add(dp[i + 1][r], dp[i][j] << 1);
                    }   
                }
                else {
                    if (j == r) {
                        dp[i + 1][r] = 2;
                        int p = 2;
                        for (int k = r - 1; k >= 0; --k) {
                            if (c[k] <= h[i]) break;
                            if (c[k] <= h[i + 1]) {
                                int down = 1;
                                if (k) down = c[k - 1];
                                dp[i + 1][k] = mod(fp(2, h[i + 1] - down + 1) - p);
                                add(p, dp[i + 1][k]);
                            }   
                        }   
                        for (int k = r; k >= 0; --k) {
                            if (c[k] <= h[i]) break;
                            dp[i + 1][k] = mod(dp[i + 1][k] * dp[i][j]);
                        }   
                    }
                    else {
                        add(dp[i + 1][j], dp[i][j] * fp(2, h[i + 1] - h[i]));
                    }   
                }   
            }   
        }   
    }   
    #ifdef HOME
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= r; ++j) cout << dp[i][j] << ' ';
        cout << '\n';
    }
    #endif
    int ans = 0;
    for (int i = 0; i <= r; ++i) add(ans, dp[n - 1][i]);
    cout << ans << '\n';
}   

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

int main(){
int N;
cin>>N;
string S;
cin>>S;

int a=0;
for(int i=1;i<N;i++){
  if(S[i-1]!=S[i]){
    a++;
  }
}
a+=1;
cout<<a<<endl;

}


Measured memory_bytes: 3756
N = int(input())
A = list(map(int, input().split()))

cost = abs(A[0])
for i in range(1, N):
    cost += abs(A[i] - A[i - 1])
cost += abs(A[N - 1])

prev = 0
A.append(0)
for i in range(N):
    x = abs(A[i + 1] - prev)
    y = abs(A[i] - prev) + abs(A[i + 1] - A[i])
    print(cost - (y - x))
    prev = A[i]

Measured memory_bytes: 20448
#include <iostream>
#include <iomanip> // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple> // get<n>(xxx)
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set> // S.insert(M);
// if (S.find(key) != S.end()) { }
// for (auto it=S.begin(); it != S.end(); it++) { }
// auto it = S.lower_bound(M);
#include <random> // random_device rd; mt19937 mt(rd());
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib> // atoi(xxx)
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.
// insert #if<tab> by my emacs. #if DEBUG == 1 ... #end

typedef long long ll;

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

// const int C = 1e6+10;
// const ll M = 1000000007;

int N;
string T;
vector<bool> X;

bool ok(bool left, bool center, bool right, bool t) {
  if (center) {
    return ((left == right) == t);
  } else {
    return ((left != right) == t);
  }
}

bool add(bool left, bool center, bool t) {
  if (center) {
    if (t) return left;
    return !left;
  } else {
    if (t) return !left;
    return left;    
  }
}

bool check(vector<bool> S) {
  assert(N == (int)S.size());
  for (auto i = 0; i < N; ++i) {
    int left, right;
    int center = i;
    if (i == 0) {
      left = N-1;
      right = 1;
    } else if (i == N-1) {
      left = N-2;
      right = 0;
    } else {
      left = i-1;
      right = i+1;
    }
    if (!ok(S[left], S[center], S[right], X[center])) {
      return false;
    }
  }
  return true;
}

void flush(vector<bool> S) {
  assert(N == (int)S.size());
  for (auto x : S) {
    if (x) {
      cout << "S";
    } else {
      cout << "W";
    }
  }
  cout << endl;
}

int main () {
  cin >> N >> T;
  for (auto x : T) {
    X.push_back(x == 'o');
  }
  vector<bool> Y[4] = { {true, true}, {true, false},
                        {false, true}, {false, false}, };
  for (auto i = 0; i < 4; ++i) {
    for (auto j = 1; j < N-1; ++j) {
      Y[i].push_back(add(Y[i][j-1], Y[i][j], X[j]));
    }
    if (check(Y[i])) {
      flush(Y[i]);
      return 0;
    }
  }
  cout << "-1" << endl;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  vector<double> dp(n+1);//dp[i]->probibility of getting exactly i head.
  double pp;
  cin>>pp;
  dp[0]=(1-pp);
  dp[1]=pp;
  for(int i=2;i<=n;i++){
    double p;
    cin>>p;
    vector<double> temp_dp=dp;
    dp[0]=temp_dp[0]*(1-p);
    for(int j=1;j<=i;j++){
      dp[j]=temp_dp[j]*(1-p)+temp_dp[j-1]*p;
    }
  }
  double ans=0;
  for(int i=(n+1)/2;i<=n;i++) ans+=dp[i];
  cout<<fixed<<setprecision(9)<<ans;
  return 0;
}

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

int main(){
  double x;
  double max_h = 0, min_h = 999999999;

  while(cin >> x){
    max_h = max(max_h, x);
    min_h = min(min_h, x);
  }

  cout << max_h - min_h << endl;
}

Measured memory_bytes: 1280
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "\n" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

int main() {

	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	int X;
	cin >> X;

	cout << (X / 100 * 5 >= X % 100) << "\n";

	return 0;
}

Measured memory_bytes: 256
import sys
readline = sys.stdin.readline
# readlines = sys.stdin.readlines
N = int(readline())
S = readline()

ans = [S[0]]
s0 = S[0]
for i in range(N-1):
  _s = S[i+1]
  if s0 != _s:
    ans.append(_s)
  s0 = _s
  
print(len(ans))


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


int main()
{
    int n;
    cin >> n;
    int inp[n+10];

    for(int i=0;i<n;i++)
    {
        cin >> inp[i];
    }

    vector<int>dp(n+10,INT_MAX);

    dp[0]=0;

    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<i+3;j++)
        {

            if(j<n)
            {
                dp[j]=min(dp[j],dp[i]+abs(inp[i]-inp[j]));
            }
        }
    }
    cout<<dp[n-1]<<endl;
}


Measured memory_bytes: 1024
#include<stdio.h>

int main(void)
{
  //入力
  int n,x;
  scanf("%d%d",&n,&x);
  int i,l[n];
  for(i=0;i<n;i++)
    scanf("%d",&l[i]);

  //計算
  int cnt=0,dist=0;
  for(i=0;i<n+1;i++){
    if(dist<=x)
      cnt++;
    dist += l[i];
  }

  //出力
  printf("%d\n",cnt);
  return 0;
}

Measured memory_bytes: 128
import java.util.*;

class Main {
        public static void main(String args[]) {
                try (Scanner sc = new Scanner(System.in)) {
                        int N = sc.nextInt();
                        int[] A = new int[N];
                        for (int i = 0; i < N; i++) {
                                A[i] = sc.nextInt();
                        }
                        for (int i = 1; i <= N; i++) {
                                System.out.printf("node %d: key = %d, ", i, A[i-1]);
                                if (i != 1) {
                                        System.out.printf("parent key = %d, ", A[i/2 - 1]);
                                }
                                if (i * 2 <= N) {
                                        System.out.printf("left key = %d, ", A[i * 2 - 1]);
                                }
                                if (i * 2 + 1 <= N) {
                                        System.out.printf("right key = %d, ", A[i * 2]);
                                }
                                System.out.print("\n");
                        }
                }
        }
}

Measured memory_bytes: 30656
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	while(true) {
		cin >> s;
		if(s == "#") {
			break;
		}
		
		int m[15][15] = {0};
		int r = 0, c = 0;
		int w, h;
		
		for(char ch : s) {
			if(ch == '/') {
				r++;
				w = c;
				c = 0;
			} else if('0' <= ch && ch <= '9') {
				for(int j = 0; j < ch - '0'; j++) {
					c++;
				}
			} else if(ch == 'b') {
				m[r][c] = 1;
				c++;
			}
		}
		
		h = r + 1;
		
		{
			int a, b, c, d;
			cin >> a >> b >> c >> d;
			m[a - 1][b - 1] = 0;
			m[c - 1][d - 1] = 1;
		}
		
		for(int r = 0; r < h; r++) {
			int cnt = 0;
			for(int c = 0; c < w; c++) {
				if(m[r][c]) {
					if(cnt > 0) {
						cout << cnt;
						cnt = 0;
					}
					cout << 'b';
				} else {
					cnt++;
				}
			}
			if(cnt > 0) {
				cout << cnt;
			}
			
			if(r != h - 1) {
				cout << '/';
			} else {
				cout << endl;
			}
		}
	}
	return 0;
}


Measured memory_bytes: 3164
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <utility>
#include <iomanip>
#include <queue>

#define rep(i,n) for(int i=0;i< (n);++i)
typedef long long ll;

using namespace std;


int main(){
    
    ll K;
    cin>>K;
    
    ll c=0;
    ll keta=1;
    ll count=0;
    bool jud=false;
    
    for(int i=0;i<=K;++i){
       // cout<<"pre:"<<keta<<endl;
        c+=(7%K)*(keta);
        c%=K;
        //cout<<c<<endl;
        
        keta=(keta*(10%K))%K;
        ++count;
        if(c==0){
            jud=true;
            break;
        }
    }
    if(jud){
    cout<<count<<endl;
    }else{
        cout<<-1<<endl;
    }

}



Measured memory_bytes: 3600
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <tuple>

using namespace std;
using ll = long long;

struct UnionFind {
	vector<int> par;

	UnionFind(int N) : par(N) {
		for (int i = 0; i < N; i++) par[i] = i;
	}

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

	void unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry) return;
		par[rx] = ry;
	}

	bool same(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};

int main() {
	int N;
	cin >> N;
	vector<tuple<int, int, int>> edges;
	vector<pair<int, int>> x(N), y(N);
	for (int i = 0; i < N; i++) {
		cin >> x[i].first >> y[i].first;
		x[i].second = i;
		y[i].second = i;
	}
	sort(x.begin(), x.end());
	for (int i = 0; i < N - 1; i++) {
		int w = x[i + 1].first - x[i].first;
		edges.push_back(make_tuple(w, x[i].second, x[i + 1].second));
	}
	sort(y.begin(), y.end());
	for (int i = 0; i < N - 1; i++) {
		int w = y[i + 1].first - y[i].first;
		edges.push_back(make_tuple(w, y[i].second, y[i + 1].second));
	}
	sort(edges.begin(), edges.end());
	UnionFind tree(N);
	int res = 0;
	for (auto e : edges) {
		int w = get<0>(e);
		int s = get<1>(e);
		int t = get<2>(e);
		if (!tree.same(s, t)) {
			tree.unite(s, t);
			res += w;
		}
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 8916
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv, std.math,
    std.functional, std.numeric, std.range, std.stdio, std.string, std.random,
    std.typecons, std.container, std.format;

// dfmt off
T lread(T = long)(){return readln.chomp.to!T();}
T[] aryread(T = long)(){return readln.split.to!(T[])();}
void scan(TList...)(ref TList Args){auto line = readln.split();
foreach (i, T; TList){T val = line[i].to!(T);Args[i] = val;}}
alias sread = () => readln.chomp();enum MOD = 10 ^^ 9 + 7;
alias PQueue = BinaryHeap!(Array!long, "a<b");
// dfmt on

void main()
{
    long N, A, B;
    scan(N, A, B);
    writefln("%d %d", min(A, B), max(0, A + B - N));
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define dl long double
#define ff first
#define ss second
#define pb push_back
#define MAXN 10100
#define MAXD 110
#define INI 12332112
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef pair<int,int> pii;
const int M = 1e9+7;

string s;
int d;
int n;
int dp[MAXN][MAXD][2];
int dp1[MAXN][MAXD];
inline int mod(int a,int m){
	int r = a%m;
	if(r<0)r+=m;
	return r;
}


int solve(int dig,int soma){
	if(dp1[dig][soma]!=-1)return dp1[dig][soma];
	if(dig==n-1){
		if(soma==0){
			dp1[dig][soma]=1;
		}
		else return dp1[dig][soma]=0;
	}
	int res=0;
	for(int i=0;i<10;i++){
		res=mod(res+solve(dig+1,mod(soma+i,d)),M);
	}
	return dp1[dig][soma]=mod(res,M);
}

int s2(int dig,int soma,int flag){
	if(dp[dig][soma][flag]!=-1)return dp[dig][soma][flag];
	if(dig==n){
		if(soma==0){
			return dp[dig][soma][flag]=1;
		}else return dp[dig][soma][flag]=0;
		
	}
	if(flag){
		int res=0;
		for(int i=0;i<10;i++){
			res=mod(res+s2(dig+1,mod(soma+i,d),1),M);
		}
		return dp[dig][soma][flag]=mod(res,M);
	}else{
		int res=0;
		for(int i=0;i<10;i++){
			if(s[dig]-'0'>i){
				res=mod(res+s2(dig+1,mod(soma+i,d),1),M);
			}else if(s[dig]-'0'==i){
				res=mod(res+s2(dig+1,mod(soma+i,d),0),M);
			}else break;
		}
		return dp[dig][soma][flag]=mod(res,M);
	}
	
}



int32_t main(){
	fastio;
	cin>>s;
	cin>>d;
	n = s.size();
	memset(dp1,-1,sizeof(dp1));
	memset(dp,-1,sizeof(dp));
//	int r1 = mod(solve(0,0),M);
	
	
	int r2 =0;
	for(int i=0;i<10;i++){
		if(s[0]-'0'>i){
			r2=mod(r2+s2(1,mod(i,d),1),M);
		}else if(s[0]-'0'==i){
			r2=mod(r2+s2(1,mod(i,d),0),M);
		}
	}
	
	cout<<mod(r2-1,M)<<endl;
	
}

Measured memory_bytes: 27136
#include <bits/stdc++.h>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define int long long
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
const int INF = 1010000000;
const double EPS = 1e-10;
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 

vector<int> init(int size){
  vector<int> par(size,-1);
  return par;
}

int root(int x, vector<int>& par){
  if(par[x] < 0){
    return x;
  }else{
    return par[x] = root(par[x],par);
  }
}

bool same(int x, int y, vector<int>& par){
  return root(x, par) == root(y, par);
}

void unite(int x, int y, vector<int>& par){
  x = root(x, par), y = root(y, par);
  if(same(x,y, par))return;
  par[x] += par[y];
  par[y] = x;
}

int size(int x, vector<int>& par){
  return -par[root(x, par)];
}

int pow(int x, int n){
  if(n == 0)return 1;
  if(n % 2 == 0)return pow(x * x % MOD, n/2);
  else return x * pow(x, n-1) % MOD;
}

vector< int > divisor(int n) {
  vector< int > ret;
  for(int i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret),greater<int>());
  return (ret);
}

int n,k;
  pair<int,int> p[2100];

signed main(){
  cin>>n>>k;
  int a[2100];rep(i,n)cin>>a[i];
  rep(i,2100)p[i].first = p[i].second = 0;
  rep(i,n){
    rep(j,n){
      if(i == j)continue;
      if(a[i] > a[j]){
        if(i > j){//自分より左にある
          p[i].first++;
        }else{//自分より右にある
          p[i].second++;
        }
      }
    }
  }
  int ans = 0;
  int nn = (1+k) * k / 2 % MOD, nn1 = (k * (k-1))/2 % MOD;
  rep(i,n){
    ans = (ans + (p[i].first * nn1 % MOD + p[i].second * nn % MOD)%MOD)%MOD;
  }
  cout << ans << endl;

}


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

// 素数判定
bool isPrime(int p) {
  if(p == 1) return false;
  else if(p == 2) return true;
  else if(p % 2 == 0) return false;
  
  double x = sqrt(p);
  for(int i = 3; i <= x; i += 2){
    if(p % i == 0) return false;
  }
  return true;
}

int main() {
  int n, i, count = 0;
  cin >> n;
  
  for(i = 11; i <= 55555; i += 5){
    if(isPrime(i)){
      cout << i << endl;
      count++;
    }
    
    if(count == n) break;
  }
}


Measured memory_bytes: 256
import sys

input = sys.stdin.readline

def main():
    n,m = map(int, input().split())
    s = []
    p = []
    min = [10**12]*n
    ans = [0]*n
    for _ in range(n):
        s.append(list(map(int, input().split())))
    for _ in range(m):
        p.append(list(map(int, input().split())))
    for i in range(n):
        a, b = s[i]
        for j in range(m):
            c,d  = p[j]
            md = abs(a-c) + abs(b-d)
            if md < min[i]:
                min[i] = md
                ans[i] = j+1
    for i in ans:
        print(i)

if __name__ == '__main__':
    main()

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

int main() {
    int n; cin >> n;
    map<int, int> a;
    rep(i, n) {
        int tmp;
        cin >> tmp;
        a[tmp]++;
    }
    int ans = 0;
    for (auto a_tmp : a)  {
        if (a_tmp.first < a_tmp.second)
            ans += (a_tmp.second-a_tmp.first);
        else if (a_tmp.second < a_tmp.first)
            ans += a_tmp.second;
    }
    cout << ans << endl;
}

Measured memory_bytes: 8076
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

double solve(int n)
{
    int NUM = 30;
    vector<double> dp(NUM+1, 0.0);
    dp[0] = 1.0;

    double ret = 0.0;
    for(int i=0; i<n; ++i){
        double prob = 1.0;
        vector<double> dp2(NUM+1, 0.0);
        for(int j=0; j<NUM; ++j){
            ret += dp[j] * prob;
            dp2[j+1] = dp[j] * prob;
            dp2[0] += dp[j] * (1-prob);
            prob *= 0.5;
        }
        dp.swap(dp2);
    }
    return ret;
}

int main()
{
    for(;;){
        int n;
        cin >> n;
        if(n == 0)
            break;
        printf("%.10f\n", solve(n));
    }

    return 0;
}

Measured memory_bytes: 948
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
#include <map>
#define pb push_back
#define ll long long
using namespace std;
int n;
int mem[100010];
typedef struct
{
    ll a,b,c;
}triplet;
ll v[100010][4],dp[100010][4];
ll maximal(ll a,ll b,ll c,ll& param)
{
    ll ans = max(max(a,b),c);
    if(ans==a)
    {
        param=1;
    }
    else if(ans==b)
    {
        param=2;
    }
    else if(ans==c)
    {
        param=3;
    }
    return ans;
}
int main()
{
    ll i,a,b,c,rez=0,maxim=-1;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        triplet t;
        maxim=-1;
        cin>>t.a>>t.b>>t.c;
        v[i][0]=t.a;
        v[i][1]=t.b;
        v[i][2]=t.c;
    }
    /*dp[1][0]=v[1][0];
    dp[1][1]=v[1][1];
    dp[1][2]=v[1][2];
    int first,second,j,k;
    int q=maximal(dp[1][0],dp[1][1],dp[1][2],first);
    dp[2][0]=q+v[2][0];
    dp[2][1]=q+v[2][1];
    dp[2][2]=q+v[2][2];*/
    int j,k;
    ll first,second;
    for(i=0;i<=n;i++)
    {
    ll aux=maximal(dp[i-1][0],dp[i-1][1],dp[i-1][2],second);
        for(j=0;j<=2;j++)
            for(k=0;k<=2;k++)
        {
            if(k!=j)
                dp[i+1][j]=max(dp[i+1][j],dp[i][k]+v[i][j]);


        // cout<<"\n"<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<'\n';

        }
    }
//        for(i=1;i<=n;i++)
//    {
//      cout<<"\n"<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<'\n';
//  }
    cout<<maximal(dp[n+1][0],dp[n+1][1],dp[n+1][2],first);

    return 0;
}


Measured memory_bytes: 6528
#include <iostream>
#include <iomanip>
#include <string>
using namespace std;
int main()
{
  int a=0,n;
  cin>>n;
  long double p;
  for(int i=1;i<=n;i++)
  {
      if(i%2!=0)
         a+=1;
  }
  p=a;
  p=p/n;
  cout<<setprecision(10)<<p;
}


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

using namespace std;

int main(){
  int a,b;
  cin >> a >> b;
  int plus,minus,mult;
  plus = a + b;
  minus = a-b;
  mult = a * b;
  cout << max({plus,minus,mult}) << endl;
}



Measured memory_bytes: 3640
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>

#define REP(i,n) for (int i = 0; (i) < (n); ++ (i))

using namespace std;
int a,b,c,d;
int main(){
	cin >> a >> b >>c >> d;
	cout << (a-c)*(b-d) << endl;
	return 0;
}


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

using namespace std;
struct _ { ios_base::Init i; _() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); } } _;

#define ff first
#define ss second

int main() {

	int n; cin >> n;
	vector<int> a(n); for (int i = 0; i <= n - 1; i++) cin >> a[i];

	vector<vector<pair<long long, long long>>> dp(n, vector<pair<long long, long long>>(n, {0, 0}));

	for (int dist = 0; dist <= n - 1; dist++) {
		for (int i = 0; i + dist <= n - 1; i++) {
			int j = i + dist;

			if (i == j) {
				if ((j - i + 1) % 2 == (n % 2)) dp[i][j] = {a[i], 0};
				else dp[i][j] = {0, a[i]};
			}
			else {
				if ((j - i + 1) % 2 == (n % 2)) {
					if (dp[i + 1][j].ff + a[i] - dp[i + 1][j].ss > dp[i][j - 1].ff + a[j] - dp[i][j - 1].ss)
						dp[i][j] = {dp[i + 1][j].ff + a[i], dp[i + 1][j].ss};
					else
						dp[i][j] = {dp[i][j - 1].ff + a[j], dp[i][j - 1].ss};
				}
				else {
					if (dp[i + 1][j].ff - dp[i + 1][j].ss - a[i] < dp[i][j - 1].ff - dp[i][j - 1].ss - a[j])
						dp[i][j] = {dp[i + 1][j].ff, dp[i + 1][j].ss + a[i]};
					else
						dp[i][j] = {dp[i][j - 1].ff, dp[i][j - 1].ss + a[j]};
				}
			}
		}
	}
	cout << dp[0][n - 1].ff - dp[0][n - 1].ss;

	return 0;
}

Measured memory_bytes: 143856
/**
 *    author:  border
 *    created: 06.01.2019 18:25:05     
**/
#include <bits/stdc++.h>

using namespace std;

#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define mem(a,val) memset(a,val,sizeof a)

#define int long long
#define ff first
#define ss second
#define pb push_back
#define endl '\n'

int n,w,W[100010],v[100010];
int dp[101][100010];

int fun(int id, int remW)
{
  if(remW == 0) return 0;
  if(id == n) return 0;
  int &ret = dp[id][remW];
  if(ret != -1) return ret;
  if(W[id] > remW) ret = fun(id+1,remW);
  if(W[id] <= remW) ret = max(fun(id+1,remW),v[id]+fun(id+1,remW-W[id]));
  return ret;
}

int32_t main()
{
  ios_base::sync_with_stdio(false);cin.tie(NULL);
  /*#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out","w",stdout);
  #endif*/
  cin >> n >> w;
  for(int i = 0; i < n; ++i){
    cin >> W[i] >> v[i];
  }
  mem(dp,-1);
  cout << fun(0,w) << endl;
}



Measured memory_bytes: 80128
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define rt return
#define dll(x) scanf("%I64d",&x)
#define xll(x) printf("%I64d\n",x)
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
inline void getInt(int* p);
const int maxn=1000010;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int n,q;
char s[maxn];
char t[maxn];
char d[maxn];
bool checkl(int pos)
{
	repd(i,1,q)
	{
		if(t[i]==s[pos])
		{
			if(d[i]=='L')
			{
				pos--;
			}else
			{
				pos++;
			}
		}
		if(pos<1)
		{
			return 1;
		}else if(pos>n)
		{
			break;
		}
	}
	return 0;
}
bool checkr(int pos)
{
	repd(i,1,q)
	{
		if(t[i]==s[pos])
		{
			if(d[i]=='L')
			{
				pos--;
			}else
			{
				pos++;
			}
		}
		if(pos>n)
		{
			return 1;
		}else if(pos<1)
		{
			break;
		}
	}
	return 0;
}
int main()
{
    //freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);
	//freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);

	gbtb;
	cin>>n>>q;
	cin>>s+1;
	repd(i,1,q)
	{
		cin>>t[i]>>d[i];
	}
	int l=1;
	int r=n;
	int mid;
	int lpos=0;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(checkl(mid))
		{
			lpos=mid;
			l=mid+1;
		}else
		{
			r=mid-1;
		}
	}
	l=1;
	r=n;
	int rpos=n+1;
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(checkr(mid))
		{
			rpos=mid;
			r=mid-1;
		}else
		{
			l=mid+1;
		}
	}
//	db(lpos);
//	db(rpos);
	cout<<(rpos-1-(lpos+1)+1)<<endl;

    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}



Measured memory_bytes: 896
#include <bits/stdc++.h>
 
using namespace std;
 
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
 
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
 
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
 
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

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

  int N;
  cin >> N;
  VI xs(N);
  REP(i,N) cin >> xs[i];

  REP(i,N) REP(j,i){
	if((xs[i] - xs[j]) % (N-1) == 0){
	  cout << xs[i] << " " << xs[j] << endl;
	  return 0;
	}
  }
  
  return 0;
}



Measured memory_bytes: 3228
using System;
using System.Collections.Generic;
using System.Text;

namespace AtTest.AGC_030
{
    class A
    {
        static void Main(string[] args)
        {
            Method(args);
            Console.ReadLine();
        }

        static void Method(string[] args)
        {
            long[] abc = ReadLongs();
            long a = abc[0];
            long b = abc[1];
            long c = abc[2];
            if (c <= b+1)
            {
                Console.WriteLine(b + c);
            }
            else
            {
                if (c <= b + a + 1)
                {
                    Console.WriteLine(b + c);
                }
                else
                {
                    Console.WriteLine(b * 2 + a + 1);
                }
            }
        }

        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


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

int main(){
  string s, t;
  int ans = 0;

  cin >> s >> t;

  if(s.size() + 1 != t.size()){
    cout << "No" << endl;
    return 0;
  }

  for(int i = 0; i < s.size(); i++){
    if(s.at(i) == t.at(i)){
      ans++;
    }
  }

  if(ans == s.size()){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 3624
#include<stdio.h>
#define MAX 10000
#define NIL -1

struct Node { int p, l, r;};
struct Node T[MAX];
int n;

void preParse(int u) {
 if ( u == NIL ) return;
 printf(" %d", u);
 preParse(T[u].l);
 preParse(T[u].r);
}

void inParse(int u) {
  if ( u == NIL) return;
  inParse(T[u].l);
  printf(" %d", u);
  inParse(T[u].r);
}

void postParse(int u) {
  if ( u == NIL ) return;
  postParse(T[u].l);
  postParse(T[u].r);
  printf(" %d", u);
}

int main() {
  int i, v, l, r, root;

  scanf("%d", &n);

  for ( i = 0; i < n; i++ ) {
    T[i].p = NIL;
  }

  for ( i = 0; i < n; i++ ) {
    scanf("%d %d %d", &v, &l, &r);
    T[v].l = l;
    T[v].r = r;
    if ( l != NIL ) T[l].p = v;
    if ( r != NIL ) T[r].p = v;
  }

  for ( i = 0; i < n ; i++ ) if (T[i].p == NIL) root = i;

  printf("Preorder\n");
  preParse(root);
  printf("\n");
  printf("Inorder\n");
  inParse(root);
  printf("\n");
  printf("Postorder\n");
  postParse(root);
  printf("\n");

  return 0;
}


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

const int maxn = 2e5 + 5;

int p[maxn], q[maxn], rp[maxn], rq[maxn];
int n;
int rA[maxn], A[maxn], B[maxn];

void power(int b){
	if (b == 0)
		return;
	power(b / 2);
	for (int i = 1; i <= n; i++)
		B[i] = A[A[i]];
	for (int i = 1; i <= n; i++)
		A[i] = B[i];
	if (b & 1){
		for (int i = 1; i <= n; i++)
			B[i] = A[q[rp[rq[p[i]]]]];
		for (int i = 1; i <= n; i++)
			A[i] = B[i];
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	int k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++){
		cin >> p[i];
		rp[p[i]] = i;
	}
	for (int i = 1; i <= n; i++){
		cin >> q[i];
		rq[q[i]] = i;
	}
	for (int i = 1; i <= n; i++)
		A[i] = i;
	power((k - 1) / 6);
	if (k % 6 == 4){
		for (int i = 1; i <= n; i++)
			B[i] = A[q[i]];
		for (int i = 1; i <= n; i++)
			A[i] = B[i];
	}
	if (k % 6 == 5 or k % 6 == 0){
		for (int i = 1; i <= n; i++)
			B[i] = A[q[rp[i]]];
		for (int i = 1; i <= n; i++)
			A[i] = B[i];
	}
	for (int i = 1; i <= n; i++)
		rA[A[i]] = i;
	k %= 6;
	if (k == 1)
		for (int i = 1; i <= n; i++)
			B[i] = p[i];
	else if (k == 2)
		for (int i = 1; i <= n; i++)
			B[i] = q[i];
	else if (k == 3)
		for (int i = 1; i <= n; i++)
			B[i] = q[rp[i]];
	else if (k == 4)
		for (int i = 1; i <= n; i++)
			B[i] = rp[i];
	else if (k == 5)
		for (int i = 1; i <= n; i++)
			B[i] = rq[i];
	else
		for (int i = 1; i <= n; i++)
			B[i] = rq[p[i]];
	for (int i = 1; i <= n; i++)
		cout << A[B[rA[i]]] << " ";
	cout << endl;
}


Measured memory_bytes: 4608
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <queue>
using namespace std;




//998244353


int main() {
    
   int r,c;
   cin >> r >> c;

   vector<string> board;

   for(int i = 0;i<r;i++){
     string line;
     cin >> line;
     board.push_back(line);
   }
  int maximum = 0;
   for(int x = 0;x<c;x++){
     for(int y = 0;y<r;y++){
       queue<tuple<int,int,int>> que;
       bool visited[21][21] = {}; 
       que.push(make_tuple(x,y,0));

       while(!que.empty()){
        tuple<int,int,int> elem = que.front();
         int x1 = get<0>(elem);
         int y1 = get<1>(elem);
         int depth = get<2>(elem);
         //cout << x1 << " " << y1 << endl;
         que.pop();
         if(x1>=c || x1<0 || y1>=r || y1<0 || board[y1][x1] == '#' || visited[x1][y1]) continue;
         visited[x1][y1] = true;
         maximum = max(maximum,depth);

         que.push(make_tuple(x1+1,y1,depth+1));
         que.push(make_tuple(x1-1,y1,depth+1));
         que.push(make_tuple(x1,y1+1,depth+1));
         que.push(make_tuple(x1,y1-1,depth+1));

       }

     }
   }
   cout << maximum;

    
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <map>

using lint = long long;

void solve() {
    std::string t;
    std::cin >> t;

    std::vector<std::vector<std::map<lint, lint>>>
        dp(1, std::vector<std::map<lint, lint>>(3));
    dp[0][1][1] = 1;

    int smax = 0;
    int sum = 0;
    lint prod = 1;
    for (char cc : t) {
        int c = cc - '0';

        sum += c;
        smax += 9;
        prod *= (c + 1);

        std::vector<std::vector<std::map<lint, lint>>>
            ndp(smax + 1, std::vector<std::map<lint, lint>>(3));

        int psmax = dp.size() - 1;
        for (int s = 0; s <= psmax; ++s) {
            for (int k = 0; k <= 2; ++k) {
                for (const auto& q : dp[s][k]) {
                    auto p = q.first;

                    for (int d = 0; d <= 9; ++d) {
                        int ns = s + d;
                        if (ns > smax) continue;

                        lint np = p * (d + 1);
                        int nk = (k != 1 ? k
                                         : (d < c ? 0 : d > c ? 2 : 1));

                        if (!ndp[ns][nk].count(np)) ndp[ns][nk][np] = 0;
                        ndp[ns][nk][np] += q.second;
                    }
                }
            }
        }
        std::swap(dp, ndp);
    }

    lint ans = 0;
    for (int s = 0; s <= sum; ++s) {
        for (int k = 0; k <= 2; ++k) {
            for (const auto& q : dp[s][k]) {
                auto p = q.first;

                if (s < sum ||
                    (s == sum && p < prod) ||
                    (s == sum && p == prod && k < 1)) {
                    ans += q.second;
                }
            }
        }
    }

    std::cout << ans << std::endl;
}

int main() {
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);

    solve();

    return 0;
}




Measured memory_bytes: 44268