akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(var,cnt) for(int (var)=0; (var)<(int)(cnt); ++(var))
#define Rep(var,init,cnt) for(int (var)=(init); (var)<(cnt); ++(var))
#define ran(var,vec) for(auto &(var):(vec))
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define SORT(v) sort(all(v))
#define RSORT(v) sort(rall(v))
#define SUM(v) accumulate(all(v),0)
#define tget(tp,idx) get<idx>(tp)
#define TF(flag) (flag)?1:0
#define yn(f) cout<<(f?"yes":"no")<<endl
#define Yn(f) cout<<(f?"Yes":"No")<<endl
#define YN(f) cout<<(f?"YES":"NO")<<endl
#define COUT(x) cout<<(x)<<endl
using namespace std;

using ll = long long;
using ull = unsigned long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
using ti = tuple<int,int,int>;
using tl = tuple<ll,ll,ll>;

template<typename T>
using vec = vector<T>;
template<typename T>
using mat = vector<vec<T>>;
template<typename T>
using cub = vector<mat<T>>;
template<typename T>
using val = valarray<T>;

template<typename T>
using pq = priority_queue<T>;
template<typename T>
using rpq = priority_queue<T,vec<T>,greater<T>>;

template<typename T1,typename T2>
ostream &operator<<(ostream &os, const pair<T1,T2> &p){
  os<<"P("<<p.first<<", "<<p.second<<") ";
  return os;
}

template<typename T1,typename T2>
istream &operator>>(istream &is, pair<T1,T2> &p){
  is>>p.first>>p.second;
  return is;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
  cout<<"V{";
  for(int i=0; i<(int)v.size(); ++i){
    os<<v[i]<<(i+1!=v.size()?" ":"");
  }
  cout<<"}";
  return os;
}

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

template<typename T>
ostream &operator<<(ostream &os, const valarray<T> &v){
  cout<<"V{";
  for(int i=0; i<(int)v.size(); ++i){
    os<<v[i]<<(i+1!=v.size()?" ":"");
  }
  cout<<"}";
  return os;
}

template<typename T>
istream &operator>>(istream &is, valarray<T> &v){
  for(T &in:v) is>>in;
  return is;
}

// Usual Template End ================================================

// Template End ======================================================

constexpr int MOD=1e9+7;

int main(void){
  int a,b,c,d; cin>>a>>b>>c>>d; COUT(min(a,b)+min(c,d));
}













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

int main()
{
  string s;
  cin>>s;
  ll ans=0;
  vector<ll> left(s.size()+1),right(s.size()+1);
  left[0]=0;
  right.back()=0;
  for (int i = 0; i < s.size(); ++i)
  {
    if (s[i]=='>') left[i+1]=0;
    else left[i+1]=left[i]+1;
  }
  for (int i = s.size()-1; i >= 0; --i)
  {
    if (s[i]=='<') right[i]=0;
    else right[i]=right[i+1]+1;
  }
  
  for (int i = 0; i < s.size()+1; ++i)
  {
    ans+=max(left[i],right[i]);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 11632
import java.util.*;
import java.io.*;

import static java.lang.Character.isUpperCase;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        String str = "No";
        for (int i = 1; i <= 9; i++) {
            for (int j = 1; j <= 9; j++) {
                if (i * j == N) {
                    str = "Yes";
                }

            }



        }
        System.out.println(str);

    }

}















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



int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int a, b;
	cin >> a >> b;
	int c;
	for (int i = 1; i <= 3; ++i)
	if (a != i && b != i)
		c = i;
	cout << c << "\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  long long w,h;cin>>w>>h;
  long long x,y;cin>>x>>y;
  cout<<(double)w*h/2<<' '<<(x==(double)w/2&&y==(double)h/2?1:0)<<endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<=(end);i++)
#define REP(i, n) FOR(i,1,n)
#define IFOR(i, begin, end) for(int i=(end);i>=(begin);i--)
#define IREP(i, n) IFOR(i,1,n)
#define SORT(a) sort(a.begin(), a.end())
#define REVERSE(a) reverse(a.begin(), a.end())

#define ll long long
using namespace std;

bool is_prime(int k)
{
    for(int j=2;j*j<=k;j++){
        if(k%j==0) {
            return false;
        }
    }
    return true;
}

int main()
{
	stringstream ss;
    // 入力
    int N,I;
    cin>>N>>I;

    cout<<N-I+1<<endl;
    return 0;
}

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

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

const int INF = 1e9;
const int mod = 1e9+7;

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

    int ss;
    for(ss = 0; ss < s.length(); ss++){
        if(s[ss] != '1') break;
    }

    cout << (k < ss+1 ? '1' : s[ss]) << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define N 3002
using namespace std;
typedef pair<int,int> P;
vector<P> G[N];
bool num[N];
int n,m,K;

double dijkstra(){
  vector<int> D(N,1e9);
  priority_queue<P,vector<P>,greater<P> >Q;
  for(int i=0;i<n;i++)if(num[i]) Q.push(P(0,i)),D[i] = 0;
  
  while(!Q.empty()){
    P t = Q.top();Q.pop();
    int cost = t.first;
    int pos = t.second;
    if(D[pos]<cost) continue;

    for(int i=0;i<G[pos].size();i++){
      int npos = G[pos][i].first;
      int ncost = cost+G[pos][i].second;
      if(D[npos]<=ncost) continue;
      Q.push(P(ncost,npos));
      D[npos] = ncost;
    }
  }

  double res = 0;
  for(int i=0;i<n;i++)
    for(int j=0;j<(int)G[i].size();j++){
      int npos = G[i][j].first;
      int ncost = G[i][j].second;
      res = max(res,(D[i]+D[npos]+ncost)/2.0);
    }
  return res;
   
}
 
int main(){
  cin>>n>>m>>K;
  for(int i=0,a,b,c;i<m;i++){
    cin>>a>>b>>c;
    G[a-1].push_back(P(b-1,c));
    G[b-1].push_back(P(a-1,c));
  }
 
  for(int i=0,a;i<K;i++)cin>>a,num[a-1]=1;
  printf("%d\n",(int)(dijkstra()+0.5));
  return 0;
}

