akhauriyash/Code-Regression huggingface dataset:
import qualified Data.Text.Lazy as T
import qualified Data.Text.Lazy.IO as T
import qualified Data.Text.Lazy.Read as T
import Data.List (unfoldr)

main :: IO ()
main = do
  let
    primeFactors :: Int -> [(Int, Int)]
    primeFactors n = filter ((/= 0) . snd) . unfoldr next $ Just (n, 2, 0)
      where
        next :: Maybe (Int, Int, Int) -> Maybe ((Int, Int), Maybe (Int, Int, Int))
        next (Just (m, d, c)) | m < d     = Just ((d, c), Nothing)
                              | r == 0    = next (Just (m', d, succ c))
                              | m < d * d = Just ((d, c), Just (m, m, 0))
                              | otherwise = Just ((d, c), Just (m, succ d, 0))
          where
            (m', r) = m `divMod` d
        next _                            = Nothing
  [a, b] <- map unsafeTextToInt . T.words <$> T.getLine :: IO [Int]
  let
    x = gcd a b :: Int
  print . (1 +) . length . primeFactors $ x

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n
{-# INLINE unsafeTextToInt #-}


Measured memory_bytes: 4880
import sys


def f(x, y):
    return x - y, x + y


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    x = [0] * n
    y = [0] * n
    for i in range(n):
        x[i], y[i] = map(int, input().split())
    f0 = [0] * n
    f1 = [0] * n
    for i in range(n):
        f0[i], f1[i] = f(x[i], y[i])
    print(max(max(f0) - min(f0), max(f1) - min(f1)))


if __name__ == "__main__":
    main()


Measured memory_bytes: 40632
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
ab=[]
bc=[]
for i in range(n):
    ab.append([a[i],n])
    bc.append([b[i],n])
    ab.append([b[i],i])
    bc.append([c[i],i])
numa=1
numb=1
numc=1
la=[1]*n
lb=[1]*n
lc=[1]*n
for i in range(1,n):
    if a[i-1]!=a[i]:
        la[i]=i+1
        numa=i+1
    else:
        la[i]=numa
    if b[i-1]!=b[i]:
        lb[i]=i+1
        numb=i+1
    else:
        lb[i]=numb
    if c[i-1]!=c[i]:
        lc[i]=i+1
        numc=i+1
    else:
        lc[i]=numc
ab.sort(key=lambda x: x[0])
numab=1
lab=[1]*(n+1)
for i in range(1,n*2):
    if ab[i-1][0]!=ab[i][0]:
        lab[ab[i][1]]=i+1
        numab=i+1
    else:
        lab[ab[i][1]]=numab
ansb=[0]*n
numb=0
for i in range(n):
    numb+=lab[i]-lb[i]
    ansb[i]=numb
bc.sort(key=lambda x: x[0])
numbc=1
lbc=[1]*(n+1)
for i in range(1,n*2):
    if bc[i-1][0]!=bc[i][0]:
        lbc[bc[i][1]]=i+1
        numbc=i+1
    else:
        lbc[bc[i][1]]=numbc
ansc=[0]*n
for i in range(n):
    ansc[i]=lbc[i]-lc[i]
ans=0
for i in range(n):
    if ansc[i]!=0:
        ans+=ansb[ansc[i]-1]
print(ans)


Measured memory_bytes: 88832
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int x = sc.nextInt();
    int a = sc.nextInt();
    int b = sc.nextInt();
    if((a-b)>=0){
      System.out.println("delicious");
    }else if((a-b)<0&&(b-a)<=x){
      System.out.println("safe");
    }else{
      System.out.println("dangerous");
    }
  }
}

Measured memory_bytes: 21844
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
// #define mt make_tuple
//typedef tuple<pii,int,int> tp;
//typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-7;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int main(){
	int n,m,a,b;
	cin>>n>>m>>a>>b;
	if(n+m==2){
		if(a||b)cout<<"NO"<<endl;
		else cout<<"YES"<<endl<<"."<<endl;;
		return 0;
	}
	vs s(n,string(m,'.'));
	if(m%2)rep(i,n/2){
		if(b){
			s[i*2][m-1]='^';
			s[i*2+1][m-1]='v';
			b--;
		}
	}
	if(n%2)rep(i,m/2){
		if(a){
			s[n-1][i*2]='<';
			s[n-1][i*2+1]='>';
			a--;
		}
	}
	rep(i,n/2)rep(j,m/2){
		if(a>=2){
			s[i*2][j*2]='<';
			s[i*2][j*2+1]='>';
			s[i*2+1][j*2]='<';
			s[i*2+1][j*2+1]='>';
			a-=2;
		}else if(b>=2){
			s[i*2][j*2]='^';
			s[i*2+1][j*2]='v';
			s[i*2][j*2+1]='^';
			s[i*2+1][j*2+1]='v';
			b-=2;
		}else if(a){
			s[i*2][j*2]='<';
			s[i*2][j*2+1]='>';
			a--;
		}else if(b){
			s[i*2][j*2]='^';
			s[i*2+1][j*2]='v';
			b--;
		}
	}
	if(a+b==1&&n%2&&m%2){
		if(b){
			if(s[n-1][m-2]!='.'){
				s[n-1][m-1]='>';
				s[n-1][m-2]='<';
			}
			if(s[n-2][m-3]=='.'){
				s[n-1][m-3]='v';
				s[n-2][m-3]='^';
				b--;
			}
		}
	}
	if(a||b)cout<<"NO"<<endl;
	else{
		cout<<"YES"<<endl;
		rep(i,n)cout<<s[i]<<endl;
	}
}








Measured memory_bytes: 2304
from collections import deque
A=deque(input())
B=deque(input())
C=deque(input())
t="a"
for i in range(300):
    if t=="a":
        if len(A)==0:
            print("A")
            exit()
        t=A.popleft()   
    if t=="b":
        if len(B)==0:
            print("B")
            exit()
        t=B.popleft()   
    if t=="c":
        if len(C)==0:
            print("C")
            exit()
        t=C.popleft()      

Measured memory_bytes: 3316
n = int(input()) 
  
# input the array 
arr = [int(x) for x in input().split()] 
ans = 0
if n>=3:
	for i in range(0,n):
		for j in range(i+1,n):
			if arr[i]==arr[j]:
				continue
			for k in range(j+1,n):
				if arr[j]==arr[k] or arr[i]==arr[k]:
					continue
				
				if arr[i]+arr[j]>arr[k] and abs(arr[i]-arr[j])<arr[k]:
					ans+=1

print(ans)


Measured memory_bytes: 9200
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int A = Integer.parseInt(sc.next());
		int B = Integer.parseInt(sc.next());
//		String s = sc.next();

		List<Integer> list = new ArrayList();

		list.add(A+B);
		list.add(A-B);
		list.add(A*B);

		Collections.sort(list);
		Collections.reverse(list);

		System.out.println(list.get(0));


	}

}



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

