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

template<typename T> class Dijkstra {
public:
  struct edge {
    int to; T cost;
  };
  int V;
  vector<vector<edge>> G;
  vector<T> dist;
  using pti = pair<T,int>;
  Dijkstra(int n) : V(n), G(V), dist(V, numeric_limits<T>::max()) {}
  void add(int u, int v, T cost) {
    G.at(u).push_back((edge) {v, cost});
    G.at(v).push_back((edge) {u, cost});
  }
  void solve(int s) {
    priority_queue<pti, vector<pti>, greater<pti>> Q;
    dist.at(s) = 0;
    Q.push(pti(0, s));
    while (!Q.empty()) {
      pti p = Q.top();
      Q.pop();
      int v = p.second;
      if (dist.at(v) < p.first) continue;
      for (auto &w : G.at(v)) {
        if (dist.at(w.to) > dist.at(v) + w.cost) {
          dist.at(w.to) = dist.at(v) + w.cost;
          Q.push(pti(dist.at(w.to), w.to));
        }
      }
    }
  }
};

int main() {
  int N, M;
  cin >> N >> M;
  Dijkstra<long> D(N);
  vector<vector<int>> G(N);
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    D.add(--a, --b, 1);
    G.at(a).push_back(b);
    G.at(b).push_back(a);
  }
  D.solve(0);
  for (int i = 0; i < N; i++) {
    if (D.dist.at(i) == LONG_MAX) return cout << "No" << "\n", 0;
  }
  cout << "Yes" << "\n";
  for (int i = 1; i < N; i++) {
    int res = G.at(i).at(0);
    for (auto g : G.at(i)) if (D.dist.at(g) < D.dist.at(res)) res = g;
    cout << res + 1 << "\n";
  }
}


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

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


// dp[n][k]=先頭からn人でk個を分け合うパターン数
ll dp[440][440] = {0};
ll a[440];
int n;




int main() {
    cin >> n;
    rep(i, n) cin >> a[i];

    // dpテーブル初期化
    rep(i, 440) rep(j, 440) dp[i][j] = 0;

    FOR(i, 1, n) FOR(j, 0, n-i) {
        ll tmp = LONG_MAX;
        ll sum = 0;
        FOR(k, j, j+i) {
            tmp = min(tmp, dp[j][k]+dp[k+1][j+i]);
            sum += a[k];
        }
        sum += a[j+i];
        dp[j][j+i] = tmp+sum;
    }

    cout << dp[0][n-1] << endl;

    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
///Welcome to Nasif's Code
#define bug printf("bug\n");
#define bug2(var) cout<<#var<<" "<<var<<endl;
#define co(q) cout<<q<<endl;
#define all(q) (q).begin(),(q).end()
typedef long long int ll;
typedef unsigned long long int ull;
const int MOD = (int)1e9+7;
const int MAX = 1e6;
#define pi acos(-1)
#define inf 1000000000000000LL
#define FastRead    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main()
{
    FastRead
    //freopen("output.txt", "w", stdout);
    ll n,k;
    cin>>n>>k;
    vector<pair<int,int> >v;
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        v.push_back({a,b});
    }
    sort(all(v));
    ll l=0;
    for(int i=0;i<n;i++){
        l+=v[i].second;
        if(k<=l){
            cout<<v[i].first<<endl;
            return 0;
        }
    }

    return 0;
}


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

using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<LD, LD> PLDLD;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define CLR(a) memset((a), 0 ,sizeof(a))
#define ALL(a) a.begin(),a.end()

const double eps=1e-5;
const long long INF=(LL)(1e9)*(LL)(1e9);

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<vector<int>> mp(n,vector<int>(n));
    REP(i,n)
    {
        REP(j,n)
        {
            cin>>mp[j][i];
        }
    }
    LL sum=0;
    bool flag=1;
    REP(i,n)
    REP(j,n)
    REP(k,n)
    {
        if(mp[i][j]>mp[i][k]+mp[k][j])
        {
            flag=0;
            break;
        }
    }

    if(!flag)
    {
        cout<<-1<<endl;
        return 0;
    }
    
    REP(i,n)
    REP(j,n)
    {
        flag=1;
        REP(k,n)
        {
            if(i==k||j==k||i==j) continue;
            if(mp[i][j]==mp[i][k]+mp[k][j])
            {
                //cout<<"d:"<<i<<" "<<j<<" "<<k<<endl;
                flag=0;
                break;
            }
        }
        if(flag)
        {
            //cout<<"a:"<<i<<" "<<j<<endl;
            sum+=mp[i][j];
        }
    }
    cout<<sum/2<<endl;
}


