akhauriyash/Code-Regression huggingface dataset:
package main

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

var (
	uft  []int
	rank []int
	ch   []int
	ans  []int64
)

func find(x int) int {
	if uft[x] == x {
		return x
	}

	uft[x] = find(uft[x])
	return uft[x]
}

func union(a, b, i int) {
	ans[i-1] = ans[i]
	ar, br := find(a), find(b)
	if ar == br {
		return
	}

	ans[i-1] -= int64(ch[ar] * ch[br])

	if rank[ar] < rank[br] {
		uft[ar] = uft[br]
		ch[br] += ch[ar]
		return
	} else if rank[ar] == rank[br] {
		rank[br]++
	}
	uft[br] = uft[ar]
	ch[ar] += ch[br]
}

func main() {
	var n, m int
	fmt.Scan(&n, &m)

	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	as := make([]int, m)
	bs := make([]int, m)
	for i := 0; i < m; i++ {
		sc.Scan()
		as[i], _ = strconv.Atoi(sc.Text())
		sc.Scan()
		bs[i], _ = strconv.Atoi(sc.Text())
	}

	uft = make([]int, n+1)
	rank = make([]int, n+1)
	ch = make([]int, n+1)
	for i := range uft {
		uft[i] = i
		ch[i] = 1
	}

	ans = make([]int64, m)
	ans[m-1] = int64(n * (n - 1) / 2)
	for i := m - 1; i >= 1; i-- {
		union(as[i], bs[i], i)
	}

	for _, v := range ans {
		fmt.Println(v)
	}
}


Measured memory_bytes: 7808
#include<bits/stdc++.h>
using namespace std;
#define l long
#define d double
int main(){
	l l a, b, c; cin>>a>>b>>c;
	l l ans=(l l)floor((l d)a*(l d)min(b-1, c)/(l d)b)-a*(l l)floor((l d)min(b-1, c)/(l d)b);
	cout<<ans<<endl; return 0;
}

Measured memory_bytes: 3676
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int a[100005];
long power(long n, long N, long m){
    if(N==0) return 1;
    if(N%2==0) return power(n*n%m,N/2,m);
    else return n*power(n,N-1,m)%m;
}
int main(void){
    int n;cin>>n;
    long ans=0;
    for(int i=0;i<n;i++){
        int x;cin>>x;
        a[x]++;
    }
    
    bool check=0;
    if(n%2==1){
        int i=0;
        while(i<n){
            if(i==0){
                if(a[i]!=1)check++;
            }else{
                if(a[i]!=2)check++;
            }
            i+=2;
        }
    }else{
        int i=1;
        while(i<(n+2)/2){
            if(a[i]!=2)check=1;
            i+=2;
        }
    }
    if(check){
        cout<<0<<endl;
    }else{
        int b=n/2;
        cout<<power(2,b,1000000007)<<endl;
    }
    
    return 0;
}


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

int main(){
    int N, M, X;
    cin >> N >> M >> X;
    int C[N];
    int A[N][M];
    int i,j;
    for(i=0; i<N; i++){
        cin >> C[i];
        for(j=0; j<M; j++){
            cin >> A[i][j];
        }
    }
    int ans = 100000000;
    int bit;
    int asum[M];
    int cost;
    bool koeru;
    for(bit=0; bit<(1<<N); bit++){
        cost = 0;
        koeru = 1;
        for(j=0; j<M; j++){
            asum[j]=0;
        }
        for(i=0; i<N; i++){
            if((bit>>i)%2==0) continue;
            cost += C[i];
            for(j=0; j<M; j++){
                asum[j]+=A[i][j];
            }
        }


        for(j=0; j<M; j++){
            if(asum[j]<X) koeru=0;
        }
        
        if(koeru==1){
            ans = min(cost,ans);
        }
    }
    if(ans<100000000){
        cout << ans << endl;
    }else{
        cout << -1 << endl;
    }
    system("pause");
    return 0;
}

Measured memory_bytes: 3696
N,M=map(int,input().split())
A=list(map(int,input().split()))
S=[0]*(N+1)
for i in range(N):
    S[i+1]=S[i]+A[i]
num={}
for i in range(N+1):
    if S[i]%M in num:
        num[S[i]%M]+=1
    else:
        num[S[i]%M]=1
ans=0
for i in num.values():
    ans+=i*(i-1)//2
#print(num)
print(ans)


Measured memory_bytes: 17228
with Ada.Text_IO, Ada.Integer_Text_IO, Ada.Float_Text_IO;
 use Ada.Text_IO, Ada.Integer_Text_IO, Ada.Float_Text_IO;

procedure main is
   type Week is array(1..7) of String(1..3);
   S: String(1..3);
   W: Week;
begin
   W(1) := "SUN";
   W(2) := "MON";
   W(3) := "TUE";
   W(4) := "WED";
   W(5) := "THU";
   W(6) := "FRI";
   W(7) := "SAT";
   S := get_line;
   for i in 1..7 loop
      if (W(i) = S) then put(7 - i + 1, 0);
      end if;
   end loop;
end main;

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

int main(void) {
  int N;
  cin >> N;
  vector<double> v(N);
  for (int i = 0; i < N; i++) {
    cin >> v[i];
  }
  sort(v.begin(), v.end());

  for (int i = 0; i < N - 1; i++) {
    v[i + 1] = (v[i] + v[i + 1]) / 2;
  }

  cout << fixed << setprecision(5) << v[N - 1] << endl;
  return 0;
}

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

lint gcd(lint x, lint y) {
  if(x == 0) { return y; }
  else { return gcd(y%x,x); }
}

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

lint C(lint n, lint k) {
  if(n == k) { return 1; }
  else if(n < k) { return 0; }
  else if(k == 0) { return 1; }
  else if(k == 1) { return n; }
  else return C(n-1,k-1) + C(n-1,k);
}

lint P(lint n, lint k) {
  if(k == 1) { return n; }
  return (n*(P(n-1,k-1)%1000000007)%1000000007);
}


