akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long int ull;
#define rep(i,a,n) for(ll i = (a);i < (n);i++)
#define all(v) (v).begin(),(v).end()
#define clr(a,b) memset((a),(b),sizeof(a))
#define sz size()
#define pb push_back
#define prull(x) cout << x << endl
int n;
ull a,ans;
vector<ull> v;

ull gcd(ull x,ull y){
  if(x > y)swap(x,y);
  if(x == 0)return y;
  return gcd(x,y%x);
}

ull lcm(ull x,ull y){
  return x/gcd(x,y)*y;
}

int main(){
  cin >> n;
  rep(i,0,n){
    cin >> a;
    v.pb(a);
  }
  if(n == 1){
    cout << a << endl;
    return 0;
  }
  ans = lcm(v[0],v[1]);
  rep(i,2,v.sz){
    ans = lcm(ans,v[i]);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl  "\n"
typedef long long ll;
 
int gcd(int a, int b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 

vector<ll> mnp(1e5+1 ,1e15 ) ;
map< pair<int ,int>, int > mp ; 

void dfs( int u  , int p, vector< vector<int> > &df,vector<int > vis, ll cost  ){
       // cout<<u<<endl;
        vis[u] = 1 ;
        mnp[u] = min( mnp[u], cost )     ;
        for( auto i  : df[u] ){
                if( vis[i] == 0  ) dfs( i, u , df, vis, cost+ mp[ {u, i} ]   );
            }
    }   
 

 int  main(){
            ll a= 0 ;
            string s ;  cin>>s ; 
            for( auto i : s ){
                    a+= (int)( i - '0' ); 
                }
            if( a%9 == 0 ) cout<<"Yes"; 
            else cout<<"No"; 
        }

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

#define DUMP(x) cerr << #x << "=" << x << endl
#define DUMP2(x, y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<")"<< endl
#define BINARY(x) static_cast<bitset<16> >(x)

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

#define in_range(x, y, w, h) (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))
#define ALL(a) (a).begin(),(a).end()

typedef long long ll;
const int INF   = 1e9;
const ll  INFLL = 1e18;
typedef pair<int, int> PII;
int dx[4]={0, -1, 1, 0}, dy[4]={-1, 0, 0, 1};

int N;
vector<vector<int>> G;
vector<int> pre_path, path1N;
set<int> path1N_node;

void get_path_dfs(int v, int pre)
{
    pre_path[v] = pre;

    for (auto u : G[v]) {
        if (u == pre) continue;

        get_path_dfs(u, v);
    }
}

void get_path()
{
    get_path_dfs(0, -1);

    path1N.push_back(N-1);
    path1N_node.insert(N-1);

    for (int u=pre_path[N-1]; u!=-1; u=pre_path[u]) {
        path1N.push_back(u);
        path1N_node.insert(u);
    }

    reverse(ALL(path1N));
}

int cnt_node(int v, int pre)
{
    int res = 1;
    for (auto u : G[v]) {
        if (u == pre || path1N_node.count(u)) continue;
        res += cnt_node(u, v);
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> N;
    G.resize(N);
    pre_path.resize(N);

    rep(i, N-1) {
        int A, B;
        cin >> A >> B;
        A--, B--;
        G[A].push_back(B);
        G[B].push_back(A);
    }

    get_path();
    // for (auto u : path1N) cerr << u << endl;

    int score_fennec = 0, score_snuke = 0;
    int NN = path1N.size();
    for (int i=0; i<NN; i++) {
        int tmp = cnt_node(path1N[i], -1);
        if ((i+1) <= (NN + 2 - 1) /2) {
            score_fennec += tmp;
        } else {
            score_snuke += tmp;
        }
    }
    // DUMP2(score_fennec, score_snuke);

    cout << (score_fennec > score_snuke ? "Fennec" : "Snuke") << endl;
}

Measured memory_bytes: 15864
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx=200+10;
char s[maxx];
int mp[maxx][maxx],n,d[maxx];
int vis[maxx];
vector<int> v,b;
queue<int> q;
void dfs(int x){
    v.push_back(x);
    vis[x]=1;
    for(int i=1;i<=n;i++){
        if(vis[i]||(!mp[x][i])) continue;
        dfs(i);
    }
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        for(int j=1;j<=n;j++){
            mp[i][j]=s[j]-'0';
        }
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
        ll res=0;
        if(vis[i]) continue;
        v.clear();
        dfs(i);
        //puts("0000");
        for(auto x:v){
            //cout<<x<<endl;
            memset(d,-1,sizeof d);
            while(!q.empty()) q.pop();
            q.push(x);
            d[x]=1;
            while(!q.empty()){
                int t=q.front(); q.pop();
                for(int j=1;j<=n;j++){
                    if(mp[t][j]&&d[j]==d[t]){
                        puts("-1"); return 0;
                    }
                    if(mp[t][j]&&(d[j]==-1)){
                        d[j]=d[t]+1;
                        q.push(j);
                    }
                }
            }
            ll tres=0;
            for(int j=1;j<=n;j++){
                tres=max(tres,1ll*d[j]);
            }
            res=max(res,tres);
        }
        ans+=res;
	}
	cout<<ans<<endl;
}


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

int main(){
  int a, b, c, d, e, k;
  cin >> a >> b >> c >> d >> e >> k;
  if (e-a <= k){
    cout << "Yay!" << endl;
  }
  else {
    cout << ":(" << endl;
  }
}

Measured memory_bytes: 256
class UnionFind():
    # コンストラクタ
    def __init__(self, n):
        # 要素数
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n

    # 要素xが属するグループの根を返す(経路圧縮)
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 要素xが属するグループと要素yが属するグループとを併合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y: return

        if self.parents[x] > self.parents[y]: x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    # 要素x,yが同じグループに属するかどうかを返す
    def same(self, x, y):
        return self.find(x) == self.find(y)

######################################################
N,M = map(int, input().split())

idx = [0] * N
for i, p in enumerate(map(int,input().split())):
    idx[p - 1] = i

UF = UnionFind(N)

for _ in range(M):
    x,y = map(int, input().split())
    UF.union(x - 1, y - 1)

ans = 0
for n in range(N):
    if UF.same(n, idx[n]):
        ans += 1

print(ans)

Measured memory_bytes: 88812
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;

int main(){
  ll N,W;
  cin >> N >> W;
  ll w[N], v[N];
  REP(i,N){
    cin >> w[i] >> v[i];
  }
  ll VMAX = 200000;
  ll dp[2][VMAX]; //i個目まで使って価値の総和jのときの重さの最小値
  fill(dp[0],dp[2],INF);
  dp[0][0] = 0;
  for(ll i = 1; i <= N; i++){
    REP(j,VMAX){
      if(j-v[i-1]<0){
        dp[1][j] = dp[0][j];
      }else{
        dp[1][j] = min(dp[0][j],dp[0][j-v[i-1]]+w[i-1]);
      }
    }
    REP(j,VMAX) dp[0][j] = dp[1][j];
  }
  ll ans = 0;
  REP(j,VMAX){
    if(dp[1][j]<=W) ans = j;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3328
package main

import (
	"bufio"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	iv, _ := strconv.Atoi(scanString())
	return iv
}

func scanString() string {
	sc.Scan()
	return sc.Text()
}

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 100001), 100001*100)
}

func main() {
	h, w, _ := scanInt(), scanInt(), scanInt()
	s := make([]string, h)
	for i := range s {
		s[i] = scanString()
	}

	sumW := make([][]int, h)
	sumH := make([][]int, h)
	for i := range s {
		sumW[i] = make([]int, w)
		sumH[i] = make([]int, w)
		for j := range s[i] {
			if j-1 >= 0 {
				sumW[i][j] = sumW[i][j-1]
			}
			if s[i][j] == '#' {
				sumW[i][j]++
			}
		}
	}
	for j := 0; j < w; j++ {
		for i := 0; i < h; i++ {
			if i-1 >= 0 {
				sumH[i][j] = sumH[i-1][j]
			}
			if s[i][j] == '#' {
				sumH[i][j]++
			}
		}
	}

	ans := make([][]int, h)
	for i := range ans {
		ans[i] = make([]int, w)
	}

	cnt := 1
	li := -1
	for i := range s {
		lj := -1
		for j := range s[i] {
			if s[i][j] == '#' {
				fi := i
				if sumH[i][j] == sumH[h-1][j] {
					fi = h - 1
				}
				fj := j
				if sumW[i][j] == sumW[i][w-1] {
					fj = w - 1
				}
				for ni := li + 1; ni <= fi; ni++ {
					for nj := lj + 1; nj <= fj; nj++ {
						ans[ni][nj] = cnt
					}
				}
				lj = j
				cnt++
			}
		}
		if sumW[i][w-1] > 0 {
			li = i
		}
	}

	var wr = bufio.NewWriter(os.Stdout)
	for _, row := range ans {
		for i, v := range row {
			wr.WriteString(strconv.Itoa(v))
			if i < w-1 {
				wr.WriteString(" ")
			} else {
				wr.WriteString("\n")
			}
		}
	}
	wr.Flush()
}


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

int main() {
  string S,T;
  cin >>S >>T;
  int n=0;
  if(S.at(0)==T.at(0)){
    n++;
  }
  if(S.at(1)==T.at(1)){
    n++;
  }
  if(S.at(2)==T.at(2)){
    n++;
  }
  cout << n;
  
  
 
}


Measured memory_bytes: 256
N = int(input())
S = [i for i in input()]
r = 0
g = 0
b = 0

for i in S:
    if i == "R":
        r += 1
    elif i == "G":
        g += 1
    else:
        b += 1

ans = r * g * b

for i in range(N):
    for j in range(i+1, N):
        k = j+j-i
        if k >= N:
            break
        if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            ans -= 1
 
print(ans)

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

using namespace std;

int main(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    int n;
    cin >> n;
    vector<long long> arr(n,0);
    for(int i=0; i<n; i++){
        cin >> arr[i];
    } 
    int cnt = 0;
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            for(int k=j+1; k<n; k++){
                if(arr[i]!=arr[j] && arr[j]!=arr[k] && arr[i]!=arr[k]){
                    if(arr[i]+arr[j] > arr[k] && arr[i]+arr[k] > arr[j] && arr[k] + arr[j] > arr[i]){
                        cnt++;
                    } 
                }
            }
        }
    }
    cout << cnt << endl;
    


    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <climits>
#define ll long long
#define MAX 25 * 1e13
#define N  200010

#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define MP(A,B) make_pair(A,B)
#define PB(X) push_back(X)
#define EB(X) emplace_back(X)
#define REP(i,a) for(int i=0;i<(a);++i)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define range(a) a.begin(), a.end()
#define VI vector<int>;
#define PI 3.14159265358979323846

using namespace std;
int MOD = 1000000007;


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,q;
  cin >> n;
  int has[100001] = {0};
  vector<ll> a(n,0);
  ll sum = 0;
  REP(i,n) cin >> a[i];
  REP(i,n) {
    sum += a[i];
    has[a[i]] ++;
  }
  
  cin >> q;
  REP(_,q) {
    int b,c;
    cin >> b >> c;
    ll cntb = has[b];
    sum = sum - cntb * b + cntb * c;
    has[b] = 0;
    has[c] += cntb;
    cout << sum << endl;
  }

  return 0;
}



