akhauriyash/Code-Regression huggingface dataset:
def x2(n)
  rn=(1+Math.sqrt(1+4*n)).floor/2
  divisors=[]
  factors=Hash.new(0)
  othersum=0
  n2=n
  (2..rn).each do |i|
    if n%i==0
      othersum+=i-1
      divisors << i
    end
    while n2%i==0
      n2/=i
      factors[i]+=1
    end
  end
  factors[n2]+=1 if n2!=1
  divisorssum=1
  divisorsnum=1
  factors.each do |f,m|
    divisorsnum*=m+1
    divisorssum*=(f**(m+1)-1)/(f-1)
  end
  return divisorssum-divisorsnum-othersum
end

puts x2(gets.to_i)

Measured memory_bytes: 1788
while line = gets.split
  if line[1] == "?"
    break
  elsif line[1] == "+"
    puts line[0].to_i + line[2].to_i
  elsif line[1] == "-"
    puts line[0].to_i - line[2].to_i
  elsif line[1] == "*"
    puts line[0].to_i * line[2].to_i
  else
    puts line[0].to_i / line[2].to_i
  end
end

Measured memory_bytes: 8616
#include<stdio.h>
int main(){
    int S,h,m,s;
    scanf("%d",&S);
    h=S / 3600;
    m=(S - h * 3600) / 60;
    s=S - h * 3600 - m * 60;
    printf("%d:%d:%d\n",h,m,s);
    return 0;
}


Measured memory_bytes: 2000
#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int main()
{
	string s;
	cin >> s;
	int count = 0;
  	for(int i = 0; i < 3; i++){
      if(s[i] == '1'){
        count++;
      }
    }
  cout << count;
  return 0;
}

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

