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

using namespace std;

#define fastio ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define t_times int t; cin >> t; while(t--)
#define _parr(a, n) for(int __i = 0; __i < (int )n; __i++) cout << a[__i] << ' '; cout << '\n'
#define fr(i, p, n) for(int i = (int )p; i < (int )n; i++)
#define frn(i, p, n) for(int i = (int )p; i <= (int )n; i++)
#define rev(i, n, p) for(int i = (int )n; i >= (int )p; i--)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).begin(), (c).end()
#define sci(n) scanf("%d", &n)
#define scl(n) scanf("%lld", &n)
#define prin(n) printf("%d\n", n)
#define prln(n) printf("%lld\n", n)
#define mp make_pair
#define F first
#define S second
#define pb push_back

typedef long long int LL;
typedef unsigned long long ULL;
typedef unsigned int uint;
typedef pair< int, int> ii;
typedef vector< int> vi;

const int mod = 1e9 + 7;
const LL INF = 9e18 + 2e17;
const int inf = 2e9;
const int N = 1e5 + 22;
const double eps = 1e-10;

int n, k;
long long fac[N], a[N];

int _modp(int a, int b) {
	long long res = 1;
	while(b) {
		if(b & 1) res = res * a % mod;
		a = (1LL * a * a) % mod;
		b >>= 1;
	}
	return res;
}

int _min() {
	long long res = 0, num = 0, den = 0;
	frn(i, 1, n - k + 1) {
		num = fac[n - i] * a[i] % mod;
		den = fac[k - 1] * fac[n - i - k + 1] % mod;
		num = num * _modp(den, mod - 2) % mod;
		num = (num + mod) % mod;
		res = (res + num) % mod;
	}
	return res;
}

int _max() {
	long long res = 0, num = 0, den = 0;
	rev(i, n, k) {
		num = fac[i - 1] * a[i] % mod;
		den = fac[k - 1] * fac[i - k] % mod;
		num = (num * _modp(den, mod - 2)) % mod;
		num = (num + mod) % mod;
		res = (res + num) % mod;
	}
	return res;
}
void _solve() {
	fac[0] = 1;
	fr(i, 1, N) fac[i] = i * fac[i - 1] % mod;
	cin >> n >> k;
	frn(i, 1, n) cin >> a[i];
	int mns = 0, mxs = 0;
	sort(a + 1, a + n + 1);
	mns = _min(), mxs = _max();
	//cout << mns << ' ' << mxs << '\n';
	mxs = (mxs - mns) % mod;
	mxs = (mxs + mod) % mod;
	cout << mxs << '\n';
}

int main() {
    fastio;
    //t_times
    _solve();
    return 0;
}

Measured memory_bytes: 1792
n,k=map(int,input().split())
x=list(map(int,input().split()))
minus_x=[i for i in x if i<0]
pz=len(minus_x)
start=pz-k
if start<0:
    start=0
if pz+k-1>n-1:
    end=n-k+1
else:
    end=pz+1
l=[]
for i in range(start,end):
    l.append(x[i+k-1]-x[i]+min(abs(x[i+k-1]),abs(x[i])))
print(min(l))


Measured memory_bytes: 14252
//    ____       ____                 _           
//   |  _ \ _ __|  _ \  ___ _ __   __| |_ __ ___  
//   | | | | '__| | | |/ _ \ '_ \ / _` | '__/ _ \ 
//   | |_| | |_ | |_| |  __/ | | | (_| | | | (_) |
//   |____/|_(_)|____/ \___|_| |_|\__,_|_|  \___/ 
//                                                

 
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;


#define db1(x) cout<<#x<<"="<<x<<'\n'
#define db2(x,y) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<'\n'
#define db3(x,y,z) cout<<#x<<"="<<x<<","<<#y<<"="<<y<<","<<#z<<"="<<z<<'\n'
#define rep(i,n) for(int i=0;i<(n);++i)
#define repA(i,a,n) for(int i=a;i<=(n);++i)
#define repD(i,a,n) for(int i=a;i>=(n);--i)
#define f first
#define s second
#define pb push_back
#define ll long long

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll LLOO = 1e18+7;
const ll OO = 1e9+7;
const int MOD = 1e9+7;
const int N = 1e5+7;



int main()
{
	
	int x;
	scanf("%d",&x);
	int x500 = x/500;
	x%=500;
	int x5 = x/5;
	x%=5;
	ll ans = x500*1000LL + x5*5LL;
	printf("%lld\n",ans);
	
    return 0;
}



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

using namespace std;
typedef long long ll;

#define  input freopen("in.txt","r",stdin)
#define  output freopen("out.txt","w",stdout)

int main()
{
	//input;
	//output;

	ll x1, x2, x3, y1, y2, y3, s;
	cin >> s;

	x1 = 0, y1 = 0, x2 = 1e9, y2 = 1;

 	y3 = s/x2;
 	if((s%x2)!=0) y3+=1;
 	x3 = (y3*x2)-s;
 	cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << ' ' << x3 << ' ' << y3 << '\n';
 	return 0;
 	
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"math"
)

func main() {
	var n int
	fmt.Scan(&n)

	x := int(math.Sqrt(float64(n)))

	var min int
	for i := x + 1; i >= 1; i-- {
		if n%i == 0 {
			min = (i - 1) + (n/i - 1)
			break
		}
	}

	fmt.Print(min)
}


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

using namespace std;
using ll = long long;
vector<int> v[3];
ll ans = 0;
void solve(int a, int b, int c)
{
    int i, j, k;
    for(auto i : v[a])  // R, G, B + R, B, G + B, R, G + B, G, R + G, R, B + G, B , R
    {
        int id = upper_bound(v[b].begin(), v[b].end(), i) - v[b].begin();
        for(j=id;j<v[b].size();j++)
        {
            int id1 = upper_bound(v[c].begin(), v[c].end(), v[b][j]) - v[c].begin();
            ans+=(v[c].size() - id1);
            if(binary_search(v[c].begin(), v[c].end(), 2*v[b][j] - i))
                ans--;
        }
    }
}
int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int i;
    for(i=0;i<n;i++)
        if(s[i] == 'R') v[0].push_back(i);
        else if(s[i] == 'G') v[1].push_back(i);
        else v[2].push_back(i);
    //ll ans = 0;
    solve(0, 1, 2);
    solve(0, 2, 1);
    solve(1, 0, 2);
    solve(1, 2, 0);
    solve(2, 0, 1);
    solve(2, 1, 0);
    cout << ans << '\n';
}