Measured memory_bytes: 640
/**
DufauX-XuafuD
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define reset(x) memset(x,-1,sizeof(x))
#define CheckBit(a,b) (a&(1ll<<b))
#define SetBit(a,b) a=(a|(1ll<<b))
#define UnSetBit(a,b) a=(a&(~(1ll<<b)))
#define maxx 10000006
#define PI 2*acos(0.0)
const long long INF = 2000000000000000000LL;	// 2e18
const int inf = 0x3f3f3f3f;	// 1061109567
const long double EPS = 1e-9;
//bitset<maxx/2>vis;
//bitset<maxx>pr;
//int mobi[maxx+10];
//vector<ll>prime;
//void sieve(){
//    ll x=maxx/2, y=sqrt(maxx)/2;
//    for(ll i=1;i<=y;i++){
//        if(vis[i]==0){
//            for(ll j=(i*(i+1)*2);j<x;j+=(2*i)+1)
//                vis[j]=1;
//        }
//    }
//    prime.push_back(2);
//    for(ll i=3;i<maxx;i+=2)
//        if(vis[i/2]==0)
//        prime.push_back(i);
//}
//void generate_mobius()
//{
//    for(int i=0;i<maxx;i++)mobi[i]=1;
//    for(int i=2;i<maxx;i++){
//        if(!pr[i]){
//            mobi[i]*=-1;
//            for(int j=i+i;j<maxx;j+=i){
//                pr[j]=1;
//                mobi[j]*=(j%(i*i)?-1:0);
//            }
//        }
//    }
//}
//bool isprime(ll a)
//{
//    if(a==1)return false;
//    if(a==2)return true;
//    if(a%2==0)return false;
//    for(ll i=0;i<prime.size() && prime[i]*prime[i]<=a;i++)
//        if(a%prime[i]==0)return false;
//    return true;
//}
/* Calculate ( a*b ) %c */
inline ll mulmod(ll a, ll b, ll c) {
    ll ret = 0 , cur = a % c ;
    while(b) { if(b%2) ret=(ret+cur)%c; cur=(cur<<1)%c; b=b>>1; }
    return ret%c;
}
//Calculate (b^p)%m || modular inverse: b^-1 = bigmod(b, m-2, m)
inline ll bigmod(ll b, ll p, ll m){
    ll ret = 1, cur = b % m;
    while(p) { if(p&1) ret=(ret*cur)%m; cur=(cur*cur)%m; p=p>>1; }
    return ret;
}
inline ll modulo(ll a,ll b,ll c) { //Same as big mod, use for numbers over 1e10
    ll ret = 1 , cur = a%c ;
    while(b) { if(b%2) ret=mulmod(ret,cur,c); cur=mulmod(cur,cur,c); b=b>>1; }
    return ret%c ;
}
inline ll power(ll b, ll p){
    ll ret = 1, cur = b;
    while(p) { if(p&1) ret=(ret*cur); cur=(cur*cur); p=p>>1; }
    return ret;
}
ll lcm(ll a,ll b)
{
    return (a/__gcd(a,b))*b;
}
ll gcd(ll a,ll b)
{
    return __gcd(a,b);
}
void Dufaux()
{
    ll arr[4];
    cin>>arr[0]>>arr[1]>>arr[2];
    sort(arr,arr+3);
    if(arr[0]+arr[1]==arr[2]){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}
int main()
{
    FastIO;
	///sieve();
	///generate_mobius();
	int test=1;
	while(test--){
        Dufaux();
	}
	return 0;
}






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

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

const string YES = "Yes";
const string NO = "No";
const ll mod = 1e9+7;


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

    ll a,b; cin >> a >> b;
    if ((a+b)%2==0){
        cout << (a+b)/2;
        return 0;
    }
    cout << "IMPOSSIBLE";

    return 0;
    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
using namespace std;
 
int main()
{
ios_base::sync_with_stdio(false);
    cin.tie(NULL);
string s,t;
cin>>s>>t;
int mini=1000;
if(s.size()<t.size())
{
	return 0;
}
for(int i=0;i<s.size()-t.size()+1;i++)
{   int count=0;
	for(int j=0;j<t.size();j++)
	{
		if(s[i+j]!=t[j])count++;
	}
	mini=min(mini,count);
}
cout<<mini<<endl;
}

 
 

 


Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define INF 1e9

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

    int A, B;
    cin >> A >> B;

    if ((A*B) % 2 != 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

int main() {
  int N;
  cin >> N;

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

  cout << "AC x " << count(ans.begin(), ans.end(), "AC") << endl;
  cout << "WA x " << count(ans.begin(), ans.end(), "WA") << endl;
  cout << "TLE x " << count(ans.begin(), ans.end(), "TLE") << endl;
  cout << "RE x " << count(ans.begin(), ans.end(), "RE") << endl;
  return 0;
}

Measured memory_bytes: 6420
#include<bits/stdc++.h>
#include<stdio.h>
#include<vector>
#include<string>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#include<set>
#define ws " "
#define nl "\n"
#define tc ll test; cin>>test; while(test--)
#define f(i, a, b) for(ll i = a; i<b; i++)
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
using namespace std;

#define pid pair<int, double>
bool compare(pid a, pid b)
{
	//for descending order replace with a.roll >b.roll
   if(a.ss < b.ss)
        return 1;
	else
		return 0;
}


void fillPrefixSum(int arr[], int n, int prefixSum[])
{
    prefixSum[0] = arr[0];
    for (int i = 1; i < n; i++)
        prefixSum[i] = prefixSum[i-1] + arr[i];

}

void SieveOfEratosthenes(ll n, bool prime[], bool primesquare[], ll a[])
{
    for (ll i = 2; i <= n; i++)
        prime[i] = true;
    for (ll i = 0; i <= (n * n + 1); i++)
        primesquare[i] = false;
    prime[1] = false;

    for (ll p = 2; p * p <= n; p++) {
        if (prime[p] == true) {
            for (ll i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }

    ll j = 0;
    for (ll p = 2; p <= n; p++) {
        if (prime[p]) {
            a[j] = p;

            primesquare[p * p] = true;
            j++;
        }
    }
}

ll countDivisors(ll n)
{
    if (n == 1)
        return 1;

    bool prime[n + 1], primesquare[n * n + 1];

    ll a[n]; // for storing primes upto n
    SieveOfEratosthenes(n, prime, primesquare, a);

    ll ans = 1;

    for (ll i = 0;; i++) {
        if (a[i] * a[i] * a[i] > n)
            break;
        ll cnt = 1; // cnt is power of prime a[i] in n.
        while (n % a[i] == 0) // if a[i] is a factor of n
        {
            n = n / a[i];
            cnt = cnt + 1; // incrementing power
        }

        ans = ans * cnt;
    }
    if (prime[n])
        ans = ans * 2;

    // Second case
    else if (primesquare[n])
        ans = ans * 3;

    // Third casse
    else if (n != 1)
        ans = ans * 4;

    return ans; // Total divisors
}

bool checkLast(ll n)
{
    if(n%10==0)
        return true;
    return false;

}
bool checkPrime(ll n)
{
    // Corner cases
    if (n <= 1)  return false;
    if (n <= 3)  return true;

    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n%2 == 0 || n%3 == 0) return false;

    for (ll i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
           return false;

    return true;
}

struct parts{
int start, en;
//bool included;

};

struct c{
ll num;
ll type;
};

int checkFor(ll m, c arr[], int n)
{
    f(i, 0, n)
    {
        if(arr[i].num==m)
            return i;
    }

}
void solve()
{

    string s1,s2;
    cin>>s1>>s2;
    ll mis = 0;

    ll l = s1.size();

    f(i, 0, l)
    {
        if(s1[i]!=s2[i])
            mis++;
    }
    cout<<mis<<nl;
}

int main()
{
    fastIO;


  //tc
    solve();
}


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

int main(){
  string str;
  cin >> str;
  int count=0;
  for (int i = 0; i < str.size(); i++) {
    if (str.at(i) == '2') {
      count++;
    }
  
  }

  cout <<count<< endl;


}


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

#define rep(i, n) for(int i = 0;i < n; i++)
typedef long long ll;

using namespace std;

int main () {
   int a, b, c, d; cin >> a >> b >> c >> d;

   bool ans = true;

   int cot = 0;
   while(1) {
      if(cot%2 == 0) {
         c -= b;
      } else {
         a -= d;
      }

      if(a <= 0) {
         ans = true;
         break;
      } else if(c <= 0) {
         ans = false;
         break;
      }

      cot ++;
   }

   if(ans) {
      cout << "No" << endl;
   } else {
      cout << "Yes" << endl;
   }
}
   


Measured memory_bytes: 3632
#include <algorithm>
#include <cassert>
#include <deque>
#include <iostream>
#include <map>
#include <vector>

static const int IINF = 1 << 30;
static const long long LINF = 1LL << 60;
static const long long MOD = 1.0e+9 + 7;

template <typename T> std::vector<T> vectors(std::size_t n, T val) {
  return std::vector<T>(n, val);
}

template <typename T, typename... Args>
auto vectors(std::size_t n, Args... args) {
  return std::vector<decltype(vectors<T>(args...))>(n, vectors<T>(args...));
}

template <class T> inline bool chmin(T &a, const T &b) {
  return (a > b) ? a = b, true : false;
}

template <class T> inline bool chmax(T &a, const T &b) {
  return (a < b) ? a = b, true : false;
}

template <class T> inline void chadd(T &a, const T &b) {
  a += b, a %= MOD;
  if (a < 0)
    a += MOD;
}

int main() {
  // Input
  int numChild;
  int numCandy;
  std::cin >> numChild >> numCandy;
  assert(1 <= numChild and numChild <= 100);
  assert(0 <= numCandy and numCandy <= 1.0e+5);
  std::vector<long long> upper(1 + numChild, -1);
  for (int i = 1; i <= numChild; ++i) {
    std::cin >> upper[i];
    assert(0 <= upper[i] and upper[i] <= numCandy);
  }

  // Initialization
  std::vector<std::vector<long long>> dp(1 + numChild);
  for (int i = 1; i <= numChild; ++i)
    dp[i].assign(1 + numCandy, 0LL);

  // Initial condition
  for (int k = 0; k <= upper[1]; ++k)
    dp[1][k] = 1;

  // DP main
  for (int i = 1; i < numChild; ++i) {
    long long currentSum = 0LL;
    std::deque<long long> dque;
    for (int k = 0; k <= numCandy; ++k) {
      if (k <= upper[i + 1]) {
        dque.push_back(dp[i][k]);
        chadd(currentSum, dque.back());
        dp[i + 1][k] = currentSum;
      } else {
        assert(dque.size() == (size_t)upper[i + 1] + 1);
        dque.push_back(dp[i][k]);
        chadd(currentSum, dque.back());
        chadd(currentSum, -dque.front());
        assert(currentSum >= 0);
        dque.pop_front();
        dp[i + 1][k] = currentSum;
      }
    }
  }

  // Output
  // long long res = 0LL;
  // for (int k = 0; k <= upper[numChild]; ++k) {
  //   chadd(res, dp[numChild][k]);
  // }
  // std::cout << res << std::endl;
  std::cout << dp[numChild][numCandy] << std::endl;

  return 0;
}


Measured memory_bytes: 79520
h,w=map(int,input().split())
a=[input()for _ in range(h)]
dp=[[0]*w for _ in range(h)]
dp[0][0]=1
for i in range(h):
    for j in range(w):
        if i>0 and a[i-1][j]!='#':
            dp[i][j]+=dp[i-1][j]
        if j>0 and a[i][j-1]!='#':
            dp[i][j]+=dp[i][j-1]
        dp[i][j]=dp[i][j]%(10**9+7)
print(dp[-1][-1])

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

long long A, B;
#define N_BITS 60
long long C;

int main() {
  cin >> A >> B;
  if(A == B) { cout << 1 << endl; return 0; }
  int k; for(k = N_BITS - 1; k >= 0; --k) {
    if(B & (1LL << k)) break;
  }
  int i; for(i = k; i >= 0; --i) {
    if(~A & B & (1LL << i)) break;
  }
  int j; for(j = i - 1; j >= 0; --j) {
    if(B & (1LL << j)) break;
  }
  long long a = A, b = B | ((1LL << (j + 1)) - 1),
    c = A + (1LL << i), d = A | ((1LL << (i + 1)) - 1);
  if(b < c) cout << b - a + 1 + d - c + 1 << endl;
  else cout << d - a + 1 << endl;
  return 0;
}


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

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

template <typename T>
void printv(const vector<T> &v)
{
    int sz = v.size();
    for (int i = 0; i < sz; i++)
    {
        cout << v[i] << " \n"[i == sz - 1];
    }
}

// cout << (f ? "Yay!" : ":(") << endl;

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

    int n, k;
    cin >> n >> k;
    if (k == 1)
    {
        cout << 0 << endl;
        return 0;
    }
    cout << n - k << endl;
}


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

int main(void) {
	int N, K, h;
	cin >> N >> K;

	int ans = 0;
	for (int i = 0; i < N; ++i) {
		cin >> h;
		if (h >= K)
			++ans;
	}

	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 256
from sys import stdin
n,k = map(int,stdin.readline().split())
p = list(map(int,stdin.readline().split()))
c = list(map(int,stdin.readline().split()))

ans = -float("inf")
def helper(index):
    visited  = {index}
    looplen = 1
    looptotal = c[index]
    while p[index]-1 not in visited:
        nextindex = p[index] - 1
        looplen += 1
        looptotal += c[nextindex]
        visited.add(nextindex)
        index = nextindex
    return (looplen,looptotal)

for i in range(n):
    looplen,looptotal = helper(i)
    if looptotal >= 0:
        cur = looptotal*((k//looplen)-1) if k >= looplen else 0
        remain = looplen + (k%looplen) if k >= looplen else k
    else:
        cur = 0
        remain = looplen
    curmax = -float("inf")
    curindex = i
    for _ in range(remain):
        nextindex = p[curindex]-1
        cur += c[nextindex]
        curmax = max(curmax,cur)
        curindex = nextindex
    ans = max(ans,curmax)
print(ans)

Measured memory_bytes: 111444
def judge(N, Y):
	for i in range(0, N+1):
		for j in range(0, N-i+1):
			if 10000*i+5000*j+1000*(N-i-j) == Y:
				return str(i) + ' ' + str(j) + ' ' + str(N-i-j)
	return '-1 -1 -1'

N, Y = map(int, raw_input().split())
print judge(N, Y)

Measured memory_bytes: 2692
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
 
using std::cin;
using std::cout;
using std::endl;
 
using std::string;
using std::pair;
 
using std::vector;
using std::sort;

long gcd(long a,long b){
    if(a<b){
        return gcd(b,a);
    }
    long m=a%b;
    if(m==0){
        return b;
    }
    return gcd(b,m);
}
 
int main(){
    long n,x;
    cin >> n >> x;
    long k=gcd(n,x);
    cout << k*3*(n/k-1) << endl;
    return 0;
}

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

long long int F[87] = {2,1,3};

int main()
{
    int m;
    cin >> m;
    for (int i = 3; i <= 86; i++) {
        F[i] = F[i-1] + F[i-2];
    }
    cout << F[m] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>

using namespace std;
typedef long double ld;

const ld eps = 1e-15;

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        ld xa, ya, ra, xb, yb, rb;
        cin >> xa >> ya >> ra >> xb >> yb >> rb;

        ld dis = sqrt(pow(xa - xb, 2) + pow(ya - yb, 2));
        if (dis < abs(ra - rb)) {
            cout << (ra > rb ? 2 : -2) << endl;
        } else if (dis <= (ra + rb) + eps) {
            cout << 1 << endl;
        } else {
            cout << 0 << endl;
        }
    }
    return 0;
}


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

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

#define FOR(i, n, m) for (ll(i) = (m); (i) < (n); ++(i))
#define REP(i, n) FOR(i, n, 0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll)1e15;

ll a[100005];
bool u[100005];

int main()
{
    int N;
    cin >> N;
    REP(i, N)
    {
        cin >> a[i];
        a[i]--;
        u[i] = false;
    }

    int index = 0;
    int num = -1;
    for (int i = 0; !u[index]; ++i)
    {
        if (index == 1)
        {
            num = i;
            break;
        }
        u[index] = true;
        index = a[index];
    }
    cout << num << endl;
    return 0;
}

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

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define MOD 1000000007
#define INF 1e7
#define LINF 1e15
typedef long long ll;
typedef long double ld;
using Graph = vector<vector<int>>;
// 'a' = 97 'z' = 122 => 'a' = 0 'z' = 25

int main() {
    double x; cin >> x;
    int ans = floor(x / 500) * 1000;
    x -= floor(x/500) * 500;
    ans += floor(x / 5) * 5;
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 256
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

l = [0]*4
for _ in range(3):
    a, b = map(int, input().split())
    l[a-1] += 1
    l[b-1] += 1

l = sorted(l)
if l[0] == 1 and l[1] == 1 and l[2] == 2 and l[3] == 2:
    print("YES")
else:
    print("NO")


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a, b, c;
  int tmp = 0;
  cin >> a >> b >> c;
  
  tmp = b;
  b = a;
  a = tmp;
  
  tmp = c;
  c = a;
  a = tmp;
  
  cout << a << ' ' << b << ' ' << c << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

using namespace std;

#define int long long
#define endl '\n'
#define maxn 100010
const int MOD = 1000000007;

void solve() {
    int n;
    cin >> n;
    
    n  = n % 10;
    set<int> st = {2, 4,5,7,9};
    if(st.find(n) != st.end())cout << "hon";
    else if(n == 3) cout << "bon";
    else cout << "pon";
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}


Measured memory_bytes: 3660
use proconio::*;
use num_integer::gcd;

fn run() {
    input! {
        n: u64,
    }
    let mut ans = 0;
    for a in 1..=n {
        for b in 1..=n {
            for c in 1..=n {
                ans += gcd(gcd(a, b), c);
            }
        }
    }
    println!("{}", ans);
}

fn main() {
    run();
}

Measured memory_bytes: 2172
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));

VI sum;

int count(int a) {
	int cnt = 0;
	REP(i , sum.size()) {
		//cout << i << endl;
		if ((sum[i]&a) == a) {
			cnt++;
		}
	}
	return cnt;
}
signed main(){
cin.tie(0);
ios::sync_with_stdio(false);

	int N, K;
	cin >> N >> K;
	VI A(N);
	REP(i, N) {
		cin >> A[i];
	}
	REP(i, N) {
		int cnt = 0;
		FOR(j, i, N) {
			 cnt += A[j];
			 sum.push_back(cnt);			
		}
	}
	int ans = 0;
	for (int i = 40; i >= 0; i--) {
		if (count(ans|(1LL<<i))>=K)
			ans += (1LL << i);
	}

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



Measured memory_bytes: 6384
//package BeginnerContest148;

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        FastReader sc = new FastReader();
        PrintWriter pw = new PrintWriter(System.out);
        int n = sc.nextInt();
        int[] list = new int[n];
        for(int i = 0; i<n; i++) list[i] = sc.nextInt();
        int curr = 1;
        int ans = 0;
        for(int i = 0; i<n; i++){
            if(curr != list[i]){
                ans++;
            }
            else{
                curr++;
            }
        }
        if(ans == n) pw.println(-1);
        else{
            pw.println(ans);
        }
        pw.close();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

Measured memory_bytes: 47440
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		long sum = 0;
		for (int i = 0; i < m; i++) {
			sum += sc.nextInt();
		}
		sc.close();
		if (n >= sum) {
			System.out.println(n - sum);
		} else {
			System.out.println(-1);
		}
	}
}


Measured memory_bytes: 38016
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Math;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            A();
        }

        static void A()
        {
            var ABCXY = ReadSplitInt();
            var A = ABCXY[0];
            var B = ABCXY[1];
            var C = ABCXY[2];
            var X = ABCXY[3];
            var Y = ABCXY[4];
            var xy = Max(X, Y) * 2;

            var min = int.MaxValue;
            for (int i = xy; i >= 0; i-=2)
            {
                var c = i * C;
                var x = (X - i / 2);
                var y = (Y - i / 2);

                var a = 0;
                var b = 0;

                if (x > -1) a = x * A;
                if (y > -1) b = y * B;

                min = Min(a + b + c, min);
            }
            Println(min);
        }

        static List<int> ReadLines(int n)
        {
            var l = new List<int>();
            for (int i = 0; i < n; i++)
            {
                l.Add(ReadInt());
            }
            return l;
        }

        static IEnumerable<int> Range(int start, int stop)
        {
            if (start < 0 || stop < 0 || start > stop || (start <= 0 && stop <= 0))
                return new List<int>();

            return Enumerable.Range(start, stop - start);
        }

        static bool IsDigit(string str)
        {
            var i = 0;
            return int.TryParse(str, out i);
        }

        static int SumDigits(long num)
        {
            return num.ToString().Select(x => x.ToString()).Sum(int.Parse);
        }

        static int[] ToIntArray(string str)
        {
            return str.Select(x => x.ToString()).Select(int.Parse).ToArray();
        }

        static int Gcd(int a, int b) => b == 0 ? a : Gcd(b, a % b);

        static bool IsPrime(int x)
        {
            if (x <= 1 || (x != 2 && x % 2 == 0)) return false;
            if (x == 2) return true;

            for (int i = 3; i < x; i += 2)
                if (x % i == 0) return false;

            return true;
        }

        static string Read() => Console.ReadLine();
        static int ReadInt() => int.Parse(Read());
        static long ReadLong() => long.Parse(Read());

        static List<string> ReadSplit() => Read().Split().ToList();
        static List<int> ReadSplitInt() => Read().Split().Select(int.Parse).ToList();
        static List<long> ReadSplitLong() => Read().Split().Select(long.Parse).ToList();

        static void Print(object value) => Console.Write(value.ToString());
        static void Println(object value) => Console.WriteLine(value.ToString());

        static string Join<T>(IEnumerable<T> list) => string.Join("", list);
    }

    public static class MyExtensions
    {
        public static string Slice(this string str, int start = 0, int stop = 0)
        {
            if (start > str.Length || stop > str.Length || start < 0 || stop < 0)
                return "";

            if (stop == 0) stop = str.Length;
            return str.Substring(start, stop - start);
        }
    }
}

