akhauriyash/Code-Regression huggingface dataset:
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(unused_macros)]
#![allow(unused_imports)]

use std::str::FromStr;
use std::io::*;
use std::collections::*;
use std::cmp::*;

struct Scanner<I: Iterator<Item = char>> {
    iter: std::iter::Peekable<I>,
}

macro_rules! exit {
    () => {{
        exit!(0)
    }};
    ($code:expr) => {{
        if cfg!(local) {
            writeln!(std::io::stderr(), "===== Terminated =====")
                .expect("failed printing to stderr");
        }
        std::process::exit($code);
    }}
}

impl<I: Iterator<Item = char>> Scanner<I> {
    pub fn new(iter: I) -> Scanner<I> {
        Scanner {
            iter: iter.peekable(),
        }
    }

    pub fn safe_get_token(&mut self) -> Option<String> {
        let token = self.iter
            .by_ref()
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        if token.is_empty() {
            None
        } else {
            Some(token)
        }
    }

    pub fn token(&mut self) -> String {
        self.safe_get_token().unwrap_or_else(|| exit!())
    }

    pub fn get<T: FromStr>(&mut self) -> T {
        self.token().parse::<T>().unwrap_or_else(|_| exit!())
    }

    pub fn vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
        (0..len).map(|_| self.get()).collect()
    }

    pub fn mat<T: FromStr>(&mut self, row: usize, col: usize) -> Vec<Vec<T>> {
        (0..row).map(|_| self.vec(col)).collect()
    }

    pub fn char(&mut self) -> char {
        self.iter.next().unwrap_or_else(|| exit!())
    }

    pub fn chars(&mut self) -> Vec<char> {
        self.get::<String>().chars().collect()
    }

    pub fn mat_chars(&mut self, row: usize) -> Vec<Vec<char>> {
        (0..row).map(|_| self.chars()).collect()
    }

    pub fn line(&mut self) -> String {
        if self.peek().is_some() {
            self.iter
                .by_ref()
                .take_while(|&c| !(c == '\n' || c == '\r'))
                .collect::<String>()
        } else {
            exit!();
        }
    }

    pub fn peek(&mut self) -> Option<&char> {
        self.iter.peek()
    }
}

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin.bytes().map(|c| c.unwrap() as char));
    let X: i64 = sc.get();
    for A in -120..=120 {
        for B in -120..=120 {
            if i64::pow(A, 5) - i64::pow(B, 5) == X {
                println!("{} {}", A, B);
                return;
            }
        }
    }
    unreachable!();
}


Measured memory_bytes: 2168
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
int main(){ 
    int s;
    cin>>s;
    vector<int> a(1000000);
    a[0]=s;
  if(s==1){
    cout<<4;
    return 0;}
  if(s==2){
    cout<<4;
    return 0;}
   for(int i=1;i<1000000;i++){
       if(s==4){
           cout<<i+3;
           return 0;
       }
        if(s%2==0){
            s/=2;
        }else{
            s=3*s+1;
        }
        
    }
   
    return 0;
}


Measured memory_bytes: 4096
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            int inputk = int.Parse(Console.ReadLine());
            string input = Console.ReadLine();
            Console.WriteLine(hantei(inputk, input));
            Console.Read();
        }

        public static string hantei(int x, string y)
        {
            string print = "";
            for(int i = 0; i < y.Length; i++)
            {
                if(i < x)
                {
                    print = print + y[i];
                }
                else
                {
                    print = print + "...";
                    break;
                }
            }
            return print;
        }
    }
}


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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef pair<int, int> pi;

int n;
const int maxn = 1e5 + 5;

vector<int> G[maxn];

int dfs(int u, int fa){
    int ans = 0;
    for(auto v : G[u]){
        if(v == fa)
            continue;
        ans ^= (dfs(v, u) + 1);
    } 
    return ans;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1;i < n;i++){
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int ret = dfs(1, 0);
    if(ret == 0){
        cout << "Bob" << endl;
    }else{
        cout << "Alice" << endl;
    }
    return 0;
}


Measured memory_bytes: 10368
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
int main() {
    string str[3];
    vector<vector<int> > num(3);
 
    for(int i = 0; i < 3; i++) {
        string str_tmp;
        vector<int> num_tmp;
        while(true) {
            char c;
            int n;
            cin >> c;
            if(c == '$') {
                break;
            }
            cin >> n;
            str_tmp += c;
            num_tmp.push_back(n);
        }
        str[i] = str_tmp;
        num[i] = num_tmp;
    }
 
    string A = str[0];
    string B = str[1];
    string C = str[2];
 
    int idx = 0;
    int pos;
    bool flag = false;
 
    while((pos = A.find(B, idx)) != string::npos) {
        int i = pos;
        flag = true;
        while(i < pos+B.size()) {
            if(i == pos) {
                if(num[0][i] < num[1][i-pos]) {
                    flag = false;
                }
            }
            else if(i == pos+B.size()-1) {
                if(num[0][i] < num[1][i-pos]) {
                    flag = false;
                }
            }
            else {
                if(num[0][i] != num[1][i-pos]) {
                    flag = false;
                }
            }
            i++;
        }
        if(!flag) {
            idx = pos+1;
        }
        else {
            break;
        }
    }
 
    if(flag) {
        string D = A.substr(0, pos);
        vector<int> D_num;
        for(int i = 0; i < pos; i++) {
            D_num.push_back(num[0][i]);
        }
 
        if(B.size() != 1) {
            if(num[0][pos] > num[1][0]) {
                D.push_back(B[0]);
                D_num.push_back(num[0][pos] - num[1][0]);
            }
        }
 
        D += C;
        for(int i = 0; i < C.size(); i++) {
            D_num.push_back(num[2][i]);
        }
 
        if(num[0][pos+B.size()-1] > num[1].back()) {
            D.push_back(B.back());
            D_num.push_back(num[0][pos+B.size()-1] - num[1].back());
        }
 
        for(int i = pos+B.size(); i < A.size(); i++) {
            D_num.push_back(num[0][i]);
        }
        D += A.substr(pos+B.size());
 
        for(int i = 0; i < D.size(); i++) {
            char c = D[i];
            int n = D_num[i];
            if(i < D.size()-1 && D[i] == D[i+1]) {
                D_num[i+1] += n;
                continue;
            }
            else {
                cout << c << " " << n << " ";
            }
        }
        cout << "$" << endl;
    }
    else {
        for(int i = 0; i < A.size(); i++) {
            cout << A[i] << " " << num[0][i] << " ";
        }
        cout << "$" << endl;
         
    }
 
    return 0;
}

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

