akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define a first
#define b second
#define mp make_pair 
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
ll H,W;
P change(ll x){
	P p;
	if(((x+W-1)/W)%2==1) p=mp((x+W-1)/W,x%(2*W));
	else p=mp((x+W-1)/W,(2*W)-(x-1)%(2*W));
	return p;
}

int main(){
	cin>>H>>W;
	ll X[501][501];
	ll cX[501][501];
	rep1(i,H)rep1(j,W){
		cin>>X[i][j];
		cX[i][j]=X[i][j];
	}

	ll cnt=0;
	rep1(i,H*W-1){
		if(cX[change(i).a][change(i).b]%2==1){
			cX[change(i).a][change(i).b]--;
			cX[change(i+1).a][change(i+1).b]++;
			cnt++;
		}
	}
	cout<<cnt<<endl;
	rep1(i,H*W-1){
		if(X[change(i).a][change(i).b]%2==1){
			X[change(i).a][change(i).b]--;
			X[change(i+1).a][change(i+1).b]++;
			cout<<change(i).a<<" "<<change(i).b<<" "<<change(i+1).a<<" "<<change(i+1).b<<endl;
		}
	}
}

Measured memory_bytes: 6016
x, n = map(int, input().split())
p = map(int, input().split())

d=150
pa = 0
px =range(102)
py = list(set(px) - set(p))

for i in py:

    if d> abs(i-x):
        pa = i
        d = abs(i-x)
    elif d == abs(i-x):
        if i < pa:
            pa =i



print(pa)

Measured memory_bytes: 61716
str = $stdin.gets.chomp

abc = {}

for i in 0..str.size-1
  if abc[str[i]] == nil
     abc[str[i]] = 0
  end
  abc[str[i]] += 1
end
ans = "Yes"
abc.each do |k, v|
 if v != 2
   ans = "No"
   break
 end
end

puts ans

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;
//inline int in() { int x; scanf("%d",&x); return x;}
inline ll in() { ll x; cin >> x; return x; }
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
const int MX = 200005;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
map<ll, ll> prime_factor(ll n) {
  map<ll, ll> ret;
  for(ll i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if (n != 1) ret[n] = 1;
  return ret;
}

vector<int> to[2505];
vector<int> rto[2505];
bool reachablefrom1[2505];
bool reachableToN[2505];
bool ok[2505];

void dfs(int v) {
  if (reachablefrom1[v]) return;
  reachablefrom1[v] = true;
  for (int u : to[v]) {
    dfs(u);
  }
}
void rdfs(int v) {
  if (reachableToN[v]) return;
  reachableToN[v] = true;
  for (int u : rto[v]) {
    rdfs(u);
  }
}

int main() {
  ll a = in(), b = in();
  ll ans = 1;
  ll lastnum = 0;
  for (auto p : prime_factor(gcd(a,b)))
    while(p.second--) {
      if (p.first != lastnum) {
        lastnum = p.first;
        ans++;
      }
    }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

static const int N = 1000;

int lcs(string X, string Y){
    int c[N+1][N+1];
    int m = X.size();
    int n = Y.size();
    int maxl = 0;
    X = ' ' + X;
    Y = ' ' + Y;
    for(int i = 0; i <= m; i++) c[i][0] = 0;
    for(int j = 0; j <= n; j++) c[0][j] = 0;
    
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if(X[i] == Y[j]){
                c[i][j] = c[i-1][j-1] + 1;
            }
            else{
                c[i][j] = max(c[i-1][j], c[i][j-1]);
            }
    
            maxl = max(maxl, c[i][j]);
        }
    }
    
    return maxl;
}

int main(){
    string s1, s2;
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> s1 >> s2;
        cout << lcs(s1, s2) << endl; 
    }
    return 0;
}


Measured memory_bytes: 7140
/// Updated! https://www.youtube.com/watch?v=U07_n9xGIlM
#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define dbug printf("I am here\n");
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int maxn = 2e5+100;

const ll inf = 1e18;

int main()
{
    ll h , a;
    cin >> h >> a;
    cout << (h+a-1)/a << endl;
    return 0;
}
/*



*/



Measured memory_bytes: 256
h,w,k=[int(j) for j in input().split()]
s=[input() for i in range(h)]
ans=[[0]*w for i in range(h)]
p=1

for i in range(h):
    q=0
    for j in range(w):
        if s[i][j]=="#":
            q+=1
            p+=1
            if q==1:
                p-=1
        ans[i][j]=p
    if q==0:
        for j in range(w):
            ans[i][j]=-1
    if q==1:
        for j in range(w):
            ans[i][j]=ans[i][0]
    p+=1

p=1
q=1
a=[[0 for i in range(w)] for i in range(h)]
for i in range(h):
    if ans[i][0]==-1:
        continue
    for j in range(w):
        if q!=ans[i][j]:
            p+=1
        q=ans[i][j]
        a[i][j]=p

for i in range(h):
    if a[i][0]==0 and i!=0:
        for j in range(w):
            a[i][j]=a[i-1][j]
for i in range(h)[::-1]:
    if a[i][0]==0 and i!=h-1:
        for j in range(w):
            a[i][j]=a[i+1][j]

if a[0][0]!=1:
    p=a[0][0]-1
    for i in range(h):
        for j in range(w):
            a[i][j]-=p
for i in a:
    print(*i)


Measured memory_bytes: 49116
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
ll mod = 1000000007;
ll INF = 1000000099;