int main() {
    int x;
    cin >> x;
    int a=x/500;
    x-=500*a;
    int b = x/5;
    cout << a*1000+b*5 << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>
#include<queue>

using namespace std;

int main()
{
	int n;
	cin >> n;
	string s,t;
	cin >> s >> t;
	for(int i=0;i<n;i++)
		cout << s[i] << t[i];
	cout << endl;




}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, x, n) for(int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long long ll;

int main() {
    int N;
    cin >> N;
    vector<int> A1(N);
    vector<int> A2(N);
    vector<int> vec(N);

    rep(i,N)
    cin >> A1.at(i);

    rep(i,N)
    cin >> A2.at(i);

    rep(i,N)
    {
        rep(j,N)
        {
        if(j<=i)
        vec.at(i) += A1.at(j);
        if(j>=i)
        vec.at(i) += A2.at(j);
        }
    }
sort(vec.begin(), vec.end()); //配列変数vecをソートする
reverse(vec.begin(), vec.end()); //配列変数vecの要素を逆転する

int ans = vec.at(0);
    



cout << ans<< endl;

}






Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
int a[100005];
int b[100005] ,c[100005];
int maxn = -1;

int max(int a,int b){ return a>b?a:b; }

int getCnt(int n,int d[]){
    int res = 0, counter = 0;
    int p = 1;
    while(p<=n){
        int np = p;
        while(np+1<=n && d[np+1]==d[p]) np++;
        int cnt = np-p+1;
        if(cnt>res){
            counter = 1;
            res = cnt;
            maxn = d[p];
        }
        else if(cnt==res) counter++;
        p = np+1;
    }
    if(counter==1) return -res;
    else return res;
}

int getSecond(int n,int d[],int maxn){
    int res = 0;
    int p = 1;
    while(p<=n){
        int np = p;
        while(np+1<=n && d[np+1]==d[p]) np++;
        if(np-p+1!=maxn) res = max(res,np-p+1);
        p = np+1;
    }
    return res;
}

int main(){
    int n;
    scanf("%d",&n);
    int sizeB = 0, sizeC = 0;
    for(int i = 1; i <= n; i++){
        int u;
        scanf("%d",&u);
        if(i%2) b[++sizeB] = u;
        else c[++sizeC] = u;
    } 
    std::sort(b+1,b+1+sizeB);
    std::sort(c+1,c+1+sizeC);
    int ub = -1, uc = -1;
    int cnt0 = getCnt(n/2,b);
    ub = maxn;
    int cnt1 = getCnt(n/2,c);
    uc = maxn;
    if(cnt0<0 && cnt1<0 && ub==uc){
        //printf("?\n");
        cnt0 *= -1, cnt1 *= -1;
        int cnt2 = getSecond(n/2,b,cnt0);
        int cnt3 = getSecond(n/2,c,cnt1);
        //printf("%d %d %d %d\n",cnt0,cnt1,cnt2,cnt3);
        int minus = max(cnt0+cnt3,cnt1+cnt2);
        printf("%d\n",n-minus);
    }
    else{
        if(cnt0<0) cnt0 *= -1;
        if(cnt1<0) cnt1 *= -1;
        printf("%d\n",n-cnt0-cnt1);
    }
    
    return 0;
}


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

using namespace std;

#define ll  long long
#define rep(i,a,b)  for(ll i=a;i<b;i++)

void solve()
{
    ll n,m,k,x,y=0,res=0,l,cnt=0,sum=0,z,sum1=0,cnt1=0,h,res1;
    cin>>n;
    ll pre[n],suf[n];
    ll ar[n];
    
	rep(i,0,n)
       cin>>ar[i];
    
	pre[0]=ar[0];suf[n-1]=ar[n-1];
	rep(i,1,n) 
	   pre[i]=__gcd(pre[i-1],ar[i]);
    
	for(ll i=n-2;i>=0;i--) 
	   suf[i]=__gcd(ar[i],suf[i+1]);
    
	ll ans=max(suf[1],pre[n-2]); 
    
	rep(i,1,n)
       ans=max(ans,__gcd(pre[i-1],suf[i+1]));
    
	cout<<ans;
}

int main()
{
    ll t=1;
    while(t--)
        solve();
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,D;
  cin >> N >> D;
  vector<vector<int>> v(N,vector<int>(D));
  for (int i=0;i<N;i++){
    for (int j=0;j<D;j++){
      cin >> v[i][j];
    }
  }
  int ans=0;
  for (int i=0;i<N-1;i++){
    for (int j=i+1;j<N;j++){
      int sum=0;
      for (int k=0;k<D;k++){
        sum+=(v[i][k]-v[j][k])*(v[i][k]-v[j][k]);
      }
      double dis1=sqrt(sum);
      int dis2=sqrt(sum);
      if (dis1==dis2){
        ans++;
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
function Main(input) {
  input=input.split("\n");
  if(input[input.length-1]===''){
    input.pop();
  }
  const N=input[0].split(' ')[0]-0;
  var array=input[1].split(' ').map((e,i)=>{
    return e-i-1;
  }).sort((a,b)=>{
    return a-b;
  });
  console.log(array.reduce((acc,cur)=>{
    return acc+Math.abs(cur-array[Math.floor(array.length/2)]);
  },0));

}

//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

function permutation(n,k){
    var ret=[[]];
    var next;
    for(var i=0;i<k;i++){
        next=[];
        ret.forEach(e=>{
            for(var k=1;k<=n;k++){
                if(!e.includes(k)){
                    next.push(e.concat([k]));
                }
            }
        });
        ret=next.concat([]);
    }
    return ret;
}

Measured memory_bytes: 53564
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod998 = 998244353;
const ll intmax = 2147483647;
const ll llmax = 9223372036854775807;
const char sp = ' ';

ll K, A, B;

int main() {
	cin >> K >> A >> B;
	if (A + 2 <= B) {
		if (K + 1 <= A) {
			cout << K + 1 << endl;
		}
		else {
			K -= A - 1;
			cout << A + (B - A)*(K / 2) + K % 2 << endl;
		}
	}
	else {
		cout << K + 1 << endl;
	}
}

Measured memory_bytes: 256
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

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

	long n, T;
	String poly;

	void run(){
		n=sc.nextLong();
		T=sc.nextLong();
		poly=sc.next();
		solve();
	}

	void solve(){
		double fT=0;
		for(char c : poly.toCharArray()){
			if(Character.isDigit(c)){
				double a=1;
				for(int i=0; i<c-'0'; i++){
					a*=n;
				}
				fT+=a*T;
			}
		}
		println(fT>1e9?"TLE":((int)fT+""));
	}

	void println(String s){
		System.out.println(s);
	}

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

Measured memory_bytes: 17328
n=int(input())
lst=[]
for i in range(n):
	a,b=map(int,input().split())
	lst.append((b,a))

#dictは同じキーが登場すると上書きしてしまうので工夫が必要
#タプルのリストのままやるぞ

lst.sort()

#print(lst)
#=>[(4, 2), (8, 1), (9, 1), (9, 4), (12, 3)]
#(deadline,time)の順で配置されている

result='Yes'
time=0 #i番目にやる仕事まで終わらせるのにかかる時間

for i in range(n):
	time+=lst[i][1]
	if time>lst[i][0]:
		result='No'

print(result)

Measured memory_bytes: 29456
#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
using ll = long long;
using ull = unsigned long long;

int main(){
    string S, T;
    cin >> S >> T;
    unsigned dif = S.size() - T.size(), tsz = T.size(), candidate = 0, answer = tsz;
    for(unsigned i = 0;i <= dif;i++){
        candidate = 0;
        for(unsigned j = 0;j < tsz;j++) if(S[i+j] != T[j]) candidate++;
        if(answer > candidate) answer = candidate;
    }
    printf("%u\n", answer);
	return 0;
}

Measured memory_bytes: 3700
import java.util.Scanner;
class Main{
	public static void main(String[] args)
    {
      Scanner sc=new Scanner(System.in);
      int n=sc.nextInt();
      int n500=0,n5=0;
      n500=n/500;
      n=n%500;
     // System.out.println(n);
      n5=n/5;
      int happy=n500*1000+n5*5;
      System.out.println(happy);
      
    }
}

Measured memory_bytes: 21588
#include <iostream>
#include <istream>
#include <string>
#include <vector>
using namespace std;
int main(void){
    int A,B;
  	int sum=0;
    cin >> A >> B;
  	if(A>B) { 
      sum+=A;
      --A;
      if(A>=B) cout << sum+A << "\n";
      if(A<B) cout << sum+B << "\n";
      return 0;
    }
  	else if(A<B){
      sum+=B;
      --B;
      if(B>=A) cout << sum+B << "\n";
      if(B<A) cout << sum+A << "\n";
      return 0;
    }
  	else {
      cout << A+B << "\n";
      return 0;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int dp[3001][3001];
char ans[3000];
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    string a,b;
    cin>>a>>b;
    int n=a.size(),m=b.size();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i-1]==b[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    int i=n,j=m,sz=0;
    while(i&&j)
    {
        if(a[i-1]==b[j-1])
        {
            ans[sz++]=a[i-1];
            --i,--j;
        }
        else if(dp[i][j]==dp[i-1][j])
            --i;
        else
            --j;
    }
    for(int i=sz-1;i>=0;i--)
        cout<<ans[i];
    cout<<flush;
    return 0;
}


Measured memory_bytes: 35456
s = list(input())
t = list(input())

capable = []
for i in range(len(s) - len(t) + 1):
    restore = s.copy()
    flg = True
    for i_o, idx in enumerate(range(i, i + len(t))):
        if s[idx] == '?' or s[idx] == t[i_o]:
            restore[idx] = t[i_o]
            continue
        else:
            flg = False
    if flg:
        capable.append(restore)

if len(capable):
    print(''.join(capable[-1]).replace('?', 'a'))
else:
    print('UNRESTORABLE')

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

int n,x,y;
int Min[2005];
int cnt[2005];

int main(){
	scanf("%d%d%d",&n,&x,&y);
	for(int i = 1; i < n; i++){
		memset(Min, 0, sizeof(Min));
		for(int j = i + 1; j <= n; j++) Min[j] = j - i;
		Min[y] = min(Min[y], abs(x - i) + 1);
		for(int Pos = y - 1; Pos > i; Pos--) Min[Pos] = min(Min[Pos], abs(x - i) + abs(y - Pos) + 1 );
		for(int Pos = y + 1; Pos <= n; Pos++) Min[Pos] = min(Min[Pos], abs(Pos - y) + 1 + abs(x -i));
		for(int j = i + 1;j <= n; j++) cnt[Min[j]]++;
	}
	for(int i = 1; i < n; i++) printf("%d\n",cnt[i]);
	return 0;
} 

Measured memory_bytes: 256
N,W = [int(s) for s in input().split()]
dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(1,N+1):
    w, v = [int(s) for s in input().split()]
    for sum_w in range(W+1):
        if sum_w - w >= 0:
            dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][sum_w-w] + v)
        else:
            dp[i][sum_w] = dp[i-1][sum_w]
print(dp[N][W])

Measured memory_bytes: 119916
#include <bits/stdc++.h>
#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define PRINT(x) cout << (x) << "\n"
using namespace std;
using ll = long long; using pint = pair<int, int>; using pll = pair<ll, ll>;
template<typename T> auto compare = [](T x, T y) -> bool{return (x < y);};
const long long MOD = 1000000007;

signed main(){
    ll X;
    cin >> X;
    if(X >= 30) PRINT("Yes");
    else PRINT("No");
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll L, R;
    cin >> L >> R;
    ll nin = 2019;
    ll nax = 0;
    int mod = 2019;
    for(ll i=0; i<=R-L && i<mod; i++)
    {
        nin = min(nin, (i+L)%mod);
        nax = max(nax, (i+L)%mod);
    }
    int ans = 2019;
    for(int i=nin; i<=nax; i++)
    {
        for(int j=i+1; j<=nax; j++)
        {
            ans = min(ans, ((i*j)%mod));
        }
    }
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> mp;
#define inf 1e9

struct edge{
    ll to,cap,cost,rev;
    edge(){}
    edge(ll to,ll cap,ll rev):to(to),cap(cap),rev(rev){}
    edge(ll to,ll cap,ll cost,ll rev):to(to),cap(cap),cost(cost),rev(rev){}
};

typedef vector<vector<edge> > graph;
struct Dinic{
    ll n;
    graph g;
    vector<ll> level,iter;
    Dinic() {}
    Dinic(ll n): n(n){
	g.resize(n);
	level.resize(n);
	iter.resize(n);
    }
    void add_edge(ll from, ll to, ll cost){
	g[from].push_back(edge(to,cost,g[to].size()   ) );
	g[to].push_back(edge(from,0,g[from].size() -1 ) );
    }
    void bfs(ll s){
	fill(level.begin(),level.end(),-1);
	queue<ll> q;
	q.push(s);
	level[s] = 0;
	while(!q.empty()){
	    ll tmp = q.front();
	    q.pop();
	    for(ll i=0;i<g[tmp].size();i++){
		edge &e = g[tmp][i];
		if(e.cap > 0 && level[e.to] < 0){
		    level[e.to] = level[tmp] + 1;
		    q.push(e.to);
		}
	    }
	}
    }
    ll dfs(ll v,ll t,ll f){
	if( v == t ) return f;
	for(ll &i = iter[v]; i < g[v].size() ; i++){
	    edge &e = g[v][i];
	    if( e.cap > 0 && level[v] < level[e.to] ){
		ll d = dfs(e.to, t, min(f,e.cap) );
		if( d > 0 ){
		    e.cap -= d;
		    g[e.to][e.rev].cap += d;
		    return d;
		}
	    }
	}
	return 0;
    }
    ll max_flow(ll s,ll t){
	ll flow = 0, f;
	while(1){
	    bfs(s);
	    if(level[t] < 0) return flow;
	    fill(iter.begin(),iter.end() , 0);
	    for(f = dfs(s,t,inf); f > 0; f = dfs(s,t,inf) ) flow += f;
	}
    }
};

struct Dinic_lr{
    Dinic f;
    ll S,T,sum_lb;
    Dinic_lr(){}
    Dinic_lr(ll n): f(n+2),S(n),T(n+1),sum_lb(0){}
    void add_edge(ll u,ll v,ll lb,ll ub){
	if( u== v || ub == 0)return ;
	f.add_edge(u,v,ub-lb);
	f.add_edge(S,v,lb);
	f.add_edge(u,T,lb);
	sum_lb += lb;
    }
    ll max_flow(ll s,ll t){
	//この順番で流すことがいい，Sから流すことで流す流量を先に減らせる．
	//そのことで通れなくなるパスは，その頂点から直接Tに向かうことができる．
	// s->T , S->tはよくわからない	
       
        ll a = f.max_flow(S,T);
	ll b = f.max_flow(s,T);
        ll c = f.max_flow(S,t);
        ll d = f.max_flow(s,t);
      
	
	//a+c は　最小流量が流れるか? a+b は最小流量が戻るか?
	return ( a + c == sum_lb && a + b == sum_lb ) ? b+d: -1;
    }
};


int main(){
    ll n,m;
 while(1){
    cin>>n>>m;
   if(n==0)break;
    vector<ll> u(m),v(m);
    for(ll i=0;i<m;i++){
	cin>>u[i]>>v[i];
	u[i]--,v[i]--;
    }
    ll p = 0,q = n;
    ll l=0;
    for(ll r = 0; r <= n; r++){
     while( l <= r ){
      Dinic_lr f(n+m+2);
      ll S = n+m,T = n+m+1;
      for(ll i=0;i<m;i++){
       f.add_edge(S,i,1,1);
       f.add_edge(i,m+u[i],0,1);
       f.add_edge(i,m+v[i],0,1);
      }
      for(ll i=0;i<n;i++){
       f.add_edge(m+i,T,l,r);
      }
      ll flow = f.max_flow(S,T);
      if( flow !=  m ){
       break;
      }
      p = l;
      q = r;
      l++;

     }
    }
    cout<<p<<' '<<q<<endl;
 }

    //cout<<f.max_flow(0,v-1)<<endl;
    
    return 0;
}



Measured memory_bytes: 5828
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
#define ll long long
#define rep(i,n) for (int i = 0; i < n; i++)
#define MOD (1000000007)
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()

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

int gcd(int a, int b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}

const ll INF = 1LL << 60;

int main(){
  int n, a, b; cin >> n >> a >> b;
  std::cout << min(a,b) << " " << max(a+b-n,0) << '\n';
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
	
	int W,H,x,y,r;

	scanf("%d %d %d %d %d\n",&W,&H,&x,&y,&r);

	if(W<(x+r) || H<(y+r) || 0>(x-r) || 0>(y-r))
		printf("No\n");
	
	else
		printf("Yes\n");

	return 0;
}

Measured memory_bytes: 584
#include <stdio.h>

int main() {
	unsigned int n;
	unsigned int k;
	unsigned int s;

	scanf("%u%u", &n, &k);

	s = k;
	k--;

	for(int i = 1; i < n; i++) {
		s *= k;
	}

	printf("%u\n", s);
}

Measured memory_bytes: 128
#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 <iomanip> // fixed, setprecision 
#include <math.h> // double sqrt
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
//最大公約数
unsigned long gcd(unsigned long a, unsigned long b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}



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


int main(){
   unsigned long A,B,C,D;
   cin>>A>>B>>C>>D;
   unsigned long c,d,cc,dd,E,e,ee;
   if(A%C==0)c=A/C-1;
   else c=A/C;
   if(A%D==0)d=A/D-1;
   else d=A/D;
   E=lcm(C,D);
   if(A%E==0)e=A/E-1;
   else e=A/E;

   cc=B/C;
   dd=B/D;
   ee=B/E;

   cout<<-cc+c-dd+d+ee-e+B-A+1;
   return 0;
   
}

Measured memory_bytes: 3104
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
template <typename T> 
using lim = numeric_limits<T>;
template <typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using indexed_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct barrier{
    ll x, y, r;
};

const int N = 1005;
barrier b[N];
vector<pair<int, ld>> graph[N];

int n;
ld dijkstra(int s){
    priority_queue<pair<ld, int>, vector<pair<ld, int>>, greater<pair<ld,int>> > pq;
    vector<ld> dist(n+2, 1e18);

    pq.push({0, s});
    dist[s] = 0;
    while(!pq.empty()){
        int u = pq.top().second;
        pq.pop();
        for (auto p : graph[u]){
            int v = p.first;
            ld w = p.second;
            if (dist[v] > dist[u]+w){
                dist[v] = dist[u]+w;
                pq.push({dist[v], v});
            }
        }
    } 
    return dist[n+1];
}

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

    int xs, ys, xt, yt;
    cin >> xs >> ys >> xt >> yt;
    cin >> n;

    b[0] = {xs,ys, 0};
    b[n+1] = {xt, yt, 0};
    for (int i = 1; i <= n; i++){
        int x, y, r;
        cin >> x >> y >> r;
        b[i] = {x,y,r};
    }

    for (int i = 0; i < n+2; i++){
        for (int j = i+1; j < n+2; j++){
            ld dist = sqrtl((b[i].x-b[j].x)*(b[i].x-b[j].x)+(b[i].y-b[j].y)*(b[i].y-b[j].y));
            ld w = dist-(b[i].r+b[j].r);
            w = max((ld)0, w);
            graph[i].push_back({j, w});
            graph[j].push_back({i, w});
        }
    }

    cout << setprecision(10) << fixed << dijkstra(0) << "\n";
}

Measured memory_bytes: 44124
#include <iostream>
 
using namespace std;
 
using int64 = long long;
 
int main()
{
  int64 A, B, C, D, E, F;
  cin >> A >> B >> C >> D >> E >> F;
 
  double ret = 0;
  int64 aa = 100 * A, bb = 0;
  for(int64 a = 0; a <= 30; a += A) {
    for(int64 b = 0; b <= 30; b += B) {
      int64 water = 100 * a + 100 * b;
      for(int64 c = 0; c <= 3000; c += C) {
        for(int64 d = 0; d <= 3000; d += D) {
          int64 solid = c + d;
          if(water + solid > F) continue;
          if((a + b) * E < solid) continue;
          if(100 * solid > ret * (water + solid)) {
            ret = (100.0 * solid) / (water + solid);
            aa = water + solid;
            bb = solid;
          }
        }
      }
    }
  }
 
  cout << aa << " " << bb << endl;
}

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

const int HIGHEST_RATE = 1000000000;
const int LOWEST_RATE  = 1;

/* ALDS 1_1_D: Maximum profit */
int main() {
    int n, rate, profit;
    int max_profit  = LOWEST_RATE - HIGHEST_RATE;
    int lowest_rate = HIGHEST_RATE * 2;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> rate;
        profit = rate - lowest_rate;

        if (max_profit < profit) {
            max_profit = profit;
        }
        if (rate < lowest_rate) {
            lowest_rate = rate;
        }
    }

    cout << max_profit << endl;
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
using namespace std;
#define fix(f,n) std::fixed<<std::setprecision(n)<<f
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long int ll;
typedef unsigned long long int ull;
#define vi vector<int>
#define pii pair<int,int>
#define vii vector<pii>
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a>b)?b:a)
#define max3(a,b,c) ((a>b)?(a>c)?a:c:(b>c)?b:c)
#define min3(a,b,c) ((a<b)?(a<c)?a:c:(b<c)?b:c)
#define REP(i,a,n) for(ll i=a;i<n;i++)
#define pb push_back
#define mp make_pair
#define mod 998244353
#define MAX 1000000001

int main(){
	fast;
	int test=1;
	//cin >> test;
	while(test--){
	    ll d,t,s;
	    cin >> d >> t >> s;
	    ll temp;
	    if(d%s==0){
	        temp=d/s;
	    }else{
	        temp=d/s;
	        temp++;
	    }
	    if(temp<=t){
	        cout << "Yes" << endl;
	    }else{
	        cout << "No" << endl;
	    }
	}
	return 0;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
int n,ans,a[10005];
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
	cin>>a[i];
	for(int j=0;a[i]%2==0;j++)
	{
	ans++;
	a[i]/=2;
	} 
	}
	cout<<ans<<endl;	
	
    return 0;
	} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using ld = long double;
const int INF = (1<<30)-1;
const long long LINF = (1LL<<62)-1;
const long double PI = acos(-1.0L);
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s, t;
  cin >> s >> t;
  sort(s.begin(), s.end());
  sort(t.begin(), t.end());
  reverse(t.begin(), t.end());
  if (s < t)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}

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