Measured memory_bytes: 5972
from bisect import bisect_left
a,b,q = map(int,input().split())
INF = 10**15
s = [-INF] + sorted([int(input()) for _  in range(a)]) + [INF]
t = [-INF] + sorted([int(input()) for _  in range(b)]) + [INF]
#print(s,t)
for i in range(q):
    pro = int(input())
    s_index = bisect_left(s, pro)
    t_index = bisect_left(t, pro)
    s1,s2 = s[s_index-1] , s[s_index]
    t1,t2 = t[t_index-1] , t[t_index]
    #print(s1,s2,t1,t2)
    minimum = []
    kouho1 = abs(pro-s1)+ abs(s1-t1)
    minimum.append(kouho1)
    kouho2 = abs(pro-s1)+ abs(s1-t2)
    minimum.append(kouho2)
    kouho3 = abs(pro-t1)+ abs(t1-s1)
    minimum.append(kouho3)
    kouho4 = abs(pro-t2)+ abs(t2-s1)
    minimum.append(kouho4)
    kouho5 = abs(pro-s2)+ abs(s2-t1)
    minimum.append(kouho5)
    kouho6 = abs(pro-s2)+ abs(s2-t2)
    minimum.append(kouho6)
    kouho7 = abs(pro-t1)+ abs(s2-t1)
    minimum.append(kouho7)
    kouho8 = abs(pro-t2)+ abs(s2-t2)
    minimum.append(kouho8)
    print(min(minimum))
    

Measured memory_bytes: 18560
#include <bits/stdc++.h>
#define pb          emplace_back
#define ll          long long
#define fi          first
#define se          second
#define mp          make_pair

using namespace std;

const int N = int(1e5) + 7;
typedef pair<int, int> pii;

vector<int> x[N], y[N];
int n, lab[N];
pii p[N];
set<int> sx[N], sy[N];

int Find(int x) {return lab[x] < 0? x: lab[x] = Find(lab[x]);}
void Union(int r, int s) {
    if(r == s) return;
    if(lab[r] > lab[s]) swap(r, s);
    lab[r] += lab[s], lab[s] = r;
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define Task        "test"
    if(fopen(Task".inp", "r")) {
        freopen(Task".inp", "r", stdin);
        freopen(Task".out", "w", stdout);
    }
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> p[i].fi >> p[i].se;
        x[p[i].fi].pb(i), y[p[i].se].pb(i);
    }
    memset(&lab, -1, sizeof lab);
    for(int i = 1; i <= int(1e5); ++i) {
        for(int j = 1; j < int(x[i].size()); ++j)
            Union(Find(x[i][j]), Find(x[i][j - 1]));
    }
    for(int i = 1; i <= int(1e5); ++i) {
        for(int j = 1; j < int(y[i].size()); ++j)
            Union(Find(y[i][j]), Find(y[i][j - 1]));
    }
    for(int i = 1; i <= n; ++i) {
        sx[Find(i)].insert(p[i].fi);
        sy[Find(i)].insert(p[i].se);
    }
    ll res = -n;
    for(int i = 1; i <= n; ++i) {
        if(lab[i] < 0) res += (ll)(sx[i].size()) * (ll)(sy[i].size());
    }
    cout << res;
}


Measured memory_bytes: 23296
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<string>
#include<cmath>
//#include<>
using namespace std;
 
typedef long long ll;
#define rep(i,j) for(i=0;i<j;i++)
#define rev_rep(i,j) for(i=j;i>=0;i--)
 
int not_[3]={2,1,0};
int and_[3][3]={{0,0,0},{0,1,1},{0,1,2}};
int or_[3][3]={{0,1,2},{1,1,2},{2,2,2}};
 
int i,p,q,r;
int rec(string s)
{
  stack<char>key;
  int ans=0,v;
  key.push('+');
  while(i<s.size())
    {
      if(s[i]==')')
    {return ans;}
      else if(s[i]=='+'||s[i]=='-'||s[i]=='*')
      key.push(s[i++]);
      else
    {
      if(s[i]=='(')
        {i++;v=rec(s);}
      else if(s[i]=='P')v=p;
      else if(s[i]=='Q')v=q;
      else if(s[i]=='R')v=r;
      else
          v=s[i]-'0';
      while(!key.empty())
        {
          if(key.top()=='+')
        ans=or_[ans][v];
          else if(key.top()=='-')
        {
          v=not_[v];
          if(key.size()==1)ans=v;
        }
          else if(key.top()=='*')
        ans=and_[ans][v];
          key.pop();
        }
      i++;
    }
    }
  return ans;
}
 
int main()
{
  string s;
  while(cin>>s)
    {
      if(s[0]=='.')return 0;
      int a,b,c;
      int cnt=0;
      rep(a,3)rep(b,3)rep(c,3)
    {
      p=a;q=b;r=c;
      i=0;
      if(rec(s)==2)cnt++;
    }
      cout<<cnt<<endl;
    }
  return 0;
}


Measured memory_bytes: 3240
n, W = map(int, input().split())
dp = [0]*(W+1)
for _ in range(n):
    w, v = map(int, input().split())
    tmp_dp = [max(dp[sum_w], dp[sum_w - w] + v) for sum_w in range(w, W+1)]
    dp[w:] = tmp_dp
print(max(dp))

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

using R=long double;
using P=complex<R>;
using VP=vector<P>;

const R EPS = 1E-11; // [-1000:1000]->EPS=1e-8 [-10000:10000]->EPS=1e-7
const R INF = 1E40;
constexpr R PI = acos(R(-1));
inline int sgn(const R& r){ return (r > EPS) - (r < -EPS);}
inline int sgn(const R& a, const R &b){ return sgn(a-b); }
inline R sq(R x){return sqrt(max<R>(x,0.0));}


// dot det
inline R dot(P o,P a,P b){a-=o,b-=o; return real(conj(a)*b);}
inline R det(P o,P a,P b){a-=o,b-=o; return imag(conj(a)*b);}


enum CCW{ LEFT = 1,RIGHT = 2,BACK = 4,FRONT = 8,ON = 16};
inline int ccw(P o,P a, P b) {
	if (sgn(det(o,a,b)) > 0) return LEFT;    // counter clockwise
	if (sgn(det(o,a,b)) < 0) return RIGHT;   // clockwise
	if (sgn(dot(o,a,b)) < 0) return BACK;    // b--base--a on line
	if (sgn(norm(a-o)-norm(b-o)) < 0) return FRONT;   // base--a--b on line
	return ON;// base--b--a on line  semnet determination betwenn a and b 
}

int n,m;
R x[110],y[110],r[110];
P p[110];


using edge=tuple<R,int>;
using G=vector<vector<edge>>;

inline bool common(int i,int j){
	R d2=norm(p[i]-p[j]);
	R ri2=norm(r[i]-r[j]);
	R ro2=norm(r[i]+r[j]);
	return ri2 < d2 && d2<ro2;
}

inline bool inside(P q,int i){
	R d2=norm(q-p[i]);
	R r2=norm(r[i]);
	return d2<r2;
}

vector<VP> pols;