Measured memory_bytes: 3672
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
       String str=sc.nextLine();
        BigInteger bg =new BigInteger(str);
        BigInteger nine=new BigInteger("9");
        BigInteger reminder=bg.remainder(nine);
        BigInteger y=new BigInteger("0");
        if(reminder.compareTo(y)==0){
            System.out.println("Yes");
        }
        else {
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 42552
#include <bits/stdc++.h>
using namespace std;
int a[5];

int main()
{
    memset(a,0,sizeof(a));
int n;
cin>>n;
string s;
for(int i=0;i<n;i++)
{
cin>>s;
if(s[0]=='M')
{
a[0]++;
}
else if(s[0]=='A')
{
a[1]++;
}
else if(s[0]=='R')
{
a[2]++;
}
else if(s[0]=='C')
{
a[3]++;
}
else if(s[0]=='H'){
a[4]++;
}
}
long long ans=0;
for(int i=0;i<5;i++)
{
    for(int j=i+1;j<5;j++)
    {
        for(int k=j+1;k<5;k++)
        {
    ans+=1LL*a[i]*a[j]*a[k];

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


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


int main()
{
	int n, nums[100];
	cin >> n;

	for (int i = 0;i < n;i++) {
		cin >> nums[i];
	}

	for (int i = n - 1;i >= 0;i--) {
		cout << nums[i];
		if (i) {
			cout << " ";
		}
	}

	cout << "\n";

    return 0;
}



Measured memory_bytes: 3116
#include <stdio.h>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <iostream>
#include<math.h>
#include<bitset>
#include<iomanip>
using namespace std;

int main() {
	string s; cin >> s;
	bool x;
	if (s[0] == 'B')x = 1;
	else x = 0;
	int c = 0;
	for (int i = 1; i < s.size(); i++) {
		if (s[i] == 'B'&&x == 0) {
			c++; x = 1;
		}
		if (s[i] == 'W'&&x == 1) {
			c++; x = 0;
		}
	}
	cout << c << endl;

}



Measured memory_bytes: 512
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=400;
int n,k,mod,dp[N][N][N];
inline void add(int &a,int b){a=(a+b)%mod;}
inline void del(int &a,int b){a=(a-b+mod)%mod;}
inline void mul(int &a,int b){a=(a*b)%mod;}
signed main()
{
	scanf("%lld%lld%lld",&n,&k,&mod);
	dp[0][1][0]=1;
	for (int i=0;i<=n;i++)
	{
		for (int j=1;j<=k;j++)
		{
			for (int p=i;p>=0;p--)
			{
				if (p>0) add(dp[i][j][p-1],dp[i][j][p]);
				else add(dp[i][j+1][i],dp[i][j][p]);
				add(dp[i+1][j][p],dp[i][j][p]*(p+1)%mod);
			}
		}
	}
	printf("%lld\n",dp[n][k+1][n]);
}


Measured memory_bytes: 288440
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = pow(10, 9) + 7;
//const int MOD = 998244353;
//const int MOD = ;
int mod(int A, int M) {return (A % M + M) % M;}
const int INF = 1LL << 60;
template <class T> bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template <class T> bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
int divCeil(int A, int B) {return (A + (B - 1)) / B;}
int myctoi(char C) {return C - '0';}
char myitoc(int N) {return '0' + N;}

signed main()
{
  int N, x;
  cin >> N >> x;
  vector<int> A(N + 1);
  A.at(0) = 0;
  for (int i = 1; i < N + 1; i++)
  {
    cin >> A.at(i);
  }

  int ans = 0;
  for (int i = 0; i < N; i++)
  {
    if (A.at(i) + A.at(i + 1) > x)
    {
      int tmp = A.at(i) + A.at(i + 1) - x;
      ans += tmp;
      A.at(i + 1) = max((int)0, A.at(i + 1) - tmp);
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 1024
n=int(input())
A=[int(input()) for _ in range(n)]+[0]

cnt=0
for i in range(n):
    cnt +=A[i]//2
    if A[i+1]!=0:
        cnt +=A[i]%2
        A[i+1] -=A[i]%2
print(cnt)

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

int main() {
  int x; cin >> x;
  puts(x >= 30 ? "Yes" : "No");
  return 0;
}


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

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> original(n, vector<int>(n, 1e9)), adj;
    vector<pair<int, int>> edge;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c, a--, b--;
        original[a][b] = original[b][a] = c;
        edge.emplace_back(a, b);
    }
    adj = original;

    vector<vector<int>> updated(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                adj[j][k] = min(adj[j][k], adj[j][i] + adj[i][k]);
            }
        }
    }

    int ans = 0;
    for (auto& e : edge) {
        if (original[e.first][e.second] != adj[e.first][e.second]) ans++;
    }
    cout << ans << endl;
}


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

int main(void) {
    string S, T, U;
    int A, B;
    
    cin >> S >> T;
    cin >> A >> B;
    cin >> U;
    
    if (S == U) {
        cout << A - 1 << " " << B << endl;
    } else if (T == U) {
        cout << A << " " << B - 1 << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
	int a,b,c;
	while(scanf("%d%d%d",&a,&b,&c),a+b+c){
		int A=99999999;
		int B=99999999;
		for(int i=0;a*i<=c;i++){
			if((c-a*i)%b==0){
				if(A+B>i+(c-a*i)/b||(A+B==i+(c-a*i)/b&&A*a+B*b>c)){
					A=i;
					B=(c-a*i)/b;
				}
			}
		}
		for(int i=0;i<=50000;i++){
			if((i*a+c)%b==0){
				if(A+B>i+(c+i*a)/b||(A+B==i+(c+i*a)/b&&A*a+B*b>i*a+c+i*a)){
					A=i;
					B=(c+a*i)/b;
				}
			}
			if((i*b+c)%a==0){
				if(A+B>i+(i*b+c)/a||(A+B==i+(i*b+c)/a&&A*a+B*b>i*b+c+i*b)){
					A=(c+i*b)/a;
					B=i;
				}
			}
		}
		printf("%d %d\n",A,B);
	}
}

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

const int64_t INF = 2 << 30;

int main() {
  int N;
  cin>>N;
  int h[N], dp[N];
  for (int i=0;i<N;i++){
    cin>>h[i];
    dp[i]=INF;
  }
  
  dp[0]=0;
  dp[1]=max(h[1]-h[0],h[0]-h[1]);
  
  for(int i=2;i<N;i++){
  	dp[i]=min(dp[i-2]+max(h[i]-h[i-2],h[i-2]-h[i]),dp[i-1]+max(h[i]-h[i-1],h[i-1]-h[i]));
  }
  cout << dp[N-1] << endl;
}  

Measured memory_bytes: 1024
#include<stdio.h>

static const int N = 1000;

void trace(int A[], int n){
  int i;
  for ( i = 1; i <= n; i++ ){
    if ( i > 1 ) printf(" ");
    printf("%d", A[i]);
  }
  printf("\n");
}

int main(){
  int n, i, j,key;
  int A[N+1];
  scanf("%d", &n);

  for ( i = 1; i <= n; i++ ) scanf("%d", &A[i]);
  
  for(i=1; i<=n; i++){
  key = A[i];
  j = i-1;
 
  while(j >= 0 && A[j] > key){
    A[j+1] = A[j];
    j--;
    A[j+1] = key;
  }
  trace(A,n);
  }
  return 0;
}

Measured memory_bytes: 608
N, A, B = (int(i) for i in input().split())
h = [0]*N
for i in range(N):
    h[i] = int(input())
hmax = max(h)
A = A-B

def func(k):
    hn = [a - k*B for a in h]
    res = 0
    for i in range(N):
        if hn[i] > 0:
            res += (hn[i]-1+A)//A
    return res <= k

left = 0
right = hmax//B + 1
while True:
    if left == right:
        break
    half = (left + right)//2
    if func(half):
        right = half
    else:
        left = half + 1
print(left)

Measured memory_bytes: 11056
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  map<string, int> plus;
  //set<string> stplus;
  string tmp;
  for(int i=0; i<n; i++){
    cin >> tmp;
    plus[tmp]++;
  }
  int m;
  cin >> m;
  map<string, int> minus;
  for(int i=0; i<m; i++){
    cin >> tmp;
    minus[tmp]++;
  }
  int ans = 0;
  for(auto itr = plus.begin(); itr != plus.end(); ++itr){
    ans = max(ans, max(plus[itr->first]-minus[itr->first], 0));}
  cout << ans << endl;
}

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

namespace AtCoder.Abc
{
    class A_162_Lucky7
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 文字列の入力
            string s = Console.ReadLine();
            bool flg = false;

            for (int i = 0; i < s.Length; i++)
            {
                if (s[i] == '7')
                {
                    flg = true;
                    Console.WriteLine("Yes");
                    break;
                }
            }

            if (flg == false)
            {
                Console.WriteLine("No");
            }

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 25740
#include <bits/stdc++.h>
#include <cstdlib>
using namespace std;
#define ll long long
typedef vector<vector<ll> > matrix;
#define pb push_back
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
const double PI  =3.141592653589793238463;
long long MOD = 1000000007;

int stringToInteger(string x){
    int gg=0;
    stringstream geek(x);
    geek >> gg;
    return gg;
}

ll powmod(ll a,ll b,ll m)
{
    ll ans=1;
    while(b>0){ if(b%2)
        {ans*=a; ans%=m;}
         b/=2; a=a*a; a=a%m;
        }
        return ans%m;
}
ll gcd(ll a,ll b)
{

    return __gcd(a,b);
}
ll mulmod(ll a,ll b,ll m)
{  ll ans=0;
    a %=m;
    while (b>0)
    {       if(b&1) ans = (ans + a) % m;
        a = (a * 2)%m;
        b /= 2;
    }
    return ans % m;
}

ll f[2000001];



ll pow(ll a, ll b, ll MOD)
{
 ll x=1,y=a;
 while(b > 0)
 	{
 		if(b%2 == 1)
 	{
 		x=(x*y);
 		if(x>MOD) x%=MOD;
 	}
 	y = (y*y);
 	if(y>MOD) y%=MOD;
 	b /= 2;
 	}
 return x;
}

/* Modular Multiplicative Inverse
 Using Euler's Theorem
 a^(phi(m)) = 1 (mod m)
 a^(-1) = a^(m-2) (mod m) */
ll InverseEuler(ll n, ll MOD)
{
 return pow(n,MOD-2,MOD);
}

bool prime[100005];
void seive()
{  memset(prime,true,sizeof(prime));
    for(int i=2;i*i<=100005;i++)
    {
         if(prime[i]==true) {
        for(int j=2*i;j<=(100005);j+=i)
           { prime[j]=false;}
           }

    }
}
bool in(float x1,float y1,float x,float y,float r )
{
    if(abs(x1-x)*abs(x1-x)+abs(y1-y)*abs(y1-y)<=r*r) return true;
    return false;
}
bool cmp(pair<int,int> &a,pair<int,int> &b)
{

        return (a.second<b.second);
}
//
//vector<vector<int> >matrix;
matrix mul(matrix A,matrix B)
{
    matrix C(3, vector<ll>(3));
    for(int i=1;i<=2;i++)
    for(int j=1;j<=2;j++)
     for(int k=1;k<=2;k++)
         C[i][j] = (C[i][j] + A[i][k] * B[k][j]);
    return C;

}
matrix pow(matrix A, int p)
{
    if (p == 1)
        return A;
    if (p % 2)
        return mul(A, pow(A, p-1));
    matrix X = pow(A, p/2);
    return mul(X, X);
}
ll fib(int N,int a,int b)
{
    vector<ll> F1(3);
    F1[1] = a;
    F1[2] = b;
    matrix T(3, vector<ll>(3));
    T[1][1] = 0, T[1][2] = 1;
    T[2][1] = -1, T[2][2] = 1;
    if (N == 1)
        return a;
    if(N==2) return b;
    T = pow(T, N-1);
    ll res = 0;
    for(int i=1;i<=2;i++)
        res = (res + T[1][i] * F1[i]+ MOD)%MOD ;
    return res;
}

//1 2 3 4 5
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

 int t =1;
 while(t--)
  {
      string s;
      cin>>s;
      string t = s;
      reverse(s.begin(),s.end());
      if(s==t) cout<<"Yes";
      else cout<<"No";
      
     // 3 0 3 0 3

  }
}


Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
)

func main() {
	var a int
	fmt.Scan(&a)
	vals := make([]float64, a)
	for i := 0; i < a; i++ {
		fmt.Scan(&vals[i])
	}

	//sort.SliceStable(vals, func(i, j int) bool { return i > j }) // Go 1.8
	sort.Sort(sort.Float64Slice(vals))

	var total float64
	for i := 0; i < a; i++ {
		v := vals[i]
		if i == 0 {
			total = v
		} else {
			total = (total + v) / 2
		}
	}

	fmt.Println(total)
}


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

int a[100000], b[100000], c[100000];
int d[100001], e[100001], f[100001];
signed main() {
	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i];
	}
	for (int i = 1; i <= n; i++) {
		d[i] = max(e[i - 1], f[i - 1]) + a[i - 1];
		e[i] = max(d[i - 1], f[i - 1]) + b[i - 1];
		f[i] = max(d[i - 1], e[i - 1]) + c[i - 1];
	}
	cout << max({ d[n],e[n],f[n] }) << endl;
}

Measured memory_bytes: 2560
from collections import defaultdict

N = int(input())
SP = sorted([list(input().split()) + [i + 1] for i in range(N)])

d = defaultdict(list)

for s, p, i in SP:
    d[s].append((int(p), i))

ans = []

for k, v in d.items():
    v = sorted(v)[::-1]
    for i, j in v:
        ans.append(str(j))

print('\n'.join(ans))


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

int main(void)
{
    int N;

    while(cin >> N, N){
        int d[10];
        for(int i = 0; i < 10; i++)
            d[i] = 0;

        int No;
        for(int i = 0; i < N; i++){
            cin >> No;
            d[No]++;
        }

       for(int i = 0; i < 10; i++){
           if(d[i] == 0)printf("-");
           else
           for(int j = 0; j < d[i]; j++) printf("*");
printf("\n");
       }
}

return 0;
}

Measured memory_bytes: 1112
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int [][][] data=new int[4][3][10];
		for(int i=1;i<=n;i++) {
			int b=sc.nextInt();
			int f=sc.nextInt();
			int r=sc.nextInt();
			int v=sc.nextInt();
			data[b-1][f-1][r-1]+=v;
		}

		for(int i=0;i<4;i++) {
			for(int j=0;j<3;j++) {
				for(int k=0;k<10;k++) {
					System.out.print(" "+data[i][j][k]);
				}
				System.out.println();
			}
			if(i!=3) {
				System.out.println("####################");
			}
		}
	}
}