signed main(){
    string s;
    cin>>s;
    ll cntw=0,cntl=0;
    ll k=(ll)s.size();
    for(int i=0;i < k;i++)
    {
        if(s.at(i)=='o'){
            cntw++;
        }else{
            cntl++;
        }
    }
    
    if(cntw+(15-k)>=8){
    cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
}



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

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> A(N), B(N), C(N);
  vector<int> D(N,N);
  
  for (int i=0; i<N; i++){
    cin >> A.at(i);
  }
  for (int a=0; a<K; a++){
    if (A==D)
      break;
    for (int i=0; i<N; i++){ 
      int j=max(0, i-A.at(i));
      B.at(j)++;
      int l = min(N-1, i+A.at(i));
      if (l<N-1)
        B.at(l+1)--;
    }
    for(int i=1;i<N;i++)
      B.at(i)+=B.at(i-1);
    A=B;
    B=C;
  }
  C=A;
  
  for (int i=0; i<N; i++){
    cout << C.at(i) << " ";
  }
  cout << endl;
  return 0;

}

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

using namespace std;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define fin(ans) cout << (ans) << endl;
#define blank(ans) cout << (ans) << " ";
#define mp(p, q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef long long lli;
typedef unsigned long long ull;
typedef long double ld;
typedef string str;

typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<ll> vll;
typedef vector<pair<ll, ll>> vpll;
typedef vector<pair<ll, str>> vpls;
typedef vector<tuple<str, ll, ll>> vtsl;
typedef vector<vector<ll>> vvll;
typedef vector<vector<char>> vvc;
typedef vector<vector<str>> vvs;

const ld PI = acos(-1.0);
const ll MAX = 9000000000000000000;
const ll MIN = -9000000000000000000;
const ld DMAX = 4500;
const ld DMIN = -4500;
const ll MOD = 1000000007;

//実行部
void Main()
{
  ll a, b, c;cin >> a >> b >> c;
  fin(a<=c&&b>=c?"Yes":"No")
}

//前処理
int main()
{
  //ios::sync_with_stdio(false);
  //cin.tie(0);
  cout << fixed << setprecision(20); //高精度少数表示
  Main();
  return 0;
}


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

int main()
{
	int N;
	cin >> N;
	vector<int> x(N);
	for (int i = 0; i < N; i++) {
		cin >> x[i];
	}
	vector<int> v(N);
	for (int i = 1; i < N; i++) {
		v[i] = v[i - 1] + (x[i - 1] >= (i - v[i - 1]) * 2 - 1 ? 0 : 1);
	}
	ll res = 1;
	for (int i = 0; i < N; i++) {
		res = (res * (i + 1 - v[i])) % mod;
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 1024
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  n = int(input())
  ps = list(map(int, input().strip().split()))
  p_min = 2 * 20**5
  count = 0
  for p in ps:
    if p < p_min:
      count += 1
      p_min = p
  print(count)

if __name__=='__main__':
  main()

Measured memory_bytes: 24744
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
//	Table is the complete reverse of dp
//	Always think of the pattern (LCM, GCD)
//	Be careful of unsigned
//	double epsilon = FLT_EPSILON;
//	Think of a solution that gets TLE and optimize it
struct ele{
	int k, l, r;
	bool operator<(const ele& other) const
	{
		return abs(l - r) > abs(other.l - other.r);
	}
};
bool cmp(const ele& x, const ele& y)
{
	return x.k < y.k;
}
int main()
{
    cin.tie(nullptr); cout.tie(nullptr); ios_base::sync_with_stdio(false);
    int t, n;
    cin >> t;
    while(t--)
    {
    	cin >> n;
    	vector<ele> big, small;
    	ll ans = 0;
    	for(int i = 0; i < n; i++)
    	{
    		ele tmp;
    		cin >> tmp.k >> tmp.l >> tmp.r;
    		if(tmp.k < n && tmp.l != tmp.r)
    		{
    			if(tmp.l > tmp.r)
					big.push_back(tmp);
				else
					small.push_back(tmp);
    		}
    		else
    			ans += tmp.l;
    	}
    	sort(big.begin(), big.end(), cmp);
    	priority_queue<ele> q;
    	for(ele &x: big)
    	{
			q.push(x);
			if(x.k < q.size())
			{
				ans += q.top().r;
				q.pop();
			}
    	}
    	while(!q.empty())
		{
    		ans += q.top().l;
    		q.pop();
		}
    	sort(small.rbegin(), small.rend(), cmp);
    	for(ele &x: small)
		{
			q.push(x);
			if(n - x.k < q.size())
			{
				ans += q.top().l;
				q.pop();
			}
		}
		while(!q.empty())
		{
			ans += q.top().r;
			q.pop();
		}
    	cout << ans << endl;
    }
}


Measured memory_bytes: 7936
while True:
  try: n=int(input())
  except: break;
  for i in range(n):
    (x,y,b,p)=map(int,input().split())
    s=b*x+p*y
    t=(max(b,5)*x+max(p,2)*y)*4//5
    print(min(s,t))

Measured memory_bytes: 6724
#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
  int t,n,i,j,k,l,l1;
  cin>>n;
  i=1;
 for(i=3;;i++)
 {
   if((n*i)%360==0)
   {
     cout<<i;
     break;
   }
 }
}

Measured memory_bytes: 3628
use std::collections::VecDeque;

fn main() {
    let mut buf = String::new();
    let handle = std::io::stdin();
    handle.read_line(&mut buf).unwrap();
    let n: usize = buf.trim().parse().unwrap();
    buf.clear();
    handle.read_line(&mut buf).unwrap();
    let mut a: Vec<u64> = buf.trim().split_whitespace()
        .map(|a| a.parse().unwrap()).collect();
    let mut b_even: Vec<u64> = Vec::with_capacity(n/2);
    let mut b_odd: Vec<u64> = Vec::with_capacity(n/2);

    for (i, aa) in a.iter().enumerate() {
        if i % 2 == 0 {
            b_even.push(*aa);
        } else {
            b_odd.push(*aa);
        }
    }

    if n % 2 == 0 {
        for i in b_odd.iter().rev() {
            print!("{} ", i);
        }
        for i in b_even {
            print!("{} ", i);
        }
    } else {
        for i in b_even.iter().rev() {
            print!("{} ", i);
        }
        for i in b_odd {
            print!("{} ", i);
        }
    }
    println!("");
}


Measured memory_bytes: 14200
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] inputs;
		inputs = br.readLine().split(" ");
		int n = Integer.parseInt(inputs[0]); // 県の個数
		int m = Integer.parseInt(inputs[1]); // 市の個数

		// 県、年でソート
		PriorityQueue<City> city = new PriorityQueue<>(m, new Comparator<City>() {
			@Override
			public int compare(City o1, City o2) {
				if ( o1.pref != o2.pref ) {		// 県でソート
					return o1.pref - o2.pref;
				} else {						// 同じ県の時は年でソート
					return o1.year - o2.year;
				}
			}
		});
		for ( int id = 1; id <= m; id++ ) {
			inputs = br.readLine().split(" ");
			city.add(new City(id, Integer.parseInt(inputs[0]), Integer.parseInt(inputs[1])));
		}

		// 県ごとに年でナンバー付けしてidでソート
		PriorityQueue<City> city2 = new PriorityQueue<>(m, new Comparator<City>() {
			@Override
			public int compare(City o1, City o2) {
				return o1.id - o2.id;
			}
		});
		int p = 0;
		int num = 0;
		while ( city.size() > 0 ) {
			City c = city.poll();
			// 新出の県の場合
			if ( p != c.pref ) {
				p = c.pref;
				num = 1;
			} else {
				num++;
			}

			c.num = num;
			city2.add(c);
			// System.out.println("id:" + c.id + " pref:" + c.pref + " year:" + c.year);
		}

		PrintWriter pw = new PrintWriter(System.out);
		while ( city2.size() > 0 ) {
			City c = city2.poll();
			// System.out.println("id:" + c.id + " pref:" + c.pref + " num:" + c.num);
			pw.print(String.format("%06d", c.pref));
			pw.println(String.format("%06d", c.num));
		}
		pw.flush();
		br.close();
	}
}

