akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=1010,INF=1<<30;

vector<pair<int,double>> S[MAX];
vector<double> dis(MAX);
int N;

void dijkstra(int u){
    
    for(int i=0;i<N+2;i++){
        dis[i]=(INF-1)*2;
    }
    dis[u]=0.0;
    priority_queue<pair<double,int>,vector<pair<double,int>>,greater<pair<double,int>>> PQ;
    
    PQ.push(make_pair(0,u));
    while(!PQ.empty()){
        double a=PQ.top().first;
        int b=PQ.top().second;
        PQ.pop();
        if(dis[b]<a) continue;
        for(int i=0;i<S[b].size();i++){
            int c=S[b][i].first;
            double d=S[b][i].second;
            if(dis[c]>dis[b]+d){
                dis[c]=dis[b]+d;
                PQ.push(make_pair(dis[c],c));
            }
        }
    }
    return;
}//a,dが長さ


int main(){
    
    double xs,ys,xt,yt;cin>>xs>>ys>>xt>>yt;
    xs/=2.0;
    ys/=2.0;
    xt/=2.0;
    yt/=2.0;
    cin>>N;
    vector<double> x(N+2),y(N+2),r(N+2);
    for(int i=0;i<N;i++){
        cin>>x[i+1]>>y[i+1]>>r[i+1];
        x[i+1]/=2.0;
        y[i+1]/=2.0;
        r[i+1]/=2.0;
    }
    x[0]=xs;
    y[0]=ys;
    r[0]=0.0;
    x[N+1]=xt;
    y[N+1]=yt;
    r[N+1]=0.0;
    
    for(int i=0;i<N+2;i++){
        for(int j=0;j<N+2;j++){
            double d=max(sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))-(r[i]+r[j]),0.0);
            S[i].push_back(make_pair(j,d));
            S[j].push_back(make_pair(i,d));
            //cout<<d<<endl;
        }
    }
    
    dijkstra(0);
    
    cout<<setprecision(15)<<dis[N+1]*2.0<<endl;
    
    
}


Measured memory_bytes: 38768
#include <algorithm>
#include <array>
#include <complex>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int MAX_V = 100000;
const int INF = 1e9;

struct edge { int to, cost; };
int V;
array<vector<edge>, MAX_V> G;

typedef int Key;
typedef int Val;

vector<Val> dist;

void dijkstra(Key s){
  dist.resize(V);
  typedef pair<Key, Val> P;
  priority_queue<P, vector<P>, greater<P> > que;
  fill(dist.begin(), dist.end(), INF);
  dist[s] = 0;
  que.push(P(0, s));

  while(!que.empty()){
    const auto p = que.top(); que.pop();
    const auto v = p.second;
    if(dist[v] < p.first) continue;
    for(auto e : G[v]){
      if(dist[e.to] > dist[v] + e.cost){
        dist[e.to] = dist[v] + e.cost;
        que.push(P(dist[e.to], e.to));
      }
    }
  }
}

int main() {
  int E, r;
  cin >> V >> E >> r;
  for(int i = 0; i < E; ++i) {
    int s, t, d;
    cin >> s >> t >> d;
    G[s].push_back({t, d});
  }
  dijkstra(r);
  for(auto d : dist){
    if(d == INF){
      cout << "INF" << endl;
    }else{
      cout << d << endl;
    }
  }

}

