akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    static void Main(string[] args)
    {
        int n = Scanner.NextInt();
        Queue<int> q = new Queue<int>();
        while (n != 0)
        {
            q.Enqueue(Solve(n));
            n = Scanner.NextInt();
        }
        while (q.Count != 0)
            Console.WriteLine(q.Dequeue());
        int i = 0;
        i++;
    }

    static int Solve(int n)
    {
        int[] arr = new int[n];
        int sum = 0;
        for (int i = 0; i < arr.Length; i++)
        {
            arr[i] = Scanner.NextInt();
        }
        Array.Sort(arr);
        for (int i = 1; i < arr.Length - 1; i++)
        {
            sum += arr[i];
        }
        return sum / (n - 2);
    }

}

    
public static class Scanner
{
    public static string[] NextStrArray()
    {
        return Console.ReadLine().Split(' ');
    }

    public static long[] NextLongArray()
    {
        string[] s = NextStrArray();
        long[] a = new long[s.Length];
        for (int i = 0; i < a.Length; i++)
        {
            a[i] = long.Parse(s[i]);
        }
        return a;
    }
    public static int[] NextIntArray()
    {

        string[] s = NextStrArray();
        int[] a = new int[s.Length];
        for (int i = 0; i < a.Length; i++)
        {
            a[i] = int.Parse(s[i]);
        }
        return a;
    }
    public static int NextInt()
    {
        string tmp = "";
        while (true)
        {
            string readData = char.ConvertFromUtf32(Console.Read());
            if (readData == " " || readData == "\n")
                break;
        
            tmp += readData;
        }
        return int.Parse(tmp);
    }
    public static double NextDouble()
    {
        string tmp = "";
        while (true)
        {
            string readData = char.ConvertFromUtf32(Console.Read());
            if (readData == " " || readData == "\n")
                break;
            tmp += readData;
        }
        return double.Parse(tmp);
    }
    public static long NextLong()
    {
        string tmp = "";
        while (true)
        {
            string readData = char.ConvertFromUtf32(Console.Read());
            if (readData == " " || readData == "\n")
                break;
            tmp += readData;
        }
        return long.Parse(tmp);
    }
    public static double[] NextDoubleArray()
    {

        string[] s = NextStrArray();
        double[] a = new double[s.Length];
        for (int i = 0; i < a.Length; i++)
        {
            a[i] = double.Parse(s[i]);
        }
        return a;
    }
}

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

int main() {
	int a, b, c, d, x, y;
	cin >> a >> b >> c >> d;
	x = a + b;
	y = c + d;
	if (x > y) {
		cout << "Left" << endl;
	}
	else if (x < y) {
		cout << "Right" << endl;
	}
	else {
		cout << "Balanced" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

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

	public static void main(String[] args) throws Exception {
		boolean[] used = new boolean[26];
		System.out.println("?a");
		System.out.flush();
		while (true) {
			String input = sc.next();
			if (input.charAt(0) != 'a' || input.equals("a") || used[input.charAt(1) - 'a']) {
				System.out.println("!OUT");
				return;
			}
			used[input.charAt(1) - 'a'] = true;
			if (input.equals("aa")) {
				System.out.println("?aaa");
			} else {
				System.out.println("?" + input.charAt(1) + "a");
			}
			System.out.flush();
		}
	}
}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
//const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

ll n,mod;
vvi g;
vl dp,DP;

void dfs(int v,int p){
	dp[v]=1;
	for(auto u:g[v]) if(u!=p){
		dfs(u,v);
		(dp[v]*=dp[u]+1)%=mod;
	}
}

void DFS(int v,int p,ll t){
	vl a;
	DP[v]=t;
	for(auto u:g[v]) if(u!=p){
		a.push_back((dp[u]+1)%mod);
		(DP[v]*=dp[u]+1)%=mod;
	}
	ll N=a.size(),I=0;
	if(!N) return;
	vl b(N);
	b[N-1]=1;
	for(int i=N-2;i>=0;i--) b[i]=b[i+1]*a[i+1]%mod;
	for(auto u:g[v]) if(u!=p){
		DFS(u,v,(t*b[I]+1)%mod);
		(t*=a[I++])%=mod;
	}
}

int main(){
	cin>>n>>mod;
	g=vvi(n);
	dp=DP=vl(n);
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		u--;v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(0,-1);
	DFS(0,-1,1);
	for(auto i:DP) cout<<i<<endl;
}

Measured memory_bytes: 22912
#include <bits/stdc++.h>
using namespace std;
#define AB_BHI_NI_DEGI                \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define int long long
#define pb push_back
#define N 100009
#define inf 1e18
const double PI = 3.141592653589793238462643383279;
int mod = 1e9 + 7;
//int mod = 998244353;
#define P pair<int, int>
#define F first
#define S second
#define all(v) v.begin(), v.end()
#define vi vector<int>
#define ld long double

int power(int a, int n, int m)
{
    int res = 1;
    while (n)
    {
        if (n & 1)
            res = (res * a) % m;
        n = n / 2;
        a = (a * a) % m;
    }
    return res;
}

bool fun(string s, int n)
{
    int res = 0;
    int po = 1;
    while (s.size())
    {
        int x = s.back() - '0';
        s.pop_back();
        x *= po;
        res += (x) % n;
        res %= n;
        po = (po * 10) % n;
    }
    //cout << res << "\n";
    return (res % n);
}

int n, k;
int a[2 * N];

bool fun(int mid)
{
    int cnt = 0;
    for (int i = 0; i < n; i++)
    {
        if (a[i] % mid)
            cnt += (a[i] / mid);
        else
            cnt += max(0LL, (a[i] / mid) - 1);
    }
    return cnt <= k;
}

void solve()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int ans = -1;
    int l = 1, r = 1e9 + 10;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (fun(mid))
        {
            r = mid - 1;
            ans = mid;
        }
        else
            l = mid + 1;
    }
    cout << ans << "\n";
}
int32_t main()
{
    AB_BHI_NI_DEGI
    int Test = 1;
    //cin >> Test;
    while (Test--)
        solve();
    return 0;
}

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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define REP(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) std::cout << x << '\n'
#define all(a) a.begin(), a.end()
#define pb push_back
#define sz(x) ((int)(x).size())
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a / g * b; }
const int dx[4] = { 1, 0, -1,  0 };
const int dy[4] = { 0, 1,  0, -1 };
const int INF = (int)1e9;
const ll  inf = (ll)1e18;
const int mod = 1000000007;
const int MAX_N = 100010;