// @@ !! LIM()

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll N; cin >> N;
  vector<ll> X(N), Y(N);
  vector<char> U(N);
  map<ll, vector<ll>> mpX, mpY, mpP, mpM;
  ll crash = LLONG_MAX;
  for (ll i = 0; i < N; i++) {
    ll x, y; cin >> x >> y;
    char u; cin >> u;
    X.at(i) = x;
    Y.at(i) = y;
    U.at(i) = u;
    if (u == 'U' || u == 'D') mpX[x].push_back(i);
    if (u == 'L' || u == 'R') mpY[y].push_back(i);
    mpP[y + x].push_back(i);
    mpM[y - x].push_back(i);
  }
  for (auto [x, v] : mpX) {
    sort(v.begin(), v.end(),
	 [&](ll i, ll j) -> bool { return Y.at(i) < Y.at(j); });
    ll up = -1;
    for (ll i : v) {
      if (U.at(i) == 'U') {
	up = Y.at(i);
      }else {
	if (up >= 0) {
	  crash = min(crash, (Y.at(i) - up) * 5);
	}
      }
    }
  }
  for (auto [y, v] : mpY) {
    sort(v.begin(), v.end(),
	 [&](ll i, ll j) -> bool { return X.at(i) < X.at(j); });
    ll right = -1;
    for (ll i : v) {
      if (U.at(i) == 'R') {
	right = X.at(i);
      }else {
	if (right >= 0) {
	  crash = min(crash, (X.at(i) - right) * 5);
	}
      }
    }
  }
  for (auto [p, v] : mpP) {
    sort(v.begin(), v.end(),
	 [&](ll i, ll j) -> bool { return X.at(i) < X.at(j); });
    ll down = LLONG_MIN;
    ll right = LLONG_MIN;
    for (ll i : v) {
      if (U.at(i) == 'R') right = X.at(i);
      if (U.at(i) == 'D') down = X.at(i);
      if (U.at(i) == 'U' && right > LLONG_MIN) {
	crash = min(crash, (X.at(i) - right) * 10);
      }
      if (U.at(i) == 'L' && down > LLONG_MIN) {
	crash = min(crash, (X.at(i) - down) * 10);
      }
    }
  }
  for (auto [p, v] : mpM) {
    sort(v.begin(), v.end(),
	 [&](ll i, ll j) -> bool { return X.at(i) < X.at(j); });
    ll up = LLONG_MIN;
    ll right = LLONG_MIN;
    for (ll i : v) {
      if (U.at(i) == 'R') right = X.at(i);
      if (U.at(i) == 'U') up = X.at(i);
      if (U.at(i) == 'D' && right > LLONG_MIN) {
	crash = min(crash, (X.at(i) - right) * 10);
      }
      if (U.at(i) == 'L' && up > LLONG_MIN) {
	crash = min(crash, (X.at(i) - up) * 10);
      }
    }
  }

    
  if (crash == LLONG_MAX) {
    cout << "SAFE" << endl;
  }else {
    cout << crash << endl;
  }

  return 0;
}