int a[100];
int dp[100005];
int n, k;

bool find_ans(int K = k){
	if(K < 0){
      return true;
    }else if(dp[K] != -1){
        return dp[K];
    }else{
        for(int i = 0; i < n; ++i){
            bool lost = find_ans(K - a[i]);
            if(!lost){
                dp[K] = 1;
                return dp[K];
            }
        }
        dp[K] = 0;
        return dp[K];
    }
}
  
int main(){
	cin >> n >> k;
	for(int i = 0; i < n; ++i){
      cin >> a[i];
    }
    
    for(int i = 0; i <= k; ++i){
        dp[i] = -1;
    }
  
  	bool ans = find_ans();
  	
  	if(ans){
      cout << "First\n";
    }else{
      cout << "Second\n";
    }
  	return 0;
}

Measured memory_bytes: 7080
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while (true) {
			String str[] = br.readLine().split(" ");
			int M = Integer.parseInt(str[0]);
			int T = Integer.parseInt(str[1]);
			int P = Integer.parseInt(str[2]);
			int R = Integer.parseInt(str[3]);

			if (M == 0 && T == 0 && P == 0 && R == 0)
				break;

			ArrayList<Team> teams = new ArrayList<>();
			for (int i = 0; i < T; i++) {
				teams.add(new Team(i + 1, P));
			}
			for (int i = 0; i < R; i++) {
				str = br.readLine().split(" ");
				int m = Integer.parseInt(str[0]);
				int t = Integer.parseInt(str[1]) - 1;
				int p = Integer.parseInt(str[2]) - 1;
				int j = Integer.parseInt(str[3]);
				teams.get(t).setJudge(m, p, j);
			}
			Collections.sort(teams);
			for (int i = 0; i < T; i++) {
				if (i != 0) {
					if (teams.get(i).answer != teams.get(i - 1).answer || teams.get(i).time != teams.get(i - 1).time) {
						System.out.print("," + teams.get(i).id);
					} else {
						System.out.print("=" + teams.get(i).id);
					}
				} else
					System.out.print(teams.get(i).id);
			}
			System.out.print("\n");
		}
	}
}

class Team implements Comparable<Team> {

	int id;
	int time;
	int answer;
	ArrayList<Integer> incorrect = new ArrayList<>();

	public Team(int id, int p) {
		this.id = id;
		time = 0;
		answer = 0;
		for (int i = 0; i < p; i++) {
			incorrect.add(0);
		}
	}

	public void setJudge(int time, int problem, int judge) {
		if (judge == 0) {
			int sum = time;
			for (int i = 0; i < incorrect.get(problem); i++) {
				sum += 20;
			}
			this.time += sum;
			this.answer++;
		} else
			incorrect.set(problem, incorrect.get(problem) + 1);
	}

	@Override
	public int compareTo(Team arg0) {
		if (this.answer > arg0.answer) {
			return -1;
		} else if (this.answer < arg0.answer) {
			return 1;
		} else {
			if (this.time < arg0.time) {
				return -1;
			} else if (this.time > arg0.time) {
				return 1;
			} else {
				if (this.id > arg0.id) {
					return -1;
				} else {
					return 1;
				}
			}
		}
	}
}



Measured memory_bytes: 36200
Sa = list(input())
Sb = list(input())
Sc = list(input())

turn = 'a'

while True:
    if turn == 'a':
        if Sa == []:
            print('A')
            break
        else:
            turn = Sa[0]
            Sa.pop(0)
    elif turn == 'b':
        if Sb == []:
            print('B')
            break
        else:
            turn = Sb[0]
            Sb.pop(0)
    else:
        if Sc == []:
            print('C')
            break
        else:
            turn = Sc[0]
            Sc.pop(0)


Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

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

using namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	unsigned r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}
map<ll, ll> prime_factor(ll n) {
	map<ll, ll> ret;
	for (ll i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			ret[i]++;
			n /= i;
		}
	}
	if (n != 1) ret[n] = 1;
	return ret;
}