// polygon realation determination  in  2 on 1 out 0???(possible non-convex) verify AOJ CGL_3-C
int in_polygon(const VP& pol, const P& p){
	int n=pol.size(),res=0;
	rep(i,n){
		if(ccw(pol[i],pol[(i+1)%n],p)==ON) return 1;
		bool f=sgn(imag(p-pol[i]))>=0;
		bool s=sgn(imag(p-pol[(i+1)%n]))<0;
		int sign=sgn(imag(pol[(i+1)%n]-pol[i]));
		bool can=sgn(sign*det(pol[i],pol[(i+1)%n],p))>0; // (a*d-b*c)*b
		if(can&&f==s) res+=(2*f-1);
	}
	return res?2:0;
}

bool can(P s,P g){
	rep(i,n) if(inside(s,i) != inside(g,i)) return false;
	rep(i,n) if(inside(s,i) && inside(g,i)) return true;
	for(auto &pol:pols) if(in_polygon(pol,s) != in_polygon(pol,g)) return false;	
	return true;
}


int main(void){
	while(cin >> n >> m,n){
		pols.clear();
		rep(i,n) cin >> x[i] >> y[i] >> r[i],p[i]=P(x[i],y[i]);

		G graph(n);
		vector<vector<int>> used(n);

		rep(i,n)rep(j,n){
			if(i==j) continue;
			if(common(i,j)){
				graph[i].push_back(make_tuple(atan2(y[j]-y[i],x[j]-x[i]),j));
				used[i].push_back(false);
			}
			sort(begin(graph[i]),end(graph[i]));
		}

		rep(v,n){
			rep(i,graph[v].size()){
				if(used[v][i]) continue;

				VP pol;
				int cur=v,idx=i;
				do{
					pol.push_back(P(x[cur],y[cur]));
					used[cur][idx]=true;

					int nxt=get<1>(graph[cur][idx]);
					int nidx=0;
					rep(j,graph[nxt].size()) if(cur==get<1>(graph[nxt][j])) nidx=j;
					nidx=(nidx+1)%int(graph[nxt].size());
					cur=nxt,idx=nidx;
				}while(cur!=v);

				pols.push_back(pol);
			}
		}

		rep(i,m){
            R sx,sy,gx,gy;
            cin >> sx >> sy >> gx >> gy;
            cout << (i?" ":"") << (can( P(sx,sy),P(gx,gy))?"YES":"NO");
        }
        cout << endl;

	}
	return 0;
}

Measured memory_bytes: 3308
using System;
using System.Collections.Generic;
using System.Linq;

class AIZU0046{
   public static void Main(string[] args) {
      List<double> History = new List<double>();
      string s;
      while(true) { 
         s=Console.ReadLine();
         if (string.IsNullOrEmpty(s)) break;
         History.Add(double.Parse(s));
      }
      Console.WriteLine(History.Max()-History.Min());
   }
}

Measured memory_bytes: 9448
#include<bits/stdc++.h>
using namespace std;
int minhe(int a[],int n)
{
    int ans=0;
    int dp[n];
    dp[0]=0;
    dp[1]=abs(a[1]-a[0]);
    for(int i=2;i<n;++i)
    {
      int min1=abs(a[i]-a[i-1])+dp[i-1];
      int min2=abs(a[i]-a[i-2])+dp[i-2];
      dp[i]=min(min1,min2);
    }
    return dp[n-1];
}
int main()
{
    int n;
    cin>>n;
    int *a=new int[n];
    for(int i=0;i<n;++i)
        cin>>a[i];
    cout<<minhe(a,n);
}


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

using namespace std;

typedef long long int li;
typedef vector<li> vi;
typedef pair<li,li> pi;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define B begin()
#define E end()
#define f(i,l,r) for(li i=l;i<=r;++i)
#define fr(i,l,r) for(li i=l;i>=r;--i)
#define u_map unordered_map
#define endl "\n"

li fastpow(li base,li exp,li M) 
{
    li res=1;
    while(exp>0) {
        if(exp&1)
            res=(res*base)%M;

        base=(base*base)%M;
        exp>>=1;
    }
    return res;
}

vi par,sz,vis,dis;
vector<vi> graph;
vector<vector<pair<li,li>>> wgraph;

void init(li n)
{
    par.resize(n);
    sz.resize(n);
    wgraph.resize(n);
    dis.resize(n);
    vis.resize(n);
    graph.resize(n);

    f(i,0,n-1)
    {
        par[i]=i;
        sz[i]=1;
        dis[i]=INT_MAX;
    }
}

li root(li a)
{
    while(a!=par[a])
    {
        par[a]=par[par[a]];
        a=par[a];
    }

    return a;
}

void unio(li a,li b)
{
    li r_a=root(a);
    li r_b=root(b);

    if(par[r_a]!=r_b)
    { 
        if(sz[r_a]<sz[r_b])
        {
            par[r_a]=par[r_b];
            sz[r_b]+=sz[r_a];
            sz[r_a]=0;
        }
        else
        {
            par[r_b]=par[r_a];
            sz[r_a]+=sz[r_b];
            sz[r_b]=0;
        }
    }
}

void dijkstra(li start)
{
    dis[start]=0;

    multiset<pair<li,li>> s;

    s.insert({0,start});

    while(!s.empty())
    {
        pair<li,li> tp=*s.B;
        s.erase(s.begin());

        li p=tp.S;

        if(!vis[p]) 
        {
            vis[p]=1;

            for(pair<li,li> v:wgraph[p])
            {
                if(dis[p]+v.S<dis[v.F])
                {
                    dis[v.F]=dis[p]+v.S;
                    s.insert({dis[v.F],v.F});
                }
            }
        }
    }
}

int main()
{    
   

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    li a,b;

    cin>>a>>b;

    li c[b],sum=0;

    for(li i=0;i<b;i++)
    {
        cin>>c[i];
        sum+=c[i];
    }

    if(sum>=a)
        cout<<"Yes";
    else
        cout<<"No";



    return 0;
}

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

using namespace std;

int main() {
	while (1)
	{
		int x, y, s;

		cin >> x >> y >> s;

		if (x + y + s == 0)
		{
			break;
		}

		int max = 0;
		for(int p1 = 1; p1 < s; ++p1)
		{
			for (int p2 = 1; p2 < s; ++p2)
			{
				if (p1 * (100 + x) / 100 + p2 * (100 + x) / 100 == s)
				{
					int s_after = p1 * (100 + y) / 100 + p2 * (100 + y) / 100;
					if (s_after > max)
						max = s_after;
				}
			}
		}
		cout << max << endl;
	}
	return 0;
}

Measured memory_bytes: 2992
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <cmath>
#define MOD 1000000007
#define SIZE 5005

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