int sod(int n) {
  int sum = 0;
  while (n > 0) {
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

int main() {
  int N, A, B;
  cin >> N >> A >> B;

  int ans = 0;

  for (int i = 0; i <= N; i++) {
    if (A <= sod(i) && sod(i) <= B) ans += i;
  }

  cout << ans << endl;
}

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

int main() {
  int a, b;
  cin >> a >> b;
  if(a+b == 15) {
    cout << "+" << endl;
  }
  else if(a*b == 15) {
    cout << "*" << endl;
  }
  else {
    cout << "x" << endl;
  }
}


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

struct Node{
	int parent, left, right;
};

struct Node t[MAX];
int n, d[MAX], h[MAX];

void setDepth(int u, int e)
{
	if(u == NIL) return;
	d[u] = e;
	setDepth(t[u].left, e+1);
	setDepth(t[u].right, e+1);
}

int setHeight(int u)
{
	int h1 = 0, h2 = 0;
	if(t[u].left != NIL) h1 = setHeight(t[u].left) + 1;
	if(t[u].right != NIL) h2 = setHeight(t[u].right) + 1;
	return h[u] = (h1 > h2 ? h1 : h2);
}

int getSibling(int u)
{
	if(t[u].parent == NIL) return NIL;
	if(t[t[u].parent].left != u && t[t[u].parent].left != NIL)
		return t[t[u].parent].left;
	if(t[t[u].parent].right != u && t[t[u].parent].right != NIL)
		return t[t[u].parent].right;
	return NIL;
}

void print(int u)
{
	printf("node %d: ", u);
	printf("parent = %d, ", t[u].parent);
	printf("sibling = %d, ", getSibling(u));
	int deg = 0;
	if(t[u].left != NIL) deg++;
	if(t[u].right != NIL) deg++;
	printf("degree = %d, ", deg);
	printf("depth = %d, ", d[u]);
	printf("height = %d, ", h[u]);
	
	if(t[u].parent == NIL)
	{
		printf("root\n");
	} else if(t[u].left == NIL && t[u].right == NIL)
	{
		printf("leaf\n");
	} else {
		printf("internal node\n");
	}
}

int main(){
	int v, l, r, root = 0;
	scanf("%d", &n);
	
	for(int i = 0; i < n; i++)
	{
		t[i].parent = NIL;
	}
	
	for(int i = 0; i < n; i++)
	{
		scanf("%d %d %d", &v, &l, &r);
		t[v].left = l;
		t[v].right = r;
		if(l != NIL) t[l].parent = v;
		if(r != NIL) t[r].parent = v;
	}
	
	for(int i = 0; i < n; i++)
	{
		if(t[i].parent == NIL)
		{
			root = i;
		}
	}
	
	setDepth(root, 0);
	setHeight(root);
	
	for(int i = 0; i < n; i++)
	{
		print(i);
	}
	
	return 0;
}
		


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

using namespace std;

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

    int k,a,b;
    cin>>k>>a>>b;

    for(int i=a;i<=b;i++){
        if(i%k==0){
            cout<<"OK\n";return 0;
        }
    }

    cout<<"NG\n";


    return 0;
}


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

#define rep2(x,fr,to) for(int x=(fr);x<(to);x++)
#define rep(x,to) for(int x=0;x<(to);x++)
#define repr(x,fr,to) for(int x=(fr);x>=(to);x--)
#define all(c) c.begin(),c.end()
#define sz(v) (int)v.size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<ll, ll> pii;
typedef vector<ll> VL; const int MD = 1e9 + 7;
void dbg(){cerr<<"\n";} template <typename T,typename ...T2> void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

vector<int64_t> fct, inv;
void finit(int cmx, ll mod =MD){
	fct.resize(cmx+20); inv.resize(cmx+20);
	fct[0] = fct[1] = inv[1] = inv[cmx] = 1;
	for(int i=2;i<cmx+3;i++) fct[i] = fct[i-1] * i % mod;
	for(ll x=fct[cmx], n=mod-2; n > 0; n >>=1, x = x*x %mod)
		if(n & 1) inv[cmx] = inv[cmx] * x %mod;
	for(int i=cmx;i>=1;i--) inv[i-1] = inv[i] * i % mod;
}
ll nCk(ll n, ll k, ll mod =MD) {
	if(k > n || n <0 || k <0) return 0;
	ll ret =fct[n] * inv[k] % mod * inv[n-k] % mod;
	return ret;
}

int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n, k;
	cin >>n >>k;
	finit(2*n+1000);
	k = min(k, n);
	ll ans =0;
	rep(i, k+1){
		(ans += nCk(n, i) * nCk(n-1, i)) %=MD;
	}
	cout << ans <<"\n";
	return 0;
}