Measured memory_bytes: 29616
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		String result = "";

		for (int i = 0; i < 10000; i++) {
			String line = sc.nextLine();
			 result = line;
			 if (line.equals("0")){
				 break;
			 }
			 System.out.println("Case " + (i + 1) + ": " + line);

		}




	}

}


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

#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
#define rep2(i,s,n) for(long long i=(s); i<(long long)(n);i++)

typedef long long ll;

const ll inf = 1e18+7;
const ll mod = 1e9+7;

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

    vector<int>S(26,-1),T(26,-1);

    rep(i,s.size()){
        int a=s[i]-'a',b=t[i]-'a';
        if(S[a]!=-1||T[b]!=-1){
            if(S[a]!=b||T[b]!=a){
                cout<<"No"<<endl;
                return 0;
            }
        }

        S[a]=b;
        T[b]=a;
    }

    cout<<"Yes"<<endl;

}



Measured memory_bytes: 776
from collections import deque
import pprint
import numpy as np

h, w = map(int, input().split())
maze = [['*']*(w+2) for j in range(h+2)]
for i in range(1,h+1):
    maze[i][1:] = map(str,list(input()))
    maze[i].append('*')

score = []
def bfs(maze):
    for i in range(1,h+1):
        for l in range(1,w+1):
            if maze[i][l] == '#':
                continue
            visited = [[-1]*(w+1) for j in range(h+1)]
            queue = deque()
            queue.append([i, l])
            visited[i][l] = 0
            while(queue):
                y, x = queue.popleft()
                for j,k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                    new_x, new_y = x+j, y+k
                    if maze[new_y][new_x] == '.' and visited[new_y][new_x] == -1:
                        queue.append([new_y, new_x])
                        visited[new_y][new_x] = visited[y][x] + 1
            idx = np.unravel_index(np.argmax(np.array(visited)), np.array(visited).shape)
            score.append(np.array(visited)[idx])
    return (max(score))