int H, W;
char A[10][10];

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

	cin >> H >> W;

	int s = 0;
	rep(i, H) {
		rep(j, W) {
			cin >> A[i][j];
			if (A[i][j] == '#') {
				s++;
			}
		}
	}

	if (s == H + W - 1) {
		cout << "Possible" << endl;
	}
	else {
		cout << "Impossible" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MXN = 55555;
bool Seive[MXN];
queue<int64_t> Primes;

void initSeive(int64_t N)
{
  for (int i = 0; i <= N; i++)
    Seive[i] = true;
}

bool isPrime(int64_t x)
{
  return Seive[x];
}

void makeSeive(int64_t N)
{
  initSeive(N);
  Seive[0] = Seive[1] = false;
  for (int64_t i = 2; i <= N; i++)
  {
    if (!isPrime(i))
      continue;
    Primes.emplace(i);
    for (int64_t j = 2; i * j <= N; j++)
    {
      Seive[i * j] = false;
    }
  }
}

int main()
{
  int N;
  cin >> N;
  makeSeive(MXN);
  vector<int64_t> A;
  while (A.size() < N)
  {
    if (Primes.front() % 5 == 1)
    {
      A.push_back(Primes.front());
    }
    Primes.pop();
  }
  for (int i = 0; i < A.size(); i++)
  {
    cout << A.at(i);
    if (i != A.size() - 1)
      cout << ' ';
  }
  cout << endl;
}

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

int main(){
    int n;
    cin >> n;
    int mini = 1000000000;
    int maxa = 0;
    for(int i = 0; i < n; i++) {
        int a; cin >> a;
        mini = min(mini,a);
        maxa = max(maxa,a);
    }
    cout << maxa - mini << endl;
}


Measured memory_bytes: 256
#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

for hoge in range(1, 100):
    n = input()
    if n == 0:
        break
    s, t = 1 - n, 1
    cnt = 1
    sign = -1
    A = ['' for i in range(n)]
    for loop in range(n * 3):
        if sign == 1:
            r = range(max(s, 0), min(t, n))
        else:
            r = range(min(t - 1, n - 1), max(s - 1, -1), -1)
        for i in r:
            A[i] += str(cnt).rjust(3)
            cnt += 1
        s += 1
        t += 1
        sign *= -1
    print "Case " + str(hoge) + ":"
    for i in range(n):
        print A[i]


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

 string S, T;
 void input() {
 cin >> S >> T;
 }

void solve() {
 T.pop_back();
 if(S == T) cout << "Yes" << endl;
 else cout << "No" << endl;
 }

 int main() {
 input();
 solve();
 return 0;
 }

Measured memory_bytes: 3624
n = int(input())
a = []
b = []
c = []
for i in range(n):
    m,v,p = map(int,input().split())
    a.append(m)
    b.append(v)
    c.append(p)
d = [[0]*3 for i in range(n)]
d[0][0]=a[0]
d[0][1]=b[0]
d[0][2]=c[0]
for i in range(1,n):
    for j in range(3):
        if j == 0:
            d[i][j] = max(d[i-1][1],d[i-1][2]) + a[i]
        elif j == 1:
            d[i][j] = max(d[i-1][0],d[i-1][2]) + b[i]
        else:
            d[i][j] = max(d[i-1][0],d[i-1][1]) + c[i]
print(max(d[-1][0],d[-1][1],d[-1][2]))


Measured memory_bytes: 34676
n,k,q = map(int,input().split())
a = [k]*n
for _ in range(q):
    i = int(input())
    a[i-1] = a[i-1] + 1

for i in range(n):
    a[i] = a[i]-q
    if a[i]>0:
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 7852
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;
using static System.Console;


namespace atcorder2
{
    class Program
    {
        public static long Read()
        {

            return long.Parse(Console.ReadLine());
        }

        public static long[] Reads()
        {

            return Console.ReadLine().Split().Select(long.Parse).ToArray();
        }

       




        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            var n = Read();
            var s = ReadLine();
           
            
            long ans = 0;
            for (int i = 1; i < n; i++)
            {
                var memo = 0;
                var c = new bool['z' - 'a' + 1];
                for (int j = 0; j < i; j++)
                {
                    for (int k = i; k < n; k++)
                    {
                        if (s[j] == s[k]) c[s[j] - 'a'] = true;
                    }
                }
                for (int j= 0; j < 'z'-'a'+1; j++)
                {
                    if (c[j]) memo++;
                }
                ans = Math.Max(ans, memo);
            }
            WriteLine(ans);
            
            
            


            Console.Out.Flush();
        }
    }
}




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

#define ln                '\n'
#define all(dat)           dat.begin(), dat.end()
#define loop(i, to)        for (int i = 0; i < to; ++i)
#define cont(i, to)        for (int i = 1; i <= to; ++i)
#define circ(i, fr, to)    for (int i = fr; i <= to; ++i)
#define foreach(i, dat)    for (__typeof(dat.begin()) i = dat.begin(); i != dat.end(); ++i)

typedef long long          num;

using namespace std;

const int nsz = 2e3, mod = 1e9 + 7;
int n;
num k, inv2, a[nsz + 5], pre[nsz + 5], ppre[nsz + 5], ans;

num inline calc(num to) {
    return (1 + to) * to % mod * inv2 % mod;
}