class City {
	int	id		= 0;
	int	pref	= 0;
	int	year	= 0;
	int	num		= 0;

	public City(int id, int pref, int year) {
		this.id = id;
		this.pref = pref;
		this.year = year;
	}
}


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

int main() {
  int a, b;
  scanf("%d %d", &a, &b);
  
  int cur = 1;
  int ans = 0;
  while (cur < b) {
    ++ans;
    cur += a-1;
  }
  
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,s,e) for (int i=s;i<(e);i++)
#define All(v) (v).begin(),(v).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
using namespace std;
typedef long long llint;
typedef pair<int, int> P;
const int MOD = (int)1e9 + 7;
const int INF = 999999999;
// i枚目までで . j枚選んだ . 合計sの場合の総数
llint dp[51][51][2501];

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

    int N, A;
    cin >> N >> A;
    memset(dp, 0, sizeof(dp));
    vector<int> x(N+1);
    REP(i, N) cin >> x[i+1];
    
    dp[0][0][0] = 1;
    FOR(i, 1, N+1)REP(j, N+1)REP(s, 50*N+1){
        dp[i][j][s] = dp[i-1][j][s];      // 選ばない
        if(j >= 1 && x[i] <= s) dp[i][j][s] += dp[i-1][j-1][s-x[i]];  // 選ぶ
    }
    llint ans = 0;
    FOR(i, 1, N+1){
        ans += dp[N][i][A*i];
    }
    cout << ans << "\n";
    
    return 0;
}

Measured memory_bytes: 51072
using System;
using System.Numerics;
using System.Linq;

public static class Common
{
    public static long GCD(long m, long n)
    {
        if (m < n)
        {
            return GCD(n, m);
        }

        while (n != 0)
        {
            var t = n;
            n = m % n;
            m = t;
        }
        return m;
    }

    public static long LCM(long m, long n)
    {
        return (long)(((BigInteger)m * n) / (GCD(m, n)));
    }
}

class Solution
{
    static void Main()
    {
        var n = int.Parse(Console.ReadLine());
        var t = new long[n];
        for (int i = 0; i < n; i++)
        {
            t[i] = long.Parse(Console.ReadLine());
        }

        var lcm = t[0];
        if (n > 1)
        {
            lcm = t.Aggregate((a, b) => Common.LCM(a, b));
        }
        Console.WriteLine(lcm);
    }
}

Measured memory_bytes: 13524
#include<iostream>
#include<sstream>
#include<vector>

using namespace std;

vector<string> map;
int w,h,area;
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};

void f(int x,int y){
	map[y][x]='#';
	for(int i=0;i<4;i++)
		if(0<=x+dx[i]&&x+dx[i]<w&&0<=y+dy[i]&&y+dy[i]<h)
			if(map[y+dy[i]][x+dx[i]]=='.'){
				area++;
				f(x+dx[i],y+dy[i]);
			}
}

int main(){
	ostringstream out;

	string line;

	while(cin >> w >> h, w|h){
		map.clear();
		int x=-1,y;
		area=1;
		for(int iy=0;iy<h;iy++){
			cin >> line;
			map.push_back(line);
			if(x==-1)
				for(int ix=0;ix<line.length();ix++)
					if(line[ix]=='@'){
						x=ix;
						y=iy;
					}
		}

		f(x,y);

		out << area << endl;
	}


	cout << out.str();
	return 0;
}