int main() {
  int l,r,d; cin >> l >> r >> d;

  int cnt=0;
  for(int i=l;i<=r;i++) {
    if(i%d == 0) { cnt++; }
  }

  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 3588
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define rep(i,l,r) for(int i=(l);i<(r);i++)
#define fcout cout << fixed << setprecision(10)
int main(){
    int n;
    cin >> n;
    int digsum = 0, a = n;
    while(a != 0){ // 各桁の和の計算
        digsum += a % 10; // 1の位を足して
        a /= 10;  //10で割る
    }
    if(n % digsum == 0) cout << "Yes";
    else cout << "No";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
	int n, d, x, a[100];
	cin >> n >> d >> x;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0;; j++) {
			if (a[i]*j + 1 > d)goto age;
			cnt++;
		}
	age:;
	}
	cout << x + cnt << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define mod 1000000007
#define ll long long
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define ff first
#define ss second
#define prec(y,x) fixed<<setprecision(y)<<x
#define inf 1e18
#define pi 3.1415926535
vector<int> col, v;
vector<vector<int>> colrow;
int k, s;
int update(int x)
{
	while (x)
	{
		if (2 * x + 1 < k)
			v[x] = max(v[2 * x], v[2 * x + 1]);
		x /= 2;
	}
	return 0;
}
int count(int x, int lx, int rx, int l, int r)
{
	if (lx > r || rx < l)
	{
		return 0;
	}
	else if (lx >= l && lx <= r && rx >= l && rx <= r)
	{
		return v[x];
	}
	else
	{
		if (2 * x + 1 < k)
		{
			int mid = l + r; mid /= 2;
			int ans = max(count(2 * x, lx, mid, l, r), count(2 * x + 1, mid + 1, rx, l, r));
			return ans;
		}
		else
			return 0;
	}
}
int query(int l, int r)
{
	return count(1, 1, s + 1, l, r);
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int h, w, m;
	cin >> h >> w >> m;
	colrow.resize(w + 1); col.resize(w + 1, 0);
	k = 0;
	for (; k < 30; k++)
	{
		if ((1 << k) >= h)
			break;
	}
	s = 1 << k; s--;
	k++; k = 1 << k;
	v.resize(k + 1, 0);
	while (m--)
	{
		int a, b;
		cin >> a >> b; col[b]++;
		v[s + a]++;
		colrow[b].pb(a);
		update(s + a);
	}
	int ans = 0;
	for (int i = 1; i <= w; i++)
	{
		for (int j = 0; j < colrow[i].size(); j++)
		{
			int a = colrow[i][j];
			v[s + a]--;
			update(s + a);
		}
		int ans1 = query(1, s + 1); ans1 += col[i];
		ans = max(ans, ans1);
		for (int j = 0; j < colrow[i].size(); j++)
		{
			int a = colrow[i][j];
			v[s + a]++;
			update(s + a);
		}


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



Measured memory_bytes: 24784
import sys
from bisect import bisect_left, bisect_right

n = int(sys.stdin.buffer.readline().rstrip())
q = list(map(int, sys.stdin.buffer.readline().split()))
s = int(sys.stdin.buffer.readline().rstrip())
t = list(map(int, sys.stdin.buffer.readline().split()))

ans = 0
for i in t:
    if q[bisect_left(q, i, 0, n-1)] == i:
        ans += 1
print(ans)


Measured memory_bytes: 14132
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>

const int MAX_N = 1e2 + 10 ;

int len1 , len2 ;
char s1[MAX_N] , s2[MAX_N] ;

bool cmp1(char a , char b) {return a < b ;}
bool cmp2(char a , char b) {return a > b ;}

int main() {
	scanf("%s %s" , s1 , s2) ;
	len1 = strlen(s1) ; len2 = strlen(s2) ;

	///

	std::sort(s1 + 0 , s1 + len1 , cmp1) ;
	std::sort(s2 + 0 , s2 + len2 , cmp2) ;

	int p = 0 , L = std::min(len1 , len2) ;
	for (; p < L && s1[p] == s2[p] ; ++p) ;

	if (p == L) {
		if (len1 >= len2) printf("No\n") ;
		else printf("Yes\n") ;
	}
	else {
		if (s1[p] > s2[p]) printf("No\n") ;
		else printf("Yes\n") ;
	}

	return 0 ;
}

Measured memory_bytes: 128
n = int(input())
A = []
for i in range(1, int(n ** .5 + 3) * 2):
    A.append(i * (i - 1) // 2)

if n in A:
    print("Yes")
    x = A.index(n) + 1
    ans = [[] for _ in range(x)]
    now = 1
    l = 0
    while l < x:
        for i in range(x - l - 1):
            ans[l].append(now)
            ans[l + 1 + i].append(now)
            now += 1
        l += 1
    print(x)
    for i in range(x):
        print(x - 1, *ans[i])
        
else:
    print("No")


Measured memory_bytes: 14280
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <iterator>
#include <stack>
#include <string.h>
#include <cstdlib>
#include <queue>
#include <list>
#include <string>

using namespace std;

int main()
{
    int n;
    cin >> n;
    if (n%10 == 3){
        cout << "bon" << endl;
    }
    else if (n%10 == 0 || n%10 == 6 || n%10 == 1 || n%10 == 8){
        cout << "pon" << endl;
    }
    else {
        cout << "hon" << endl;
    }
}


Measured memory_bytes: 3596
# -*- coding: utf-8 -*-
from fractions import gcd

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))

    L = [0]
    R = [0]

    for i in range(N):
        L.append(gcd(L[-1], A[i]))
    for i in range(N-1, -1, -1):
        R.append(gcd(R[-1], A[i]))

    ans = 0

    for i in range(N):
        ans = max(ans, gcd(L[i], R[N - i - 1]))

    print(ans)


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

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

int main() {
  cin.tie(0);
  cout << fixed << setprecision(10);

  int n; cin >> n;
  vi a(n);
  map<int, ll> mp;
  for(int i=0;i<n;++i) {
    cin >> a[i];
    mp[a[i]]++;
  }

  ll tmp = 0;
  for(auto &e: mp) {
    tmp += e.second * (e.second-1) / 2;
  }

  for(int i=0;i<n;++i) {
    int now = mp[a[i]];
    cout << tmp - now * (now-1)/2 + (now-1) * (now-2) / 2 << endl;
  }

  
}


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

int main() {
  int a,b;
  cin >> a >> b;
  
  if(a>=13){
    cout << b << endl;
  }
  
  else if(a <= 5){
    cout << "0" << endl;
  }
  
  else{
    cout << b/2 << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define y1 zzz
#define fi first
#define se second
#define PII pair<int,int>
#define PII2 pair<int,PII >
#define PII3 pair<PII,int >
#define PII4 pair<PII,PII >
#define all(x) (x).begin(),(x).end()
#define pb push_back
int x,y,a,b,c,arr1[200010],arr2[200010],sum,val;
multiset<int> ms;
void solve()
{
    cin>>x>>y>>a>>b>>c;
    for(int i=1;i<=a;i++)cin>>arr1[i];
    for(int i=1;i<=b;i++)cin>>arr2[i];
    sort(arr1+1,arr1+1+a,greater<int>());
    sort(arr2+1,arr2+1+b,greater<int>());
    for(int i=1;i<=x;i++)
    {
        ms.insert(arr1[i]);
        sum+=arr1[i];
    }
    for(int i=1;i<=y;i++)
    {
        ms.insert(arr2[i]);
        sum+=arr2[i];
    }
    for(int i=1;i<=c;i++)
    {
        cin>>val;
        auto it=ms.begin();
        if(*it<val)
        {
            sum+=val-(*it);
            ms.erase(ms.begin());
            ms.insert(val);
        }
    }
    cout<<sum;
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //freopen("STRWC.inp","r",stdin);
    //freopen("FORMMAU.out","w",stdout);
    //int t;cin>>t;while(t--)
    solve();
    return 0;
}


Measured memory_bytes: 10240
#include "bits/stdc++.h"

using namespace std;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	set<int> a;

	for (int i = 0; i < 3; i++) {
		int t;
		cin >> t;
		a.insert(t);
	}

	int l = -1,ans = 0;
	for (auto x:a) {
		if (x != l)
			ans++;
		l = x;
	}

	cout << ans << endl;

	return 0;

}

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

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

  ll N; cin >> N;
  vector<ll> A(N); for (ll i = 0; i < N; i++) cin >> A[i];

  for (ll i = 0; i < N; i++) {
    ll temp = A[i];
    ll j = i - 1;
    while (j >= 0 && A[j] > temp) {
      A[j + 1] = A[j];
      j--;
    }
    A[j + 1] = temp;
    cout << A[0]; for (int i = 1; i < A.size(); i++) { cout << ' ' << A[i]; }
    cout << '\n';
  }
  return 0;
}


Measured memory_bytes: 3136
#include<stdio.h>
#include<string.h>
 
 
 
int main(){
  int N,L;
  scanf("%d%d",&N,&L);
  int i,j;
  char s[N][L+1];
  char tmp[L+1];
  char str[10001];
  for(i=0;i<N;i++){
    scanf("%s",s[i]);
  }
  //printf("%s\n",s[0]);
  for(i=1;i<N;i++){
    for(j=1;j<N;j++){
      if(strcmp(s[j-1],s[j])>0){
        strcpy(tmp,s[j-1]);
        strcpy(s[j-1],s[j]);
        strcpy(s[j],tmp);
      }
    }
  }//文字列を辞書中にソート
  for(i=0;i<N;i++){
    strcat(str,s[i]);
  }
  printf("%s",str);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

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

int main(){
  string S;
  cin >> S;
  int len = S.length()-1;
  int sum = 0;
  if(len % 2 == 0){
    for(int i =0;i<=len/2;i++){
      sum += (S[i] != S[len-i]);
    }
  }
  else
  {
    for(int i =0;i<=(len-1)/2;i++){
      sum += (S[i] != S[len-i]);
    }
  }
  cout << sum << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <deque>
using namespace std;
 
int main(){
    int ans = 0;
    int N,M;
    cin >> N >> M ;
    int p[N];
    vector<int> edge[N];
    for(int i=0; i<N; i++){
        cin >> p[i];
        p[i] --;
    }
    for(int i=0;i<M;i++){
        int x,y;
        cin >> x >> y;
        edge[x-1].push_back(y-1);
        edge[y-1].push_back(x-1);
    }
    int A[N] = {};
    for(int i=0;i<N;i++){
        vector<int> queue;
        vector<int> hoge;
        int q;
        if(A[i] == 0){
            queue.push_back(i);
            hoge.push_back(p[i]);
            A[i] = 1;
        }
        int now = 0;
        while(queue.size() > now){
            q = queue.at(now);
            for(int j=0;j<edge[q].size();j++){
                if (A[edge[q][j]] == 0){
                    queue.push_back(edge[q][j]);
                    hoge.push_back(p[edge[q][j]]);
                    A[edge[q][j]] = 1;
                }
            }
            now ++;
        }
        if(hoge.size() > 0){
            sort(hoge.begin(),hoge.end());
            sort(queue.begin(),queue.end());
            int x=0,y=0;
            while(x<hoge.size() && y<queue.size()){
                if (hoge[x] == queue[y]){
                    ans++;
                    x++;
                    y++;
                }else if(hoge[x] > queue[y]){
                    y++;
                }else{
                    x++;
                }
            }
        }
    }

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

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

using S = set<int>;

S* merge(S* a, S* b){
    if(a->size() < b->size()) swap(a, b);
    for(auto x : *b){
        a->insert(x);
    }
    return a;
}

void compress(vector<int> &v){
    auto tmp = v;
    sort(tmp.begin(), tmp.end());
    map<int,int> ord;
    for(int i=0;i<int(tmp.size());i++){
        ord[tmp[i]] = i;
    }
    for(auto& x : v) x = ord[x];
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    compress(a);
    vector<S> sv(n);
    queue<S(*)> que;
    for(int i=0;i<n;i++){
        sv[i].insert(a[i]);
        que.push(&sv[i]);
    }
    long long ans = 0;
    for(int i=0;i<n;i++){
        while(1){
            auto s = que.front();
            que.pop();
            if(s->find(i) != s->end()){
                s->erase(i);
                ans += s->size();
                if(!s->empty()) que.push(s);
                break;
            }else{
                que.front() = merge(que.front(), s);
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 36220
import static java.lang.System.out;
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()) {
            List<Integer> list = new ArrayList<>();
            list.add(scan.nextInt());
            list.add(scan.nextInt());

            if (list.get(0).equals(0) && list.get(1).equals(0)) {      
                break;
            }

            if (list.get(0) > list.get(1)) {
                int tmp = list.get(0);
                list.set(0, list.get(1));
                list.set(1, tmp);
            }

            out.printf("%d %d%n", list.get(0), list.get(1));
        }
    }
}

Measured memory_bytes: 39844
tmp = input().split()
A = int(tmp[0])
B = int(tmp[1])
if B == 1:
    print(0)
    exit()
if 2 <= A and A <= 20:
    if 1 <= B and B <= 20:

        power = 1
        count = 0

        while True:
            count += 1
            power = power - 1 + A
            # print(power)
            if power >= B:
                print(count)
                break



Measured memory_bytes: 3060
#include <stdio.h>

int main()
{
    int a,b,c,d;
    int t,s;
    scanf("%d", &a);
    scanf("%d", &b);
    scanf("%d", &c);
    scanf("%d", &d);
    if(a<b){
        t=a;
    }else{
        t=b;
    }
    if(c<d){
        s=c;
    }else{
        s=d;
    }
    printf("%d\n", s+t);
    return 0;
}


Measured memory_bytes: 128
unittest
{
	assert( [ "117" ].parse.expand.solve == "Yes" );
	assert( [ "123" ].parse.expand.solve == "No" );
	assert( [ "777" ].parse.expand.solve == "Yes" );
}



import std.conv;
import std.range;
import std.stdio;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = input.front.to!( dchar[] );
	return tuple( n );
}

auto solve( dchar[] n )
{
	foreach( c; n )
	{
		if( c == '7' ) return "Yes";
	}
	return "No";
}


Measured memory_bytes: 2784
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

#define REP(i,N) for(int i = 0; i < (int)(N); ++i)
#define ALL(v) (v).begin(), (v).end()
typedef long long Int;
template<class T> void pv(T a, T b){for(T i=a;i!=b;++i)cout<<*i<<" ";cout<<endl;}

double dp[1024 * 1024];
double next[1024 * 1024];

double solve(int N, int M, int K) {
        if( N == 1 ) {
                double res = 0;
                for(int m = 1; m <= M; m++)
                        res += max(1, m - K);
                return res / M;
        }
        
        int L = N * M + 1;
        
        REP(i, L) dp[i] = 0;
        dp[0] = 1.0;
        double p = 1.0 / M;
        REP(step, N) {
                REP(i, L) next[i] = 0;
                REP(i, L) if( dp[i] > 0 ) 
                        for(int m = 1; m <= M; m++)
                                next[i + m] += dp[i] * p;
                REP(i, L) dp[i] = next[i];
        }
        double res = 0;
        REP(i, L) {
                res += max(1, i - K) * dp[i]; 
        }
        return res;
}

int main() {
        int N, M, K;
        for(;;) {
                cin >> N >> M >> K;
                if( N == 0 && M == 0 && K == 0 ) break;
                double res = solve(N, M, K);
                printf("%.8f\n", res);
        }
        return 0;
}

Measured memory_bytes: 0
#include <cstdio>
#define _abs(_a) ((_a)<0?0:(_a))
#define _min(_a,_b) ((_a)<(_b)?(_a):(_b))

int main()
{
	int N,A,B;scanf("%d%d%d",&N,&A,&B);
	printf("%d %d\n",_min(A,B),_abs(A+B-N));
	return 0;
}

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

//配列の辞書順を返す関数。
//第1引数に配列、第2引数に配列の大きさを代入して使う。
//計算量O(N!)なのでN=10くらいが限界。
int getDictionaryOrder(int p[], int n){
    int permutation[n];
    for(int i=0; i<n; i++){
        permutation[i] = i+1;
    }
    sort(permutation, permutation + n);
    int dicOrder = 1;
    do {
        bool isok = true;
        for(int i=0; i<n; i++){
            if(p[i] != permutation[i]){
                isok = false;
                break;
            }
        }
        if(isok){
            break;
        }else{
            dicOrder++;
        }
    } while (next_permutation(permutation, permutation + n));
    return dicOrder;
}

int main(){
    int n;
    cin >> n;
    int p[10], q[10];
    for(int i=0; i<n; i++){
        cin >> p[i];
    }
    for(int i=0; i<n; i++){
        cin >> q[i];
    }

    cout << abs(getDictionaryOrder(p, n) - getDictionaryOrder(q, n)) << endl;
    return 0;
}

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

long long dp[105][100005];
long long weight[100005];
long long value[100001];
long long solve(long long n , long long w){

    if(n == 0 || w==0)
        return 0;
    if(dp[n-1][w] != -1 )
        return dp[n-1][w];
    if(weight[n-1] > w) {
        dp[n - 1][w] = solve(n - 1, w);
        return dp[n - 1][w];
    }
    else{
        dp[n-1][w] = max( solve(n-1, w) , value[n-1] + solve(n-1,w-weight[n-1]) );
        return dp[n-1][w];
    }


}






int main() {


    long long n;
    long long w;
    cin >> n >> w;

    for(int i=0;i<n;i++){
        cin >> weight[i] >> value[i];
    }
//    for(int i =0; i<=n;i++)
//         memset(dp[i] , -1 , 100005);
    for (int i = 0; i <= n; i++)
        for (int j = 0; j < w + 1; j++)
            dp[i][j] = -1;
    cout << solve(n,w);
    return 0;
}


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

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define erep(i, n) for (ll i = 0; i <= (ll)(n); ++i)
#define FOR(i,a,b) for (ll i = (a); i < (ll)(b); ++i)
#define EFOR(i,a,b) for (ll i = (a); i <= (ll)(b); ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } }

const ll sub = 998244353;

int pow_kai(ll a, ll n){//aのn乗を計算します。
    int x = 1;
    while(n > 0){//全てのbitが捨てられるまで。
        if(n&1){//1番右のbitが1のとき。
            x = x*a%sub;
        }
        a = a*a%sub;
        n >>= 1;//bit全体を右に1つシフトして一番右を捨てる。
    }
    return x;
}

int main() {
    int n; cin >> n;
    vector<int> d(n);
    rep(i,n) cin >> d[i];

    if(d[0] != 0) {
        cout << 0 << endl;
        return 0;
    }

    vector<int> level(n,0);
    rep(i, n) {
        level[d[i]]++;
    }

    if(level[0] != 1) {
        cout << 0 << endl;
        return 0;
    }

    ll ans = 1;
    for(int i=1; i<n; i++) {
        if(level[i]!=0) {
            if(level[i-1] == 0) {
                cout << 0 << endl;
                return 0;
            }
            ans = ans*pow_kai(level[i-1], level[i])%sub;
        }
    }

    cout << ans%sub << endl;

    return 0;

}



Measured memory_bytes: 1024
#include <stdio.h>

#define GRAY 0
#define WHITE 1
#define BLACK -1

typedef struct{
  int color;
  int cnt;
  int next[10];
}Node;

int d[101],f[101];
Node dfs[101];

int time;

void visit(int u){

  int i;
  // printf("now %d\n",u);
  dfs[u].color=GRAY;
  d[u]=++time;

  for(i=1;i<=dfs[u].cnt;i++){
    if(dfs[dfs[u].next[i]].color==WHITE)
      visit(dfs[u].next[i]);
  }
  dfs[u].color=BLACK;
  f[u]=++time;
  //printf("%d:(%d,%d)\n",u,d[u],f[u]);

}



int main(){

  int n,m,k,l,i,j;
  
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    dfs[i].color=WHITE;
    scanf("%d%d",&m,&k);
    for(j=1;j<=k;j++){
      scanf("%d",&l);
      dfs[i].next[j]=l;
      dfs[i].cnt=k;
    }
  }
    
  for(i=1;i<=n;i++){
    if(dfs[i].color==WHITE)visit(i);
  }

  for(i=1;i<=n;i++){
    printf("%d %d %d\n",i,d[i],f[i]);
  }
  


  
  return 0;
}



Measured memory_bytes: 2076
x1,y1,x2,y2=list(map(int,input().split()))
cx = x2-x1
cy = y2-y1
vx = -cy
vy = cx
x3 = x1 + vx
y3 = y1 + vy
x4 = x2+vx
y4 = y2+vy
print(x4,y4,x3,y3)

Measured memory_bytes: 3060
//BISMILLAHHIR RAHMANIR RAHIM
#include<bits/stdc++.h>
using namespace std;
typedef long long int            ll;
typedef unsigned long long int   ull;
#define min3(a,b,c)              min(a,min(b,c))
#define F                        first
#define S                        second
#define PB                       push_back
#define MP                       make_pair
#define PI                       2*acos(0.0)
#define MOD                      9982443
int main()
{
    vector<int>v,ch;
   vector<pair<int,int> >mp;
    bool have =false;
    int x,n;
    cin>>x>>n;
    int ara[n];
    for(int i=0; i<n; i++){
        cin>>ara[i];
        if(ara[i]==x)have=true;
    }
    sort(ara,ara+n);
    if(!have)cout<<x<<endl;
    else{
        int j=0;
        for(int i=0; i<=101; i++){
            v.push_back(i);
        }
        int sz=v.size();
        for(int i=0; i<sz; i++){
            if(ara[j]==v[i])j++;
            else ch.push_back(v[i]);
        }
       // for(int i=0; i<ch.size(); i++)cout<<ch[i]<<" ";
        //cout<<endl;
        int l=ch.size();
        for(int i=0; i<l; i++){
          mp.push_back(make_pair(abs(ch[i]-x),ch[i]));
        }
        sort(mp.begin(),mp.end());
        cout<<mp[0].S<<endl;
    }
    return 0;
}


Measured memory_bytes: 3636
N = int(input())
S = [i for i in input()]

r = 0
g = 0
b = 0
no = 0

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

for i in range(N):
    for j in range(i+1, N):
        k = j*2 - i
        if k >= N:
            break
        elif S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            no += 1
 
print(r*g*b - no)

Measured memory_bytes: 9220
def st2(x, y):
    l = int((x * y * 4 - 1) ** 0.5)
    return l - 1 - int(x != y)


def st3(x, y):
    p, q = 1, (max(x, y) + 1) * 2
    while q - p > 1:
        m = (p + q) // 2
        if m * m < x * y * 4:
            p = m
        else:
            q = m
    l = p
    return l - 1 - int(x != y)

def query(x, y):
    print(st3(x, y))


def main():
    n = int(input())
    for _ in range(n):
        x, y = map(int, input().split())
        query(x, y)


if __name__ == '__main__':
    main()

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

int main()
{
	int a[3];
	cin>>a[0]>>a[1]>>a[2];
	int sum=a[0]+a[1]+a[2];
	if (sum>=22)
		cout<<"bust";
	else
		cout<<"win";
	return 0;
}

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

int main () {
  string s; cin >> s;
  string a = s.substr(0, 5);
  string b = s.substr(6, 7);
  string c = s.substr(14, 5);
  cout << a << ' ' << b << ' ' << c << endl;
}

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

#define fo(i, n) for(ll i = 0; i < n; i++)
#define of(i, n) for(ll i = n - 1; i >= 0; i--)
#define ll long long
#define vec vector<ll>
#define fio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define tr(container, it) \
for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)


ll mod= 1e9+7;

#define umap unordered_map

string t;

ll sub(string s)
{
    ll l=0,h=s.length();
    ll j=0;
    for (int i=0; i<s.length()&&j<t.length(); i++)
       if (t[j] == s[i])
         j++;

    return (j==t.length());
}

ll check(ll n, string s)
{
    ll l,h;
    l=0;h=n-1;
    while(h<s.length()){
        if(sub(s.substr(l,h))) return 1;
        l++;h++;
    }
    return 0;
}

ll ab(ll x)
{
    if(x<0) x*=-1;
    return x;
}
int main()
{
    fio;
    ll n;
    cin>>n;
    ll h[n];
    fo(i,n) cin>>h[i];
    ll c[n];
    //cout<<llabs(-29);
    fo(i,n) c[i]=1e9;
    c[0]=0;
    c[1]=abs(h[1]-h[0]);
    for(int i=2;i<n;i++)
    {
        c[i] = min(c[i-1]+ab(h[i]-h[i-1]),c[i-2]+ab(h[i]-h[i-2]) );
    }
    cout<<c[n-1]<<endl;

}






Measured memory_bytes: 1792
fun main(args:Array<String>?): Unit {
    while(true){
        val (d, n) = readLine()!!.trim().split(' ').map(String::toInt)
        if (n == 0) return
        val tools = Array(n){
            val (a, e, r) = readLine()!!.trim().split(' ').map(String::toInt)
            Tool(a, e, r)
        }
        println(
                solve(d, tools) ?: "NA"
        )
    }
}
fun solve(treeHealth: Int, tools: Array<Tool>): Int? {
    if (tools.none{it.experienceNeed == 0 && (it.experienceGain > 0 || it.damage > 0)}) return null
    val sorted = tools.filterNot{it.damage == 0 && it.experienceGain == 0}.sortedBy(Tool::experienceNeed)
    val maxExperience = sorted.maxBy(Tool::experienceNeed)!!.experienceNeed
    val memo = Array(treeHealth + 1){Array(maxExperience + 1){Array(tools.size){null as Int?}}}
    fun sub(health: Int, experience: Int, tool: Int): Int? {
        return when{
            health <= 0 -> 0
            tool >= sorted.size -> null
            memo[health][experience][tool] != null -> memo[health][experience][tool]
            experience < sorted[tool].experienceNeed -> null
            sorted[tool].damage == 0 && experience == maxExperience -> {
                memo[health][experience][tool] = sub(health, experience, tool + 1)
                memo[health][experience][tool]
            }
            else -> {
                memo[health][experience][tool] = listOf(sub(health - sorted[tool].damage, minOf(maxExperience, experience + sorted[tool].experienceGain), tool)?.let{it + 1}, sub(health, experience, tool + 1)).filterNotNull().min()
                memo[health][experience][tool]
            }
        }
    }
    return sub(treeHealth, 0, 0)
}
data class Tool(val damage: Int, val experienceGain: Int, val experienceNeed: Int)


Measured memory_bytes: 543664
#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <cstring>

using namespace std;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
#define pii pair < int, int >
#define pll pair < long long, long long>
#define ull unsigned long long
#define vi vector < int >
#define vll vector < long long >
#define sz(a) (int)a.size()
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it++)
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x))
#define fname "searching"