Measured memory_bytes: 71412
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#define rep(i, n) for(int i = 0; i<n; i++)
#define rep_s(i, start, n) for(int i= start;  i<n; i++)
#define ALL(a) (a).begin(), (a).end()
string alphabet_upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string alphabet_lower  = "abcdefghijklmnopqrstuvwxyz";

/*
using edge = struct {int to; ll cost;};
vector<edge> tree[limit];
ll depth[limit];

void dfs(int v, int p, ll d){
  depth[v] = d;
  //cout <<"v: " << v << endl;
  for (auto &e: tree[v]){
    //cout << "e.to: " << e.to << endl;
    if (e.to == p) continue;
    dfs(e.to, v, d+e.cost);
  }
}
*/

int main(void){
  int a, b, c;
  cin >> a >> b >> c;
  if (a==b ) cout << c << endl;
  else if(a == c) cout << b << endl;
  else cout << a << endl;

}


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

char txt[100001];
int dp[100001];
int main(){
	int N,Q;
	cin >> N >> Q;
	cin >> txt;
	for(int i=1;i<N;i++){
		if(txt[i]=='C'&&txt[i-1]=='A') dp[i]++;
		dp[i]+=dp[i-1];
	}
	while(Q--){
		int l,r;
		cin >> r >> l;
		cout << dp[l-1]-dp[r-1] << "\n";
	}
}