num inline qpow(num a, int p) {
    num res = 1;
    for (; p; p >>= 1) {
        if (p & 1) {
            res *= a;
            res %= mod;
        }
        a *= a;
        a %= mod;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(0);
    inv2 = qpow(2, mod - 2);
    cin >> n >> k;
    cont (i, n) {
        cin >> a[i];
        ++pre[a[i]];
    }
    cont (i, nsz) {
        pre[i] = pre[i - 1] + pre[i];
        ppre[i] = (ppre[i - 1] + (i * (i + 1) / 2) % mod) % mod;
    }
    cont (i, n) {
        num cnt0 = 0, cnt1 = pre[a[i] - 1];
        circ (j, i, n) {
            if (a[j] < a[i]) {
                ++cnt0;
            }
        }
        ans += calc(k) * cnt0 % mod;
        ans %= mod;
        ans += calc(k - 1) * (cnt1 - cnt0) % mod;
        ans %= mod;
    }
    cout << ans << ln;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**9)

n,m = map(int,input().split())
G = [[] for _ in range(n)]
for _ in range(m):
    x,y = map(int,input().split())
    x -= 1
    y -= 1
    G[x].append(y)

dp = [-1]*(n+1)
# dp[i]:頂点iに到達したときの有向辺の最長の長さ
def dfs(cur):
    if dp[cur] != -1:
        return dp[cur]
    res = 0
    for nx in G[cur]:
        res = max(res,dfs(nx)+1)
    dp[cur] = res
    return res
    
for i in range(n):
    dp[i] = max(dp[i],dfs(i))

print(max(dp))


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

using namespace std;

int main()
{
    string S;
    int K;
    cin >> S >> K;
    int ind = 0;

    while(S[ind] == '1' && ind<K)
            ind++;
    if(ind == K)
        cout << S[ind-1];
    else
        cout << S[ind];
}


Measured memory_bytes: 256
#include <stdio.h>

 int main() {
  int a,b,c;
  scanf("%d%d%d", &a,&b,&c);
  int min = a+b;
  if( min >= (b+c)){
      min = b+c;
    }
  if( min >= (a+c)){
    min = a+c;
  }
  printf("%d\n", min);
  return 0;
 }

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define lol long long
int main(){
  string s;
  int a,b=0,c=0;
  cin>>a>>s;
  for(int i=0;i<a;i++){
    if(s[i]=='I') c++;
    else c--;
    if(b<c) b=c;
  }
  cout<<b<<"\n";
  return(0);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1LL<<60;
int main() {
	int N;
	cin >> N;
	vector<vector<long long>> A(N, vector<long long>(N));
	for (int i = 0; i < N; ++ i) for (int j = 0; j < N; ++ j) {
		cin >> A[i][j];
	}
	auto B = A;
	for (int k = 0; k < N; ++ k) for (int i = 0; i < N; ++ i) for (int j = 0; j < N; ++ j) {
		B[i][j] = min(B[i][j], B[i][k] + B[k][j]);
	}
	if (A != B) {
		cout << -1 << endl;
		return 0;
	}
	vector<pair<int, pair<int,int>>> E;
	for (int i = 0; i < N; ++ i) for (int j = i+1; j < N; ++ j) E.push_back({A[i][j], {i,j}});
	sort(E.begin(), E.end());
	long long r = 0;
	vector<vector<long long>> C(N, vector<long long>(N, INF));
	for (int i = 0; i < N; ++ i) C[i][i] = 0;
	for (auto e : E) {
		int u = e.second.first;
		int v = e.second.second;
		int w = e.first;
		if (w < C[u][v]) {
			r += w;
			C[u][v] = C[v][u] = w;
			for (int i = 0; i < N; ++ i) for (int j = 0; j < N; ++ j) {
				C[i][j] = C[j][i] = min(C[i][j], min(C[i][u] + w + C[v][j], C[i][v] + w + C[u][j]));
			}
		}
	}
	if (A != C) throw 1;
	cout << r << endl;
}


Measured memory_bytes: 2936
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int r,c;
	cin>>r>>c;
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			string x;
			cin>>x;
			if(x == "snuke")
			{
				cout<<(char)('A'+j)<<i+1<<"\n";
				return 0;
			}
		}
	}
	return 0;
}

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

using namespace std;

int main(void){
  string str;
  cin >> str;
  int N = str.length();
  // kaibun ?
  for(int i=0;i<N/2;i++){
    if(str[i] != str[N-1-i]){
      cout << "No" << endl;
      return 0;
    }
  }
  // second ?
  for(int i=0;i<(N-1)/4;i++){
    if(str[i] != str[(N-1)/2-i-1]){
      cout << "No" << endl;
      return 0;
    }
  }

    // Third ?
  for(int i=0;i<(N-3)/4;i++){
    if(str[(N+3)/2+i-1] != str[N-1-i]){
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
  
}


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

int n;
int ans = 0;

void maxMove(vector<int> &H, int i) {
    int move = 0;
    while (i < n - 1 && H[i] >= H[i + 1]) {
        i++;
        move++;
    }
    ans = max(ans, move);

    if (i < n - 2) {
        maxMove(H, i + 1);
    }
}

int main() {
    cin >> n;
    vector<int> H(n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &H[i]);
    }

    maxMove(H, 0);

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 640
import math

n,d = map(int,input().split())
#xy = [list(map(float,input().split())) for i in range(n)]
xy = []
for i in range(n):
  xy.append(list(map(float,input().split())))
count = 0
for i in range(n):
  for j in range(i+1,n):
    dis=0
    for k in range(d):
      dis += (xy[i][k]-xy[j][k])**2
    dis = math.sqrt(dis)
    if dis.is_integer():
      count +=1
      
print(count)

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

using namespace std;

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldbl;
typedef pair<int, int> pii;
typedef pair<uint, uint> puu;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
typedef vector<int> vi;
typedef vector<uint> vu;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<pii> vpii;
typedef vector<puu> vpuu;
typedef vector<pll> vpll;
typedef vector<pull> vpull;
typedef vector<string> vstr;
typedef vector<double> vdbl;
typedef vector<ldbl> vldbl;
#define pb push_back
#define ppb pop_back
#define pfr push_front
#define ppfr pop_front
#define emp emplace
#define empb emplace_back
#define be begin
#define rbe rbegin
#define all(x) (x).be(), (x).end()
#define rall(x) (x).rbe(), (x).rend()
#define fir first
#define sec second
#define mkp make_pair
#define brif(cond) if (cond) break
#define ctif(cond) if (cond) continue
#define retif(cond) if (cond) return
void canhazfast() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);}
template<typename T> T gcd(T a, T b) {return b ? gcd(b, a%b) : a;}
template<typename T> T extgcd(T a, T b, T &x, T &y)
{
    T x0 = 1, y0 = 0, x1 = 0, y1 = 1;
    while (b) {
        T q = a/b; a %= b; swap(a, b);
        x0 -= q*x1; swap(x0, x1);
        y0 -= q*y1; swap(y0, y1);
    }
    x = x0; y = y0; return a;
}
int ctz(uint x) {return __builtin_ctz(x);}
int ctzll(ull x) {return __builtin_ctzll(x);}
int clz(uint x) {return __builtin_clz(x);}
int clzll(ull x) {return __builtin_clzll(x);}
int popcnt(uint x) {return __builtin_popcount(x);}
int popcntll(ull x) {return __builtin_popcountll(x);}
int bsr(uint x) {return 31^clz(x);}
int bsrll(ull x) {return 63^clzll(x);}

