akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define rp(i,n) for(int i=0;i<n;i++)
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define lrp(i,n) for(long long i=0;i<n;i++)
#define lrep(i,m,n) for(long long i=m;i<=n;i++)
#define ll long long
#define sort(a) sort(a.begin(),a.end())
#define reverse(a) reverse(a.begin(),a.end())
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define abs(a,b) (a-b>0?a-b:b-a)

int main(){
    int w,a,b;
    cin >> w >> a >> b;
    if(a-w<=b&&b<=a+w){
        cout << 0 << endl;
    }else if(b<a-w){
        cout << a-b-w << endl;
    }else if(a+w<b){
        cout << b-a-w << endl;
    }
}


Measured memory_bytes: 256
/** BiSmIlLaHiR rAhMaNiR rAhIm **\
 
*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*
*$*                                             *$*
*$*    ||||||||  ||||||||  ||||||||  ||||||||   *$*
*$*    ||    ||  ||           ||     ||         *$*
*$*    ||||||||  ||||||||     ||     ||||||     *$*
*$*    ||    ||        ||     ||     ||         *$*
*$*    ||    ||  ||||||||  ||||||||  ||         *$*
*$*                                             *$*
*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*$*
 
            \**  DIIT(17th batch) **/
 
#include<bits/stdc++.h>
#define ll long long int
#define ul unsigned long long int
#define pf printf
#define sf scanf
#define endl "\n"
#define pb push_back
#define eb emplace_back
#define makep make_pair
#define MOD 1000000007
#define PI 2*acos(0.0)
#define PII pair<ll, ll>
#define pii pair<int, int>
#define what_is(x) cerr<<#x<<" is "<<x<<endl;
#define fio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;

ll count1=0;

void Merge(ll *A,ll *L,ll leftCount,ll *R,ll rightCount) {
    ll i,j,k;
    i = 0; j = 0; k =0;

    while(i<leftCount && j< rightCount) {
        if(L[i]  < R[j]){
            A[k++] = L[i++];
            count1++;
        }
        else{
            A[k++] = R[j++];
            count1++;
        }
    }
    while(i < leftCount){
        A[k++] = L[i++];
        count1++;
    }
    while(j < rightCount){
        A[k++] = R[j++];
        count1++;
    }
}
void asif(ll *A,ll n) {
    ll mid,i;
    if(n < 2) return;

    mid = n/2;
    ll L[mid];
    ll R[n-mid];

    for(i = 0;i<mid;i++) L[i] = A[i];
    for(i = mid;i<n;i++) R[i-mid] = A[i];

    asif(L,mid);
    asif(R,n-mid);
    Merge(A,L,mid,R,n-mid);
}

int main()
{
    fio();
    ll i,n;
    cin>>n;
    ll a[n];
    for(i=0;i<n;i++)
        cin>>a[i];
    asif(a,n);
    //sort(a,a+n);
    for(i=0;i<n-1;i++)
        cout<<a[i]<<" ";
    cout<<a[n-1]<<endl<<count1<<endl;
}


Measured memory_bytes: 14876
#include<bits/stdc++.h>
#define n 500000
#define mem(arr) memset(arr, 0, sizeof(arr))
using namespace std;
typedef long long lli;
typedef double llf;
typedef pair<int, int> P;
void solve();
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int times = 1;
//	cin >> times;
	for(int i=0; i<times; i++)
	{
		solve();
		cout << '\n';
	}
	return 0;
}

int a, b, c, d, e, f, g, h;
int arr[n + 50], arr1[n + 50], arr2[n + 50];

//type here

void solve()
{
	string str; cin >> str;
	bool yes = true;
	for(int i=0; i<str.size(); i++)
	{
		if(i % 2 && str[i] == 'R') yes = false;
		if(i % 2 == 0 && str[i] == 'L') yes = false;
	}
	if(yes) cout << "Yes";
	else	cout << "No";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pint;

char tb[2][3];
int main(){
    cin>>tb[0]>>tb[1];
    rep(i,1)rep(j,3){
        if(tb[i][j]!=tb[1-i][2-j]){
            cout<<"NO"<<endl;return 0;
        }
    }
    cout<<"YES"<<endl;
    return 0;
}

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

int main() {
  
  int64_t N, D; cin >> N >> D;
  
  int ans = 0; D *= D;
  
  for (int i = 0; i < N; i++) {
    
    int64_t X, Y; cin >> X >> Y;
    
    int64_t tmp = int64_t(pow(X, 2)) + int64_t(pow(Y, 2));
    
    if (tmp <= D) ans++;
    
  }
  
  cout << ans << endl;
  
}

Measured memory_bytes: 3612
N, M = list(map(int, input().split()))
A = sorted(list(map(int, input().split())), reverse=True)+[-1]
B = sorted(list(map(int, input().split())), reverse=True)+[-1]
nA = nB = 0
ans = 1
mod = 10**9+7
for x in range(N*M, 0, -1):
    r = 1
    if x==A[nA] and x==B[nB]:
        nA += 1
        nB += 1
    elif x==A[nA] and x!=B[nB]:
        nA += 1
        r = nB
    elif x!=A[nA] and x==B[nB]:
        nB += 1
        r = nA
    else:
        r = nA*nB - (N*M-x)
        
    ans = ans*r % mod

print(ans)

Measured memory_bytes: 3316
#include "bits/stdc++.h"
#define PRECISION(x) cout << fixed << setprecision(x)
#define FAST_IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define ALLR(X) (X).rbegin(), (X).rend()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define F first
#define S second

using namespace std;
 
template<class T> bool max_self(T & a, const T & b){ 
  return b > a ? a = b, true : false; 
}
template<class T> bool min_self(T & a, const T & b){ 
  return b < a ? a = b, true : false;    
}
typedef long long LL;
const int INF = 1e9 + 7;
const double PI = acos(-1.0);
const double EPS = (1e-9);

int main(){
  FAST_IO
  LL N, M;
  cin >> M;
  N = M;
  int total = 0;
  
  for(LL div = 2; div * div <= M; ++div){
    if(N % div) continue;
    int cnt = 0;
    while(N % div == 0){
      N /= div;
      cnt++;
    }

    int howMany = 0;
    for(int cur = 1; ; ++cur){
      if(cnt < cur) break;
      cnt -= cur;
      howMany++;
    }

    total += howMany;
  }

  if(N > 1) total += 1;


  cout << total << "\n";
  return 0;
}


Measured memory_bytes: 3604
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int N;
    int X;
    cin>>N>>X;
    
    int kaisu=0;
    kaisu++;
    vector<int> J(N+10,X*2);
    J.at(0)=0;
    
    int L;
    for(int i=1;i<N+1;i++){
        cin>>L;
        J.at(i)=J.at(i-1)+L;
        if(J.at(i)<=X)kaisu++;
    }
    printf("%d",kaisu);
}


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