Measured memory_bytes: 1280
#include <bits/stdc++.h>
    using namespace std;
     
    int N;
    int x[10], y[10];
     
    double dist(int i, int j) {
        double dx = x[i] - x[j];
        double dy = y[i] - y[j];
        return pow(dx * dx + dy * dy, 0.5);
    }
     
    void solve() {
        cin >> N;
        for(int i = 1; i <= N; i++) cin >> x[i] >> y[i];
        double sum = 0.0;
        vector<int> v(N);
        for(int i = 0; i < N; i++) v[i] = i + 1;
        do {
            for(int i = 0; i < N - 1; i++) sum += dist(v[i], v[i+1]);
        } while(next_permutation(v.begin(), v.end()));
        int Factorial = 1;
        for(int i = 2; i <= N; i++) Factorial *= i;
        cout << fixed << setprecision(10) << sum / Factorial << endl;
        return;
    }
     
    int main() {
        solve();
        return 0;
    }

Measured memory_bytes: 256
/// author: Mr.Hakimov

#include <bits/stdc++.h>
#include <chrono>

#define fi first
#define se second
#define pb push_back
#define pf push_front
#define Pb pop_back
#define Pf pop_front
#define all(x) (x).begin(), (x).end()
#define fin(s) freopen(s, "r", stdin);
#define fout(s) freopen(s, "w", stdout);

using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

typedef long long ll;
typedef long double ld;

int TN = 1;

