akhauriyash/Code-Regression huggingface dataset:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def MI(): return map(int, input().split())


def S(): return input()


def MS(): return map(str, 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 input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['No', 'Yes']
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']


show_flg = True
show_flg = False


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


# N個の最大公約数
def eucledean(A, N):
    # A = sorted(A)
    ans = A[0]
    for i in range(1, N):
        ans = gcd(A[i], ans)
    return ans


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


# N個最小公倍数
def lcm_n(A, N):
    # A = sorted(A)
    ans = A[0]
    # for i in range(1, N):
    #     ans = fractions.gcd(A[i], ans)
    for i in range(1, N):
        ans = lcm(ans, A[i])
    return ans


def modinv(a):
    return pow(a, MOD-2, MOD)


def main():
    N = I()
    A = LI()
    ans = 0

    # N = 10 ** 4
    # A = [10**6] * N
    # for i in range(N):
    #     A[i] -= i
    # # A[0] = 10**6 - 1
    # # A[1] = 10**6 - 2
    a = lcm_n(A, N)
    a %= MOD
    for i in range(N):
        ans += a * modinv(A[i])
    print(ans % MOD)


if __name__ == '__main__':
    main()


Measured memory_bytes: 69460
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <set>
#include <math.h>
#include <queue>
#define rep(i,n) for (int i = 0; i < (n); ++i)
typedef long long ll;
using namespace std;

int main() {
    ll n, d, cnt=0;
    cin >> n >> d;
    rep(i,n) {
        ll x,y;
        cin >> x >> y;
        double r=sqrt(x*x+y*y);
        if (r<=d) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 3172
#include <stdio.h>
#define MAX 10000000;

int adj[10000][10000][2];
int cost[10000];
int check[10000];
int size[10000];

int heaps[10000000], h = 0;

void min_heapify(int a[], int i) {
  int smallest, b;
  int l = i * 2;
  int r = i * 2 + 1;

  if (l <= h && -cost[a[l]] > -cost[a[i]])
    smallest = l;
  else
    smallest = i;
  if (r <= h && -cost[a[r]] > -cost[a[smallest]])
    smallest = r;

  if (smallest != i) {
    b = a[i];
    a[i] = a[smallest];
    a[smallest] = b;
    min_heapify(a, smallest);
  }
}

void check_minheap(int a[], int i) {
  int b;
  while (i > 1 && -cost[a[i]] > -cost[a[i / 2]]) {
    b = a[i];
    a[i] = a[i / 2];
    a[i / 2] = b;
    i = i / 2;
  }
}

void insert(int a[], int key, int i) {
  a[i] = key;

  check_minheap(a, i);
}

int extract(int a[], int i) {
  int min = a[1];
  a[1] = a[i];
  h--;
  min_heapify(heaps, 1);
  return min;
}

void setup(int n) {
  for (int i = 0; i < n; i++)
    cost[i] = MAX;
}

void input(int n) {
  int node, k;
  for (int i = 0; i < n; i++) {
    scanf("%d", &node);
    scanf("%d", &k);
    size[node] = k;
    for (int j = 0; j < k; j++)
      scanf("%d%d", &adj[i][j][0], &adj[i][j][1]);
  }
}

void dijkstra(int n) {
  int t, v, j;
  setup(n);
  cost[0] = 0;
  insert(heaps, 0, ++h);

  while (h != 0) {
    t = extract(heaps, h);
    check[t]++;
    j = 0;
      for (int j = 0; j < size[t]; j++) {
	v = adj[t][j][0];
	if (cost[v] > cost[t] + adj[t][j][1]) {
	  cost[v] = cost[t] + adj[t][j][1];
	  insert(heaps, v, ++h);
	}
      }
    
  }
}

int main(void) {
  int n;

  scanf("%d", &n);
  input(n);
  
  dijkstra(n);

  for (int i = 0; i < n; i++)
    printf("%d %d\n", i, cost[i]);

  return 0;
}



Measured memory_bytes: 43844
n = int(input())
s = input()

order  = ["R", "G", "B"]
prefix = [[0 for i in range(n+1)] for i in range(3)]

for i in range(n):
	prefix[0][i+1] = prefix[0][i]
	prefix[1][i+1] = prefix[1][i]
	prefix[2][i+1] = prefix[2][i]
	if s[i] == "R":
		prefix[0][i+1] += 1
	elif s[i] == "G":
		prefix[1][i+1] += 1
	elif s[i] == "B":
		prefix[2][i+1] += 1
	else:
		print("Exception!")

# print("r_prefix", prefix[0])
# print("g_prefix", prefix[1])
# print("b_prefix", prefix[2])

ans = 0
for first in range(n):
	for second in range(first+1, n):
		if s[first] == s[second]:
			pass
		else:
			# print("first", first)
			# print("second", second)
			missing = list({"R", "G", "B"} - {s[first], s[second]})[0]
			mis_order = order.index(missing)

			# print("missing", missing)
			# print("mis_order", mis_order)
			to_exclude = second + (second - first)

			ans += prefix[mis_order][n] - prefix[mis_order][second+1]
			if to_exclude < n and s[to_exclude] == missing:
				ans -= 1
			# print("ans", ans)
			# print()
print(ans)




Measured memory_bytes: 69384
import math
def main():
  n = int(input())
  a = list(map(int,input().split()))
  ans=0
  while True:
    flg=0
    for i in range(0,n):
      if a[i]%2==1:
        flg=1
        break
      a[i]/=2
    if flg==1:
      print(ans)
      break
    ans+=1
main()


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

#define rep(i,n) for(long long (i)=0;(i)<(n);(i)++)
#define reps(i,s,n) for(long long (i)=(s);(i)<(n);(i)++)
#define repr(i,n) for(int (i)=(n)-1;(i)>=0;(i)--)
#define all(v) (v).begin(),(v).end()
#define chmax(a, b) a = max((a),(b))
#define chmin(a, b) a = min((a),(b))
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define inf 1000000000
#define llinf 1000000000000000


typedef long long ll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;



int main(){
    ll l,r;
    cin>>l>>r;
    r=min(r+1,l+5000);
    ll ans=inf;
    reps(i,l,r){
        reps(j,i+1,r){
            //cout<<i<<" "<<j<<endl;
            //cout<<(int)((ll)i*(ll)j%2019)<<endl;
            ans=min(ans,(i*j%2019));
            //cout<<i<<" "<<j<<" "<<ans<<endl;
            //chmin(ans,(int)((ll)i*(ll)j%2019));
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int h, w;
  cin >> h >> w;
  int mp[10][10] = {};
  rep(i, 0, 10) rep(j, 0, 10) cin >> mp[i][j];

  for (int i = 0; i < 10; i++)
    for (int j = 0; j < 10; j++)
      for (int k = 0; k < 10; k++)
        mp[j][k] = min(mp[j][k], mp[j][i] + mp[i][k]);

  int ans = 0;
  rep(i, 0, h) rep(j, 0, w) {
    int a;
    cin >> a;
    if (a >= 0)
      ans += mp[a][1];
  }
  cout << ans << endl;
}


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

int main()
{
	int N, T;
	cin >> N >> T;
	vector<int>c(N);
	vector<int>t(N);
	vector<int>a(N);
	int n;
	n = 0;
	while (n<N)
	{
		cin >> c[n] >> t[n];

		if (t[n]<=T)
		{
			a[n] = 1;
		}
		else
		{
			a[n] = 0;
		}
		n = n + 1;
	}
	int ans = 0; 
	int i = c[0];
	if (a[0]==1)
	{
		ans = 1;
	}
	n = 0;
	while (n<N)
	{
		if (c[n]<i)
		{
			if (a[n]==1)
			{
				i = c[n];
				ans = n + 1;

			}
		}
		n = n + 1;
	}
	if (ans == 0)
	{
		cout << "TLE" << endl;
	}
	else
	{
		cout << c[ans-1] << endl;
	}

    return 0;
}



Measured memory_bytes: 256
x, y, a, b, c = map(int, input().split())
p = sorted(list(map(int, input().split())))[::-1][:x]
q = sorted(list(map(int, input().split())))[::-1][:y]
r = sorted(list(map(int, input().split())))[::-1]
merge = sorted(p + q + r,reverse= True)

print(sum(merge[:(x+y)]))

Measured memory_bytes: 110828
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin>>N;
    vector<int>a(N);
    bool Even=true;
    for(int &i:a)cin>>i;
    for(int i=0;i<N;i++){
        int sum=0;
        sum+=a.at(i);
        if(sum%2){
            Even=false;
            break;
        }
    }
    int count=0;
    while(Even){
        int sum=0;
        for(int i=0;i<N;i++){
            sum+=a.at(i);
            if(sum%2){
                Even=false;
                break;
            }else{
                a.at(i)/=2;
            }
        }
        if(!Even)break;
        count++;
    }
    cout<<count<<endl;
}

Measured memory_bytes: 256
import sys

K = int(input())
a = []
i = 1

a.append(7 % K)
while i < K:
    a.append((a[i-1]*10+7) % K)
    i += 1

i = 0
while i < K:
    if(a[i]==0):
        print(i+1)
        exit(0)
    i += 1

print(-1)

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

int main() {
    int n,q;cin>>n>>q;
    queue<int > a[n];
    while(q--){
        int i;cin>>i;
        if(i==0){
            int t,x;cin>>t>>x;
            a[t].push(x);
        }
        if(i==1){
            int t;cin>>t;
            if(a[t].empty()){
                continue;
            }
            cout<<a[t].front()<<endl;
        }
        if(i==2){
            int t;cin>>t;
            if(a[t].empty()){
                continue;
            }
            a[t].pop();
        }
    }
    return 0;
}



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


void solve(long long N, std::vector<long long> a){
  long long acc = 0;

  for(long long i = 0; i < N; i++) {
    long long mya = a[i];
    long long count = 0;
    while(mya % 2 == 0) {
      mya /= 2;
      count++;
    }
    acc += count;
  }

  cout << acc << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
  scanf("%lld",&N);
  std::vector<long long> a(N);
  for(int i = 0 ; i < N ; i++){
    scanf("%lld",&a[i]);
  }
    solve(N, std::move(a));
    return 0;
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main {
	static int[] A;
	static int[][] x;
	static int[][] y;
	static int n;

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

		A = new int[20];
		x = new int[20][20];
		y = new int[20][20];

		n = sc.nextInt();






		for(int i =0; i < n; i++){
			A[i] = sc.nextInt();
			for(int j = 0; j < A[i]; j++){
				x[i][j] = sc.nextInt();
				y[i][j] = sc.nextInt();


			}
		}


		int count = 0;
		int max = 1<<n;

		for(int num = 0; num < max; num++) {
			if(canConsist(num) ){
				int tmp = Integer.bitCount(num);
				if(tmp > count){
					count =tmp;
				}
			}



		}
		System.out.print(count);



	}
	static boolean canConsist(int num){
		boolean canConsist = true;

		for(int i = 0; i < n;i++){
			if(((num>>i)&1 )==0) {
				continue;

			}
			for(int j =0; j <A[i]; j++){
				if((num >>x[i][j] -1 &1 ^ y[i][j] )==1){
					return false;
				}


			}
		}
		return true;

	}


}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
#define INF 5000000000000000000
#define ll long long
#define pll pair<ll, ll>
using namespace std;

int main()
{
  ll H, W;
  cin >> H >> W;
  vector<vector<char>> S(H + 2, vector<char>(W + 2, '.'));
  for (ll i = 0; i < H; ++i) {
    string s;
    cin >> s;
    for (ll j = 0; j < W; ++j) {
      S.at(i + 1).at(j + 1) = s[j];
    }
  }
  bool pos = true;
  for (ll i = 1; i <= H; ++i) {
    for (ll j = 1; j <= W; ++j) {
      if (S.at(i).at(j) == '#') {
        bool ok = false;
        if (S.at(i + 1).at(j) == '#') {
          ok = true;
        }
        if (S.at(i).at(j + 1) == '#') {
          ok = true;
        }
        if (S.at(i - 1).at(j) == '#') {
          ok = true;
        }
        if (S.at(i).at(j - 1) == '#') {
          ok = true;
        }
        if (!ok) {
          pos = false;
        }
      }
    }
  }
  if (pos) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }

  // for (ll i = 0; i < H; ++i) {
  //   for (ll j = 0; j < W; ++j) {
  //     cout << S.at(i).at(j);
  //   }
  //   cout << endl;
  // }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
const int N=100005;
using namespace std;
int j,i;
string s,t;                                           
int main(){	
	cin>>s>>t;
    for(i=s.size()-t.size();i>=0;i--)
	{
		for(j=0;j<t.size();j++)      
		{if(s[j+i]!=t[j]&&s[i+j]!='?') break;}
	    if(j==t.size()) break;
    }
    if(i<0) cout<<"UNRESTORABLE";
    else{
    	for(j=0;j<t.size();j++) s[i+j]=t[j];
		for(i=0;i<s.size();i++) if(s[i]=='?') s[i]='a';
		cout<<s;
	}
	return 0;
}

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

#define int long long

signed main() {
  int n;
  cin >> n;

  vector<int> a(n);
  for ( int i = 0; i < n; i++ ) cin >> a[i];

  if ( a[0] != 0 ) {
    cout << -1 << endl;
    return 0;
  }

  int cnt = 0;
  for ( int i = 1; i < n; i++ ) {
    if ( a[i]-a[i-1] >= 2 ) {
      cout << -1 << endl;
      return 0;
    }
    if ( a[i]-a[i-1] == 1 ) cnt++;
    else cnt += a[i];
  }

  cout << cnt << endl;
  
  return 0;
}


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

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

typedef long long ll;
int mod = 1000000007;

const int INF = 1 << 30;
const ll LLINF = 1LL << 60;

int N, M;
int P[10];
vector<int> sw[10];

bool solve(vector<int> work){
    int cnt_bit = 0;
    rep(i, work.size()) if(work[i] == 1) cnt_bit++;

    int light = 0;
    rep(i, M){
        int acc = 0;
        rep(j, sw[i].size()){
            if(work[sw[i][j]] == 1) acc++;
        }
        if(acc % 2 == P[i]) light++;
    }

    return light == M;
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    rep(i, M){
        int k; cin >> k;
        rep(j, k){
            int s; cin >> s;
            sw[i].push_back(s-1);
        }
    }
    rep(i, M) cin >> P[i];

    int ans = 0;
    int loop = (1 << N);
    rep(i, loop){
        int val = i;
        vector<int> work;
        rep(j, N){
            work.push_back(val%2);
            val/=2;
        }
        if(solve(work)) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#define TEMPLATE_USED
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) for(ll i=0;i<(n);++i)
#define _rep3(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2)(__VA_ARGS__)
#define _repe2(i,n) for(ll i=0;i<=(n);++i)
#define _repe3(i,a,b) for(ll i=(a);i<=(b);++i)
#define repe(...) _overload3(__VA_ARGS__,_repe3,_repe2)(__VA_ARGS__)
#define _rrep2(i,n) for(ll i=(n)-1;i>=0;i--)
#define _rrep3(i,a,b) for(ll i=(b)-1;i>=(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
template<class T>
bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>
bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
template<class T>
using pq=priority_queue<T,vector<T>,greater<T>>;

void solve();

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

void solve(){
    ll n;cin>>n;
    vl c(n-1),s(n-1),f(n-1);
    rep(i,n-1)cin>>c[i]>>s[i]>>f[i];

    rep(i,n-1){
        ll t=0;
        rep(j,i,n-1){
            chmax(t,s[j]);
            t=(t+f[j]-1)/f[j]*f[j];
            t+=c[j];
        }
        cout<<t<<endl;
    }
    cout<<0<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define y_n(ans) cout<<(ans?"Yes":"No")<<endl;

int main() {
    long long a, b, c, d;
    cin >> a >> b >> c >> d;
    long long ans;
    ans = max(a * c, b * d);
    ans = max(ans, a * d);
    ans = max(ans, b * c);
    if (a * b < 0ll || c * d < 0ll) {
        ans = max(ans, 0ll);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3632
function Main(input) {
  var N = parseInt(input.split(" ")[0]);
  var K = parseInt(input.split(" ")[1]);
  
  var output = 0;
  if(N >= K){
     output += (N - K + 1) / N;
     for(var i = 1; i <= K - 1; i++){
       var count = 0;
       var tmp = i;
       while(true){
          if(tmp >= K){
             break;
          }
         tmp = tmp * 2;
         count++;
       }
       output += (1 / N) * (1 / Math.pow(2, count));
     }
  }else{
    for(var i = 1; i <= N; i++){
       var count = 0;
       var tmp = i;
       while(true){
          if(tmp >= K){
             break;
          }
         tmp = tmp * 2;
         count++;
       }
       output += (1 / N) * (1 / Math.pow(2, count));
     }
  }
  console.log(output);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 20808
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
#include<iomanip>
#include<cstring>
#include<string>
#include<set>

#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

using namespace std;
using ll = long long int;

const ll INF = 1<<30;
const ll LINF = 1LL<<60;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(void) {
    char a; cin >> a;
    if (a - 'a' >= 0 && a - 'a' <= 26) cout << 'a' << endl;
    else cout << 'A' << endl;
}

Measured memory_bytes: 3620
#include <iostream>
#include <vector>
#include <cstdio>
#include <map>
#include <algorithm>
#include <cmath>
#include <math.h>
#define DICE 6
using namespace std;
struct Dice {
	int D[6];
	void roll(char C) {
		if (C == 'N') {
			int t = D[0];
			D[0] = D[1];
			D[1] = D[5];
			D[5] = D[4];
			D[4] = t;
		}
		else if (C == 'E') {
			int t = D[0];
			D[0] = D[3];
			D[3] = D[5];
			D[5] = D[2];
			D[2] = t;
		}
		else if (C == 'W') {
			int t = D[0];
			D[0] = D[2];
			D[2] = D[5];
			D[5] = D[3];
			D[3] = t;
		}
		else if (C == 'S') {
			int t = D[0];
			D[0] = D[4];
			D[4] = D[5];
			D[5] = D[1];
			D[1] = t;
		}

	}
};

int main() {
	struct Dice D;
	int a;
	for (unsigned int i = 0; i < 6; i++) {
		cin >> a;
		D.D[i] = a;
	}
	string S; cin >> S;
	for (unsigned int i = 0; i < S.size(); i++) {
		char Ch = S.at(i);
		D.roll(Ch);
	}
	cout << D.D[0] << endl;
}


Measured memory_bytes: 3216
import java.util.*;
import java.io.PrintWriter;

public class Main{
	static int[] c=new int[26];
	static int[] lastD=new int[26];
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		long startTime = System.currentTimeMillis();
		Random rd=new Random();
		Random rc=new Random();
		int d=sc.nextInt();
		for(int i=0; i<26; i++){
			c[i]=sc.nextInt();
		}
		int[][] s=new int[d][26];
		for(int i=0; i<d; i++){
			for(int j=0; j<26; j++){
				s[i][j]=sc.nextInt();
			}
		}
		int maxSati=-1000000;
		int maxInd=-1;
		int[] ans=new int[d];
		TreeSet<Integer>[] memo=new TreeSet[26];
		for(int i=0; i<26; i++){
			memo[i]=new TreeSet<>();
			memo[i].add(0);
			memo[i].add(d+1);
		}
		//j:何日目
		long endSati=0;
		for(int j=0; j<d; j++){
			//i:どの大会をやるか
			for(int i=1; i<=26; i++){
				int sati=0;
				sati+=s[j][i-1];
				sati-=subSati(j+1,i-1);
				if(maxSati<sati){
					maxSati=sati;
					maxInd=i;
				}
			}
			ans[j]=maxInd;
			memo[maxInd-1].add(j+1);
			lastD[maxInd-1]=j+1;
			endSati+=maxSati;
			maxSati=-1000000;
			maxInd=-1;
		}
		long endTime=0;
		while(endTime-startTime<1800){
			int tmpd=rd.nextInt(d)+1;
			int tmpc=rc.nextInt(26)+1;
			long oldSati=endSati;
			endSati-=s[tmpd-1][ans[tmpd-1]-1];
			endSati+=s[tmpd-1][tmpc-1];
			endSati-=c[ans[tmpd-1]-1]*(tmpd-memo[ans[tmpd-1]-1].lower(tmpd))*(memo[ans[tmpd-1]-1].higher(tmpd)-tmpd);
			endSati+=c[tmpc-1]*(tmpd-memo[tmpc-1].lower(tmpd))*(memo[tmpc-1].higher(tmpd)-tmpd);
			if(oldSati<endSati){
				memo[ans[tmpd-1]-1].remove(tmpd);
				memo[tmpc-1].add(tmpd);
				ans[tmpd-1]=tmpc;
			}else{
				endSati=oldSati;
			}
			endTime = System.currentTimeMillis();
		}
		PrintWriter pw=new PrintWriter(System.out);
		for(int i:ans){
			pw.println(i);
		}
		pw.flush();
	}
	static int subSati(int d,int ii){
		int ret=0;
		for(int i=0; i<26; i++){
			if(i==ii) continue;
			ret+=c[i]*(d-lastD[i]);
		}
		return ret;
	}
}


Measured memory_bytes: 59772
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i, n) for (int i = 0; i < ((int)(n)); i++) // 0-indexed昇順

int main()
{
  string A, B, C;
  cin >> A >> B >> C;
  if (A.at(A.size() - 1) == B.at(0) && B.at(B.size() - 1) == C.at(0)) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
int n;
const int maxN = 2e5 + 10;
int x[maxN];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.txt", "r", stdin);
    cin >> n;
    vector < int > gg;
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
        gg.emplace_back(x[i]);
    }
    sort(gg.begin(), gg.end());
    int where = gg[n / 2 - 1];
    for (int i = 1; i <= n; i++) {
        if (x[i] > where) cout << gg[n / 2 - 1] << "\n";
        else cout << gg[n / 2] << "\n";
    }
    return 0;
}

Measured memory_bytes: 4892
from numpy import zeros, maximum
N, T, *AB = map(int, open(0).read().split()) 
dp = zeros(6010, int)
for w, v in sorted(zip(*[iter(AB)] * 2)):
  dp[w:T + w] = maximum(dp[w:T + w], dp[:T] + v)
print(dp.max())

Measured memory_bytes: 12740
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <iomanip>
using namespace std;
#define pb push_back
#define pf push_fron
#define INF 1e9
#define PI acos(-1)
typedef long long ll;

ll a[110], b[110];

int main() {
	
	int q;
	cin >> q;
	for (int i = 0; i < q; i++) {
		ll a, b;
		cin >> a >> b;
		if (a > b)swap(a, b);
		ll ans = 2 * (a - 1);

		ll num = 0;
		for (int j = 29; j >= 0; j--) {
			num += 1 << j;
			if (a + num > b) {
				num -= 1 << j;
				continue;
			}
			int ng = 0;
			for (int x = num / 2 - 2; x <= num / 2 + 2; x++) {
				if (x <= 0 || x > num)continue;
				if ((a + x)*(a + num - x) >= a * b)ng = 1;
			}
			if (ng) num -= 1 << j;
		}
		ans += num;
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void){
	int h[1000],H,w[1000],W,a=0,i=0;
	for(;;){
		scanf("%d %d",&h[i],&w[i]);
		if(h[i]==0&&w[i]==0){
			break;
		}else{
			a++;
		}
		i++;
	}
	
	for(i=0;i<a;i++){
		for(H=0;H<h[i];H++){
			for(W=0;W<w[i];W++){
				if(H==0||W==0||H==h[i]-1||W==w[i]-1){
					printf("#");
				}else{
					printf(".");
				}
				if(W==w[i]-1){
					printf("\n");
				}
			}
			if(H==h[i]-1){
				printf("\n");
			}
		}
	}
	return 0;
}


Measured memory_bytes: 2036
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define FORL(i,x) for(int i=head[x];i;i=nxt[i])
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define PB push_back
#define MP make_pair
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }



int main() {
  int n,k;
  cin >> n >> k;
  int h[n];
  int ans = 0;
  FOR(i,0,n-1){
    int input;
    cin >> input;
    if(input>=k) ++ans;
  }

  cout << ans << endl;

  
  

}



Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007

vector <int> dx = {-1,1,0,0};
vector <int> dy = {0,0,-1,1};
const int maxn = 2e5+ 10;
vector<int> g[maxn];
int par[maxn];
int sz[maxn];
int n,m;
int find_set(int v) {
    if (v == par[v])
        return v;
    return par[v] = find_set(par[v]);
}
void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (sz[a] < sz[b])
            swap(a, b);
        par[b] = a;
        sz[a] += sz[b];
    }
}

int main(){
	cin>>n>>m;
	int a,b;
	for(a=1;a<=n;a++){
		par[a]=a;
		sz[a]=1;
	}
	while(m--){
		cin>>a>>b;
		union_sets(a,b);
	}
	int ans = 0;
	for(int i=1;i<=n;i++){
		if(i==par[i]){
			ans = max(ans, sz[i]);
		}
	}
	cout << ans<<"\n";
	return 0;
}

Measured memory_bytes: 9808
n=int(input())
a=[int(x) for x in input().rstrip().split()]
b=[int(x) for x in input().rstrip().split()]
c=[int(x) for x in input().rstrip().split()]

ans=0
mae=float('inf')
for i in range(n):
    if mae+1==a[i]:
        ans+=c[mae-1]
    ans+=b[a[i]-1]
    mae=a[i]

print(ans)


Measured memory_bytes: 9180
// inputに入力データ全体が入る
function Main(input) {
	input = input.split("\n");
	tmp = input[0].split(" ");
	//文字列から10進数に変換するときはparseIntを使います
	var a = parseInt(tmp[0], 10);
	var b = parseInt(tmp[1], 10);

    var answer = a <= b ? a : a - 1;
	console.log(answer);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr ll mod=1000000007;

int N,M,X,C[12],A[12][12],res;

int main(){
	cin>>N>>M>>X;
	for(int i=0;i<N;i++){
		cin>>C[i];
		for(int j=0;j<M;j++){
			cin>>A[i][j];
		}
	}
	res=2000000000;
	for(int i=0;i<(1<<N);i++){
		int T[12];
		int c=0;
		for(int j=0;j<M;j++){
			T[j]=0;
		}
		for(int j=0;j<N;j++){
			if(i&(1<<j)){
				c+=C[j];
				for(int k=0;k<M;k++){
					T[k]+=A[j][k];
				}
			}
		}
		for(int j=0;j<M;j++){
			if(T[j]<X)c=-1;
		}
		if(c!=-1)res=min(res,c);
	}
	if(res==2000000000)res=-1;
	cout<<res<<endl;
}


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

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if (abs(a - c) <= d || abs(b - a) <= d && abs(c - b) <= d) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
  int n, m, x, y, i;
  int xn, yn, xmax, ymin;
  scanf("%d %d %d %d", &n, &m, &x, &y);

  xmax=x;
  ymin=y;
  
  for(i=0; i < n; i++) {
    scanf("%d", &xn);
    if(xmax < xn) {
      xmax = xn;
    }
    //    printf("xn=%d\n", xn);
  }

  for(i=0; i < m; i++) {
    scanf("%d", &yn);
    if(ymin > yn) {
      ymin = yn;
    }
  }

  if(xmax < ymin) {
    printf("No ");
  }
  printf("War\n");

  //  printf("xmax=%d ymin=%d\n", xmax, ymin);
  
}


Measured memory_bytes: 256
#include <cstdio>

int main(void)
{
    int A,B,N;
    scanf("%d%d%d",&N,&A,&B);
    if(N==1)
    {
        if(A==B)
            printf("1\n");
        else
            printf("0\n");
    }
    else 
    {
        if(A>B)
            printf("0\n");
        else
            printf("%lld\n",(long long )(B-A)*(N-2)+1);
    }
    return 0;
}

Measured memory_bytes: 760
import sys
range = xrange
input = raw_input

mod = 10**9 + 7

n,h,d = [int(x) for x in input().split()]

big = 10**6+10
fac = [1]
while len(fac)<big:
    fac.append(fac[-1] * len(fac) % mod)

cumfac = [0]
for f in fac:
    cumfac.append((cumfac[-1] + f)%mod)

DP = [0]*(h+1)
DP[0] = fac[n]

multi = cumfac[n+1] - cumfac[1]
s = 0
for i in range(1,h):
    s += DP[i-1]
    if i-d-1>=0:
        s -= DP[i-d-1]
    s %= mod
    DP[i] = s*multi % mod

# special
DP[h] = sum(DP[max(0,h-d):h]) % mod

print DP[-1]


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

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

typedef long long ll;
typedef pair<int, int> P;

const int MAX = 1e5 + 5;
const int INF = 1001001001;
const int MOD = 1e9 + 7;

int main(){
    int N, M;
    cin >> N >> M;

    vector<int> p(M);
    vector<string> S(M);
    rep(i, M) cin >> p[i] >> S[i];

    vector<bool> used(N + 1, false);
    vector<int> cntwa(N + 1);
    rep(i, M) {
        int num = p[i];
        if (S[i] == "AC") used[num] = true;
        if (!used[num] && S[i] == "WA") cntwa[num]++;
    }

    int ac = 0, wa = 0;
    rep(i, N + 1) {
        if (used[i]) {
            ac++;
            wa += cntwa[i];
        }
    }

    cout << ac << " " << wa << endl;
}

Measured memory_bytes: 6528
#include<iostream>
using namespace std;
int main(){
    int c[3][3];
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            cin >> c[i][j];
        }
    }
    for(int i=0;i<3;i++){
        for(int j=i+1;j<3;j++){
            for(int k=0;k<3;k++){
                for(int l=k+1;l<3;l++){
                    if(c[i][k]+c[j][l] != c[i][l]+c[j][k]){
                        cout << "No" << endl;
                        return 0;
                    }
                }
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}


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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define mp(a,b) make_pair(a,b)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;

#define INF 1e15

#define MAX_N 1000

ll a,b;

int main(){
	cin.sync_with_stdio(false);
	cin>>a>>b;
	ll res=abs(abs(a)-abs(b));
	if(a*b<0){
		res++;
	}else if(a*b>0){
		if(a>b)res+=2;
	}else{
		if(a>b)res++;
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=100000;

int n;
int val[MAXN];
int cur[MAXN];

bool win() {
	REP(i,n) cur[i]=val[i];
	bool inv=false;
	while(true) {
		int nevn=0,idx=-1; REP(i,n) if(cur[i]%2==0) ++nevn; else idx=i; assert(nevn!=n);
		if(nevn%2==1) return !inv;
		if(nevn!=n-1||cur[idx]==1) return inv;
		--cur[idx]; inv=!inv; int g=cur[0]; FOR(i,1,n) g=gcd(cur[i],g); REP(i,n) cur[i]/=g;
	}
}

void run() {
	scanf("%d",&n);
	REP(i,n) scanf("%d",&val[i]);
	printf("%s\n",win()?"First":"Second");
}

int main() {
	run();
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <math.h>

using namespace std;

int main(){
	string s;
	string t;
	cin >> s >> t;
	int count = 0;

	for (int i = 0; i < 3; ++i){
		if (s[i] == t[i]){
			count += 1;
		}
	}

	cout << count << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main{
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String[] str = s.split("");
		int count = 0;
		for(int i=0;i<str.length;i++){
			if(!(str[i].equals(str[str.length -1 - i]))){
				str[str.length - 1 - i] = str[i]; 
				count++;
			}
		}
		System.out.println(count);
	}
}


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

using namespace std;

typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef long long ll;

const int inf = 1e9;
const ll inf64 = 1e18;

const int N = 2e5 + 5;

int n;
vector<int> g[N];
int dist[N];

pii bfs(int s) {
    fill(dist + 1, dist + n + 1, inf);
    queue<int> q;
    q.push(s);
    dist[s] = 0;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int to : g[v]) {
            if (dist[to] > dist[v] + 1) {
                q.push(to);
                dist[to] = dist[v] + 1;
            }
        }
    }
    int res = -1;
    for (int v = 1; v <= n; v++) {
        if (res == -1 || dist[v] > dist[res]) {
            res = v;
        }
    }
    return make_pair(dist[res], res);
}

int main() {

#ifdef debug
    freopen("input.txt", "r", stdin);
#endif

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    for (int u, v, i = 1; i < n; i++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    int diam = bfs(bfs(1).second).first;

    if (diam == 0) {
        cout << "First\n";
    } else if (diam == 1) {
        cout << "Second\n";
    } else {
        diam -= 2;
        diam %= 3;
        if (diam == 2) {
            cout << "Second\n";
        } else {
            cout << "First\n";
        }
    }

    return 0;
}

Measured memory_bytes: 13556
n,m,k = map(int,input().split())

def cmb(n, r, mod):#コンビネーションの高速計算　
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
mod = 998244353 #出力の制限
N = n #Nの最大値
g1 = [0]*(N+1) #元テーブル(p(n,r))
g1[0] = g1[1] = 1
g2 = [0]*(N+1) #逆元テーブル
g2[0] = g2[1] = 1
inverse = [0]*(N+1) #逆元テーブル計算用テーブル
inverse[0],inverse[1] = 0,1
for i in range(2,N+1):
    g1[i] = (g1[i-1] * i) % mod
    inverse[i] = (-inverse[mod % i] * (mod//i)) % mod
    g2[i] = (g2[i-1] * inverse[i]) % mod

# i組　-> m * (n-1)Ci * (m-1)^(n-1-i)
ans = 0
for i in range(k+1):
    ans += m * cmb(n-1,i,mod) * pow(m-1,n-1-i,mod)
    ans %= mod
print(ans)

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

int main() {
  int N,count=2;
  cin>>N;
  vector<char> S(N);
  rep(i,N) cin>>S.at(i);
  sort(S.begin(),S.end());
  S.push_back(10);
  vector<int> num;
  for(int i=1;i<N+1;i++){
    if(S.at(i)==S.at(i-1)) count++;
    else{
      num.push_back(count);
      count=2;
    }
  }
  int64_t ans=1;
  rep(i,num.size()){
    ans*=num.at(i);
    ans%=MOD;
  }
  cout<<ans-1;
}



Measured memory_bytes: 3652
n=int(input())
A=list(map(int,input().split()))
A.insert(n,0)
A.insert(0,0)
f=0
for i in range(n+1):
    f+=abs(A[i+1]-A[i])
for i in range(1,n+1):
    d=abs(abs(A[i-1]-A[i])+abs(A[i]-A[i+1])-abs(A[i-1]-A[i+1]))
    print(f-d)

Measured memory_bytes: 13920
n = int(input())
a = ord('a')

count = [0]*26
def p():
    return list(map(lambda x: ord(x) - a, list(input())))
s = p()
for s_ in s:
    count[s_] += 1
for _ in range(n-1):
    c = [0]*26
    s = p()
    for s_ in s:
        c[s_] += 1
    for i in range(26):
        count[i] = min(count[i], c[i])
ans = ""
for i in range(26):
    ans += chr(i+a)*count[i]
print(ans)


Measured memory_bytes: 3064
def digit_sum(n):
    result = 0
    while n > 0:
        result += n % 10
        n = n // 10
    return result

N = int(input())
mi = 1e10
for i in range(1, N):
    mi = min(mi, digit_sum(i) + digit_sum(N - i))
print(mi)


Measured memory_bytes: 3316
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>

int main(void){
	int i,j,sum=0,sl;
	
	int n,l;
	
	scanf("%d%d",&n,&l);
	
	sl=l;
	
	for(i=1;i<=n;i++){
		sum+=l;
		l++;
	}
	
	if(sl>=0){
		sum-=sl;
	}else if(sl+n-1>=0){
	}else{
		sum-=sl+n-1;
	}
	
	printf("%d\n",sum);
	
	return 0;
}

Measured memory_bytes: 128
import java.util.*;
import java.text.DecimalFormat;

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

        DecimalFormat df = new DecimalFormat("0.0000000000");
        if (N % 2 == 0) {
            System.out.println("0.5000000000");
        } else {
            int a = (N - 1) / 2;
            double b = (a + 1.0) / N;
            System.out.println(df.format(b));
        }
    }
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
#include<cmath>
using namespace std;
typedef double db;
int main () {
  const db PI = 3.14159265;
  db a, b, x;
  cin >> a >> b >> x;
  db V = a * a * b;
  if (x > V / 2) {
    x = V - x;
    x /= (a * a);
    x *= 2;
    cout << setprecision(13) << (atan(x / a) / PI) * 180  << endl;
  }
  else {
    x /= a;
    db k = x / b;
    k *= 2;
    cout << setprecision(13) << (atan(b / k) / PI) * 180 << endl;
  }
}



Measured memory_bytes: 4024
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n= int(input())
a=list(map(int, input().split()))
b = [0]*(n+1)
c = [0]*(n+1)
su = 0

for x in range(n):
    b[a[x]] += 1

for y in range(len(b)):
    if b[y] >=2:
        c[y]=combinations_count(b[y], 2)
    else:
        c[y]=0
    su += c[y]

for z in range(n):
    if c[a[z]] > 0:
        ans = su - (b[a[z]] - 1)
    else:
        ans = su

    print(str(ans))

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

using namespace std;

#define FOR(i, N) for (int i = 0; i < (int)N; i++)
#define FORIN(i, a, b) for (int i = a; i < (int)b; i++)
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
#define INF (1 << 29)
#define LLINF (1LL << 60)
#define DEBUG(...) debug(__LINE__, ":" __VA_ARGS__)

using Pi = pair<int, int>;
using ll = long long;

string to_string(string s) { return s; }
template <class S>
string to_string(unordered_set<S> s);
template <class S>
string to_string(set<S> s);
template <class S, class T>
string to_string(map<S, T> m);
template <class T>
string to_string(vector<T> v);

template <class S, class T>
string to_string(pair<S, T> p) {
  return "{" + to_string(p.first) + "," + to_string(p.second) + "}";
}

template <class S>
string to_string(unordered_set<S> s) {
  string ret = "{";
  for (S x : s) ret += to_string(x) + ",";
  return ret + "}";
}

template <class S>
string to_string(set<S> s) {
  string ret = "{";
  for (S x : s) ret += to_string(x) + ",";
  return ret + "}";
}

template <class S, class T>
string to_string(map<S, T> m) {
  string ret = "{";
  for (pair<S, T> x : m) ret += to_string(x) + ",";
  return ret + "}";
}

template <class T>
string to_string(vector<T> v) {
  string ret = "{";
  for (int i = 0; i < (int)v.size() - 1; ++i) {
    ret += to_string(v[i]) + ",";
  }
  if (v.size() > 0) {
    ret += to_string(v.back());
  }
  ret += "}";
  return ret;
}

void debug() { cerr << endl; }

template <class Head, class... Tail>
void debug(Head head, Tail... tail) {
  cerr << to_string(head) << " ";
  debug(tail...);
}

void print() { cout << endl; }

template <class Head, class... Tail>
void print(Head head, Tail... tail) {
  cout << to_string(head);
  print(tail...);
}

int main() {
  cin.tie(0);
	int m1,d1,m2,d2;
	cin>>m1>>d1>>m2>>d2;
	if(m1==m2){
		print(0);
	}else{
		print(1);
	}
  return 0;
}

Measured memory_bytes: 256
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x) cout << #x << ' ' << '=' << ' ' << (x) << endl;
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
typedef vector<ll> vec;
typedef vector<P> pvec;
typedef vector<vector<ll>> vvec;
typedef vector<vector<P>> pvvec;
typedef priority_queue<ll> PQI;
typedef priority_queue<P> PQP;
typedef priority_queue<ll,vector<ll>,greater<ll>> PQIG;
typedef priority_queue<P,vector<P>,greater<P>> PQPG;
const vector<int> dx = {0, -1, 0, 1, 1, 1, -1, -1};
const vector<int> dy = {1, 0, -1, 0, 1, -1, 1, -1};
const int MOD = (1000000007);
// const int MOD = (998244353);
// const int INF = (1 << 30);
const int INF = (1LL << 60);
const double EPS = (1 >> 30);
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}
template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; }
template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in : v) is >> in; return is; }



signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
    //---------------------------------------------
    
    int n;
    cin>>n;
    vector<int> a(n);
    REP(i,n) cin >> a[i],a[i]--;
    int ans=0;
    rep(i,n){
        if(i==a[a[i]]) ans++;
    }
    cout<<ans/2<<endl;
    
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include<string.h>
 
typedef long long int ll;
#define all(x) (x).begin(), (x).end()
 
using namespace std;

int nxt() {
    int x;
    cin >> x;
    return x;
}

ll nxtl(){
    ll x;
    cin>>x;
    return x;
}
 
void SieveOfEratosthenes(int n,vector <int> &primes) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          primes.push_back(p);
} 
 
ll max(ll a,ll b)
{
    if(a>b)
        return a;
    return b;
}
 
ll power(ll x, ll y,ll mod) 
{ 
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2,mod); 
    if (y%2 == 0) 
        return (temp*temp)%mod; 
    else
        return (((x*temp)%mod)*temp)%mod; 
} 

vector <vector <int> > g;
int n;
map <pair<int,int>,int> m;
vector <int> color;
void bfs();

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    n=nxt();
    vector <int> row;
    g.resize(n+1,row);
    for(int i=1;i<=n-1;i++)
    {
        int u=nxt(),v=nxt();
        m[{u,v}]=i;
        m[{v,u}]=i;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    color.resize(n);
    bfs();
    int max=1;
    for(int i=1;i<n;i++)
        if(color[i]>max)
            max=color[i];
        cout<<max<<endl;
    for(int i=1;i<=n-1;i++)
        cout<<color[i]<<endl;

    
    
    

    return 0;   
}

void bfs()
{
    vector <bool> visited;
    visited.resize(n+1,0);
    queue <int> q;
    visited[1]=1;
    vector <int> vertex_color(n+1);
    vertex_color[1]=0;
    q.push(1);
    while(q.size())
    {
        int x=q.front();
        q.pop();
        int cur=1;
        for(int i=0;i<g[x].size();i++)
        {
            if(!visited[g[x][i]])
            {
                visited[g[x][i]]=1;
                if(cur==vertex_color[x])
                    cur++;
                vertex_color[g[x][i]]=cur++;
                color[m[{x,g[x][i]}]]=vertex_color[g[x][i]];
                q.push(g[x][i]);
            }
        }

    }
}


 
 


Measured memory_bytes: 19200
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include<iostream>
#include<algorithm>//next_permutation

using namespace std;

int main() {
	int A, B;
	cin >> A >> B;
	int answer = -1;
	int D, E;
	for (int i = 0;i < 100000;i++) {
		D = i * 0.08;
		E = i * 0.1;
		if (D == A && E == B) {
			answer = i;
			break;
		}
	}
	cout << answer << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#define INF 10000000
#define N 101

int matrixChainOrder(int *);

int n;

int main()
{
  int i, p[N];
  
  scanf("%d", &n);
  
  for(i = 0; i < n; i++){
    scanf("%d%d", &p[i], &p[i+1]);
  }
  
  printf("%d\n", matrixChainOrder(p));
  
  return 0;
}


int matrixChainOrder(int *p)
{
  int i, j, l, k, q;
  int m[N][N];
  
  n = n+1;

  for(i = 1; i < n; i++) m[i][i] = 0;
  for(l = 2; l < n; l++){
    for(i = 1; i < n-l+1; i++){
      j = i+l-1;
      m[i][j] = INF;
      for(k = i; k <= j-1; k++){
	q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
	if(m[i][j] > q) m[i][j] = q;
      }
    }
  }

  return m[1][n-1];
}

Measured memory_bytes: 632
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int k = Integer.parseInt(in.readLine());
    String str[] = in.readLine().split(" ");
    int a = Integer.parseInt(str[0]);
    int b = Integer.parseInt(str[1]);
    in.close();
    int largest = (b/k) * k;
    System.out.println(a<=largest?"OK":"NG");
  }
}