ll inv[SIZE],fac[SIZE],finv[SIZE];
ll tw[SIZE];
void make()
{
	fac[0]=fac[1]=1;
	finv[0]=finv[1]=1;
	inv[1]=1;
	for(int i=2;i<SIZE;i++)
	{
		inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
		fac[i]=fac[i-1]*(ll) i%MOD;
		finv[i]=finv[i-1]*inv[i]%MOD;
	}
	tw[0]=1;
	for(int i=1;i<SIZE;i++) tw[i]=tw[i-1]*2LL%MOD;
}
ll C(int a,int b)
{
	if(a<b) return 0;
	return fac[a]*(finv[b]*finv[a-b]%MOD)%MOD;
}

int main()
{
	make();
	int A,B;
	scanf("%d %d",&A,&B);
	ll ret=A+1;
	for(int k=1;k<B;k++)
	{
		ll sum=0;
		ll all=0;
		for(int i=A-B+k;i>=0;i--)
		{
			int zan=(A+k)-(i+B);
			if(zan<=B-k-1)
			{
				all+=C(B-k-1,zan);
				if(all>=MOD) all-=MOD;
			}
			sum+=all;
			if(sum>=MOD) sum-=MOD;
			ret+=C(B-1,k-1)*sum%MOD;
			if(ret>=MOD) ret-=MOD;
		}
	}
	printf("%lld\n",ret);
	return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD 1000000007
int main()
{
	ll h,w;
	cin>>h>>w;
	string s[h];
		for(ll j=0;j<h;j++)
		{
			cin>>s[j];
		}
	ll ans[h][w];
	for(ll i=0;i<h;i++)
	{
		for(ll j=0;j<w;j++)
		{
			ans[i][j]=1;
		}
	}
	for(ll i=0;i<h;i++)
	{
		for(ll j=0;j<w;j++)
		{
			if(i==0 && j==0)
			{
				ans[0][0]=1;
				continue;
			}
			ll check1=0,check2=0;
			if(int(s[i-1][j])==46 && i>=1)
			{
			  check1=1;	
			}
			if(int(s[i][j-1])==46 && j>=1)
			{
			check2=1;	
			}
			ans[i][j]=check1*ans[i-1][j]+check2*ans[i][j-1];
			ans[i][j]%=MOD;
		}
	}
	cout<<ans[h-1][w-1];
}

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

void fast(){
ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
}

#define ll				long long
#define rep(i,x,y)  	for(__typeof(x) i=x;i<=y;i++)
#define repi(i,x,y) 	for(__typeof(x) i=x;i>=y;i--)
#define vfor(it,x)		for(__typeof(x.begin()) it= x.begin() ; it!=x.end(); it++)
#define vfori(it,x)		for(__typeof(x.begin()) it= x.end() ; it!=x.begin(); it--)
#define test(t)    	    cin >> t;while(t--)
#define yes             cout <<"YES"<<endl;
#define no              cout <<"NO"<<endl;
#define debug(x)		cout << #x <<" = "<<x<<" ";	
#define pi              3.14159265358979323846 

// a/b  mod m= a⋅b^(−1) mod m
// b^(-1)mod m = b^(m-2) mod m   and m is a prime number

ll power(ll x, ll y, ll p) 
{ 
    ll res = 1;     
  
    x = x % p;   
    while (y) 
    { 
        if (y & 1) 
            res = (res*x) % p; 
        y = y>>1;  
        x = (x*x) % p; 
    } 
    return res; 
} 
 
ll nCrModP(ll n, ll r, ll p) 
{ 
    if (!r) 
      return 1; 
  
    ll fac[n+1]; 
    fac[0] = 1; 
    for (ll i=1 ; i<=n; i++) 
        fac[i] = fac[i-1]*i%p; 
  
    return (fac[n]* power(fac[r], p-2,p) % p * power(fac[n-r], p-2,p) % p) % p; 
}

ll pow_mod(ll x,ll n,ll m)
{
    if (n == 0) 
    	return 1;
	ll t;
    t = pow_mod(x, n/2, m);
 	if(n%2==0)
        return t * t  % m;
    else
        return t * t * x  % m;
}

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


Measured memory_bytes: 3784
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
typedef long double lb;
typedef pair<int,int> P;
const int MOD = 1000000007;
const ll INF = 1e16;
const double EPS = 1e-10;
const double PI = 3.141592653589793;
template<class T> inline bool chmin(T& a, T b){if(a>b){a = b;return 1;}return 0;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a = b;return 1;}return 0;}
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 
#define int long long
#define double long double

////////////////////////////////////////////////////////////////////
template<typename T>
struct edge {
  int to, from;T cost;
  edge(int to) : from(-1), to(to), cost(-1) {}
  edge(int to, T cost) : from(-1), to(to), cost(cost) {}
  edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
};
template<typename T>
using edges = vector<edge<T>>;
template<typename T>
using graph = vector<edges<T>>;
template<typename T>
using matrix = vector<vector<T>>;

template<typename T>
bool compByCost(const edge<T>& left, const edge<T>& right){
  return left.cost < right.cost; 
}
class union_find{
  int N;vector<int> par;
  public:
    union_find(int n){
      N = n;
      par.resize(N);
      rep(i,N)par[i] = i;
    }
    int find(int x){
      if(par[x] == x)return x;
      else{
        return par[x] = find(par[x]);
      }
    }
    void unite(int x, int y){
      x = find(x);
      y = find(y);
      if(x == y)return;
      par[x] = y;
    }
    bool same(int x, int y){
      return find(x) == find(y);
    }
};
int kruskal(edges<int>& es){
  sort(es.begin(), es.end(), compByCost<int>);
  union_find u(es.size());
  int res = 0;
  rep(i, es.size()){
    edge<int> e = es[i];
    if(!u.same(e.from, e.to)){
      u.unite(e.from, e.to);
      res += e.cost;
    }
  }
  return res;
}

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

int n,x[110000],y[110000];P a[110000], b[110000];
edges<int> es;
signed main(){
  cin>>n;rep(i,n)cin>>x[i]>>y[i];
  rep(i,n){
    a[i].first = x[i];
    b[i].first = y[i];
    a[i].second = b[i].second = i;
  }
  sort(a, a+n);sort(b, b+n);
  rep(i,n-1){
    int from = a[i].second, to = a[i+1].second;
    es.push_back(edge<int>(from, to, min(abs(x[from]-x[to]), abs(y[from]-y[to]))));
    es.push_back(edge<int>(to, from, min(abs(x[from]-x[to]), abs(y[from]-y[to]))));
    from = b[i].second, to = b[i+1].second;
    es.push_back(edge<int>(from, to, min(abs(x[from]-x[to]), abs(y[from]-y[to]))));
    es.push_back(edge<int>(to, from, min(abs(x[from]-x[to]), abs(y[from]-y[to]))));
  }
  cout << kruskal(es) << endl;
}




