akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int main() {
    int s;
    int n,m;
    cin >> s;
    vector<int> retu;
    retu.push_back(s);
    int flag = 0;
    int i = 0;
    while (flag == 0){
        if (retu[i] % 2 == 0){
            retu.push_back(int(retu[i]/2));
        }
        else{
            retu.push_back(3 * retu[i] + 1);
        }
        i = i + 1;
        for (int j = 0;j < i;j++){
            if (retu[i] == retu[j]){
                flag = 1;
                n = retu[j];
                m = i + 1;
            }
        }
    } 
    cout << m << endl;

}

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

#define int long long
#define double long double
#define ff first
#define ss second
#define endl '\n'
#define ii pair<int, int>
#define mp make_pair
#define mt make_tuple
#define DESYNC                      \
  ios_base::sync_with_stdio(false); \
  cin.tie(0);                       \
  cout.tie(0)
#define pb push_back
#define vi vector<int>
#define vii vector<ii>
#define all(x) x.begin(), x.end()
#define EPS 1e-9
#define INF 1e18
#define ROOT 1
#define M 1000000007
#define curtime chrono::steady_clock::now().time_since_epoch().count
#define rep(i, beg, n, s) for (int i = beg; i < n; i += s)
const double PI = acos(-1);

using namespace std;

inline int mod(int n, int m = M) {
  int ret = n % m;
  if (ret < 0) ret += m;
  return ret;
}

int exp(int n, int k) {
  if (k == 0) return 1;
  if (k == 1) return n;
  int ax = exp(n, k / 2);
  ax = mod(ax * ax);
  if (k % 2) ax = mod(ax * n);
  return ax;
}

int gcd(int a, int b) {
  if (a == 0)
    return b;
  else
    return gcd(b % a, a);
}

//#define MULTIPLE_TEST_CASE
void solution() {
  int n;
  cin >> n;
  vector<int> dp(n + 1, 0);
  dp[0] = 1;
  for (int k = 0; k <= n; k++) {
    for (int i = 3; i <= n; i++) {
      if (k - i < 0) continue;
      dp[k] += dp[k - i];
      dp[k] = mod(dp[k]);
    }
    // cout << "dp[" << k << "] = " << dp[k] << endl;
  }
  cout << dp[n] << endl;
}

int32_t main() {
  DESYNC;
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  int t = 1;
#ifdef MULTIPLE_TEST_CASE
  cin >> t;
#endif
  while (t--) solution();
}


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

const int MAXN = 1e5 + 5;

using namespace std;

int n,dp[MAXN],v[MAXN];

int main()
{
    cin>>n;
    for(int i = 1; i <= n; i++)
        cin>>v[i];
    dp[1] = 0;
    dp[2] = abs(v[2] - v[1]);
    for(int i = 3; i <= n; i++){
        dp[i] = min(dp[i - 2] + abs(v[i - 2] - v[i]),dp[i - 1] + abs(v[i - 1] - v[i]));
    }
    cout<<dp[n];
    return 0;
}


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

using namespace std;

int main()
{
    int N;
    cin>>N;
    vector< vector<int> > v(3, vector<int>(N));
    for (int i=0;i<3;i++) {
        for (int j=0;j<N;j++) {
            cin>>v[i][j];
        }
    }
    sort(v[0].begin(), v[0].end());
    sort(v[1].begin(), v[1].end());
    sort(v[2].begin(), v[2].end());
    long sum=0;
    for (int i=0;i<N;i++) {
        auto it0=lower_bound(v[0].begin(), v[0].end(), v[1][i]);
        //中央に対してそれ以下の上段の個数
        long kosu0=it0-v[0].begin();
        auto it2=upper_bound(v[2].begin(), v[2].end(), v[1][i]);
        //中央に対してそれ以上の下段の個数
        long kosu2=N-(it2-v[2].begin());
        sum+=kosu0*kosu2;
    }
    cout<<sum<<endl;

    
    return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  sort(a.begin(),a.end());
  reverse(a.begin(),a.end());
  ll m=a[0],c=1,mm;
  bool f=true;
  for(int i=1;i<n;i++){
    if(m==a[i]){
      c++;
    }else{
      if(c>=4&&f){
        cout<<m*m;
        return 0;
      }else if(c>=2&&!f){
        cout<<m*mm;
        return 0;
      }else if(c>=2){
        mm=m;
        f=false;
      }
      c=1;
      m=a[i];
    }
  }
  if(c>=4&&f){
    cout<<m*m;
  }else if(c>=2&&!f){
    cout<<m*mm;
  }else{
    cout<<0;
  }
}

Measured memory_bytes: 640
fun main(args: Array<String>) {
    val input = readLine()!!.split(" ").map { it.toInt() }
    val n = input[0]
    val l = input[1]
    val s: Array<String> = Array(n) { "" }
    for (i in 0 until n) {
        s[i] = readLine()!!
    }

    var tmp = ""
    for (i in 0 until n - 1) {
        for (j in i + 1 until n) {
            if (s[j] < s[i]) {
                tmp = s[i]
                s[i] = s[j]
                s[j] = tmp
            }

        }
    }

    print(s.joinToString(""))
}

Measured memory_bytes: 36028
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Program
{
    static void Main(string[] args)
    {
    	var sc = new Scanner();
    	int h = sc.NextInt();
    	int w = sc.NextInt();
    	int a = sc.NextInt();
    	int b = sc.NextInt();
    	Console.WriteLine(h * w - h * b - (w - b) * a);
    }
}

class Scanner
{
    int index = -1;
    string[] buf;

    public Scanner()
    {
    }

    public int NextInt()
    {
        CheckNext();
        return int.Parse(buf[index++]);
    }
        
    public long NextLong()
    {
    	CheckNext();
    	return long.Parse(buf[index++]);
    }

    public string NextString()
    {
        CheckNext();
        return buf[index++];
    }

    private void CheckNext()
    {
        if (index >= 0 && index < buf.Length) return;

        buf = Console.ReadLine().Split(' ');
        index = 0;
    }
}

Measured memory_bytes: 13140
N,A,B=map(int,input().split())

def digit_sum(n):
  ret=0
  while(n>0):
    ret+=n%10
    n//=10
    
  return ret