Measured memory_bytes: 11296
#include<bits/stdc++.h>
using namespace std;
int main(void){
    int n, k;
    cin >> n >> k;
    if(n & 1) n = n / 2 + 1;
    else n /= 2;
    if(n >= k) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
data = []
for x in range(M):
    line = input().split()
    data.append(list(map(int, line[1:])))
turns = list(map(int, input().split()))

def check(i, s, data, turns):
    count_on = 0
    for x in data[i]:
        if s[x - 1] == '1':
            count_on = count_on + 1
    return count_on % 2 == turns[i]

def exec(s, n, data, turns, cases):
    if n == 0:
        ans = True
        for x in range(M):
            if check(x, s, data, turns) == False:
                ans = False
                break
        if ans == True:
            # print(s)
            cases.append(1)
        return
    for i in range(2):
        exec(s + str(i), n - 1, data, turns, cases)

cases = []
exec('', N, data, turns, cases)
print(len(cases))

Measured memory_bytes: 3064
#include<iostream>

using namespace std;

int main() {
    int a,b;

    cin >> a >> b;
    if (a > b) {
        cout << "a > b" << endl;
    }
    else if (a == b) {
        cout << "a == b" << endl;
    }
    else if (a < b) {
        cout << "a < b" << endl;
    }
        
    return 0;
}


Measured memory_bytes: 3080
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1000000007;
const LL INF=100000000000;
string u="abcdefghijklmnopqrstuvwxyz";


int main(){
    int N;
    LL T;
    cin >> N >> T;
    LL t[N];
    for(int i=0;i<N;i++){
        cin >> t[i];
    }
    LL ans=T;
    for(int i=1;i<N;i++){
        if(t[i-1]+T<=t[i]) ans+=T;
        else ans+=t[i]-t[i-1];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define INF 1000000010
#define EPS 1e-9
#define fst first
#define scd second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define lp(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"

vector<int> s[200];
int color[200]={0};
int ans=0;
bool check=true;
queue<pair<int,int>> q;
int nex;

void bfs(){
  while(!q.empty()){
    pair<int,int> p=q.front();
    q.pop();
    int now=p.fst,cnt=p.scd;
    //cout<<now<<" "<<cnt<<endl;
    nex=now;
    rep(i,s[now].size()){
      if(color[now]==1){
	if(color[s[now][i]]==0){
	  color[s[now][i]]=-1;
	  q.push(make_pair(s[now][i],cnt+1));
	  ans=max(ans,cnt+1);
	}else if(color[s[now][i]]==1) check=false;
      }else if(color[now]==-1){
	if(color[s[now][i]]==0){
	  color[s[now][i]]=1;
	  q.push(make_pair(s[now][i],cnt+1));
	  ans=max(ans,cnt+1);
	}else if(color[s[now][i]]==-1) check=false;
      }
    }
  }
}
  



signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  int n;
  cin>>n;
  string mp;
  int cnt=0;
  int mnpn=0,mn=INF;
  rep(i,n){
    cnt=0;
    cin>>mp;
    rep(j,n){
      if(mp[j]=='1'){
	cnt++;
	s[i].push_back(j);
	s[j].push_back(i);
      }
    }
    if(mn>cnt){mn=cnt;mnpn=i;}
  }
  color[mnpn]=1;
  q.push(make_pair(mnpn,1));
  bfs();
  rep(i,200) color[i]=0;
  color[nex]=1;
  q.push(make_pair(nex,1));
  bfs();
  // rep(i,n) cout<<color[i]<<endl;
  if(check) cout<<ans<<endl;
  else cout<<-1<<endl;
  return 0;
}


Measured memory_bytes: 1152
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    s=str(input())
    ans='No'
    for i in range(len(s)-1):
        if s[i:i+2]=='AC':
            ans='Yes'
    print(ans)
    
    
resolve()

Measured memory_bytes: 38256
//Bismillahir Rahmanir Rahim
#include<bits/stdc++.h>
using namespace std;

int main()
{
    /*freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);*/
    string str;
    string str2;
    string str3;
    cin>>str;
    cin>>str2;
    str3=str+str2;
    int ln=str3.size();
    int rem=0,sq,temp;
    for(int i=0;i<ln;i++){
    rem=rem*10+(str3[i]-'0');
    }
    temp=rem;
    sq=sqrt(rem);
    if(sq*sq==temp){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
    

    return 0;
}


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

using namespace std;

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


    map<char, int> cnt;

    long long ans = 1;
    int total = 0;

    for (auto &c : s) {
        ans += total - cnt[c];
        ++cnt[c];
        total += 1;
    }

    cout << ans << endl;

    return 0;
}


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

#define rep(ver,n) rep2(ver,0,n)
#define rep2(ver,m,n) for(int ver=m;ver<(n);ver++)
#define loop while(true)
#define dup(x,y) (((x)+(y)-1)/(y))
#define all(v) (v).begin(), (v).end()
#define debug(x) std::cerr<<#x<<": "<<x<<"\n"
#define debug2(x,y) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<"\n"
#define debug3(x,y,z) std::cerr<<#x<<": "<<x<<", "<<#y<<": "<<y<<", "<<#z<<": "<<z<<"\n"

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

int h,w;
int ch,cw,dh,dw;
char m[2000][2000]={};
int go[2000][2000]={};
const int NOT_REACH=1<<30;

int sets[]={-2,-1,0,1,2};

int main(){
  scanf("%d %d\n%d %d\n%d %d",&h,&w,&ch,&cw,&dh,&dw);
  ch--;cw--;dh--;dw--;
  rep(i,h){
    scanf("%s",m[i]);
    rep(j,w){
      go[i][j]=NOT_REACH;
    }
  }
  
  queue<tuple<int,int,int>> q[2];
  q[0].push(make_tuple(ch,cw,0));
  go[ch][cw]=0;
  while(!q[0].empty()){
  while(!q[0].empty()){
    auto now=q[0].front();q[0].pop();
    int nh=get<0>(now),nw=get<1>(now),c=get<2>(now);
    rep(i,5){
      rep(j,5){
        if(sets[i]==0&&sets[j]==0)continue;
        int nxh=nh+sets[i],nxw=nw+sets[j];
        nxh=max(0,nxh);
        nxw=max(0,nxw);
        nxh=min(h-1,nxh);
        nxw=min(w-1,nxw);
        if(m[nxh][nxw]=='#')continue;
        if(abs(sets[i])+abs(sets[j])==1){
          if(go[nxh][nxw]<=c)continue;
          go[nxh][nxw]=c;
          q[0].push(make_tuple(nxh,nxw,c));
        }
        else{
          if(go[nxh][nxw]<=c+1)continue;
          go[nxh][nxw]=c+1;
          q[1].push(make_tuple(nxh,nxw,c));
        }
      }
    }
  }
  while(!q[1].empty()){
    auto now=q[1].front();q[1].pop();
    int nh=get<0>(now),nw=get<1>(now),c=get<2>(now);
    if(go[nh][nw]<=c){}
    else{
      q[0].push(make_tuple(nh,nw,c+1));
    }
  }
  }
  
  
  if(go[dh][dw]==NOT_REACH){
    cout<<-1;
  }
  else{
    cout<<go[dh][dw];
  }
  
  /*
  rep(i,h){
    rep(j,w){
      cerr<<go[i][j]<<", ";
    }
    cerr<<endl;
  }
  */
  
  return 0;
}


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

ll find(const vector<ll>& b, int s) {
	ll res = 0;
	for (int i = s; i > 0; i = i & (i - 1))
		res = max(res, b[i]);
	return res;
}

void add(vector<ll>& b, int s, ll val) {
	int n = b.size();
	for (int i = s; i < n; i += (i & -i))
		b[i] = max(b[i], val);
}

int main()
{
	cin.sync_with_stdio(false);
	int n;
	cin >> n;
	ll sum = 0;
	vector<ll> bit(n + 1);
	for (int i = 0, x; i < n; i++) {
		cin >> x; sum += x;
		add(bit, x, find(bit, x - 1) + x);
	}
	printf("%lld\n", sum - find(bit, n));
	return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;

vector<int> v,sorted;
void solve() {
    int n; cin >> n;
    v.resize(n); sorted.resize(n);

    // value, sorted index
    map<int,int> mp;

    REP(i,n) {
        cin >> v[i];
        sorted[i] = v[i];
    }

    sort(ALL(sorted));
    REP(i,n) mp[sorted[i]] = i;

    // find cycle
    vector<int> used(n);

    ll cost = 0;
    REP(i,n) {
        if(used[i]) continue;
        int target = v[i];
        used[mp[v[i]]] = true;
        int seeing = v[mp[v[i]]];
        int cycle = 1;
        int minimum_element = target;
        int sm = target;
        while (target != seeing) {
            cycle++;
            used[mp[seeing]] = true;
            sm+=seeing;
            chmin(minimum_element,seeing);
            seeing = v[mp[seeing]];
        }

        if(cycle == 1) continue;
        cost += min(sm + (cycle-2) * minimum_element, sm + minimum_element+ (cycle+1) * sorted[0]);
    }
    cout << cost << endl;


}

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


Measured memory_bytes: 3232
N = int(input())
a = list(map(int, input().split()))
dp = [[[0,0] for j in range(N)] for i in range(N)]
for i in range(N):
    dp[i][i] = [a[i],0]
for i in range(1,N):
    for j in range(N-i):
        Num = 0
        Num2 = 10**13
        for k in range(j, j+i):
            num2 = dp[j][k][1]+dp[k+1][j+i][1]+dp[j][k][0]+dp[k+1][j+i][0]
            if Num2 > num2:
                Num2 = num2
                Num = dp[j][k][0]+dp[k+1][j+i][0]
        dp[j][j+i] = [Num, Num2]
print(dp[0][N-1][1])

Measured memory_bytes: 62172
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
using ll=long long;
using P=pair<ll,ll>;
using PP=tuple<ll,ll,ll>;
using S=multiset<ll>;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
ll modpow(ll a,ll b){a%=mod;if(b==0)return 1;if(b&1)return a*modpow(a,b-1)%mod;ll k=modpow(a,b/2);return k*k%mod;}
void decimal(int x){cout<<fixed<<setprecision(x);}
vi calc(ll x){vi res;while(x>0){res.eb(x%10);x/=10;}reverse(all(res));return res;}

void solve() {
  int n;
  cin>>n;
  vi a=calc(n);
  bool f=false;
  rep(i,3) if(a[i]==7) f=true;
  YesNo(f);
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n , sum , res , a[100001];
main(){
    cin >> n; 
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i ++){
        if(sum * 2 >= a[i]){
            res ++;
        }
        else{
            res = 0; 
        }
        sum += a[i];
    }
    cout << ++res << "\n";
}

Measured memory_bytes: 1024
s = input()
t = input()
match_s = 0
for i in range(len(s) - len(t) + 1):
    tmp_match_s = 0
    for j in range(len(t)):
        if s[i + j] == t[j]:
            tmp_match_s += 1
    match_s = max(match_s, tmp_match_s)
print(len(t)- match_s)

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

int main()
{
	int n,sum = 0,max = 0;
	cin >> n;
	for(int i = 0,temp;i < n;i ++)
	{
		cin >> temp;
		sum += temp;
		max = max > temp ? max : temp;
	}
	if(sum > 2 * max)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ld long double
#define INF 1000000000000000000
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;

struct mat {
    int row = -1;
    int col = -1;
};

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

    int N;
    cin >> N;
    vector<mat> M(N);
    rep(i, N) {
        int a, b;
        cin >> a >> b;
        M[i].row = a, M[i].col = b;
    }

    vector<vector<ll>> dp(N + 5, vector<ll>(N + 5, INF));
    rep(i, N + 5) { dp[i][i] = 0; }

    for (int w = 1; w < N; w++) {
        for (int i = 0; i < N; i++) {
            if (i + w >= N)
                continue;
            int j = i + w;
            for (int k = i; k < j; k++) {
                ll num_pro = M[i].row * M[k].col * M[j].col;
                dp[i][i + w] =
                    min(dp[i][i + w], dp[i][k] + dp[k + 1][i + w] + num_pro);
            }
        }
    }

    cout << dp[0][N - 1] << endl;
}


Measured memory_bytes: 3212
#include <stdio.h>

int main(void)
{
	int a,b;
	scanf("%d%d",&a,&b);
	if((a+b)%2==0)
		{
		int x=(a+b)/2;
		printf("%d\n",x);
		}
	else
		{
		int x=(a+b+1)/2;
		printf("%d",x);
		}
	return 0;
}


Measured memory_bytes: 128
require "set"

s = gets.to_s.chomp.bytes
x, y = gets.to_s.split.map{|t| t.to_i }

# p "FT".bytes # => [70, 84]
state = 0
yoko = []
tate = []
tmp = 0
s.each do |c|
  
  if c == 70
    tmp += 1
  else
    if state == 0
      yoko << tmp
    else
      tate << tmp
    end
    tmp = 0
    state = 1 - state
  end
end

if state == 0
  yoko << tmp
else
  tate << tmp
end

sx = sy = 0
if s[0] == 70
  sx = yoko.shift
end

yoko.sort!
tate.sort!

hx = { sx => true }
set_x = Set[sx]
yoko.each do |d|
  t = Set[]
  set_x.each do |k, v|
    t << k+d 
    t << k-d 
  end
  set_x = t
end

hy = { sy => true }
set_y = Set[sy]
tate.each do |d|
  t = Set[]
  set_y.each do |k, v|
    t << k+d 
    t << k-d
  end
  set_y = t
end

puts ( set_x.include?(x) && set_y.include?(y) ) ? "Yes" : "No"


Measured memory_bytes: 73080
using System;

namespace ConsoleApp8
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int a = int.Parse(input[0]);
            int b = int.Parse(input[1]);
            if (a < b) Console.WriteLine("a < b");
            else if (a > b) Console.WriteLine("a > b");
            else if (a == b) Console.WriteLine("a == b");
        }
    }
}



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