#define ll              long long int
#define ull             unsigned long long int
#define pii             pair < int, int>
#define pll             pair < ll, ll>
#define sc              scanf
#define scin(x)         sc("%d",&(x))
#define scln(x)         sc("%lld",&(x))
#define pf              printf
#define NL              pf("\n")
#define ms(a,b)         memset(a,b,sizeof(a))
#define pb(a)           push_back(a)
#define mp              make_pair
#define db              double
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define vi              vector< int >
#define vl              vector< ll >
#define vii             vector<vector< int > >
#define vll             vector<vector< ll > >
#define DBG             pf("HI\n")
#define MOD             1000000007
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define RUN_CASE(t,T)   for(__typeof(t) t=1;t<=T;t++)
#define CASE(t)         printf("Case %d: ",t)
#define CASEL(t)        printf("Case %d:\n",t)
#define intlimit        2147483648
#define longlimit       9223372036854775808
#define infinity        (1<<28)
#define gcd(a, b)       __gcd(a,b)
#define lcm(a, b)       ((a)*(b)/gcd(a,b))
#define mx              1234567899
#define PI              2*acos(0.0)
#define rep(i,a,b)      for(ll i=a; i<=b; i++)
#define rev(i,a,b)      for(ll i=a; i>=b; i--)
#define file             #define file            freopen("E:\\file.txt", "r", stdin);ios_base::sync_with_stdio(false); cin.tie(NULL);

using namespace std;

///--------------Graph Moves--------------------------------------
///const int fx[] = {+1,-1,+0,+0};
///const int fy[] = {+0,+0,+1,-1};
///const int fx[] = {+0,+0,+1,-1,-1,+1,-1,+1}; ///King's move
///const int fy[] = {-1,+1,+0,+0,+1,+1,-1,-1}; ///king's Move
///const int fx[] = {-2,-2,-1,-1,+1,+1,+2,+2}; ///knight's move
///const int fy[] = {-1,+1,-2,+2,-2,+2,-1,+1}; ///knight's move
///---------------------------------------------------------------

long long BigMod(long long int a, long long int b, int M) { /// a function to determine a^b(mod M)
    long long remainder, answer = 1;                            /// set two variables for remainder and answer
    remainder = a%M;                                         /// setting remainder as
    while(b!=0)                                                     ///  loop occurs until b is not equal to 0
    {
        if(b%2==1) answer = (answer*remainder)%M;                  /// checking if b is odd
                /// taking the present remainder in the answer if b is odd
        remainder = (remainder*remainder)%M;    /// making remainder double on each turn of the loop
        b/=2;                                  /// reducing b by dividing it by 2 in every turn,
    }
    return answer;
}
bool cmp(int a,int b)
{
    return a>b;
}
int main()
{
    int n, a,b;
    cin >>n>>a >> b;
    cout << min(a,b) << " " << max(0,a+b-n)<<endl;
    return 0;
}


Measured memory_bytes: 256
y = raw_input()
n, x = y.split()
n = int(n)
x = int(x)
co = 0

while n != 0 or x != 0:
    for i in range(1, n-1):
        for j in range(2, n):
            for k in range(3, n+1):
                sum = i + j + k
                if sum == x and i < j and j < k:
                    co += 1
                    break

    print co
    
    y = raw_input()
    n, x = y.split()
    n = int(n)
    x = int(x)
    co = 0