#define MX 128

char s[MX][MX];
int dp[MX][MX];

int main()
{
    canhazfast();

    int n, m, ans;

    cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> s[i];
    for (int i = 0; i < n-1; ++i) dp[i][m] = MX;
    fill_n(dp[n], m-1, MX);

    for (int i = n-1; i >= 0; --i) {
        for (int j = m-1; j >= 0; --j) {
            int resa = dp[i][j+1], resb = dp[i+1][j];
            if (s[i][j] == '#') {
                if (s[i][j+1] != '#') ++resa;
                if (s[i+1][j] != '#') ++resb;
            }
            dp[i][j] = min(resa, resb);
        }
    }
    /*cerr << "dp =\n";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) cerr << setw(4) << dp[i][j];
        cerr << '\n';
    }*/
    ans = dp[0][0];
    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 384
from fractions import gcd
import collections
from collections import defaultdict

# mod. m での a の逆元 a^{-1} を計算する
# b * a^{-1} (mod m)を計算したい場合はb * modinv(a, m) % m
def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = int(a / b)
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u
    
# 途中計算でmodを計算する高速な累乗計算
def pow_k_mod(x, n, m):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
            K %= m
        x *= x
        x %= m
        n //= 2

    return (K * x) % m
    
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

N = int(input())
A = list(map(int, input().rstrip().split()))

factor = defaultdict(lambda: -1)
for i in range(N):
    c = collections.Counter(prime_factorize(A[i]))
    for k, v in c.items():
        factor[k] = max(factor[k], v)

lcm = 1
for k, v in factor.items():
    lcm *= pow_k_mod(k, v, int(1e9+7))
    lcm %= int(1e9+7)

print(sum([(lcm * modinv(x, int(1e9+7)) % int(1e9+7)) for x in A]) % int(1e9+7))

Measured memory_bytes: 78548
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;

int n,l=0;

vector<vector<int>> G;
vector<int> depth;

int dfs(int s,int par){
    if (par!=-1) depth[s]=depth[par]+1;
    vector<int> a={depth[s],depth[s]};
    rep(i,G[s].size()){
        int t=G[s][i];
        if (t==par) continue;
        a.push_back(dfs(t,s));
    }
    sort(a.begin(),a.end(),greater<int>());
    l=max(l,a[0]+a[1]-2*depth[s]);
    return a[0];
}

void solve(){
    cin >> n;
    G.resize(n,{});depth.resize(n,0);
    rep(i,n-1){
        int a,b;
        cin >> a >> b;
        G[a-1].push_back(b-1);
        G[b-1].push_back(a-1);
    }

    dfs(0,-1);
    
    if (l%3==1) cout << "Second" << endl;
    else cout << "First" << endl;
    
}

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

Measured memory_bytes: 41984
#include <iostream>
#include <stdio.h>
using namespace std;
struct track{
	int number;
	double time;
};

int main(){
	struct track a[3][8],t,x,y,z;
	for(int i=0;i<3;i++){
		for(int j=0;j<8;j++){
			cin>>a[i][j].number>>a[i][j].time;
		}
	}

	for(int i=0;i<3;i++){
		for(int j=0;j<7;j++){
			for(int k=j+1;k<8;k++){
				if(a[i][j].time>a[i][k].time){
					t = a[i][j];
					a[i][j] = a[i][k];
					a[i][k] = t;
				}
			}
		}
	}
	for(int i=0;i<3;i++){
		for(int j=0;j<2;j++){
			printf("%d %.2lf\n",a[i][j].number,a[i][j].time);
		}
	}
	
	x = a[0][2];
	y = a[1][2];
	z = a[2][2];
	for(int i=0;i<2;i++){
		if(x.time<y.time && x.time<z.time){
			printf("%d %.2lf\n",x.number,x.time);
			x = a[0][3];
		}else if(y.time<x.time && y.time<z.time){
			printf("%d %.2lf\n",y.number,y.time);
			y = a[1][3];
		}else if(z.time<y.time && z.time<x.time){
			printf("%d %.2lf\n",z.number,z.time);
			z = a[2][3];
		}
	}

	return 0;
}

Measured memory_bytes: 1240
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,u) for(int i=start[u];i;i=e[i].next)
#define fi first
#define se second
#define mkr(a,b) make_pair(a,b)
#define SZ(A) ((int)A.size())
template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}
template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}
inline void myassert(bool a,string s){ if(!a)cerr<<s<<endl,exit(0);}
inline int read()
{
	int s=0,f=1;char ch=getchar();
	while(!isdigit(ch) && ch!='-')ch=getchar();
	if(ch=='-')ch=getchar(),f=-1;
	while(isdigit(ch))s=s*10+ch-'0',ch=getchar();
	return ~f?s:-s;
}

const int maxn=5e3+20;
const int mod=1e9+7;
vector<int>ed[maxn];
int n;
int f[maxn];