struct st{int a,b,c;}s[200000];
ll sumx[200000],sumy[200000];

int main(){
	int x,y,z;cin>>x>>y>>z;
	int n=x+y+z;
	rep(i,n){
		scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].c);
	}
	sort(s,s+n,[](st a,st b){
		return a.a-a.b>b.a-b.b;
	});
	ll sum=0;
	priority_queue<int>que;
	for(int i=0;i<n;i++){
		que.push(s[i].c-s[i].a);
		sum+=s[i].c-s[i].a;
		if(que.size()>x)sum-=que.top(),que.pop();
		sumx[i]=sum;
	}
	sum=0;
	while(!que.empty())que.pop();
	for(int i=n-1;i>=0;i--){
		que.push(s[i].c-s[i].b);
		sum+=s[i].c-s[i].b;
		if(que.size()>y)sum-=que.top(),que.pop();
		sumy[i]=sum;
	}
	ll ans=LLONG_MIN;
	for(int i=x-1;i<n-y;i++){
		ans=max(ans,-(sumx[i]+sumy[i+1]));
	}
	rep(i,n)ans+=s[i].c;
	cout<<ans<<endl;
}

Measured memory_bytes: 4216
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <cmath>
#define int long long
using namespace std;

#define fi first
#define se second

const long long MOD = 998244353;
long long a, b;