const int inf = (int)1e9;
const ll INF = (ll)1e18;
const double eps = 1e-9;
const double pi = acos(-1.0);
const int mod = (int)1e9 + 7;

// Rating 1-399 : gray
// Rating 400-799 : brown
// Rating 800-1199 : green
// Rating 1200-1599 : cyan
// Rating 1600-1999 : blue
// Rating 2000-2399 : yellow
// Rating 2400-2799 : orange
// Rating 2800-3199 : red

int n;
int cnt[10];

int num_color(int x){
    if(x < 400) return 0;
    else if(x < 800) return 1;
    else if(x < 1200) return 2;
    else if(x < 1600) return 3;
    else if(x < 2000) return 4;
    else if(x < 2400) return 5;
    else if(x < 2800) return 6;
    else if(x < 3200) return 7;
    else return 8;
}

void solve(){
    cin >> n;
    for(int i = 0, x; i < n; ++i){
        cin >> x;
        cnt[(num_color(x))]++;
    }
    int sum = 0;
    for(int i = 0; i < 8; ++i)
        sum += (cnt[i] > 0);
    
    cout << (sum > 0 ? sum : 1) << " " << (sum + cnt[8]) << "\n";
}

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

    solve();
    
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
  int n,k;
  cin >> n >> k;
  string s;
  cin >> s;
  switch(s[k-1]){
    case 'A': s[k-1] = 'a'; break;
    case 'B': s[k-1] = 'b'; break;
    case 'C': s[k-1] = 'c'; break;
  }
  cout << s;
  return 0;
}  

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(false),cin.tie(nullptr);
#define task "c"
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define bit(x,i) ((x>>(i-1))&1)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1<<(i-1)))