inline void init()
{
	n=read();
	REP(i,1,n-1)
	{
		int x=read(),y=read();
		ed[x].push_back(y);
		ed[y].push_back(x);
	}
	f[0]=1;
	REP(i,1,n>>1)f[i]=((ll)(2*i-1)*f[i-1])%mod;
}

int dp[maxn][maxn];
int sz[maxn];

void dfs(int u,int fa)
{
	dp[u][sz[u]=1]=1;
	for(int v:ed[u])
	{
		if(v==fa)continue;
		dfs(v,u);
		DREP(a,sz[u],1)
		{
			int t=dp[u][a]; dp[u][a]=0;
			DREP(b,sz[v],0)
			{
				dp[u][a+b]=(dp[u][a+b]+(ll)t*dp[v][b])%mod;
			}
		}
		sz[u]+=sz[v];
	}
	REP(j,1,sz[u]>>1)dp[u][0]=(dp[u][0]-(ll)dp[u][j<<1]*f[j])%mod;
}

inline void doing()
{
	dfs(1,0);
	int ans=dp[1][0];
	ans=(mod-ans)%mod;
	printf("%d\n",ans);
}

int main()
{
	init();
	doing();
	return 0;
}


Measured memory_bytes: 98304
#include<iostream>
#include<cstdio>
using namespace std;
#define LL long long
const int CN = 1e5+5;
const LL R = 998244353;
int n,fir; LL s[CN];
LL qpow(LL a,LL b){
    LL rec = 1;
    while(b){
        if(b & 1) (rec *= a) %= R;
        (a *= a) %= R; b >>= 1;
    }
    return rec;
}
int main(){
    scanf("%d%d",&n,&fir);
    for(int i=2;i<=n;i++){
        int x; scanf("%d",&x); 
        if(!x) {fir = 1; break;}
        s[x]++;
    }

    for(int i=1;i<=n;i++) if(s[i]) s[0] = i;
    for(int i=1;i<=s[0];i++) if(!s[i]) fir = 1;

    if(fir) printf("0");
    else{
        LL ans = 1;
        for(int i=2;i<=s[0];i++) (ans *= qpow(s[i-1], s[i])) %= R;
        printf("%lld",ans);
    }
}

Measured memory_bytes: 1024
n = int(input())
a = list(map(int,input().split()))

cnt = 0
for i in range(100):

    if sum(list(1 for x in a if x % 2 == 1)) != 0:
        print(cnt)
        exit()
    
    a = list(x // 2 for x in a)
    cnt += 1

print(cnt)

Measured memory_bytes: 38640
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
using namespace std;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1145141919810364364LL;
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)

vector<int>E[101010];
int N, M, Q;

int memo[101010][15];
void rec(int v,int d,int c){
	if (d < 0)return;
	if (memo[v][d] != 0)return;
	memo[v][d] = c;
	for (int i = d - 1; i >= 0; i--)rec(v,i,c);
	fore(x,E[v])rec(x, d - 1, c);
}

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

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		E[a].pb(b);
		E[b].pb(a);
	}
	cin >> Q;
	vector<vector<int>>dat(Q);

	for (int i = 0; i < Q; i++) {
		int v, d, c;
		cin >> v >> d >> c;
		v--;
		dat[i] = { v,d,c };
	}
	reverse(all(dat));

	for (int i = 0; i < Q; i++) {
		int v = dat[i][0];
		int d = dat[i][1];
		int c = dat[i][2];
		rec(v, d, c);
	}
	for (int i = 0; i < N; i++)puts(memo[i][0]);

	return 0;
}

Measured memory_bytes: 17912
#include <stdlib.h>
#include <cmath>
#include <cstdio>
#include <cstdint>
#include <string>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
using namespace std;