void solve() {
	string s1;
	string s2;
	
	cin >> s1 >> s2;
	
	if (s2.substr(0, s1.size()) == s1 && (int) s1.size() + 1 == (int) s2.size()) {
		cout << "Yes";
	} else {
		cout << "No";
	}
}

int main() {
    auto start = chrono::steady_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    /// =========================================
    /// fin("input.txt"); fout("output.txt");
    /// fin("file.in"); fout("file.out");
    /// cin >> TN;
    /// =========================================

    while (TN--) {
        solve();
    }

    auto finish = chrono::steady_clock::now();
    auto elapsed_ms = chrono::duration_cast<chrono::milliseconds>(finish - start);
    cerr << endl << "Time: " << elapsed_ms.count() << " ms\n";

    return 0;
}


Measured memory_bytes: 3644
n = int(input())
playlist = []
for i in range(n):
    playlist.append(input().split())
x = input()

start = 0
ans = 0
for i in range(n):
  if playlist[i][0] == x:
    start = i+1
for i in range(start,n):
  ans += int(playlist[i][1])
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <functional>
using namespace std;
using Int = long long;
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,f,t) for(int i=f;i<t;i++)
#define P(r) do{for(auto i:r){cout<<i<<' ';}cout<<'\n';}while(0)
int main()
{
    int N, Ma, Mb; cin >> N >> Ma >> Mb;
    Int dp[401][401], inf = (Int)1 << 32;
    REP(i, 401) REP(j, 401) dp[i][j] = inf;
    dp[0][0] = 0;
    REP(i, N) {
        Int a, b, c; cin >> a >> b >> c;
        for (int j = 400; j >= a; j--) {
            for (int k = b; k < 401; k++) {
                dp[j][k] = min(dp[j][k], dp[j-a][k-b] + c);
            }
        }
    }
    Int ans = inf;
    for (int i = Ma, j = Mb; i < 401 && j < 401; i += Ma, j += Mb) {
        ans = min(ans, dp[i][j]);
    }
    cout << (ans == inf ? -1 : ans) << endl;
    return 0;
}


Measured memory_bytes: 1536
#include <cstdio>

int main(){
	int a[5], b[5];a[4] = b[4] = 0;
	for(int i = 0;i < 4;i++){scanf("%d", &a[i]);a[4] += a[i];}
	for(int i = 0;i < 4;i++){scanf("%d", &b[i]);b[4] += b[i];}
	if(a[4] >= b[4])printf("%d\n", a[4]);
	else printf("%d\n", b[4]);
	return 0;
}

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

int main() {
  char n[4];
  cin >>n;
  string result;
  if (n[0]==n[1] && n[1]==n[2]) result ="Yes";
  else if (n[1]==n[2] && n[2] ==n[3]) result ="Yes";
  else result = "No";
  
  cout << result;
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use proconio::{
    fastout, input,
    marker::{Bytes, Chars, Isize1, Usize1},
};

fn count_divx(x: u128, mut n: u128) -> usize {
    let mut r = 0;
    while n % x == 0 {
        r += 1;
        n /= x;
    }
    r
}

#[fastout]
fn main() {
    input! {
        n:usize,
        a:[f64;n]
    }
    let mut v = vec![];
    let mut table = vec![vec![0; 64]; 64];

    let mut ans = 0;
    let mut zero = 0;
    for (c, i) in a.iter().enumerate() {
        let buf = (i * 1000000000.0 + 0.2) as u128;
        if buf == 0 {
            ans += c;
            zero += 1;
        } else {
            let d2 = count_divx(2, buf);
            let d5 = count_divx(5, buf);
            v.push((d2, d5));
            ans +=
                table[if d2 > 18 { 0 } else { 18 - d2 }][if d5 > 18 { 0 } else { 18 - d5 }] + zero;
            for i in 0..=d2 {
                for j in 0..=d5 {
                    table[i][j] += 1;
                }
            }
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 9536
import java.util.*;

public class Main {
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int X = sc.nextInt();
    int[] x = new int[N];
    for (int i = 0; i < N; i++) {
      x[i] = sc.nextInt();
    }
    int gcd = Math.abs(X - x[0]);
    for (int i = 1; i < N; i++) {
      gcd = gcd(gcd, Math.abs(X - x[i]));
    }
    
    System.out.println(gcd);
  }
  
  private static int gcd(int a, int b) {
    if (b > a) {
      int tmp = a;
      a = b;
      b = tmp;
    }
    if (b == 0) {
      return a;
    }
    
    return gcd(b, a % b);
  }
}

Measured memory_bytes: 46356
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#include<cmath>
#include<cstdint>
 
#define INF 1e9
#define LINF 1e19
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)
     
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<ll, ll>;
     
const ll MOD = 1e9 + 7;
const ll ZER = 0;
 

ll dp[1000100][2];

int main(){
  string s;
  cin >> s;
  reverse(ALL(s));
  int n = s.size();
  dp[0][1] = 1;
  rep(i, n){
    int d = s[i] - '0';
    int a[2][2];
    a[0][0] = d;
    a[0][1] = 10 - d;
    a[1][0] = d + 1;
    a[1][1] = 9 - d;

    rep(j, 2){
      dp[i + 1][j] = min(dp[i][0] + a[0][j], dp[i][1] + a[1][j]);
    }
    /*
    rep(j, 2)rep(k, 2)cout << a[j][k] << " ";
    cout << endl;
    cout << dp[i + 1][0] << " " << dp[i + 1][1] << endl;
    */
  }
  //cout << dp[n][0] << " " << dp[n][1] << endl;
  cout << min(dp[n][0], dp[n][1] + 1) << endl;
}
 

Measured memory_bytes: 20052
while True:
    n, x = map(int, input().split())
    
    if n == 0 and x == 0:
        break
    else:
        pass
    
    result = 0
    for i in range(1, n+1):
        for j in range(i+1, n+1):
            for k in range(j+1, n+1):
                if i + j + k == x:
                    result += 1
                else:
                    pass
    print(result)


Measured memory_bytes: 5596
(n,m) = [int(i) for i  in input().split()]
A = []
b = []
for i in range(n):
    A.append([int(j) for j in input().split()])

for i in range(m):
    b.append(int(input()))

for i in range(n):
    s = 0
    for j in range(m):
        s += A[i][j] * b[j]
    print(s)

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

namespace NotFounds
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            new Program().Solve(new ConsoleInput(Console.In, ' '));
            Console.Out.Flush();
        }

        public void Solve(ConsoleInput cin)
        {
            var N = cin.ReadLong;
            var K = cin.ReadLong;

            var ary = new long[100001];
            for (int i = 0; i < N; ++i)
                ary[cin.ReadLong] += cin.ReadLong;

            long cnt = 0;
            for (int i = 0; i < 100001; ++i)
            {
                cnt += ary[i];
                if (cnt >= K)
                {
                    WriteLine(i);
                    return;
                }
            }
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); }}
        public int ReadInt { get { return int.Parse(Read); }}
        public long ReadLong { get { return long.Parse(Read); }}
        public double ReadDouble { get { return double.Parse(Read); }}
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret;}
        public void ReadIntArrays(long N, out int[] A, out int[] B) { A = new int[N]; B = new int[N]; for (long i = 0; i < N; ++i) { A[i] = ReadInt; B[i] = ReadInt; }}
        public void ReadLongArrays(long N, out long[] A, out long[] B) { A = new long[N]; B = new long[N]; for (long i = 0; i < N; ++i) { A[i] = ReadLong; B[i] = ReadLong; }}
    }
}