Measured memory_bytes: 6528
#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#define dump(...)                                                    \
    cout << "   " << string(#__VA_ARGS__) << ": "                    \
         << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" \
         << endl                                                     \
         << "   ",                                                   \
        dump_func(__VA_ARGS__)
#else
#define dump(...)
#endif

#define ll long long
#define BUF 1e5
#define INF 1 << 30
#define vi vector<int>
#define vvi vector<vector<int>>
#define all(a) (a).begin(), (a).end()
constexpr ll mod = 1e9 + 7;
using namespace std;
ll A, B, C, D, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;
ll ans = 0;

signed main() {
    cin >> A >> B;
    if ((A + B) % 2 == 0) {
        cout << abs(B - A) / 2 + min(A, B);
    } else {
        cout << "IMPOSSIBLE" << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#pragma region atcoder
/*#include <atcoder/all>
using namespace atcoder;
//These are for segment tree
/*int op(int a, int b){return max(a, b);}
int e(){return -1;}
int target;
bool f(int v){ return v < target;}
*/
#pragma endregion
#pragma region macros
using ll = long long;
using vi = vector<int>;
using vs = vector<string>;
using vl = vector<ll>;
using vb = vector<bool>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rrep(i, n) for(int i = n - 1; i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
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; }
template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<class T> T lcm(T a,T b){return a / gcd(a, b) * b;}
#pragma endregion
#pragma region debug for var, v, vv
#define debug(var)  do{std::cout << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){cout << endl;int cnt = 0;for(const auto& v : vv){cout << cnt << "th : "; view(v); cnt++;} cout << endl;}
#pragma endregion
const ll mod = 1000000007;
const int inf = 1001001001;
const ll INF = 1001001001001001001;
const int MAX = 2000005;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main(){
    int d, t, s; cin >> d >> t >> s;
  if(d > t * s) cout << "No" << endl;
  else cout << "Yes" << endl;
}


Measured memory_bytes: 3568
import java.util.Scanner;
class Main{
     public static void main(String[] args){
    	Scanner scan = new Scanner(System.in);
    	
    	double x1 = scan.nextDouble();
    	double y1 = scan.nextDouble();
    	double x2 = scan.nextDouble();
    	double y2 = scan.nextDouble();
    	
    	double num = Math.pow((x2 - x1), 2) + Math.pow((y2 - y1), 2);
    	double p = Math.sqrt(num); 
    	
    	System.out.println(String.format("%.8f", p));
     }
}

Measured memory_bytes: 28096
#include <bits/stdc++.h>
#include <string>
using namespace std;
 
int main(){
  int N, L;
  cin >> N >> L;
  vector<string> S(N);
  for(int i=0; i<N; i++){
    cin >> S.at(i);
  }
  sort(S.begin(), S.end());
  
  for(int i=0; i<N; i++){
    cout << S.at(i);
  }
  cout << ' ' << endl;  
}

Measured memory_bytes: 256
N, K = map(int, input().split())
S = list(input())

if S[K-1] == 'A':
    S[K-1] = 'a'
elif S[K-1] == 'B':
    S[K-1] = 'b'
elif S[K-1] == 'C':
    S[K-1] = 'c'

print(''.join(S))


Measured memory_bytes: 3060
#include <cstdio>
#include <algorithm>
using namespace std;
const int mod = 1e9 + 7;
int dp[105][105][105] , n , a[105];
int main() {
	scanf("%d" , &n);
	for (int i = 1; i <= 2 * n - 1; ++i) scanf("%d" , &a[i]);
	sort(a + 1 , a + 1 + 2 * n - 1);
	dp[n][1][0] = 1;
	for (int i = n - 1; i >= 1; --i) {
		int lf = (a[i] != a[i + 1]) , rf = (a[2 * n - i] != a[2 * n - i - 1]);
		for (int l = 0; l <= 2 * n - 1; ++l) {
			for (int r = 0; r <= 2 * n - 1; ++r) {
				if(dp[i + 1][l][r]) {
					int t = dp[i + 1][l][r];
					for (int dl = 1; dl <= l + lf; ++dl) dp[i][l + lf - dl + 1][r + rf + (dl > 1)] += t , dp[i][l + lf - dl + 1][r + rf + (dl > 1)] %= mod;
					for (int dr = 1; dr <= r + rf; ++dr) dp[i][l + lf + 1][r + rf - dr] += t , dp[i][l + lf + 1][r + rf - dr] %= mod;
				}
			}
		}
	} 
	long long ans = 0;
	for (int l = 0; l <= 2 * n - 1; ++l) {
		for (int r = 0; r <= 2 * n - 1; ++r) {
			ans = (ans + dp[1][l][r]) % mod;
		}
	}
	printf("%lld" , ans);
	return 0;
}

Measured memory_bytes: 2864
import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def measure(x):
    dist = [INF] * (N)
    dist[x] = 0
    que = deque()
    que.append(x)
    while que:
        cur = que.popleft()
        cur_dist = dist[cur]
        for next, c in edges[cur]:
            if dist[next] == INF:
                dist[next] = cur_dist + c
                que.append(next)
    
    return dist

N = ir()
INF = 10 ** 15
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = lr()
    edges[a-1].append((b-1, c))
    edges[b-1].append((a-1, c))

Q, K = lr()
dist = measure(K-1)
for _ in range(Q):
    x, y = lr()
    print(dist[x-1] + dist[y-1])


# 20


Measured memory_bytes: 48812
#include<iostream>
using ll=long long;

int main(){
  ll h,v;
  std::cin>>h>>v;
  ll r = (h*v)%2;
  if(h==1 || v==1)
    std::cout<<1<<std::endl;
  else{
    if(r==1)
    std::cout<<((ll)(h*v)/2)+1<<std::endl;
    else
    std::cout<<((ll)(h*v)/2)<<std::endl;
  }
}


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

// #define int long long
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) int(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const ll INF = 1e15;
const int MOD = 1e9+7;
const ll LINF = 1e18;

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n; cin>>n;
  cout<<0<<endl<<flush;
  string a0;
  cin>>a0;
  if(a0=="Vacant"){
    return 0;
  }
  ll l=1, r=n;
  rep(_,20){
    ll mid=(l+r)/2;
    cout<<mid<<endl<<flush;
    string res;
    cin>>res;
    if(res=="Vacant"){
      return 0;
    }
    
    if((mid%2==0 && res==a0) || (mid%2==1 && res!=a0)){
      l=mid+1;
    }else{
      r=mid;
    }
  }
}

Measured memory_bytes: 852
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>

using namespace std;

int main() {
	int i;
	int N, M;

	cin >> N >> M;

	vector<int> X(M);

	for (i = 0; i < M; i++)
		cin >> X[i];

	sort(X.begin(), X.end());

	vector<int> sub(M - 1);
	for (i = 0; i < M - 1; i++)
		sub[i] = abs(X[i + 1] - X[i]);

	sort(sub.begin(), sub.end(), greater<int>());

	int sum = 0;
	for (i = N - 1; i < M - 1; i++)
		sum += sub[i];

	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
int main()
{
	int T,a[100];
	scanf("%d",&T);
	int i,j,sum = 0;
	for(i = 0;i < T; i++)
	{
		scanf("%d",&a[i]);
		sum += a[i];
	}
	for(i = 0;i < T; i++)
	  for(j = i+1;j < T;j++)
	  	if(a[i]>a[j])
	  	{
	  		int t = a[i];
	  		a[i] = a[j];
	  		a[j] = t;
		  }
	if(sum%10!=0) printf("%d\n",sum);
	else
	{
		for(i = 0;i < T; i++)
    	{
		if(a[i]%10!=0) 
		{
			printf("%d\n",sum-a[i]);break;
		 } 
		if(i==T-1) printf("0\n");
    	}	
	}  	
 } 

Measured memory_bytes: 128
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

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

const ll MOD = 1000000007;
const ll MAX = 2000001;

ll mod(ll a){
  return a % MOD;
}

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

ll fac[MAX], finv[MAX], inv[MAX];

void nCrprep() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll nCr(ll n, ll r){
    if (n < r) return 0;
    if (n < 0 || r < 0) return 0;
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}

ll nCrcheep(ll n,ll r){
  if(r == 0) return 1;
  else if(r == 1) return n;
  else return nCrcheep(n-1,r-1)*n/r;
}

vector<pair<ll,ll>> prime_factorize(ll n){
  vector<pair<ll,ll>> res;
  
  for(ll i=2; i*i <= n; i++){
    if(n % i != 0) continue;
    
    ll ex = 0;
    while(n % i == 0){
      ex++;
      n /= i;
    }
    
    res.push_back({i,ex});
  }
  
  if(n != 1) res.push_back({n,1});
  
  return res;
  
}




int main(){
  ll x,a,b; cin >> x >> a >> b;
  
  cout << (x-a) % b << endl;
  
  
}

Measured memory_bytes: 3596
//shan61916
#include <bits/stdc++.h>
  using namespace std;
typedef   long long ll;
typedef   unsigned long long ull ;
typedef   double dll ;

#define   mp make_pair
#define   pb push_back
#define   ff first 
#define   ss second
#define   IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define   endl "\n" 
#define   pll pair<ll, ll>
#define   all(x) x.begin(), x.end()
#define   vll vector<ll> 

int main(){
 IOS
#ifdef SHAN
    freopen("input.txt" , "r" , stdin);  
#endif
  ll n;
  cin >> n;
  vector<ll> a(n);
  for(ll i  =0 ; i < n; i++) cin >> a[i];
  ll xx = 1; 
  ll i = 0;
  while(i < n-1) {
  	ll j = i+1; 
  	ll pp = a[i];
  	ll curr = 1;
  	while(j < n and a[j] <= pp) {
  		pp = a[j];
  		j++;
  		curr++;
  	}
  	// cout << curr << endl;
  	xx = max(curr, xx);
  	i = j;
  }
  cout << xx - 1 << endl;
  return 0;
} //good night.

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

using namespace std;

#define int long long
const double PI = 3.14159265358979323846;
typedef vector<int> vint;
typedef pair<int, int> pint;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
// cout << fixed << setprecision(20);

signed main() {
    int A,B;
    cin>>A>>B;
    if((A-B)&1==1)cout<<"IMPOSSIBLE"<<endl;
    else cout<<B+(A-B)/2<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
  
int main(){
  int n, x, i, j, k, c = 0;
  while(scanf("%d%d", &n, &x)){
    if(n == 0 && x == 0) break;
    for(i = 1;i < n - 1;i++)
      for(j = i + 1;j < n;j++)
        for(k = j + 1;k < n + 1;k++)
          if((i + j + k) == x) c++;
    printf("%d\n", c);
    c = 0;
  }
  return 0;
}


Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a),i##formax=(b);i<i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formax=(b);i>=i##formax;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)
#define show(x) cout<<#x<<" = "<<x<<endl;
#define all(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))
#define bitComb(a,n,k) for(int a##x,a##y,a=(1<<k)-1;a<(1<<n);a##x=a&-a,a##y=a+a##x,a=(((a&~a##y)/a##x)>>1)|a##y)
#define uniq(v) sort(all(v));v.erase(unique(all(v)), v.end())
#define bit(n) (1LL<<(n))
#define randInt(l,r) (uniform_int_distribution<ll>(l,r)(rnd))
#define randDouble(l,r) (uniform_real_distribution<double>(l,r)(rnd))
#define dout(d) printf("%.12f\n",d)

typedef long long ll;
typedef __int128_t lll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>ostream& operator<<(ostream& o,const pair<T,Y>& p){return o<<"("<<p.fi<<", "<<p.se<<")";}
template<typename A,size_t N,typename T>void Fill(A (&array)[N],const T&v){fill((T*)array,(T*)(array+N),v);}
lll gcd(lll a,lll b,lll &x,lll &y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll gcd(ll a,ll b){lll x=0,y=0;return gcd(a,b,x,y);}
ll modInv(ll a,ll m){lll x,y;gcd(a,m,x,y);return (x%m+m)%m;}
ll modPow(lll a,lll n,ll m){if(!a)return a;lll p=1;for(;n>0;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
bool isPrime(ll n){if(n<2||n%2==0)return n==2;lll t=n-1,d=t/(t&-t);for(lll a:{2,325,9375,28178,450775,9780504,1795265022})if(a%n){for(t=d,a=modPow(a,t,n);t!=n-1&&a!=1&&a!=n-1;a=a*a%n,t=t*2%n);if(a!=n-1&&t%2==0)return 0;}return 1;}
const int IINF = 1e9+6;
const ll LINF = 1e18;
const int MOD = 1e9+7;
const double PI = acos(-1);
const double EPS = 1e-10;
static random_device rd;
static mt19937 rnd(rd());

const int N = 1e5;

int n, t[N], a[N];
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n;
  FOR(i, 0, n) cin >> t[i];
  FOR(i, 0, n) cin >> a[i];
  int p = 0;
  FOR(i, 0, n){
    if(t[i]!=p) t[i] *= -1;
    p = abs(t[i]);
  }
  p = 0;
  ll ans = 1;
  FORR(i, n-1, 0){
    if(p!=a[i] && t[i]<0) if(a[i]+t[i]!=0) ans = 0;
    if(p==a[i] && t[i]<0) if(abs(t[i]) > a[i]) ans = 0;
    if(p!=a[i] && t[i]>0) if(a[i]>t[i]) ans = 0;
    if(p==a[i] && t[i]>0) ans = ans * min(t[i], a[i]) % MOD;
    p = a[i];
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.OptionalDouble;
import java.util.function.DoubleFunction;

public class Main {

	private interface F extends DoubleFunction<OptionalDouble> {
	}

	private static void setVMaxLine(int[] t, int[] v, List<F> vmaxs) {
		int n = t.length;
		int lastTime = 0;
		for (int i = 0; i < n; lastTime += t[i++]) {
			final int now = lastTime;
			final int time = t[i];
			final int vmax = v[i];
			// vmaxにラインを引いておく
			vmaxs.add(x -> {
				double dx = x - now;
				if (0 <= dx && dx <= time) {
					return OptionalDouble.of(vmax);
				}
				return OptionalDouble.empty();
			});
		}
	}

	private static void setUpLine(int[] t, int[] v, List<F> up) {
		int n = t.length;
		int lastTime = 0;
		double lastSpeed = 0;
		for (int i = 0; i < n; lastTime += t[i++]) {
			final double speed = lastSpeed;
			final int now = lastTime;
			final int time = t[i];
			final int vmax = v[i];

			final double needUpSpeed = vmax - speed;

			if (needUpSpeed > 0) {
				final double canUpSpeed = Math.min(needUpSpeed, time);
				up.add(x -> {
					double dx = x - now;
					if (0 <= dx) {
						return OptionalDouble.of(dx + speed);
					}
					return OptionalDouble.empty();
				});
				lastSpeed += canUpSpeed;
			} else {
				lastSpeed = vmax;
			}
		}
	}

	private static void setDownLine(int[] t, int[] v, int T, List<F> down) {
		final int n = t.length;
		int lastTime = T;
		double lastSpeed = 0;
		for (int i = n - 1; i >= 0; lastTime -= t[i--]) {
			final double speed = lastSpeed;
			final int now = lastTime;
			final int time = t[i];
			final int vmax = v[i];

			final double needUpSpeed = vmax - speed;

			if (needUpSpeed > 0) {
				final double canUpSpeed = Math.min(needUpSpeed, time);
				down.add(x -> {
					double dx = now - x;
					if (0 <= dx) {
						return OptionalDouble.of(dx + speed);
					}
					return OptionalDouble.empty();
				});
				lastSpeed += canUpSpeed;
			} else {
				lastSpeed = vmax;
			}
		}
	}

	public static void main(String[] args) throws IOException {
		try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
			br.readLine();
			int[] t = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
			int[] v = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

			int T = Arrays.stream(t).sum();

			List<F> functions = new ArrayList<>();

			setVMaxLine(t, v, functions);
			setUpLine(t, v, functions);
			setDownLine(t, v, T, functions);

			// 0.5ごとにマッピングする
			double sum = 0;
			double last = 0;
			for (int i = 0; i <= 2 * T; i++) {
				double x = i / 2.0;
				OptionalDouble min = functions.stream().map(f -> f.apply(x)).filter(OptionalDouble::isPresent)
						.mapToDouble(OptionalDouble::getAsDouble).min();

				if (min.isPresent()) {
					sum += last + min.getAsDouble();
					last = min.getAsDouble();
				} else {
					last = 0;
				}
			}
			System.out.println(sum / 4.0);
		}
	}

}


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

int main()
{
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n;
	scanf("%d",&n);
	if(n/10==9||n%10==9) printf("Yes\n");
	else printf("No\n");
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static long Mod = (long)1e9 + 7;
        static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            var DG = Sarray();
            var D = DG[0];
            var G = DG[1];
            var Pd = new long[D];
            var cd = new long[D];
            for (var i = 0; i < D; ++i)
            {
                var pc = Sarray();
                Pd[i] = pc[0];
                cd[i] = pc[1];
            }
            var dp = Enumerable.Repeat(-1L, 1001).ToArray();
            dp[0] = 0;
            for (var d = 0; d < D; ++d)
            {
                var next = Enumerable.Repeat(-1L, 1001).ToArray();
                next[0] = 0;
                var pt = 0L;
                for (var i = 1; i <= Pd[d]; ++i)
                {
                    pt = (d + 1) * 100 * i;
                    if (i == Pd[d]) pt += cd[d];
                    for (var j = i; j < dp.Length; ++j)
                    {
                        if (-1 == dp[j - i])
                            break;
                        next[j] = Max(next[j], Max(dp[j], dp[j - i] + pt));
                    }
                }
                dp = next;
            }
            for (var i = 0; i < dp.Length; ++i)
            {
                if (G <= dp[i])
                {
                    WriteLine(i);
                    return;
                }
            }
            //Out.Flush();
        }
    }
}

Measured memory_bytes: 13328
mtx = [list(map(int, input().split())) for _ in range(3)]

diff1 = mtx[0][0] - mtx[1][0]
diff2 = mtx[0][0] - mtx[2][0]

diff3 = mtx[0][0] - mtx[0][1]
diff4 = mtx[0][0] - mtx[0][2]

if mtx[0][1] - mtx[1][1] != diff1:
    print('No')
elif mtx[0][2] - mtx[1][2] != diff1:
    print('No')
elif mtx[0][1] - mtx[2][1] != diff2:
    print('No')
elif mtx[0][2] - mtx[2][2] != diff2:
    print('No')
elif mtx[1][0] - mtx[1][1] != diff3:
    print('No')
elif mtx[2][0] - mtx[2][1] != diff3:
    print('No')
elif mtx[1][0] - mtx[1][2] != diff4:
    print('No')
elif mtx[2][0] - mtx[2][2] != diff4:
    print('No')
else:
    print('Yes')


Measured memory_bytes: 9264
#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

#define FOR(i,init,n) for(int i = init; i < n ;i++)
#define REP(i,n)  FOR(i,0,n)
#define MON 1
#define SAT 6



int isMonSatPrime(int cand){

	if (cand % 7 != 1 && cand % 7 != 6){
		return(0);
	}
	int i = 6;
	int next = MON;

	if (cand < 2){
		return(0);
	}

	while (i > 1){
		if (cand % i == 0){
			break;
		}

		if (next == SAT){
			i += 5;
			next = MON;
		}
		else if (next == MON){
			i += 2;
			next = SAT;
		}
	}

	if (i == (cand)){
		return(1);
	}
	else{
		return(0);
	}
}

int main()
{
	while (1){
		int num;
		scanf("%d", &num);
		if (num == 1){
			break;
		}
		printf("%d:", num);
		int i = 6;
		int next = MON;
		while (i <= num){

			if (num%i == 0){
				if (isMonSatPrime(i) == 1){
					printf(" %d",i);
				}
			}

			if (next == SAT){
				i += 5;
				next = MON;
			}
			else if (next == MON){
				i += 2;
				next = SAT;
			}
		}
		puts("");
	}
	return 0;
}

Measured memory_bytes: 1036
#include<iostream>
using namespace std;
long mod=1e9+7,ans=1;
int n,m;
long fac[1<<17];
long power(long a,long b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;}
main()
{
	cin>>n>>m;
	fac[0]=1;
	for(long i=1;i<1<<17;i++)fac[i]=fac[i-1]*i%mod;
	for(int i=2;i*i<=m;i++)
	{
		if(m%i==0)
		{
			long p=0;
			while(m%i==0)m/=i,p++;
			ans=ans*fac[n+p-1]%mod*power(fac[n-1],mod-2)%mod*power(fac[p],mod-2)%mod;
		}
	}
	if(m>1)
	{
		ans=ans*fac[n]%mod*power(fac[n-1],mod-2)%mod;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 1280
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<cstring>
using namespace std;


class PMA{//Aho-Corasick
	int id;
	bool match;
	PMA *failure;
	PMA *next[256];
public:
	PMA(int id=0):id(id),match(false),failure(0){
		memset(next,0,sizeof(next));
	}
	~PMA(){
		for(int i=0;i<256;i++){
			if(next[i]&&next[i]!=this)delete next[i];
		}
	}
	int getID()const{return id;}
	bool matched()const{return match;}
	void build(const vector<string> &p){
		int num=0;
		for(int i=0;i<(int)p.size();i++){
			const string &s=p[i];
			PMA *t=this;
			for(int j=0;j<(int)s.size();j++){
				if(!t->next[s[j]])t->next[s[j]]=new PMA(++num);
				t=t->next[s[j]];
			}
			t->match=true;
		}
		queue<PMA*> q;
		for(int i=0;i<256;i++){
			if(next[i]){
				q.push(next[i]);
				next[i]->failure=this;
			}else next[i]=this;
		}
		while(!q.empty()){
			PMA *t=q.front();q.pop();
			for(int i=0;i<256;i++){
				if(t->next[i]){
					q.push(t->next[i]);
					PMA *r=t->failure->step(i);
					t->next[i]->failure=r;
					t->next[i]->match |= r->match;
				}
			}
		}
	}
	PMA *step(char c)const{
		const PMA *t=this;
		while(!t->next[c])t=t->failure;
		return t->next[c];
	}
};

string ch("DRUL");
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};

int h,w;
char m[52][52];
int dp[51][51][102];

struct Node{
	int y,x;
	PMA *p;
};
int bfs(PMA &pma){
	memset(dp,-1,sizeof(dp));
	Node a,b;
	for(int i=1;i<=h;i++)for(int j=1;j<=w;j++)if(m[i][j]=='S'){
		a.y=i;
		a.x=j;
		a.p=&pma;
	}
	queue<Node> q;
	dp[a.y][a.x][a.p->getID()]=0;
	q.push(a);
	while(!q.empty()){
		a=q.front();q.pop();
		int d=dp[a.y][a.x][a.p->getID()];
		for(int i=0;i<4;i++){
			b.y=a.y+dy[i];
			b.x=a.x+dx[i];
			if(m[b.y][b.x]=='#')continue;
			b.p=a.p->step(ch[i]);
			if(b.p->matched())continue;
			if(m[b.y][b.x]=='G')return d+1;
			if(dp[b.y][b.x][b.p->getID()]==-1){
				dp[b.y][b.x][b.p->getID()] = d+1;
				q.push(b);
			}
		}
	}
	return -1;
}

int main(){
	while(cin>>h>>w&&(h||w)){
		memset(m,'#',sizeof(m));
		for(int i=1;i<=h;i++)
			for(int j=1;j<=w;j++)
				cin>>m[i][j];
		int n;
		cin>>n;
		vector<string> p(n);
		for(int i=0;i<n;i++){
			cin>>p[i];
		}
		PMA pma;
		pma.build(p);
		cout<<bfs(pma)<<endl;
	}
	return 0;
}

Measured memory_bytes: 2452
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main()
{
  int n;
  cin >> n;
  vector<int> v(n);
  for (auto i = 0; i < n; i++) {
    cin >> v[i];
  }
  auto sum = accumulate(begin(v), end(v), 0);
  auto mean = double(sum) / n;
  vector<double> d(n);
  for (auto i = 0; i < n; i++) {
    d[i] = double(v[i]) - mean;
    if (d[i] < 0) d[i] *= -1;
  }
  auto ans = distance(begin(d), min_element(begin(d), end(d)));
  cout << ans << endl;
}


Measured memory_bytes: 888
/// time to restore the past glory

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
long long a, b, c, ans;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b >> c;
    if(c >= 1)
        ++ans, --c;
    ans += 2 * min(b, c);
    long long z = min(b, c);
    b -= z;
    c -= z;
    ans += min(a, c);
    z = min(a, c);
    a -= z;
    c -= z;
    ans += b;
    cout << ans;
    return 0;
}


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

using namespace std;

int m[502][502] = {};
vector<string> res;

int main(){
  int h, w;
  cin >> h >> w;
  for (int i=1;i<=h;i++) {
    for (int j=1;j<=w;j++) {
      int a;
      cin >> a;
      m[i][j] = a;
    }
  }
  for (int i=1;i<=h;i++) {
    for (int j=1;j<=w-1;j++) {
      if (m[i][j] % 2 == 1) {
	m[i][j]--;
	m[i][j+1]++;
	ostringstream ostr;
	ostr << i << " " << j << " " << i << " " << j+1;
	res.push_back(ostr.str());
      }
    }
  }
  for (int i=1;i<=h-1;i++) {
    if (m[i][w] % 2 == 1) {
      m[i][w]--;
      m[i+1][w]++;
      ostringstream ostr;
      ostr << i << " " << w << " " << i+1 << " " << w;
      res.push_back(ostr.str());
    }
  }
  cout << res.size() << endl;
  for (auto it = res.begin();it != res.end();it++) {
    cout << *it << endl;
  }

  // for (int i=1;i<=h;i++) {
  //   for (int j=1;j<=w;j++) {
  //     cout << m[i][j] << "\t";
  //   }
  //   cout << endl;
  // }

  return(0);
}


Measured memory_bytes: 6128
#include <iostream>
#include <fstream>
#include <string> 
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
#include <cctype>

#define BIT(a) (1 << (a))

using namespace std;

long long MOD = 1000000007;


long long mod_pow(long long x, long long n){
    long long res = 1;
    for(int i = 0;i < 60; i++){
        if(n >> i & 1) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}

int main(void){
	int a[4];
	for (int i = 0; i < 4; i++){
		cin >> a[i];
	}
	printf("%d\n", (a[0]>a[1]?a[1]:a[0])+(a[2]>a[3]?a[3]:a[2]));
	return 0;

}



Measured memory_bytes: 256
#include <cassert>
#include "limits.h"
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <random>
#include <memory>
#include <utility>
 
#define rep(i, a, b) for (long long (i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cerr << "debug " <<"LINE:"<<__LINE__<<"  "<< #i <<":"<< i << std::endl

 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}
 
long long pow_mod(long long a, long long b, long long mod=-1) {
  if ((a == 0)||(mod!=-1&&a%mod==0)) {
    return 0;
  }
 
  long long x = 1;
 
  while (b > 0) {
    if (b & 1) {
      x = (mod!=-1)?(x * a) % mod:x*a;
    }
    a = (mod!=-1)?(a * a) % mod:a*a;
    b >>= 1;
  }
  return x;
}
 
// const long long MOD = 998244353;
const long long MOD = 1e9 + 7;

using ll = long long;
using P = std::pair<ll, ll>;



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

  std::string s;
  std::cin>>s;

  ll n=s.size();

  std::vector<ll> a(n+1,0);

  rep(i,1,n+1){
    if((a[i-1]>>(s[i-1]-'a'))&1)a[i]=a[i-1]-(1ll<<(s[i-1]-'a'));
    else a[i]=a[i-1]+(1ll<<(s[i-1]-'a'));
  }

  std::vector<int> min(1ll<<26,MOD);

  min[0]=0;

  ll dp=0;

  rep(i,1,n+1){
    ll temp=min[a[i]];

    rep(j,0,26)chmin(temp,min[a[i]^(1ll<<j)]);
    dp=temp+1;
    chmin(min[a[i]],dp);
  }

  std::cout<<dp<<"\n";

  return 0;
}

Measured memory_bytes: 264340
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include <cmath>
#include <limits>
#include <utility>
#include <map>
#include <iomanip>
#include <queue>
#include <cctype>
#include <stack>


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

using namespace std;

ll gcd(ll a, ll b) {
	if (a < b) {
		ll tmp = a;
		a = b;
		b = tmp;
	}
	ll tmp = 0;
	while (a % b != 0) {
		tmp = b;
		b = a % b;
		a = tmp;
	}
	return b;
}

//131 C
int main(void) {
	ll a, b, c, d;
	cin >> a >> b >> c >> d;
	ll cd = (c * d) / gcd(c, d);
	ll cDiv = b / c - (a-1) / c;
	ll dDiv = b / d - (a - 1) / d;
	ll cdDiv = b / cd - (a - 1) / cd;
	cout << b - a + 1 - cDiv - dDiv + cdDiv << endl;
}


Measured memory_bytes: 256
b=input().split(" ")
a=[]
for i in b:
  a+=[int(i)]
ans=0
if a[1]-a[0]>=1:
  ans+=a[1]*2-1
elif a[0]-a[1]>=1:
  ans+=a[0]*2-1
else:
  ans+=a[0]+a[1]
print(ans)
  

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

typedef unsigned long long int ull;
typedef long long int ll;
typedef vector<ll> vi;

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define nl cout<<'\n'
#define pb push_back
#define all(s) s.begin(),s.end()
#define bs binary_search

#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) (a)*(b)/(__gcd((a),(b)))

const int Mod=1e9+7;
#define sum(a,b) (((a)%Mod)+((b)%Mod))%Mod
#define sub(a,b) (((a)%Mod)-((b)%Mod))%Mod
#define mul(a,b) (((a)%Mod)*((b)%Mod))%Mod
#define digit(x) floor((log10(x))+1)


#define count1(x) __builtin_popcount(x)

#define dbg(x) cout << #x <<":"<<x<<endl;

bool isPowerOfTwo (int x)  
{  
    /* First x in the below expression is for the case when x is 0 */
    return x && (!(x&(x-1)));  
} 

ll pow(ll x, ll y, ll mod)
{
	int ans=1;
	while(y)
	{
		if(y&1)
			ans=(ans*x)%mod;
		y/=2;
		x=(x*x)%mod;
	}
	return ans;
}

int main()
{
	fast;
	ll i,ans=0;
	string s,t;
	cin >> s >> t;
	for(i=0;i<s.length();i++)
	{
		if(s[i]!=t[i])
			ans++;
	}
	cout << ans << endl;
}

Measured memory_bytes: 3888
#include <iostream>
#include <string>
// #include <vector>
#include <map>
#define REP(i,k,n) for(int(i)=(k);(i)<(n);(i)++)
using namespace std;

const int MAX_N = 100;
// const long MAX_W = (long)1e9;

int N;
long w[MAX_N], v[MAX_N];
// メモ化テーブル
typedef pair<int,long> P;
map<P,long> dp;

// i番目以降の品物から重さの総和が
// j以下となるように選ぶ
// 戻り値: その選び方をしたときの価値の総和
// j: 残りの容量 (重さ)
long rec(int i, long j)
{
  // メモを利用
  if (dp.count(P(i,j))) return dp[P(i,j)];

  long res;
  if (i == N) res = 0;
  // 商品 i は入らない
  // 他の商品が入るか試す
  else if (j < w[i]) res = rec(i+1, j);
  // 商品 i を入れる場合・入れない場合を両方とも試して、
  // 大きい方をとる
  else res = max(rec(i+1, j),
                 rec(i+1, j - w[i]) + v[i]);
  dp[P(i,j)] = res;
  return res;
}

int main()
{
  long W;
  cin >> N >> W;
  REP(i,0,N) cin >> w[i] >> v[i];

  long res = rec(0, W);
  cout << res << endl;

  return 0;
}


Measured memory_bytes: 6400
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <cmath>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define INF 1145141919
typedef long long int ll;
using namespace std;

template <typename T>
istream &operator>>(istream &is, vector<T> &vec)
{
    for (T &x : vec)
        is >> x;
    return is;
}

ll gcd(ll m, ll n)
{
    if ((0 == m) || (0 == n))
        return 0;
    while (m != n)
    {
        if (m > n)
            m = m - n;
        else
            n = n - m;
    }
    return m;
}

ll lcm(ll m, ll n)
{
    if ((0 == m) || (0 == n))
        return 0;
    return ((m / gcd(m, n)) * n);
}

int ctoi(const char c)
{
    if ('0' <= c && c <= '9')
        return (c - '0');
    return -1;
}

int calc(int n){
    if(n%2==0)  return n/2;
    return 3*n+1;
}

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

    set<int> val;
    val.insert(s);

    int i=2;
    while(1){
        s = calc(s);
        if(val.find(s)==val.end())  val.insert(s);
        else{
            cout << i << endl;
            return 0;
        }
        i++;
    }

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>

using namespace std;

typedef long long in;

int main(){
    in a,b;
    char c;
    cin >> a;
    cin >> c;
    cin >> b;
    if(c=='+')
        cout << a+b;
    else
        cout << a-b;
    cout << endl;
    return 0;
}


Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007

int main() {
  int n, m;
  cin >> n >> m;
  long x[n], y[m];
  for (int i=0; i<n; i++)
    cin >> x[i];
  for (int i=0; i<m; i++)
    cin >> y[i];
  long sigmax = 0, sigmay = 0, ans;
  for (int i=0; i<n; i++) {
    sigmax += x[i]*(2*i-n+1);
    sigmax %= MOD;
  }
  for (int i=0; i<m; i++) {
    sigmay += y[i]*(2*i-m+1);
    sigmay %= MOD;
  }
  ans = (sigmax*sigmay) % MOD;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>

#define max(a, b) ((a)>(b)?(a):(b))

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

  int h[n][3];
  int t[n][3];

  for (i=0; i<n; i++)
    scanf("%d %d %d", &h[i][0], &h[i][1], &h[i][2]);

  t[n-1][0] = h[n-1][0];
  t[n-1][1] = h[n-1][1];
  t[n-1][2] = h[n-1][2];

  for (i=n-2; i>=0; i--) {
    t[i][0] = max(t[i+1][1],t[i+1][2])+h[i][0];
    t[i][1] = max(t[i+1][2],t[i+1][0])+h[i][1];
    t[i][2] = max(t[i+1][0],t[i+1][1])+h[i][2];
  }
  printf("%d\n", max(max(t[0][0], t[0][1]), t[0][2]));
  return 0;
}


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

constexpr int N_max = 200'000;
int main() {
    int n;
    cin >> n;

    auto count = 0LL;
    const auto width = [n] {
        for (int x = n, w = 1;;) {
            if (x <= 9)
                return w;
            x /= 10;
            ++w;
        }
    }();

    constexpr int middle[] = {-1, -1, 0, 90, 990, 9990, 99990};
    constexpr int tops[] = {0, 1, 10, 100, 1000, 10000, 100000};

    const auto n_btm = n % 10;
    for (int a = 1; a <= n; ++a) {
        const auto a_btm = a % 10;
        if (!a_btm)
            continue;
        const auto a_top = [a]() {
            for (int x = a;; x /= 10) {
                if (x <= 9)
                    return x;
            }
        }();
        const auto b_top = a_btm;
        const auto b_btm = a_top;
        // cerr << "A is " << a << " b_top " << b_top << " b_btm " << b_btm << "\n";

        // for b_width==1
        if (a_btm == a_top && a_btm <= n) {
            //cerr << "counting++\n";
            count++;
        }

        for (auto b_width = 2; b_width <= width; ++b_width) {
            auto tens = 1;
            for (int i = 2; i <= b_width; ++i)
                tens *= 10;
            auto b_min = tens * b_top + b_btm;
            auto b_max = tens * b_top + (tens - 10) + b_btm;

            if (n < b_min)
                continue;

            if (n < b_max) {
                b_max = n - n_btm + b_btm;
                if (b_max > n)
                    b_max -= 10;
                assert(b_max <= n);
            }
            if (b_max < b_min)
                continue;

            auto b_count = (b_max / 10 - b_min / 10) + 1;
            count += b_count;

            //cerr << "B " << b_min << ":" << b_max << " count " << b_count << " total " << count << "\n";
        }
    }

    cout << count;
    return 0;
}


Measured memory_bytes: 256