Measured memory_bytes: 18024
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;

int main() {
	int H, W, ans = INT_MAX;
	cin >> H >> W;
	vector<vector<int>> A(H, vector<int>(W));
	for (vector<int>& i : A) {
		for (int& j : i) cin >> j;
	}
	for (int i = 0; i < H; ++i) {
		for (int j = 0; j < W; ++j) {
			int a = 0;
			for (int k = 0; k < H; ++k) {
				for (int l = 0; l < W; ++l) a += A[k][l] * min(abs(i - k), abs(j - l));
			}
			ans = min(a, ans);
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 3136
#include <stdio.h>

int main() {
        int N, K;
        scanf("%d %d", &N, &K);

        int count = 0;
        for (int val = 1 ; val <= N ; val += 2) {
                count++;
        }

        if (count < K) {
                printf("NO\n");
        } else {
                printf("YES\n");
        }
}

Measured memory_bytes: 128
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using static System.Console;
using static System.Math;
using static MyIO;
using static MyUtil;

public class A { public static void Main() => (new Solver()).Solve(); }

public class Solver
{
	public void Solve()
	{
		long H = GetLong();
		long W = GetLong();
		var isBlack = new bool[H + 1, W + 1];
		for(long i = 0; i < H; i++)
		{
			var S = GetString();
			for(long j = 0; j < W; j++)
			{
				if(S[(int)j] == '#')
					isBlack[i + 1, j + 1] = true;
			}
		}

		long INF = long.MaxValue / 2;
		var dp = new long[H + 2, W + 2];
		for(long i = 0; i < H + 1; i++)
		{
			for(long j = 0; j < W + 1; j++)
				dp[i, j] = INF;
		}
		dp[0 ,1] = 0;
		dp[1, 0] = 0;

		for(long i = 1; i < H + 1; i++)
		{
			for(long j = 1; j < W + 1; j++)
			{
				chmin(ref dp[i, j], dp[i - 1, j] + (isBlack[i, j] ^ isBlack[i - 1, j] ? 1 : 0));
				chmin(ref dp[i, j], dp[i, j - 1] + (isBlack[i, j] ^ isBlack[i, j - 1] ? 1 : 0));
			}
		}
		long K = isBlack[H, W] ? dp[H, W] + 1 : dp[H, W];
		WriteLine(K / 2);
	}
}

public static class MyIO
{
	private static string[] args = new string[0];
	private static int cnt = 0;
	private static IEnumerable<string> getArgs(long N) => Range(0, N).Select(_ => getArg());
	private static string getArg()
	{
		if(cnt == args.Length) { args = Console.ReadLine().Split(); cnt = 0; }
		return args[cnt++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static decimal GetDecimal() => decimal.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(long N) => getArgs(N).Select(int.Parse).ToArray();
	public static long[] GetLongs(long N) => getArgs(N).Select(long.Parse).ToArray();
	public static double[] GetDoubles(long N) => getArgs(N).Select(double.Parse).ToArray();
	public static decimal[] GetDecimals(long N) => getArgs(N).Select(decimal.Parse).ToArray();
	public static string[] GetStrings(long N) => getArgs(N).ToArray();
}

public static class MyUtil
{
	public static void chmax<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) < 0) x = y; }
	public static void chmin<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) > 0)	x = y; }
	public static void swap<T>(ref T x, ref T y) { T tmp = x; x = y; y = tmp; }
	public static long rightShift(long x, long y) => (x >> (int)y);
	public static long leftShift(long x, long y) => (x << (int)y);
	public static bool contains(long s, long x) => (rightShift(s, x) & 1L) == 1L;
	public static long gcd(long x, long y) => (y == 0) ? x : gcd(y, x % y);
	public static long lcm(long x, long y) => (x / gcd(x,y)) * y;	
	public static IEnumerable<int> Range(long start, long count) => Enumerable.Range((int)start, (int)count);
	public static void Sort(this List<string> source) => source.Sort(StringComparer.Ordinal);
}


Measured memory_bytes: 27660
import itertools
n,m,q = map(int,input().split())  
stock = list(range(1,m+1))
A = list(itertools.combinations_with_replacement(stock,n))
lst = []
for i in range(q):
    a = list(map(int,input().split()))
    lst.append(a)
lstx = []    
for k in range(len(A)):
    sum = 0    
    for j in range(q):
        if A[k][lst[j][1]-1] - A[k][lst[j][0]-1] == lst[j][2]:
            sum += lst[j][3]
    lstx.append(sum)    
print(max(lstx))                      


Measured memory_bytes: 25280
//#include <bits/stdc++.h>
//#include <stdio.h>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<cmath>
#include<utility>
#include<functional>
#include<map>
#include<set>
#include<cctype>
#include<fstream>


#define FOR(i, a, b) for( int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for( int i=(a);i>=(b);i--)
#define LFOR(i, a, b) for( long long int i=(a);i<=(b);i++)
#define LRFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 1000000000 //2000000000
#define LLINF 1000000000000000000 //9000000000000000000
#define PI 3.14159265358979
#define MAXI 7500000

using namespace std;
typedef long long int ll;
typedef pair< long long int, long long  int> P;

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



int main(void) {
	
	long long int N, W;

	cin >> N >> W;
	vector<long long int>w(N + 1), v(N + 1);
	vector<vector<long long int> >value(N + 1, vector<long long int>(W + 1,0));
	FOR(i, 1, N) {
		cin >> w[i] >> v[i];
	}

	FOR(i, 0, W) {
		value[0][i] = 0;
	}

	FOR(i, 1, N) {
		FOR(j, 0, W) {
			if (j - w[i] >= 0) {
				value[i][j] = max(value[i-1][j], value[i - 1][j - w[i]] + v[i]);
			}
			else {
				value[i][j] = value[i - 1][j];
			}
			//cout << i << " " << j << " " << value[i][j] << endl;
		}
	}

	cout << value[N][W] << endl;


	return 0;
}

Measured memory_bytes: 80256
import std.algorithm;
import std.range;
import std.stdio;
import std.math;
import std.array;
import std.string;
import std.conv;

