akhauriyash/Code-Regression huggingface dataset:
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;

public class Main {

	public static void main(String[] args) {
		Task task = new Task();
		task.solve();
	}

	public static class Task {
		static final long MOD = (long) 1e9 + 7;

		public void solve() {
			Scan sc = new Scan();
			int k = (int) sc.scanLong();
			int t = (int) sc.scanLong();
			int mx = 0;
			while (t-- > 0) {
				int curr = (int) sc.scanLong();
				mx = Math.max(mx, curr);
			}
			int rem = k - mx;
			if (rem > mx)
				System.out.println(0);
			else
				System.out.println(mx - rem - 1);
		}
	}

	public static class Scan {
		private byte[] buf = new byte[1024];
		private int index;
		private InputStream in;
		private int total;

		public Scan() {
			in = System.in;
		}

		public int scan() {
			if (total < 0)
				throw new InputMismatchException();
			if (index >= total) {
				index = 0;
				try {
					total = in.read(buf);
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
				if (total <= 0)
					return -1;
			}
			return buf[index++];
		}

		public long scanLong() {
			long integer = 0;
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			int neg = 1;
			if (n == '-') {
				neg = -1;
				n = scan();
			}
			while (!isWhiteSpace(n)) {
				if (n >= '0' && n <= '9') {
					integer *= 10;
					integer += n - '0';
					n = scan();
				} else
					throw new InputMismatchException();
			}
			return neg * integer;
		}

		public double scanDouble() throws IOException {
			double doub = 0;
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			int neg = 1;
			if (n == '-') {
				neg = -1;
				n = scan();
			}
			while (!isWhiteSpace(n) && n != '.') {
				if (n >= '0' && n <= '9') {
					doub *= 10;
					doub += n - '0';
					n = scan();
				} else
					throw new InputMismatchException();
			}
			if (n == '.') {
				n = scan();
				double temp = 1;
				while (!isWhiteSpace(n)) {
					if (n >= '0' && n <= '9') {
						temp /= 10;
						doub += (n - '0') * temp;
						n = scan();
					} else
						throw new InputMismatchException();
				}
			}
			return doub * neg;
		}

		public String scanString() {
			StringBuilder sb = new StringBuilder();
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			while (!isWhiteSpace(n)) {
				sb.append((char) n);
				n = scan();
			}
			return sb.toString();
		}

		public char scanChar() {
			int n = scan();
			while (isWhiteSpace(n))
				n = scan();
			return (char) n;
		}

		private boolean isWhiteSpace(int n) {
			if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1)
				return true;
			return false;
		}
	}
}


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