print(bfs(maze))


Measured memory_bytes: 12500
k = int(input())
a = [x for x in range(1, 10)]

while(1):
    if(k <= len(a)):
        print(a[k-1])
        break
    k -= len(a)
    old = []
    old, a = a, old
    for x in old:
        for i in range(-1, 2):
            d = x % 10+ i
            if(d < 0 or d > 9):
                continue
            nx = x*10 + d
            a.append(nx)


Measured memory_bytes: 11028
from fractions import gcd
def gcm(a,b):
    k = a * b / gcd(a,b)
    return int(k)

A,B,C,D = map(int,input().split())
bk = B - B//C - B//D + B//gcm(C,D)
ak = (A-1) - (A-1)//C - (A-1)//D + (A-1)//gcm(C,D)

print(bk-ak)


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

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

using namespace std;

int main() {
  int64_t n, x;
  std::cin >> n >> x;
  std::vector<int64_t> a(n);
  rep(i, n) std::cin >> a[i];

  sort(a.begin(), a.end());
  int ans = 0;
  rep(i, n) {
    if (a[i] <= x) {
      x -= a[i];
      ans++;
    } else {
      break;
    }
  }

  if (ans == n && x > 0) {
    ans--;
  }

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


Measured memory_bytes: 3556
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <queue>
#include <cmath>
typedef long long ll;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mod 1000000007
const long long INF = 1LL<<60;

int main(){
	int N,M,X;
	cin >> N >> M >> X;
	vector<int> A(M);
	for(int i = 0; i < M; i++){
		cin >> A[i];
	}
	int left = 0, right = 0;
	for(int i = 0; i < M; i++){
		if(A[i] < X){
			left++;
		} else{
			right++;
		}
	}
	int ans = 0;
	ans = min(left, right);
	cout << ans << endl;
}	

Measured memory_bytes: 256
using System;
//using System.Collections.Generic;
public class ProCon
{
    public static void Main(){     
        string[] line1 =　Console.ReadLine().Split(' ');

        long coin = long.Parse(line1[0]);
        long happiness = 0;
        happiness += (coin / 500) * 1000;
        coin = coin % 500;
        happiness += (coin / 5) * 5;

        Console.WriteLine(happiness);
    }
}

Measured memory_bytes: 13140
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c0 = min(a) + min(b)
for i in range(M):
    x, y, c = map(int, input().split())
    x -= 1
    y -= 1
    cnext = a[x] + b[y] - c
    c0 = min(c0, cnext)
print(c0)

Measured memory_bytes: 18736
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define vi vector<int>
#define vivi vector<vi>
const int INF = 1<<29;
typedef long long ll;

int dp[100][2][100];//dp[keta][未満である][0でない数の個数]

struct UnionFind {
  vi parent;
  UnionFind(int N) : parent(N) {
    rep(i, N)parent[i] = i;
  }

  int getRoot(int child){
    return ((parent[child] == child) ? child : parent[child] = getRoot(parent[child]));
  }
  void unite(int x, int y){
    int root_x = getRoot(x);
    int root_y = getRoot(y);
    if(root_x == root_y)return;
    parent[root_x] = parent[root_y];
  }
  bool isSame(int x, int y){
    return getRoot(x) == getRoot(y);
  }
};
int main(){
    int X;cin >> X;
    int ans1 = X % 100, ans2 = X / 100;
    if(ans2 * 5 >= ans1)
        cout << 1;
    else
        cout << 0;
}


Measured memory_bytes: 384
#include<cstdio>
const int N=55;
long long dp[N][N*N];
int n,a,x[N];
int main()
{
    scanf("%d %d",&n,&a);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x[i]);
    }
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=i-1;j>=0;j--)    //每一次个数向下减少
        {
             for(int k=0;k<=N*j;k++)    //优化时间  由于k最大为N*j次
            {
                dp[j+1][k+x[i]]=dp[j+1][k+x[i]]+dp[j][k];       //个数加1 则找到前面个数的值相加
            }
        }
    }
    long long ans=0;
    for(int i=1;i<=n;i++)
            ans+=dp[i][i*a];    //累计所有个数会出现平均值满足a的情况
    printf("%lld",ans);
    return 0;
}