Measured memory_bytes: 4516
#include <bits/stdc++.h>
#define PI acos(-1)
typedef long long ll ;
using namespace std ;

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

    int n , digits ;
    double d = 0 ;
    ll prod = 1 ;
    cin >> n ;
    for(int i = 0 ; i < n ; i++)
    {
        ll value ;
        cin >> value ;
        prod = prod * value ;
        d = d + log10(value) ;
    }
    digits = floor(d) + 1 ;
    if(digits > 19) cout << -1 << "\n" ;
    else
    {
        if(prod > 1000000000000000000) cout << -1 << "\n" ;
        else cout << prod << "\n" ;
    }
}

Measured memory_bytes: 3940
#include <bits/stdc++.h>
using namespace std;
#define MOD1 1000000007
#define MOD2 1000000009
#define ll long long int
#define li long int
#define fi first
#define se second
#define ffl fflush(stdout);
#define whT int t; cin>>t; while(t--)
int main() 
{
	
	int ans;
	for(int i=0;i<5;i++) {
		int t;
		cin>>t;
		if(t==0) {
			ans=i+1;
		}
	}
	cout<<ans;

}


Measured memory_bytes: 3592
#ソートして左から数えるver
N = int(input())
a = sorted([int(input()) for i in range(N)])

count_list = [1]*len(set(a))
j = 0