int main()
{
  int N, K;
  cin >> N >> K;
  string input;
  cin >> input;

  string result;

  int i = 0;
  for (char charInStr : input)
  {
    i++;
    if (K == i)
    {
      if (charInStr == 'A')
      {
        result += 'a';
      }
      else if (charInStr == 'B')
      {
        result += 'b';
      }
      else
      {
        result += 'c';
      }
    }
    else
    {
      result += charInStr;
      continue;
    }
  }
  cout << result << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;using ll = long long;using ld = long double;using P = pair<ll,ll>;
#define rt "\n"
#define sp " "
#define test1 cout << "test1" << endl;
#define test2 cout << "test2" << endl;
#define fixprecision(n) fixed; cout << setprecision(n)
#define kyopro ios::sync_with_stdio(false);cin.tie(NULL)
#define MOD 1000000007
#define iikae auto&
#define rep(i, s, N) for(ll i{s}; i < N; i++)
#define rem(i, s, N) for(ll i{N - 1}; i > s - 1; i--)
ll gcd(ll a, ll b){return b != 0 ? gcd(b, a % b) : a;}
struct UnionFind{vector<ll> par;UnionFind(ll n) : par(n, -1){}void init(ll n){par.assign(n, -1);}ll root(ll x){if (par[x] < 0) return x;else return par[x] = root(par[x]);}bool issame(ll x, ll y){return root(x) == root(y);}bool merge(ll x, ll y){x = root(x); y = root(y);if(x == y) return false;if(par[x] > par[y]) swap(x, y);par[x] += par[y];par[y] = x;return true;}int size(int x) {return -par[root(x)];}};

int main(){
  kyopro;
  ll N, M;
  cin >> N >> M;
  vector<P> XY(M);
  for(auto&& i : XY){
    ll third;
    cin >> i.first >> i.second >> third;
    i.first--;
    i.second--;
  }
  UnionFind card(N);
  for(auto&& i : XY){
    card.merge(i.first, i.second);
  }
  set<ll> nekko;
  rep(i, 0, N){
    nekko.insert(card.root(i));
  }
  cout << nekko.size() << rt;
}

Measured memory_bytes: 7296
#include <iostream> // cin, cout, cerr
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota
#include <cstdio> // printf, scanf
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <iomanip> // cout<<setprecision(n)
#include <functional> // function<void(int)>

#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif

#define int long long // at least int64 > 9*10^18
#define ENDL '\n'
#define rep(i,n) for(int i = 0; i < (n); i++)
#define print(i) std::cout << (i) << '\n'
#define all(v) (v).begin(), (v).end()
/* libraries */

signed main() {
	int n;
	std::cin >> n;
	std::string s;
	std::cin >> s;
	if(n%2==1) {
		print("No");
		return 0;
	}
	int yes = true;
	rep(i,n/2) {
		if(s[i]!=s[n/2+i]) yes = false;
	}
	if(yes) print("Yes");
	else print("No");
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include<algorithm> 
using namespace std;
 
# define p(s) std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
 
int main()
{
    int n;cin >> n ;

    map<long long int,long long int> m;
    vector<long long int> l;
    for(int i=0;i<n;i++){
        long long int tmp;cin >> tmp;
        m[tmp]++;
        if(m[tmp]==2) l.push_back(tmp);
        if(m[tmp]==4) l.push_back(tmp);
    }
    sort(l.begin(),l.end(),greater<>());
    if(l.size()<=1) p(0)
    else p(l[0]*l[1])
}

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

int main() {
  int N, count;
  count = 0;
  cin >> N;
  vector<int> L(N);
  for(int i = 0; i < N; i++){
    cin >> L[i];
  }
  
  for(int i = 0; i < N-1; i++){
    for(int j = i + 1; j < N; j++){
      for(int k = j + 1; k < N; k++){
        if(L[i] + L[j] > L[k] 
           && L[j] + L[k] > L[i]
           && L[i] + L[k] > L[j]
           && L[i] != L[j]
           && L[i] != L[k]
           && L[j] != L[k] ){
          count++;
        }
        
      }
    }
  }
  
  cout << count << endl;
}

Measured memory_bytes: 3636
use std::io::Read;
use std::collections::VecDeque;

fn bfs(tree: &Vec<Vec<usize>>, start: usize) -> Vec<usize> {
    let mut dist: Vec<usize> = vec![tree.len(); tree.len()];
    let mut queue: VecDeque<usize> = VecDeque::new();

    dist[start] = 0;
    queue.push_back(start);

    while !queue.is_empty() {
        let curr_node = queue.pop_front().unwrap();
        for i in &tree[curr_node] {
            if dist[*i] < tree.len() {
                continue;
            }
            dist[*i] = dist[curr_node] + 1;
            queue.push_back(*i);
        }
    }
    dist
}

fn main() {
    let mut buf = String::new();
    let stdin = std::io::stdin();
    stdin.lock().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();

    let n: usize = iter.next().unwrap().parse().unwrap();
    let u: usize = iter.next().unwrap().parse().unwrap();
    let v: usize = iter.next().unwrap().parse().unwrap();

    let mut tree: Vec<Vec<usize>> = vec![vec![0]; n+1];

    for _ in 1..n {
        let a: usize = iter.next().unwrap().parse().unwrap();
        let b: usize = iter.next().unwrap().parse().unwrap();
        tree[a].push(b);
        tree[b].push(a);
    }

    let mut ans: usize = 0;
    let dist_from_u = bfs(&tree, u);
    let dist_from_v = bfs(&tree, v);

    for (du, dv) in dist_from_u.iter().zip(&dist_from_v) {
        if du <= dv {
            ans = std::cmp::max(ans, dv-1);
        }
    }
    
    println!("{}", ans);
}


Measured memory_bytes: 16636
#include<bits/stdc++.h>
#define ci const int&
using namespace std;
struct edge{
	int u,v,val;
}e[100010];
int n,m,h,w,u,v,val,f[200010],tg[200010];
long long ans;
bool cmp(edge x,edge y){
	return x.val>y.val;
}
int getf(ci x){
	return f[x]!=x?f[x]=getf(f[x]):x;
}
void Kruscal(){
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;++i){
		if(getf(e[i].u)==getf(e[i].v))!tg[f[e[i].u]]?tg[f[e[i].u]]=1,ans+=e[i].val:0;
		else if(!tg[f[e[i].u]]||!tg[f[e[i].v]])f[f[e[i].u]]=f[e[i].v],tg[f[e[i].v]]|=tg[f[e[i].u]],ans+=e[i].val;
	}
}
int main(){
	scanf("%d%d%d",&m,&h,&w),n=h+w;
	for(int i=1;i<=n;++i)f[i]=i;
	for(int i=1;i<=m;++i)scanf("%d%d%d",&u,&v,&val),e[i]=(edge){u,h+v,val};
	Kruscal(),printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 3200
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define endl '\n'
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int main()
{
    FASTINOUT;
    int x;
    cin>>x;
    int y[x];
    for (int i=0; i<x; i++)
    {
        cin>>y[i];
    }
    sort(y,y+x);
    reverse(y,y+x);
    ll sum=y[0];
    int i=1,cnt=1;
    while (cnt<x-1)
    {
        cnt+=2;
        sum=sum+y[i]+y[i];
        i++;
    }
    cout<<sum-(x&1?y[i-1]:0)<<endl;
    return 0;
}


Measured memory_bytes: 4392
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int N;

int main() {
    cin >> N;
    int A[1000000];
    for (int i = 0; i < 3 * N; i++) {
        cin >> A[i];
    }
    sort(A, A + 3 * N, greater<>());
    long long int sum = 0;
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        cnt++;
        sum += A[cnt];
        cnt++;
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define sz size
#define se second
#define fe first
#define mper make_pair
#define all(x) x.begin(), x.end()
#define mal ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL);
#define saken string
#define erba continue
using namespace std;

ll a, b;

bool kek = 0;

int main(){

mal

cin >> a >> b;

if(a == b) {cout << 0;return 0;}
else if(abs(a) == abs(b)) {cout << 1;return 0;}

if(b == 0) {

    kek = 1;

}


if(a >= 0 && b >= 0) {

    if(b > a) {cout << b - a - kek;}
    else {

        cout << (a - b) + 2 - kek;

    }

}

else if(a >= 0 && b < 0) {

    if(b * -1 > a) {cout << (b * -1) - a + 1 - kek;}
    else {

        cout << (a - (b * -1)) + 1 - kek;

    }

}

else if(a < 0 && b >= 0) {

    if(b > a * -1) {cout << b - (a * -1) + 1 - kek;}
    else {

        cout << (a * -1) - b + 1 - kek;

    }

}

else {

    if(a * -1 < b * -1) {cout << 2 + ((b * -1) - (a * -1)) - kek;}
    else {cout << abs(a) - abs(b) - kek;}

}

return 0;
}



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

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
	ll n{0};
	ll k{0};
	cin>>n>>k;

	ll arr[n];
	for(ll i=0;i<n;i++)
		cin>>arr[i];


	ll j{0};
	for(ll i=k;i<n;i++){
		if(arr[i]>arr[j])
			cout<<"Yes"<<endl;
		else
			cout<<"No"<<endl;
		j++;
	}
	return 0;
}



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

int main() {
    int in = 1;
    int i = 1;
    while (true) {
        cin >> in;
        if (in == 0) {
            break;
        }
        cout << "Case " << i << ": " << in << endl;
        i += 1;
    }
}

Measured memory_bytes: 2992
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;

int main(){
  int a,b;
  cin >> a >> b;
  if((a+b)%2==0){
    cout << (a+b)/2 << endl;
  }else{
    cout << (a+b+1)/2 << endl;
  }
}


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

int main(){
  int n,ans,count,hoge,j;
  cin>>n;
  ans = 1;
  count = 0;
  for(int i=1;i<=n;i++){
    j = 0;
    hoge = i;
    while(hoge%2==0){
      hoge = hoge/2;
      j++;
    }
    if(count<j){
      count = j;
      ans = i;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
n, m = map(int, input().split())
digit = ''.join(['0',str(n),'b'])
cost = [0] + [m*10**5+1] * (2**n-1)
for i in range(m):
  a, b = map(int,input().split())
  c = list(map(int, input().split()))
  cc = 0
  for j in c:
      cc += 2**(j-1)
  for j in range(2**n):
    jj = j | cc
    cost[jj] = min(cost[jj],cost[j]+a)
if cost[-1] == m*10**5+1:
  print(-1)
else:
  print(cost[-1])

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

using namespace std;

bool ok(const string& S)
{
	const int L = S.size();
	if (L % 2 != 0) {
		return false;
	}
	for (int i = 0; i < L; i += 2) {
		if (S.substr(i, 2) != "hi") {
			return false;
		}
	}
	return true;
}

int main()
{
	string S;
	cin >> S;
	if (ok(S)) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No";
	}
}


Measured memory_bytes: 256
mod io{
    use std::io::*;
    pub fn read<T: ::std::str::FromStr>()->T{
        let stdin=stdin();
        let ret=stdin.lock().bytes().map(|c|c.unwrap()as char)
        .skip_while(|c|c.is_whitespace())
        .take_while(|c|!c.is_whitespace())
        .collect::<String>().parse().ok().unwrap();
        ret
    }
}
use io::read;
fn main(){
    let a=(read::<i32>()+11)%13;
    let b=(read::<i32>()+11)%13;
    println!("{}",if a>b{"Alice"}else if a<b{"Bob"}else{"Draw"})
}

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

int main() {
    int n, ix;
    cin >> n >> ix;
    vector<int> x(n);
    for (auto& e : x) cin >> e;
    x.push_back(ix);
    sort(begin(x), end(x));
    int s = x[0];
    for (auto& e : x) e -= s;
    vector<int> d;
    for (int i = 0; i + 1 < x.size(); i++) d.push_back(x[i+1] - x[i]);
    int ans = d[0];
    for (int i = 1; i < x.size(); i++) ans = __gcd(ans, d[i]);
    cout << ans << endl;
}


Measured memory_bytes: 1528
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL<<60;

ll solve() {
    ll N;
    cin >> N;
    ll a;
    vector<pair<ll,int>> A(3*N);
    for ( int i = 0; i < 3*N; i++ ) {
        cin >> a;
        A[i] = make_pair(a, i);
    }
    set<pair<ll,int>> sp, sm, sr;
    ll tp = 0, tm = 0;
    for ( int i = 0; i < N; i++ ) {
        sp.insert(A[i]);
        tp += A[i].first;
    }
    for ( int i = N; i < 3*N; i++ ) {
        sm.insert(A[i]);
        tm += A[i].first;
    }
    for ( int i = 0; i < N; i++ ) {
        auto p = sm.end();
        p--;
        tm -= p->first;
        sr.insert(*p);
        sm.erase(p);
    }

    ll ans = tp - tm;
    for ( int i = N; i < 2*N; i++ ) {
        if ( sm.find(A[i]) != sm.end() ) {
            sm.erase(A[i]);
            tm -= A[i].first;
            auto x = *sr.begin();
            sm.insert(x);
            tm += x.first;
            sr.erase(x);
        } else {
            sr.erase(A[i]);
        }

        sp.insert(A[i]);
        tp += A[i].first;
        auto y = *sp.begin();
        sp.erase(y);
        tp -= y.first;

        if ( ans < tp - tm ) ans = tp - tm;
    }

    return ans;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

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

int main()
{
    ll N,W;
    cin>>N>>W;
    vector<vector<ll>>dp(N+1,vector<ll>(W+1));
    for (size_t i = 1; i <= N; i++)
    {   ll v,w;
        cin>>v>>w;
        rep(j,W+1)
        {   ll kosu= j!=0 ? j/w : 0; //商品の重さ/その列の重さ
            if(kosu>=1)
            {
             //rep(k,kosu+1){dp[i][j]=max(dp[i][j],max(dp[i-1][j],dp[i-1][j-w*k]+v*k));}
            //ここで、個数を最大の場合しか考えていなかったためWA,全ての個数について見るとTLE
            //dp[i][j-w]で、重複して選んだときの最善を考慮している(遷移前後のDPと、その式の内容(品1がn個、品2がm個などのように)をたどって書き出していくと理解しやすい)
            dp[i][j]=max(dp[i][j-w]+v,max(dp[i-1][j],dp[i-1][j-w]+v));
            }
            else
            {dp[i][j]=dp[i-1][j];}
            //cout<<float(v/w)<<endl;
            
           /* if(j<=W&&j-w>=0)
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v);
            else dp[i][j]=dp[i-1][j];*/
        }
      // cout<<dp[i][5-w]+v<<endl;
    }
    /*
    rep(i,N+1)
    {
        rep(j,W+1)
        {
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }*/
    cout<<dp[N][W]<<endl;

    return 0;
}


Measured memory_bytes: 10748
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

#define MOD 1000000007
#define REP(i, N) for (int i = 0; i < N; ++i)
#define REP1(i, N) for (int i = 1; i <= N; ++i)
#define RREP(i, N) for (int i = N - 1; i >= 0; --i)
#define ALL(a) a.begin(), a.end()

int main() {
  int N, Y;
  cin >> N >> Y;
  for (int i = 0; i <= N; ++i) {
    for (int j = 0; j <= N - i; ++j) {
      int k = N - i - j;
      if (0 <= k && k <= N) {
        int tmp = 10000 * i + 5000 * j + 1000 * k;
        if (tmp == Y) {
          cout << i << " " << j << " " << k << endl;
          return 0;
        }
      }
    }
  }
  cout << -1 << " " << -1 << " " << -1 << endl;
  return 0;
}

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

int n;
int arr[100005][3];
int dp[100005][3];

int solve(int pos,int choose)
{
    int &ret=dp[pos][choose];
    if(ret!=-1)return ret;
    if(pos>n)return 0;
    ret=-1;
    for(int next=0;next<3;next++){
        if(next!=choose)ret=max(ret,solve(pos+1,next)+arr[pos][choose]);
    }
    return ret;
}

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
    memset(dp,-1,sizeof(dp));
    int ans=max(max(solve(0,0),solve(0,1)),solve(0,2));
    cout<<ans;


}


Measured memory_bytes: 8832
import sys

sys.setrecursionlimit(10 ** 6)


def dfs(v, p, c):
    colors[v] = c
    for next_v, d in g[v]:
        if next_v == p:
            continue
        if d % 2 == 0:
            dfs(next_v, v, c)
        else:
            dfs(next_v, v, 1 - c)


N = int(input())

g = [[] for _ in range(N)]
colors = [[] for _ in range(N)]
for i in range(N - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append([v, w])
    g[v].append([u, w])

dfs(0, -1, 0)
print(*colors, sep='\n')

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

#define ll long long

int main()
{
    ll n,k;
    cin>>n>>k;
    if(k==1||n==k)
        cout<<0;
    else
    {
        ll x = n%k;
        ll a = abs(x-k);
        ll b = abs(a-k);
        cout<<min(a,b);
    }
    return 0;
}

Measured memory_bytes: 3600
// 4_abc132_d
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define SZ(x) ((int)(x).size())
#define INF (1e16)
typedef long long ll;

const int MAX = 510000;
const int MOD = 1000000007;

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

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

long long PERM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[n - k] % MOD) % MOD;
}

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

    COMinit();

    int n, k;
    cin >> n >> k;
    rep1(i, k){
        cout << COM(n - k + 1, i) * COM(k - 1, i - 1) % MOD << endl;
    }
    return 0;
}


Measured memory_bytes: 12160
#include <string>
#include <vector>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
using namespace std;


#define prec(i) cout << fixed << setprecision(i)

const long long int MOD = 1000000007;


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


int main()
{
    prec(9);
  
	long long int n;
	double max;

	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] = (double)(v[i] + v[i + 1]) / 2;
	}

	cout << v[n - 1] << endl;

	return 0;

}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)