void main() {
	auto s = readln().chomp.splitter("/").joiner.array;
	writefln("%s", (s <= "20190430") ? "Heisei" : "TBD");
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=long long int;
int main()
{
    int n;
    cin>>n;
    n=n%10;
    if(n==3)
    cout<<"bon"<<endl;
    else if(n==0||n==1||n==6||n==8)
    cout<<"pon"<<endl;
    else
    {
        cout<<"hon"<<endl;
    }
    
}

Measured memory_bytes: 3592
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

int N , a[200005] ;

long long calc( int x ){
	long long rt = 0 ;
	for( int i = 1 ; i <= N ; i ++ )
		rt += abs( a[i] - x - i ) ;
	return rt ;
}

void solve(){
	int lf = -1e9 , rg = 1e9 , mL , mR ;
	long long vL , vR , ans = ( 1LL << 60 ) ;
	while( rg - lf >= 3 ){
		mL = lf + ( rg - lf ) / 3 , mR = rg - ( rg - lf ) / 3 ;
		vL = calc( mL ) , vR = calc( mR ) ;
		vL > vR ? lf = mL : rg = mR ;
	}
	for( int i = lf ; i <= rg ; i ++ )
		ans = min( ans , calc( i ) ) ;
	printf( "%lld" , ans ) ;
}

int main(){
	scanf( "%d" , &N ) ;
	for( int i = 1 ; i <= N ; i ++ )
		scanf( "%d" , &a[i] ) ;
	solve() ;
}


Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
int main() {
	string S; cin >> S;
	int N; N = S.size();
	int num[N];
	for (int i = 0; i < N; i++) {
		if (S[i] == 'A' || S[i] == 'T' || S[i] == 'G' || S[i] == 'C') {
			num[i] = 1;
		}
		else {
			num[i] = 0;
		}
	}
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		int temp = 0;
		for (int j = i; j < N; j++) {
			if (num[j] == 1) temp++;
			else break;
		}
		cnt = max(cnt, temp);
	}
	cout << cnt << endl;
}


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

template<typename T>
T gcd(T a, T b) {
  if (a == 0) return b;
  return gcd(b%a, a);
}

template<typename T>
T lcm(T a, T b) {
  return (a*b)/gcd(b%a, a);
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << setprecision(20);
  string s;
  int nouse, i;
  cin >> nouse >> i >> s;
  s[i-1] = tolower(s[i-1]);
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 256
X,N = map(int,input().split())
P = list(map(int,input().split()))

if N == 0:
  print(X)
else:
  for i in range(X,-2,-1):
    if i not in P:
      a = abs(X - i)
      break
  for j in range(X+1,102):
    if j not in P:
      b = abs(j - X)
      break
  if a <= b:
    print(i)
  else:
    print(j)

Measured memory_bytes: 9188
class UnionFind:
    def __init__(self, size):
        self.parent = [-1 for i in range(size)]#非負なら親ノード，負ならグループの要素数

    def root(self, x): #root(x): xの根ノードを返す．
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x]) #xをxの根に直接つなぐ
            return self.parent[x]

    def merge(self, x, y): #merge(x,y): xのいるグループと$y$のいるグループをまとめる
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.parent[x] > self.parent[y]: #xの要素数がyの要素数より「小さい」とき入れ替える
            x,y=y,x
        self.parent[x] += self.parent[y] #xの要素数を更新
        self.parent[y] = x #yをxにつなぐ
        return True

    def issame(self, x, y): #same(x,y): xとyが同じグループにあるならTrue，違うならFalse
        return self.root(x) == self.root(y)
        
    def size(self,x): #size(x): xのいるグループの要素数を返す
        return -self.parent[self.root(x)]
#>>>>>>>>>>>>>>EhdCutHere>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

n,m = list(map(int,input().split()))
p = list(map(lambda x: int(x)-1,input().split()))

uf = UnionFind(n)
for i in range(m):
    x,y=list(map(int,input().split()))
    uf.merge(x-1,y-1)

ans = 0
for i in range(n):
    if uf.issame(i,p[i]):
        ans += 1

print(ans)
#print([uf.root(i) for i in range(n)])
#print([uf.parent[i] for i in range(n)])
#print([uf.size(i) for i in range(n)])



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

long long w[109];
long long v[109];
long long dp[109][100005];

int main(){
	int n,c;
	cin>>n>>c;
	for(int i=1;i<=n;++i)
		cin>>w[i]>>v[i];
	for(int i=0;i<=n;++i){
		for(int wt=0;wt<=c;++wt){
			if(i==0||wt==0){
				dp[i][wt]=0;
				continue;
			}
			dp[i][wt]=dp[i-1][wt];
			if(wt-w[i]>=0)
				dp[i][wt]=max(dp[i][wt],dp[i-1][wt-w[i]]+v[i]);
		}
	}
	cout<<dp[n][c]<<endl;
	return 0;
}


Measured memory_bytes: 80128
import java.util.Scanner;

public class Main  {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int[] how = new int[a];

		for(int i=0 ; a>i ; i++) {
			int b = sc.nextInt();
			how[i]=b;
		}

		int count = 0;
		int z =0;
		while(true) {
			for (int i = 0; a>i; i++) {
				if (how[i]%2==1) {
					z = 1;
					break;
				}

				else if (how[i]%2==0) {
					how[i]=how[i]/2;

					if (i==(a-1)){
						count++;
					}
				}

			}
			if(z==1)
				break;
		}


		System.out.println(count);

	}

}


Measured memory_bytes: 23764
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
using namespace std;

using ll = long long;

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; }
template<class T> inline void dump(vector<T> v) { for (auto& x : v) cerr << x << " "; cerr << endl; }
template<class T> inline void dump(vector<pair<T, T>> v) { for (auto& p : v) cerr << p.first << " " << p.second << endl; }
template<class T> inline void dump(vector<vector<T>> vv) { for (auto& v : vv) {for (auto& x : v) cerr << x << " "; cerr << endl;} }

constexpr int INF = 1e9+5;
constexpr long long INFLL = 1LL<<60;
constexpr double eps = (1e-9);

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

  int h, w;
  cin >> h >> w;
  vector<string> a(h);
  rep(i, h) cin >> a[i];

  map<char, int> mp;
  rep(i, h) rep(j, w) {
    mp[a[i][j]]++;
  }

  int num4 = 0;
  int num2 = 0;
  int num1 = 0;

  for (auto& p : mp) {
    int num = p.second;
    num4 += num / 4;  num %= 4;
    num2 += num / 2; num %= 2;
    num1 += num;
  }

  int req4 = 0;
  int req2 = 0;
  int req1 = 0;

  if (h % 2 == 0) {
    req4 = (w / 2) * (h / 2);
    req2 = (w % 2) * (h / 2);
  } else {
    if (w % 2 == 0) {
      req4 = (w / 2) * (h / 2);
      req2 = w / 2;
    } else {
      req4 = (w / 2) * (h / 2);
      req2 = (w / 2) + (h / 2);
      req1 = 1;
    }
  }