Measured memory_bytes: 1244
#! /usr/bin/python 
# -*- coding: utf-8 -*- 
#===============================================================================
# Date created  : 2019-03-28T20:56:32+09:00
# Date modified : 2019-03-28T21:27:00+09:00
# Author        : awk
# Description   : unanswered
#===============================================================================

# dp[len][last3][last2][last1] :=  
#String -> *. + last3 + last2 + last1 を満たすような String の個数
# "ACGT" -> [0,1,2,3]
#NG:  AGC,ACG,GAC,AG?C,A?GC
#initialization
MOD = 10**9+7
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] \
    for _ in range(101) ]
dp[0][3][3][3] = 1
for l in range(100):
    for last3 in range(4):
        for last2 in range(4):
            for last1 in range(4):
                for now in range(4):
                    if last2 == 0 and last1 == 2 and now == 1:
                        continue
                    if last2 == 0 and last1 == 1 and now == 2:
                        continue
                    if last2 == 2 and last1 == 0 and now == 1:
                        continue
                    if last3 == 0 and last2 == 2 and now == 1:
                        continue
                    if last3 == 0 and last1 == 2 and now == 1:
                        continue

                    dp[l+1][last2][last1][now] += dp[l][last3][last2][last1]
                    dp[l+1][last2][last1][now] %= MOD
N = int(input())
ans = 0
for last3 in range(4):
    for last2 in range(4):
        for last1 in range(4):
            ans += dp[N][last3][last2][last1]
print(ans%MOD)






Measured memory_bytes: 47216
#unionfind木_集合の管理_同じ集合の数を数える場合：
#parには集合の数と親の名前を同時にメモ化する（根なら-size, 子なら親）
def find(k):#要素k
    if par[k] < 0:#初期はparがすべて負の値
        return k
    else:
        par[k] = find(par[k])
        return par[k]

def unite(i, j):
    i = find(i)
    j = find(j)
    if i==j:#すでに同じ集合
        return False
    else:
        #sizeが大きい方がi
        if i > j:#sizeはマイナス管理なので、i>jの時jの方がサイズが大きい
            i, j = j, i
        par[i] += par[j] #親は負の値で大きくなる
        par[j] = i
        return True

def size(x):
    return -par[find(x)]

n, m= map(int, input().split())
par = [-1]*n#初めは自分自身が親

for i in range(m):
    a, b = map(lambda x:int(x)-1, input().split())
    unite(a, b)

ans = 0
for i in range(n):
    ans = max(ans, -par[i])
print(ans)

Measured memory_bytes: 80636
require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

require 'bigdecimal'

N = get_int

odd = []
1.step(N) do |n|
  if n % 2 == 1
    odd.push n
  end
end

puts (BigDecimal(odd.length) / N).to_f


Measured memory_bytes: 14588
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define FOREQ(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

int h, n, p, m, k;
int A[110];
int B[110];

int sum[600];
bool exist[600];
int himo[600];

double DP[510][110][110];

int main() {
  while (scanf("%d %d %d %d %d", &h, &n, &p, &m, &k) > 0) {
    p--;
    MEMSET(exist, false);
    MEMSET(himo, 0xde);
    MEMSET(sum, 0);
    MEMSET(DP, 0);
    REP(i, m) {
      scanf("%d %d", &A[i], &B[i]);
      B[i]--;
      exist[A[i]] = true;
      himo[A[i]] = B[i];
    }
    REP(i, h + 2) {
      sum[i + 1] = sum[i] + exist[i];
    }

    DP[h][p][k] = 1.0;
    for (int y = h; y > 0; y--) {
      REP(x, n) {
        REP(rest, k + 1) {
          if (exist[y]) {
            if (himo[y] == x) {
              DP[y - 1][x + 1][rest] += DP[y][x][rest];
            } else if (himo[y] == x - 1) {
              assert(x > 0);
              DP[y - 1][x - 1][rest] += DP[y][x][rest];
            } else {
              DP[y - 1][x][rest] += DP[y][x][rest];
            }
          } else {
            assert(y - sum[y] > 0);
            if (rest > y - sum[y]) { continue; }
            double useP = (double)rest / (y - sum[y]);
            DP[y - 1][x][rest] += (1.0 - useP) * DP[y][x][rest];
            if (rest == 0) { continue; }
            double restP = 1.0;
            if (x != n - 1) {
              restP -= 1.0 / (n - 1);
              DP[y - 1][x + 1][rest - 1] += useP / (n - 1) * DP[y][x][rest];
            }
            if (x != 0) {
              restP -= 1.0 / (n - 1);
              DP[y - 1][x - 1][rest - 1] += useP / (n - 1) * DP[y][x][rest];
            }
            DP[y - 1][x][rest - 1] += useP * restP * DP[y][x][rest];
          }
        }
      }
    }
    double ans = 0.0;
    REP(x, n) {
      ans = max(ans, DP[0][x][0]);
    }

    printf("%.8f\n", ans);
  }
}

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

#define int long long
#define vi vector <int>
#define endl "\n"
#define vvi vector <vector<int> >
#define vii vector <pair<int,int> >
#define rep(i,a,b) for (int i=a;i<b;i++)
#define repD(i,a,b) for (int i=a;i>=b;i--)
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define init(i,k) memset(i,k,sizeof i)
#define pb push_back
#define pii pair <int,int>
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
const int N=1e5+5 , MOD=1e9+7;

int dp[N]={0}, a[N];

//---------------------------------------------------------------


void solve()
{
    int n,k;
    cin >> n >> k;
    rep(i,0,n) cin >> a[i];
    // dp[1]=a[1]-a[0];
    // cout << dp[0] <<" ";

    for(int i=1;i<n;i++)
    {
    	dp[i] = dp[i-1] + abs(a[i]-a[i-1]);
    	// cout << dp[i] <<" ";
    	for(int j=2;j<=min(i,k);j++)
    	{
    		dp[i] = min(dp[i], (dp[i-j]+abs(a[i]-a[i-j])));
    		// cout << dp[i] <<" "<< i << endl;
    	}
    	// cout << dp[i] <<" ";
    }
    // rep(i,0,n)
    cout << dp[n-1] << endl;
}

signed main()
{
    speed;
    
 //    int t; cin >> t;
 //    rep(tt,1,t+1)
 //    {
	// cout <<"Case #"<<tt<<": ";
	solve();
 //    }
    return 0;
}

Measured memory_bytes: 1792
#include<stdio.h>
int main(void)
{
    int a[5],b[5];
	int i,max,sum[5];
	char c2,c[5]={'A','B','C','D','E'};
	while (scanf("%d %d",&a[0],&b[0])!=EOF){
	    if(a[0]==0&&b[0]==0) break;
		sum[0]=a[0]+b[0];
		max=sum[0];
		c2='A';
		for(i=1;i<5;i++){
		    scanf("%d %d",&a[i],&b[i]);
			sum[i]=a[i]+b[i];
		}
		for(i=0;i<5;i++){
            if(max<sum[i]){
			    max=sum[i];
				c2=c[i];
			}
		}
		printf("%c %d\n",c2,max);
	}
	return 0;
}	

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

int main(){
  int n;cin>>n;
  pair<pair<string,int>,int> p[100];
  REP(i,n){
    string store; int score;
    cin>>store>>score;
    p[i]=make_pair(make_pair(store,-score),i+1);
  }
  sort(p,p+n);
  REP(i,n) cout<<p[i].second<<endl;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <clocale>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i, s, n) for(int i = (s), i##_len=(n); i < i##_len; ++i)
#define FORS(i, s, n) for(int i = (s), i##_len=(n); i <= i##_len; ++i)
#define VFOR(i, s, n) for(int i = (s); i < (n); ++i)
#define VFORS(i, s, n) for(int i = (s); i <= (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FORS(i, 0, n)
#define VREP(i, n) VFOR(i, 0, n)
#define VREPS(i, n) VFORS(i, 0, n)
#define RFOR(i, s, n) for(int i = (s), i##_len=(n); i >= i##_len; --i)
#define RFORS(i, s, n) for(int i = (s), i##_len=(n); i > i##_len; --i)
#define RREP(i, n) RFOR(i, n, 0)
#define RREPS(i, n) RFORS(i, n, 0)
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v), greater<decltype(v[0])>())
#define SZ(x) ((int)(x).size())
#define REV(x) reverse(ALL(x))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())