int main(){
	ll N;
	cin >> N;
	ll ans = 1;
	for (int i = 0; i < 3; i++) {
		ans *= N;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define FORq(i, m, n) for(int i = m;i <= n;i++)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n);
#define DEBUG printf("%s\n","debug")
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef long long ll;

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


ll N,A,B;
ll bmax = 0;
ll h[100002];


bool enough(ll T){
	ll k[100002];
	ll d1 = B*T;
	ll d2 = A-B;
	
	ll count = 0;
	
	REP(i,N){
		k[i] = h[i] - d1;
		
		if (k[i] <= 0) continue;
		if ((k[i] % d2) == 0) {
			count += k[i] / d2;
		} else {
			count += (k[i] / d2) + 1;
		}
	
	}
	
	if (count <= T) return true;
	else return false;
}


int binarysearch(ll L,ll R){
	while(abs(R-L) > 1){
		ll mid = (L+R)/2;
		if (enough(mid)) R = mid;
		else L = mid;

	}
	
	if (enough(L)) return L;
	else return R;
	
}


int main(){

	SCD3(N,A,B);
	REP(i,N){
		SCD(h[i]);
	}
	bmax = 1000000000;
	ll ans = binarysearch(1,bmax);
	
	PRINTLLD(ans);
	return 0;
}







Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i < (int)(n); i++)
#define Sort(a) sort(a.begin(), a.end())
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
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;}