int main(){
  int N,M;
  cin >> N >> M;
  vector<int> A(N);
  long long sum=0;
  for(int i=0; i<N; i++){
    cin >> A.at(i);
    sum+=A.at(i);
  }
  
  sort(A.begin(),A.end());
  int select=0;
  for(int i=0; i<N; i++){
    if(A.at(i)*4*M<sum) continue;
    else select++;
    if(select==M){
      cout << "Yes" << endl;
      return 0;
    }
  }

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


Measured memory_bytes: 256
lst_1 = input().split()

N = int(lst_1[0])
M = int(lst_1[1])
X = (lst_1[2])
Y = (lst_1[3])

lst_X = input().split()
lst_Y = input().split()

lst_X.append(X)
lst_Y.append(Y)

for i in range(N+1):
    lst_X[i] = int(lst_X[i])
for i in range(M+1):
    lst_Y[i] = int(lst_Y[i])

X_max = max(lst_X)
Y_min = min(lst_Y)

if (X_max < Y_min) and (X < Y):
    ans = "No War"

else:
    ans = "War"

print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <math.h>
using namespace std;
typedef long long ll;

int main() {
    int n, q, c, b, e;
    cin >> n;
  	int a[n];
  	for (int i = 0; i < n; i++) cin >> a[i];
  	cin >> q;
  	for (int i = 0; i < q; i++)
  	{
        cin >> b >> e;
  	    reverse(a+b,a+e);
  	}
  	for (int i = 0; i < n; i++) 
  	{
  	    cout << a[i];
  	    if (i == n-1) cout << endl;
  	    else cout << " ";
  	}
	return 0;
}


Measured memory_bytes: 3124
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;

string s;

ll dfs(int i, string t, ll sum) {
    if (i == s.size() - 1) {
        sum += stoll(t + s[i]);
        return sum;
    }

    ll res = 0;

    res = dfs(i + 1, t + s[i], sum);

    sum += stoll(t + s[i]);
    res += dfs(i + 1, "", sum);

    return res;
}

int main() {
    cin >> s;
    cout << dfs(0, "", 0) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds; 
using ll = long long int;
#define INF             1e14
#define dd              double
#define MOD             998244353
#define my_sizeof(type) ((char *)(&type+1)-(char*)(&type)) 
#define nl              cout<<endl
#define fill(a,val)     memset(a,val,sizeof(a))
#define mp              make_pair
#define endl            "\n"
#define pb              push_back
#define ff              first    
#define ss              second
#define SIZE            200005
#define all(v)          v.begin(),v.end()
#define s(ar,n)         sort(ar,ar+n)
#define rs(ar,n)        sort(ar, ar+n, greater<ll>()) 
#define oa(a,n)         for(ll i=0;i<n;i++)cout<<a[i]<<" ";nl
#define cn(a,n)         for(ll i=0;i<n;i++)cin>>a[i];
#define maxa(ar,N)      *max_element(ar,ar+N)
#define mina(ar,N)      *min_element(ar,ar+N)
#define fastio()        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define printclock      cerr<<"Time : "<<1000*(long double)clock()/(long double)CLOCKS_PER_SEC<<"ms\n";
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// find_by_order() - 0 indexing
// order_of_key() - number of elements strictly smaller
ll power(ll x, ll y){
    ll res=1;x=x;
    while(y>0){
        if(y&1)
            res = (res*x);
        y = y>>1;
        x = (x*x);
    }
    return res;
}  
ll logtwo(ll n){
    if(n==1)
        return 0;
    return logtwo(n/2)+1;
}
//---------------------------------------GL HF------------------------------------------------------
// -------------------------------------ManavJ07----------------------------------------------------
signed main()
{
    fastio();   
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    ll N,K;
    cin>>N>>K;
    pair<ll,ll> ar[K];
    for(ll i=0;i<K;i++){
        cin>>ar[i].ff>>ar[i].ss;
    }
    ll dp[N+1]={},dpSum[N+1]={};
    dp[1]=1;dpSum[1]=1;
    for(ll i=2;i<=N;i++){
        for(ll j=0;j<K;j++){
            if(i-ar[j].ff<=0)
                continue;
            ll chg=dpSum[i-ar[j].ff]-dpSum[max(i-ar[j].ss,1ll)-1];
            chg%=MOD;
            if(chg<0)
                chg+=MOD;
            dp[i]+=chg;
            dp[i]%=MOD;
        }
        dp[i]%=MOD;
        dpSum[i]=dp[i]+dpSum[i-1];
        dpSum[i]%=MOD;
        //cout<<i<<" "<<dp[i]<<" "<<dpSum[i]<<endl;
    }
    cout<<dp[N]%MOD<<endl;
}

Measured memory_bytes: 6752
#include <bits/stdc++.h>
#define DEBUG if(0)
#define lli long long int
#define ldouble long double
using namespace std;

const int maxN = 50, maxM = 20; int n, m;
int edgesSolves[maxN];
vector<pair<int, int>> tree[maxN];
vector<pair<int, int>> restrictions;

bool fillEdgesSolves(int u, int target, int r, int prv = -1)
{
  if (u == target) return true;
  for (auto &e: tree[u])
    if (e.first != prv && fillEdgesSolves(e.first, target, r, u))
    {
      edgesSolves[e.second] |= 1 << r;
      return true;
    }
  return false;
}

lli memo[maxN][1 << maxM];
lli solve(int i = 0, int bitmask = 0)
{
  if (i == n - 1) return bitmask == ((1 << restrictions.size()) - 1);
  if (memo[i][bitmask] != -1) return memo[i][bitmask];
  return memo[i][bitmask] = solve(i + 1, bitmask) + solve(i + 1, bitmask | edgesSolves[i]);
}

int main()
{
  while (scanf("%d", &n) != EOF)
  {
    for (int i = 0; i < n; i ++) tree[i].clear();
    memset(edgesSolves, 0, sizeof(edgesSolves));
    restrictions.clear();

    for (int i = 0; i < n - 1; i ++)
    {
      int u, v; scanf("%d %d", &u, &v); u --, v --;
      tree[u].push_back({v, i}), tree[v].push_back({u, i});
    }
    scanf("%d", &m);
    for (int i = 0; i < m; i ++)
    {
      int u, v; scanf("%d %d", &u, &v); u --, v --;
      restrictions.push_back({u, v});
    }

    for (int i = 0; i < restrictions.size(); i ++)
    {
      auto &r = restrictions[i];
      fillEdgesSolves(r.first, r.second, i);
    }

    memset(memo, -1, sizeof(memo));
    lli ans = solve();
    printf("%lld\n", ans);
  }
  return 0;
}

Measured memory_bytes: 409856
import java.util.Scanner;

class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int[][] bi =new int[3][3];
		boolean[][] fl=new boolean[3][3];
		for(int i=0; i<3; i++) {
			for(int j=0; j<3; j++) {
				bi[i][j]=sc.nextInt();
				fl[i][j]=false;
			}
		}
		int N=sc.nextInt();
		for(int i=0; i<N; i++) {
			int tmp=sc.nextInt();
			for(int k=0; k<3; k++) {
				for(int l=0; l<3; l++) {
					if(bi[k][l]==tmp) {
						fl[k][l]=true;
					}
				}
			}
		}
		boolean kekka =true;
		int cnt=0;
		for(int i=0; i<3; i++) {
			kekka =true;
			for(int j=0; j<3; j++) {
				if(fl[i][j] && kekka) {
					//
				}
				else {
					kekka=false;
				}
			}
			if(kekka) {
				cnt++;
			}
		}

		for(int j=0; j<3; j++) {
			kekka =true;
			for(int i=0; i<3; i++) {
				if(fl[i][j] && kekka) {
					//
				}
				else {
					kekka=false;
				}
			}
			if(kekka) {
				cnt++;
			}
		}
		kekka=true;
		for(int i=0; i<3; i++) {
			if(fl[i][i] && kekka) {
				//
			}
			else {
				kekka=false;
			}
		}
		if(kekka) {
			cnt++;
		}

		kekka=true;
		for(int i=0; i<3; i++) {
			if(fl[i][2-i] && kekka) {
				//
			}
			else {
				kekka=false;
			}
		}
		if(kekka) {
			cnt++;
		}
		if(cnt>0) {
			pl("Yes");
		}
		else {
			pl("No");
		}

	}
	public static void pl(Object o) {
		System.out.println(o);
	}
}

