akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h> 
using namespace std;

typedef long long ll;

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0) 
#define rep(pp,nn) for (int i = pp; i < nn; ++i)
#define vi vector<int>
#define vll vector<ll>
#define vs vector<string>
#define endl "\n"

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

string int_to_string(int x) {
    stringstream ss;
	ss << x;
	string ni = ss.str();
	return ni;
}
int string_to_int(string x) {
	int n;
	stringstream s(x);
	s >> n;
	return n;
}

int64_t power_mod(ll a, ll b, ll mo) {
	ll ans = 1;
	while (b) {
		if(b & 1) {
			ans = (ans % mo * a % mo) % mo;
		}
		a = (a % mo * a % mo) % mo;
		b /= 2;
	}
	return ans;
}
int64_t POW(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if(b & 1) {
			ans = ans * a;
		}
		a = a * a;
		b /= 2;
	}
	return ans;
}

vector<int64_t> INVERSE(int64_t nn, int64_t mo) {
	vector<int64_t> inv(nn + 1);
	vector<int64_t> mul(nn + 1);
	inv[0] = 1;
    inv[1] = 1;
	for (ll i = 2; i <= nn; ++i) {
		inv[i] = (mo - (mo / i) * inv[mo % i] % mo) % mo; 
	}
	mul[0] = 1;
	for (int i = 1; i <= nn; ++i) {
		mul[i] = (mul[i - 1] * inv[i]) % mo;
	}
	return mul;
}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}

#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

int main() {
	IOS;
	int n, k;
	cin >> n >> k;
	vector<int> d(n);
	for (int i = 0; i < n; ++i) {
		cin >> d[i];
	}
	int l = 1;
	int r = *max_element(d.begin(),d.end());
	while (l < r) {
		int mid = (l + r) / 2;
		int x = 0;
		for (int i = 0; i < n; ++i) {
			x += ((d[i] + mid - 1) / mid) - 1;
		} 
		if (x <= k) {
			r = mid;
		}else {
			l = mid + 1;
		}
	}
	cout << l;
}


