int main(){
    int n;
    cin >> n;
    vi a(n);
    rep(i, n) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    ll sum = a[n-1];
    rep(i, (n-2)/2) {
        sum += a[n-i-2]*2;
        //cout << sum << " " << a[n-i-2]*2 << endl;
    }
    if(n%2 == 1) {
        sum += a[n-((n-2)/2)-2];
        //cout << sum << " " << a[n-((n-2)/2)-2] << endl;
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 4052
#include <bits/stdc++.h>
using namespace std;
int main(){
        int x, y; cin >> x >> y;
        if ((y % 2 == 0) && (y >= x * 2 && y <= x * 4)){
            cout << "Yes" << endl;
        }
        else{
            cout << "No" << endl;
        }
    return 0;
}


Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(a,b) for(int a=0;a<b;a++)
#define Sort(a) sort(a.begin(),a.end())
 int wari(int a,int b) {
   if(a%b==0)
     return a/b;
   else
     return a/b+1;
 }
 int keta(int a){//桁数
  double b=a;
  b=log10(b);
  int c=b;
  return c+1;
 }
 int souwa(int a){
  return a*(a+1)/2;
 }
 int lcm(int a,int b){//最小公倍数
  int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return d*e/f;
    }
  int gcm(int a,int b){//最大公約数
      int d=a,e=b,f;
  if(a<b)
    swap(a,b);
  int c,m=1;
  while(m){
    c=a%b;
    if(c==0){
       f=b;
      m--;
    }
    else{
      a=b;
      b=c;
 }
  }
  return f;
  }
signed main(){
  int x,a,b;
  cin>>x>>a>>b;
  cout<<(x-a)%b<<endl;
}

Measured memory_bytes: 256
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cfloat>
#define curr(P, i) P[(i) % P.size()]
#define next(P, i) P[(i+1) % P.size()]
#define prev(P, i) P[(i+P.size()-1) % P.size()]

using namespace std;

double EPS = 1e-10;
const double PI = acos(-1);

double add(double a, double b){
  if(abs(a+b) < EPS * (abs(a)+abs(b)))return 0;
  return a+b;
}

struct point{
  double x, y;
  point(){}
  point(double x,double y) : x(x) , y(y){}

  point operator + (point p){
    return point(add(x,p.x), add(y,p.y));
  }

  point operator - (point p){
    return point(add(x,-p.x), add(y,-p.y));
  }

  point operator * (double d){
    return point(x*d,y*d);
  }

};

double dot(point a, point b) {
  return (a.x * b.x + a.y * b.y);
}

double cross(point a, point b) {
  return (a.x * b.y - a.y * b.x);
}

int is_orthogonal(point a1, point a2, point b1, point b2) {
  return dot(a1-a2, b1-b2)==0.0;
}

int is_parallel(point a1, point a2, point b1, point b2) {
  return cross(a1-a2, b1-b2)==0.0 ;
}

int main(void){

  int q;
  cin >> q;
  while(q--){
    point a,b,c,d;
    cin >> a.x >> a.y >> b.x >> b.y;
    cin >> c.x >> c.y >> d.x >> d.y;
    if(is_orthogonal(a,b,c,d))cout << 1 << endl;
    else if(is_parallel(a,b,c,d))cout << 2 << endl;
    else cout << 0 << endl;
  }
  return 0;
}

Measured memory_bytes: 1232
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define All(V) V.begin(), V.end()
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD = 1e9+7, INF = 1e9;

int main()
{
  int k; cin >> k;
  if(k <= 9){
    cout << k << endl;
    return 0;
  }
  queue<ll> q;
  for(int i = 1; i <= 9; i++)q.push(i);
  for(int i = 0; i < k-1; i++){
    ll x = q.front(); q.pop();
    for(int j = -1; j <= 1; j++){
      ll nx = x % 10 + j;
      if(nx < 0 || nx > 9)continue;
      q.push(x*10 + nx);
    }
  }
  cout << q.front() << endl;
  system("pause");
}

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

int main(){
  string s;
  cin>>s;
  int a=0;
  int b=0;
  for(int i=0;i<3;i++){
    if(s.at(i)=='A'){
      a++;
    }
    if(s.at(i)=='B'){
      b++;
    }
  }
  if(a==3||b==3){
    cout<<"No"<<endl;
  }
  else{
    cout<<"Yes"<<endl;
  }
}

Measured memory_bytes: 3624
#include <cstdio>

using namespace std;

#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DUMP(a, n) REP(i, n) printf("%d%c", a[i], i + 1 == n ? '\n' : ' ')

const int N_MAX = 100000;

int N;
char s[N_MAX + 1];
int q[N_MAX + 1];
int a[N_MAX + 2];

void solve() {
  REP(i, N) q[i] = s[i] == 'o' ? 0 : 1;
  q[N] = q[0];
  REP(k, 4) {
    a[0] = k / 2; a[1] = k % 2;
    FOR(i, 1, N) {
      a[i + 1] = a[i] ^ q[i] == 0 ? a[i - 1] : (1 - a[i - 1]);
    }
    // DUMP(a, N + 1);
    if (a[N] == a[0] && a[N + 1] == a[1]) {
      REP(i, N) printf("%c", a[i] == 0 ? 'S' : 'W');
      printf("\n");
      return;
    }
  }
  puts("-1");
}

void input() {
  scanf("%d", &N);
  scanf("%s", s);
}

int main() {
  input();
  solve();
  return 0;
}


Measured memory_bytes: 1152
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int n, k;
    vector<map<int, int>> m(1024), ans(11);
    vector<int> cnt(1024, 1);
    m[0][0]++;
    for (int i = 0; i < (1 << 10); ++i) {
        for (int j = 0; j < 10; ++j) {
            if(!(i& (1 << j))){
                cnt[i^(1 << j)] = cnt[i]+1;
                for (auto &&l : m[i]) {
                    m[i^(1 << j)][l.first+(cnt[i])*j] += l.second;
                }
            }
        }
        for (auto &&j : m[i]) {
            ans[cnt[i]-1][j.first] += j.second;
        }
    }
    while(cin >> n >> k){
        cout << ans[n][k] << "\n";
    }
    return 0;
}


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

using namespace std;

const long long SZ = 26, MAXN = 2e3 + 40, MAXM = 2e6 + 40, mod = 1e9 + 7;
const double eps = 1e-9, Pi = acos(-1), inf = 1e9 + 100;
mt19937 rnd(mod);

int par[MAXN];
bool us[MAXN], vis[MAXN];
vector <int> g[MAXN];

void solve () {
    long long k;
    string s;
    cin >> s >> k;
    long long cnt = 0;
    long long a = 0, b = 0;
    int n = s.length();
    int last = 0, l = 0, r = n - 1;
    if (s[0] == s[n - 1]) {
        for (; l < n; ++l) {
            if (s[l] != s[0])
                break;
        }
        --l;

        for (; r >= 0; --r) {
            if (s[r] != s[0])
                break;
        }
        ++r;

        a = l + 1, b = n - r;
        last = l + 1;
        --r;
    }
    for (int j = l + 1; j <= r; ++j) {
        if (s[last] != s[j]) {
            cnt += j - last >> 1;
            last = j;
        }
    }
    if (last < r)
        cnt += r - last + 1 >> 1;
    if (a == n) {
        cnt = (a * k) >> 1;
    }
    else {
        cnt *= k;
        cnt += (k - 1) * (a + b >> 1) + (a >> 1) + (b >> 1);
    }
    cout << cnt;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(9);

//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    long long t = 1;
    while (t--)
        solve();
}


Measured memory_bytes: 256
// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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

const int N=3000+10;

int n,a[N];

struct edge { int v,nxt; } e[N<<1];
int head[N];
void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int dp[N];
void dfs(int u,int f) {
    dp[u]=0;
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==f||a[v]>=a[u]) continue;
        dfs(v,u); if (!dp[v]) { dp[u]=1; break; }
    }
}