signed main()
{
    cin >> a >> b;
    if (a * b * 3 % 2 == 0)
    {
        cout << "No";
    }
    else
    {
        cout << "Yes";
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	int pn = 1;
	if (ci - cn + 16 > cm) {
		if ((ct = getcha()) == '-') { pn = -1; ct = getcha(); }
		A = ct - '0';
		while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';;
		return pn * A;
	}
	else {
		if ((ct = *ci++) == '-') { pn = -1; ct = *ci++; }
		A = ct - '0';
		while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';;
		return pn * A;
	}
}

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


	int N = getint(), M = getint();
	bool X[200010] = {};
	rep(i, M) X[getint() + 100000] = true;

	int mae = -1;
	int sa[200010] = {};
	rep(i, 200001) {
		if (X[i]) {
			if (mae != -1) {
				sa[i - mae]++;
			}
			mae = i;
		}
	}

	int kotae = 0;
	rep(i, 200001) {
		if (M <= N) break;
		int k = min(M - N, sa[i]);
		kotae += i * k;
		M -= k;
	}

	co(kotae);

	Would you please return 0;
}

Measured memory_bytes: 1408
#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#include<cmath>
#include<iomanip>
#include<map>
using namespace std;
typedef long long ll;
/*
struct node{
	ll x, y;

}r[1234567],w;
map<ll, ll>ma;
ll main() {
	ll n;
	cin >> n;
	for (ll i = 0; i < n; i++) {
		cin >> r[i].x >> r[i].y;
	}
	ll x, y, ans = 0;
	for (ll i = 0; i < n; i++) {
		w.x = r[i].x; w.y = r[i].y;
		queue<node> q;
		q.push(w);
		for (ll j = 0; j < n; j++) {
			if (j == i) continue;
			while (!q.empty()) {
				w = q.front(); q.pop();
				ll nx = w.x + r[j].x;
				ll ny = w.y + r[j].y;
				if (nx * nx + ny * ny > w.x * w.x + w.y * w.y) {
					w.x = nx; w.y = ny; q.push(w);
				}
				if (nx * nx + ny * ny == w.x * w.x + w.y * w.y) {
					q.push(w);
					w.x = nx; w.y = ny; q.push(w);
				}
			}
			ans = max(ans, w.x * w.x + w.y * w.y);
		}
		
	}
	cout << fixed << setprecision(30) << ((long double)sqrt(ans)) << '\n';
	return 0;
}

*/


int main() {
	ll a[12345];
	ll n, k,m = 1e9+7;
	cin >> n >> k;
	for (ll i = 0; i < n; i++) cin >> a[i];
	ll cnt = 0;
	for (ll i = 0; i < n; i++) {
		for (ll j = i+1; j < n; j++) {
			if (a[i] > a[j]) cnt++;
		}
	}
	ll cnt2 = 0;
	for (ll i = 0; i < n; i++) {
		for (ll j = 0; j < n; j++) {
			if (a[i] > a[j]) cnt2++;
		}
	}
	ll g = (k-1) * k / 2 % m;
	cout << (cnt2 * g + cnt*k) % m << '\n';

}

Measured memory_bytes: 256
import Control.Monad