Measured memory_bytes: 3892
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,a,b) for(int i =(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPm(i,n) for(int i=(n)-1;i>=0;i--)
#define REP1(i,n) for(int i=1;i<=(n);i++)
#define mp make_pair
typedef long long ll;
int main(){
    int N,A,B;
    cin >> N >> A >> B;
    if((B-A)%2 == 0) cout << "Alice" << endl;
    else cout << "Borys" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define print(A,x,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i]x;}cout<<endl;
#define pprint(A,y,m,n) rep(j,0,m){print(A[j],y,n);}
const long mod=1e9+7;
const int size=1e4;
const long inf=1e9;
int main(){
	int A[3][3];
	rep(i,0,3)rep(j,0,3) cin>>A[i][j];
	int N;cin>>N;
	int b; int C[3][3];
	rep(i,0,N){
		cin>>b;
		rep(j,0,3)rep(k,0,3){
			if(b==A[j][k]) C[j][k]=1;
		}
	}
	rep(i,0,3){
		if(C[0][i]+C[1][i]+C[2][i]==3){ cout<<"Yes"<<endl; return 0; }
		if(C[i][0]+C[i][1]+C[i][2]==3){ cout<<"Yes"<<endl; return 0; }
	}
	if(C[0][0]+C[1][1]+C[2][2]==3){ cout<<"Yes"<<endl; return 0; }
	if(C[2][0]+C[1][1]+C[0][2]==3){ cout<<"Yes"<<endl; return 0; }
	cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>

long long inp_n1, inp_n2, inp_n3, inp_n4, i1;

long long inp_a[100005];

long long readNumber() {
	long long temp_func;
	scanf("%lld", &temp_func);
	return temp_func;
};
long long printNumber(long long temp_func) {
	printf("%lld", temp_func);
	return 0;
};

bool caler() {
	
	int i = 1;
	
	while (1) {
		
		if (i == 1) {
			
			inp_n3 -= inp_n2;
			
			if (inp_n3 <= 0) {
				
				return true;
				
			};
			
		} else {
			
			inp_n1 -= inp_n4;
			
			if (inp_n1 <= 0) {
				
				return false;
				
			};
			
		};
		
		i *= -1;
		
	};
	
};

int main() {
	
	inp_n1 = readNumber();
	
	inp_n2 = readNumber();
	
	inp_n3 = readNumber();
	
	inp_n4 = readNumber();
	
	if (caler()) {
		
		printf("Yes");
		
	} else {
		
		printf("No");
		
	};
	
}

Measured memory_bytes: 1736
n = int(input())
arms = [list(map(int, input().split())) for _ in range(n)]
arms.sort(key=lambda x: x[0]+x[1])
ans = 0
cur = -10**20
for x, l in arms:
	if x-l >= cur:
		ans += 1
		cur = x+l
print(ans)

Measured memory_bytes: 32296
from numpy import *
H,W = map(int,input().split())
N = int(input())
A = list(map(int,input().split()))
B = []
ans = zeros((H,W),int64)

for n in range(N):
  B.extend(A[n]*[n+1])

n = 0
for h in range(H):
  for w in range(W):
    if h%2==0:
      ans[h][w] = B[n]
    else:
      ans[h][-(w+1)] = B[n]
    n+=1

for h in range(H):
  print(*ans[h])

Measured memory_bytes: 27452
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int cl(int a, int b) {
	return (a - (a%b)) / b;//b=0だと積む
}
int up(int a, int b) {
	return cl(a + b - 1, b);//b=0だと積む
}
int main() {
    int az=0;
    while(az==0){
	int n,m, ba,tu; int ans = 0;
	cin >> n>>m;
	if(n*n+m*m==0){
	    az=1;
	}
	else{
	vector<int> ch(n,0);
	vector<int> yobi(n, 0);
	ch[0] = 1;
	vector<int> a(m);
	vector<int> b(m);
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x>>y;
		a[i] = x - 1; b[i] = y - 1;
	}
	for (int j = 0; j < 2; j++) {
		yobi = ch;
		for (int i = 0; i < m; i++) {
			if (yobi[a[i]] == 1 or yobi[b[i]] == 1) {
				ch[a[i]] = 1;
				ch[b[i]] = 1;
			}
		}
	}
	ch[0] = 0;
	for (int i = 0; i < n; i++) {
		ans = ans + ch[i];
	}
	cout <<ans << endl;
	}
    }
}



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

using ll = long long int;
using bigint = int64_t;

#define pll pair<ll, ll>
#define vll vector<ll>
#define vpll vector<pll>
#define lob lower_bound
#define upb upper_bound
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define ins insert
#define mp make_pair
#define w(t) cin >> t;while(t--)
#define bitcount __builtin_popcount
#define endl "\n"
#define sz(s) (int)s.size()
#define mem(n,m) memset(n,m,sizeof(n))
#define deb(x) cout << #x << " = " << x << endl;
#define rep(i,n) for(ll i = 0; i < n; i++)
#define ren(i,n) for(ll i = n-1; i >= 0; i--)
#define all(x) x.begin(),x.end()
#define fo(i, a, b) for(ll i = a; i <= b; i++)
#define ffo(i, a, b) for(ll i = a; i >= b; i--)
#define ffi(i,a,b,c) for(ll i = a ; i <= b ; i += c)
#define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int mod = 1000000007;

void io_set() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

void solve() {
    ll n, ans = 0;
    cin >> n;
    ll a[n], suff[n];
    rep(i, n)   cin >> a[i], suff[i] = 0;
    ren(i, n - 1) {
        suff[i] = (suff[i] % mod + (suff[i + 1] % mod + a[i + 1] % mod) % mod) % mod;
    }
    //rep(i, n)   cout << suff[i] << " ";
    rep(i, n) {
        ans = (ans % mod + (a[i] % mod * suff[i] % mod) % mod) % mod;
    }
    cout << ans << endl;
}

int main() {
    IOS;
    //io_set();
    ll tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 6776
from collections import deque
 
K = int(input())
que = deque([i for i in range(1, 10)])
lunlun = []
 
while que:
    num = que.pop()
    lunlun.append(num)
    for i in range(10):
        if abs(int(str(num)[-1]) - i) <= 1:
            cand = int(str(num) + str(i))
            if cand < 10000000000:
                que.append(cand)
 
lunlun.sort()
print(sorted(lunlun)[K - 1])


Measured memory_bytes: 59868
// Copyright 2020 yaito3014
#include <bits/stdc++.h>

int main() {
  std::cin.tie(nullptr); std::ios::sync_with_stdio(false);
  int N;
  std::cin >> N;
  bool ans = N / 10 == 9 || N % 10 == 9;
  std::cout << (ans ? "Yes" : "No") << std::endl;
}


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

namespace _0177
{
    public class Program

    {
        public static void Main(string[] args)
        {
            while (true)
            {
                double[] items = RDoubleAr();
                if (items.All(x => x == -1)) break;
                Console.WriteLine(Math.Round(GetDistance(items),0,MidpointRounding.AwayFromZero));
            }
        }

        private static double GetDistance(double[] items)
        {
            const double R = 6378.1;

            double lat1 = items[0];
            double lng1 = items[1];
            double lat2 = items[2];
            double lng2 = items[3];

            double theta = Math.Cos(lat1 / 180 * Math.PI) *
                           Math.Cos((lng2 - lng1) / 180 * Math.PI) *
                           Math.Cos(lat2 / 180 * Math.PI) +
                           Math.Sin(lat1 / 180 * Math.PI) *
                           Math.Sin(lat2 / 180 * Math.PI);

            return R * Math.Acos(theta);
        }

        static string RSt() { return Console.ReadLine(); }
        static int RInt() { return int.Parse(Console.ReadLine().Trim()); }
        static long RLong() { return long.Parse(Console.ReadLine().Trim()); }
        static double RDouble() { return double.Parse(Console.ReadLine()); }
        static string[] RStAr(char sep = ' ') { return Console.ReadLine().Trim().Split(sep); }
        static int[] RIntAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => int.Parse(e)); }
        static long[] RLongAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => long.Parse(e)); }
        static double[] RDoubleAr(char sep = ' ') { return Array.ConvertAll(Console.ReadLine().Trim().Split(sep), e => double.Parse(e)); }
        static string WAr<T>(IEnumerable<T> array, string sep = " ") { return string.Join(sep, array.Select(x => x.ToString()).ToArray()); }
    }

}



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

vector<long> factori(long v){
  vector<long> ret;
  for(long i = 2; i*i<=v; i++){
    if(v % i==0){
      ret.push_back(i);
    }
    while(v%i==0)v/=i;
  }
  if(v > 1)ret.push_back(v);
  return ret;
}
void solve()
{
  long A, B;
  cin >> A >> B;
  long g = __gcd(A,B);
  auto v = factori(g);
  int cnt = v.size();
  //long ans = 1;
  //rep(i,cnt)ans*=cnt;
  cout << (cnt+1) << endl;
}
int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(11);
  solve();
  return 0; 
}


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

using namespace std;

int main(){
	
	long long int ans[40];
	
	for(int i = 0; i < 40; i++){
		ans[i] = 0;
	}
	
	ans[0] = 1;
	
	for(int i = 0; i < 31; i++){
		ans[i + 3] += ans[i];
		ans[i + 2] += ans[i];
		ans[i + 1] += ans[i];
	}
	
	while(true){
		
		int n;
		
		cin >> n;
		
		if(n == 0){
			break;
		}
		
		cout << (ans[n] + 3649) / 3650 << endl;
		
	}
	
	return 0;
}