int main() {
    n=read();
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    for (int i=1;i<=n;++i) { dfs(i,0); if (dp[i]) printf("%d ",i); }
    puts("");
    return 0;
}

Measured memory_bytes: 384
#include <algorithm>
#include <cctype>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>

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

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

typedef long long ll;

using namespace std;

class UnionFind {
   public:
    UnionFind(int n)  // 0~n-1までitemを初期化
    {
        parent = vector<int>(n, -1);  //親なら-size
    }
    int root(int a) {
        if (parent[a] < 0) return a;
        return parent[a] = root(parent[a]);
    }
    int size(int a) { return -parent[root(a)]; }
    bool connect(int a, int b) {
        int A = root(a);
        int B = root(b);
        if (A == B) return false;
        if (size(A) > size(B)) swap(A, B);
        parent[B] += parent[A];
        parent[A] = B;
        return true;
    }

   private:
    vector<int> parent;
};
struct edge {
    int to;
    int from;
    int cost;
};
struct city {
    int num;
    int x;
    int y;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // cout<<setprecision(10);
    int n;
    cin >> n;
    UnionFind uni(n + 1);
    vector<city> town(n);
    rep(i, n) {
        city nc;
        nc.num = i + 1;
        cin >> nc.x >> nc.y;
        town[i] = nc;
    }
    sort(all(town), [](city a, city b) { return a.x < b.x; });
    vector<edge> edges;
    rep(i, n - 1) {
        edge ne;
        ne.cost = town[i + 1].x - town[i].x;
        ne.to = town[i + 1].num;
        ne.from = town[i].num;

        edges.push_back(ne);
    }
    sort(all(town), [](city a, city b) { return a.y < b.y; });
    rep(i, n - 1) {
        edge ne;
        ne.cost = town[i + 1].y - town[i].y;
        ne.to = town[i + 1].num;
        ne.from = town[i].num;

        edges.push_back(ne);
    }
    sort(all(edges), [](edge a, edge b) { return a.cost < b.cost; });
    int res = 0;
    rep(i, edges.size()) {
        if (uni.connect(edges[i].to, edges[i].from)) res += edges[i].cost;
    }
    cout << res << endl;
    return 0;
}


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