Measured memory_bytes: 17888
#include <iostream>
#include <string>
#include <algorithm>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <deque>
#include <cstdio>
#include <set>
#include <map>
#include <bitset>
#include <stack>
#include <cctype>
using namespace std;
int main() {
	int n;
	cin >> n;
	if (n == 1) {
		cout << "1" << endl;
		return 0;
	}
	pair<int, int> a[100];
	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
	}
	sort(a, a + n);
	int ans = 1000000007;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			int x = a[j].first - a[i].first;
			int y = a[j].second - a[i].second;
			int co = n;
			for (int k = 0; k < n; k++) {
				for (int l = k + 1; l < n; l++) {
					if (a[l].first - a[k].first == x && a[l].second - a[k].second == y) {
						co--;
					}
				}
			}
			if (ans > co) {
				ans = co;
			}
		}
	}
	cout << ans << endl;
	return 0;
}


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

int main() {      
	char a;
    char b = 'x';
	cin >> a;
	if (a == 'a'){
		b = 'o'    ;
    }if (a == 'i'){
		b = 'o' ;
       }if (a == 'u'){
		b = 'o'    ;
          }if (a == 'e'){
		b = 'o'  ;
             }if (a == 'o'){
    	b = 'o';
                }if (b =='o'){
    	cout << "vowel" << endl; 
                   }else{ 
      					cout << "consonant" << endl;
}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 10e17
#define rep(i,n) for(long long i=0; i<n; i++)
#define repr(i,n,m) for(long long i=m; i<n; i++)
#define mod 1000000007
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<long long>())
#define debug(x) std::cerr << (x) << std::endl;
#define roll(x) for (auto&& itr : x) { cerr << (itr) << " "; }

template <class T> inline void chmax(T &ans, T t) { if (t > ans) ans = t;}
template <class T> inline void chmin(T &ans, T t) { if (t < ans) ans = t;}

int main() {
  int n;
  cin >> n;
  map<string, int> mp;
  rep(i, n) {
    string s;
    cin >> s;
    mp[s] += 1;
  }

  vector<set<string>> a(n+1);
  int mmax = 0;
  for (auto itr : mp) {
    a[itr.second].insert(itr.first);
    if (mmax < itr.second) {
      mmax = itr.second;
    }
  }

  for (auto itr : a[mmax]) {
    cout << itr << endl;
  }
}

Measured memory_bytes: 43904
fn main() {
  let n: i64 = read();
  let mut vec: Vec<i64> = read_vec();
  
  let sum = vec.iter().sum::<i64>();
  let psum = n * (n + 1) / 2;
  let k = sum / psum;
  if sum % psum != 0 {
    println!("NO");
    return
  };
  
  let &head = vec.first().unwrap();
  vec.push(head);
  
  if vec.windows(2).map(|w|w[1]-w[0]-k).all(|x|x<=0 && x%n==0) {
    println!("YES");
  } else {
    println!("NO");
  }
}

fn read<T: std::str::FromStr>() -> T {
  let mut buf = String::new();
  std::io::stdin().read_line(&mut buf).ok();
  buf.trim().parse::<T>().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
  let mut buf = String::new();
  std::io::stdin().read_line(&mut buf).ok();
  buf.trim().split_whitespace().map(|t| t.parse::<T>().ok().unwrap()).collect()
}

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