for i in range(len(a)-1):
	if a[i] == a[i+1]:
		count_list[j] += 1
	else:
		j += 1

print(sum([ i%2 == 1  for i in count_list]))

Measured memory_bytes: 13756
#include <cstdio>

const int size = 1000005;
int n;
bool ispm[size];

int get(int n) {
	int ans = 0;
	for ( int i = 1; i <= n; i ++ ) ispm[i] = 1;
	for ( int i = 2; i <= n; i ++ ) {
		if(ispm[i]) {
			ans ++;
			for ( int j = 2*i; j <= n; j += i) ispm[j] = 0;
		}
	}

	return ans;
}

int main() {
	while( scanf("%d", &n) != EOF ) {
		printf("%d\n", get(n));
	}

	return 0;
}

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

int main() {
    string S;
    cin >> S;
    set<P> paren;
    for(int i = 0; i < S.size(); i++) {
        if(S[i] != '(') continue;
        int depth = 1;
        for(int j = i + 1; j < S.size(); j++) {
            if(S[j] == '(') depth++;
            if(S[j] == ')') depth--;
            if(depth == 0) {
                paren.emplace(i, j);
                break;
            }
        }
    }

    int apos;
    for(int i = 0; i < S.size(); i++) if(S[i] == '*') {
        apos = i;
        break;
    }

    int ans = 0;
    for(auto &&ele : paren) {
        int l, r;
        tie(l, r) = ele;
        if(l < apos && apos < r) ans++;
    }

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



Measured memory_bytes: 3204
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] B = new int[N - 1];
        for(int i = 0; i < N - 1; i++) {
            B[i] = scanner.nextInt();
        }
        int ans = B[0] + B[N - 2];
        for(int i = 1; i < N - 1; i++) {
            ans += Math.min(B[i], B[i - 1]);
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
using namespace std;
#define getbit(n, i) (((n) & (1LL << (i))) != 0) 
#define setbit0(n, i) ((n) & (~(1LL << (i)))) 
#define setbit1(n, i) ((n) | (1LL << (i))) 
#define togglebit(n, i) ((n) ^ (1LL << (i))) 
#define lastone(n) ((n) & (-(n))) 
char gap = 32;
template<typename T> 
ostream& operator<<(ostream &os, const vector<T> &v) { 
    os << '{'; 
    for (const auto &x : v) os << gap << x;
        return os << '}'; 
}
template<typename A, typename B> 
ostream& operator<<(ostream &os, const pair<A, B> &p) {
        return os << '(' << p.first << gap << p.second << ')';
}

template <class T>
void read(T &x) {
    char c;
    for (c = getchar(); c < '0' || c > '9'; c = getchar())
        ;
    for (x = 0; c <= '9' && c >= '0'; c = getchar()) x = x * 10 + (c & 15);
}
#define ll long long 
#define lll __int128_t
#define pb push_back
#define mp make_pair
typedef pair < int,int> ii;
typedef vector<ii> vii;
typedef vector<ll>vl;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll hashPrime = 1610612741;
ll dp[200][200005];
ll weight[200005];
ll val[200005];   
int main()
{
 
    ll n,i,j,k,l,W;
    scanf("%lld%lld",&n,&W);
    for(i=1;i<=n;i++){
    	scanf("%lld%lld",&weight[i],&val[i]);
	}
	for(i=0;i<=n;i++){
		for(j=0;j<=100000;j++){
			if(j==0)
			dp[i][j]=0;
			else
			dp[i][j]=-1;
		}
	}
	ll sum=0;
	for(i=1;i<=n;i++){
		sum+=val[i];
		for(j=1;j<=sum;j++){
			if(j-val[i]>=0&&dp[i-1][j-val[i]]!=-1){
				if(dp[i-1][j]!=-1){
					dp[i][j]=min(dp[i-1][j],dp[i-1][j-val[i]]+weight[i]);
				}
				else{
					dp[i][j]=dp[i-1][j-val[i]]+weight[i];
				}
			}
			else{
			   	if(dp[i-1][j]!=-1){
					dp[i][j]=dp[i-1][j];
				}	
			}
		}
	}
	ll maxi=-1;
	for(i=1;i<=n;i++){
		for(j=1;j<=sum;j++){
			if(dp[i][j]<=W&&dp[i][j]!=-1)
			maxi=j;
		}
	}
	printf("%lld",maxi);
    return 0;
}

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

B=[a-1 for a in A]

S=[0]
for b in B:
    S.append((S[-1]+b)%K)

from collections import Counter
C=Counter()

ANS=0
for i in range(N+1):
    ANS+=C[S[i]]
    #print(i,ANS,C)
    C[S[i]]+=1

    if i-K+1>=0:
        C[S[i-K+1]]-=1


print(ANS)

Measured memory_bytes: 114316
let n = read_int ()
let s = read_line ()

let rec f maxim now str =
  let len = String.length str in
  if len = 0 then maxim
  else if str.[0] = 'I' then
    f (max maxim (now + 1)) (now + 1) (String.sub str 1 (len - 1))
  else f maxim (now - 1) (String.sub str 1 (len - 1))

let () = f 0 0 s |> Printf.printf "%d\n"

Measured memory_bytes: 384
while 1:
    cust_list=[]
    ans=0
    n=int(input())
    if n==0:break
    for i in range(n):
        cust_list.append(int(input()))
    cust_list.sort()
    for i in range(len(cust_list)):
        ans+=sum(cust_list[:i])
    print(ans)


Measured memory_bytes: 5720
def tax(p,x):
    return p*(100 + x)//100
    
def solve(x,y,s):
    ans = 0
    for i in range(1,s):
        for j in range(1,s):
            tot = tax(i,x) + tax(j,x)
            if tot == s:
                ans = max(ans,tax(i,y) + tax(j,y))
            elif tot > s:
                break
    print(ans)

def main():
    while True:
        x,y,s = map(int,input().split())
        if s == 0:
            return
        solve(x,y,s)
if __name__ == '__main__':
    main()


Measured memory_bytes: 5600
//problem url : https://atcoder.jp/contests/dp/tasks/dp_i
// author : siddharth mani
#include <bits/stdc++.h>
#define dd double
using namespace std;

int n;
dd arr[3001];
dd dp[3001][3001];

//each state of dp is dependent on two variables : index and number of heads uptill that index
dd rec(int idx, int noH)
{
    if (idx == n+1)
    {
        if(noH > (n / 2))
        {
            return 1.0;
        }
        else
        {
            return 0.0;
        }
        
    }
    if (dp[idx][noH] != -1)
    {
        return dp[idx][noH];
    }

    dp[idx][noH] = rec(idx + 1, noH + 1) * arr[idx] + rec(idx + 1, noH) * (1.0 - arr[idx]);
    return dp[idx][noH];
}

int main()
{
    for (int i = 0; i <= 3000; i++)
    {
        for (int j = 0; j <= 3000; j++)
        {
            dp[i][j] = -1;
        }
    }

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }
    dd ans = rec(1, 0);
    cout <<setprecision(10)<<ans;
    return 0;
}