ok' bit s p = (length $ [] ++ [ ()| si <- s, bit !! (si-1) ]) `mod` 2 == p
ok bit s p m = (length $ [] ++ [ ()| i <- [0..m - 1], ok' bit (s !! i) (p !! i)]) == m
main = do
    [n, m] <- fmap (map read . words) getLine
    s <- replicateM m $ fmap (tail . map read . words) getLine
    p <- fmap(map read . words) getLine
    let bit = sequence $ replicate n [False, True]
    print.length $ [ () | b <- bit, ok b s p m ]

Measured memory_bytes: 4300
using System;

public class ABC152A {
  public static void Main(string[] args) {
    var str1 = Console.ReadLine();
    var n = int.Parse(str1);
    var str2 = Console.ReadLine().Split();
    var b = new int[n];
    var count = 0;
    
    for (var i = 0; i < n; i++) {
      b[i] = int.Parse(str2[i]);
    }
    var min = b[0];
    for (var i = 0; i < n; i++) {
      if (b[i] <= min) {
        min = b[i];
        count++;
      }
    }
    /*
    for (var i = 0; i < n; i++) {
      b[i] = int.Parse(str2[i]);
      var min = b[i];
      if (i >= 1) {
        for (var j = 0; j < i; j++) {
          if (b[j] < min) {
            min = b[j];
            break;
          }
        }
      }
      if (min == b[i]) {
        count++;
      }
    }
    */
    
    Console.WriteLine(count);
  }
}

Measured memory_bytes: 33116
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;

int main()
{
    string str;
    getline(cin,str);
    for(int i=0;i<str.length();i++){
        if(str[i]>='a'&&str[i]<='z'){
            str[i]=(char)((int)str[i]-32);
        }
    }
    cout<<str<<endl;
    return 0;
}

Measured memory_bytes: 1172
#include <iostream>
using namespace std;
#include<stdlib.h>
#include<stdio.h>
  
int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    if(a==b && a!=c){
        cout<<"Yes\n";
    }
    else if(a==c && a!=b){
        cout<<"Yes\n";
    }
    else if(c==b && b!=a){
        cout<<"Yes\n";
    }
    else{
        cout<<"No\n";
    }
    return 0;
}



Measured memory_bytes: 256
#if 1
	#include <stdio.h>
	#include <set>
	#include <map>
	#include <unordered_map>
	#include <unordered_set>
	#include <list>
	#include <queue>
	#include <stack>
	#include <cmath>
	#include <ctime>
	#include <cstdio>
	#include <vector>
	#include <string>
	#include <bitset>
	#include <cctype>
	#include <cstdlib>
	#include <cstring>
	#include <utility>
	#include <numeric>
	#include <complex>
	#include <sstream>
	#include <fstream>
	#include <iomanip>
	#include <cassert>
	#include <iostream>
	#include <iterator>
	#include <algorithm>
	#include <functional>
#else
	#include <bits/stdc++.h>
#endif

using namespace std;

typedef long long LL;
typedef unsigned int UI;
typedef long double LD;

const LL MOD = (LL)1000000007;
const LL LL_INF = (LL)1 << 62;
const int INT_INF = (int)1 << 30;

#define rSort(a) 		sort(a.rbegin(),a.rend())
#define Sort(a) 		sort(a.begin(),a.end())
#define Reverse(a) 		reverse(a.begin(),a.end())
#define Sum(a)  		accumulate(a.begin(), a.end(), 0)
#define REP(i, n) 		for(UI i = 0;i < n;i++)
#define REPR(i, n) 		for(UI i = n;i >= 0;i--)
#define FOR(i, m, n) 	for(UI i = m;i < n;i++)
#define pb(i) 			push_back(i)
#define SWAP(x,y) 		((x!=y)&&(x^=y,y^=x,x^=y))



int main(int argc, char* argv[]) {

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

	LL N,M;
	LL ans = 0;
	string s;
	map<string,LL> mp={};

	cin >> N;
	REP(i, N) {
		cin >> s;
		mp[s]++;
	}

	cin >> M;
	REP(i, M) {
		cin >> s;
		mp[s]--;
	}


	for(const auto& wrk:mp){
#if 0
		cout << wrk.first << ":" << wrk.second <<endl;
#endif
		if (wrk.second > ans) ans = wrk.second;
	}

	cout << ans <<endl;

	return 0;
}

Measured memory_bytes: 256
def resolve():
    n, y = map(int, input().split())

    for a in range(n + 1):
        for b in range(n + 1 - a):
            c = n - a - b
            if a * 10000 + b * 5000 + c * 1000 == y:
                print(*[a, b, c])
                return
    print("-1 -1 -1")
    
resolve()

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

using namespace std;
using ll = long long;

int main() {
  int N, K;
  cin >> N >> K;
  vector<ll> s(N + 1, 0);
  for (int i = 0; i < N; i++) {
    int a;
    cin >> a;
    s[i + 1] += s[i] + a;
  }
  
  int B = 0;
  for (ll b = s[N]; b > 0; b >>= 1) ++B;

  vector<ll> ss;
  for (int l = 0; l < N; l++) {
    for (int r = l + 1; r < N + 1; r++) {
      ss.push_back(s[r] - s[l]);
    }
  }
  sort(begin(ss), end(ss), greater<ll>());
  
  ll ans = 0;
  for (int i = B - 1; i >= 0; i--) {
    int cnt = 0;
    ll tmp = ans | (1LL << i);
    for (int j = 0; j < N * (N + 1) / 2; j++) {
      if ((tmp & ss[j]) == tmp) ++cnt;
    }
    if (cnt >= K) {
      ans = tmp;
    }
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std ;
typedef long long ll;
typedef string str;
typedef pair<int, int> pii;
typedef vector<int> vint;
typedef vector<double> vdou ;
typedef vector<ll> vll;
typedef vector<vint> vvint;
typedef vector<str> vstr;
typedef pair<ll,ll> pll ;
typedef vector<pii> vpii ;
typedef vector<pll> vpll ;

#define REP(i, n) for (ll (i) = 0; (i) < (ll)(n); i++) 
#define FOR(i, a, b) for(ll (i) = a; (i) < (ll)b; i++)
#define ALL(v) (v).begin(),(v).end()
#define MOD 1000000007
#define CHI 1000000000000000003
#define NIL -1
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define NP next_permutation
#define SZ(x)  (ll)x.size()
#define SP(x)  setprecision((ll)x)

const int INF = 1e9;
const ll LINF = 1e18;
const double EPS = 1e-9;
const double PI = M_PI;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} //最大公約数
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} //最小公倍数

void yes(){
  cout <<"Yes"<<endl ;
}
void no(){
  cout <<"No"<<endl ;
}
//-----------------------------------------

const int MAX_V = 1e6;

struct edge{
  int to ; 
  ll cost ;
  //iからの行き先とそのコストの情報
};

int n ;
vector<edge> G[MAX_V] ;
//G[i]...iからの行き先(to)とコスト(cost)の情報を持つ
int d[MAX_V] ;
//d[i]...sからiへ行くのにかかるコストの最小

vector<int> par ;
//par[i]...iの一個前


void dijkstra(int s){
  priority_queue<pii, vector<pii>, greater<pii>> que;
  //pair<sからiへ行くのの暫定最小コスト、i>の優先度付きキュー
  REP(i,n){
    d[i] = INF ;
    par.PB(i) ;
    //はじめコストはINFとして初期化
  }
  d[s] = 0 ;
  que.push(MP(0,s)) ;
  //自身へのコストは0としてqueへ入れる
  
  while(!que.empty()){
    pii p = que.top() ;
    que.pop() ;
    int v = p.SE ;
    //queが空になるまで取り出す
    if(d[v]<p.FI){
      //すでにそれ以下があれば見る必要はない
      continue ;
    }
    REP(i,SZ(G[v])){
      //vを経由した行き先について
      edge e = G[v][i] ;
      if(d[e.to]>d[v]+e.cost){
        //vを経由した方がコストが小さいなら更新し、queに入れる
        d[e.to] = d[v]+e.cost ;
        par[e.to] =  v ;
        que.push(MP(d[e.to],e.to)) ;
      }
    }
  }
}

//頂点tへの最短路
vector<int> get_path(int t){
    vector<int> path;
    int i = t ;
    while(i!=par[i]){
      path.PB(i) ;
      i = par[i] ;
    }
    reverse(ALL(path)) ;
    return path ;
}


















//-----------------------------------------
int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n ;
  int x, y ;
  cin >> x >> y ;
  edge k = {y-1,1} ;
  G[x-1].PB(k) ;
  edge l = {x-1,1} ;
  G[y-1].PB(l) ;
  REP(i,n-1){
    edge e = {i+1,1} ;
    G[i].PB(e) ;
    edge f = {i,1} ;
    G[i+1].PB(f) ;
  }
  
  vvint vec(n,vint(n)) ;
  
  REP(i,n){
    dijkstra(i) ;
    REP(j,n){
      vec[i][j] = d[j] ;
    }
  }
  
  vint cnt(n,0) ;
  
  REP(i,n){
    REP(j,n){
      cnt[vec[i][j]]++ ;
    }
  }
  
  FOR(i,1,n){
    cout << cnt[i]/2 <<endl; 
  }
  
  
  
  return 0 ;
}