Measured memory_bytes: 11348
#include <queue>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
const vector<int> dx = { 1, 0, -1, 0 };
const vector<int> dy = { 0, 1, 0, -1 };
int H, W, sx, sy, gx, gy, comp_cnt; vector<int> comp_size; vector<vector<int> > dist, used; vector<vector<int> > comp; vector<string> s;
void comp_dfs(int x, int y) {
	comp[x][y] = comp_cnt;
	++comp_size[comp_cnt];
	for (int i = 0; i < 4; ++i) {
		int tx = x + dx[i], ty = y + dy[i];
		if (0 <= tx && tx < H && 0 <= ty && ty < W && s[tx][ty] == 'X' && comp[tx][ty] == -1) {
			comp_dfs(tx, ty);
		}
	}
}
bool reach(int x, int y, int rem) {
	if (x == gx && y == gy) return true;
	if (dist[x][y] > rem) return false;
	used[x][y] = rem;
	for (int i = 0; i < 4; ++i) {
		int tx = x + dx[i], ty = y + dy[i];
		if (0 <= tx && tx < H && 0 <= ty && ty < W && s[tx][ty] != '#' && (s[tx][ty] != 'X' || comp_size[comp[tx][ty]] >= 2) && used[tx][ty] == -1) {
			bool ok = true;
			for (int j = 0; j < 4 && ok; ++j) {
				int rx = tx + dx[j], ry = ty + dy[j];
				if (0 <= rx && rx < H && 0 <= ry && ry < W && used[rx][ry] >= rem + 2) ok = false;
			}
			if (ok) {
				if (s[tx][ty] == 'X') comp_size[comp[tx][ty]] -= 2;
				if (reach(tx, ty, rem - 1)) return true;
				if (s[tx][ty] == 'X') comp_size[comp[tx][ty]] += 2;
			}
		}
	}
	used[x][y] = -1;
	return false;
}
int main() {
	while (cin >> W >> H, H != 0) {
		s = vector<string>(H);
		for (int i = 0; i < H; ++i) {
			cin >> s[i];
			if (s[i].find('S') != string::npos) sx = i, sy = s[i].find('S');
			if (s[i].find('G') != string::npos) gx = i, gy = s[i].find('G');
		}
		comp = vector<vector<int> >(H, vector<int>(W, -1));
		comp_size.clear();
		comp_cnt = 0;
		for (int i = 0; i < H; ++i) {
			for (int j = 0; j < W; ++j) {
				if (s[i][j] == 'X' && comp[i][j] == -1) {
					comp_size.push_back(0);
					comp_dfs(i, j);
					++comp_cnt;
				}
			}
		}
		dist = vector<vector<int> >(H, vector<int>(W, -1));
		dist[gx][gy] = 0;
		queue<pair<int, int> > que; que.push(make_pair(gx, gy));
		while (!que.empty()) {
			pair<int, int> u = que.front(); que.pop();
			for (int i = 0; i < 4; ++i) {
				int tx = u.first + dx[i], ty = u.second + dy[i];
				if (0 <= tx && tx < H && 0 <= ty && ty < W && dist[tx][ty] == -1) {
					dist[tx][ty] = dist[u.first][u.second] + 1;
					que.push(make_pair(tx, ty));
				}
			}
		}
		used = vector<vector<int> >(H, vector<int>(W, -1));
		int steps = 1;
		while (!reach(sx, sy, steps)) ++steps;
		cout << steps << '\n';
	}
	return 0;
}