Measured memory_bytes: 2988
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class AtCoderA
{
    static void Main()
    {
        var sc = new Scanner();

        int n = sc.NextInt();
        int m = sc.NextInt();

        int[] counts = new int[n];
        for (int i = 0; i < n; i++)
        {
            counts[i] = 1;
        }
        bool[] ok = new bool[n];
        ok[0] = true;

        for (int i = 0; i < m; i++)
        {
            int x = sc.NextInt() - 1;
            int y = sc.NextInt() - 1;
            bool isRed = ok[x];
            counts[x]--;
            counts[y]++;
            if (counts[x] == 0)
            {
                ok[x] = false;
            }
            if (isRed)
            {
                ok[y] = true;
            }
        }

        int answer = ok.Where(b => b).Count();

        Console.WriteLine(answer);
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}


Measured memory_bytes: 17456
#include<bits/stdc++.h>
using namespace std;
#define N 2005
#define ll long long
const ll mod=1e9+7;
int a[N],b[N];
ll dp[N][N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
        scanf("%d",&b[i]);

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            dp[i][j]=(dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1])%mod;
            if(a[i]==b[j])
                dp[i][j]=(dp[i][j] + dp[i-1][j-1] + 1)%mod;
        }
   cout<<(dp[n][m]+1+mod)%mod;
    return 0;
}


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

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
//typedef pair<ll, ll> P;
typedef pair<double, double> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<string> &o) {
    string a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const ll mod = 1e10;

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;


int main() {
    ll q, h, s, d;
    cin >> q >> h >> s >> d;
    cmin (h, q + q);
    cmin (s, h + h);
    cmin (d, s + s);

    ll n;
    cin >> n;

    if (n % 2 == 0) {
        cout << (n / 2) * d << endl;
    } else {
        cout << (n / 2) * d + s << endl;
    }

}


Measured memory_bytes: 256
a,b= map(int,input().split())
arr = [0]*b

for x in range(a):
    te = list(map(int,input().split()))
    K = te[0]
    if a != 1:
        for p in range(K):
            arr[te[p+1]-1] += 1
    else:
        arr = list(set(te[1:len(te)]))
h = max(arr)

if h == a:
    print(arr.count(h))
elif a == 1:
    print(len(arr))
else:
    print(0)

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

using namespace std;

#define    watch(x); cout << "\n" <<  #x << " is: " << x << "\n";
#define    all(a) (a).begin(), (a).end()
#define    fi first
#define    se second

template<class A, class B>
ostream& operator << (ostream& output, const pair<A, B>& p) {
    output << "(" << p.first << ", " << p.second << ")";
    return output;
}

template<class A>
ostream& operator << (ostream& output, const vector<A>& a) {
    output << "[";
    for(auto it = a.begin(); it != a.end(); ++it) {
        if(it != a.begin()) {
            output << ", ";
        }
        output << *it;
    }
    output << "]";
    return output;
}

using lld = long long;
using pii = pair<int, int>;
using pll = pair<lld, lld>;

//const int inf = 1e9;
//const int mod = 1e9 + 7;
//const double PI = acos(-1.0);
//const int mx = 1e5 + 5;



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifndef ONLINE_JUDGE
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif

    int n;
    cin >> n;
    if(n & 1) {
        cout << n * 2 << endl;
    }
    else {
        cout << n << endl;
    }

    return 0;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;
ll a[200005];
ll b[200005];

int main(void){
	scanf("%d",&n);
	ll sum=0;
	for(int i=0;i<n;i++){
		scanf("%lld%lld",&a[i],&b[i]);
		sum+=a[i];
	}
	bool flag=false;
	for(int i=0;i<n;i++){
		if(a[i]!=b[i])flag=true;
	}
	if(!flag){
		printf("0\n");
		return 0;
	}
	for(int i=0;i<n;i++){
		if(a[i]<b[i]){
			b[i]-=a[i];
			a[i]=0;
		}
	}
	for(int i=0;i<n;i++){
		if(a[i]==b[i]){
			b[i]-=a[i];
			a[i]=0;
		}
	}
	ll v=-1;
	for(int i=0;i<n;i++){
		if(a[i]>b[i]){
			if(v==-1)v=b[i];
			else v=min(b[i],v);
		}
	}
	printf("%lld\n",sum-v);
	return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int h[200000];
int main(){
	string s;
	getline(cin,s);
	for(int i=0;i<s.length();i++){
		if(s[i]=='0'){
			h[i]=0;
		}else{
			h[i]=1;
		}
	}
	int cnt1=0,cnt2=0;
	for(int i=1;i<s.length();i+=2){
		if(h[i]==1){
			cnt1++;
		}
	}
	for(int i=0;i<s.length();i+=2){
		if(h[i]==1){
			cnt2++;
		}
	}
	int ans=0;
//	cout<<cnt2<<" "<<cnt1<<endl; 
	if(cnt2>cnt1){
		for(int i=0;i<s.length();i++){
			if(i%2==0&&h[i]==0){
				ans++;
			}
			if(i%2==1&&h[i]==1){
				ans++;
			}
		}
	}else{
		for(int i=0;i<s.length();i++){
			if(i%2==0&&h[i]==1){
				ans++;
			}
			if(i%2==1&&h[i]==0){
				ans++;
			}
		}
	}
	cout<<ans;
	return 0;
} 

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

string s[106];

int main ()
{
    map<string,int> mp;
    int n;
    cin >> n;
    for (int i=0;i<n;++i)
    {
        string x;
        cin >> x;
        s[i] = x;
        mp[x] = 1;
    }
    if (mp.size() != n)
    {
        puts("No");
        return 0;
    }
    for (int i=1;i<n;++i)
    {
        if (s[i-1].back() == s[i].front()) ;
        else 
        {
            puts("No");
            return 0;
        }
    }
    puts("Yes");
    return 0;
}


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

using namespace std;

typedef long long ll;

int main() {
	ll n;
	while (cin >> n, n) {
		vector<ll> v;
		for (ll i = 0; i < n; ++i) {
			ll a; cin >> a;
			v.push_back(a);
		}

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

		ll s = 0;
		for (ll i = 0; i < n-1; ++i)
			s += v[i] * (n-i-1);

		cout << s << endl;
	}
}

Measured memory_bytes: 1336
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
int n;
map<int,int>mp1;
map<int,int>mp2;
struct P
{
    int x,y;
    P(){}
    P(int a,int b)
    {
        x=a;y=b;
    }
}p1[100000+5],p2[100000+5];
bool cmp(const P &t1,const P &t2)
{
    return t1.y>t2.y;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        if(i%2==1)
        {
            mp1[x]++;
        }
        else
        {

            mp2[x]++;
        }
    }
    int n1=0,n2=0;
    for(map<int,int>::iterator it=mp1.begin();it!=mp1.end();it++)
    {
        p1[n1++]=P((*it).first,(*it).second);
    }
    for(map<int,int>::iterator it=mp2.begin();it!=mp2.end();it++)
    {
        p2[n2++]=P((*it).first,(*it).second);
    }
    sort(p1,p1+n1,cmp);
    sort(p2,p2+n2,cmp);
    if(p1[0].x==p2[0].x)
    {
        if(n1>=2&&n2==1)
        {
            printf("%d\n",n/2-p1[1].y);
        }
        else if(n1==1&&n2>=2)
        {
            printf("%d\n",n/2-p2[1].y);
        }
        else if(n1==1&&n2==1)
        {
            printf("%d\n",n/2);
        }
        else
        {
            printf("%d\n",n-max(p1[0].y+p2[1].y,p1[1].y+p2[0].y));
        }
    }
    else printf("%d\n",n-p1[0].y-p2[0].y);
    return 0;
}


Measured memory_bytes: 5760
#include<stdio.h>
int main(void){
	int a,b,c;
	char chr;
	while(scanf("%d %c %d",&a,&chr,&b) && chr != '?'){
	if(chr == '+')	c = a+b;
	else if(chr == '-')  c = a-b;
	else if(chr == '*')  c = a*b;
	else if(chr =='/') c = a/b;
	printf("%d\n",c);
	}
	return 0;
}


Measured memory_bytes: 2056
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

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; }

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