Measured memory_bytes: 59624
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
int main(){
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	rep(i, n) cin >> a[i];
	sort(a.begin(), a.end());
	int ans = 0;
	rep(i, k) ans += a[i];
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3576
a, b, x = gets.chomp.split(" ").map(&:to_i)

if x == a**2 * b
    puts 0
elsif ((2 * x).quo(a**2)) >= b # 台形
    rad = Math.atan2(a**3, (2 * a**2 * b) - (2 * x))
    puts 90 - (rad * 180) / Math::PI

else #三角形
    rad = Math.atan2((2 * x), (a * b**2))
    puts 90 - (rad * 180) / Math::PI
end

Measured memory_bytes: 1788
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {

    private void solveX(BufferedReader sc) throws IOException {
        String line = sc.readLine();
        print(line);
    }

    private void print(String elem) {
        String[] line = elem.split(" ");
        long a = Long.parseLong(line[0]);
        long b = Long.parseLong(line[1]);
        long x = Long.parseLong(line[2]);

        long all = b / x;
        long outer = a / x;
        System.out.println(all - outer + (a % x == 0 ? 1 : 0));
    }

    private void solveA(Scanner sc) {
        int n = sc.nextInt();
        String s = sc.next();
        String t = sc.next();

        int min = 0;
        for (int i = 1; i <= n; i++) {
            String check = t.substring(0, i);
            if (s.endsWith(check)) {
                min = i;
            }
        }
        System.out.println(n * 2 - min);
    }

    private void solveB(BufferedReader sc) throws IOException {
        String[] line = sc.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int x = Integer.parseInt(line[1]);

        if (x == 1 || x == 2 * n - 1) {
            System.out.println("No");
            return;
        }

        if (n == x) {
            for (int i = 1; i <= 2 * n - 1; i++) {
                System.out.println(i);
            }
            return;
        }

        boolean underHarf = x < n;
        for (int i = 0; i < (underHarf ? n : n - 1); i++) {
            if (n - i == x) {
                continue;
            }
            System.out.println(n - i);
        }

        System.out.println(x);

        if (!underHarf) {
        }

        for (int i = 0; i < n - 1; i++) {
            if (2 * n - i - 1 == x) {
                continue;
            }
            System.out.println(2 * n - i - 1);
        }

        System.out.println(1);
    }

    private void solveC(Scanner sc) {
        int n = sc.nextInt();
        int[] pos = new int[n];
        for (int i = 0; i < n; i++) {
            pos[i] = sc.nextInt();
        }
        int m = sc.nextInt();
        long k = sc.nextLong();

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // try (Scanner sc = new Scanner(System.in)) {
        Main app = new Main();
        // app.solveA(sc);
         app.solveX(br);
//        app.print("4 8 2");
//        app.print("1 1 1");
//        app.print("9 9 3");
//        app.print("1 1000000000000000000 3");
        // app.solveC(sc);
        // }
    }
}


Measured memory_bytes: 8276
S = []
cou = []
ans = 0
x = str(input())

for i in x:
    S.append(i)

for i in range(len(S) - 2):
    cou.append(abs(753 - (int(S[0 + i]) * 100 + int(S[1 + i]) * 10 + int(S[2 + i]))))
else:
    print(min(cou))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(a);i>(b);--i)
#define eper(i,a,b) for(int i=(a);i>=b;--i)
#define pb push_back
#define mp make_pair
#define INF 100100100100
#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
#define vii vector<int>
#define vll vector<long long>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
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; }
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

int n, m;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
    int X, Y;
    cin >> n >> m >> X >> Y;
    vii xp(n), yp(m);
    rep(i, 0, n) cin >> xp[i];
    rep(i, 0, m) cin >> yp[i];
    erep(z, X+1, Y) {
        bool flag = true;
        rep(j, 0, n) {
            if (xp[j] >= z) flag = false;
        }
        rep(j, 0, m) {
            if (yp[j] < z) flag = false;;
        }
        if (flag) {
            cout << "No War" << endl;
            return 0;
        }
    }
    cout << "War" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm(c++17)
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//イテレータあるけど順序保持しないmap
#include<unordered_set>//イテレータあるけど順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列
using namespace std;