Measured memory_bytes: 6388
/**
 *    author:  tourist
 *    created: 13.06.2020 15:36:00       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long a, v, b, w, t;
  cin >> a >> v >> b >> w >> t;
  long long d = abs(a - b);
  if (v > w && d <= (v - w) * t) {
    cout << "YES" << '\n';
  } else {
    cout << "NO" << '\n';
  }
  return 0;
}


Measured memory_bytes: 3652
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string> //文字列
#include <iomanip> //doubleの桁数指定 setprecision()
#include <list> //前後に数値を入れれる配列
#include <map> //map
#include <vector> //vecror



#define REP(i,m,n) for(ll i = (ll) (m);i < (ll) (n);i++) //forの短縮
#define rep(i,n) REP(i,0,n) //REPが0の時
#define ll long long int

using namespace std;

double PI = acos(-1); //円周率

//常設関数↓

//最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

//最小公倍数
ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}

//degree → radian
long double chg_DegRad(long double deg) {
	return deg * PI / 180.0;
}

//radian → degree
long double chg_RadDeg(long double rad) {
	return rad * 180.0 / PI;
}
 
//桁数
ll CountDigit(ll n) {
	ll digit = 1;
	while ((n /= 10) != 0) digit++;
	return digit;
}

//距離
double dis(double xa, double ya, double xb, double yb) {
	return pow(pow(xa - xb, 2.0) + pow(ya - yb, 2.0), 0.5);
}

//abs()平均
//pow(,)累乗


//提出コード↓


string s;
bool J = true;



int main() {
	cin >> s;
	ll  n = s.size();
	
	rep(i, n) {
		if(s[i] == s[n - i - 1]) {}
		else {
			J = false;
			break;
		}
	}
	ll N = (n - 1) / 2;
	rep(i, N) {
		if(s[i] == s[N - i - 1]){}
		else {
			J = false;
			break;
		}
	}
	ll S = (n + 3) / 2;
	ll c = 0;
	REP(i, S, n) {
		if(s[i - 1] == s[n - c - 1]){}
		else {
			J = false;
				break;
		}
		c++;
	}
	if (J) cout << "Yes" << endl;
	else cout << "No" << endl;


	return 0;
}



Measured memory_bytes: 256
import java.io.*;

class Main {
    public static void main (String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nums;
        int h, w, i, j;
        while (true) {
            nums = br.readLine().split(" ");
            h = Integer.parseInt(nums[0]);
            w = Integer.parseInt(nums[1]);
            if (h == 0 && w == 0) break;
            for (i = 0; i < h; i++) {
                for (j = 0; j < w; j++) {
                    if (i % 2 == j % 2) System.out.print("#");
                    else System.out.print(".");
                }
                System.out.println();
            }
            System.out.println();
        }
    }
}

Measured memory_bytes: 32740
//codeforces
//
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define F first
#define S second
//#define inf 1e9+7
#define int64 long long
#define VI vector < int >
#define all(v) v.begin(),v.end()
#define inpv(v) for(auto &x:v) cin>>x
#define pii pair < int , int >
#define CASES int tt;cin>>tt; while(tt--)
#define for0(i,n) for(int i=0; i<n; i++)
const int64 inf = 1e9+7;
const char nwl = '\n';

int main()
{
  //ur code
  int64 n,a,b;
  cin>>a>>b>>n;
  int64 s=1;
  /*for(int64 i=1; i<=n; i++){
    int64 tmp = floor((a*i)/b) - a*floor(i/b);
    if(tmp>s)
      s=tmp;
  }*/
  int64 tmp=b-1;
  if(tmp>n)
    tmp=n;
  s = floor((a*(tmp))/b) - a*floor((tmp)/b);
  cout<<s;
	
	return 0;
}


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

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

using namespace std;

int main() {
    string s;
    int i,j,flag=0;
    cin>>s;
    rep(i,s.size()){
    	rep(j,s.size()){
    		if(s[i]==s[j] && i!=j){
    			flag=1;
    		}
    	}
    }
    if(flag==0){
    	cout<<"yes"<<endl;
    }
    else{
    		cout<<"no"<<endl;
    }
	// your code goes here
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
    Main(){
	Scanner sc = new Scanner(System.in);

	while(sc.hasNext()){
	    String s1 = sc.next();
	    char[] ch1 = s1.toCharArray();
	    int n = sc.nextInt();
	    int c = 0;
	    for(int i = 0; i < n; i++){
		String s2 = sc.next();
		char[] ch2 = s2.toCharArray();
		for(int j = 0; j < s2.length(); j++){
		    if(ch1[0] == ch2[j]){
			boolean f = true;
			int t = j;
			for(int k = 1; k < s1.length(); k++){
			    if(k+t == s2.length()){
				t = -k;
			    }
			    if(ch1[k] != ch2[t+k]){
				f = false;
				break;
			    }
			}
			if(f){
			    c++;
			    break;
			}
		    }
		}
	    }

	    System.out.println(Integer.toString(c));
	}
    }

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

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

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

    set<int> values;
    for (int i = 0; i < N; ++i) {
        values.insert(d[i]);    
    }

    cout << values.size() << endl;
}

Measured memory_bytes: 256
//#include<cstdio>
//#include<cassert>
//#include<iostream>
//#include<cstring>
//#include<algorithm>
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define MAX ((int)1e9 + 5)
#define MAXL ((ll)3e18 + 7)
#define MAX_X ((ll)1e5 + 2)
#define pi (2.0*acos(0))
#define M ((int)1e6 + 7)
#define MOD ((int)1e9 + 7)
#define NN ((int)3e6 + 7)
#define N ((int)1e5 + 5)
#define eps (0)
#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
#define logn 29
#define endl "\n"
#define mp make_pair
#define BUCK 105
#define RIG ((idx<<1)|1)
#define LEF (idx<<1)
//#define int ll


using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;

/*fast io
ios_base::sync_with_stdio(false);
cin.tie(NULL);
*/




typedef tree < int,  null_type,  less < int >,  rb_tree_tag,  tree_order_statistics_node_update > o_set;
/// o_set s;
/// s.order_of_key(k) : Number of items strictly smaller than k .
/// *(s.find_by_order(k)) : K-th element in a set (counting from zero).


int arr[N];


int main()
{
    fastio;
    int n ;
    cin>>n;
    unordered_map < int , bool > pos;
    for(int i = 1 ; i<=n ; i++){
        cin>>arr[i];
        pos[arr[i]] = i&1;
    }
    sort(arr+1,arr+n+1);
    int ans = 0;
    for(int i = 1 ; i<=n ; i++){
        bool flag = pos[arr[i]];
        if(flag != (i&1)) ans++;
    }
    cout<<ans/2<<endl;
    return 0;
}


Measured memory_bytes: 4900
#include<iostream>
#include<fstream>
#include<vector>
#include<initializer_list>
#include<string>
using namespace std;
  int main(){
 int a;
 cin >> a;
int b;
cin >> b;
int c;
cin >> c;

if (a+b == c || c+b == a || c+a == b)
cout << "Yes" << endl;
else cout << "No" << endl;





}

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