using ld = long double;
using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using Pi_i = pair<int, int>;
using Pll_ll = pair<ll, ll>;
using VB = vector<bool>;
using VC = vector<char>;
using VD = vector<double>;
using VI = vector<int>;
using VLL = vector<ll>;
using VS = vector<string>;
using VSH = vector<short>;
using VULL = vector<ull>;

const int MOD = 1000000007;
const int INF = 1000000000;
const int NIL = -1;
const double EPS = 1E-10;

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


int main(){
    int N, M, K; cin >> N >> M >> K;
    bool okay = false;
    REPS(k, N){
        if(2*k == N){
            if(k*M == K) okay = true;
        }else{
            int l = (K - k*M) / (N - 2*k);
            if(l >= 0 && l <= M && k*(M-l) + (N-k)*l == K)
                okay = true;
        }
    }
    cout << (okay ? "Yes" : "No") << endl;
    return 0;
}


Measured memory_bytes: 256
import std.stdio, std.string, std.conv, std.math;

void main() {
    double[] tmp = readln.split.to!(double[]);
    double a = tmp[0], b = tmp[1], x = tmp[2];
    double c = 2.0 * x / (a * a) - b;
    if (c > 0) {
        writefln("%.10f", 90.0 - atan(a / (b - c)) * 180.0 / PI);
    } else {
        double d = 2.0 * x / (a * b);
        writefln("%.10f", 90.0 - atan(d / b) * 180.0 / PI);
    }
}

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

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second

template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }

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

const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS = 1e-5;

double dp[51][10001]; // i, sum+5000 = ?¢????
int X, Y, Z;
int V[4];
vector<pii> g[51];
pii event[51];

int main() {
	while (cin >> X >> Y >> Z, X || Y || Z) {
		REP(i, X) scanf("%d", V + i);
		
		fill(event, event + Y + 1, pii(0, 0));
		REP(i, Y + 1) g[i].clear();
		
		fill(dp[0], dp[Y + 1], 0);
		
		REP(i, Z) {
			int n, e, a;
			scanf("%d %d %d", &n, &e, &a);
			if (e == 1) {
				event[n] = pii(1, a);
			}
			else {
				if (e == 3) a = -a;
				event[n] = pii(2, a);
			}
		}
		
		REP(i, Y) {
			REP(j, X) {
				int p = min(i + V[j], Y);
				int c = 0;
				
				if (event[p].fi == 1) p = min(p + event[p].se, Y);
				else if (event[p].fi == 2) c = event[p].se;
				
				g[i].push_back(pii(p, c));
			}
		}
		
		dp[0][5000] = 1;
		REP(i, Y) {
			REP(j, 10001) {
				if (dp[i][j] == 0) continue;
				
				REP(k, g[i].size()) {
					int np = g[i][k].fi;
					int nc = max(j + g[i][k].se, 5000);
					
					dp[np][nc] += dp[i][j] / X;
				}
			}
		}
		
		double ans = 0;
		FOR(i, 5000, 10001) if (dp[Y][i] != 0)
			ans += (i - 5000) * dp[Y][i];
		ans += EPS;
		
		printf("%d\n", (int)ans);
	}
	return 0;
}