const long long MOD = 1000000007;
//const long long MOD = 998244353;
const long long INF = 1LL << 60;


const int MAX_N = 100010;
const long double PI = 3.14159265359;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	char s; cin >> s;
	cout << (char)(s + 1) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int maxn=100005,maxm=200005;
struct edge { int obj,last; } e[maxm<<1];
int n,m,cnt,point[maxn],Q[maxn],d[maxn],pre[maxn];
bool vis[maxn];
void add_edge(int x,int y)
{
	cnt++;
	e[cnt].obj=y;
	e[cnt].last=point[x];
	point[x]=cnt;
}
void bfs()
{
	Q[1]=1;
	vis[1]=true;
	for (int head=1,tail=1,u;head<=tail;head++)
	{
		u=Q[head];
		for (int i=point[u],v;i;i=e[i].last)
		{
			v=e[i].obj;
			if (vis[v]) continue;
			d[v]=d[u]+1;
			pre[v]=u;
			Q[++tail]=v;
			vis[v]=true;
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1,x,y;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		add_edge(x,y);
		add_edge(y,x);
	}
	bfs();
	bool sol=true;
	for (int i=1;i<=n;i++)
		if (!vis[i])
		{
			sol=false;
			break;
		}
	if (!sol) { puts("No"); return 0; }
	puts("Yes");
	for (int i=2;i<=n;i++) printf("%d\n",pre[i]);
	return 0;
}


Measured memory_bytes: 8476
#include <iostream>

using namespace std;

int w, h;
int c[55][55], ans;

void dfs(int y, int x) {
	c[y][x] = 0;
	for (int i = -1; i <= 1; i++) {
		for (int j = -1; j <= 1; j++) {
			int ny = y + i, nx = x + j;
			if (ny >= 0 && ny < h&&nx >= 0 && nx < w)
				if (c[ny][nx] == 1)
					dfs(ny, nx);
		}
	}
}

int main() {
	while (cin >> w >> h&&w + h) {
		for (int i = 0; i < h; i++)
			for (int j = 0; j < w; j++)
				cin >> c[i][j];
		ans = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (c[i][j] == 1)
					dfs(i, j),ans++;
			}
		}
		cout << ans << endl;
	}
	
}

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

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

    bool ok = true;
    rep(i, S.size()) {
        if (i%2 == 0) {
            if (S[i] == 'L') ok = false;
        }
        else {
            if (S[i] == 'R') ok = false;
        }
    }

    cout << (ok ? "Yes" : "No") << endl;
}


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

double distance(vector<int> a, vector<int> b)
{
    double sum = 0;
    for (auto i = 0; i < a.size(); i++)
    {
        sum += pow(a[i] - b[i], 2);
    }

    sum = sqrt(sum);
    return sum;
}