int main(){
	int H,W;
	while(cin >> H >> W,H||W){
	for(int i=0;i<W;i++) cout << "#";
	cout << endl;
	H-=2;
	while(H--){
	cout << "#";
	for(int j=1;j<W-1;j++) cout <<".";
	cout << "#"<<endl;
	}
	for(int i=0;i<W;i++) cout << "#";
	cout << endl;
	cout << endl;
	}

	return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define pb push_back
using ll = long long;
using vin=vector<int>;
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() {
  int n;
  cin>>n;
  vin a(n);
  rep(i,0,n)cin>>a[i];
  //////
  ll mny=1000;
  ll kabu=0;
  rep(i,0,n-1){
    mny+=kabu*a[i];
    kabu=0;
    
    
    if(a[i]<a[i+1]){
      kabu+=mny/a[i];
      mny-=a[i]*kabu;
    }
    else{
      continue;
    }
  }
  mny+=kabu*a[n-1];
  cout<<mny<<endl;
}

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

using namespace std;

int main() {
    int n , l;

    cin >> n >> l;

    string strings[n]; 
    for (int i; i < n; i++) {
        cin >> strings[i];
    }

    sort(strings, strings+n);

    for(int i = 0; i < n; i++) {
        cout << strings[i];
    }
    cout << "\n";
    return 0;
}

Measured memory_bytes: 256
n,q=map(int,input().split())
s=input()
idx=[0 for i in range(n+1)]

for i in range(n-1):
    if s[i:i+2]=="AC":idx[i+1]=idx[i]+1
    else:idx[i+1]=idx[i]

ans=[]
for i in range(q):
    l,r=map(int,input().split())
    print(idx[r-1]-idx[l-1])

Measured memory_bytes: 6080
#include <bits/stdc++.h>
#define rep(i,n) for(long long int i = 0; i < n; i++)
#define print(n) std::cout << n << std::endl
using namespace std;
const int N = 1000000;

int fun(int n){
    if (n % 2 == 0) return n / 2;
    else return 3 * n + 1;
}

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

    vector<int> a;
    a.push_back(s);

    for (int i = 1; i < N; ++i) {
        s = fun(s);
        auto itr = find(a.begin(), a.end(), s);
        if(itr != a.end()){
            print(i+1);
            break;
        }
        a.push_back(s);
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <utility>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cstdio>

using namespace std;

constexpr long long mod = 1000000007;
constexpr double eps = 0.0000000001;

int main() {
    int n,m;
    priority_queue<int> a;
    cin >> n >> m;
    for(int i = 0;i < n;i++) {
        int s;
        cin >> s;
        a.push(s);
    }
    for(int i = 0;i < m;i++) {
        int s = a.top();
        a.pop();
        a.push(s/2);
    }
    long long r = 0;
    while(!a.empty()) {
        r += a.top();
        a.pop();
    }
    cout << r << endl;
}

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

using ll = long long;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void dump(vector<T> v) { for (auto& x : v) cerr << x << " "; cerr << endl; }
template<class T> inline void dump(vector<pair<T, T>> v) { for (auto& p : v) cerr << p.first << " " << p.second << endl; }
template<class T> inline void dump(vector<vector<T>> vv) { for (auto& v : vv) {for (auto& x : v) cerr << x << " "; cerr << endl;} }

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

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

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

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

  vector<vector<int>> d(h, vector<int>(w, INF));
  vector<pair<int, int>> blacks;
  rep(i, h) rep(j, w) {
    if (a[i][j] == '#') {
      blacks.emplace_back(i, j);
      d[i][j] = 0;
    }
  }

  int ans = 0;
  while (!blacks.empty()) {
    vector<pair<int, int>> new_blacks;
    for (auto& b : blacks) {
      int sh = b.first;
      int sw = b.second;
      rep(i, 4) {
        int nh = sh + dx[i];
        int nw = sw + dy[i];
        if (nh < 0 || nw < 0 || h <= nh || w <= nw) continue;
        if (a[nh][nw] == '#') continue;
        a[nh][nw] = '#';
        new_blacks.emplace_back(nh, nw);
      }
    }
    if (new_blacks.empty()) break;
    ans++;
    blacks = new_blacks;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 18604
from sys import *

n = int(stdin.readline())
arr = list(map(int, stdin.readline().split()))
last = arr[n - 1]
for i in range(n - 1, -1, -1):
	if arr[i] > last:
		d = arr[i] - last
		if d > 1:
			print("No")
			exit(0)
	last = min(last, arr[i])
print("Yes")

Measured memory_bytes: 41836
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)
int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if ( a == b && b == c && c == a ) cout << "Yes" << endl;
    else                              cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(c) (c).begin(), (c).end()
#define pb push_back
#define eb emplace_back
using namespace std;
const long long INF = 1LL<<60; // 仮想的な無限大の値;
using ll = long long;
using P  = pair<int, int>;
#define vi vector<int>
#define vll vector<ll>
#define vs vector<string>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main()
{
    ll N, K;
    cin >> N >> K;
    if(N < K && N < K-N) {
        cout << N << endl;return 0;
    }
    if(N%K == 0)
    {
        cout << 0 << endl;return 0;
    }

    ll x = N%K;
    ll ans = INF;
    int cnt = 0;
    while(1)
    {
        x = abs(x-K);
        if(!chmin(ans, x)) ++cnt;
        if(cnt > 100) break;
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
    string s;
    cin >> s;
    if(s == "Sunny") cout << "Cloudy"  << endl;
    if(s == "Cloudy") cout << "Rainy"  << endl;
    if(s == "Rainy") cout << "Sunny"  << endl;
    return 0;
}

Measured memory_bytes: 256
N, M = map(int,input().split())
coef = [-1]*N
for i in range(M):
    si, ci = map(int, input().split())
    if si==1 and N>1 and ci==0:
        print(-1)
        exit()
    elif coef[si-1]==ci or coef[si-1]<0:
        coef[si-1] = ci
    else:
        print(-1)
        exit()

if coef[0]<0:
    coef[0]=1 if N > 1 else 0

print("".join([str(x) if x>=0 else "0" for x in coef]))

Measured memory_bytes: 3064
#include <iomanip>
#include <iostream>
#include <map>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

map<int64_t, int> prime_factor(int64_t n) {
  map<int64_t, int> ret;
  for (int64_t i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if (n != 1) ret[n] = 1;
  return ret;
}

int main(void) {
  ios::sync_with_stdio(false);
  int64_t N;
  cin >> N;
  int64_t answer = 0;
  for (auto& mp : prime_factor(N)) {
    int num = mp.second;
    int use = 1;
    while (num > 0) {
      num -= use;
      if (num >= 0) {
        ++answer;
      }
      ++use;
    }
  }
  cout << answer << endl;
  return 0;
}


Measured memory_bytes: 3656
class Rectangle:
    def __init__(self, height, position):
        self.height = height
        self.position = position

def getLargestRectangleRow(size, bufTmp):
    S = []
    maxv = 0
    #bufTmp[0] * size
    bufTmp.append(0)
    for i in range(size + 1):
        rect = Rectangle(bufTmp[i], i)
        
        if len(S) == 0:
            S.append(rect)
        else:
            if S[-1].height < rect.height:
                S.append(rect)
            elif S[-1].height > rect.height:
                target = i
                while len(S) >= 1 and S[-1].height >= rect.height:
                    pre = S.pop()
                    area = pre.height * (i-pre.position)
                    maxv = max(maxv, area)
                    target = pre.position
                rect.position = target
                S.append(rect)
    return maxv


def getLargestRectangle():
    for j in range(W):
        for i in range(H):
            if buf[i][j]:
                T[i][j] = 0
            else:
                if i > 0:
                    T[i][j] = T[i-1][j] + 1
                else:
                    T[i][j] = 1
    maxv = 0
    for i in range(H):
        maxv = max(maxv, getLargestRectangleRow(W, T[i]))

    return maxv


nums=list(map(int,input().split()))
H = nums[0]
W = nums[1]
buf = [[0 for i in range(W)] for j in range(H)]
T = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
    nums=list(map(int,input().split()))
    for j in range(W):
        buf[i][j] = nums[j]

print(getLargestRectangle())






















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

int main() {
	ios_base::sync_with_stdio( false );

	int N;
	cin >> N;

	map<int, int, greater<int>> m;
	for( int i = 0; i < N; ++i ) {
		int a;
		cin >> a;
		m[a] += 1;
	}

	int64_t result = 1;
	int x = 2;
	auto it = m.begin();

	while( x > 0 && it != m.end() ) {
		if( it->second < 2 ) {
			++it;
		}
		else {
			result *= it->first;
			it->second -= 2;
			x -= 1;
		}
	}

	cout << (x == 0 ? result : 0) << endl;
	return 0;
}


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

int main() {
  int N;
  cin >> N;
  vector<double> A(N);
  for (int i=0; i<N; i++) {
  	cin >> A.at(i);
  }
  sort(A.begin(), A.end());
  for (int i=0; i<N-1; i++) {
    A.at(i+1) = (A.at(i)+A.at(i+1))/2;
  }
  cout << A.at(N-1) << endl;
  
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

int len1,len2;
string s1,s2;
int f[3010][3010];

int main()
{
	cin>>s1>>s2;
	len1=s1.length();
	len2=s2.length();
	s1=' '+s1;
	s2=' '+s2;
	for(int i=1;i<=len1;i++)
	{
		for(int j=1;j<=len2;j++)
		{
			if(s1[i]==s2[j])
			{
				f[i][j]=f[i-1][j-1]+1;
			}
			else f[i][j]=max(f[i][j-1],f[i-1][j]);
		}
	}
	string s3;
	while(len1>0 && len2>0)
	{
		if(s1[len1]==s2[len2])
		{
			s3+=s1[len1];
			len1--;
			len2--;
		}
		else if(f[len1][len2]==f[len1][len2-1])
		{
			len2--;
		}
		else
		{
			len1--;
		}
	}
	reverse(s3.begin(),s3.end());
	cout<<s3;
	return 0;
}








Measured memory_bytes: 35584
n = int(input())
alst = list(map(int, input().split()))
alst.sort()
bef = -1
ans = n
for num in alst:
    if bef == num:
        ans -= 1
    bef = num
if ans % 2 == 1:
    print(ans)
else:
    print(ans - 1)

Measured memory_bytes: 20840
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>

using namespace std;
#define inf 0x3f3f3f3f
#define fast ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mp make_pair
#define pb push_back
#define sz(v) (int)v.size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)

typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
//const int N=1e6+7;

int main(){
    fast;
    int t=1;
    //cin>>t;
    for1(ks,t){
        int n,a,b,m;
        string s;
        cin>>n>>a>>b>>s;
        m=a+b;
        forn(i,n){
            if(s[i]=='c'){
                printf("No\n");
            }else if(s[i]=='a'&&m){
                printf("Yes\n"); m--;
            }else if(s[i]=='b'&&b&&m){
                printf("Yes\n"); b--;m--;
            }else{
                printf("No\n");
            }
        }
    }
    return 0;
}


Measured memory_bytes: 848
n, m = map(int, input().split())
List = list(map(int, input().split()))

if n >= m:
  print(0)
  
else:
  List.sort()
  dis = []
  for i in range(1, len(List)):
    dis.append(List[i] - List[i-1])
  dis.sort()
  res = 0
  for i in range(len(dis)-(n-1)):
    res += dis[i]
  print(res)

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

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  vector<int> B(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
    B.at(A.at(i) - 1) = i + 1;
  }
  
  for (int i = 0; i < N; i++) {
    cout << B.at(i);
    if (i < N - 1) {
      cout << " ";
    }
    else {
      cout << endl;
    }
  }
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
const int w=3e5+5;
const ll mod=1e9+7;
ll a[w];
ll n,m;
bool ok(ll x)
{
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==0)
        {
            if(x<=0)
                ans+=n-i;
            else
                continue;
        }
        else if(a[i]<0)
        {
            int l=i+1,r=n;
            while(l<=r)
            {
                int mid=(l+r)/2;
                if(a[mid]*a[i]>=x)
                    l=mid+1;
                else
                    r=mid-1;
            }
            ans+=r-i;
            //cout<<ans<<"^^^^"<<endl;
        }
        else
        {
            ll u=x/a[i];
            if(x%a[i]!=0)
                u++;
            int pos=lower_bound(a+1,a+1+n,u)-a;
            pos=max(i+1,pos);
            ans+=n-pos+1;
        }
    }
    return ans>=m;
}
int main()
{
    int i,j;
    cin>>n>>m;
    for(i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    sort(a+1,a+1+n);
    m=n*(n-1)/2-m+1;
    ll l=-1e18,r=1e18;
    while(l<=r)
    {
        ll mid=(l+r)/2;
        if(ok(mid))
            l=mid+1;
        else
            r=mid-1;
    }
    cout<<r<<endl;
    return 0;
}


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

using namespace std;

const int maxn = 1e5 + 100;
vector <int> v[maxn];
int dad[maxn];
long long dp[maxn];
bool visited[maxn];
int col[maxn];

int dfs(int x)
{
    visited[x] = 1;
    int tmp = 0;
    int ans = 0;
    for (int i = 0; i < v[x].size(); i++)
    {
        int u = v[x][i];
        if (!visited[u])
        {
            dad[u] = x;
            int ny = dfs(u);
            if(ny %2== 1)
            {
                tmp++;
            }
            ans += ny;
        }
        if(tmp > 1)
        {
            cout << "First";
            exit(0);
        }
    }
    return ans + 1;
}


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


    long long n, m;
    cin >> n;

    m = n - 1;
    for(int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    if (n %2== 1)
    {
        cout << "First";
        return 0;
    }
    dfs(0);
    cout << "Second";
}


Measured memory_bytes: 6272
n = int(input())

list_N = list(map(int, input().split()))

list_correct = list(range(1, len(list_N)+1))

score = 0
for i in range(n):
    if list_correct[i] != list_N[i]:
        score = score + 1

if score == 2 or score == 0:
    print("YES")
else:
    print("NO")

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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define each(x, y) for (auto &x : y)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ll << (b))
#define uniq(v) (v).erase(unique(all(v)), (v).end())
#define rsort(v) sort(all(v)); reverse(all(v))

using namespace std;

using i32 = int;
using i64 = long long;
using f80 = long double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << '\n'; exit(0); }
inline void no() { cout << "No" << '\n'; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { return a / gcd(a, b) * b; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }
template<typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template<typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template<typename T> inline void amax(T &x, T y) { if (x >= y) x = y; }
template<typename T> inline void amin(T &x, T y) { if (x <= y) x = y; }
template<typename T> inline T power(T x, i64 n) { T r = 1; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template<typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }

void solve() {
  string s;
  cin >> s;
  rep(i, s.size() - 8) cout << s[i]; cout << '\n';
}


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

using namespace std;

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    vector < int > li = {a, b, c};
    sort(li.begin(), li.end(), greater<>());
    cout << 10 * li[0] + li[1] + li[2] << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <numeric>
#include <algorithm>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main() {
	int n, m; cin >> n >> m;
	int N = (n * (n - 1)) / 2;
	int M = (m * (m - 1)) / 2;
	cout << N + M << endl;
}


Measured memory_bytes: 3616
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,K,*A = map(int, read().split())

    ans = float('inf')
    for i in range(2**(N-1)):
        if bin(i).count("1") != K-1:
            continue
        height = A[0]
        tmp = 0
        for j in range(N-1):
            if (i >> j) & 1:
                height += 1
                if A[j+1] >= height:
                    height = A[j+1]
                    continue
                tmp += height - A[j+1]
            height = max(height, A[j+1])
        ans = min(ans, tmp)
    
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
  using namespace std;
  long long MOD=1000000007;
  #define IOS() ios_base::sync_with_stdio(0); cin.tie(0);
  typedef long long ll;
  #define pb push_back
  typedef pair<string,string> pi;


int main()
{
  IOS();
  string a;
  string b;
  cin>>a>>b;
  // dp first
  //then find the string that is needed
  int A=a.length();
  int B=b.length();
  int dp[A+1][B+1];

  for (int i = 0; i <=B; ++i)
  {
  		dp[0][i]=0;
  }
  for (int i = 0; i <=A; ++i)
  {
  		dp[i][0]=0;
  }

  for(int i=1;i<=A;i++)
  {
  	for(int j=1;j<=B;j++)
  	{
  		if(a[i-1]==b[j-1])
  			dp[i][j]=dp[i-1][j-1]+1;
  		else
  			dp[i][j]=std::max(dp[i-1][j],dp[i][j-1]);
  	}
  }

	string ans="";
	int i=A;
	int j=B;
	while(i>0 && j>0)
	{
		if(b[j-1]==a[i-1])
		{
			
			ans=b[j-1]+ans;
			i--;j--;
		}
		else
		{
			if(dp[i-1][j]>dp[i][j-1])
				i--;
			else
				j--;
		}
	}
  
  cout<<ans<<endl;



  return 0;
}

Measured memory_bytes: 38804
#include <iostream>

using namespace std;

int cost(int N, int K, int X, int Y){
    int cost = 0;
    for (int i = 1; i <= N; i++){
        if(i <= K){
            cost += X;
        }else{
            cost += Y;
        }
    }
    return cost;
}


int main()
{
    int N, K, X, Y;
    cin >> N;
    cin >> K;
    cin >> X;
    cin >> Y;
    
    cout <<  cost(N, K, X, Y) << endl;

    return 0;
}

Measured memory_bytes: 256
N = int(input())
import heapq
def dijkstra_heap(s):
    d = [float("inf")] * N
    used = [True] * N
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d


edge = [[] for i in range(N)]
for i in range(N-1):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1])
    edge[y-1].append([z,x-1])