//  cerr << req4 << " " << req2 << " " << req1 << endl;
//  cerr << num4 << " " << num2 << " " << num1 << endl;

  if (num4 < req4) {
    puts("No");
    return 0;
  }
  num4 -= req4;
  if (num4 > 0) num2 += num4 * 2;
  if (num2 < req2) {
    puts("No");
    return 0;
  }

  puts("Yes");

  return 0;
}


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

int main() {
    int64_t k;
    cin >> k;
    vector<int64_t> ans(50);
    iota(begin(ans), end(ans), 0);
    for (auto& e : ans) e += k / 50, e -= k % 50;
    for (int64_t i = 0; i < k % 50; i++) ans[i] += 51;
    cout << 50 << endl;
    for (auto& e : ans) cout << e << " ";
}


Measured memory_bytes: 256
loop do
    w, q = gets.split.map(&:to_i)
    break if w == 0
    x = 0
    sleep = {}
    q.times do
        type, id, wid = gets.chomp.split
        if type == ?s
            wid = wid.to_i
            b = (0..w-wid).find do |b|
                (((1 << wid) - 1) << b) & x == 0
            end
            if b
                puts b
                x |= (((1 << wid) - 1) << b)
                sleep[id] = [b, wid]
            else
                puts 'impossible'
            end
        else
            b, wid = sleep[id]
            x -= (((1 << wid) - 1) << b)
        end
    end
    puts 'END'
end

Measured memory_bytes: 8732
# -*- coding: utf-8 -*-

s = list(input())
n = len(s)
can = []

def dfs(i,left,sum):
    if i + 1 == n:
        sum += int("".join(s[left:]))
        can.append(sum)
        return
    dfs(i + 1,left,sum)
    dfs(i + 1,i + 1,sum + int("".join(s[left:i+1])))
    return

dfs(0,0,0)
print(sum(can))


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define db(a) cout << fixed << #a << " = " << a << endl;

using namespace std;

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	ll n, K;
	cin >> n >> K;
	vector<int> P(n), C(n);
	for (int i = 0; i < n; i++) {cin >> P[i]; P[i]--;};
	for (int i = 0; i < n; i++) cin >> C[i];
	ll R = 0;
	for (int i = 0; i < n; i++) {
		ll S = 0;
		ll tmp_R = 0;
		ll tmp_K = K;
		ll x = P[i];
		S += C[x];
		ll k = 1;
		while (x != i) {
			x = P[x];
			S += C[x];
			k++;
		}
		ll d = tmp_K / k;
		if (d > 2) {
			if (S >= 0) {
				tmp_R += S * (d - 2);
			}
			tmp_K -= (d - 2) * k;
		}
		x = P[i];
		S = 0;
		S += C[x];
		ll max_score = S;
		tmp_K--;
		while (tmp_K > 0) {
			x = P[x];
			S += C[x];
			max_score = max(max_score, S);
			tmp_K--;
		}
		if (i == 0) R = max_score + tmp_R;
		else R = max(R, max_score + tmp_R);
	}
	cout << R << endl;
}



Measured memory_bytes: 3656
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <string>
#include <algorithm>
#include <string>
#include <climits>

#define REP(i, n) for (int (i) = 0; (i) < (int)(n); (i)++)
#define REG(i, a, b) for (int (i) = ((int)(a)); (i) < ((int)(b)); i++)
#define ALL(V) ((V).begin(), (V).end())
#define PRINT(STR) (cout << (STR) << endl)

typedef long long ll;
using namespace std;

bool isOK(int n, int h[], int a) {
	REP(i, n) {
		if (i == a) continue;
		if (h[i] != 0) return false;
	}
	return true;
}

void step(int a, int n, int* s, int h[]) {
	if (*s == 0) {
		*s = h[a];
		h[a] = 0;
	} else {
		h[a]++;
		*s -= 1;
	}
}

int main() {
	cin.tie(0); //?????±?????????????????????
	ios::sync_with_stdio(false); //printf??¨??±??????????????????
	int n, p;
	int h[51];
	while (cin >> n >> p, n + p != 0) {
		int a = 0;
		fill(h, h + 51, 0);
		while(true) {
			step(a, n, &p, h); 
			if (p == 0 && isOK(n, h, a) == true) {
				break;
			}
			a++;
			if (a == n) {
				a = 0;
			}
		}
		PRINT(a);
	}

	return 0;
}

Measured memory_bytes: 1192
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(long long int i=0;i<n;i++)
#define foi(i,a,n) for(long long int i=a;i<n;i++)
#define el "\n"

const int INF = 2e9+5;
using ll = long long int;