answer=0
for i in range(1,N+1):
  si=digit_sum(i)
  if A<=si and si<=B:
    answer+=i
    
print(answer)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;

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

    vector<ll> height(N+10),cost(N+10);
    for(int i=0;i<N;i++){
        cin >> height[i];
    }
    for(int i=1;i<K;i++){
        ll tmp=100000000;
        for(int j=1;j<=i;j++){
            tmp=min(cost[i-j]+abs(height[i]-height[i-j]),tmp);
        }
        cost[i]=tmp;
    }
    for(int i=K;i<N;i++){
        ll tmp=1000000000;
        for(int j=1;j<=K;j++){
          tmp=min(cost[i-j]+abs(height[i]-height[i-j]),tmp); 
        }
        cost[i]=tmp;
    }
    cout << cost[N-1] << endl;
}

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

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

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

	string S; cin >> S;

	char c = S[S.size()/2];
	int ci = S.size()/2;
	int ans = S.size()/2;
	if(S.size()%2 == 0){
		if(S[ci-1] != c){
			cout << ans << endl;
			return 0;
		}
		ans++;
		int cnt = 1;
		while(ci+cnt < S.size() && S[ci+cnt] == c && S[ci-1-cnt] == c){ ans++; cnt++;}
		cout << ans << endl;
	}else{
		ans++;
		int cnt = 1;
		while(ci+cnt < S.size() && S[ci-cnt] == c && S[ci+cnt] == c){ans++; cnt++;}
		cout << ans << endl;
	}
	

	return 0;

}


Measured memory_bytes: 512
import numpy as np
import math
import scipy as sp
import queue
import collections

MOD = 10 ** 9 + 7
INF = 10 ** 9

def main(kwargs):
    x = kwargs["x"]
    res = "No"
    if x >= 30:
        res = "Yes"
    return res

if __name__ == "__main__":
    kwargs = {}

    cin = input().split()
    kwargs["x"] = [int(i) for i in cin][0]

    cout = main(kwargs)
    print(cout)

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