using namespace std;

int main() {
  int K,X; cin>>K>>X;

  int left = X - (K-1);
  int right = X + (K-1);

  for (int i = left; i < right; i++) {
    cout << i << " ";
  }
  cout << right << endl;

  return 0;
}


Measured memory_bytes: 256
import itertools
while True:
    N = int(input())
    if not N:
        break
    D = [[] for _ in range(30)]
    for i in range(N):
        for x in map(int, input().split()[1:]):
            D[x - 1].append(i)
    C = [1 << i for i in range(N)]
    for d in range(30):
        for i, j in itertools.combinations(D[d], 2):
            C[i] = C[j] = C[i] | C[j]
        if any(x == (1 << N) - 1 for x in C):
            print(d + 1)
            break
    else:
        print(-1)

Measured memory_bytes: 7684
#include <bits/stdc++.h>
using namespace std;
#define DEBUG 1
#define nl          '\n'
#if     DEBUG
#define trace(var)  {cerr << "Line " << __LINE__ << ": " << #var << "=" << var << nl;}
#else
#define trace(var)	{}
#endif
#define fori(n)			for(int i = 0; i < n; ++i) 
#define forj(n)			for(int j = 0; j < n; ++j)
#define fork(n)			for(int k = 0; k < n; ++k)
#define forl(n)			for(int l = 0; l < n; ++l)

typedef long long ll;typedef pair<int,int> pii;typedef vector<bool> vbool;typedef vector<int> vint;typedef vector<ll> vll;typedef long double ld;typedef vector<vector<int>> vvi;

const ll N = 10010;
const ll INF = 0x3f3f3f3f;
const ll MOD = 1e9 + 7;

int num[2010];

//find number of inversions in array a
ll findInv(int n, vint &a) {
	ll ans = 0;
	for(int i = n-1; i >= 0; --i) {
		for(int j = 0; j < i; j++) {
			if	(a[j] > a[i]) {
				ans = (ans+1)%MOD;
			}	
		}
	}
	return ans;
}


int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n, k; cin >> n >> k;
	vint a(n);
	fori(n) {
		cin >> a[i];
		num[a[i]]++;
	}
	ll inv = findInv(n, a);
	trace(inv);
	inv = (inv*k)%MOD;
	ll sum = 0;
	fori(n) {
		ll c = 0;
		for(int j = a[i]-1; j > 0; --j) c += num[j];
		sum = (sum+c)%MOD;
		trace(c);
	}
	ll mul = (k-1)*k/2; mul %= MOD;
	sum = (sum*mul)%MOD;
	
	cout << (sum + inv)%MOD << nl;
	#if DEBUG
	cerr << "Time: " << (ld)clock() / CLOCKS_PER_SEC << " s" << nl;
	#endif
	return 0;
}


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