Measured memory_bytes: 22612
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
#include<stdio.h>
#include<string.h>
#include<cstdio>
#include<iomanip>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using piii = pair<pii, pii>;
const int INF = 1e9 + 7;
int main() {
	ll N, P;
	cin >> N >> P;
	if (N == 1) {
		cout << P << endl;
		return 0;
	}
	ll ans = 1;
	ll a = 1;
	while (pow(a, N) <= P) {
		ll kake = pow(a, N);
		if (P%kake == 0)ans = a;
		a++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#define _CRT_SECURE_NO_WARNINGS
//~ #pragma GCC optimize("Ofast, unroll-loops")
#include <iostream>
//~ #include <algorithm>
#include <vector>
#include <iomanip>
#include <ctime>
#include <unordered_set>
#include <string>
#include <map>
#include <unordered_map>
#include <random>
#include <set>
#include <cassert>
#include <string.h>
#include <stack>
#include <functional>
#include <queue>
#include <numeric>
#include <bitset>
#include <iterator>
//~ #include <algorithm>
#include <sstream>



#define inf 0x3f3f3f3f
#define sup_inf 2e18
#define pb push_back
#define f first
#define s second
#define ii pair<int,int>
#define iii pair<int, ii >
#define vai freopen("in","r",stdin);
//~ #define imprime freopen("myfile.txt","w",stdout);	

	
using namespace std;	
typedef long long ll;	
const int maxn = 5000;
const int MAX = 100;




 
int n , k;
int main (){
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	 
	cin >> n >> k;
	int ans = 1 ;
	n-=k;
	while ( n > 0 ) n-=(k-1), ++ans;
	cout << ans << '\n';
}


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

using namespace std;

int main() {
  for (;;) {
    int s[3];
    for (int i = 0; i < 3; i++)
      cin >> s[i];
    if (!s[0] && !s[1] && !s[2]) return 0;
    sort(s, s+3);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
      int r;
      cin >> r;
      if (s[0]*s[0] + s[1]*s[1] < 4*r*r)
        cout << "OK" << endl;
      else
        cout << "NA" << endl;
    }
  }
}

Measured memory_bytes: 0
//By Krishna Yadav
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define testcase(t) int t; cin>>t; while(t--)
#define forstl(i,v) for(auto &i: v)
#define forn(i,e) for(int i = 0; i < e; i++)
#define ln "\n"
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define dbg2(x,y) cout<<#x<<" = "<<x<<" & "<<#y<<" = "<<y<<ln
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> p32;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef map<int, int> m32;
const int LIM = 2e5+5, MOD = 1e9+7;
int t,n,m,k,x,y;

int main(){
  fastio;
  int H, W, h, w;
  cin>>H>>W>>h>>w;
  cout<<(H-h)*(W-w)<<endl;
}

Measured memory_bytes: 256
from sys import stdin
A,B,C = [int(x) for x in stdin.readline().rstrip().split()]
d = sorted([A,B,C])
 
a = A % 2
b = B % 2
c = C % 2
 
if a == b == c:
    ans = ((d[2] - d[1]) + (d[2] -d[0])) // 2
    
elif a == b:
    A += 1
    B += 1
    d = sorted([A,B,C])
    ans = ((d[2] - d[1]) + (d[2] -d[0])) // 2
    ans += 1
    
elif a == c:
    A += 1
    C += 1
    d = sorted([A,B,C])
    ans = ((d[2] - d[1]) + (d[2] -d[0])) // 2
    ans += 1
 
elif c == b:
    B += 1
    C += 1
    d = sorted([A,B,C])
    ans = ((d[2] - d[1]) + (d[2] -d[0])) // 2
    ans += 1
 
    
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007

ll answer[100001];
vector<ll>answer1[100001];
int main(){
  FIO;
  // ifstream cin("input");
  ll n,m;
  cin>>n>>m;
  ll a[n];
  ll i;
  for(i=0;i<n;i++){
    cin>>a[i];
  }
  ll x,y;
  while(m--){
    cin>>x>>y;
    x--;
    y--;
    if(a[x]>a[y]){
      answer[x]++;
    }else if(a[x]<a[y]){
      answer[y]++;
    }
    answer1[x].push_back(y);
    answer1[y].push_back(x);
  }
  ll ans=0;
  for(i=0;i<n;i++){
    if(answer[i]==answer1[i].size()){
      ans++;
    }
  }
  cout<<ans<<endl;
  return 0;  
}

Measured memory_bytes: 11032
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i)
#define all(a) (a).begin(), (a).end()

int N;
vector<double> x, y;

int main() {
  cin >> N;
  x.resize(N), y.resize(N);

  rep(i, N) cin >> x[i] >> y[i];

  double ans = 0;
  rep(i, N) rep(j, N) {
    double dx = x[i] - x[j], dy = y[i] - y[j];
    ans += sqrt(dx * dx + dy * dy);
  }
  ans /= N;

  printf("%.8lf\n", ans);
  return 0;
}


Measured memory_bytes: 256
import math

a,b,x = map(int,input().split())

if x >= a**2*b/2:
    theta = math.atan(2*((a**2)*b-x)/(a**3))
else:
    theta = math.pi/2 - math.atan((2*x)/(a*(b**2)))
print(math.degrees(theta))

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

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define SUM(x) accumulate(ALL(x), 0)
#define INF 1000000000000
#define MOD 10000007
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define MAXR 100000

int main()
{
  ll a, b, c, x, y; cin >> a >> b >> c >> x >> y;

  ll sum1 = a * x + b * y;

  ll sum2 = 0;
  if (x < y) {
    sum2 = c * x * 2 + (y - x) * b;
  } else {
    sum2 = c * y * 2 + (x - y) * a;
  }

  ll sum3 = max(x, y) * c * 2;

  cout << min (sum1, min(sum2, sum3)) << endl;
  return 0;
}


Measured memory_bytes: 256
from sys import stdin
input = stdin.readline