int main(int argc, char const *argv[]) {
    string s,t; cin>>s>>t;
    int ans = 0;
    rep(i,s.length()) if (s[i] != t[i]) ans++;
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 3848
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define fs first
#define sc second
typedef pair<ll, ll> l_l;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main(){
  string s;
  cin>>s;
  int tmp;
  for(int i=s.size()-1;i>=0;i--){
    if(s[i]=='A') tmp=i;
  }
  int cnt;
  for(int i=0;i<s.size();i++){
  if(s[i]=='Z') cnt=i;
  }
  cout<<cnt-tmp+1<<endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define BIG 1000000010
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
typedef long long int ll;


int main(){
  char x,y;
  cin>>x>>y;
  if(x==y) cout<<"="<<endl;
  else if(x>y) cout<<">"<<endl;
  else cout<<"<"<<endl;

  return 0;
}





Measured memory_bytes: 256
n,y = list(map(int,input().split()))
y /= 1000


for b in range(n+1):
  for f in range(n-b+1):
    if (y - b*10 - 5*f) == n-b-f:
      ans = [b, f, n-b-f]
      print(*ans)
      exit()

ans = [-1,-1,-1]
print(*ans)

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

int main()
{
    long double a, b, c;
    cin >> a >> b >> c;
    if(a + b + 2*sqrt(a*b) < c) cout << "Yes";
    //if(sqrt(a) + sqrt(b) < sqrt(c)) cout << "Yes";
    else cout << "No";
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define f first
#define s second
#define go ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mem(arr,v) memset(arr,v,sizeof(arr))
/*bool sortbysec(const pair<int,int> &a,
              const pair<int,int> &b)
{
    return (a.second < b.second);
} */
int main()
{
     ll t,a,b,vk,kk;
     cin>>t>>a>>b;
     kk=a+b;
     vk=t/kk;
     t=t%(a+b);
     cout<<vk*a+min(t,a)<<endl;
}


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

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

	int ans = 0;

	for (int i = 0;i < n - 1;i++) {
		int count = 0;
		bool x[26];
		for (int j = 0;j < 26;j++) {
			x[j] = false;
		}
		for (int j = 0;j <= i;j++) {
			x[s[j] - 'a'] = true;
		}
		for (int j = i + 1;j < n;j++) {
			if (x[s[j] - 'a']) {
				x[s[j] - 'a'] = false;
				count++;
			}
		}
		ans = max(ans, count);
	}

	cout << ans << endl;





	return 0;
}

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


using namespace std;

vector<int> a(100001, 0);

int main() {
	int N;
	cin >> N;
	int tmp = 0;

	for (int i = 0; i < N; i++)
	{
		cin >> tmp;

		if (tmp != 0) {
			a[tmp - 1]++;
			a[tmp]++;
			a[tmp + 1]++;
		}
		if (tmp == 0) {
			a[tmp]++;
			a[tmp + 1]++;
		}
	}

	int nowMax = 0;
	for (int i = 0; i < a.size(); i++)
	{
		if (a[i] > nowMax) {
			nowMax = a[i];
		}
	}

	cout << nowMax << endl;
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

int main()
{
	long long x,y;
	cin>>x>>y;
	long long i=x;
	int cnt=0;
	while (i<=y)
	{
		cnt++;
		i*=2;
	}
	cout<<cnt<<endl;
	return 0;
}


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

class Graph{
public:
	std::vector< std::vector<int> > A;
	std::vector<int> Cluster;
	int n;

	Graph(int n);

	bool isConnected(int s, int t);

	void MakeCluster();

	void Link(int s, int t);

};

Graph::Graph(int n){
	A.resize(n);
	Cluster.resize(n);
	for (int i = 0; i < n; i++) Cluster[i] = 0;
	this->n = n;
}

void Graph::Link(int s, int t){
	A[s].push_back(t);
	A[t].push_back(s);
	return;
}

void Graph::MakeCluster(){
	int clusternum = 0;
	std::list<int> Q;
	for (int i = 0; i < n; i++){
		if (Cluster[i] == 0){
			Q.clear();
			clusternum++;
			Cluster[i] = clusternum;
			Q.push_back(i);
			bool res = false;
			while (!Q.empty()){
				int f = Q.front();
				Q.pop_front();
				for (std::vector<int>::iterator itr = A[f].begin(); itr != A[f].end(); itr++){
					if (Cluster[*itr] == false){
						Cluster[*itr] = clusternum;
						Q.push_back(*itr);
					}
				}
			}
		}
	}
	return;
}

bool Graph::isConnected(int s, int t){
	return Cluster[s] == Cluster[t];
}

int main(){
	int n, m, s, t, q;
	scanf("%d%d", &n, &m);
	Graph G(n);
	for (int i = 0; i < m; i++){
		scanf("%d%d", &s, &t);
		G.Link(s, t);
	}
	scanf("%d", &q);
	G.MakeCluster();
	for (int i = 0; i < q; i++){
		scanf("%d%d", &s, &t);
		if (G.isConnected(s, t)) printf("yes\n"); else printf("no\n");
	}
	
	return 0;
}


Measured memory_bytes: 8940
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repR(i, n) for(int i = n; i >= 0; ++i)
#define FDS(i, n) for(ll i = 0; i < n; ++i)
#define FDSR(i, n) for(int i = n; i >= 0; ++i)
#define FOR(i, m, n) for(int i = m; i < n; ++i)
#define FORR(i, m, n) for(int i = m;i >= n;--i)
#define VSORT(v) sort(v.begin(), v.end());
#define INF 999999999
#define itn int
#define ednl endl
using namespace std;
typedef long long ll;template<typename TypeInt>TypeInt G_C_D(TypeInt a, TypeInt b){if (a < 0) a = -a;if (b < 0) b = -b;while (b != 0) {a %= b;if (a == 0) return b;b %= a;}return a;}template<typename TypeInt>
TypeInt G_C_D(const std::vector<TypeInt> &list){TypeInt a = list[0];for (size_t i = 1; i < list.size(); ++i) {a = G_C_D(a, list[i]);}return a;}template<typename TypeInt>TypeInt L_C_M(TypeInt a, TypeInt b) {if( a == 0 && b == 0)return 0;return a / G_C_D(a, b) * b;}
template<typename TypeInt>TypeInt L_C_M(const std::vector<TypeInt> &list){TypeInt a = list[0];for (size_t i = 1; i < list.size(); ++i) {a = L_C_M(a, list[i]);}return a;}

int main(){
	int N,n;
	cin>>N>>n;
	cout<<N+n/2<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define all(t) t.begin(), t.end()
#define inrange(i, a, b) (((i)>= min((a), (b))) && ((i) <= max((a), (b))))
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
#define fi first
#define se second
#define upb upper_bound
#define lwb lower_bound
#define show(x) cout << #x << " is " << x << "\n";
const ll inf = 2e18;
const ll mod = 1e9 + 7;
const ld pi = 3.141592653589793238462643383279502884;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void print(ll a[], ll n){for(ll i=0;i<n;i++){cout<<a[i]<<" ";}cout<<"\n";}
ll power(ll x, ll y){
    if(y<=0) return 1;
    ll ans = 1;
    x %= mod;
    while(y){
        if(y&1)
            ans = (x * ans) % mod;
        x = (x * x) % mod;
        y >>= 1;
    }
    return ans;
}
ll modInverse(ll n) {return power(n, mod-2);}
inline ll mul(ll a, ll b){ return (a * b) % mod; }
inline ll sub(ll a, ll b){ ll c = (a - b); if(c < 0) c += mod; return c; }
inline ll add(ll a, ll b){ ll c = (a + b); if(c >= mod) c -= mod; return c; }
inline ll divi(ll a, ll b){ return mul(a, modInverse(b)); }

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

//const ll N = 2e5 + 1;
//vector<ll> adj[N];
//bool visited[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cout<<fixed<<setprecision(10);

	ll n;
	cin>>n;
	string s;
	cin>>s;
	int i=0, j = n-1;
	while(i<n && s[i]=='R') i++;
	while(j>=0 && s[j]=='W') j--;
	if(i==n || j==-1 || i-j==1) cout<<0;
	else{
		int r=0, w=0;
		for(int k=i;k<=j;k++){
			if(s[k]=='R') r++;
			else w++;
		}
		ll ans = min(r, w);
		ll c=0;
		for(int k=i;k<i+r;k++){
			if(s[k]=='W') c++;
		}
		
		cout<<min(ans, c);
	}
    return 0;
}


Measured memory_bytes: 3776
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for(int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

int main() {
    int n, k;
    cin >> n >> k;
    int p[n];
    rep(i,n)cin >> p[i];
    sort(p,p+n);

    int ans = 0;
    rep(i,k)ans += p[i];

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




Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
int main(){
  string str;

  getline(cin,str);

  for(int i=0; i<(int)str.size(); i++){
    if(islower(str[i])){
	str[i]=toupper(str[i]);
    } else if( isupper(str[i])){
	str[i] = tolower(str[i]);
    }
  }
  cout << str << endl;
  return 0;
}


Measured memory_bytes: 3204
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B;
  cin >> A >> B;
  
  int count = 1;
  for(int i=1; i<20; i++){
    if(B == 1){
      cout << 0 << endl;
      break;
    }
    count += A - 1;
    if (count >= B){
      cout << i << endl;
      break;
    }
  }
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(100000)

N,K=map(int,input().split())
MOD=10**9+7
branch=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  branch[a-1].append(b-1)
  branch[b-1].append(a-1)

if K==1:
  if N==1:
    print(1)
  else:
    print(0)
  exit()
  
P=[0]*(K-1)
P[K-2]=K-2
for i in range(K-3,0,-1):
  P[i]=P[i+1]*i%MOD
  
def PPP(start,num):
  if start<num:
    return 0
  if start==K-2:
    return P[start-num+1]
  if start==K-1:
    return P[start-num+2]*(K-1)%MOD
  
ans=1

def draw(parent,nord):
  global ans
  children=len(branch[nord])-(parent !=-1)
  if children==0:
    return
  #(K-2)*(K-1)*... をchildrenの数だけ掛ける。
  ans=ans*PPP(K-1-(parent !=-1),children)%MOD
  for b in branch[nord]:
    if b != parent:
      draw(nord,b)

for i in range(len(branch[0])+1):
  ans=ans*(K-i)%MOD
for bra in branch[0]:
  draw(0,bra)
print(ans)

Measured memory_bytes: 156544
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto S = readln.chomp.to!(char[]);
    foreach (i, c; S) {
        if (i%2 == 0) {
            if (c == 'L') {
                writeln("No");
                return;
            }
        } else {
            if (c == 'R') {
                writeln("No");
                return;
            }
        }
    }
    writeln("Yes");
}

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

int main()
{
 string s,s1;
  cin >> s;
  cin >> s1;
  s1 = s1.substr(0,s1.length()-1);
  if(s == s1)
  {
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 3628
N, M = list(map(int, input().split(" ")))

A = []
for i in range(N):
    A.append(input())
    
B = []
for i in range(M):
    B.append(input())

    
ans_flag = False
for i in range(N-M+1):  
    for j in range(N-M+1):
        if A[i][j:j+M] == B[0]:
            ans_flag = True
            for k in range(1, M):
                if A[i+k][j:j+M] != B[k]:
                    ans_flag = False
                    break
            if ans_flag == True:
                break
        if ans_flag == True:
                break
    if ans_flag == True:
                break
            
if ans_flag == True:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
#define lld long double
#define MOD 1000000007
#define CAP 100000001
#define inf 1000000000000000LL
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define sz(v) v.size()
#define all(v)    v.begin(),v.end()
#define fast  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define int ll
using namespace std;
ll power(ll x,ll y, ll md=MOD){ll res = 1;x%=md;while(y>0){if(y&1)res = (res*x)%md;x = (x*x)%md;y = y>>1;}return res%md;}

signed main() {
	fast;
	string s;
	cin>>s;
	ll n=s.size();

	ll cnt=0;
	ll temp=0;
	ll prev=-1;
	for(int i=n-1;i>1;i--){

		if(s[i]=='C'&&s[i-1]=='B'&&s[i-2]=='A'){
			cnt++;
			s[i-2]='B';
			s[i-1]='C';
			s[i]='A';

			if(prev==-1||prev!=i+2) temp=0;

			cnt+=temp;
			if(prev!=-1)prev--;
		}
		if(s[i]=='C'&&s[i-1]=='B') {
			if(prev==-1){
				prev=i;
				temp=1;
			}
			else if(prev==i+2) {
				temp++;
				prev=i;
			}
			else{
				temp=1;
				prev=i;
			}
		}
	}
	cout<<cnt;
} 

Measured memory_bytes: 720
N=list(map(int,input()))
N.reverse()
N.append(0)
n=len(N)
pay=[0]*n
price = list(N)

for i in range (n):
    if N[i]>5:
        pay[i]=0
        N[i+1]=N[i+1]+1
    elif  N[i]<5:
        pay[i]=N[i]
    else:
        if N[i+1]>=5:
            pay[i]=0
            N[i+1]=N[i+1]+1
        else:
            pay[i]=N[i]


#print(price)
#print(pay)
sum_pay=sum(pay)

c=0
for i in range (n):
    if pay[i]-price[i]>=0:
        c=c+pay[i]-price[i]
    else:
        c=c+10+pay[i]-price[i]
        pay[i+1]=pay[i+1]-1

sum_otsuri=c

#print(sum_otsuri)
#print(sum_pay)

sum=sum_otsuri+sum_pay
print(sum)

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


int main() {
  string s;
  cin >> s;
  int c = s.back() - '0';
  
  if (c == 3) {
    cout << "bon" << endl;
  } else if (c == 0 || c == 1 || c == 6 || c == 8) {
    cout << "pon" << endl;
  } else {
    cout << "hon" << endl;
  }
}

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

int main(){
    int A, B, C;
    cin >> A >> B >> C;
    if( A == 5 && B == 5 && C == 7){
        cout << "YES" << endl;
    }else if( A == 5 && B == 7 && C == 5){
        cout << "YES" << endl;
    }else if( A == 7 && B == 5 && C == 5){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    return 0;
}

Measured memory_bytes: 3600
//kとk-1ミスって３０分溶かした。
#include <iostream>
#define int long long
using namespace std;

int powmod(int a, int n, int mod) {
	if (n == 0) return 1;
	if (n % 2 == 0) return powmod((a * a) % mod, n / 2, mod);
	return (a * powmod(a, n - 1, mod)) % mod;
}

int mod = 1000000007;
int fact[114514];
int factInv[114514];
int n, X, Y;

void input() {
	static int a[114514];
	static int cnt[114514] = {0};
	int i;
	
	cin >> n;
	for (i = 0; i < n + 1; i++) {
		cin >> a[i];
		cnt[a[i]]++;
	}
	
	for (i = 1; i <= n; i++) {
		if (cnt[i] == 2) {
			break;
		}
	}
	
	int val = i; X = -1;
	for (i = 0; i <= n; i++) {
		if (a[i] == val) {
			if (X == -1) X = i;
			else Y = n - i;
		}
	}
}

void init() {
	fact[0] = 1;
	for (int i = 1; i < n + 2; i++) fact[i] = (fact[i - 1] * i) % mod;
	for (int i = 0; i < n + 2; i++) factInv[i] = powmod(fact[i], mod - 2, mod);
}

int comb(int n, int k) {
	if (k > n) return 0;
	return (((fact[n] * factInv[n - k]) % mod) * factInv[k]) % mod;
}

signed main() {
	input();
	init();
	
	cout << n << endl;
	for (int k = 2; k <= n + 1; k++) {
		int ans = 0;
		
		ans += comb(n - 1, k - 2);
		ans += comb(n - 1, k - 1);
		
		int Z = n - X - Y - 1;
		int tmp = 0;
		tmp += comb(X + Y + Z, k - 1);
		tmp -= comb(X + Y, k - 1);
		tmp += mod;
		tmp %= mod;
		//cout << "k = " << k << " tmp = " << tmp << endl;
		ans += tmp;
		
		ans += comb(n - 1, k);
		ans %= mod;
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  int a[n];
  for(int i=0; i<n; i++){
    cin >> a[i];
  }
  int sum,mi=99999999;
  for(int i=-100; i<=100; i++){
    sum = 0;
    for(int j=0; j<n; j++){
      sum += (a[j]-i)*(a[j]-i);
    }
    mi = min(mi,sum);
  }
  cout << mi << endl;
}

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

int main()
{
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto&& e : a) cin >> e;
  string ans = "APPROVED";
  for (const auto& e : a) {
    if (e % 2 != 0) continue;
    if (e % 3 == 0 || e % 5 == 0) continue;
    ans = "DENIED";
    break;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
my $input_string = <STDIN>;

my $N = 0;
my $K = 0;

($N, $K) = split(/ /, $input_string);

my $input_string = <STDIN>;

my @L = ();
@L = split(/ /, $input_string);

@L = sort {$b <=> $a} @L;

my $snake = 0;
for(my $i = 0; $i < $K; $i++){
	$snake += $L[$i];
}
print $snake;

Measured memory_bytes: 384
N = int(input())
l = list(map(int,input().split()))
abs_min = 10001
for i in range(N):
  min_ = sum(l[0:i])
  sum_ = sum(l)
  abs_d = abs(sum_ - 2*min_)
  if abs_min > abs_d:
    abs_min = abs_d
print(abs_min)

Measured memory_bytes: 3060
n,q=map(int,input().split())
s=str(input())
a=[0]*(n+1)
a[0]=0
for i in range(n):
    if s[i:i+2]=="AC":
        a[i+1]=a[i]+1
    else:
        a[i+1]=a[i]+0
for i in range(q):
    b,c=map(int,input().split())
    print(int(a[c-1]-a[b-1]))

Measured memory_bytes: 7748
from fractions import gcd
# from datetime import date, timedelta
# from heapq import *
import heapq
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import fractions
import sys
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
# input = sys.stdin.readline


def lcm(a, b):
    return a * b / fractions.gcd(a, b)


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def is_prime(n):
    if n == 1:
        return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


def modinv(a, mod):
    return modpow(a, mod - 2, mod)


def cnk(a, b):
    MOD = 10**9+7
    ret = 1
    for i in range(b):
        ret *= (a-i)
        ret %= MOD
        ret = ret * modinv(i+1, MOD) % MOD
    return ret




def main():
    # n = int(input())
    # a = list(map(int, input().split()))
    
    # v = a[0]
    # for i in range(1, n):
    #     v = lcm(v, a[i])
    
    # ans = 0
    # v %= MOD
    # for i in range(n):
    #     ans += v * modinv(a[i], MOD) % MOD
    #     ans %= MOD
    # print(int(ans))
    n = int(input())
    d = defaultdict(int)
    for i in range(1,n+1):
        if i < 10:
            d[(i, i)] += 1
        else:
            d[(int(str(i)[-1]), int(str(i)[0]))] += 1
    
    ans = 0
    for i in range(1, n+1):
        if i < 10:
            ans +=d[(i, i)]
        else:
            if int(str(i)[-1]) == int(str(i)[0]):
                ans += d[(int(str(i)[0]), int(str(i)[-1]))]
            else:
                ans += d[(int(str(i)[0]), int(str(i)[-1]))]
    print(ans)

            


    




    


if __name__ == '__main__':
    main()


Measured memory_bytes: 68312
#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 fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

int dp[1000001];
int pre[1000001];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	string s; cin>>s;
	/*
	set<int> pos;
	for(int i=0;i<n;i++)
	{
		if(s[i]=='1') 
		{
			pos.insert(i);
		}
	}
	int cnt=0;
	set<int> S;
	for(auto it = pos.begin(); it != pos.end(); it++)
	{
		if(next(it)!=pos.end())
		{
			if((*next(it))==(*it)+2)
			{
				S.insert((*it));
			}
		}
	}
	while(!S.empty())
	{
		int u = (*S.begin());
		cerr<<u<<' '<<pos.size()<<'\n';
		cnt++;
		pos.erase(u); pos.erase(u+2);
		S.erase(u);
		if(pos.find(u-2)!=pos.end())
		{
			S.erase(u-2);
		}
		if(pos.find(u+4)!=pos.end())
		{
			S.erase(u+2);
		}
		pos.insert(u+1);
		if(pos.find(u+3)!=pos.end()) S.insert(u+1);
		if(pos.find(u-1)!=pos.end()) S.insert(u-1);
	}
	cout<<cnt<<'\n';
	*/
	for(int i=0;i<n;i++)
	{
		if(s[i]=='0')
		{
			pre[i]=-1;
		}
		else
		{
			if(i>0&&pre[i-1]>=0) pre[i]=pre[i-1];
			else pre[i]=i;
		}
	}
	dp[0] = 0;
	for(int i=1;i<n;i++)
	{
		dp[i]=dp[i-1];
		if(i>=2&&s[i]=='1'&&s[i-2]=='1'&&s[i-1]=='0')
		{
			int z = pre[i-2];
			//take [z,i-2]
			int cost = i - 2 - z + 1;
			if(z-1>=0) cost+=dp[z-1];
			dp[i]=max(dp[i],cost);
			if(z<i-2)
			{
				cost = i - 2 - z;
				if(z>=0) cost += dp[z];
				dp[i] = max(dp[i],cost);
			}
		}
		if(s[i]=='1')
		{
			int z=pre[i];
			if(z>=2&&s[z]=='1'&&s[z-2]=='1'&&s[z-1]=='0')
			{
				//[z, i]
				int cost = i - z + 1;
				if(z>=3) cost += dp[z-3];
				dp[i]=max(dp[i],cost);
			}
		}
		//cerr<<i<<' '<<dp[i]<<'\n';
	}
	cout<<dp[n-1]<<'\n';
}


Measured memory_bytes: 6940
def main():
    N = int(input())
    A = tuple(map(int, input().split()))
    MOD = 10**9 + 7
    MAX_N = 10**5

    count_arr = [0]*(MAX_N+1)
    count_arr[0] = 3

    ans = 1
    for a in A:
        ans *= count_arr[a]
        ans %= MOD

        count_arr[a] -= 1
        count_arr[a+1] += 1

    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 20772
import java.util.*;
public class Main{
	public static HashMap<String,Integer> puzzle;
    public static int[] moves={1,-1,4,-4};
    public static HashMap<String,Integer> solve(){
        Queue<String> q = new ArrayDeque<String>();
        puzzle = new HashMap<String,Integer>();
        puzzle.put("01234567",0);
        q.offer("01234567");
        while(q.size()>0){
            String x=q.poll();
            int z_ind=x.indexOf("0");
            for(int i=0;i<4;i++){
                int z=z_ind+moves[i];
				if((i==1&&(z_ind==0||z_ind==4))||(i==0&&(z_ind==3||z_ind==7))||z<0||z>7){
					continue;
				}
                char[] ch=x.toCharArray();
                char tmp=ch[z_ind];
                ch[z_ind]=ch[z];
                ch[z] = tmp;
                String s = String.valueOf(ch);
                if(puzzle.containsKey(s))continue;
                puzzle.put(s,puzzle.get(x) + 1);
                q.offer(s);
            }
        }
		return puzzle;
	}		
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		HashMap<String,Integer> puzzle=solve();
		while(sc.hasNext()){
			String unsolved="";
			for(int i=0;i<8;i++){
				unsolved+=sc.next();
			}
			System.out.println(puzzle.get(unsolved));
		}
	}
}


Measured memory_bytes: 41816
import sys
readline = sys.stdin.readline

N = int(readline())
S = readline().rstrip()

def zalgo(S):
  N = len(S)
  res = [0] * N
  res[0] = N
  i = 1
  j = 0
  while i < N:
    while i + j < N and S[j] == S[i + j]:
      j += 1
    res[i] = j
    if j == 0:
      i += 1
      continue
    k = 1
    while i + k < N and k + res[k] < j:
      res[i + k] = res[k]
      k += 1
    i += k
    j -= k
  return res

res = 0
for i in range(N):
  T = S[i:]
  lcp = zalgo(T)
  for j in range(len(T)):
    l = min(lcp[j],j)
    if res < l:
      res = l

print(res)

Measured memory_bytes: 49756
#include<stdio.h>
	int gcd( int m, int n )
{
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	while( m != n )
	{
		if ( m > n ) m = m - n;
		else         n = n - m;
	}
	return m;
}
	
	int lcm( int m, int n )
{
	if ( ( 0 == m ) || ( 0 == n ) )
		return 0;
	
	return ((m / gcd(m, n)) * n); 
}

int main(void){
	int m,n;
	int a,b;
	while(scanf("%d",&m)!=EOF){
		scanf("%d",&n);
		a=gcd(m,n);
		b=lcm(m,n);
		printf("%d %d\n",a,b);
	}
	return 0;
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
#define LL long long
#define REP(i,n) for(int i=0;i<(n);++i)
#define PER(i,n) for(int i=n-1;i>=0;--i)
#define REPA(i,n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define PII pair<int,int>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define MOD ((LL)1e9+7) 
#define INF ((int)1e9+7)
#define INFLL ((LL)1e18)
#define ALL(x) (x).begin(),(x).end()
#define BIT(x) (1LL << (x))
using namespace std;

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

LL modpow(LL x, LL b){
	LL res = 1;
	while(b){
		if(b&1)res = res * x % MOD;
		x = x * x % MOD;
		b>>=1;
	}
	return res;
}

LL modinv(LL x){
	return modpow(x, MOD-2);
}


int main(){
	int A, B, Q;
	cin >> A >> B >> Q;
	vector<LL> S(A), T(B);
	foreach(i, S)cin>>i;
	foreach(i, T)cin>>i;
	REP(i, Q){
		LL x;
		cin >> x;
		LL ans = INFLL;
		REP(I, 2){
			vector<LL> &s = (I==0?S:T);
			vector<LL> &t = (I==0?T:S);
			vector<LL> a;
			vector<LL> b;
			int p = lower_bound(ALL(s), x) - s.begin();
			if(p)a.push_back(s[p-1]);
			if(p<s.size())a.push_back(s[p]);
			foreach(j, a){
				p = lower_bound(ALL(t), j) - t.begin();
				if(p)b.push_back(t[p-1]);
				if(p<t.size())b.push_back(t[p]);
			}
			foreach(j, a){
				foreach(k, b){
					chmin(ans, abs(x-j)+abs(j-k));
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 2944
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1000005;
int n,m,a[N],f[N];
int check(int x){
	int num=m;
	for (int i=1;i<=n;i++)
		num-=max(0ll,a[i]-x/f[n-i+1]);
	return num>=0;	
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for (int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for (int i=1;i<=n;i++)scanf("%lld",&f[i]);
	sort(a+1,a+n+1);sort(f+1,f+n+1);
	int l=0,r=1e12;
	while (l<r){
		int mid=(l+r)/2;
		if (check(mid))r=mid;
		else l=mid+1;
	}
	printf("%lld\n",l);
}

Measured memory_bytes: 5888