const int N=200010;

int n,step;
int a[N],b[N];
priority_queue<ii> h;

main(){
    //freopen(task".inp","r",stdin);
    //freopen(task".out","w",stdout);
    n=in;
    forinc(i,1,n) a[i]=in;
    forinc(i,1,n) b[i]=in;
    auto L=[&](int i){
        return i==1?n:i-1;
    };
    auto R=[&](int i){
        return i==n?1:i+1;
    };
    auto chk=[&](int i){
        if(b[i]>a[i]) h.push({b[i],i});
    };
    forinc(i,1,n) chk(i);
    while(h.size()){
        int c=h.top().fi,i=h.top().se; h.pop();
        if(b[i]!=c) continue;
        int x=b[L(i)],y=b[i],z=b[R(i)];
        if(y<x+z) return cout<<-1,0;
        int del=(y-a[i])/(x+z);
        step+=del;
        b[i]-=del*(x+z);
        chk(L(i));
        chk(R(i));
    }
    forinc(i,1,n) if(b[i]^a[i]) return cout<<-1,0;
    cout<<step;
}


Measured memory_bytes: 13036
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()

int main(){
    int N;cin>>N;
    bool flag=false;
    for(int i=1;i<=9;i++){
        int a=N/i;
        if(a<=9 && a>0 && N%i==0){
            flag=true;
            break;
        }
    }
    if(flag){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}


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

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

        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(f.readLine());

        int N = Integer.parseInt(st.nextToken());
        int W = Integer.parseInt(st.nextToken());

        long[][] dp = new long[N + 1][W + 1]; // default 0ed out

        long[][] items = new long[N][2];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(f.readLine());
            items[i][0] = Long.parseLong(st.nextToken());
            items[i][1] = Long.parseLong(st.nextToken());
        }

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[i].length; j++) {
                if (j < items[i-1][0] ) { // first item indexing
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][ (int) (j - items[i-1][0])] + items[i-1][1]);
                }
            }
        }

        /* for (long[] i : dp){
            for (long j : i){
                System.out.print(String.valueOf(j) + " ");
            }
            System.out.println();
        } */

        System.out.println(dp[N][W]);
    }
}