Q, K = map(int, input().split())
result = dijkstra_heap(K-1)
for i in range(Q):
    x, y = map(int, input().split())
    print(abs(result[x-1]-result[K-1])+abs(result[y-1]+result[K-1]))

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

const int size = 100000;

int main() {
    int n, tmp;
    cin >> n;
    int X[size];
    fill(X, X+size, 0);
    for (int i = 0; i < n; i++) {
        cin >> tmp;
        tmp--;
        for (int j = max(tmp-1, 0); j < min(tmp+2, size); j++) {
            X[j]++;
        }
    }

    cout << *max_element(X, X+size) << endl;
    return 0;
}

Measured memory_bytes: 640
n=int(input())
l=list(map(int,input().split()))
ml=max(l)
m=[0]*(ml+1)
for i in l:
    m[i]+=1
for i in range(ml+1):
    if m[i]>=1:
        for j in range(2*i,ml+1,i):
            if m[j]>0:
                m[j]=0
                #print(j)
for i in range(ml+1):
    if m[i]>=2:
        m[i]=0
print(sum(m))


Measured memory_bytes: 32196
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
char a[54]; 
int main() {
	scanf("%d",&n);
	scanf("%s",a+1);
	int ans=0;
	for (int s=1;s+2<=n;++s)
		if (a[s]=='A'&&a[s+1]=='B'&&a[s+2]=='C')
			++ans;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int count(int x, int c) {
    if(x >= 500) {
        return count(x-500, c+1);
    }
    if(x >= 100) {
        return count(x-100, c+1);
    }
    if(x >= 50) {
        return count(x-50, c+1);
    }
    if(x >= 10) {
        return count(x-10, c+1);
    }
    if(x >= 5) {
        return count(x-5, c+1);
    }
    if(x == 0) {
        return c;
    }
    else {
        return count(x-1, c+1);
    }
}

int main(void){
    int x;
    while(true) {
        cin >> x;
        if(x == 0) {
            break;
        }
        cout << count(1000 - x, 0) << endl;
    }
}



Measured memory_bytes: 3016
n = int(input())
prev = input()
s = set([prev])
for i in range(n-1):
    w = input()
    if w in s:
        print('No')
        exit()
    if w[0] != prev[-1]:
        print('No')
        exit()
    s.add(w)
    prev = w
print('Yes')

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ll long long
#define eps 1e-7
using namespace std;
#define pi acos(-1)

struct Node { int key; Node* le, * ri, * p; };
Node* root, * NIL;
void insert(int k) {
	Node* y = NIL, * x = root;
	Node* z;
	z = new(Node);
	z->key = k;
	z->le = NIL, z->ri = NIL;
	while (x != NIL) {
		y = x;
		if (z->key < x->key) x = x->le;
		else x = x->ri;
	}
	z->p = y;
	if (y == NIL) root = z;
	else {
		if (z->key < y->key) y->le = z;
		else y->ri = z;
	}
}
Node* find(int k) {
	Node* x = root;
	while (x != NIL) {
		if (x->key > k) x = x->le;
		else if (x->key == k) return x;
		else x = x->ri;
	}
	return NIL;
}
Node* getminium(Node* x) {
	while (x->le != NIL) x = x->le;
	return x;
}
Node* getsuccessor(Node* x) {// 返回最小大于key值的结点
	if (x->ri != NIL) return getminium(x->ri);
	Node* y = x->p;
	while (y != NIL && x == y->ri) {
		x = y;
		y = y->p;
	}
	return y;
}
void del(int k) {
	Node* u = find(k);
	Node* x, * y;
	if (u->le == NIL || u->ri == NIL) y = u;
	else y = getsuccessor(u);
	if (y->le != NIL) x = y->le;
	else x = y->ri;
	if (x != NIL) x->p = y->p;
	if (y->p == NIL) root = x;
	else {
		if (y == y->p->le) y->p->le = x;
		else y->p->ri = x;
	}
	if (y != u) u->key = y->key;
	free(y);
}
void preorder(Node* u) {
	if (u != NIL) {
		printf(" %d", u->key);
		preorder(u->le);
		preorder(u->ri);
	}
}
void inorder(Node* u) {
	if (u != NIL) {
		inorder(u->le);
		printf(" %d", u->key);
		inorder(u->ri);
	}
}


int main() {
	int n, i, k;
	string com;
	cin >> n;
	while (n--) {
		cin >> com;
		if (com == "insert") cin >> k, insert(k);
		else if (com == "print") inorder(root), cout << endl, preorder(root), cout << endl;
		else if (com == "find") {
			cin >> k;
			if (find(k) != NIL) cout << "yes" << endl;
			else cout << "no" << endl;
		}
		else if (com == "delete") cin >> k, del(k);
	}
}


Measured memory_bytes: 22076
#include <iostream>
using namespace std;
int x;
int main() {
	// your code goes here
	cin>>x;
	if(x%10==9){
		cout<<"Yes"<<endl;
		return 0;
	}
	x/=10;
	if(x==9){
		cout<<"Yes"<<endl;
		return 0;
	}
	else
	cout<<"No"<<endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;
 
int n, s, s2, mx = -2e9, a[105][15], b[105][15];
int main()
{
	int i, j, k, w;
	cin >> n;
	for (i = 0; i < n; i++) {
		for (j =0; j < 10; j++) {
			scanf ("%d", &a[i][j]);
		}
	}
	for (i = 0; i < n; i++) {
		for (j = 0; j <= 10; j++) {
			scanf ("%d", &b[i][j]);
		}
	}
	for (i = 1; i < 1024; i++) {
		s = 0;
		for (j = 0; j < n; j++) {
			w = i;
			s2 = 0;
			for (k =9; k >= 0; k--) {
				if (w % 2 == a[j][k] && w % 2 == 1) s2++;
				w /= 2;
			}
			s += b[j][s2];
		}
		mx = max(mx, s);
	}
	cout << mx;
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var X = ReadInt();
            var list = new List<string>() { "thu", "fri", "sat", "sun", "mon", "tue", "wed" };
            WriteLine(list[X % 7]);
        }
        private static string Read() { return ReadLine(); }
        private static string[] Reads() { return (Read().Split()); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}



Measured memory_bytes: 18000
n,m = map(int,input().split())
x = list(map(int,input().split()))
y = list(map(int,input().split()))
mod = 1000000007

keisu = len(x)-1
keisu_kaisa = keisu
ans = 0
for i in range(1,n):
  #print(keisu)
  ans = ans + 1*(x[i]-x[i-1])*keisu
  keisu_kaisa = keisu_kaisa -2
  keisu = keisu +(keisu_kaisa)
  ans = ans % mod
  
keisu = len(y)-1
keisu_kaisa = keisu
ans_2 = 0
for i in range(1,m):
  ans_2 = ans_2 + ans*(y[i]-y[i-1])*keisu
  keisu_kaisa = keisu_kaisa -2
  keisu = keisu +(keisu_kaisa)
  ans_2 = ans_2 % mod  
print(ans_2)

Measured memory_bytes: 18752
n = int(input())
l = list(map(int,input().split(" ")))
total = 0
for i in l:
    total += i

x = l[0]
y = total - x
a = abs(x - y)


for t in range(n):
    x = 0
    for i in range(t+1):
        x += l[i]
    y = total - x
    b = abs(x - y)
    if a > b:
        a = b

print(a)

Measured memory_bytes: 9184
N, W = map(int,input().split())
ls = []
for i in range(N):
  w, v = map(int, input().split())
  ls += [[w,v]]
w1 = ls[0][0]
for i in range(N):
  ls[i][0] -= w1
ans = 0
M = 3*N
dp = [[-1]*(M+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
  w, v = ls[i]
  for h in range(N,0,-1):
    for j in range(M,-1,-1):
      if j-w>=0 and dp[h-1][j-w]!=-1:
        dp[h][j] = max(dp[h][j], dp[h-1][j-w]+v)
for i in range(1,N+1):
  B = i*w1
  m = 0
  for j in range(M+1):
    if B+j<=W:
      m = max(m,dp[i][j])
  if ans<m:
    ans = m
print(ans)


Measured memory_bytes: 3460
def slove():
    import sys
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [int(input().rstrip('\n')) for _ in range(n)]
    cnt = 0
    q = 0
    while True:
        if cnt > n:
            print(-1)
            exit()
        elif q == 1:
            print(cnt)
            exit()
        else:
            q = a[q] - 1
            cnt += 1


if __name__ == '__main__':
    slove()


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

int main() {
  int x;
  rep(i,5) {
    cin >> x;
    if (x==0) {
      cout << i+1 << endl;
      return 0;
    }
  }
}

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

int main() {
  int N;
  long long Sum=0;
  cin >> N;
  vector<long long> A(N);
  map<long long, int> M;
  rep(i, N){
    cin >> A.at(i);
    M[i+A.at(i)]++;
  }
  rep(i, N) Sum+=M[i-A.at(i)];
  cout << Sum << endl;
}

Measured memory_bytes: 27280
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
   int t=1;
  // cin>>t;
   while(t--)
   {
    int n,k,i,x,y,ans=0;
    cin>>n>>k;
    for(i=0;i<n;i++)
   {
       cin>>x>>y;
      double z=(x*x+y*y);
       z=sqrt(z);
       double  p=k;
       if(z<=p)
       ans++;
   }
   cout<<ans<<endl;
   }
}


Measured memory_bytes: 3672
def bin_search(num, array):
    low = 0
    high = len(array) - 1

    while low <= high:
        mid = (low + high) // 2
        # print(mid)
        if array[mid] == num:
            return mid
        
        elif array[mid] > num:
            high = mid - 1
        
        elif array[mid] < num:
            low = mid + 1
    
    return -1

n = int(input())
S = tuple(map(int, input().split()))
q = int(input())
T = tuple(map(int, input().split()))

ans = 0
for i in T:
    # print("i = ",i)
    if bin_search(i, S) != -1:
        ans += 1
print(ans)


Measured memory_bytes: 16948
import sys
import itertools

input = sys.stdin.readline


def main():
    D, G = [int(x) for x in input().split()]
    pc = []
    for _ in range(D):
        pc.append([int(x) for x in input().split()])

    ruiseki = []
    for i, v in enumerate(pc):
        ruiseki.append((i + 1) * v[0] * 100 + v[1])

    ans = float("inf")
    for i in itertools.product(range(3), repeat=D):
        tmp = 0
        c = 0
        x = []
        for j, v in enumerate(i):
            if v == 0:
                continue
            elif v == 2:
                tmp += ruiseki[j]
                c += pc[j][0]
            else:
                if pc[j][0] == 1:
                    continue
                x.append(j)

        while tmp < G and x:
            y = x.pop()
            if G - tmp > (pc[y][0] - 1) * (y + 1) * 100:
                tmp += (pc[y][0] - 1) * (y + 1) * 100
                c += pc[y][0] - 1
            else:
                z = -(-(G - tmp) // ((y + 1) * 100))
                c += z
                tmp += z * (y + 1) * 100

        if tmp >= G:
            ans = min(ans, c)

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3188