int main(){
  
  int A,B,C,D; cin >> A >> B >> C >> D;
  
  int train;
  int bus;
  
  if(A < B){
    train = A;
  }
  else{
    train = B;
  }
  
  if(C < D){
    bus = C;
  }
  else{
    bus = D;
  }
  
  cout << train + bus << endl;
  
  return 0;
  
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	string n;
	cin>>n;
	if (n[0]==n[1]&&n[1]==n[2])
		cout<<"Yes"<<endl;
	else if (n[1]==n[2]&&n[2]==n[3])
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX 1100000
#define MAX_N 1010
#define MAX_H 1010
#define MAX_W 1010
 
int par[MAX],rank[MAX];
 
void init(){
    for(int i = 0 ; i < MAX ; i++){
	par[i] = i;
	rank[i] = 0;
    }
}
 
int find(int x){
    if(par[x] == x){
	return x;
    }
    return par[x] = find(par[x]);
}
 
void unite(int x,int y){
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(rank[x] < rank[y]){
	par[x] = y;
    }else{
	par[y] = x;
	if(rank[x] == rank[y]){
	    rank[x]++;
	}
    }
}
 
bool same(int x,int y){
    return find(x) == find(y);
}
 
int H,W,N,start,goal;
int x[MAX_N],y[MAX_N];
char field[MAX_H][MAX_W];
bool visited[MAX_H][MAX_W];
const int dx[4] = {-1,0,1,0};
const int dy[4] = {0,-1,0,1};
 
int solve(){
    init();
    for(int i = 0 ; i < H ; i++){
	for(int j = 0 ; j < W ; j++){
	    if(field[i][j] == '#') continue;
	    for(int k = 0 ; k < 4 ; k++){
		int nx = j + dx[k];
		int ny = i + dy[k];
		if(0 > nx || W <= nx || 0 > ny || H <= ny){
		    continue;
		}
		if(field[ny][nx] == '#') continue;
		if(!same(i*W+j,ny*W+nx)){
		    unite(i*W+j,ny*W+nx);
		}
	    }
	}
    }
    if(same(start,goal)){
	return 0;
    }
    for(int i = 0 ; i < N ; i++){
	field[y[i]][x[i]] = '.';
	for(int j = 0 ; j < 4 ; j++){
	    int nx = x[i] + dx[j];
	    int ny = y[i] + dy[j];
	    if(0 > nx || W <= nx || 0 > ny || H <= ny){
		continue;
	    }
	    if(field[ny][nx] == '#') continue;
	    if(!same(y[i]*W+x[i],ny*W+nx)){
		unite(y[i]*W+x[i],ny*W+nx);
	    }
	}
	if(same(start,goal)){
	    return i+1;
	}
    }
    return -1;
}
 
int main(){
    while(cin >> W >> H){
	start = 0;
	for(int i = 0 ; i < H ; i++){
	    for(int j = 0 ; j < W ; j++){
		cin >> field[i][j];
		if(field[i][j] == 't'){
		    field[i][j] = '.';
		    goal = i*W+j;
		}
	    }
	}
	cin >> N;
	for(int i = 0 ; i < N ; i++){
	    cin >> x[i] >> y[i];
	}
	cout << solve() << endl;
    }
    return 0;
}

Measured memory_bytes: 10756
N = int(input())
a = input()
list1 = list(map(int,a.split()))
cout = 0
for i in range(0,N-1):
    
    if list1[i] > list1[i+1]+1:
        print("No")
        exit()
    elif list1[i] == list1[i+1]:
        cout += 1
    elif list1[i] == list1[i+1]+1:
        if cout >= 1: #coutが溜まっているなら平らなところ全部1減らす
            for j in range(i-cout,i+1):
                list1[j] = list1[j] -1
            cout = 0
        else:
            list1[i] = list1[i] -1
    else:
        cout = 0

#段差がないかの判定
for i in range(0,N-1):
    if list1[i] > list1[i+1]:
        print("No")
        exit()
print("Yes")


Measured memory_bytes: 15476
import java.util.*;
// warm-up
public class Main {

	static void solve() {
		Scanner sc = new Scanner(System.in);
		boolean ok = false;
		String s = sc.next();
		if (s.charAt(0)==s.charAt(1) && s.charAt(1)==s.charAt(2)) ok = true;
		else if (s.charAt(1)==s.charAt(2) && s.charAt(2)==s.charAt(3)) ok = true;
		System.out.println(ok ? "Yes" : "No");
		sc.close();		
	}

	public static void main(String args[]) {
		solve();
	}

}

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

#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair()
#define FOR(i, a, b) for (int i=a; i<(b); i++)
int main()
{
    ios_base::sync_with_stdio (false) ;
    cin.tie(0) ; cout.tie(0) ;
    ll n,d; cin>>n>>d;
    ll m=2*d+1;
    cout<<n/m + (n % m != 0);

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i ,n) for(int i = 0 ; i < (n) ; i ++ )
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
using ll = long long;
using vll=vector<ll>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

int main() {
  string s,t;
  cin>>s>>t;
  int ans=0;
  rep(i,3){
   if (s[i]==t[i]) ans++;
  }
  cout<<ans<<endl;
}

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

#define iin(x) scanf("%d", &x)
#define lin(x) scanf("%lld", &x)
#define fin(x) scanf("%lf", &x)

#define iout(x) printf("%d", x)
#define lout(x) printf("%d", x)
#define fout(x) printf("%.10f", x)
#define _ putchar(' ')
#define endl puts("")

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

int n, q;
int A[22], m;
int sum[1<<22] = {};

int main() {
  int i, j, k;

  iin(n);
  rep(i, n) iin(A[i]);

  rep(i, 1<<n) {
    rep(j, n) if((i>>j)&1) sum[i] += A[j];
  }
  
  iin(q);  
  rep(i, q) {
    int flag = 0;
    iin(m);
    rep(j, 1<<n) {
      if(sum[j] == m) {
	flag = 1;
	break;
      }
    }
    puts((flag ? "yes" : "no"));
  }

  
  
  return 0;
}

Measured memory_bytes: 6724
#include <iostream>
#include <string>
using namespace std;
 
int main(){
 bool l,r,u;
string s;
 l=r=u=false;
 int ans=0;
 int n,i;
 cin >> n;
 while(n){
  l=r=u=false;
  ans=0;
  for(i=0;i<n;i++){
   cin >> s;
   if(s=="lu")l=true;
   if(s=="ld")l=false;
   if(s=="ru")r=true;
   if(s=="rd")r=false;
   if(l==r){
    if(u!=l)ans++;
    u=l;
   }
  }
  cout << ans << endl;
  cin >> n;
 }
 return 0;
}


Measured memory_bytes: 2988
#include<cstdio>
#include<cstdlib>
#include<cmath>

long Grundy(long a,long k){
	while(a%k != 0 && a/k > 0){
		a -= (a/k + 1)*(((a%k)+(a/k))/(a/k + 1));
	}
	return a/k;
}
int main(void){
	int N;
	long A[200],K[200],grun[200],ans;
	scanf("%d", &N);
	for(int i=0;i<N;i++){
		scanf("%ld%ld",&A[i],&K[i]);
	}
	ans = Grundy(A[0],K[0]);//grun[0]

	for(int i =1;i<N;i++){
		grun[i] = Grundy(A[i],K[i]);
		ans = ans^grun[i];
	}
		
	if(ans > 0)printf("Takahashi\n");
	else printf("Aoki\n");
	fflush(stdout);

	return 0;
}

Measured memory_bytes: 128
def solve(n, ABC):
    dp = [[0] * n for _ in range(3)]
    dp[0][0], dp[1][0], dp[2][0] = ABC[0]
    for i in range(1, n):
        for j in range(3):
            dp[j][i] = max(dp[(j + 1) % 3][i - 1], dp[(j + 2) % 3][i - 1]) + ABC[i][j]
    return max(dp[0][n - 1], dp[1][n - 1], dp[2][n - 1])

_n = int(input())
_ABC = [list(map(int, input().split())) for _ in range(_n)]
print(solve(_n, _ABC))


Measured memory_bytes: 64472
#include <iostream>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <bitset>
#include <vector>
#include <set>
using namespace std;

int main(){
    int dif = 1000;
    string S;

    cin >> S;

    for(int i = 0; i < (S.size() - 2); i++){
        string three;
        three += S.at(i);
        three += S.at(i+1);
        three += S.at(i+2);
        int tmp = abs(753 - stoi(three));
        if(dif > tmp){
            dif = tmp;
        }
    }

    cout << dif << endl;
}

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

string s, t;

int main(){

    cin >> s >> t;

    int size;
    size = s.size();

    for (int i=0; i<size; i++){
        if (s.at(i) != t.at(i)){
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}

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

int i,j,k,h,w,ii,jj,cnt=0,ans=0;
int a[6],b[6];
char c[6][6];
 bool f=0;

int main (void)
{
 
  cin>>h>>w>>k;
  for(i=0;i<h;i++)for(j=0;j<w;j++)cin>>c[i][j];
  int n=1;
  for(i=0;i<h+w;i++){n*=2;}
  for(i=0;i<n;i++)
  {
    int aa=i;
    for(j=0;j<h+w;j++)
    {
      if(j<h){a[j]=aa%2;}
      else{b[j-h]=aa%2;}
      aa/=2;
    }
    for(ii=0;ii<h;ii++)
    {
      for(jj=0;jj<w;jj++)
      {
      if(a[ii]==0&&b[jj]==0&&c[ii][jj]=='#'){cnt++;}
      }
    }
    if(cnt==k)ans++;
    cnt=0;
  }

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

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

int main(){
  int N ;
  cin >> N ; 
  double  C = 0 ; 
  vector<double> A(N)  , B(N) ; 
  
  for(int i = 0 ; i < N ; i++){
    cin >> A[i] ; 
    B[i] = 1/A[i]  ;
    C = C + B[i] ; 
  }
  
  
  cout << 1/C << endl ; 
  
}


Measured memory_bytes: 3720
#include<bits/stdc++.h>
#define ci const int&
using namespace std;
struct edge{
	int t,nxt;
}e[4010];
int n,u,v,be[2010],cnt,tt[2010],tg[2010],vis[2010],f[2010],ans=1e9;
char s[2010];
void add(ci x,ci y){
	e[++cnt]=(edge){y,be[x]},be[x]=cnt;
}
void dfs(ci x){
	vis[x]=1,tg[x]=(s[x]=='1'),tt[x]=f[x]=0;
	for(int i=be[x];i;i=e[i].nxt)!vis[e[i].t]?dfs(e[i].t),tt[x]+=tt[e[i].t],tg[x]+=tg[e[i].t]:f[x]=e[i].t;
	tt[x]+=tg[x],vis[x]=0;
}
bool Solve(ci x,ci us){
	int tm=tt[x]-tg[x]+us;
	for(int i=be[x];i;i=e[i].nxt)if(f[x]!=e[i].t&&tt[e[i].t]>(tm>>1))return tg[e[i].t]<=(tm-tt[e[i].t])?Solve(e[i].t,tm-tt[e[i].t]-tg[e[i].t]):false;
	return true;
}
int main(){
	scanf("%d%s",&n,s+1);
	for(int i=1;i<n;++i)scanf("%d%d",&u,&v),add(u,v),add(v,u);
	for(int i=1;i<=n;++i)dfs(i),!(tt[i]-tg[i]&1)&&Solve(i,0)?ans=min(ans,tt[i]-tg[i]>>1):0;
	printf("%d",ans==1e9?-1:ans);
	return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
#include<stdlib.h>
using namespace std;

class Stack {
  int top;
  int V[200];

  public:
    Stack() { top = 0; }
    void push(int x) {
      V[top++] = x;
    }
    int pop() {
      return V[--top];
    }
};

int main() {
  char c[10];
  int a, b;
  Stack stack;

  while( scanf("%s", c) != EOF ) {
    switch(c[0]) {
      case '+':
        a = stack.pop();
        b = stack.pop();
        stack.push(a+b);
        break;
      case '-':
        a = stack.pop();
        b = stack.pop();
        stack.push(b-a);
        break;
      case '*':
        a = stack.pop();
        b = stack.pop();
        stack.push(a*b);
        break;
      default:
        stack.push(atoi(c));
    }
  }

  printf("%d\n", stack.pop());
  return 0;
}



Measured memory_bytes: 2692
#include <stdio.h>
 
int main(void) {
  int h,m,s;
  scanf("%d",&s);

  m=s/60;
  h=m/60;

  m=m-60*h;
  s=s-60*m-3600*h;

  printf("%d:%d:%d\n",h,m,s);
  return 0;
}


Measured memory_bytes: 2096
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL_DEBUG
  #include "LOCAL_DEBUG.hpp"
#endif
#define int long long
const int INF = 1LL << 60;

signed main(){

  int k; cin >> k;
  string s; cin >> s;
  if(s.size() <= k){
    cout << s << endl;
  }else{
    string t = s.substr(0, k) + "...";
    cout << t << endl;
  }

  return 0;
}

Measured memory_bytes: 3636
// I saw the editorial to solve this problem :-)
#include <iostream>
#include <vector>
#include <numeric>
#include <tuple>
#include <set>

using ll = long long int;
using namespace std;

vector<tuple<ll, ll, ll>> events;


int main() {
  ll N, Q;
  cin >> N >> Q;
  for (int i = 0; i < N; i++) {
    ll s, t, x;
    cin >> s >> t >> x;
    events.push_back({s - x, 1, x});
    events.push_back({t - x, -1, x});
  }

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

  set<ll> stucked;
  int index = 0;
  for (int i = 0; i < Q; i++) {
    ll d;
    cin >> d;
    
    for (; get<0>(events[index]) <= d && index < 2 * N; index++) {
      if (get<1>(events[index]) == 1) {
        stucked.insert(get<2>(events[index]));
      } else {
        stucked.erase(get<2>(events[index]));
      }
    }

    if (stucked.size() == 0) {
      cout << "-1" << endl;
    } else {
      ll mn = *stucked.begin();
      cout << mn << endl;
    }
  }

  return 0;
}


Measured memory_bytes: 20200
def count_k(num):
    a = list(str(num))
    a = list(list(map(int, a)))
    return sum(a)

N = int(input())

arr = [0] * N

for i in range(1, N):
    arr[i] = count_k(i)

re = 0
for i in range(0, int(N/2)):
    c = arr[i +1] + arr[N - i - 1]
    if re > c or re == 0:
        re = c
        
print(re)

Measured memory_bytes: 3828
N,M = map(int,input().split())
ab = []
for i in range(M):
    a,b = list(map(int,input().split()))
    a -= 1
    b -= 1
    ab.append([a,b])
    
def bfs(ab):
    from collections import deque
    que = deque()
    alr = [0]
    que.append(0)
    while que:
        q = que.popleft()
        for i in ab[q]:
            if i not in alr:
                alr.append(i)
                que.append(i)
    if len(alr) < N:
        return 1
    else:
        return 0

count = 0
for i in range(M):
    ab2 = [[] for k in range(N)]
    for j in range(M):
        if j != i:
            a,b = ab[j]
            ab2[a].append(b)
            ab2[b].append(a)
    count += bfs(ab2)
print(count)
    

Measured memory_bytes: 3416
#include <stdio.h>
#include <vector>
#include <stack>
#include <functional>
#include <numeric>
#include <complex>
#include <queue>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <unordered_set>
#include <assert.h>
#include <cstring>
#include <sstream>
#include <string>
#include <algorithm>
#include <iostream>
 
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define X first
#define Y second
#define pb(x) push_back(x)
#define FOR(k, n) for (int k = 0; k < n; k++)
#define FORN(k, s, n) for (int k = s; k < n; k++)
#define debug(x) printf("x = %d\n", x);
#define debug2(x, y) printf("x = %d, y = %d\n", x, y);
#define debug3(x, y, z) printf("x = %d, y = %d, z = %d\n", x, y, z);
#define debug4(x, y, z, t) printf("x = %d, y = %d, z = %d, t = %d\n", x, y, z, t);
 
#pragma warning(disable : 6031)
#pragma warning(disable : 4101)
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
typedef complex<double> cd;
 
const int INF = 1e9;
const long long LINF = 1e18;
const double PI = acos(-1);
 
// Solution

const int MAXN = 3003;
const ll MOD = 1000000007ll;

ll n, m, A[MAXN], B[MAXN], DP[MAXN][MAXN];

void init() {
    for (int i = 0; i < MAXN; i++) {
        DP[0][i] = DP[i][0] = 1ll;
    }
}

int main() {
    init();

    scanf("%lld%lld", &n, &m);

    for (int i = 1; i <= n; i++) {
        scanf("%lld", &A[i]);
    }

    for (int i = 1; i <= m; i++) {
        scanf("%lld", &B[i]);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (A[i] == B[j]) {
                DP[i][j] = (DP[i - 1][j] + DP[i][j - 1] + 1ll) % MOD;
            } else {
                DP[i][j] = (DP[i - 1][j] + DP[i][j - 1] - DP[i - 1][j - 1] + MOD) % MOD;
            }
        }
    }

    printf("%lld\n", (((DP[n][m] + 1ll) % MOD) * 500000004) % MOD);
    
    return 0;
}

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

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

int main() {
    ll n;cin>>n;
    ll a[n];
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    ll sum[n][n];
    ll i,j,k;
    for(i=0;i<n;i++){
        for(k=0;k<n-i;k++){
            if(k==0){
                sum[i][i+k]=a[i];
            }else{
                sum[i][i+k]=sum[i][i+k-1]+a[i+k];
            }
        }
    }
    ll mini;
    ll dp[n][n];
    for(k=0;k<n;k++){
        for(i=0;i<n-k;i++){
            mini=0;
            if(k==0){
                dp[i][i+k]=0;
            }else{
                mini=1000000000000000;
                for(j=0;j<k;j++){
                    mini=min(mini,dp[i][i+j]+dp[i+j+1][i+k]);
                }
                dp[i][i+k]=sum[i][i+k]+mini;
            }
        }
    }
    cout<<dp[0][n-1]<<endl;
    
    return 0;
}


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

using namespace std;

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

  while (s.size() > 1) {
    s.pop_back();

    int size = s.size();
    if (size % 2 != 0) {
      continue;
    }

    int half_size = size / 2;
    string left = s.substr(0, half_size);
    string right = s.substr(half_size, size);

    if (left == right) {
      cout << size << endl;
      break;
    }
  }


  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>


#define REP(i,N) for(auto i = 0; i <N; i++)
using namespace std;
typedef long long ll;


int in(){
    int temp;
    scanf("%d",&temp);
    return temp;
}

ll lin(){
    ll temp;
    scanf("%lld",&temp);
    return temp;
}


int main() {
    
    ll N = lin();
    
    vector<ll> A;
    for(auto i = 0; i<N; i++){
        A.push_back(in()-i-1);
    }
    
    sort(A.begin(),A.end());
    
    ll piv = 0;
    
    ll sum = 0;
    
    if (N%2 == 1){
        piv = A[(N)/2];
        
        for(auto a:A){
            sum += abs(piv - a);
        }
        
        cout << sum << endl;
        
        return 0;
        
    }
    
    ll sum1 = 0;
    ll sum2 = 0;
    
    piv = A[(N)/2-1];
    
    for(auto a:A){
        sum1 += abs(piv - a);
    }
    
    piv = A[(N)/2];
    
    for(auto a:A){
        sum2 += abs(piv - a);
    }
    
    cout << min(sum1,sum2) << endl;
    
    return 0;
}










Measured memory_bytes: 2420
V, E = map(int, input().split())

# -*- coding: utf-8 -*-
import collections
import queue


class Dinic:
    def __init__(self, N):
        self.N = N
        self.edges = collections.defaultdict(list)
        self.level = [0 for _ in range(self.N)]
        self.iter = [0 for _ in range(self.N)]

    def add(self, u, v, c, directed=True):
        """
        0-indexed
        u = from, v = to, c = cap
        directed = Trueなら、有向グラフである
        """
        if directed:
            self.edges[u].append([v, c, len(self.edges[v])])
            self.edges[v].append([u, 0, len(self.edges[u])-1])
        else:  # TODO
            self.edges[u].append([v, c, len(self.edges[u])])

    def bfs(self, s):
        self.level = [-1 for _ in range(self.N)]
        self.level[s] = 0
        que = queue.Queue()
        que.put(s)
        while not que.empty():
            v = que.get(s)
            for i in range(len(self.edges[v])):
                e = self.edges[v][i]
                if e[1] > 0 and self.level[e[0]] < 0:
                    self.level[e[0]] = self.level[v] + 1
                    que.put(e[0])

    def dfs(self, v, t, f):
        if v == t:
            return f
        for i in range(self.iter[v], len(self.edges[v])):
            self.iter[v] = i
            e = self.edges[v][i]
            if e[1] > 0 and self.level[v] < self.level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d > 0:
                    e[1] -= d
                    self.edges[e[0]][e[2]][1] += d
                    return d
        return 0

    def maxFlow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow
            self.iter = [0 for _ in range(self.N)]
            f = self.dfs(s, t, float('inf'))
            while f > 0:
                flow += f
                f = self.dfs(s, t, float('inf'))

graph = Dinic(V)

for i in range(E):
    u, v, c = map(int, input().split())
    graph.add(u, v, c)

print(graph.maxFlow(0, V-1))


Measured memory_bytes: 7124
const input = require('fs').readFileSync('/dev/stdin', 'utf8');
const lines = input.trim().split('\n');
const target = lines[1].split(' ');
const min = target.reduce((a,b)=> Number(a)<Number(b)?a:b);
const max = target.reduce((a,b)=>Number(a)>Number(b)?a:b);
let sum = 0;

target.forEach(function(val){
  sum += Number(val);
});

console.log(min + ' ' + max + ' ' + sum);


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

const double pi = 3.14159265358979323846;
const ll mod = 1000000007;


int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
	int n; cin >> n;
	unordered_map<int, int> mp(n);
	ll sum = 0;
	rep(i,n){
		int a; cin >> a;
		sum += a;
		mp[a]++;
	}
	int q; cin >> q;
	for(int i = 0; i < q; i++){
		int a, b; cin >> a >> b;
		sum += (b-a)*mp[a];
		int num = mp[a];
		mp[b] += num;
		mp.erase(a);
		cout << sum << endl;
	}
} 

Measured memory_bytes: 6004
def main():
	x,y,z = map(int, raw_input().split("/"))
	if x>2019 or x==2019 and y>4 or x==2019 and y==4 and z>31:
		print "TBD"
	else:
		print "Heisei"
	
	return 0

if __name__ == '__main__':
	main()



Measured memory_bytes: 2568
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>

using namespace std;


int main() {

    int N, M;
    cin >> N >> M;
    vector<int> AS;
    int A;
    int sum = 0;
    for (int i = 0; i < N; ++i) {
        cin >> A;
        AS.push_back(A);
        sum += A;
    }

    int cnt = 0;
    for (int i = 0; i < N; ++i) {
        if ((AS[i] * (4 * M)) >= sum) {
            cnt += 1;
        }
    }

    if (cnt >= M) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}


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

int main(){
    int64_t t1, t2, a1, a2, b1, b2;
  
    cin>>t1>>t2>>a1>>a2>>b1>>b2;
    if(a1*t1+a2*t2==b1*t1+b2*t2) cout<<"infinity";
    else if(a1*t1>b1*t1&&a1*t1+a2*t2>b1*t1+b2*t2) cout<<0;
    else if(a1*t1<b1*t1&&a1*t1+a2*t2<b1*t1+b2*t2) cout<<0;
    else if(a1*t1<b1*t1&&a1*t1+a2*t2>b1*t1+b2*t2){
        int64_t sa=a1*t1+a2*t2-(b1*t1+b2*t2);
        int64_t sb=-a1*t1+b1*t1;
        int64_t as=1LL+sb/sa*2LL;
        
        if(sb%sa==0) as=as-1LL;
        cout<<as;

    }
    else if(a1*t1>b1*t1&&a1*t1+a2*t2<b1*t1+b2*t2){
        int64_t sa=-(a1*t1+a2*t2)+(b1*t1+b2*t2);
        int64_t sb=a1*t1-b1*t1;
        int64_t as=1LL+sb/sa*2LL;
        if(sb%sa==0) as=as-1LL;
        cout<<as;   
    }
}

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





int N;
//-----------------------------------------------------------------------------------
int main() {
    cin >> N;
    
    int x = 800 * N;
    int y = 200 * (N / 15);

    cout << x - y << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	vector<int> s(4,0);
	int t;
	for(t=0;t<n;t++)
	{
		int a;
		scanf("%d",&a);
		s[a%4] ++;
	}
	int s1;
	s1 = s[1]+s[3]+s[2]%2;
	if(s[0] >= s1-1)
		printf("Yes\n");
	else
		printf("No\n");
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

import static java.lang.System.*;

class Main {
	public static Scanner sc = new Scanner(in);
	public static Random rand=new Random();

	static class P{
		int x;
		int y;
		public P(int x,int y){
			this.x=x;this.y=y;
		}

		@Override
		public boolean equals(Object obj) {
			if(!(obj instanceof P))return false;
			P p=(P)obj;
			return p.x==x && p.y==y;
		}
		@Override
		public String toString() {
			return "("+x+","+y+")";
		}
	}

	public void run() {
		Test:while(true){
			int w=sc.nextInt(),h=sc.nextInt();
			if(w==0 && h==0)return;
			boolean[][] wall=new boolean[h][w];
			Queue<P> pq=new LinkedList<P>();
			for(int i=0;i<h;i++){
				char[] mc=sc.next().toCharArray();
				for(int j=0;j<w;j++){
					switch(mc[j]){
					case '#':
						wall[i][j]=true;
						break;
					case '@':
						wall[i][j]=true;
						pq.offer(new P(j,i));
					}
				}
			}

			int res=1;

			int[][] d=new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
			while(!pq.isEmpty()){
				P p=pq.poll();
				for(int i=0;i<4;i++){
					int x=p.x+d[i][0];
					int y=p.y+d[i][1];
					if(0<=x && x<w && 0<=y && y<h){
						if(!wall[y][x]){
							wall[y][x]=true;
							res++;
							pq.add(new P(x,y));
						}
					}
				}
			}
			ln(res);
		}
	}
	public static void main(String[] args) {
		new Main().run();
	}

	public int[] nextIntArray(int n){
		int[] res=new int[n];
		for(int i=0;i<n;i++){
			res[i]=sc.nextInt();
		}
		return res;
	}
	public static void pr(Object o) {
		out.print(o);
	}
	public static void ln(Object o) {
		out.println(o);
	}
	public static void ln() {
		out.println();
	}
}

Measured memory_bytes: 29784
import java.util.Scanner;

public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    int rtn=0;
    for (int i=0; i<n; i++) {
      int x = sc.nextInt();
      int ml = Math.min(x, k-x);
      rtn+=ml*2;
    }
    sc.close();
    System.out.println(rtn);
  }
}

Measured memory_bytes: 22100
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.UncheckedIOException;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        LightScanner in = new LightScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        BAtCoderBeginnerContest111 solver = new BAtCoderBeginnerContest111();
        solver.solve(1, in, out);
        out.close();
    }

    static class BAtCoderBeginnerContest111 {
        public void solve(int testNumber, LightScanner in, PrintWriter out) {
            int n = in.ints();
            int c = n / 100 * 111;
            out.println(n <= c ? c : c + 111);
        }

    }

    static class LightScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;

        public LightScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
        }

        public String string() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new UncheckedIOException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int ints() {
            return Integer.parseInt(string());
        }

    }
}