Measured memory_bytes: 127572
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
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; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;
ll n, m, x;
vector<vector<ll>> a;
vector<ll> cost;
ll ans = INF;

int main() {

  cin >> n >> m >> x;
  a.assign(n, vector<ll>(m));
  cost.resize(n);

  rep(i, n) {
    cin >> cost[i];
    rep(j, m) cin >> a[i][j];
  }

  rep(i, 1<<n) {
    vector<int> d(n);
    rep(j, n) if (i>>j&1) {
      d[j] = 1;
    }
    vector<ll> score(m, 0);
    ll money = 0;

    rep(j, n) {
      if (d[j] == 1) {
        rep(k, m) score[k] += a[j][k];
        money += cost[j];
      }
    }

    bool flg = true;
    rep(i, m) {
      if (score[i] < x) flg = false;
    }
    if (flg) chmin(ans, money);
  }

  if (ans == INF) cout << -1 << endl;
  else cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3632
#include<stdio.h>
#define N 2000000
#define INFTY (1<<30)

void insert(int);
int extractmax(void);
void maxHeap(int);
void increase(int,int);
int H,A[N+1];

int main()
{
  
  char c[10];
  int n;
  while(1){
    scanf("%s",c);

    if(c[0]=='e' && c[1]=='n')break;
    else if(c[0]=='i'){
      scanf("%d",&n);
      insert(n);   }
    else printf("%d\n",extractmax());
	   }
  return 0;
}

void increase(int i,int n)
{
  int x;
  if(n<A[i])return;
  A[i]=n;
  while(i>1 && A[i/2]<A[i])
    {
      x=A[i];
      A[i]=A[i/2];
      A[i/2]=x;
      i=i/2;
    }
}

void insert(int n)
{
  H++;
  A[H]=-INFTY;
  increase(H,n);
}

int extractmax(void)
{
  int max;
  if(H<1)return -INFTY;
  max=A[1];
  A[1]=A[H--];
  maxHeap(1);
  return max;
}

void maxHeap(int i)
{
  int l,r,largest,x;
  l = i*2;
  r = i*2+1;
  /* 左の子、自分、右の子で値が最大のノードを選ぶ*/
if (l<=H && A[l]>A[i])
  largest = l;
else
  largest = i;

if(r<=H && A[r] > A[largest])
  largest = r;
 if (largest != i)
   {x=A[i];
    A[i]=A[largest];
    A[largest]=x;

   maxHeap(largest);/* 再帰的に呼び出し*/ }
}




Measured memory_bytes: 5600
fn main() {
    use std::io::{stdin, stdout, BufRead, BufReader, BufWriter, Write};
    let stdin = stdin();
    let stdin = BufReader::new(stdin.lock());
    let stdout = stdout();
    let mut stdout = BufWriter::new(stdout.lock());

    let mut lines = stdin.lines();
    let a: Vec<usize> = lines
        .next()
        .unwrap()
        .unwrap()
        .split_whitespace()
        .map(|s| s.parse().unwrap())
        .collect();
    let n = a[0];
    let k = a[1];

    let mut a: Vec<i64> = lines
        .next()
        .unwrap()
        .unwrap()
        .split_whitespace()
        .map(|s| s.parse::<i64>().unwrap())
        .collect();

    let ans: i64 = if k >= a.len() {
        0
    } else {
        a.sort();
        a.into_iter()
            .enumerate()
            .filter(|&(i, _)| i < n - k)
            .map(|(_, v)| v)
            .sum()
    };
    writeln!(stdout, "{}", ans).unwrap();
}

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

map<vector<int>, int> dp;

int rec(vector<int> &v, int sum){
    if(dp.count(v)) return dp[v];
    int res = 0;
    for(int i=9; i>=1; i--){
        if(v[i]>0 && sum+i<=10){
            v[i]--;
            res = max(res, rec(v, (sum+i)%10)+(sum+i)/10);
            v[i]++;
        }
    }
    return dp[v] = res;
}

int main() {
    int n;
    while(cin >> n, n){
        vector<int> v(10,0);
        int ans = 0;
        for(int i=0;i<n;i++){
            int a;
            cin >> a;
            v[a]++;
        }
        for(int i=1;i<=4;i++){
            int tmp = min(v[i], v[10-i]);
            ans += tmp;
            v[i] -= tmp;
            v[10-i] -= tmp;
        }
        ans += v[5]/2;
        v[5] %= 2;
        dp.clear();
        ans += rec(v, 0);
        cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 68112
n,a,b= map(int, input().split())
mod=pow(10,9)+7

x=pow(2,n,mod)

v=1
w=1
for i in range(a):
    v*=n-i
    v%=mod
    w*=a-i
    w%=mod

c=v*pow(w,mod-2,mod)
v=1
w=1
for i in range(b):
    v*=n-i
    v%=mod
    w*=b-i
    w%=mod

d=v*pow(w,mod-2,mod)
d%=mod

ans=(x-c-d-1)%mod
print(ans)


Measured memory_bytes: 39024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pll pair<ll, ll>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define endl '\n'
const int inf = 1000000007;
const ll INF = 1e18;
// int mod = 998244353;
int mod = 1000000007;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
template<typename T, typename U> T pow_(T a, U b) { return b ? pow_(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll modpow(ll a, ll b, ll _mod) { return b ? modpow(a * a % _mod, b / 2, _mod) * (b % 2 ? a : 1) % _mod : 1; }
template<class T, class U> ostream& operator << (ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) { rep(i, sz(vec)) { if (i) os << " "; os << vec[i]; } return os; }
template<class T> ostream& operator << (ostream& os, const set<T>& s) { for (auto e : s) os << e; return os; }
template<typename T> inline istream& operator >> (istream& is, vector<T>& v) { rep(j, sz(v)) is >> v[j]; return is; }
template<class T, class T2> inline void add(T &a, T2 b) { (a += b % mod) %= mod; if (a < 0) a += mod; }
template<class T> void operator += (vector<T>& v, vector<T> v2) { rep(i, sz(v2)) v.eb(v2[i]); }


void solve();

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout << fixed << setprecision(12); // debuged
  int T;
  T = 1;
  while (T--) solve();
}

using pci = pair<char, int>;
vector<pci> runlength(string s) {
  vector<pci> ret;
  int cnt = 1;
  int n = sz(s);
  rep3(i, 1, n) {
    if (s[i] == s[i - 1]) ++cnt;
    else { ret.eb(s[i - 1], cnt); cnt = 1; }
  }
  ret.eb(s[n - 1], cnt);
  return ret;
}

void solve() {
  int n;
  cin >> n;
  vector<int> a(n);
  cin >> a;
  sort(all(a));
  ll ans = 0;
  rep(i, n) rep3(j, i + 1, n) { // 小さい方2本探索
    int it = lb(a, a[i] + a[j]);
    it--;
    if (it <= j) continue;
    ans += max(0, it - j);
  }
  cout << ans << endl;
}


Measured memory_bytes: 3628
#include<stdio.h>
int main(void){
	int i[100000],x,y,z,a;
	
	x=0;
	z=0;
	
	while(1){
		scanf("%d",&i[x]);
		if(i[x]==0)
		{break;}
		x++;
		z++;
	}
	x=0;
	a=1;
	
	for(y=0;y<z;y++)
	{
	printf("Case %d: %d\n",a,i[x]);
	x++;
	a++;
	}
	return 0;
}


Measured memory_bytes: 1976
#pragma GCC optimize("O3")
/* #pragma GCC target ("avx2") */
/* #pragma GCC optimize("Ofast") */
/* #pragma GCC optimize("unroll-loops") */
/* #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") */
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T, typename cmp=less<T>>
using ordered_set=tree<T,null_type,cmp,rb_tree_tag,tree_order_statistics_node_update>;
template<typename K, typename V, typename cmp=less<K>>
using ordered_map=tree<K, V, cmp, rb_tree_tag, tree_order_statistics_node_update>;
// find_by_order(k) returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;
using ll = long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
const int nax = 1000*1007;
#define ar array
#define len(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define tT template<typename T
#define tV typename V
#define ins inline string
#ifdef LOCAL
tT>ins to_string(T& t);
ins to_string(string s) {return '"' + s + '"';}
ins to_string(char c){string res="'";res.push_back(c);return res+"'";}
ins to_string(const char* s) {return to_string((string)s);}
ins to_string(char* s) {return to_string((string)s);}
template <size_t N>ins to_string(bitset<N> v) {string res="";for(size_t i = 0; i < N; i++){
res += static_cast<char>('0' + v[i]);}return res;}
ins to_string(bool b) {return (b ? "true" : "false");}
tT,tV>ins to_string(pair<T, V>& p){return "("+ to_string(p.first)+", "+to_string(p.second)+")";}
tT>ins to_string(T& v){string res="{";for(auto& i:v){res+=to_string(i)+',';} return res+'}';}
#define log(...) cerr<< "[" << #__VA_ARGS__ << " : "<< to_string(__VA_ARGS__) << "]"<<endl
#else
#define log(...) 0x30
#endif

int dp[100000+7][3];

int solve(const vector<array<int, 3>>& arr, int n, int dont){
    if( n == 1){
        if(dont == 0) return max(arr[n-1][1], arr[n-1][2]);
        else if(dont == 1) return max(arr[n-1][0], arr[n-1][2]);
        else return max(arr[n-1][0], arr[n-1][1]);
    }
    if(dp[n][dont]!=-1){
        log("found");
        return dp[n][dont];
    }

    if(dont == 0){
        return dp[n][dont] = max(solve(arr, n-1, 1)+arr[n-1][1], solve(arr, n-1, 2)+arr[n-1][2]);
    }
    else if(dont == 1){
        return dp[n][dont] = max(solve(arr, n-1, 0)+ arr[n-1][0], solve(arr, n-1, 2) + arr[n-1][2]);
    }
    else return dp[n][dont] = max(solve(arr, n-1, 0) + arr[n-1][0], solve(arr, n-1, 1) + arr[n-1][1]);
}

inline void test_case(){
    memset(dp, -1, sizeof dp);
    int n;
    cin>>n;
    vector<array<int, 3>> arr(n);
    for(int i=0; i<n; i++){
        for(int j=0; j<3; j++){
            cin>>arr[i][j];
        }
    }
    cout<<max(max(solve(arr, n, 0), solve(arr, n, 1)), solve(arr, n, 2))<<"\n";
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    test_case();
}   



Measured memory_bytes: 6528
abcd = input()
ans=''
for i in range(8):
    op1 = '+' if (1 & i) != 0 else '-'
    op2 = '+' if (2 & i) != 0 else '-'
    op3 = '+' if (4 & i) != 0 else '-'
    s = abcd[0] + op1 + abcd[1] + op2 + abcd[2] + op3 + abcd[3]
    if eval(s) == 7: ans = s + '=7'
print(ans)


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

const int MAX_N = 1e5+10;
int N;
int a[MAX_N],b[MAX_N];

void solve()
{
	long long ans = 0;
	for(int i=0;i<N;++i){
		long long cur = 0, nex = 0;	
		if(a[i] > 0){
			cur = min(a[i],b[i]);
			a[i]-=cur;
			b[i]-=cur;
		}
		if(a[i+1]>0 && b[i] > 0){
			nex = min(a[i+1], b[i]);
			a[i+1]-=nex;
			b[i]-=nex;
		}
		ans += cur + nex;
	}
	cout << ans << endl;
}

int main()
{
	cin >> N;
	for(int i=0;i<=N;++i)cin >> a[i];
	for(int i=0;i<N;++i)cin >> b[i];
	solve();
	return 0;
}

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

int main(){
  string a;
  cin>>a;
  char b=a.at(0);
  int c=0;
  for(int i=0;i<a.size();i++){
    if(a.at(i)!=b){
      b=a.at(i);
      c++;
    }
  }
  cout<<c<<endl;
}

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

using namespace std;

ll h, w, ans = 0, d[11], c[11][11], f[11][11], a[201][201];

int main(){
    cin >> h >> w;
    for (int i = 0; i <= 9; i++)
        for (int j = 0; j <= 9; j++) cin >> c[i][j], f[i][j] = c[i][j];
    for (int i = 1; i <= h; i++)
        for (int j = 1; j <= w; j++){
            cin >> a[i][j];
            if (a[i][j] != -1) d[a[i][j]]++;
        }
    for (int k = 0; k <= 9; k++)
        for (int i = 0; i <= 9; i++)
            for (int j = 0; j <= 9; j++) f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
    for (int i = 0; i <= 9; i++) ans += f[i][1] * d[i];
    cout << ans;
}

Measured memory_bytes: 512