typedef long long ll;

//マクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 1000000007 //10^9+7
#define MAXR 100000 //10^5:最大のrange(素数列挙などで使用)

int main(void){
    ll x, a;
    //string s;
    cin >> x;
    a = 100;
    ll i = 0;
    while(a < x) {
        a = floor((double)a*1.01);
        i++;
    }
    
    cout << i << endl;
    return 0;
}

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

int main(){
	long double n,k;
	cin>>n>>k;
	long double prob = (long double) 1/n;
	long double ans = 0.0;
	long double power;
	long double limits = n>k? k:n;
	
	for(long double i = 1;i<=limits;i++){
			
		  power = pow(0.5,ceil(log2(k/i)));
		  ans += power;
		 // printf("%.12Lf\n",power);
	}
//	printf("%.12Lf\n",ans);
	if(n-k>0.0){
		ans+= (n-k);
	}
//	printf("%.12Lf",ans);
	
	//printf("%.12Lf",prob);
	printf("%.12Lf",prob*ans);
	return 0;
}


Measured memory_bytes: 512
from collections import defaultdict
S=input()
T=input()
d=defaultdict(list)
e=defaultdict(list)
for i in range(len(S)):
  d[S[i]].append(i)
  e[T[i]].append(i)
print("Yes" if all(item in e.values() for item in d.values()) else "No")

Measured memory_bytes: 14768
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<time.h>
#include<tuple>
#include<set>
#include<map>
#include<cctype>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define vint vector<int> 
#define vvint vector<vint>
#define ct(a) cout<<a<<endl
#define tget(a,b) get<a>(b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;
const int MOD = 1e9 + 7;

ll N,ans;
int main(void) {
	cin >> N;
	FOR(i, 0, 4) {
		if (N % 10 == 2)ans++;
		N /= 10;
	}
	ct(ans);
	return 0;
}

Measured memory_bytes: 256
import sys
from math import factorial
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

k, n = MAP()
a = LIST()
dis = [a[i+1]-a[i] for i in range(n-1)]
dis.append(k-a[n-1]+a[0])

print(sum(dis)-max(dis))

Measured memory_bytes: 109552
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int main() {
    int x,y;
    cin>>x>>y;
    if(1LL*x*y<0) cout<<abs(abs(x)-abs(y))+1;
    else if(x<=y) cout<<y-x;
    else if(x&&y) cout<<x-y+2;
    else cout<<x-y+1;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using Vec  =vector<int>;

int		main(void)
{
	int a, b;
	cin >> a >> b;

	if (a != 1 && b != 1)
		cout << 1 << endl;
	else if (a != 2 && b != 2)
		cout << 2 << endl;
	else
		cout << 3 << endl;
}


Measured memory_bytes: 256
N, K = map(int, input().split())
start = sum(range(K))
end = sum(range(N-K+1, N+1))
count = 0
#print(start, end)
for k in range(K, N + 2):
    count += end - start + 1
    count %= 1000000007
    start += k
    end += (N-k)
    
print(count)

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

const int N = 1111111;

char s[N];
int w;

int main(void) {
	scanf("%s", s);
	cin >> w;
	int now = strlen(s) - 1;
	for(int i = 0; i <= now; i += w) cout << s[i];
	
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      	int a = sc.nextInt();
    	int b = sc.nextInt();
	    int c = sc.nextInt();
      
      	if(a+b >= c) System.out.println("Yes");
      	else System.out.println("No");
    }
}

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

int m, n;
int blue[505];
int red[505];

bool bluematch[505];
int redpair[505];

int path[505][505];

int gcd(int a, int b)
{
    int m;
    
    while(1){
        m = a%b;
        if(m==0)
            return b;
        a = b;
        b = m;
    }
    return 1;
}

bool match(int x){
    if(x<0) return true;
    
    if(bluematch[x]){
        return false;
    }
    bluematch[x]=true;
    
    for(int y=0; y<n; y++){
        if(!path[x][y]) continue;
        if(match(redpair[y])){
            redpair[y]=x;
            return true;
        }
    }
    
    return false;
}

int main() {
    ios_base::sync_with_stdio(0);
    
    int i, j, cnt;
    while(1){
        cin >> m >> n;
        if(m==0)
            return 0;
        
        for(i=0;i<m;i++){
            cin >> blue[i];
        }
        
        for(i=0;i<n;i++){
            cin >> red[i];
        }
        
        for(i=0; i<m; i++){
            for(j=0; j<n; j++){
                if(gcd(blue[i],red[j])!=1){
                    path[i][j]=1;
                }
                else{
                    path[i][j]=0;
                }
            }
        }
        
        fill(redpair, redpair+n, -1);
        cnt=0;
        for(i=0; i<m; i++){
            fill(bluematch, bluematch+m, 0);
            if(match(i)){
                cnt++;
            }
        }
        cout << cnt << endl;
    }
    
    return 0;
}

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

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

void main()
{
    long N = lread();
    long[long][long] V; // V[min(u,v)][max(u,v)] = w
    auto T = new long[][](N);
    foreach (_; 0 .. N - 1)
    {
        long u, v, w;
        scan(u, v, w);
        u--;
        v--;
        T[u] ~= v;
        T[v] ~= u;
        V[min(u, v)][max(u, v)] = w;
    }
    auto ans = new long[](N);
    ans[] = -1;

    PQueue!(Tuple!(long, long), "b<a") Q;
    Q.insert(Tuple!(long, long)(0, 0)); // dist, id
    while (!Q.empty)
    {
        auto u = Q.front;
        Q.removeFront();

        ans[u[1]] = u[0] & 1;

        foreach (v; T[u[1]])
        {
            if (ans[v] == -1)
            {
                Q.insert(Tuple!(long, long)(u[0] + V[min(u[1], v)][max(u[1], v)], v));
            }
        }
    }
    ans.map!(text).join('\n').writeln();
}