using namespace std;

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

	while (true)
	{
		scanf("%d", &N);
		scanf("%d", &M);

		if (N == 0 && M == 0) { break; }

		vector<int> C; C.push_back(0);

		for (int i = 0; i < N; i++)
		{
			scanf("%d", &D);

			if (D <= M)
			{
				C.push_back(D);
			}
		}

		vector<int> r1, r;

		for (int i = 0; i < C.size(); i++)
		{
			for (int j = i; j < C.size(); j++)
			{
				if (C[i] + C[j] <= M)
				{
					r1.push_back(C[i] + C[j]);
				}
			}
		}

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

		r.push_back(r1[0]);

		for (int i = 0; i < r1.size(); i++)
		{
			if (r1[i - 1] != r1[i])
			{
				r.push_back(r1[i]);
			}
		}

		int ret = 0;

		for (int i = 0; i < r.size(); i++)
		{
			int ptr = upper_bound(r.begin(), r.end(), M - r[i]) - r.begin() - 1;
			
			if (ptr >= 0)
			{
				ret = max(ret, r[i] + r[ptr]);
			}
		}

		printf("%d\n", ret);
	}

	return 0;
}

Measured memory_bytes: 8928
A, B = list(map(int, input().split()))

def sum_tap_num(tap_num, A, B):
	tap_sum = (tap_num-1)*(A-1)+A
	if tap_sum >= B:
		return tap_num
  	
	return sum_tap_num(tap_num+1, A, B)
if B==1:
	print(0)
else:
	print(sum_tap_num(1, A, B))



Measured memory_bytes: 61556
#include <bits/stdc++.h>
#define int long long
using namespace std;

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

    long double w,h,x,y;
    cin>>w>>h>>x>>y;
    long double z;
    z=(w*h)/2;
    cout<<fixed<<setprecision(9)<<z<<" ";
    if(w/2==x && h/2==y)
    {
        cout<<1;
    }
    else
        cout<<0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <utility>
#include <map>
#include <list>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>

// #define cerr if(false)cerr
#define watch(x) cerr << "> " << #x << ": " << x << "\n";

using namespace std;

template <typename T>
std::ostream &operator <<(std::ostream &out, vector<T> &v) {
	for (typename vector<T>::size_type i = 0; i < v.size(); ++i)
		out << v[i] << " ";
	out << "\n";
    return out;
}
template <typename T, typename N>
std::ostream &operator <<(std::ostream &out, vector<pair<T, N> > &v) {
	for (size_t i = 0; i < v.size(); ++i)
		out << "(" << v[i].first << ", " << v[i].second << ") ";
	out << "\n";
    return out;
}
template <typename T>
std::ostream &operator <<(std::ostream &out, vector<vector<T> > &v) {
	for (size_t i = 0; i < v.size(); ++i) {
		for (size_t j = 0; j < v[i].size(); ++j) {
			out << v[i][j] << " ";
		}
		out << "\n";
	}
   	return out;
}

int main() {

	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	long long a;
	cin >> a;

	long double b;
	cin >> b;

	b = round(b * 100);

	cout << (long long) (a * b / 100) << "\n";

	return 0;

}