void solve(){
	string s1,s2;cin>>s1>>s2;
  	int n=s1.length(),m=s2.length();
  	vector<vector<int>> dp(n+1,vector<int>(m+1));
  	dp[0][0]=0;
  	foi(i,1,n+1)foi(j,1,m+1){
    	if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1]+1;
      	else{
        	dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
  	
  	int ind = dp[n][m];
  	char ans[ind];
  	ind--; 
  	int i=n-1,j=m-1;
  	while(i>=0 && j>=0){
    	if(s1[i]==s2[j]){
        	ans[ind]=s1[i];
          	ind--,i--,j--;
        }else if(dp[i][j+1]>dp[i+1][j]) i--;
      	else j--;
    }
  	for(auto c:ans)cout<<c;
}

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

Measured memory_bytes: 38628
#include<cstdio>
int n,c[510],s[510],f[510],*d=c,*t=s,*g=f,i,a,j;main(){for(scanf("%d",&n);d<c+n-1;)scanf("%d%d%d",d++,t++,g++);for(*g=1;i<n;)for(a=0,j=i++;j<n||!printf("%d\n",a);)a=(a<s[j]?s[j]:(~-a/f[j]+1)*f[j])+c[j++];}

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

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rrep2(i,a,b) for (int i=(a)-1;i>=b;i--)
#define chmin(a,b) (a)=min((a),(b));
#define chmax(a,b) (a)=max((a),(b));
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define printV(v) cerr<<(#v)<<":";for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;
#define printVS(vs) cerr<<(#vs)<<":"<<endl;for(auto(s):(vs)){cerr<<(s)<< endl;}
#define printVV(vv) cerr<<(#vv)<<":"<<endl;for(auto(v):(vv)){for(auto(x):(v)){cerr<<" "<<(x);}cerr<<endl;}
#define printP(p) cerr<<(#p)<<(p).first<<" "<<(p).second<<endl;
#define printVP(vp) cerr<<(#vp)<<":"<<endl;for(auto(p):(vp)){cerr<<(p).first<<" "<<(p).second<<endl;}

inline void output(){ cerr << endl; }
template<typename First, typename... Rest>
inline void output(const First& first, const Rest&... rest) {
    cerr << first << " "; output(rest...);
}

using ll = long long;
using Pii = pair<int, int>;
using TUPLE = tuple<int, int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
const int inf = 1ll << 60;
const int mod = 1e9 + 7;
using Graph = vector<vector<int>>;

// N, E, S, W
const int dx[4] = {-1, 0,  1,  0};
const int dy[4] = { 0, 1,  0, -1};

int chr2int(char c) {
    if (c == 'W') return 0;
    if (c == 'N') return 1;
    if (c == 'E') return 2;
    return 3;
}

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

    int n;
    while (cin >> n, n) {
        vector<Pii> vp(n);
        rep(i, n) cin >> vp[i].first >> vp[i].second;
        int m;
        cin >> m;
        vector<vector<bool>> visited(21, vector<bool>(21));
        int x = 10, y = 10;
        visited[x][y] = true;
        rep(i, m) {
            char c;
            int l;
            cin >> c >> l;
            int d = chr2int(c);
            while (l--) {
                x += dx[d];
                y += dy[d];
                visited[x][y] = true;
            }
        }

        int cnt = 0;
        rep(i, n) {
            cnt += visited[vp[i].first][vp[i].second];
        }

        cout << (cnt == n ? "Yes" : "No") << endl;


    }
}

Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (long long i = 0; i < n; i++)
#define inf 1000000000
typedef long long ll;
typedef unsigned long long ull;
int n;
ull a;
ull ans = 1;

int main(){
    bool ok = true;
    cin >> n;
    rep(i,n){
        cin >> a;
        if (a == 0) {
                cout << 0 << endl;
                return 0;
            }
        if (a > 1000000000000000000 / ans)
            {
                ok = false;
            }
            if(ok){ans *= a;}
    }
    if(ok){cout << ans << endl;}

    else
        {cout << -1 << endl;}
    return 0;
}

Measured memory_bytes: 3564
#!/usr/bin/env python3
#ABC68 C

n,m = map(int,input().split())

s = [0]*(200000+1)
g = [0]*(200000+1)
for _ in range(m):
    a,b = map(int,input().split())
    if a == 1:
        s[b] += 1
    if b == n:
        g[a] += 1
f = 0
for i in range(200000+1):
    if s[i] & g[i]:
        f = 1
        break
if f:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')


Measured memory_bytes: 47704
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>

using ll = long long;
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int>W(N);
    for (int i = 0; i < N; i++) {
        cin >> W[i];
    }

    int ans = 99999999;
    for (int t = 1; t < N; t++) {
        int sum1 = 0;
        int sum2 = 0;
        for (int i = 0; i < N; i++) {
            if (i <= t) {
                sum1 += W[i];
            }
            else {
                sum2 += W[i];
            }
        }
        ans = min(ans, abs(sum2 - sum1));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

namespace MyProgram{
    class AtCoder{
        static void Main(){
            long N = long.Parse(Console.ReadLine());
            var A = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
            long gcd = A[0];
            for(var i=1;i<N;i++){
                gcd = Gcd(gcd,A[i]);
            }
            Console.WriteLine(gcd);
        }

        static long Gcd(long m,long n){
            long temp;
            while(m%n!=0){
                temp =n;
                n = m%n;
                m = temp;
            }
            return n;
        }
    }
    
}


Measured memory_bytes: 18912
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>

#define ll long long int
#define mod 1000000007

using namespace std;


int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    int k;
    int a,b;
    cin >> k>> a>> b;
    for(int i = a; i <= b;i++){
        if(i % k == 0){
        cout << "OK";
        return 0;
        }
    }
    cout << "NG";
}









Measured memory_bytes: 3564
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
#define FOR(i, a, b) for(LL i=(LL)(a);i<(LL)(b);i++)
#define REP(i,x) for(LL i=0;i<(LL)(x);i++)

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed << setprecision(10);

    string S;
    cin >> S;

    if(S == "AAA" || S == "BBB")
    {
        cout << "No" << endl;
    }
    else
    {
        cout << "Yes" << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
#include <deque>
#include <cstring>
char s[200005];
long long Mod[200005];
long long Hash[10005];
int main() {
    long long N, P, Temp = 1;
    long long ans = 0;
    cin >> N >> P;
    cin >> s;
    if(P == 2) {
        for(long long i = 0; i < N; i++)
            if((long long)(s[i] - '0') % 2ll == 0)
                ans += (i + 1ll);
        cout << ans << endl;
        return 0;
    }
    if(P == 5) {
        for(long long i = 0; i < N; i++)
            if((long long)(s[i] - '0') % 5ll == 0)
                ans += (i + 1ll);
        cout << ans << endl;
        return 0;
    }
    for(long long i = N - 1; i >= 0; i--)
        Mod[i] = (Mod[i + 1] + Temp * (long long)(s[i] - '0')) % P, Temp = (Temp * 10) % P, Hash[Mod[i]]++;
    for(int i = 1; i < P; i++)
        ans += Hash[i] * (Hash[i] - 1ll) / 2ll;
    ans += Hash[0];
    ans += Hash[0] * (Hash[0] - 1ll) / 2ll;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 2048
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] A = new int[N + 1];
		int[] B = new int[N + 1];
		int[] C = new int[N];
		int sum = 0;
		int target = -1;
		int add = 0;

		for (int i = 1; i < N + 1; i++) {
			A[i] = sc.nextInt();
		}
		for (int i = 1; i < N + 1; i++) {
			B[i] = sc.nextInt();
		}
		for (int i = 1; i < N; i++) {
			C[i] = sc.nextInt();
		}

		for (int i = 1; i < N + 1; i++) {
			sum+=B[A[i]];
			//addできるか
			if (A[i] == target) {
				sum+=add;
				target = -1;
			}

			//C確認
			if (A[i] < C.length) {
				target = A[i] + 1;
				add = C[A[i]];
			}else {
				target = -1;
			}

		}

		System.out.println(sum);
	}

}

Measured memory_bytes: 35436
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long int n,c=0,i,j,k;
    cin>>n;
    long long int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);
     for( i=0;i<n;i++)
    {
        for( j=i+1;j<n;j++)
        {
            if(a[j]!=a[i])
            {
                for( k=j+1;k<n;k++)
                {
                    if(a[k]!=a[j] && a[k]!=a[i])
                    {
                        if(a[i]+a[j]>a[k])
                            c++;
                    }
                }
            }
        }
    }
    cout<<c;
}


Measured memory_bytes: 3640