Measured memory_bytes: 7152
#include <bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(ll i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define pc(x)  __builtin_popcount (x)
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define ld long double
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod 1000000007
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
#define test ll t;cin >> t; while(t--)
#define nx_pe next_permutation(s.begin(),s.end())
#define cl cout<<"\n"

    
int main()
{
   std::ios::sync_with_stdio(false);
   ll n,m;
   cin>>n>>m;
   ll a[n][m];
   rep(i,n)
   {
       rep(j,m)
       {
           char c;
           cin>>c;
           if(c=='.')a[i][j]=1;
           else a[i][j]=0;
       }
   }
   
   ll dp[n+1][m+1];
   memset(dp,0,sizeof(dp));
   dp[0][0]=1;
   f(i,1,n)
   {
       if(a[0][i]==1)dp[0][i]=dp[0][i-1];
       else
       {
           break;
       }
   }
   f(i,1,m)
   {
       if(a[i][0]==1)dp[i][0]=dp[i-1][0];
       else {
           break;
       }
   }
   f(i,1,n)
   {
       f(j,1,m)
       {
         
           if(a[i][j])
           {
               if(a[i-1][j]==1&&dp[i-1][j]!=0)dp[i][j]+=dp[i-1][j];
               if(a[i][j-1]==1&&dp[i][j-1]!=0)dp[i][j]+=dp[i][j-1];
           }
           dp[i][j]%=mod;
       }
   }
  
   cout<<dp[n-1][m-1];
}













Measured memory_bytes: 15872
n,q = gets.split.map(&:to_i)
s = gets.chomp
t,d = 2.times.map{Array.new(q)}
q.times do |i|
    t[i],d[i] = gets.chomp.split
end
t.reverse!
d.reverse!
l = 0
r = n-1
t.each_with_index do |c,i|
    if d[i] == "L"
        l += 1 if s[l] == c
        r += 1 if r < n-1 && s[r+1] == c
    else
        l -= 1 if l > 0 && s[l-1] == c
        r -= 1 if s[r] == c
    end
end
puts r-l+1

Measured memory_bytes: 46148
#include <vector>
#include <list>
#include <map>
#include <set>
#include "queue"
#include <deque>
#include <stack>
#include <numeric>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <complex>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <cassert>
#include <iostream>
using namespace std;
#define MOD 1000000007
#define MODSET(d) if ((d) >= MOD) d %= MOD;
#define MODNEGATIVESET(d) if ((d) < 0) d = (d % MOD + MOD) % MOD;
#define pii pair<long long ,long long >
#define ll  long long int
#define loop(i,n) for(ll i=0;i<n;i++)
#define loop2(i,n) for(ll i = 1;i<=n;i+=1)
#define pb push_back
#define mp make_pair
#define EPS 1e-7
using namespace std;
// JAI SHREE KRISHNA
//S :- 6 US :- 6  (Maintain US/S<=1)
//Find the holy grail in an  adventure frought with danger
//The bigger the occasion, the better the response.
//Never giving in, fighting to the end....
//Code till the end of the contest
//Check if its Binary Search
//Winning only to losing
//Losing to any one winning

int a[4001][4001],n,m,f[810][4001],s[810][4001];
void read(int &x){
    char ch;x=0;
    for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
    x=ch-'0';
}
int sum(int x,int y){
    return a[y][y]-a[x-1][y]-a[y][x-1]+a[x-1][x-1];
}



int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll a,b,c;
    cin>>a>>b>>c;
    if(a+b==c||a+c==b||c+b==a)
    {
        cout<<"Yes";
    }
    else{
        cout<<"No";
    }
    return 0;
}


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

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

    int n;
    cin >> n;
    if(n < 1000){
        cout << "ABC";
    }else{
        cout << "ABD";
    }
    cout << endl;
    return 0;
}


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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = a; i >= (b); --i)
#define trav(a, x) for(auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;



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

  int n;
  cin >> n;
  vector<pii> v(n);
  rep(i,0,n)
    cin >> v[i].first >> v[i].second;
  
  rep(i,1, n - 1) {
    if (v[i].first == v[i].second && v[i - 1].first == v[i - 1].second
        && v[i + 1].first == v[i + 1].second)
        {
          cout << "Yes";
          return 0;
        }
  }
  cout << "No";
}