Measured memory_bytes: 3788
#include<bits/stdc++.h>
// Useful constants
#define INF  (int)1e9
#define EPS   1e-9
#define MOD 1000000007ll
#define PI 3.14159
// for input-output
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
// iteration macros: have advantage of auto-casting and not recomputing arguments
#define REP(i, a, b) \
for (int i = int(a); i <= int(b); i++) // a to b, and variable i is local!
#define TRvi(c, it) \
for (vi::iterator it = (c).begin(); it != (c).end(); it++)
#define TRvii(c, it) \
for (vii::iterator it = (c).begin(); it != (c).end(); it++)
#define TRmsi(c, it) \
for (msi::iterator it = (c).begin(); it != (c).end(); it++)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define setBit(S, j) (S |= (1 << j))
#define clearBit(S, j) (S &= ~(1 << j))
#define toggleBit(S, j) (S ^= (1 << j))
// input macro
#define in(x,n)   for(int e=0;e<n;e++){ll y;cin>>y;x.pb(y);}
//output macro
#define print(x)    for(auto it:x) cout<<it<<' '; cout<<endl;
#define printii(x)  for(auto it:x) cout<<it.F<<' '<<it.S<<'\t';  cout<<endl;
// shortcut for data type
#define ll long long
#define vi vector<ll>
#define vvi vector<vi>
#define ii pair<ll,ll>
#define pll pair<ll,ll>
#define vii vector<ii>
#define vvii vector<vii>
#define viii vector<pair<ii,ll>>
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define uset unordered_set
#define umap unordered_map
//--namespace
using namespace std;
//--useful function
ll gcd(ll a, ll b){ll temp;while (b > 0){temp = a%b;a = b;b = temp;} return a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}
// --clock funtion
clock_t time_p=clock();
void TimeTaken()
{
    time_p=clock()-time_p;
    cerr<<"Completion time : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}
// --solve function

// --solve function
void solve() {

}
//--main function



int main(){
    int a,b,c,a2,b2,c2;
    cin>>a>>b>>c;
    if(a==1&&b==1&&c==1)cout<<0<<endl;
    else if(a==b&&c==a)cout<<-1<<endl;
    else{
        int ans=0;
        while(a%2==0&&b%2==0&&c%2==0){
            ans++;
            a2=(b+c)/2;
            b2=(a+c)/2;
            c2=(a+b)/2;
            a=a2;
            b=b2;
            c=c2;
        }
        cout<<ans<<endl;
    }
}




Measured memory_bytes: 256
import java.math.BigInteger;
import java.util.*;

public class Main {
	Scanner sc = new Scanner(System.in);
	void doIt() {
		int n = sc.nextInt();
		for(int i = 0;i < n;i++){
			String a = sc.next();
			String b = sc.next();
			BigInteger numa = new BigInteger(a);
			BigInteger numb = new BigInteger(b);
			BigInteger all = numa.add(numb);
			String allnum = all.toString();
			if(allnum.length() > 80){
				System.out.println("overflow");
			}else{
				System.out.println(all);
			}
		}
     }
    public static void main(String[] args) {
    	// TODO Auto-generated method stub
    	new Main().doIt();
    }
}

Measured memory_bytes: 18440
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
template<typename T>
void print(T x) {
    cout << x << endl;
}
int main(void) {
    int n, m, c; cin >> n >> m >> c;
    vector<int> b(m);
    vector<vector<int>> a(n,vector<int>(m));
    rep(i, m) cin >> b[i];
    int cnt = 0;
    rep(i, n) {
        int sum = 0;
        rep(j, m) {
            cin >> a[i][j];
            sum += a[i][j] * b[j];
        }
        if(sum + c> 0) cnt++;
    }
    cout << cnt;
}


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

class FastReader 
{ 
    BufferedReader br; 
    StringTokenizer st; 
    
    public FastReader() 
    { 
        br = new BufferedReader(new InputStreamReader(System.in)); 
    } 
    
    String next() 
    { 
        while (st == null || !st.hasMoreElements()) 
        { 
            try
            { 
                st = new StringTokenizer(br.readLine()); 
            } 
            catch (IOException  e) 
            { 
                e.printStackTrace(); 
            } 
        } 
        return st.nextToken(); 
    } 
    
    int nextInt() 
    { 
        return Integer.parseInt(next()); 
    } 
    
    long nextLong() 
    { 
        return Long.parseLong(next()); 
    } 
    
    double nextDouble() 
    { 
        return Double.parseDouble(next()); 
    } 
    
    String nextLine() 
    { 
          String str = ""; 
        try
        { 
            str = br.readLine(); 
        } 
        catch (IOException e) 
        { 
            e.printStackTrace(); 
        } 
        return str; 
    } 
} 

class Solution
{
    void solve()
    {
        FastReader s = new FastReader();
        
        String S = s.next();

        Set<Character>hash_set = new HashSet<Character>();

        for(int i = 0; i < S.length(); i++)
        {
            char ch = S.charAt(i);
            hash_set.add(ch);
        }

        if(hash_set.size() != 2)
            System.out.println("No");
        else
            System.out.println("Yes");
    }
}
  
public class Main 
{ 
    public static void main(String[] args) 
    { 
        Solution ob = new Solution();

        ob.solve();
    } 
} 

Measured memory_bytes: 32972
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <iostream>

using namespace std;
typedef long long ll;

void calc(int n,int m){
    int c,a,b,d=-1,dp[151][10][80],ans=1000000000,s,dis;
    vector<pair<int,int> > stone[151];
    
    //scanf("%d%d",&n,&m);
    
    for(int i=0;i<n;i++){
        for(int j=0;j<10;j++){
            for(int k=0;k<=m;k++){
                dp[i][j][k]=1000000000;
            }
        }
    }
    
    for(int j=0;j<10;j++){
        dp[0][j][0]=0;
        dp[1][j][1]=0;
    }
    
    for(int i=0;i<n;i++){
        scanf("%d",&c);
        
        for(int j=0;j<c;j++){
            scanf("%d%d",&a,&b);
            stone[i].push_back(make_pair(a,b));
        }
    }
    
    for(int i=0;i<n-1;i++){
        for(int j=0;j<stone[i].size();j++){
            
            for(int k=0;k<stone[i+1].size();k++){
                for(int l=0;l<=m;l++){
                    s=stone[i][j].second+stone[i+1][k].second;
                    dis=abs(stone[i][j].first-stone[i+1][k].first);
                    dp[i+1][k][l]=min(dp[i+1][k][l],dp[i][j][l]+s*dis);
                }
            }
            for(int k=0;k<stone[i+2].size();k++){
                for(int l=0;l<m;l++){
                    s=stone[i][j].second+stone[i+2][k].second;
                    dis=abs(stone[i][j].first-stone[i+2][k].first);
                    dp[i+2][k][l+1]=min(dp[i+2][k][l+1],dp[i][j][l]+s*dis);
                }
            }
        }
    }
    
    for(int i=0;i<stone[n-1].size();i++){
        for(int j=0;j<=m;j++){
            ans=min(ans,dp[n-1][i][j]);
        }
    }
    
    for(int i=0;i<stone[n-2].size();i++){
        for(int j=0;j<m;j++){
            ans=min(ans,dp[n-2][i][j]);
        }
    }
    
    printf("%d\n",ans);
    
    return;
}

int main(){
    int n,m;
    
    while(1){
        scanf("%d%d",&n,&m);
        if(n==0) break;
        calc(n,m);
    }
    
    return 0;
}

Measured memory_bytes: 1688
import bisect

n = int(input())
xy = [tuple(map(int, input().split())) for i in range(n)]
xy.sort(key=lambda x: x[0] + x[1])
a = xy[0]
xy.sort(key=lambda x: x[0] - x[1])
b = xy[0]
xy.sort(key=lambda x: -x[0] + x[1])
c = xy[0]
xy.sort(key=lambda x: -x[0] - x[1])
d = xy[0]

def man(a:tuple, b:tuple):
    return abs(a[0]-b[0])+abs(a[1]-b[1])

ans = 0
ans = max(ans, man(a, b))
ans = max(ans, man(a, c))
ans = max(ans, man(a, d))
ans = max(ans, man(b, c))
ans = max(ans, man(b, d))
ans = max(ans, man(d, d))
print(ans)

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

using namespace std;
#define MAX 100000
class UnionFind{
  int v[MAX];
  int deep[MAX];
  public:
  UnionFind(){
    for(int i=1;i<MAX;i++){
      v[i]=i;
      deep[i] = 0;
    }
  }

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

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

  void unite(int x,int y){
    x = root(x);
    y = root(y);
    if(deep[x] > deep[y]){
            v[y] = x;
    }else{
      if(deep[x] == deep[y])deep[y]++;
      v[x] = y;
    }
    return;
  }
};

int main(){
  UnionFind uf;
  int n,m,ans=0;
  cin >> n >> m;
  int p[n+1];
  int i;
  for(i=0;i<n;i++)cin >> p[i+1];
  for(i=0;i<m;i++){
    int x,y;
    cin >> x >> y;
    uf.unite(x,y);
  }
  for(i=0;i<n;i++){
    if(uf.same(i+1,p[i+1]))ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1408