Measured memory_bytes: 896
#include <stdio.h>

int main(void)
{
	int n, a, b, c;
	int d[128];
	int i, j;
	int temp;
	int max = 0;
	int money = 0;
	int cal = 0;

	scanf("%d", &n);
	scanf("%d %d", &a, &b);
	scanf("%d", &c);

	for (i = 0; i < n; i++){
		scanf("%d", &d[i]);
	}

	for (i = 0; i < n - 1; i++){
		for (j = n - 1; j > i; j--){
			if (d[j - 1]  < d[j]){
				temp = d[j];
				d[j] = d[j - 1];
				d[j - 1] = temp;
			}
		}
	}
	
	cal = c;
		
	for (i = 0; i < n; i++){
		cal += d[i];

		if (cal / (a + b * (i+ 1)) > max){
			max = cal / (a + b * (i + 1));
		}
	}
	printf("%d\n", max);
	
	return (0);
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const ll INF = 1LL << 60;

int main(){
     ll n, k;
     cin >> n >> k;
     vector<ll> h(n);
     rep(i,n) cin >> h.at(i);
     sort(all(h));
     ll ans=1e9;
     for(int i=0; i<=n-k; i++){
         ll diff = h.at(i+k-1) - h.at(i);
         ans = min(ans,diff);
     }
     cout << ans << endl;

     
}

Measured memory_bytes: 4028
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
	int n; cin>>n;
	if(n%2==1){
		cout<<"No"<<endl;
		return 0;
	}
	string s;
	cin>>s;
	for(int i=0; i<n/2; i++){
		if(s[i]!=s[i+n/2]){
			cout<<"No"<<endl;
			return 0;
		}
	}
	cout<<"Yes"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream> 
#include<string>
#include<algorithm>
using namespace std;
int main()
{
	int a, b,c;
	cin >> a >> b>>c;
	if (c > b && b > a) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}


Measured memory_bytes: 3124
#include<bits/stdc++.h>
#define PI 3.141592653589
#define ll long long
using namespace std;

int main(){
  int n, m;
  cin >> n >> m;
  
  ll ac = 0;
  ll pena = 0;

  int wa[n] = {}, isac[n] = {};
  for(int i=0; i<m; ++i){
    int p; string s;
    cin >> p >> s;
    --p;
    if(s == "AC"){
      if(!isac[p]){
        ++ac;
        pena += wa[p];
        isac[p] = true;
      }
    }
    else wa[p]++;
  }
  cout << ac << " " << pena << endl;


}



Measured memory_bytes: 1024
import java.util.PriorityQueue;
import java.util.Scanner;

//Power
public class Main{

	class R implements Comparable<R>{
		int s, t;
		public R(int s, int t) {
			this.s = s;
			this.t = t;
		}
		public int compareTo(R o) {
			return s-o.s;
		}
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(), M = sc.nextInt();
		PriorityQueue<R> q = new PriorityQueue<R>();
		while(M--!=0)q.add(new R(sc.nextInt(), sc.nextInt()));
		int res = 0, f = 0;
		while(!q.isEmpty()&&f<N){
			if(f+1 < q.peek().s)break;
			int max = q.poll().t;
			while(!q.isEmpty()&&q.peek().s<=f+1)max = Math.max(max, q.poll().t);
			if(f<max){
				res++; f = max;
			}
		}
		System.out.println(f==N?res:"Impossible");
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

s = inputS()

s = list(s)
s_ = s[::-1]

count = 0
for i in range(len(s)):
  if s[i] != s_[i]:
    count += 1
    
print(count//2)


Measured memory_bytes: 63980
/**
 *      purpose : CODE FESTIVAL 2016 Final
 *      author  : kyomukyomupurin
 *      created : 2018-11-13 01:40:20
**/

#include <bits/stdc++.h>
using namespace std;
#define int64 long long
#define print(x) cout << (x) << '\n'

inline int square(int N){
    for (int i = 1; ; ++i){
        if (N > (i - 1) * i / 2 && N <= i * (i + 1) / 2) return i;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N; scanf("%d", &N);
    while (N > 0){
        print(square(N)); N -= square(N);
    }
    
    return 0;
}


Measured memory_bytes: 256
object Main {
  def main(args: Array[String]): Unit = {
    val s = new Main()
    s.solve()
    s.out.flush()
  }
}

class Main {
  import java.io._
  import java.util.StringTokenizer

  import scala.collection.mutable
  import scala.util.Sorting
  import math.{abs, max, min}
  import mutable.{ArrayBuffer, ListBuffer}
  import scala.reflect.ClassTag

  val MOD = 1000000007
  val out = new PrintWriter(System.out)

  def solve(): Unit = {
    val N, K = ni()
    val H = na(N)
    Sorting.quickSort(H)
    var r = 0
    var ans = Integer.MAX_VALUE
    REP(N) { l =>
      while(r < N && r - l + 1 < K) r += 1
      if (r < N) ans = min(ans, H(r) - H(l))
    }
    out.println(ans)
  }

  class InputReader(val stream: InputStream) {
    private val reader = new BufferedReader(new InputStreamReader(stream), 32768)
    private var tokenizer: StringTokenizer = _

    def next(): String = {
      while (tokenizer == null || !tokenizer.hasMoreTokens)
        tokenizer = new StringTokenizer(reader.readLine)
      tokenizer.nextToken
    }

    def nextInt(): Int = next().toInt
    def nextLong(): Long = next().toLong
    def nextChar(): Char = next().charAt(0)
  }
  val sc = new InputReader(System.in)
  def ni(): Int = sc.nextInt()
  def nl(): Long = sc.nextLong()
  def nc(): Char = sc.nextChar()
  def ns(): String = sc.next()
  def ns(n: Int): Array[Char] = ns().toCharArray
  def na(n: Int, offset: Int = 0): Array[Int] = map(n)(_ => ni() + offset)
  def na2(n: Int, offset: Int = 0): (Array[Int], Array[Int]) = {
    val A1, A2 = Array.ofDim[Int](n)
    REP(n) { i =>
      A1(i) = ni() + offset
      A2(i) = ni() + offset
    }
    (A1, A2)
  }
  def nm(n: Int, m: Int): Array[Array[Int]] = {
    val A = Array.ofDim[Int](n, m)
    REP(n) { i =>
      REP(m) { j =>
        A(i)(j) = ni()
      }
    }
    A
  }
  def nal(n: Int): Array[Long] = map(n)(_ => nl())
  def nm_c(n: Int, m: Int): Array[Array[Char]] = map(n) (_ => ns(m))
  def REP(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
    var i = offset
    val N = n + offset
    while(i < N) { f(i); i += 1 }
  }
  def REP_r(n: Int, offset: Int = 0)(f: Int => Unit): Unit = {
    var i = n - 1 + offset
    while(i >= offset) { f(i); i -= 1 }
  }

  def map[@specialized A: ClassTag](n: Int, offset: Int = 0)(f: Int => A): Array[A] = {
    val res = Array.ofDim[A](n)
    REP(n)(i => res(i) = f(i + offset))
    res
  }


  def sumL(as: Array[Int]): Long = {
    var s = 0L
    REP(as.length)(i => s += as(i))
    s
  }

  def cumSum(as: Array[Int]) = {
    val cum = Array.ofDim[Int](as.length + 1)
    REP(as.length) { i =>
      cum(i + 1) = cum(i) + as(i)
    }
    cum
  }
}

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using ll = long long;
int mod = 1000000000+7;

int main(){

	int n,m;
	cin>>n>>m;
	vector<vector<int>> g(n);
	int a,b;
	rep(i,m){
		cin>>a>>b;
		g[a-1].push_back(b-1);
		g[b-1].push_back(a-1);
	}

	int ans[n]={};
	int dist[n];
	rep(i,n)dist[i]=mod;
	dist[0]=0;
	queue<int> q;
	q.push(0);
	while(!q.empty()){
		int s=q.front();
		q.pop();
		for(int i=0;i<g[s].size();i++){
			if(dist[g[s][i]]!=mod)continue;
			dist[g[s][i]]=dist[s]+1;
			ans[g[s][i]] = s;
			q.push(g[s][i]);
		}
	}

	cout<<"Yes"<<endl;
	for(int i=1;i<n;i++)cout<<ans[i]+1<<endl;

	return 0;
}


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

#define ll long long int
#define pii pair<int,int>
const int sz=5e5+100;

int tree[sz*4];
int mark[sz];
int rig[sz];

bool cmp(pair<pii,int> A,pair<pii,int> B)
{
    return A.first.first<B.first.first;
}

void update(int l,int r,int id,int val,int pos)
{
    //cout<<l<<" "<<r<<" "<<id<<endl;
    if(l==r && id==l){
        tree[pos]+=val;
        return ;
    }
    int mid=(l+r)/2;
    int lc=pos*2+1;
    int rc=lc+1;
    if(id<=mid) update(l,mid,id,val,lc);
    else update(mid+1,r,id,val,rc);
    tree[pos]=tree[lc]+tree[rc];
}

int query(int l,int r,int p,int q,int pos)
{
    if(r<p || q<l) return 0;
    else if(p<=l && r<=q) return tree[pos];
    int mid=(l+r)/2;
    int lc=pos*2+1;
    int rc=lc+1;

    return (query(l,mid,p,q,lc)+query(mid+1,r,p,q,rc));
}

int main()
{
     int n,m,p,q,l,r,x,y,i;
     cin>>n>>m;
     int ara[n+1];
     memset(mark,-1,sizeof mark);
     for(i=1;i<=n;i++) cin>>ara[i];

     for(i=n;i>=1;i--){
         rig[i]=mark[ara[i]];
         mark[ara[i]]=i;
     }

     pair<pii,int> Q[m];
     for(i=0;i<m;i++) {
            cin>>Q[i].first.first>>Q[i].first.second;
            Q[i].second=i;
     }

     int ans[m];

     sort(Q,Q+m,cmp);

     int last=1;

     memset(mark,-1,sizeof mark);
     for(i=1;i<=n;i++){
        if(mark[ara[i]]==-1) update(1,n,i,1,0);
        mark[ara[i]]=1;
     }

     for(i=0;i<m;i++){
         while(last<Q[i].first.first){
            if(rig[last] != -1) update(1,n,rig[last],1,0);
            ++last;
         }

         ans[Q[i].second]=query(1,n,Q[i].first.first, Q[i].first.second,0);
     }

     for(i=0;i<m;i++) cout<<ans[i]<<'\n';

}


Measured memory_bytes: 21512
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod (ll)1000000007
#define fast std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define input int t;cin>>t;while(t--)
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define f(i, a, b) for (int i = (a); i < (b); i++)
#define fr(i, a, b) for (int i = (a); i >= (b); i--)
#define mp make_pair
#define pb push_back
#define fs first
#define sc second
#define all(x) x.begin(), x.end()
#define cins(s) string s; cin>>s;
#define cini(i) int i; cin>>i;
#define cinll(l) ll l; cin>>l;
#define cind(d) double d; cin>>d;
#define PI 3.1415926535897932384626433
int i,j,k;
int main()
{
	int n;
	cin>>n;
	n=n%10;
	if(n==2 or n==4 or n== 5  or n== 7 or n== 9)
		cout<<"hon";
	else if(n==0  or n==1 or n==  6  or n==8)
		cout<<"pon";
	else
		cout<<"bon";
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
#define MAXN 100005
#define INF 1000000000
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
char str[MAXN];
int n,k,res;
vector<int> consec;
int main()
{
    scanf("%s",str+1);
    scanf("%d",&k);
    n=strlen(str+1);
    bool f=true;
    for(int i=2;i<=n;i++)
    {
        if(str[i]!=str[i-1])
        {
            f=false;
            break;
        }
    }
    if(f)
    {
        printf("%lld\n",1LL*n*k/2);
        return 0;
    }
    int cnt=1;
    res=0;
    for(int i=2;i<=n;i++)
    {
        if(str[i]==str[i-1]) cnt++;
        else
        {
            consec.push_back(cnt);
            res+=cnt/2;
            cnt=1;
        }
    }
    consec.push_back(cnt);
    res+=cnt/2;
    if(str[1]!=str[n]) printf("%lld\n",1LL*res*k);
    else
    {
        ll ans=1LL*res*k;
        ans-=1LL*(k-1)*(consec[0]/2+consec.back()/2);
        ans+=1LL*(k-1)*((consec[0]+consec.back())/2);
        printf("%lld\n",ans);
    }
    return 0;
}


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

int main() {
  int a, b, k;
  cin>>a>>b>>k;
  set<int> s;
  for (int i=a; i<=min(a+k-1, b); i++) {
    s.insert(i);
  }
  for (int i=max(b-k+1, a); i<=b; i++) {
    s.insert(i);
  }
  for (int i: s) {
    cout<<i<<endl;
  }
}

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

// 入力
int N, P, Q;
int A[1 << 18], B[1 << 18];
int C[1 << 18], D[1 << 18];
vector<int> X[1 << 18];
vector<int> Y[1 << 18];

// LCA
int par[1 << 18][22];

// その他
int dist1[1 << 18];
int dist2[1 << 18];
bool rakuen[1 << 18];
bool used[1 << 18];

void dfs1(int pos, int dep) {
	dist1[pos] = dep;
	for (int i : X[pos]) {
		if (dist1[i] != -1) continue;
		dfs1(i, dep + 1);
	}
}

void dfs2(int pos, int dep) {
	dist2[pos] = dep;
	for (int i : Y[pos]) {
		if (dist2[i] != -1) continue;
		dfs2(i, dep + 1);
		par[i][0] = pos;
	}
}

void dfs3(int pos, int pre) {
	used[pos] = true;
	for (int i : X[pos]) {
		if (i == pre) continue;
		if (dist1[i] >= dist2[i]) continue;
		dfs3(i, pos);
	}
}

int prevs(int u, int x) {
	for (int i = 21; i >= 0; i--) {
		if (x >= (1 << i)) { x -= (1 << i); u = par[u][i]; }
	}
	return u;
}

int lca(int u, int v) {
	if (dist2[u] > dist2[v]) swap(u, v);
	v = prevs(v, dist2[v] - dist2[u]);
	if (u == v) return u;

	for (int i = 21; i >= 0; i--) {
		if (par[u][i] != par[v][i]) { u = par[u][i]; v = par[v][i]; }
	}
	return par[u][0];
}

int getdst(int u, int v) {
	int w = lca(u, v);
	return dist2[u] + dist2[v] - 2 * dist2[w];
}

int main() {
	cin >> N >> P >> Q;
	for (int i = 1; i <= N - 1; i++) {
		cin >> A[i] >> B[i];
		X[A[i]].push_back(B[i]);
		X[B[i]].push_back(A[i]);
	}
	for (int i = 1; i <= N - 1; i++) {
		cin >> C[i] >> D[i];
		Y[C[i]].push_back(D[i]);
		Y[D[i]].push_back(C[i]);
	}
	for (int i = 1; i <= N; i++) dist1[i] = -1;
	for (int i = 1; i <= N; i++) dist2[i] = -1;
	dfs1(P, 0);
	dfs2(Q, 0);
	dfs3(P, -1);

	for (int i = 1; i <= 21; i++) {
		for (int j = 1; j <= N; j++) par[j][i] = par[par[j][i - 1]][i - 1];
	}
	for (int i = 1; i <= N - 1; i++) {
		if (getdst(A[i], B[i]) <= 2) continue;
		rakuen[A[i]] = true;
		rakuen[B[i]] = true;
	}

	int Answer = 0;
	for (int i = 1; i <= N; i++) {
		if (used[i] == true && rakuen[i] == true) {
			cout << "-1" << endl;
			return 0;
		}
		if (used[i] == true) Answer = max(Answer, dist2[i] * 2);
	}
	cout << Answer << endl;
	return 0;
}

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

int main(int argc, char *argv[])
{
  for(;;) {
    int w, h;
    cin >> h >> w;
    if(h == 0 && w == 0) break;
    auto compare = [](int w, int h, int x, int y) {
      int dwh = w*w + h*h;
      int dxy = x*x + y*y;
      if(dwh == dxy) return h - y; // the same diag -> height
      return dwh - dxy;
    };
    int xx = 150, yy = 150; // tentative answer
    for(int y = 1; y <= 150; y++) {
      for(int x = y + 1; x <= 150; x++) {
        if(compare(w, h, x, y) < 0) { // x-y is bigger than w-h
          if(compare(xx, yy, x, y) > 0) { // x-y is smaller than xx-yy
            xx = x; // update the tentative answer
            yy = y;
          }
        }
      }
    }
    cout << yy << " " << xx << endl;
  }
  return 0;
}



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

#define DEBUG(x) cout<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl

typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
const int inf = 1000000001;
const ll INF = 1e18 * 4;
#define MOD 1000000007
#define mod 1000000009
#define pi 3.14159265358979323846
#define Sp(p) cout<<setprecision(15)<<fixed<<p<<endl;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };

int main() {
	int a, b;
	cin >> a >> b;
	cout << 2 * b - a << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma comment(linker, "/stack:200000000")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
 
#define X first
#define Y second
 
//#include <boost/unordered_map.hpp>
//using namespace boost;
 
/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
rbtree T;
*/
 
using i32 = int;
using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;
//using i128 = __int128_t;
//using u128 = __uint128_t;
using i128 = i64;
using u128 = u64;
 
ll power(ll a, ll b, ll p)
{
    if (!b) return 1;
    ll t = power(a, b/2, p);
    t = t*t%p;
    if (b&1) t = t*a%p;
    return t;
}
 
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll px, py;
    ll d = exgcd(b, a%b, px, py);
    x = py;
    y = px-a/b*py;
    return d;
}
 
template<class T>
inline void freshmin(T &a, const T &b)
{
    if (a > b) a = b;
}
 
template<class T>
inline void freshmax(T &a, const T &b)
{
    if (a < b) a = b;
}
 
//#define getchar getchar_unlocked
//#define putchar putchar_unlocked
 
int inp() {
    int x = 0, f = 0; char ch;
    for(ch = getchar(); !isdigit(ch); ch = getchar())
        if(ch == '-') f = 1;
    for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
    return f ? -x : x;
}
 
ll inp_ll() {
    ll x = 0; int f = 0; char ch;
    for(ch = getchar(); !isdigit(ch); ch = getchar())
        if(ch == '-') f = 1;
    for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
    return f ? -x : x;
}
 
template<class T>
bool read(T &x)
{
    x = 0;
    char ch = getchar();
    if (ch == EOF) return 0;
    for(; !isdigit(ch); )
    {
        ch = getchar();
        if (ch == EOF) return 0;
    }
    for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
    return 1;
}
 
template<class T>
void write(T x)
{
    static char s[22];
    static char *it = s+20;
    static char *end = s+20;
    if (!x)
        *-- it = '0';
    while (x)
    {
        *-- it = x%10+'0';
        x /= 10;
    }
    for (; it < end; ++ it)
        putchar(*it);
}
 
template<class T>
void writeln(T x)
{
    write(x);
    putchar('\n');
}
 
const int MAXN = 200010;
const int INF = 1000000000;
const int MOD = 1000000007;

int main()
{
	
	int a, b, c;
	cin >> a >> b >> c;
	cout << max(c-(a-b), 0) << endl;
	
	return 0;
}


Measured memory_bytes: 256
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x<0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
n,m=map(int,input().split())
uf=UnionFind(n)
for i in range(m):
  x,y,z=map(int,input().split())
  uf.unite(x-1,y-1)
print(uf.group_count())

Measured memory_bytes: 7856
#!/usr/bin/env python
# -*- coding: utf-8 -*-

while True:
    x,y,s = map(int,input().split())
    if (x,y,s) == (0,0,0):
        break
    ans = 0
    for i in range(1,s//2 + 1):
        for j in range(1,s-i + 1):
            if i*(100+x)//100 + j*(100+x)//100== s:
                ans = max(ans,i*(100+y)//100 + j*(100+y)//100)
    print(ans)

Measured memory_bytes: 6724
#include<iostream>
#include<string>
#include<cmath>

using namespace std;

int main(){

	int N ;
	cin >> N;
	for(int i=0; i<3;i++){
		if(N % 10 == 7){
			cout << "Yes" << endl;
			return 0;
		}else
			N /= 10;

	}
	cout << "No" << endl;

	return 0;
}


Measured memory_bytes: 3636