int main(){
  int n,m;
  cin>>n>>m;
  char a[50][50];
  int w[50],r[50],b[50];
  lp(i,50){
    w[i]=0;
    r[i]=0;
    b[i]=0;
  }
  lp(i,n){
    lp(j,m){
      cin>>a[i][j];
      if(a[i][j]=='W') w[i]++;
      if(a[i][j]=='R') r[i]++;
      if(a[i][j]=='B') b[i]++;
    }
  }
  int ans=10000;
  lp(i,n-2){
    for(int j=i+1;j<n-1;j++){
      int mem=0;
      for(int k=0;k<=i;k++){
	mem+=r[k]+b[k];
      }
      for(int k=i+1;k<=j;k++){
	mem+=w[k]+r[k];
      }
      for(int k=j+1;k<n;k++){
	mem+=w[k]+b[k];
      }
      if(mem<ans) ans=mem;
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3068
#include<stdio.h>
 long long a[100010];
 int main(){int n;scanf("%d",&n);for(int i=0;i<n;i++)scanf("%lld",&a[i]);int zero=0;
for(int i=0;i<n;i++)if(a[i]==0)zero++;if(zero >0){
printf("0\n");return 0;}long long prod=1;for(int i=0;i<n;i++){if(a[i]<=1000000000000000000/prod){//Thisconditionisequivalenttoprod*a[i]<=10ˆ18
	prod*=a[i];}else{printf("-1\n");return 0;}}printf("%lld\n",prod);}

Measured memory_bytes: 2488
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

//Bus Line
public class Main{

	static class T{
		int p;
		boolean up;
		String s;
		public T(int p, String s, boolean d) {
			this.p = p;
			this.up = d;
			this.s = s;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while(t--!=0){
			int s = sc.nextInt();
			int g = sc.nextInt();
			List<T> l = new ArrayList<T>();
			l.add(new T(s,s+"",true));
			l.add(new T(s,s+"",false));
			boolean[][] u = new boolean[10][2];
			u[s][0] = u[s][1] = true;
			while(!l.isEmpty()){
				List<T> next = new ArrayList<T>();
				for(T w:l){
					if(w.p==g){
						next.clear();
						System.out.println(w.s);
						break;
					}
					if(w.up){
						if(w.p==9){
							if(!u[5][1]){
								u[5][1] = true;
								next.add(new T(5,w.s+" "+5,false));
							}
						}
						else if(!u[w.p+1][0]){
							u[w.p+1][0] = true;
							next.add(new T(w.p+1, w.s+" "+(w.p+1),true));
						}
					}
					else{
						if(w.p==0){
							if(!u[1][0]){
								u[1][0] = true;
								next.add(new T(1,w.s+" 1",true));
							}
						}
						else{
							if(w.p>=6)continue;
							if(!u[w.p-1][1]){
								u[w.p-1][1] = true;
								next.add(new T(w.p-1,w.s+" "+(w.p-1),false));
							}
						}
					}
				}
				l = next;
			}
		}
	}
}

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

using namespace std;

string s;
int vf[30];

int main()
{
    cin >> s;
    for(int i = 0;i < s.size();i++)  {
        vf[s[i] - 'a']++;
    }
    bool ok = 1;
    for(int i = 0;i <= 26;i++)
        if(vf[i] >= 2)
            ok = 0;
    if(ok == 1)
        cout << "yes";
    else
        cout << "no";
    cout << "\n";
    return 0;
}


Measured memory_bytes: 256
// clang-format off
#include <bits/stdc++.h>

#define mp make_pair
#define fst first
#define snd second
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define forn1(i,n) for (int i = 1; i <= int(n); i++)
#define popcnt __builtin_popcount
#define ffs __builtin_ffs
#define ctz __builtin_ctz
#define clz __builtin_clz
#define all(a) (a).begin(), (a).end()
 
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
using pil = pair<int,ll>;
using pll = pair<ll,ll>;
template <typename T> using vec = vector<T>;
using vi = vec<int>;
using vl = vec<ll>;
template <typename T> using que = queue<T>;
template <typename T> using deq = deque<T>;

template <typename T> T id(T b) {return b;};
template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}
template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}
template <typename S, typename K> bool contains(S &s, K k) { return s.find(k) != s.end(); }
void fastio() { ios_base::sync_with_stdio(false); cin.tie(nullptr); }
constexpr ll TEN(int n) { if (n == 0) return 1LL; else return 10LL*TEN(n-1); }
// clang-format on

const int MAX_N = 12;
int n, m, x;
int c[MAX_N];
int a[MAX_N][MAX_N];

int main() {
    fastio();

    cin >> n >> m >> x;
    forn(i, n) {
        cin >> c[i];
        forn(j, m) cin >> a[i][j];
    }

    int ans = INT_MAX;
    for (int b = 0; b < (1 << n); b++) {
        vi temp(m, 0);
        int cost = 0;
        forn(i, n) {
            if ((b >> i) & 1) {
                cost += c[i];
                forn(j, m) {
                    temp[j] += a[i][j];
                }
            }
        }

        if (all_of(all(temp), [](int v) { return v >= x; })) {
            chmin(ans, cost);
        }
    }

    if (ans == INT_MAX) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

using Edge = struct{int to;};
using Graph = vector<vector<Edge>>;
vector<int> c, res;
int n;
int ind = 0;

Graph G;
void dfs(int v, int p, int a){
    res[v] = c[a];
    for(auto e: G[v]){
        if(e.to == p) continue;
        ind++;
        dfs(e.to, v, ind);
    }
}



int main(){
    cin >> n;
    G.assign(n, vector<Edge>());
    for(int i=0; i<n-1; i++){
        int u, v;
        cin >> u >> v;
        u--; v--;
        G[u].push_back(Edge{v});
        G[v].push_back(Edge{u});
    }
    for(int i=0; i<n; i++){
        int C; cin >> C;
        c.push_back(C);
    }

    sort(c.rbegin(), c.rend());

    res.assign(n, 0);
    dfs(0, -1, 0);

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

Measured memory_bytes: 1408
from collections import Counter

N, M, K = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
CD = [tuple(map(int, input().split())) for _ in range(K)]


class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def root(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        root_x = self.root(x)
        root_y = self.root(y)
        if self.rank[x] > self.rank[y]:
            self.parent[root_y] = root_x
        elif self.rank[x] < self.rank[y]:
            self.parent[root_x] = root_y
        elif root_x != root_y:
            self.parent[root_y] = root_x
            self.rank[x] += 1
        pass


uf = UnionFind(N)

for a, b in AB:
    uf.unite(a - 1, b - 1)

roots = [uf.root(i) for i in range(N)]
counter_roots = Counter(roots)

ans = [counter_roots[roots[i]] - 1 for i in range(N)]

for a, b in AB:
    if roots[a - 1] == roots[b - 1]:
        ans[a - 1] -= 1
        ans[b - 1] -= 1
for a, b in CD:
    if roots[a - 1] == roots[b - 1]:
        ans[a - 1] -= 1
        ans[b - 1] -= 1

print(*ans)


Measured memory_bytes: 48372
#include<cstdio>
char s[200001];
int w[200001];
int main()
{
	int n,i,b=0,ans=2e9;
	scanf("%d%s",&n,s);
	for(i=n-1;i>=0;i--)w[i]=w[i+1]+(s[i]=='.');
	for(i=0;i<=n;b+=s[i++]=='#')if(b+w[i]<ans)ans=b+w[i];
	printf("%d\n",ans);
}


Measured memory_bytes: 1152