def pow_k(x, n, MOD=1_000_000_007):
  if n == 0:
    return 1
  K = 1
  while n > 1:
    if n % 2 != 0:
      K *= x
      K %= MOD
    x *= x
    x %= MOD
    n //= 2
  return K * x % MOD


def comb(n, r, MOD=1_000_000_007):
  if n - r < r: r = n - r
  if r == 0: return 1
  if r == 1: return n

  numerator = [n - r + k + 1 for k in range(r)]
  denominator = [k + 1 for k in range(r)]

  for p in range(2, r+1):
    pivot = denominator[p-1]
    if pivot > 1:
      offset = (n - r) % p
      for k in range(p-1, r, p):
        numerator[k - offset] /= pivot
        denominator[k] /= pivot

  result = 1
  for k in range(r):
    if numerator[k] > 1:
      result *= int(numerator[k])
      result %= MOD

  return result


def main():
  N, a, b = list(map(int, input().split()))

  print((pow_k(2, N)-1-comb(N, a)-comb(N, b)) % 1_000_000_007)


if(__name__ == '__main__'):
  main()


Measured memory_bytes: 107492
/*
 * main.cpp
 *
 *  Created on: 2020/04/10
 *      Author: SkAaO
 */

#include <iostream>
#include <algorithm>

using namespace std;

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

	int sum_odd = 0, sum_even = 0;
	for(int i = 0; i < N; i++){
		if(i % 2 == 0){
			sum_odd += a[i];
		}else{
			sum_even += a[i];
		}
	}

	cout << sum_odd - sum_even << endl;

	return 0;
}




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

int main(){
  string S;
  cin>>S;
  bool flag=true;
  if(S.at(0)!='A'){
    flag=false;
  }
  int n=S.size();
  int x=S.at(1)-'a';
  if(x<0||x>=26){
    flag=false;
  }
  int num=0;
  for(int i=2;i<n-1;i++){
    if(S.at(i)=='C'){
      num++;
    }else{
      x=S.at(i)-'a';
      if(x<0||x>=26){
        flag=false;
      }
    }
  }
  if(num!=1){
    flag=false;
  }
  x=S.at(n-1)-'a';
  if(x<0||x>=26){
    flag=false;
  }
  if(flag){
    cout<<"AC"<<endl;
  }else{
    cout<<"WA"<<endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <sstream>
#include <algorithm>
#include <math.h>
#include <map>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>

#define PI 3.14159265359

#define INF 99999999;

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

#define EPS 1e-10

typedef long long ll;

using namespace std;



/*
class TheKingsArmyDiv2
{
public:
	int getNumber(vector <string> state)
	{

	}
};
*/


double a, b, c, d, e, f, g, h;
double det()
{
	double dx1, dy1, dx2, dy2;
	
	dx1 = a - c;
	dy1 = b - d;
	dx2 = e - g;
	dy2 = f - h;
	
	return dx1*dy2 - dy1*dx2;
}


int main()
{
	int n;
	
	cin >> n;
	while (n--)
	{
		cin >> a >> b >> c >> d >> e >> f >> g >> h;
		cout << (fabs(det()) < EPS ? "YES" : "NO") << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1224
#include <iostream>
#include <algorithm>
#include <string>
#include <numeric>
#include <vector>
using namespace std;
int main(){
  int n,x,i;
  cin>>n>>x;
  vector <int> L(n);
  for(i=0;i<n;i++){
    cin>>L[i];
    x-=L[i];
  }
  cout<<n + x / *min_element(L.begin(),L.end());
 }

Measured memory_bytes: 256
N=gets.to_i
AS = N.times.map {
    n = gets.to_i
    n.times.map { gets.split.map(&:to_i) }
}

def f(target)
    target.each.with_index do |a,i|
        next if a == 0
        AS[i].each do |x,y|
            # p [target[x-1], 1-(a^y), [a,i],[x,y]]
            if target[x-1] != y
                return 0
            end
        end
    end
    target.count(1)
end

ret = 0
[0,1].repeated_permutation(N) do |target|
    # p target
    n = f(target)
    ret = n if ret < n
end

puts ret

Measured memory_bytes: 2044
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		long ans = Long.parseLong(sc.next());

		for (int i=0; i<n-1;i++){
			ans = lcm(ans, Long.parseLong(sc.next()));
		}
		System.out.println(ans);
    }

	public static long gcd(long x, long y){
		if (y == 0){
			return x;
		}else {
			return gcd(y, x%y);
		}
	}

	public static long lcm(long x, long y){
		return x / gcd(x, y) * y;
	}
}

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

int main(){
  
  int a, b, c;
  cin >> a >> b >> c;
  string ans = "No";

  if(a <= c && c <= b) ans = "Yes";
  cout << ans << endl;

}

Measured memory_bytes: 256
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    a, b = map(int, readline().split())

    d = b - a
    ans = d * (d + 1) // 2 - b
    print(ans)

    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 9088
#include <iostream> // cin, cout, cerr, clog
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota, accumulate, inner_product
#include <cstdio> // printf, scanf
#include <climits> // INT_MIN, LLONG_MIN
#include <cmath> // long, trig, pow
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <stack> // stack
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <unordered_map> // hashed by keys
#include <unordered_set> // hashed by keys
#include <iomanip> // cout<<setprecision(n)

#define rep(i,n) for(int i = 0; i < n; i++)
#define ENDL "\n"
#define print(i) std::cout << (i) << "\n"

#define int long long // at least int64 > 9*10^18
#define all(v) v.begin(), v.end()

signed main() {
	int n,q;
	std::cin >> n >> q;
	std::map<int,int> map;
	int one = 1;
	rep(i,q) {
		rep(j,3) map[one-1+j] = 1;
		int a,b;
		std::cin >> a >> b;
		if(one==a) one = b;
		else if(one==b) one = a;
		std::swap(map[a],map[b]);
	}
	rep(j,3) map[one-1+j] = 1;
	int sum = 0;
	for(auto& i:map) {
		if(i.first==0||i.first==n+1) continue;
		sum+=i.second;
	}
	print(sum);
	return 0;
}


Measured memory_bytes: 5376