int main()
{
    int n, d;
    cin >> n >> d;
    vector<vector<int>> points(n);
    int ans=0;
    for (auto i = 0; i < n; i++)
    {
        for (auto j = 0; j < d; j++)
        {
            int x;
            cin >> x;
            points[i].push_back(x);
        }
    }

    for (auto i = 0; i < n; i++)
    {
        for (auto j = i + 1; j < n; j++)
        {
            double dis = distance(points[i], points[j]);
            if(ceil(dis) == floor(dis)){
                ans += 1;
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
from collections import Counter


def inpl():
    return list(map(int, input().split()))


N = int(input())
S = list(input())

cS = Counter(S)

for i in range(10):
    cS[str(i)] = cS.get(str(i), 0)

ans_1 = {}
ans_2 = {}
ans_3 = {}
for s in S:
    for v in ans_2.keys():
        ans_3[v + s] = True
    for v in ans_1.keys():
        ans_2[v + s] = True
    ans_1[s] = True

print(len(ans_3))


Measured memory_bytes: 3700
n=int(input())
a=[int(x) for x in input().split()]
b=[int(x) for x in input().split()]
c=[int(x) for x in input().split()]
sum1=0
for i in range(n):
	sum1+=b[a[i]-1]
	if(i!=n-1):
		if(a[i+1]-a[i]==1):
			sum1+=c[a[i]-1]
print(sum1)
      

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

int main() {

    int k, cnt1 = 0, cnt2 = 0;
    cin >> k;
    string s;
    cin >> s;
    for(int i=0; i<k; i++)
        if(s[i] == 'R') cnt1++;
    if(cnt1 == k) cout << 0;
    else{
    for(int i=0; i<cnt1; i++)
        if(s[i] == 'R') cnt2++;

    cout << cnt1 - cnt2;}

}


Measured memory_bytes: 3720
W, H, x, y, r = map(int, input().split())
bool1 = False
if(x - r >= 0):
    if(y - r >= 0):
        if(x + r <= W):
            if(y + r <= H):
                bool1 = True
if(bool1 == True):
    print("Yes")
else:
    print("No")



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

using namespace std;


int main() {
    int n,m; cin >> n >> m;
    vector<int> p(m);
    vector<string> s(m);
    vector<int> a(n,0);
    vector<bool> b(n,false);

    long ac = 0;
    long wa = 0;
    for(int i=0; i<m; i++){
        cin >> p[i] >> s[i];
        p[i]--;
        if(!b[p[i]]){
            if(s[i] == "AC"){
                b[p[i]] = true;
            }else{
                a[p[i]]++;
            }
        }
    }
    for(int i=0; i<n; i++){
        if(b[i]){
            ac++;
            wa += a[i];
        }
    }
    // long ac = 0;
    // long wa = 0;
    // for(int i=0; i<m; i++){
    //     cin >> p[i] >> s[i];
    //     p[i]--;

    //     if(s[i] == "AC" && a[p[i]] == 0){
    //         a[p[i]]++;
    //         ac++;
    //     }
    //     if(s[i] == "WA" && a[p[i]] == 0){
    //         wa++;
    //     }
    // }
    cout << ac << " " << wa << endl;



}

Measured memory_bytes: 7200
import java.util.Scanner;

public class Main {
    int h, w, d;
    Pair[] as;
    int q;
    int[] rs, ls;

    public static void main(String[] args) {
        Main m = new Main();
        m.read();
        m.solve();
    }

    private void read() {
        Scanner sc = new Scanner(System.in);
        h = sc.nextInt();
        w = sc.nextInt();
        d = sc.nextInt();
        as = new Pair[h*w + 1];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                int a = sc.nextInt();
                as[a] = new Pair(i+1, j+1);
            }
        }
        q = sc.nextInt();
        rs = new int[q]; ls = new int[q];
        for (int i = 0; i < q; i++) {
            ls[i] = sc.nextInt();
            rs[i] = sc.nextInt();
        }
    }

    private void solve() {
        int[] acc = new int[h * w + 1];
        for (int i = 1; i <= d; i++) {
            acc[i] = 0;
            for (int j = i + d; j <= h * w; j += d) {
                acc[j] = acc[j-d] + as[j].dst(as[j-d]);
            }
        }
        for (int i = 0; i < q; i++) {
            System.out.println(acc[rs[i]] - acc[ls[i]]);
        }
    }

    private class Pair {
        int fst, snd;
        Pair (int fst, int snd) {
            this.fst = fst;
            this.snd = snd;
        }

        int dst(Pair p) {
            int a = Math.abs(fst - p.fst);
            int b = Math.abs(snd - p.snd);
            return a + b;
        }
    }
}


Measured memory_bytes: 98008
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
//#########################################
int calc(int s,int g,int num){
    return (s+g)*num/2;
}
signed main(){
    int n;cin >> n;
    int ret = 0;
    for(int l = 1;l <= n;l++){
        ret += calc(1,n-l+1,n-l+1);
    }
    rep(i,n-1){
        int a,b;cin >> a >> b;
        --a;--b;
        if(a > b)swap(a,b);
        ret -= (a+1)*(n-b);
    }
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 3592
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = (ll)1e9;
const ll mod = (ll)1e9 + 7;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

#define print(s) cout << s;
#define println(s) cout << s << endl;
#define printd(s, f) cout << fixed << setprecision(f) << s << endl;


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

	vector<int> c(30);
	for (int i = 0; i < s.length(); i++)
	{
		c.at(s.at(i) - 'a') ++;
	}

	for (int i = 0; i < 26; i++)
	{
		if (c.at(i) == 0)
		{
			println((char)('a' + i));
			return 0;
		}
	}

	println("None");
}


Measured memory_bytes: 512
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

static long gcd(long a, long b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

long long int facctorialMethod(int k){//階乗
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

long long int tousasum(long long int n){//等差数列
    return n*(n+1)/2;
}

unsigned GetDigit(unsigned num){//桁数
    unsigned digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}

bool IsPrime(int num)//素数判定
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}

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

int main() {

    long long int A,B;
    cin >> A;
    cin >> B;
    long long int N=gcd(A,B);
    long result = 1;
    for(auto p : prime_factor(N)) {
        long before = 0;
        while(p.second--){
            if(before!=p.first){
                before = p.first;
                result++;
            }
        }
    }
    cout << result << endl;
}








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

using namespace std;

#define int long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define INF ((long long)1e18)
#define MOD ((int)1e9+7)
#define endl "\n"

#define yn(f) ((f)?"Yes":"No")
#define YN(f) ((f)?"YES":"NO")

#define MAX

string JAG(string str){
	string res;
	pair<int,string> hoge = {};
	stack<pair<int,string>> sta;
	int num = 0;
	
	sta.push(hoge);
	
	for(int i = 0; i < str.size(); i++){
		if(str[i] == '?'){
			num = 0;
			str[i] = 'A';
		}
		if(str[i] == '-') num--;
		else if(str[i] == '+') num++;
		else if('A' <= str[i] && str[i] <= 'Z'){
			int temp = str[i]-'A';
			num += 26*100;
			temp = (26+temp+num)%26;
			pair<int,string> fuga;
			fuga = sta.top(); sta.pop();
			fuga.second += (char)('A'+temp);
			sta.push(fuga);
			
			num = 0;
		} else if(str[i] == '['){
			sta.push(hoge);
		} else if(str[i] == ']'){
			pair<int,string> fuga, fuga2;
			fuga = sta.top(); sta.pop();
			fuga2 =  sta.top(); sta.pop();
			reverse(fuga.second.begin(), fuga.second.end());
			fuga2.second += fuga.second;
			sta.push(fuga2);
		}
	}
	hoge = sta.top();
	return hoge.second;
}

string solve(string str){

	return  JAG(str);
}
signed main(){
	// cin.tie(0);
	// ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	
	while(true){
		string s;
		
		cin>>s;
		
		if(s == ".") break;
		
		cout<<solve(s)<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 3044
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>

typedef unsigned long long ULLONG;
typedef long long LLONG;
static const LLONG MOD_NUM = 1000000007;//998244353;

template<class _T> static void get(_T& a) {
	std::cin >> a;
}
template<class _T> static void get(_T& a, _T& b) {
	std::cin >> a >> b;
}
template<class _T> static void get(_T& a, _T& b, _T& c) {
	std::cin >> a >> b >> c;
}
template<class _T> static void getint(_T& a) {
	if (sizeof(_T) > sizeof(int)) {
		scanf("%lld", &a);
	}
	else {
		scanf("%d", &a);
	}
}
template <class _T> static _T tp_abs(_T a) {
	if (a < (_T)0) {
		a *= (_T)-1;
	}
	return a;
}

static void exec();

int main()
{
	exec();
	fflush(stdout);
	return 0;
}

static void exec()
{
	int N;
	get(N);

	LLONG surp = 0, ans = 0;
	std::vector<LLONG> ai(N, 0);
	for (int i = 0; i < N; i++) {
		get(ai[i]);
		if (surp && ai[i]) {
			ans++;
			ai[i]--;
		}
		ans += ai[i] / 2LL;
		surp = ai[i] % 2LL;
	}
	printf("%lld\n", ans);
}


Measured memory_bytes: 4044
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**6)
input=lambda: sys.stdin.readline().rstrip()

show_flg=False
show_flg=True

n,m=LI()

#####min######
#def min(x,y):
#    return 

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=min(seg[2*i+1],seg[2*i+2]) 

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = min(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = min(res,seg[p])
        if q&1 == 1:
            res = min(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,seg[p])
    else:
        res = min(min(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = inf

ans=inf

s=[int(i) for i in input()]

def dp(b,m): # N log (N)
    N=len(b)-1
    n=N+1
    global seg
    global num
    
    #num:n以上の最小の2のべき乗
    num =2**(n-1).bit_length()
    seg=[ide_ele]*2*num
    init([inf]*n)
    
    update(0,0)

    dp=[0]+[inf]*(N)
    for i in range(N):
        if b[i+1]==1:
            continue
        dp[i+1]=query(max(i-m+1,0),i+1)+1
        update(i+1,dp[i+1])
        #show(seg)
        #show(dp)
    return dp

dp1=dp(s,m)
step=dp1[n]
if step==inf:
    print(-1)
    exit()

dp2=dp(s[::-1],m)[::-1]

move=[0]
ans=[]
j=1
for i in range(step,0,-1): # N
    while j<=n and dp2[j]!=i-1:
        j+=1
    #ans.append(j-move[-1])
    move.append(j)

# 2 * N log N + N
'''
show(s)
show(dp1,step)
show(dp2)
show(move)
'''

for i in range(len(move)-1):
    ans.append(move[i+1]-move[i])
print(*ans)



Measured memory_bytes: 101592
#include<stdio.h>

int main(void){
    int n,x;
    long min=1000000,max=-1000000,sum=0;

    scanf("%d",&n);

    while(n>0){
        scanf("%d",&x);
        if(x<min) min=x;
        if(x>max) max=x;
        sum+=x;
        n--;
    }
    printf("%ld %ld %ld\n",min,max,sum);

    return 0;
}


Measured memory_bytes: 2104
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define all(x) (x).begin(), (x).end()
#define INF 1000000007
#define mod 1005
#define ll long long int
const double mx = 2e6 + 5 ;

void solve()
{
	int n;
	cin>>n;
	int cnt = 0;
	vector<int> vect(n+1);
	for(int i=1; i<=n; i++)
		cin>>vect[i];
	for(int i=2; i<n; i++)
	{
		if(vect[i]>vect[i-1] && vect[i]<vect[i+1])
			cnt++;
		if(vect[i]>vect[i+1] && vect[i]<vect[i-1])
			cnt++;
	}
	cout<<cnt<<"\n";
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t = 1;
//	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;

int main(){
ll a;
ll sum=0;
cin >> a;
for( ll i = 1 ; i <=a ; i++){
  if(i%3!=0 && i%5!=0){
 sum+=i;
}
}
cout << sum << endl;
}


Measured memory_bytes: 3628
#include "bits/stdc++.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
/*----------------------------------------------------------------*/

// int MOD = 998244353;
int MOD = 1000000007;

int w,h;
int c[51][51];
int dx[8] = {-1,0,1,-1,1,-1,0,1};
int dy[8] = {-1,-1,-1,0,0,1,1,1};
bool isin(int x,int y){
    if(x < h && 0 <= x && y < w && 0 <= y)return true;
    else return false;
}
void dfs(int x,int y){
    c[x][y] = 2;
    rep(i,8)if(isin(x+dx[i],y+dy[i]) && c[x+dx[i]][y+dy[i]] == 1)dfs(x+dx[i],y+dy[i]);
}

/*----------------------------------------------------------------*/
signed main(){

    while(1){
        cin >> w >> h;
        if(w == 0)break;
        int cnt = 0;
        rep(i,h)rep(j,w)cin >> c[i][j];
        rep(i,h)rep(j,w){
            if(c[i][j] == 1){
                cnt++;
                dfs(i,j);
            }
        }
        // rep(i,h){
        //     rep(j,w){
        //         cerr << c[i][j] << " ";
        //     }
        //     cerr << endl;
        // }
        cout << cnt << endl;
    }
  
	return 0;
}
/*----------------------------------------------------------------*/

// g++ -std=c++14 code1.cpp
// sudo pip3 install --upgrade online-judge-tools
// rm -r -f test;oj dl https://code-festival-2018-quala.contest.atcoder.jp/tasks/code_festival_2018_quala_c
// rm -r -f test;oj dl https://pakencamp-2019-day3.contest.atcoder.jp/tasks/pakencamp_2019_day3_c
// rm -r -f test;oj dl https://arc054.contest.atcoder.jp/tasks/arc054_b


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

int main(){
    int n;cin>>n;
    vector<int> pri;
    int tmp=n;
    for(int i=2;i*i<=tmp;i++){
        if(tmp%i==0){
            pri.push_back(i);
            while(tmp%i==0)tmp/=i;
        }
    }
    if(tmp>1)pri.push_back(tmp);
    int K=pri.size();
    int ans=0;
    for(int bit=0;bit<(1<<K);bit++){
        int a=1,cnt=0;
        for(int i=0;i<K;i++){
            if((bit>>i)&1){
                cnt++;
                a*=pri[i];
            }
        }
        if(cnt&1)ans-=n/a;
        else ans+=n/a;
    }
    cout<<ans<<endl;
}



Measured memory_bytes: 3156
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
#include <bitset>
#include <numeric>
#include <cassert>
#include <random>
using namespace std;
using ll = long long;


// Modint
struct Mint {
	static const ll mod = (ll)(1e9 + 7);
	ll val;

	Mint() { val = 0; }
	Mint(ll a) { val = a; verify_value(); }

	void verify_value() {
		if (val >= mod) val %= mod;
		if (val < 0) val %= mod, val += mod;
	}

	Mint pow(ll p) const {
		Mint cur = Mint(val), ret = 1;
		while (p > 0) {
			if (p & 1) ret *= cur;
			cur *= cur;
			p >>= 1LL;
		}
		return ret;
	}
	Mint inv() const {
		if (val == 0) cerr << "WARNING: inv() is called with 0." << endl;
		return pow(mod - 2);
	}

	Mint operator+() const { return *this; }
	Mint operator-() const { return Mint(mod - val); }

	Mint operator+=(const Mint &a) {
		val += a.val;
		if (val >= mod) val -= mod;
		return Mint(val);
	}
	Mint operator*=(const Mint &a) {
		val *= a.val;
		if (val >= mod) val %= mod;
		return Mint(val);
	}
	Mint operator-=(const Mint &a) { return *this += -a; }
	Mint operator/=(const Mint &a) { return *this *= a.inv(); }

	Mint operator++() { return *this += Mint(1); }
	Mint operator--() { return *this -= Mint(1); }
	Mint operator++(int) {
		Mint ret = *this;
		++(*this);
		return ret;
	}
	Mint operator--(int) {
		Mint ret = *this;
		--(*this);
		return ret;
	}

	operator ll() const { return val; }
};

Mint operator+(const Mint &a, const Mint &b) {
	ll ret = a.val + b.val;
	if (ret >= Mint::mod) ret -= Mint::mod;
	return Mint(ret);
}
Mint operator*(const Mint &a, const Mint &b) {
	ll ret = a.val * b.val;
	if (ret >= Mint::mod) ret %= Mint::mod;
	return Mint(ret);
}
Mint operator-(const Mint &a, const Mint &b) { return a + (-b); }
Mint operator/(const Mint &a, const Mint &b) { return a * b.inv(); }

ostream &operator<<(ostream &out, const Mint &a) { return out << a.val; }
istream &operator>>(istream &in, Mint &a) {
	in >> a.val;
	a.verify_value();
	return in;
}

Mint pow(Mint a, ll b) {
	return a.pow(b);
}

int n;
vector<vector<int>> edg;
vector<int> cnt;
vector<vector<Mint>> ev;

int func(int pos, int prev = -1) {
	int ret = 1;
	for (int e : edg[pos]) {
		if (e == prev) continue;
		ret += func(e, pos);
	}
	return cnt[pos] = ret;
}

void func2(int pos, int prev = -1) {
	for (int i = 0; i < (int)edg[pos].size(); i++) {
		int e = edg[pos][i];
		if (e == prev) continue;
		ev[pos][i] = Mint(1) - pow(Mint(1)/Mint(2), (ll)cnt[e]);
		ev[pos][i] *= Mint(1) - pow(Mint(1)/Mint(2), (ll)(n - cnt[e]));
		func2(e, pos);
	}
}

int main() {
	cin >> n;
	edg.resize(n);
	for (int i = 0; i < n - 1; i++) {
		int a, b; cin >> a >> b;
		a--; b--;
		edg[a].push_back(b);
		edg[b].push_back(a);
	}
	cnt.resize(n);
	func(0);
	ev.resize(n);
	for (int i = 0; i < n; i++) {
		ev[i].resize(edg[i].size());
	}
	func2(0);
	Mint ans = Mint(1) - pow(Mint(1)/Mint(2), (ll)n) - Mint(n) / Mint(2);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < (int)edg[i].size(); j++) {
			ans += ev[i][j];
		}
	}
	cout << ans << endl;
	return 0;
}


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


int main(){
	char a,b,c,d;
	cin >> a >> b >> c >> d;
	
	int A,B,C,D;
	A = a - '0';
	B = b - '0';
	C = c - '0';
	D = d - '0';
	
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++){
				int b_,c_,d_;
				if(i == 0){
					b_ = B;
				}else{
					b_ = -B;
				}
				if(j == 0){
					c_ = C;
				}else{
					c_ = -C;
				}
				if(k == 0){
					d_ = D;
				}else{
					d_ = -D;
				}
				if(A + b_ + c_ + d_ == 7){
					cout << a;
					if(i == 0){
						cout << "+";
					}else{
						cout << "-";
					}
					cout << B;
					if(j == 0){
						cout << "+";
					}else{
						cout << "-";
					}
					cout << C;
					if(k == 0){
						cout << "+";
					}else{
						cout << "-";
					}
					cout << D;
					cout << "=7" << endl;
					return 0;
					
				}
				
				
			}
		}
	}
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
 public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();

        int result = 0;

        for(int i = 1 ; i <= n; i++){
            int sum = findSumOfDigits(i);
            if(sum >= a && sum <= b){
                result += i;
            }
        }

        System.out.println(result);
    }

    public static int findSumOfDigits(int n){
        int sum = 0;
        while (n > 0){
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }
}

Measured memory_bytes: 23764
N,L=map(int,input().split())
Aji=[0]*N
Sum=0
AjiMin=10**9
EatApple=0
for i in range(N):
  if i==0:
    Aji[i]=L
  else:
    Aji[i]=Aji[i-1]+1
  Sum+=Aji[i]
  AbsVal=abs(Aji[i])
  if AbsVal<AjiMin:
    AjiMin=AbsVal
    EatApple=Aji[i]
print(Sum-EatApple)

Measured memory_bytes: 3064
#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;

int main() {
  for(int tci = 0; ; tci++) {
    int m; scanf("%d", &m);
    if(m==0) break;
    int n = 0;
    int tbl[10][10];
    for(int i = 0; i < 10; i++)
      for(int j = 0; j < 10; j++)
        tbl[i][j] = i==j ? 0 : INT_MAX/2;
    for(int i = 0; i < m; i++) {
      int a,b,c; scanf("%d%d%d", &a, &b, &c);
      tbl[a][b] = tbl[b][a] = min(tbl[b][a],c);
      n = max(n,max(a+1,b+1));
    }
    for(int k = 0; k < n; k++)
      for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
          tbl[i][j] = min(tbl[i][j], tbl[i][k]+tbl[k][j]);
    pair<int,int> result(INT_MAX,INT_MAX);
    for(int i = 0; i < n; i++) {
      int sum = 0;
      for(int j = 0; j < n; j++) {
        sum += tbl[i][j];
      }
      result = min(result,make_pair(sum,i));
    }
    printf("%d %d\n", result.second, result.first);
  }
  return 0;
}

Measured memory_bytes: 0
#define _USE_NATH_DEFINES
#include<cstdio>
#include <iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include <string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#include <random>

using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
#define EPS 1e-9
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const int MINF = -1e9;;


int main() {
	int n;
	cin >> n;
	vector<int> h;
	h.resize(n);
	rep(i, n) cin >> h[i];
	
	h[0]--;
	rep(i, n - 1) {
		if (h[i] > h[i + 1]) {
			cout << "No" << endl;
			return 0;
		}
		if (h[i] < h[i + 1]) --h[i + 1];
	}

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

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

#ifdef _DEBUG
#define debug(x) cerr << "line: " << __LINE__ << ", func: " << __func__ << " ->  " << #x << " = " << x << endl
#else
#define debug(x)
#endif

#define all(s) begin(s), end(s)
#define rall(s) rbegin(s), rend(s)
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = ((a)-1); i >= (b); i--)
#define pb push_back
#define sz(a) int((a).size())
#define put(a) ((cout) << (a) << (endl))
#define putf(a, n) ((cout) << (fixed) << (setprecision(n)) << (a) << (endl))
#define deg2rad(x) (((x)*PI) / (180.0))
#define rad2deg(x) (((x) * (180.0)) / PI)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i_i = pair<int, int>;
using ll_ll = pair<ll, ll>;
using d_ll = pair<double, ll>;
using ll_d = pair<ll, double>;
using d_d = pair<double, double>;
template <class T> using vec = vector<T>;

static constexpr ll LL_INF = 1LL << 60;
static constexpr int I_INF = 1 << 28;
static constexpr double PI = static_cast<double>(3.14159265358979323846264338327950288);
static constexpr double EPS = numeric_limits<double>::epsilon();

static map<type_index, const char* const> scanType = {
    {typeid(int), "%d"}, {typeid(ll), "%lld"}, {typeid(double), "%lf"}, {typeid(char), "%c"}};

template <class T> static void scan(vector<T>& v);
[[maybe_unused]] static void scan(vector<string>& v, bool isWord = true);
template <class T> static inline bool chmax(T& a, T b);
template <class T> static inline bool chmin(T& a, T b);
template <class T> static inline T gcd(T a, T b);
template <class T> static inline T lcm(T a, T b);
template <class A, size_t N, class T> static void Fill(A (&arr)[N], const T& val);
template <class T> T mod(T a, T m);

int main(int argc, char* argv[]) {
  long long N;
  scanf("%lld", &N);
  std::vector<long long> a(N);
  map<ll, ll> m;
  for (int i = 0; i < N; i++) {
    scanf("%lld", &a[i]);
    m[a[i]]++;
  }

  ll ans = 0;
  rep(i, 0, 100000) {
    ll count = m[i] + m[i - 1] + m[i + 1];
    chmax(ans, count);
  }
  put(ans);
  return 0;
}

template <class T> static void scan(vector<T>& v) {
  auto tFormat = scanType[typeid(T)];
  for (T& n : v) {
    scanf(tFormat, &n);
  }
}

static void scan(vector<string>& v, bool isWord) {
  if (isWord) {
    for (auto& n : v) {
      cin >> n;
    }
    return;
  }

  int i = 0, size = v.size();
  string s;
  getline(cin, s);

  if (s.size() != 0) {
    i++;
    v[0] = s;
  }

  for (; i < size; ++i) {
    getline(cin, v[i]);
  }
}

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

template <class T> inline T gcd(T a, T b) { return __gcd(a, b); }

template <class T> inline T lcm(T a, T b) { return (a * b) / gcd(a, b); }

template <class A, size_t N, class T> void Fill(A (&arr)[N], const T& val) {
  std::fill((T*)arr, (T*)(arr + N), val);
}

template <class T> T mod(T a, T m) { return (a % m + m) % m; }


Measured memory_bytes: 7296
#include <bits/stdc++.h>
#define repl(i, l, r) for (int i = l; i < r; ++i)
#define rep(i, n) repl(i, 0, n)
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using G = vector<vector<int>>;
const int MOD = 998244353;
const int INF = 1001001001;
const ll LINF = 1001001001001001001;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, -1, 0, 1};

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

int main()
{
    int n, h;
    cin >> n >> h;
    vector<int> a(n), b(n);
    rep(i, n) {
        cin >> a[i] >> b[i];
    }
    sort(rall(a));
    sort(rall(b));
    int ma = a[0];
    int ans = INF;
    rep(k, n + 1) {
        if(k > 0) {
            h -= b[k-1];
        }
        int cnt = 0;
        if(h > 0) {
            cnt = (h + ma - 1) / ma;
        }
        ans = min(ans, k + cnt);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4016
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define rep(i,s,f) for(i=s;i<f;i++)
#define print(v) for(auto &z:v) cout<<z<<' ';cout<<'\n'
#define hi cout<<'h'<<'i'<<'\n' 
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define B begin()
#define E end()
#define all(v) v.B,v.E
#define sz(v) (int)((v).size())
#define vi vector<int>
#define vii vector<pair<int,int>>
#define boost ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define clk1 clock_t start_time=clock()
#define clk2 cout<<(clock()-start_time)/(double)CLOCKS_PER_SEC
#define clean(arr) memset(arr,0,sizeof(arr))
#define mod 1000000007
#define mod2 998244353
#define space 100005
//<<fixed << setprecision(9)

int main()
{
    int n,i,j,t;
    boost;
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    i=0;
    while(a>0 && c>0)
    {
        if(i==0)
        {   
            c-=b;
        }
        else
        {
            a-=d;
        }
        i^=1;
    }
    if(a>0)cout<<"Yes";
    else cout<<"No";
    return 0;
}



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

int n;

bool checkPal(string s, int st, int en) {
    for (int i=st; i<=en; ++i) {
        if (s[i]!=s[en-i+1]) {
            return 0;
        }
    }

    return 1;
}

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

    string s;
    cin >> s;
    n=s.size();
    s.insert(0, 1, '*');

    if (!checkPal(s, 1, n)) {
        cout << "No";
        return 0;
    }

    if (!checkPal(s, 1, (n-1)/2)) {
        cout << "No";
        return 0;
    }

    if (!checkPal(s, (n+3)/2, n)) {
        cout << "No";
        return 0;
    }

    cout << "Yes";

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main () {
  long N;
  cin >> N;
  vector<pair<long, long>> data(N);
  int a;
  for(int i = 0; i < N; i++){
    cin >> a;
    if(i - a >= 0){
      data.at(i - a).first++;
    }
    if(i + a <= N - 1)data.at(i + a).second++;
  }
  long ans = 0;
  for(int i = 0;i < N; i++){
    ans += data.at(i).first * (data.at(i).second);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 6304
def main():
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    def f(n, c, d):
        return n // c + n // d - n // (c * d // gcd(c, d))
    a, b, c, d = map(int, input().split())
    # print(b - a + 1)
    # print(f(b, c, d))
    # print(f(a - 1, c, d))
    print(b - a + 1 -  f(b, c, d) + f(a - 1, c, d))
    return 0

main()

Measured memory_bytes: 3060
#include<stdio.h>
int main(){
    int x,y,i,j;
    int group1[7]={1,3,5,7,8,10,12};
    int group2[4]={4,6,9,11};
    scanf("%d%d",&x,&y);
    if(x==y){
        printf("Yes\n");
        return 0;
    }
    else if(x==2||y==2){
        printf("No\n");
        return 0;
    }
    else {
        for(i=0;i<7;i++){
            if(group1[i]==x){
                for(j=0;j<7;j++){
                    if(group1[j]==y){
                        printf("Yes\n");
                        return 0;
                    }
                }
                if(j>=7){
                    printf("No\n");
                    return 0;
                }
            }
        }
        for(i=0;i<4;i++){
            if(group2[i]==x){
                for(j=0;j<4;j++){
                    if(group2[j]==y){
                        printf("Yes\n");
                        return 0;
                    }
                }
                if(j>=4){
                    printf("No\n");
                    return 0;
                }
            }
        }
    }
   return 0;
}


Measured memory_bytes: 128