Measured memory_bytes: 33660
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.NoSuchElementException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
*/public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FasterScanner in = new FasterScanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskC solver = new TaskC();
		solver.solve(1, in, out);
		out.close();
	}
static class TaskC   {
public void solve(int testNumber, FasterScanner in, PrintWriter out) {
        final int n = in.nextInt();
        long ans = 0;
        for(int i = 0; i < n; i++){
            long count = 0;
            int a = in.nextInt();
            while(a % 2 == 0){
                a /= 2;
                count++;
            }
            ans += count;
        }
        out.println(ans);
    }

}
static class FasterScanner   {
private InputStream in;
private byte[] buffer;
private int bufPointer;
private int bufLength;

public FasterScanner(InputStream in) {
        this.in = in;
        buffer = new byte[1024];
    }

private boolean hasNextByte() {
        if (bufPointer < bufLength) return true;
        bufPointer = 0;
        try {
            bufLength = in.read(buffer);
        } catch (IOException e){
            e.printStackTrace();
        }
        return (bufLength > 0);
    }

private int readByte() {
        if(hasNextByte()) return buffer[bufPointer++];
        return -1;
    }

private static boolean isPrintableChar(int c) {
        return (c >= 33 && c <= 126);
    }

public boolean hasNext() {
        while(hasNextByte() && !isPrintableChar(buffer[bufPointer])) bufPointer++;
        return hasNextByte();
    }

public int nextInt() {
        long nl = nextLong();
        if(nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }

public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-'){
            minus = true;
            b = readByte();
        }
        if (b < '0' || b > '9') throw new NumberFormatException();

        while(true){
            if (b >= '0' && b <= '9'){
                n *= 10;
                n += b - '0';
            }else if (b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

}
}



Measured memory_bytes: 22356
import sys

s = input()
s_list = set(list(s))

if (len(s_list) != 2):
    print('No')
    sys.exit()

is_ok = True
for char in set(list(s)):
    if (s.count(char) != 2):
        is_ok = False

if is_ok:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3060
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <vector>
#include <tuple>
#include <map>
#include <iomanip>
#include <string>
#include <queue>

using namespace std;

typedef long long ll;
typedef long double ld;

#define int ll
#define double ld
#define loop(i, n) for (int i = 0; i < (int)n; ++i)
#define loop1(i, n) for (int i = 1; i <= (int)n; ++i)
#define pb push_back
#define pi pair<double, double>
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define ti tuple<int, int, int, int>
#define mkt make_tuple
#define mkp make_pair
#define cerr if (1) cerr

map <int, double> ans;

void calc(int n, int a, int b, int c, int d) {
    if (ans.find(n) != ans.end())
        return;
    ans[n] = (ld)n * d;

    calc(n / 2, a, b, c, d);
    calc((n + 1) / 2, a, b, c, d);
    ans[n] = min({ ans[n], ans[n / 2] + a + n % 2 * d, ans[(n + 1) / 2] + a + (2 - n % 2) * d });

    calc(n / 3, a, b, c, d);
    calc((n + 2) / 3, a, b, c, d);
    ans[n] = min({ ans[n], ans[n / 3] + b + n % 3 * d, ans[(n + 2) / 3] + b + (3 - n % 3) * d });

    calc(n / 5, a, b, c, d);
    calc((n + 4) / 5, a, b, c, d);
    ans[n] = min({ ans[n], ans[n / 5] + c + n % 5 * d, ans[(n + 4) / 5] + c + (5 - n % 5) * d });
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t; cin >> t; 
    loop(i, t) {
        ans[0] = 0;
        int n, a, b, c, d;
        cin >> n >> a >> b >> c >> d;
        calc(n, a, b, c, d);
        cout << (ll)ans[n] << "\n";
        ans.clear();
    }
    return 0;
}

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

#define PrintLn(X) cout << X << endl
#define Rep(i, n) for(int i = 0; i < (int)(n); ++i)

int main(void)
{
	char a, b;
	cin >> a >> b;
	PrintLn((a == b ? 'H' : 'D'));
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <queue>
#include <algorithm>
#include <sstream>
#include <string>
#include <map>
using namespace std;
#define FOR(I,N) for(int I = 0; I < (int)(N); I++)
#define fin(V) cout<< V <<endl
#define INF 114514
string sValueOf(int v){stringstream ss;ss<<v;return ss.str();}
int parseInt(string v){int i;stringstream ss(v);ss>>i;return i;}

int D, N;
int day[201];
int MIN[201], MAX[201], rare[201];
int dp[201][201];
int mx = 0;
int solve(int day, int now, int bef);


int solve(int n, int b){
	if(n == D)
		return 0;
	if(dp[n][b] != -1){
		return dp[n][b];
	}

	int mx = 0;
	for(int i = 0; i < N; i++){
		if(MAX[i] >= day[n] && MIN[i] <= day[n]){
			mx = max(mx, abs(rare[i] - b) + solve(n+1, rare[i]));
		}
	}
	return dp[n][b] = mx;
}


int main(){
	fill_n(*dp, 201*201, -1);
	cin >> D >> N;
	for(int i = 0; i < D; i++){
		cin >> day[i];
	}
	for(int i = 0; i < N; i++){
		cin >> MIN[i] >> MAX[i] >> rare[i];
	}

	int mx = 0;
	//一番最初の服を決める
	for(int i = 0; i < N; i++){
		if(MAX[i] >= day[0] && MIN[i] <= day[0]){
			mx = max(mx, solve(1, rare[i]));
		}
	}

	fin(mx);
}

Measured memory_bytes: 1336