Measured memory_bytes: 70784
A,B,C,D = map(int,input().split())

import fractions

def f(N):
    red = N//C
    red += N//D
    X = (C * D // fractions.gcd(C, D))
    red -= N//X
    return N - red

ans = f(B) - f(A-1)
print(ans)

Measured memory_bytes: 5048
#include <iostream>

using namespace std;

struct mat {
    unsigned long long a, b, c, d;
    mat() {
        a = 1;
        b = 1;
        c = 1;
        d = 0;
    }

    void mul(mat other) {
        unsigned long long na = a * other.a + b * other.c;
        unsigned long long nb = a * other.b + b * other.d;
        unsigned long long nc = c * other.a + d * other.c;
        unsigned long long nd = c * other.b + d * other.d;
        a = na; b = nb; c = nc; d = nd;
    }

    mat copy() {
        mat m;
        m.a = a;
        m.b = b;
        m.c = c;
        m.d = d;
        return m;
    }

    void dump() {
        cout << a << ", " << b << ", " << c << ", " << d << "\n";
    }
};

void power(mat& m, int n) {
    if (n == 1)
        return;

    for (int i = 1; i < n; i++)
        m.mul(mat());

//    cout << "result: ";
 //   m.dump();
}
int main() {
    int n;
    cin >> n;

    if (n == 1) {
        cout << "1\n";
        return 0;
    }
    if (n == 0) {
        cout << "2\n";
        return 0;
    }
    mat m;
    power(m, n - 1);

    cout << (m.a + m.b * 2) << "\n";
}

Measured memory_bytes: 256
from collections import Counter

n,a = map(int,input().split())
x = list(map(int,input().split()))

dp = [Counter()]
# [何個使ったか][sum]
dp[0][0] = 1
for i,j in enumerate(x):
	dp.append(Counter())
	for k in reversed(range(i+1)):
		for m,p in dp[k].items():
			dp[k+1][m+j] += p

res = 0
for i in range(1,n+1):
	res += dp[i][i*a]
print(res)

Measured memory_bytes: 5492
N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

X = 0
Y = 0

for i in range(N):
    if V[i] > C[i]:
        v = V[i]
        c = C[i]
        X = X + v
        Y = Y + c

print(X-Y)

Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<sstream>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<cmath>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<numeric>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

int main()
{

    ll a,b,k;
    cin >> a >> b >> k;
    ll ansA,ansB;
    if(a>=k)
    {
        ansA = a-k;
        ansB = b;
    }
    else
    {
        ansA = 0;
        if(a-k+b<0)
        {
            ansB = 0;
        }
        else
        {
            ansB = a-k+b;
        }
    }

    cout << ansA << " " << ansB << endl;    

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>




int main(void){
int a,b;
char s[5];
for(;;){
scanf("%d %s %d",&a,s,&b);
if(s[0]=='?'){break;}
if(s[0]=='+'){printf("%d\n",a+b);}
if(s[0]=='-'){printf("%d\n",a-b);}
if(s[0]=='*'){printf("%d\n",a*b);}
if(s[0]=='/'){printf("%d\n",a/b);}


}

return 0;
}



Measured memory_bytes: 2064
#include <iostream>
using namespace std;
int main(void){
    int a, b, c, d, i, j;
    cin >> a >> b >> c >> d;
    
    for(i=0; c > 0; i++){
        c = c-b;
    }
    for(j=0; a > 0; j++){
        a = a-d;
    }
    if(i > j){
        cout << "No" << endl;
    }else if(j > i){
        cout << "Yes" << endl;
    }else if(i == j){
        cout << "Yes" << endl;
    }
    return 0;
}

Measured memory_bytes: 3576
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() { 
  ios::sync_with_stdio(false); cin.tie(0);
  //f
  long long n, d, k;
  cin >> n >> d >> k;
  vector<pair<long long, long long>> x(n);
  for (int i = 0; i < n; i++) {
    cin >> x[i].first >> x[i].second;
    x[i].second = (x[i].second + k - 1) / k;
  }
  sort(x.begin(), x.end());
  priority_queue<long long, vector<long long>, greater<long long>> que;
  map<long long, long long> segs;
  long long cur = 0;
  d *= 2;
  for (int i = 0; i < n; i++) {
    while (que.size() && que.top() < x[i].first) {
      long long ed = que.top();
      que.pop();
      cur -= segs[ed];
    }
    if (x[i].second <= cur) continue;
    que.push(x[i].first + d);
    segs[x[i].first + d] = x[i].second - cur;
    cur = x[i].second;
  }
  long long ans = 0;
  for (auto& p : segs) ans += p.second;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 15872
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int main(void) {
  int i,j;
  int n;
  cin>>n;
  vi a(n);
  rep(i,n)cin>>a[i];
  int n2,n4,ne;
  n2=n4=ne=0;
  rep(i,n)
    if(a[i]%4==0)n4++;
    else if(a[i]%2==0)n2++;
    else ne++;
  //  cout<<n4<<" "<<n2<<" "<<ne<<endl;
  if(ne==0 || ne<=n4)cout<<"Yes"<<endl;
  else if(ne-1==n4 && n2==0)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;

}


Measured memory_bytes: 640
#include<stdio.h>

int main(void){

    long int A,B,ans;
    char op;

    scanf("%ld %c %ld",&A,&op,&B);

    if(op == '+'){
        ans = A + B;
    }else{
        ans = A - B;
    }

    printf("%ld\n",ans);
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2000;
int a[maxn+5],n,now;
int num[maxn*maxn+5],T;
bitset<maxn*maxn+maxn> S;
int main(){
	scanf("%d",&n),S[0]=1;
	for(int i=1;i<=n;i++){
		scanf("%d",&now);
		S|=S<<now;
	}
	for(int i=1;i<=maxn*maxn;i++) if(S[i]) num[++T]=i;
	printf("%d\n",num[(T+1)>>1]);
	return 0;
}

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

int main() {
 char c;
  cin >> c;
  
  if(c == 'a' ||c == 'i' ||c == 'u' ||c == 'e' ||c == 'o' ){
    cout << "vowel" << endl;
  }
  else{
    cout << "consonant" << endl;
  }
}

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

int h, w;
char a[110][110];
int f(int y, int x) {
	return y * w + x;
}

template<typename T>
struct Dinic {
	struct Edge {
		// cap := 容量
		// rev := 逆辺のID
		const int to;
		T cap;
		const int rev;
		Edge(const int to, const T cap, const int rev) :
			to(to),
			cap(cap),
			rev(rev)
			{}
	};
	const int V;
	static constexpr T INF = numeric_limits<T>::max();
	// G[from][num] := fromから出るnum番目の辺
	vector<vector<Edge>> G;
	Dinic(const int V) :
		V(V),
		G(vector<vector<Edge>>(V, vector<Edge>()))
		{}
	void addEdge(const int from, const int to, const int cap) {
		G[from].emplace_back(to, cap, (int)G[to].size());
		G[to].emplace_back(from, 0, (int)G[from].size() - 1);
	}
	T flow(const int start, const int goal) {
		T ans = 0;
		vector<int> level(V);
		while(bfs(start, goal, level)) {
			vector<int> checked(V);
			while(1) {
				T fmax = dfs(start, goal, level, checked, INF);
				if(fmax <= 0) break;
				ans += fmax;
			}
		}
		return ans;
	}
	bool bfs(const int start, const int goal, vector<int> &level) {
		for(int i = 0; i < V; ++i) level[i] = -1;
		queue<int> que;
		level[start] = 0;
		que.push(start);
		while(que.size() and level[goal] == -1) {
			int from = que.front();
			que.pop();
			for(Edge e : G[from]) {
				if(e.cap > 0 and level[e.to] == -1) {
					level[e.to] = level[from] + 1;
					que.push(e.to);
				}
			}
		}
		return level[goal] != -1;
	}
	T dfs(const int from, const int goal, const vector<int> &level, vector<int> &checked, T fmax) {
		if(from == goal) return fmax;
		for(int &id = checked[from]; id < (int)G[from].size(); ++id) {
			Edge &e = G[from][id];
			if(level[e.to] <= level[from]) continue;
			if(e.cap <= 0) continue;
			T f = dfs(e.to, goal, level, checked, min(e.cap, fmax));
			if(f <= 0) continue;
			e.cap -= f;
			G[e.to][e.rev].cap += f;
			return f;
		}
		return 0;
	}
};

int main() {
	cin >> h >> w;
	Dinic<int> dinic(h + w + 2);
	int s = 0, t = 1;
	for(int i = 0; i < h; ++i) {
		for(int j = 0; j < w; ++j) {
			cin >> a[i][j];
			if(a[i][j] == 'S') {
				dinic.addEdge(s, i + 2, dinic.INF);
				dinic.addEdge(s, h + j + 2, dinic.INF);
				a[i][j] = 'o';
			}
			if(a[i][j] == 'T') {
				dinic.addEdge(i + 2, t, dinic.INF);
				dinic.addEdge(h + j + 2, t, dinic.INF);
				a[i][j] = 'o';
			}
		}
	}
	for(int i = 0; i < h; ++i) {
		for(int j = 0; j < w; ++j) {
			if(a[i][j] != 'o') continue;
			dinic.addEdge(i + 2, h + j + 2, 1);
			dinic.addEdge(h + j + 2, i + 2, 1);
		}
	}
	int ans = max(-1, dinic.flow(s, t));
	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 4276
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <numeric>
#include <functional>
#include <array>
#include <map>
#include <set>

#define INF 1000000007 //1000000000000000003
#define MOD 1000000007
#define MAX 2000005

#define ll long long

//printf("%.10f", );
//cout << fixed << setprecision(10) << heikin << endl;
//vector<vector<int>> data(3, vector<int>(4, -1));
//left + 1 < top

using namespace std;
using P = pair<int, int>;
using Pc = pair<double, int>;
using T = tuple<int, int, int>;
using edge = struct { int to; long long dist; };
const double PI = 3.141592653589793;
long long fact[MAX], inv[MAX];
int dx[] = { -1,0,1,0 };
int dy[] = { 0,-1,0,1 };

//////////////////////////////////

vector<vector<int>> bingo(3, vector<int>(3));
vector<vector<int>> tree(100005);
int color[100005];
map<P, int>colorMap;
int m = 0;

struct BridgeInfo {
	int town1;
	int town2;
	int year;
	BridgeInfo(int t1, int t2, int y) {
		town1 = t1;
		town2 = t2;
		year = y;
	}
};

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

struct UnionFind {
	vector<int>uf;

	UnionFind(int size) :uf(size, -1) {};

	int root(int target) {
		if (uf[target] < 0)return target;
		else return uf[target] = root(uf[target]);
	}

	void merge(int a, int b) {
		a = root(a);
		b = root(b);
		if (a == b)return;
		if (uf[b] < uf[a])swap(a, b);
		uf[a] += uf[b];
		uf[b] = a;
	}
};

ll CalcPow(ll num, ll power) {
	if (power == 0)return 1;
	if (power % 2 == 0) {
		ll half = CalcPow(num, power / 2);
		return (half * half) % MOD;
	}
	else return (num * CalcPow(num, power - 1)) % MOD;
}

ll combination(ll all, ll select) {
	if (all < select) return 0;
	if (all < 0 || select < 0) return 0;
	return fact[all] * (inv[select] * inv[all - select] % MOD) % MOD;
}

void initCombination(int max) {
	fact[0] = fact[1] = 1;
	for (int i = 2; i <= max; ++i) {
		fact[i] = fact[i - 1] * i % MOD;
	}

	inv[max] = CalcPow(fact[max], MOD - 2);
	for (int i = max - 1; 0 <= i; --i) {
		inv[i] = (inv[i + 1] * (i + 1)) % MOD;
	}
}

ll getGcd(ll a, ll b) {
	if (a < b) {
		ll temp = b;
		b = a;
		a = temp;
	}

	ll r;
	while ((r = a % b) != 0) {
		a = b;
		b = r;
	}
	return b;
}

/*int getNum(ll target) {

	int bottom = 0;
	int top = 151;
	while (1 < top - bottom) {
		int middle = (top + bottom) / 2;
		if (target < line[middle])top = middle;
		else bottom = middle;
	}
	return bottom;
}*/

int main() {

	double A, B, H, M; cin >> A >> B >> H >> M;
	double zishin = 0.5;
	double hunshin = 6.0;

	double kakudo = abs((zishin * (H * 60 + M)) - hunshin * M);
	kakudo = min(360 - kakudo, kakudo);
	double radian = kakudo * PI / 180.0;
	double ans2 = A * A + B * B - 2 * A * B * cos(radian);
	double ans = sqrt(ans2);

	cout << fixed << setprecision(15) << ans << endl;
}




Measured memory_bytes: 5468
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0; i<(n); i++)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int main(){
    ll n,k; cin>>n>>k;
    if(k==0){
        cout<<n*n<<endl;
        return 0;
    }
    ll res=0;
    for(ll b=1; b<=n; b++){
        if(b<=k) continue;
        res+=(b-k)*(n/b);
        res+=max(0ll, n%b-k+1);
    }
    cout<<res<<endl;
    return 0;
}

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

template<class INT>
std::vector<INT> factorize(INT n){
    std::vector<INT> res;
    for (INT i = 1; i * i <= n; i++){
        if (n % i == 0){
            res.push_back(i);
            if (i * i != n)
                res.push_back(n / i);
        }
    }
    return res;
}

int main(){
    int n, k;
    cin >> n >> k;
    vector<int64_t> A(n);
    copy_n(istream_iterator<int64_t>(cin), n, A.begin());
    auto factors = factorize(accumulate(A.begin(), A.end(), 0L));

    int64_t ans = 0;
    for (const auto &f: factors){
        vector<int64_t> B(n);
        for (int i = 0; i < n; i++)
            B[i] = A[i] % f;
        auto S = accumulate(B.begin(), B.end(), 0L);
        auto i = S / f;
        nth_element(B.begin(), B.begin() + (n - i), B.end());
        if (max(accumulate(B.begin(), B.begin() + (n - i), 0L), i * f - accumulate(B.begin()+ (n - i), B.end(), 0L)) <= k)
            ans = max(ans, f);
    }

    cout << ans << endl;

}

Measured memory_bytes: 256
#include <iostream>

int main(void){
    using namespace std;
    long N, A, B;
    cin >> N >> A >> B;

    if((B-A)%2==0){
        cout << (B - A) / 2 << endl;
        return 0;
    }

    if(A-1<N-B){
        cout << (B + A - 1) / 2 << endl;
        return 0;
    }

    cout << (2 * N - B - A + 1) / 2 << endl;
    return 0;
}

Measured memory_bytes: 256
sx,sy,dx,dy=map(int,raw_input().split())
x=dx-sx
y=dy-sy
s=""
for i in xrange(x):
	s+="R"
for i in xrange(y):
	s+="U"
for i in xrange(x):
	s+="L"
for i in xrange(y):
	s+="D"
s+="D"
for i in xrange(x+1):
	s+="R"
for i in xrange(y+1):
	s+="U"
s+="L"
s+="U"
for i in xrange(x+1):
	s+="L"
for i in xrange(y+1):
	s+="D"
s+="R"
print s

Measured memory_bytes: 2692
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(n) begin(n),end(n)
using ll = long long;
using P = pair<int,int>;

int main() {
    ll n, p;
    cin >> n >> p;
    ll ans = 1;
    for(ll i = 2; i*i <= p; ++i) {
        if(p%i==0){
            ll cnt = 0;
            while(p%i==0){
                p/=i;
                cnt++;
            }
            ll t = cnt/n;
            rep(j,t) ans*=i;
        }   
    }
    if(n==1) ans = ans*p;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3552
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>
#include<tuple>

using namespace std;
using ll = long long;
using ldb = long double;

int main() {
	int N, M; cin >> N >> M;
	vector<int> cnt(M), pac(M);
	map<int, int> mp;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		cnt[x % M]++;
		mp[x]++;
	}

	for (auto p : mp) {
		pac[p.first % M] += p.second / 2;
	}


	ll ans = 0;
	for (int i = 0; i <= M / 2; i++) {
		if (i == 0) ans += cnt[0] / 2;
		else if (i < M / 2) {
			int low = 0, up = 0;
			if (cnt[i] < cnt[M - i]) low = i, up = M - i;
			else low = M - i, up = i;
			ans += cnt[low];
			ans += min((cnt[up] - cnt[low]) / 2, pac[up]);
		}
		else if (i == M / 2) {
			if (M % 2 == 0)ans += cnt[i] / 2;
			else {
				int low = 0, up = 0;
				if (cnt[i] < cnt[M - i]) low = i, up = M - i;
				else low = M - i, up = i;
				ans += cnt[low];
				//cout << "low=" << low << " up=" << up << endl;
				//cout << "i=" << i << " ans=" << ans << endl;
				ans += min((cnt[up] - cnt[low]) / 2, pac[up]);
				//cout << "i=" << i << " ans=" << ans << endl;
			}
		}
		//cout <<"i="<<i<< " ans=" << ans << endl;
	}

	cout << ans << endl;
}


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

using namespace std;

int main(){

	int a,b,c;

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

	if( a <= c && (a + b >= c ) )
	{
		cout << "YES" << "\n";
	}
	else
	{
		cout << "NO" << "\n";
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin>>n;
    vector<ll>v(n);
    for(ll i=0;i<n;i++)
        cin>>v[i];
    sort(v.begin(),v.end());
    long double ans=(long double)(v[0]+v[1])/2;
    for(ll i=2;i<n;i++)
    {
        ans=(ans+v[i])/2;
    }
    cout<<ans;
	return 0;
}


Measured memory_bytes: 256
m,d=map(int,input().split())
l=list(range(1,m+1))
ans=0
for i in range(1,d+1):
    d_1=i%10
    d_10=(i-d_1)//10
    if d_1*d_10  in l and d_1!=1 and d_10!=1:
        ans+=1
print(ans)

Measured memory_bytes: 9124
#include <stdio.h>

int main(void){
    int num,count,sum,sign;
    while(1){
        sum=0;
        sign=0;
        scanf("%d",&num);
        if(num == 0)
            break;
        while(num){
            scanf("%d",&count);
            if(count >= 2)
                sign=1;
            if(count >= 1)
                sum++;
            num--;
        }
        if(sign == 0)
            printf("NA\n");
        else
            printf("%d\n",sum+1);
    }
    return 0;
}

Measured memory_bytes: 612
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] input = reader.readLine().split(" ");

        final int first = Integer.valueOf(input[0]);
        final int second = Integer.valueOf(input[2]);

        if ("+".equals(input[1])) {
            System.out.println(first+second);
        } else {
            System.out.println(first-second);
        }
    }
}

Measured memory_bytes: 20692
#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;
const int MOD = 1000000007;
const int INF = 1010000000;
const double EPS = 1e-10;
using namespace std;
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 


signed main() {
  int n,m,c;cin>>n>>m>>c;
  int b[50];rep(i,m)cin>>b[i];
  int ans = 0;
  rep(i,n){
    int a = 0;
    rep(i,m){
      int x;cin>>x;
      a += x * b[i];
    }
    if(a > -c)ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>
#include <random>
#include <cstring>


#define rep(i,n) for(int i=0;i<int(n);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back

using namespace std;
using ll = long long;

const ll mod = 1000000007;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

/*---------------------------------------------------*/

int main(){
  int A, B;
  cin >> A >> B;
  cout << (B % A ? B - A : A + B) << endl;
  return 0;
}

Measured memory_bytes: 256
// ABC047 A - キャンディーと2人の子供
#include <stdio.h>

int main(void) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    
    int ab = a + b;
    int ac = a + c;
    int bc = b + c;

    if (a == bc || b == ac || c == ab) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <numeric>
#include <complex>
#define ll long long
using namespace std;

int main() {
	int a, b, c, d, ab, bc, ac;
	cin >> a >> b >> c >> d;
	ab = abs(a - b);
	bc = abs(b - c);
	ac = abs(a - c);
	if (ac <= d || (ab <= d && bc <= d))cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


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

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

    string cp = s;
    int ans = 0;
    int tmp = 0;

    // 偶数番目 0 奇数番目 1
    rep (i, s.size()) {
        if (i % 2 == 0) if (s[i] != '0') tmp++;
        if (i % 2 == 1) if (s[i] != '1') tmp++;
    }

    ans = tmp;

    tmp = 0;
    rep (i, s.size()) {
        if (i % 2 == 1) if (s[i] != '0') tmp++;
        if (i % 2 == 0) if (s[i] != '1') tmp++;
    }
    cout << min(ans, tmp) << endl;

    return 0;
}

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

using namespace std;

#define int long long
#define all(v) (v).begin(), (v).end()
#define resz(v, ...) (v).clear(), (v).resize(__VA_ARGS__)
#define reps(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep(i, n) reps(i, 0, n)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using Pi = pair<int, int>;
using Tapris = tuple<int, int, int>;
using vint = vector<int>;
#define MAX_N 202020

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

long long C[1010][1010];

void make_C(){
  memset(C, 0, (int)sizeof(C));
  for(int i = 0; i < 1010; i++){
    C[i][0] = C[i][i] = 1;
    for(int j = 1; j < i; j++) C[i][j] = (C[i-1][j-1] + C[i-1][j]);
  }
}


signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N, A, B;
  cin >> N >> A >> B;
  vint v(N);
  rep(i, N) cin >> v[i];
  sort(all(v));
  reverse(all(v));
  int sum = 0;
  rep(i, A) sum += v[i];
  cout << (double)sum/A << endl;
  int mx = v[0];
  int cnt = 0;
  int cnt2 = 0;
  rep(i, N) cnt += (mx == v[i]);
  rep(i, A) cnt2 += (mx == v[i]);
  make_C();
  if(cnt2 == A) {
    int ans = 0;
    reps(i, A, B+1) {
      ans += C[cnt][i];
    }
    cout << ans << endl;
  } else {
    int mn = v[A-1];
    int cnt3 = 0;
    int cnt4 = 0;
    rep(i, N) cnt3 += (mn == v[i]);
    rep(i, A) cnt4 += (mn == v[i]);
    cout << C[cnt3][cnt4] << endl;
  }

  return 0;
}


Measured memory_bytes: 8192
#include<iostream>
#include<string>

using namespace std;

int main(){
	int n;
	cin>>n;
	string str;
	cin>>str;
	int ans=0;
	for(int co=0;co<n;co++){
		string s;
		cin>>s;
		int now=0;
		for(int i=0;i<s.size();i++){
			if(s[i]==str[0]){
				for(int j=i+1;j<s.size();j++){
					if(s[j]==str[1]){
						int no=2;
						for(int k=j+(j-i);k<s.size();k+=(j-i),no++){
							if(s[k]!=str[no])goto fail;
							if(no>=str.size()-1){
								ans++;
								goto suc;
							}
						}
						//ans++;
						//goto suc;
					}
					fail:;
				}
				
			}
			
		}
		suc:;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 1208
import java.util.Scanner;

public class Main {

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		// 整数の入力
		int n = sc.nextInt();
		
		int num = 0;
		int keta = 0;
		
		int n2 = n;
		
		while(n2 > 0) {
			keta++;
			n2 /= 10;
		}
		
		int keta2 = keta;
		
		while(keta > 0) {
			if(keta % 2 == 1) {
				if(keta2 == keta) {
					num = n + 1 - (int)Math.pow(10, keta-1);
				} else {
					num += (int)Math.pow(10, keta-1)*9;
				}
			}
			keta--;
		}
		
		System.out.println(num);
		
        sc.close();
	}
}

Measured memory_bytes: 23380
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
#include<math.h>
#include<bitset>
#include<iomanip>
using namespace std;

typedef stack<int> IntStack;
typedef queue<int> IntQueue;

const double pi = 3.141592653589793;

/*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*/



int main()
{	
	int H, W;

	for (int i = 0;i < 10000;i++)
	{
		cin >> H >> W;
		if (H == 0 && W == 0) break;

		for (int j = 0; j < H; j++)
		{
			for (int k = 0; k < W; k++)
			{
				cout << "#";
			}
			cout << "\n";
		}
		cout << "\n";
	}

	return 0;
}



Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main(void)
{
    int r, D, x2000;
    cin >> r >> D >> x2000;
    long long ans = 0, b = x2000;
    for (int i = 2001; i <= 2010; i++)
    {
        long long c = 0;
        c = r * b - D;
        cout << c << endl;
        b = c;
    }
    return 0;
}

Measured memory_bytes: 256
num=list(map(int,input().split(" ")))
A=[list(map(int,input().split(" ")))for i in range(num[0])]
B=[list(map(int,input().split(" ")))for i in range(num[1])]
C=[[0]*num[2] for i in range(num[0])]

for i in range(num[0]):
    for j in range(num[2]):
        for k in range(num[1]):
            C[i][j]+=A[i][k]*B[k][j]
for i in C:
    print(" ".join(map(str,i)))


Measured memory_bytes: 6896
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_range(i, s, e) for (int i = (s); i < (int)(e); i++)
#define rep_rev(i, s, e) for (int i = (s)-1; i >= (int)(e); i--)
#define sort_vec(v) sort((v).begin(),(v).end())
typedef int64_t lint;
// lint mod = 998244353;
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); }

bool app() {
  string s,t;
  cin>>s>>t;

  rep(i,s.length()){
    if(s[i]!=t[i]) return false;
  }
  return true;
}

int main(){cout<<(app()?"Yes":"No")<<endl;return 0;}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fi first
#define sc second
#define ALL(x) x.begin(), x.end()
#define RALL(X) x.begin(), x.end()
#define FOR(i, n, k) for(i=0; i<n; i+=k)
#define FO(i, n, k) for(i=1; i<=n; i+=k)
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define N 100005
#define mid ((l+r)/2)
#define dbg(x) (cerr << #x << " : " << x << endl)
#define endl "\n"

using namespace std;

typedef long long int lli;

int const NMAX = 1e5+5;
lli const MOD = 1e9+7;
vector <vector <int>> adj(NMAX, vector <int>());
lli n, k;
lli res;

void dfs(int i, int par, int cho){
	res = res * cho % MOD; 
	cho = k-1;
	if(par != -1) cho--;
	for(int chi: adj[i]){
		if(chi == par) continue;
		dfs(chi, i, cho--);
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	res = 1;
	cin >> n >> k;
	for(int i=0; i<n-1; i++){
		int a, b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}

	dfs(1, -1, k);
	cout << res % MOD;
	return 0;
}

Measured memory_bytes: 9216
#include<stdio.h>
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <iterator>
#include <list>
#include <map>     
#include <numeric>
#include <utility>
#include <queue>
#include <set>
#include <sstream>
#include <iomanip>
#include <stack>
#include <string>
#include <limits>
#include <vector>
using namespace std;
#define ll long long
#define ld long double
#define rep(a,t) for(int a=0;a<t;++a) 
#define forever while(true)
#define Sort(a) sort(a.begin(),a.end())
#define Reverse(a) reverse(a.begin(),a.end())
#define pb push_back
#define print_double(val,a) cout << fixed << setprecision(a) << val << endl;
ll mod = 1e9 + 7;
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<int>a(n);
	int firstx = -1;
	rep(i, n) {
		cin >> a[i];
		if (firstx < 0 && a[i] >= 0) { firstx = i; }
	}
	if (firstx == -1) { firstx = n; }
	if (a[0] >= 0) {
		cout << a[m - 1] << endl; return 0;
	}
	if (a[n - 1] < 0) {
		Reverse(a);
		cout << 0 - a[m - 1] << endl; return 0;
	}
	int mint = 2147483647;
	rep(i, n) {
		int left = m-abs(firstx-i);
		int nowittook = abs(a[i]);
		if (left < 0) { continue; }
		if (left == 0) { mint = min(mint, abs(a[i])); }
	
		int hidari = i - left;
		int migi = i + left;
		if(firstx-i<0){hidari=i-m+1;}
		 else {migi=i+m-1;}
		//cout<<i<<" ";
		if (hidari >= 0) { mint = min(mint,nowittook+abs(a[i]-a[hidari])); }
		if (migi <= n - 1) { mint = min(mint, nowittook + abs(a[i]-a[migi])); }
	}
	cout << mint << endl;
	return 0;
}


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

inline void IOS() { ios::sync_with_stdio(false), cin.tie(0); }

template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
	fill((T *)array, (T *)(array + N), val);
}

const ll INF = 1e16;
const ll MOD = 1e9 + 7;
//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//ll pas[5001][5002];



signed main(){
	IOS();
	ll n, r;
	while(1){
		cin >> n >> r;
		if(n == 0 && r == 0)break;
		vector<ll> a(n + 1), a2(n + 1);
		for (int i = 0;i <= n;++i) {
			a[i] = a2[i] = n - i + 1;
		}
		for (int i = 0;i < r;++i) {
			a = a2;
			ll p, c;
			cin >> p >> c;
			for (int i = 0;i < c;++i) {
				a2[i + 1] = a[p + i];
			}
			for (int i = 1;i < p;++i) {
				a2[i + c] = a[i];
			}
		}
		cout << a2[1] << endl;
	}

	return 0;
}


Measured memory_bytes: 3096