Measured memory_bytes: 3628
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}
fn main() {
    let v: i32 = read();
    let h = v / (60 * 60);
    let m  = v  / 60 % 60 ;
    let s = v %  60;
    println!("{}:{}:{}", h, m, s);
}



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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { cout << #a << " = " << a << endl; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T> void operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) cin >> e; }

typedef long long ll;
int const inf = 1<<29;

int64_t const MOD = 998244353;

namespace math { namespace integer {

template<class T> T mod_mul(T x, T k, T m) { if(k == 0) { return 0; } if(k % 2 == 0) { return mod_mul((x + x) % m, k / 2, m); } else { return (x + mod_mul(x, k - 1, m)) % m; } }
template<class T> T mod_pow(T x, T n, T mod) { if(n == 0) { return 1; } if(n % 2 == 0) { return mod_pow(mod_mul(x, x, mod) % mod, n / 2, mod); } else { return mod_mul(x, mod_pow(x, n - 1, mod), mod); } }
template<class T> T extgcd(T a, T b, T& x, T& y) { T d = a; if(b != 0) { d = extgcd(b, a % b, y, x); y -= (a / b) * x;} else { x = 1, y = 0; } return d; }
template<class T> T mod_inverse(T x, T mod) { return mod_pow(x, T(mod - 2), mod); /* use fermat */ }
template<class T> T mod_inverse_composite_num_mod(T a, ll mod) { T x, y; extgcd(a, mod, x, y); return (mod + x % mod) % mod; }

}}
using namespace math::integer;

namespace math {

constexpr int64_t MaxFact = 300010;

template<class T = int64_t>
struct FactRevFactList {

  array<T, MaxFact+1> fact_;
  array<T, MaxFact+1> rev_fact_;

  FactRevFactList() {
    fact_[0] = 1;
    for(int i=1; i<MaxFact; i++) {
      fact_[i] = fact_[i-1] * i;
      fact_[i] %= MOD;
    }

    rev_fact_[MaxFact-1] = mod_pow(fact_[MaxFact-1], (T)MOD-2, MOD);

    for(int i=MaxFact-2; i>=0; i--) {
      rev_fact_[i] = rev_fact_[i+1] * (i+1);
      rev_fact_[i] %= MOD;
    }
  }

  T fact(int x) const { return fact_[x]; }
  T fact_inv(int x) const { return rev_fact_[x]; }

};

template<class T = int64_t>
struct CombinationBig {
  math::FactRevFactList<> fr_;
  T comb(T n, T r) { return (fr_.fact(n) * fr_.fact_inv(r) % MOD) * fr_.fact_inv(n-r) % MOD; }
};

}

math::CombinationBig<> cbig;

int main() {
  int64_t N, A, B, K;
  cin >> N >> A >> B >> K;
  int64_t ans = 0;
  rep(a, N + 1) {
    auto rest = K - A * a;
    if (rest < 0) continue;
    auto b = rest / B;
    if (rest % B == 0 && b <= N) {
      ans += cbig.comb(N, a) * cbig.comb(N, b) % MOD;
      ans %= MOD;
    }
  }
  cout << ans << endl;
}


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

using namespace std;

#define debug(x) cout << "\n" << (#x) << " is " << (x) << endl

int main(){
	#ifdef EVAL	
		freopen("input.txt","r",stdin);
		//freopen("output.txt","w",stdout);
	#endif
	int N, A, B;
	cin >>  N >> A >> B;
	cout << min(B, A * N);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int main(void){

  int K, X;   cin >> K >> X;
  cout << X - K + 1;
  for(int i = X - K + 2 ; i <= X + K - 1 ; i++)
    cout << " " << i;

  return 0;
}


Measured memory_bytes: 256
/*
  Esteban Arango Medina
*/
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#include <tuple>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;

using ll=long long;
#define int ll

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<string,int> si;
typedef pair<int,ii> iii;
typedef vector <si> vsi;
typedef vector <ii> vii;
typedef vector <int> vi;
typedef vector <char> vc;
typedef vector <string> vs;
typedef map <string,vs> msvs;
typedef map <string,int> msi;
typedef map <char,int> mci;
typedef map <int,int> mii;
typedef map <string,string> mss;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mp make_pair
#define endl '\n' // Normal `cout << endl` flushes the output every time wich hit performance badly
#define INF 1000000000
#define deb(x) cout<<#x<<": "<<x<<endl;
#define printArray(arr) for(auto x: arr) { cout<<x<<", "; }
#define printMatrix(mat) for(auto x: mat) { cout<<" "; printArray(x); cout<<endl; }
#define printMap(mmap) for(auto p: mmap) { cout<< p.first<<": "<<p.second<<endl; }

signed main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL); // Fast input
  #ifdef LOCAL_PROJECT
    freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
  #endif

  int T = 1; //cin>>T;
  while(T--) {
    string s, t;
    cin>>s;
    cin>>t;
    int n = s.size(), m = t.size();
    vector<vi> DP(n, vi(m, 0));
    DP[0][0] = s[0] == t[0] ? 1 : 0;
    rep(i, 1, n) { DP[i][0] = (s[i] == t[0]) ? 1 : DP[i-1][0]; }
    rep(j, 1, m) { DP[0][j] = (s[0] == t[j]) ? 1 : DP[0][j-1]; }

    rep(i, 1, n) {
      rep(j, 1, m) {
        DP[i][j] = (s[i] == t[j]) ? DP[i-1][j-1] + 1 : max(DP[i-1][j], DP[i][j-1]);
      }
    }
    // printMatrix(DP);
    string ans;
    int i = n-1, j = m-1;
    while(ans.size() < DP[n-1][m-1] && i >= 0 && j >= 0) {
      if(s[i] == t[j]) { ans.pb(s[i]); i--; j--; continue; }
      if(i - 1 >= 0 && DP[i-1][j] >= DP[i][j-1]) { i--; } else { j--; }
    }
    reverse(all(ans));
    cout<<ans;
  }
  return 0;
}

Measured memory_bytes: 70656
#include<bits/stdc++.h>
using namespace std;
int main (){
    int N,L,sum=0;cin>>N>>L;

    vector<int>flavor;

    for(int i=1;i<=N;i++){flavor.push_back(L+i-1);sum+=(L+i-1);}
    int mn = 1e9,res=0;
    for(int i=0;i<N;i++){
        if( abs(-flavor[i]) < mn){
            mn = abs(-flavor[i]);
            res = sum-flavor[i];
        }
    }
    cout<<res<<endl;
    return 0;
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------


void solve() {
    int i,j,k,l,r,x,y; string s;
    bool exit = false;
    int A, B, C;
    cin >> A >> B >> C;
    if(A==B && B==C){
        cout<<"Yes";
    }else{
        cout<<"No";
    }    
    /*cin>>N;
    vector<ll> V((N+1)*(N+1));
    FOR(x,N+1) {
            FOR(y,N+1) {
                    ll ret=1;
                    FOR(i,x) ret*=2;
                    FOR(i,y) ret*=5;
                    V.push_back(ret);
            }
    }
    sort(ALL(V));
    FORR(v,V) cout<<v<<endl;*/
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}



Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void){
    int i,j,k,l;
    int n;
    long long ave;
    long long data;
    long long sum=0;
    
    cin>>n;
    for(i=0;i<n;i++){
        cin>>data;
        sum+=data;
    }
    ave=sum/n;
    cout<<ave<<endl;
    return(0);
}