Measured memory_bytes: 32400
import sys
input = sys.stdin.readline


x = int(input())

prime = [True] * (100004)
prime[2] = True

def e_prime(x):
	i = 2
	flag = False
	while True:
		if(i==x):flag=True
		if prime[i]:
			if(flag==True):
				return i
			else:
				for j in range(i**2,len(prime),i):
					prime[j]=False
		i+=1

print(e_prime(x))

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

int main(){
  char s[3],t[3];
  cin >> s >> t;
  int ans = 0;
  for(int i=0; i<3; i++){
    if(s[i]==t[i]) ans++;
  }
  cout << ans << endl;
  return 0;
}

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


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

void solve() {
    int N; cin >> N;
    cout << (N+2-1)/2 << "\n";
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

Measured memory_bytes: 256
n = int(input())
A = list(map(int,input().split()))

A.sort()
#print(A)

ans = 0
size = 0
for i in range(n):
    if A[i] <= 2*size:
        ans += 1
    else:
        ans = 1
    size = A[i] + size

print(ans)

Measured memory_bytes: 85544
#include<stdio.h>
#include<string.h>

int main(void)
{
    long int n,k,l, i;
	k = 0;
	l = 0;
	long int num;
	scanf("%ld", &n);
	for (i = 0; i < n; i++)
	{
		scanf("%ld", &num);
		if (num % 4 == 0)
		{
			k++;
		}
		else if (num % 2 == 0)
		{
			l++;
		}


	}
	for (i = 0; i < n; i++)
	{
		
	}
	for (l; l >= 2; l--)
	{
		k++;
		l--;
	}
	if (k >=(n / 2))
	{
		printf("Yes\n");
	}
	else
	{
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 128