Measured memory_bytes: 22740
#include <stdio.h>

int main(){
    int secretNo=0;
    int n=0;
    char buf[100];
    char *pt;
    
    while (scanf("%s",buf)!=EOF){
        pt=buf;
        while (*pt!='\0'){
            if (*pt<'0' || *pt>'9'){
                pt++;
                continue;
            }
            for (n=0; *pt>='0' && *pt<='9'; pt++){
                 n = n*10 + *pt - '0';
            }
            secretNo += n;
        }
    }
    printf("%d\n",secretNo);
    
    return 0;
}

Measured memory_bytes: 968
def main():
    from sys import stdin, setrecursionlimit
    setrecursionlimit(10**6)
    r = stdin.readline()[:-1]
    #n = int(stdin.readline()[:-1])   
    #r = [stdin.readline() for i in range(n)]
    #t = [int(stdin.readline()) for i in range(n)]

    res = 0
    a, b, c, d = map(int, r.split())
    if abs(b-a) <= d and abs(c-b) <= d or abs(c-a) <= d:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()



Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = (s); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for(int i = (n); i >= 0; i--)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(void)
{
    IOS
    int N, C, K;
    cin >> N >> C >> K;
    vector<int> T(N);
    REP(i,N) cin >> T[i];

    sort(ALL(T));
    int c = 0, time = 0;;
    int ans = 0;
    c = 1, time = T[0];
    FOR(i,1,N) {
        if (T[i] - time > K || c >= C) {
            ans++;
            c = 0;
        }
        if (c == 0) {
            time = T[i];
            c++;
        } else {
            c++;
        }
    }
    ans++;

    cout << ans << '\n';

    return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <math.h>
#include <queue>
#include <vector>
using namespace std;
 
int main()
{
    double a,b,c;
    int n,i;
    priority_queue< double, vector<double>, greater<double> > que;
 
    scanf("%d",&n);
 
    for(i = 0; i < n; i++){
        scanf("%lf %lf %lf",&a,&b,&c);
        que.push(a);
        que.push(b);
        que.push(c);
        a = que.top();
        que.pop();
        b = que.top();
        que.pop();
        if(pow( que.top(),2.0 ) == pow( a,2.0 ) + pow( b,2.0 )){
            printf("YES\n");
        }
        else{
            //printf("%lf %lf\n",pow( que.top(),2.0 ),pow( a,2.0 ) + pow( b,2.0 ));
            printf("NO\n");
        }
        que.pop();
    }
 
    return 0;
}

Measured memory_bytes: 2592
#include<stdio.h>
int max(int x,int y)
{
    return x>y?x:y;
}
int min(int x,int y)
{
    return x<y?x:y;
}
int n,a,b;
int main()
{
    scanf("%d %d %d",&n,&a,&b);
    printf("%d %d",min(a,b),max(a+b-n,0));
}

Measured memory_bytes: 128
public class Main {

  private static void solve() {
    int n = ni();
    char[] s = ns();
    if (n % 2 == 1) {
      System.out.println("No");
      return;
    }

    for (int i = 0; i < n / 2; i++) {
      if (s[i] != s[i + n / 2]) {
        System.out.println("No");
        return;
      }
    }
    System.out.println("Yes");

  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}



Measured memory_bytes: 21332
function Main(input) {
  input=input.split("\n");
  if(input[input.length-1]===''){
    input.pop();
  }
  const N=input[0].split(' ')[0]-0;
  const S=input[1];
  var previous='A';
  var t=0;
  for(var i=0;i<S.length;i++){
    if(previous!==S[i]){
      previous=S[i];
      t++;
    }
  }
  console.log(t);
}




//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 32448
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include <cstdlib>

using namespace std;

int main(){

	string s,t;
	cin >> s >> t;
	sort(s.begin(),s.end());
	sort(t.begin(),t.end());
	reverse(t.begin(),t.end());

	int a;
	a = s.size();

	for(int i = 0; i < a; i++){
		if(s == t){
			cout << "No" <<endl;
			return 0;
		}
		else if(s[i]<t[i]){
			cout <<"Yes"<<endl;
			return 0;
		}
		else if(s[i]==t[i]){
			if(i == a-1){
				cout << "Yes" <<endl;
				return 0;
			}
		}
	}
	cout << "No" <<endl;
	return 0;
}


Measured memory_bytes: 256
s = input()
t = input()

ans = ''
#dp[i][j]:sをi文字目、tをj文字目まで見たときの最長部分列長
dp = [[0 for _ in range(len(t)+1)] for _ in range(len(s)+1)]

for i in range(len(s)):
  for j in range(len(t)):
    if s[i] == t[j]:
      dp[i+1][j+1] = dp[i][j] + 1
    else:
      if dp[i+1][j] > dp[i][j+1]:
        dp[i+1][j+1] = dp[i+1][j]
      else:
        dp[i+1][j+1] = dp[i][j+1]
    #print(dp)
#print(dp)
#print(dp[len(s)][len(t)])

# dpを逆にたどって最長部分文字列を復元する
ans = ''
i = len(s)
j = len(t)
while(dp[i][j]>0):
  if dp[i][j] == dp[i-1][j-1] +1 and dp[i][j] == dp[i-1][j] +1 and dp[i][j] == dp[i][j-1] +1:
    ans += s[i-1]
    i -= 1
    j -= 1
  elif dp[i-1][j] > dp[i][j-1]:
    i -= 1
  else:
    j -= 1
print(''.join(reversed(list(ans))))


Measured memory_bytes: 120796
#include <iostream>
using namespace std;
int w,h,p,x[125010],y[125010],t,ans, map[60][60];
int main() {
	cin>>w>>h>>t>>p;
	for(int i=0;i<p;i++)cin>>x[i]>>y[i]>>t;
	for(int i=0;i<h;i++)for(int j=0;j<w;j++)cin>>map[j][i];
	for(int i=0;i<p;i++)if(map[x[i]][y[i]])ans++;
	cout<<ans<<endl;
	return 0;
}


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

const string YES = "YES";
const string NO = "NO";

void solve(long long a, long long b, long long c){
    if(2*b == a+c) cout << YES << endl;
    else cout << NO << endl;
}

int main(){
    long long a;
    scanf("%lld",&a);
    long long b;
    scanf("%lld",&b);
    long long c;
    scanf("%lld",&c);
    solve(a, b, c);
    return 0;
}


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

using namespace std;
using lint = long long;

int main(void)
{
    lint A, B, N;
    cin >> A >> B >> N;

    lint x = B-1;
    if(N < x){
        x = N;
    }

    cout << A * x / B - A * (x / B) << endl;
    return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main(){
    int n, ans = 0;
    cin >> n;
    int l[n], r[n];
    for (int i = 0; i < n; i++){
        cin >> l[i] >> r[i];
        ans += abs(l[i] - r[i]) + 1;
    }
    cout << ans;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#ifdef _WIN32
#include "debug.hpp"
#endif
using namespace std;

#define rep(i, N)  for(int i = 0; i < (N); i++)
#define reps(i, N) for(int i = 1; i <= (N); i++)
#define repr(i, N) for(int i = (N) - 1; i >= 0; i--)
#define pub push_back

template<typename T> 
void chmax(T &a, T b){ a = max(a, b); };
template<typename T> 
void chmin(T &a, T b){ a = min(a, b); };

typedef long long ll;
typedef pair<int, int> P;
const int INF = 100000000;
const ll LINF = 10000000000000000;
const int MOD = 1000000007;
const int dx[9] = { 0, 1,  0, -1, 1,  1, -1, -1, 0};
const int dy[9] = { 1, 0, -1,  0, 1, -1, -1,  1, 0};
//--------------------------------------//
int N;
ll A[200];

void solve(){
	int c = 0;
	ll n = 2;
	while(1){
		rep(i, N){
			if(A[i] % n or A[i] < n){
				goto A;
			}
		}
		c++;
		n *= 2;
	}
A:
	cout << c << endl;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> N;
	rep(i, N) {
		cin >> A[i];
	}
		solve();
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define N 100002
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;

int main(){
  ll w,h;
  cin>>w>>h;
  vector <PP> path;

  ll p[N],q[N];
  for(int i=0;i<w;i++) cin>>p[i],path.push_back(PP(P(p[i],i+1),0));
  for(int i=0;i<h;i++) cin>>q[i],path.push_back(PP(P(q[i],i+1),1));
  sort(path.begin(),path.end());
  
  ll sum=0,cnt[2]={},wh[]={w+1,h+1};
  bool used[2][N]={},cnted[2][N]={},flg[2]={};
  
  for(int i=0;i<path.size();i++){
    ll cost=path[i].first.first;
    ll k=path[i].first.second;
    ll f=path[i].second;
    cnt[f]++;
    sum+=cost*(wh[!f]-cnt[!f]);
  }
  cout <<sum<<endl;  

  return 0;
}


Measured memory_bytes: 7536
n, m, k = map(int, input().split())
MOD = 998244353
fact = [0 for _ in range(n+1)]
fact[1] = m

for i in range(2, n+1):
    fact[i] = fact[i-1] * (m - 1)
    fact[i] %= MOD

class Facts():
    # O(max_num)
    def __init__(self, max_num=2 * 10**5, p=10**9 + 7):
        self.p = p
        self.max_num = max_num
        self.fact = [1] * (self.max_num + 1)
        for i in range(1, self.max_num + 1):
            self.fact[i] = self.fact[i-1] * i
            self.fact[i] %= self.p

    def comb(self, n, k):
        # nCk mod p with memo
        # O(log(p))
        if n < 0 or k < 0 or n < k:
            return 0
        if n == 0 or k == 0:
            return 1
        a = self.fact[n]
        b = self.fact[k]
        c = self.fact[n-k]
        return (a*self.power_func(b, self.p-2) *
                self.power_func(c, self.p-2)) % self.p

    def comb_base(self, n, k):
        # nCk mod p w/o memo
        # O(min(n, k)) ?
        if n < 0 or k < 0 or n < k:
            return 0
        if n == 0 or k == 0:
            return 1
        a, b = 1, 1
        for i in range(k):
            a *= (n-i)
            a %= MOD
        for i in range(k):
            b *= (k-i)
            b %= MOD
        return (a*self.power_func(b, self.p-2)) % self.p

    def perm(self, n, k):
        # nPk mod p
        # O(log(p))
        if n < 0 or k < 0 or n < k:
            return 0
        if n == 0 or k == 0:
            return 1
        a = self.fact[n]
        b = self.fact[n-k]
        return (a * self.power_func(b, self.p-2)) % self.p


    def power_func(self, a, b):
        # a^b mod p
        # O(log(b))
        ans = 1
        while b > 0:
            if b & 1:
                ans = ans * a % self.p
            a = a * a % self.p
            b >>= 1
        return ans


facts = Facts(p=MOD)
ans = 0
for i in range(n-k, n+1):
    if i != n:
        ans += fact[i] * facts.comb(n-1, n-i)
    else:
        ans += fact[i]
    ans %= MOD
print(ans)

Measured memory_bytes: 82824
#include<bits/stdc++.h>
using namespace std;
int main(){
  vector<int>A(3);cin>>A[0]>>A[1]>>A[2];
  sort(A.begin(),A.end());
  
  if((A[2]-A[0])%2==0 && (A[2]-A[1])%2==0)cout<<(A[2]-A[0])/2+(A[2]-A[1])/2;
  if((A[2]-A[0])%2==0 && (A[2]-A[1])%2==1)cout<<(A[2]-A[0])/2+(A[2]-A[1])/2+2;
  if((A[2]-A[0])%2==1 && (A[2]-A[1])%2==0)cout<<(A[2]-A[0])/2+(A[2]-A[1])/2+2;
  if((A[2]-A[0])%2==1 && (A[2]-A[1])%2==1)cout<<(A[2]-A[0])/2+(A[2]-A[1])/2+1;
  
  
}

Measured memory_bytes: 256
def main():
    num, max_jump = map(int, input().split())
    data = list(map(int, input().split()))

    dp = [0 for i in range(num - 1)]
    dp[0] = abs(data[1] - data[0])

    for i in range(1, num - 1):
        min_data = 10 ** 10
        for j in range(min(max_jump, i + 1)):
            min_data = min(min_data, dp[i - 1 - j] + abs(data[i + 1] - data[i - j]))
        dp[i] = min_data


    print(dp[-1])

if __name__ == '__main__':
    main()


Measured memory_bytes: 56544
a,b = map(int,input().split())
if abs((b-a)/2) == int(abs((b-a)/2)):
    ans = a + int(abs((b-a)/2))
    if not (a < ans < b):
        ans = a - int(abs((b-a)/2))
    print(ans)
else:
    print('IMPOSSIBLE')

Measured memory_bytes: 3060