Measured memory_bytes: 1164
#include<bits/stdc++.h>
using namespace std;
typedef long long int  ll;
const ll mod = 1e9+7;
const ll mod1 = 998244353;
#define rep(i,a,b) for(ll i=a;i<b;i++)

void swap(ll &a , ll &b){
    ll t = a;
    a = b;
    b = t;
}

ll min(ll a, ll b){
    if(a<b)return a;
    return b;
}

ll max(ll a, ll b){
    if(a>b)return a;
    return b;
}

 ll pow(ll a, ll b) {
    a %= mod;
    ll ans = 1;
    while (b > 0) {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b /= 2;
    }
    return ans;
 }

 int n;
 int visited[102] = {0};
int x[102], y[102];

void dfs(int i)
{
    visited[i] = 1;
    for(int j=0; j<n; j++)
    {
        if(x[j] == x[i] || y[j]==y[i] )
        {
            if(visited[j] == 0)
            {
                dfs(j);
            }
        }
    }
}

int main(){

   ios_base :: sync_with_stdio(0);
   cin.tie(0);

   int a,b,k;
   cin>>k>>a>>b;

   int flag = 0;
   for(int i=a; i<=b; i++)
   {
        if(i%k==0)
        {
            flag = 1;
            cout<<"OK\n";
            break;
        }
   }

    if(flag == 0)
        cout<<"NG\n";

    return 0;

}


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

int main(){
  int N;
  cin >> N;
  vector<int> L(2*N);
  for(int i=0; i<2*N; i++){
    cin >> L.at(i);
  }
  sort(L.begin(), L.end());
  int Ans=0;
  for(int i=0; i<N; i++){
    Ans+=L.at(2*i);
  }
  cout << Ans << endl;
}

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

#define ms(s, n) memset(s, n, sizeof(s))
#define f(i, a, b) for (int i = (a); i <=(b); i++)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define present(t, x) (t.find(x) != t.end())
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define prec(n) fixed<<setprecision(n)
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<ll> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int MOD2 = MOD + 2; //1007681537;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) - 1);
const ld EPS = 1e-9;
inline ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
inline ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
inline ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> inline int chkmin(T& a, const T& val) {return val < a ? a = val, 1 : 0;}
template<class T> inline int chkmax(T& a, const T& val) {return a < val ? a = val, 1 : 0;}
inline ll isqrt(ll k) {ll r = sqrt(k) + 1; while (r * r > k) r--; return r;}
inline ll icbrt(ll k) {ll r = cbrt(k) + 1; while (r * r * r > k) r--; return r;}
inline void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
inline void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
inline int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
inline int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}
inline int sign(ld x) {return x < -EPS ? -1 : x > +EPS;}
inline int sign(ld x, ld y) {return sign(x - y);}
int modulo(int a, int b) { return (a % b + b) % b; }
#define db(x) cerr << #x << " = " << (x) << " ";
#define endln cerr << "\n";

int main()
{
	IOS;
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	char ch;
	cin>>ch;
	if(ch>=97){
		cout<<'a'<<endl;
	}
	else{
		cout<<'A'<<endl;
	}
	// read the stuff at the bottom
	return 0;
}
/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
	* WRITE STUFF DOWN
	* use int when constraints limits are tight
	* Time taken : global variable < pass by refernce < pass by value
	* It takes significant amt. of time in pass by value
*/





























Measured memory_bytes: 3624
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(self.n+1) # 1-indexed

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

    def add(self, i, x):
        # i: 0-indexed
        i += 1 # to 1-indexed
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    def sum(self, i, j):
        # return sum of [i, j)
        # i, j: 0-indexed
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        # return sum of [0, i)
        # i: 0-indexed
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & (-i)
        return res

import sys
import io, os
input = sys.stdin.buffer.readline
#input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

n, m, Q = map(int, input().split())
X = []
for i in range(m):
    l, r = map(int, input().split())
    l, r = l-1, r-1
    X.append((l, r, 0, i))
for i in range(Q):
    p, q = map(int, input().split())
    p, q = p-1, q-1
    X.append((p, q, 1, i))
X.sort(key=lambda x: (x[1], x[2]))
bit = BIT(550)
ans = [-1]*Q
for l, r, t, i in X:
    if t == 0:
        bit.add(l, 1)
    else:
        ans[i] = bit.sum(l, r+1)
print(*ans, sep='\n')


Measured memory_bytes: 140688
#include <iostream>
#include <vector>
#include <math.h>

using namespace std;
 
int main() {
	int ans = 0;
	int n;
	int i;
	
	cin >> n;
	
	vector<int> ary(n-1);
	for(i=0; i<n-1; i++){
		cin >> ary[i];
	}
	
	int a;
	int b;
	
	for(i=0; i<n-1; i++){
		a = ary[i];
		if(i!=0)if(a>b) a = b;
		ans += a;
		
		b = ary[i];
	}
	ans += b;
	
	
	cout << ans;
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  int c=0;
  for(int i=0;i<n;i++){
    int a;
    cin>>a;
    while(a%2==0){
      c++;
      a/=2;
    }
  }
  cout<<c<<endl;
}

Measured memory_bytes: 3636