Measured memory_bytes: 3184
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
#define FI(i, a, b) for (int i = (a); i <= (b); ++i)
#define FD(i, b, a) for (int i = (b); i >= (a); --i)
#define DEBUG(x) cerr << #x << ": " << (x) << endl;

int n, d;
vector<int> points[15], a;
int dist(int i, int j) {
  int tot = 0;
  for (int k = 1; k <= d; k++) {
    int x = points[i][k] - points[j][k];
    tot += x * x;
  }
  return tot;
}

int main() {
  cin >> n >> d;
  for (int i = 1; i <= 10000; i++) a.push_back(i * i);
  FI(i, 1, n) {
    points[i].resize(d + 1);
    FI(j, 1, d) scanf("%d", &points[i][j]);
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
      int d = dist(i, j);
      if (binary_search(a.begin(), a.end(), d)) ans++;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 384
N = int(input())
A=sorted(list(map(int,input().split())))
dp = [[0 for i in range(N)] for j in range(2)]
dp[0][0] = A[0]
dp[1][0] = -A[0]
for i in range(1,N-1):
    dp[0][i] = max(dp[0][i-1]+A[i],dp[1][i-1]-A[i])
    dp[1][i] = max(dp[0][i-1]-A[i],dp[1][i-1]+A[i])
dp[0][-1] = max(dp[0][-2]+A[-1],dp[1][-2]-A[-1])
print(max(dp[0][-1],dp[1][-1]))

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

int main(){
    int n,a,ans = 0;
    cin >> n;
    vector<int> num(1000001,0);
    for(int i = 0;i < n;i++){
        cin >> a;
        num[a]++;
    }
    for(int i = 1;i<= 1000000;i++){
        if(num[i] >= 1){
            if(num[i] == 1)ans++;
            for(int j = i;j <= 1000000;j += i){
                num[j] = 0;
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 7184
import sys
import math
def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()
n = II()
ans = ""
while(n>0):
	ans+=chr(96+n%26) if n%26>0 else 'z'
	if n%26 == 0:
		n//=26
		n-=1
	else:
		n//=26
print(ans[:][::-1])


Measured memory_bytes: 9192
#include <bits/stdc++.h>
#define PREP(i, s, x) for(ll i = (s); i < (x); i++)
#define MREP(i, s, x) for(ll i = (s); i >= (x); i--)
#define REP(i, x) PREP(i, 0, x)
using namespace std;
using ll = long long;
typedef long long ll;
typedef pair<ll, ll> P;
template<typename T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template<typename T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}

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

constexpr ll INF = (1ll << 60);
constexpr ll MOD = 998244353ll;

double absld(double a, double b){
    double res = a - b;
    if(res < 0) res *= -1;
    return res;
}

int main() {
    ll a, b;
    ll h, m;
    cin >> a >> b >> h >> m;

    double a_kakudo = (double)(30 * h) + (double)0.5 * (double)m;
    double b_kakudo = (double)(6 * m);

    double kakudo = absld(a_kakudo, b_kakudo);

    kakudo = (kakudo * M_PI) / (double)180;

    double ans = a * a + b * b - (double)(2 * a * b) * cos(kakudo);

    ans = sqrt(ans);
    
    // 小数点以下の桁数を指定
    cout << fixed << setprecision(10);
    // 変更するまで10桁のまま。

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

Measured memory_bytes: 4160
#include <bits/stdc++.h>
#define ll long long
#define N 100010
#define M 1010

using namespace std;


int read() {
	int s = 0, f = 0; char ch = getchar();
	while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}

int main() {
	int x = 0, k = read();
	for (int i = 1; i <= k; i++) {
		x = x * 10 + 7;
		x %= k;
		if (x == 0) {
			cout << i << "\n";
			return 0;
		}
	}
	cout << -1 << "\n";
}

Measured memory_bytes: 3632
//
// Created by rajshah9914 on 05/04/20.
//

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,k,c;
    cin>>n>>k>>c;
    string s;
    cin>>s;
    int m1=0,m2=k-1;
    int last=INT_MIN;
    int g1[200000],g2[200000];
    for(int i=0;i<n && m1<k;i++)
    {
        if(s[i]=='o' && i>last+c)
        {
            g1[m1++]=i;
            last=i;
        }
    }
//    for(int i=0;i<n;i++)
//        cout<<g1[i]<<" ";
//    cout<<endl;
    last=INT_MAX;
    for(int i=n-1;i>=0 && m2>=0;i--)
    {
        if(s[i]=='o' && i<last-c)
        {
            last=i;
            g2[m2--]=i;
        }
    }
    for(int i=0;i<k;i++)
    {
        if(g1[i]==g2[i])
            cout<<g1[i]+1<<endl;
    }
}

Measured memory_bytes: 3332
#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7,inv2=(mod+1)/2;
long long n,q,a[3333],x[3333],y[3333],pw[3333],ipw[3333],dp[3333][3333],cur,ans; 
int main()
{
	scanf("%lld%lld",&n,&q);
	for (long long i=1;i<=n;i++) scanf("%lld",&a[i]);
	for (long long i=1;i<=q;i++) 
	{
		scanf("%lld%lld",&x[i],&y[i]);
		if (x[i]>y[i]) swap(x[i],y[i]);
	}
	pw[0]=1;
	for (long long i=1;i<=3000;i++)
	{
		pw[i]=pw[i-1]*2%mod;
		ipw[i]=ipw[i-1]*inv2%mod;
	}
	for (long long i=1;i<=n;i++)
	{
		for (long long j=i+1;j<=n;j++)
		{
			dp[i][j]=1;
		}
	}
	for (long long i=q;i>=1;i--)
	{
		cur=(dp[x[i]][y[i]]+dp[y[i]][x[i]])*inv2%mod;
		dp[x[i]][y[i]]=dp[y[i]][x[i]]=cur;
		for (long long j=1;j<=n;j++)
		{
			if (j==y[i] || j==x[i]) continue;
			cur=(dp[x[i]][j]+dp[y[i]][j])*inv2%mod;
			dp[x[i]][j]=dp[y[i]][j]=cur;
			cur=(dp[j][x[i]]+dp[j][y[i]])*inv2%mod;
			dp[j][x[i]]=dp[j][y[i]]=cur;
		}
	}
	for (long long i=1;i<=n;i++)
	{
		for (long long j=1;j<=n;j++)
		{
			if (i==j) continue;
			if (a[i]>a[j]) ans=(ans+dp[i][j]*pw[q])%mod;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 80256
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define dbg(x) cout<<#x<<":"<<x<<endl
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;

int main(){
  ll n,d,a;
  cin>>n>>d>>a;
  vector<P> x(n);
  for(ll i=0;i<n;i++){
    cin>>x[i].fi>>x[i].se;
  }
  sort(all(x));
  ll ans=0;
  ll nowcnt=0;
  vector<ll> micnt(n);
  for(int i=0;i<n;i++){
    ll xi=x[i].fi;
    ll hi=x[i].se;
    ll pluscnt=max((hi-(nowcnt*a)+a-1)/a,0LL);
    nowcnt+=pluscnt;
    ans+=pluscnt;
    ll l=i,mid,r=n;
    while(r-l>1){
      mid=(r+l)/2;
      if(x[mid].fi<=xi+d*2)l=mid;
      else r=mid;
    }
    micnt[l]+=pluscnt;
    nowcnt-=micnt[i];
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c,d[256];
  cin>>a>>b>>c;
  d[0]=a;
  d[1]=b;
  d[2]=c;
  sort(d,d+3);
  if(d[0]+d[1]==d[2]){
    cout<<"Yes"<<'\n';
  }
  else{
    cout<<"No"<<'\n';
  }
  return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
while n != 0:
    val = pow(n, m)
    x = ["", "Man", "Oku", "Cho", "Kei", "Gai", "Jo", "Jou", "Ko", "Kan", "Sei", "Sai", "Gok", "Ggs", "Asg", "Nyt",
         "Fks", "Mts"]
    ans = []
    for i in x:
        if val % 10000 > 0:
            ans.append(str(val % 10000) + i)
        val //= 10000
    print(''.join(ans[::-1]))
    n, m = map(int, input().split())


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


int main(){
    int n, x = 0, ans = 0;
    string s;
    cin >> n >> s;
    for(int i = 0; i < n; i++){
        if(s[i] == 'I') x++;
        if(s[i] == 'D') x--;
        ans = max(ans, x);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#python3
from itertools import permutations
n=int(input())
p=[int(i) for i in input().split()]
q=[int(i) for i in input().split()]

def f(lis):
  cnt=0
  for i in permutations(range(1,n+1)):
    cnt+=1
    if i == tuple(lis):
      return cnt

print(abs(f(p)-f(q)))


Measured memory_bytes: 3060
#ifdef _MSC_VER
#include "stdc++.h"
#endif
#ifdef __GNUC__
#include<bits/stdc++.h>
#endif
using namespace std;

using ll = long long;

//constant
const double EPS = 1e-10;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, s, e) for (ll i = s; i < e; i++)
#define RREP(i, n) for (ll i = n; i >= 0; i--)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(), (x).rend()

//debug
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define DEBUG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl;

// vector
//template<typename T> vector<vector<T>> vv(ll H, ll W, T v) { return vector<vector<T>> vec(H, vector<T>(W, v)); }

// view vector
template<typename T> void view(T e) { cerr << e << endl; }
template<typename T> void view(const vector<T>& v) { for (const auto& e : v) { cerr << e << " "; } cerr << endl; }
template<typename T> void view(const vector<vector<T> >& vv) { for (const auto& v : vv) { view(v); } }

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




// ***************************************

int main() {

    string s, t;
    cin >> s >> t;

    ll S = s.size();
    ll T = t.size();

    vector<vector<ll>> dp(S + 1, vector<ll>(T + 1, 0));
    
    REP(i, S) {
        REP(j, T) {
            if (s[i] == t[j]) chmax(dp[i + 1][j + 1], dp[i][j] + 1);
            chmax(dp[i + 1][j + 1], dp[i][j + 1]);
            chmax(dp[i + 1][j + 1], dp[i + 1][j]);
        }
    }


    ll i = S, j = T;
    string ans = "";
    while (dp[i][j] > 0) {
        while (dp[i][j] == dp[i][j - 1]) j--;
        while (dp[i][j] == dp[i - 1][j]) i--;
        i--; j--;
        ans = s[i] + ans;
    }

    cout << ans << endl;


    return 0;
}



Measured memory_bytes: 70784
#include<stdio.h>
int main(void){
  char *s="python3 -c\""
"n,*w=map(int,open(0).read().split());print(min(abs(sum(w[:i])-sum(w[i:]))for i in range(n)))\n"
"\"";
  system(s);
  return 0;
}            

Measured memory_bytes: 8380
import java.io.{BufferedReader, InputStream, InputStreamReader}
import java.util.StringTokenizer

object Main {

  val MOD = 1000000007

  def solve(): Unit = {
    val sc = new FastScanner(System.in)
    val N = sc.nextInt
    val S1 = sc.next
    val S2 = sc.next
    var ans: Long = 1
    var prev = 0

    def countSame(remain:  List[Char], prevChar: Char, prevCnt: Int, building: List[Int]): List[Int] = remain match {
      case Nil => prevCnt :: building
      case c :: next =>
        c match {
          case `prevChar` => countSame(next, c, prevCnt + 1, building)
          case _ => countSame(next, c, 1, prevCnt :: building)
        }
    }
    val cases = countSame(S1.drop(1).toList, S1.head, 1, Nil).reverse
    cases foreach { cur =>
      val mult = (prev, cur) match {
        case (0, 1) => 3
        case (0, 2) => 6
        case (1, 1) => 2
        case (1, 2) => 2
        case (2, 1) => 1
        case (2, 2) => 3
      }
      ans = ans * mult % MOD
      prev = cur
    }
    println(ans)
  }

  def main(args: Array[String]): Unit = {
    solve()
  }

  class FastScanner(val stream: InputStream) {
    val in = new BufferedReader(new InputStreamReader(stream))
    var st: StringTokenizer = _

    def next: String = {
      while (st == null || !st.hasMoreTokens) {
        val rl = in.readLine
        if (rl == null) return null
        st = new StringTokenizer(rl)
      }
      st.nextToken
    }

    def nextInt: Int = next.toInt
  }
}


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

using namespace std;

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;
using vld = vector<ld>;
using vvld = vector<vld>;

typedef pair<ll, ll> P;

#define bit(n) (1LL << (n))

//#define int long long

#define all(v) v.begin(), v.end()

#define rep(i, n) for (ll i = 0; i < n; i++)
#define REP(i, n) for (ll i = 1; i < n; i++)

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORm(i, m) for (auto i = m.begin(); i != m.end(); i++)

template <class T>
inline void chmax(T& a, T b) {
  a = std::max(a, b);
}
template <class T>
inline void chmin(T& a, T b) {
  a = std::min(a, b);
}

#define mod (ll)(1e9 + 7)
const long long INF = 1LL << 60;

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);

  ll k;
  cin >> k;

  // k <= 50*10^16
  // 2<= n <= 50
  // 0 <= Ai <= 10^16+1000

  vll a = vll(50);

  if (k < 50) {
    rep(i, k) {
      a[i] = 50;
    }
  } else {
    rep(i, 50) {
      a[i] = 50;
    }
    k -= 50;
    ll p = k / 50;
    ll q = k % 50;
    rep(i, 50) {
      a[i] += p;
      if (i < q) {
        a[i]++;
      } else {
        a[i] -= q;
      }
    }
  }

  cout << a.size() << endl;
  rep(i, a.size()) {
    cout << a[i] << " ";
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(void){
  int n;
  long long ans;
  vector<int> v;
  
  cin >> n;
  for (int i=0; i<n*3; i++){
    int t;
    cin >> t;
    v.push_back(-t);
  }
  sort(v.begin(), v.end());
  ans = 0;
  for (int i=0; i<n; i++){
    ans += -v[i*2+1];
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 2420
#include <bits/stdc++.h>
int n,m,k,t;
using namespace std;
int main()
{
    int i,j;
    long long p,q;
    scanf("%lld%lld",&p,&q);
    int ret=0;
    while(p<=q)ret++,p*=2;
    printf("%d\n",ret);
    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<cstdio>

using namespace std;

int s;

int main()
{
	cin>>s;
	int s1=s/1000;
	int s2=s/100%10;
	int s3=s/10%10;
	int s4=s%10;
	if(s1==s2||s2==s3||s3==s4)
		cout<<"Bad"<<endl;
	else
		cout<<"Good"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define ALL(a)    a.begin(), a.end() 
#define rep(i, K, N)  for(int i = K; i < N; i++)
#define ll long long int
using namespace std;

ll F(ll n){
ll A = 2, B = 1;
    while(A <= n){
    B *= A;B %= 1000000007;
    A++;
    }
return B;
}

int main() {
ll N, M;cin >> N >> M;

if(abs(N - M) >= 2)cout << 0;

if(N == M)cout << (F(N)*F(M)*2)%1000000007;

if(abs(N - M) == 1)cout << (F(N)*F(M))%1000000007;

}


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

#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define intll int long long
const int INF = 1e9;
const int MOD = 1e9 + 7;

int main() {
 int n , r ;
  cin >> n >> r ;
  
  if( n<10)
    cout << r+100*(10-n) ;
  
  else 
    cout << r ;


}


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

ll A[1005],B[1005];
ll dp[1005][10005];

int main(int argc, char *argv[]) { ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);


  ll h,n;cin>>h>>n;

  for(int i=0;i<n;i++){
    cin>>A[i]>>B[i];
  }
  for(int i=0;i<=n;i++){
    for(int j=0;j<=h;j++){
      dp[i][j]=pow(10,8);
    }
  }
  for(int i=0;i<n;i++){
    auto a = A[i], b = B[i];
    dp[i][0]=0;
    for(int j=0;j<=h;j++){
      auto damage = min(h, j + a);
      dp[i + 1][j] = min(dp[i + 1][j], dp[i][j]);
      dp[i + 1][damage] = min(dp[i + 1][damage], dp[i][j] + b);
      dp[i + 1][damage] = min(dp[i + 1][damage], dp[i + 1][j] + b);
    }
  }

  cout<<dp[n][h]<<endl;

  
  return 0;
}


Measured memory_bytes: 78464
n = int(input())
P = list(map(int, input().split()))

cnt = 0
for i in range(1, n-1):
    if (P[i-1]<P[i] and P[i]<P[i+1]) or (P[i-1]>P[i] and P[i]>P[i+1]):
        cnt+=1

print(cnt)

Measured memory_bytes: 3060
def dfs(s):
    if s != "":
        if int(s) > n:
            return 0
    if len(set(s)) == 3:
        cnt = 1
    else:
        cnt = 0
    for i in "753":
        cnt += dfs(s + i)
    return cnt


n = int(input())
print(dfs(""))

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

int main(void)
{
    int D;
    scanf("%d", &D);

    if (D == 25)
        printf("Christmas\n");
    if (D == 24)
        printf("Christmas Eve\n");
    if (D == 23)
        printf("Christmas Eve Eve\n");
    if (D == 22)
        printf("Christmas Eve Eve Eve\n");

    return 0;
}

Measured memory_bytes: 128