akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll x, y;
	cin >> x >> y;
	cout << (llabs(x-y) <= 1LL ? "Brown" : "Alice") << endl;
	return 0;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <map>
#include <cmath>
#include <string>
#include <math.h>
using namespace std;

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

typedef long long ll;


ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll c, ll d) { return c / gcd(c, d) * d; }

int main() {
  int n, x;
  cin >> n >> x;

  int m[n]; int min_elem = 1001; int count = 0;
  rep(i, n) {
      cin >> m[i]; 
      min_elem = min(min_elem, m[i]);
      x -= m[i]; count++;
  }
  while (x/min_elem != 0)
  {
      x -= min_elem;
      count++;
  }
  
  cout << count << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<cmath>
using namespace std;
#define REP(i, limit) for(int i=0; i< limit; ++i)
#define FOR(i, j, limit) for(int i=j; i< limit; ++i)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ECHO(x) cout<<x<<endl;
#define LL long long
int INF = 2147483647;
LL LINF = 9223372036854775807;
LL MOD = 1000000007;
typedef pair<int, int>P;
typedef pair<LL, LL>PL;


int main(){
  int n, q;
  cin>>n>>q;
  char s[n+2];
  REP(i, n) cin>>s[i+1];
  s[0]='0';
  s[n+1]='0';
  char t[q], d[q];
  for(int i=0; i<q; ++i){
    cin>>t[i]>>d[i];
  }
  int l=0;
  int r=n+1;
  int a;
  int w;
  while(l<r-1){
    a = (l+r)/2;
    w = a;
    REP(i, q){
      if(t[i]==s[w] && d[i]=='L') --w;
      if(t[i]==s[w] && d[i]=='R') ++w;
      if(w==0) break;
    }
    if(w==0) l=a;
    else r=a;
    //cout<<l<<r<<a<<endl;
  }
  w = r;
  REP(i, q){
    if(t[i]==s[w] && d[i]=='L') --w;
    if(t[i]==s[w] && d[i]=='R') ++w;
    if(w==0) break;
  }
  if(w==0) a=r;
  else a=l;


  l=0;
  r=n+1;
  int b;

  while(l<r-1){
    b = (l+r)/2;
    w=b;
    REP(i, q){
      if(t[i]==s[w] && d[i]=='L') --w;
      if(t[i]==s[w] && d[i]=='R') ++w;
      if(w==n+1) break;
    }
    if(w==n+1) r=b;
    else l=b;
  }
  w = l;
  REP(i, q){
    if(t[i]==s[w] && d[i]=='L') --w;
    if(t[i]==s[w] && d[i]=='R') ++w;
    if(w==0) break;
  }
  if(w==n+1) b=l;
  else b=r;

  cout<<max(0, b-a-1)<<endl;
  return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using Graph= vector<vector<ll>>;
struct edge{ll to ; ll cost ;} ;
using graph =vector<vector<edge>> ;
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define mpa make_pair
#define fi first
#define se second 
#define set20 cout<<fixed<<setprecision(20) ;
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}
double pi=acos(-1) ;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}


int main(){
  ll t ; cin>> t ;
  rep(ww,t){
    ll n ;cin>>n ;
    vector<ll> K(n),L(n) ,R(n),sa(n) ;
    ll sum=0 ;
    ll ans=0 ;
    rep(i,n){
     cin>>K[i]>>L[i]>>R[i] ;
       sa[i]= L[i]-R[i] ;
       sum+= min(R[i],L[i]) ;
    }
    
    map<ll,vector<ll>> mp,pm ; ll cnt,dnt ;
    rep(i,n){
       if(sa[i]>0) {
           mp[K[i]].pb(sa[i])  ;
           cnt++ ;
           }
       else {
           K[i]++ ;
           pm[K[i]].pb(-sa[i]) ;
           dnt++ ;
       }
    }
    priority_queue<int> pq ; 
    rep3(i,n,1){
     for(auto u :mp[i]){
        pq.push(u) ;
     }
     if(!pq.empty()){
     ll x= pq.top() ;
          if(i<=cnt){
              ans+=x ;
              pq.pop() ;
          }
      }
     }
     priority_queue<int> qp ;
    rep2(i,1,n){
        for(auto u :pm[i]){
          qp.push(u) ;  
        }
        if(!qp.empty()){
            ll x= qp.top() ;
            if(n-i+1<=dnt){
                ans+= x ;
                qp.pop() ;
            }
        }
    } 
     
     
     
     cout<<ans+sum<<endl ;
  
    }
    
   
  
   return 0 ; 
}



Measured memory_bytes: 45404
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int a[15],b[15];
bool judge(int o1,int o2,int d,int s,int k){
    if(s==0)return true;
    if(k==0)return false;
    if(d==0){
        bool h=false,m=false;
        if(a[o1]==0&&a[o2]==0)return judge(o1,o2,(d+1)%2,s,k);
        if(a[o1]){
            a[o1]=0;
            h=judge(o1-1,o2,(d+1)%2,s-1,k);
            a[o1]=1;
        }
        if(a[o2]){
            a[o2]=0;
            m=judge(o1,o2+1,(d+1)%2,s-1,k);
            a[o2]=1;
        }
        if(h||m)return true;
        else return false;
    }else{
        bool h=true,m=true;
        if(b[o1]==0&&b[o2]==0)return judge(o1,o2,(d+1)%2,s,k);
        if(b[o1]){
            b[o1]=0;
            h=judge(o1-1,o2,(d+1)%2,s,k-1);
            b[o1]=1;
        }
        if(b[o2]){
            b[o2]=0;
            m=judge(o1,o2+1,(d+1)%2,s,k-1);
            b[o2]=1;
        }
        if(h==false||m==false)return false;
        else return true;
    }
}
int main(void){
    int n;
    cin>>n;
    while(n){
        for(int i=1;i<=13;i++){
            a[i]=0;
            b[i]=1;
            if(i==7)b[i]=0;
        }
        for(int i=0;i<6;i++){
            int f;
            cin>>f;
            a[f]=1;
            b[f]=0;
        }
        if(judge(6,8,0,6,6))cout<<"yes\n";
        else cout<<"no\n";
        n--;
    }
}

Measured memory_bytes: 3088
n = int(input())
M = 1000000007
a = input().split()
sum = 0
sq_sum = 0
for x in a:
    y = int(x)
    sum += y
    sq_sum += (y*y)
sum = sum * sum
ans = abs(sum - sq_sum)//2
ans = (ans + M) % M
ans = int(ans)
print(ans)


Measured memory_bytes: 25092
#include <stdio.h>

int main (void)
{
    int N,key=0;
    scanf("%d",&N);
    for(int i=0;i<N;i++)
    {
        char c;
        scanf("%c",&c);
        if(c=='Y')
        {
            key++;
            break;
        }
    }
    if(key==1)
    {
        puts("Four");
    }else{
        puts("Three");
    }
    return 0;
}

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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

signed main(){
    string a,b,c;
    cin>>a>>b>>c;
    cout<<"A"<<b[0]<<"C"<<endl;
    return 0;
}


Measured memory_bytes: 256
H, W = map(int, input().split())
field = [list(input()) for i in range(H)]
flag = []
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

for i in range(H):
    for j in range(W):
        if field[i][j] == '.':
            continue
        inflag = False
        for k in range(4):
            ni = i + dx[k]
            nj = j + dy[k]
            if ni < 0 or ni >= H or nj < 0 or nj >= W:
                continue
            elif field[ni][nj] == '#':
                inflag = True
        flag.append(inflag)

if all(flag):
    print('Yes')
else:
    print('No')


Measured memory_bytes: 3064
N = int(input())
A = [list(map(int, input().split())) for _ in range(2)]

v1 = A[0][0]
v2 = A[1][0] + v1

if N==1:
    print(v2)
    exit()

for j in range(1, N):
    v1 += A[0][j]
    v2 = A[1][j] + max(v2, v1)

print(v2)


Measured memory_bytes: 3060
import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n, a, b = inintm()
s = input()

rank = 1
tuka = 0

for i in range(n):
    if s[i] == "a":
        if tuka < a+b:
            print("Yes")
            tuka += 1
            continue
    elif s[i] == "b":
        if tuka < a+b and rank <= b:
            print("Yes")
            tuka += 1
            rank += 1
            continue
    print("No")


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

int a, b, c;
int ans;

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

			

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

ll gcd(ll a, ll b){return (b==0?a:gcd(b,a%b));}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}

int main(){
  ll N, M;
  cin >> N >> M;
  vector<ll> v;
  rep(i,N){
    ll a;
    cin >> a;
    v.push_back(a);
  }

  map<int,int> w;
  rep(i,N){
    ll tmp = v[i];
    int cnt = 0;
    while(tmp%2==0){
      cnt++;
      tmp /= 2;
    }
    w[cnt]++;
  }

  if(w.size() != 1){
    cout << 0 << endl;
    return 0;
  }
  
  
  ll x = 1;
  rep(i,N){
    x = lcm(x, v[i]/2);
    
    if(x > M){
      cout << 0 << endl;
      return 0;
    }
  }

  ll y = M / x;
  cout << (y + 1)/2 << endl;

  return 0;
}



Measured memory_bytes: 1400
<?php
$n = trim(fgets(STDIN));

for ($i = 0; $i < $n; ++$i) {
  list($h, $m) = explode(':', trim(fgets(STDIN)));
  $dig_h = $h * 30 + $m * 0.5;
  $dig_m = $m * 6;
  if ($dig_h >= 360) { $dig_h -= 360; }
  $df = abs($dig_h - $dig_m);
  if ($df > 180) { $df = 360 - $df; }

//  echo $df.':';
  if ($df < 30) {
    echo "alert\n";
  } else if ($df < 90) {
    echo "warning\n";
  } else {
    echo "safe\n";
  }
}

Measured memory_bytes: 15344
N, M = [int(i) for i in input().split()]
dic = {}

for _ in range(M):
    p, s = input().split()
    if p not in dic:
        dic[p] = [False, 0]
    isAC, WC = dic[p]
    if isAC:
        continue
    if s == "AC":
        dic[p][0] = True
    elif s == "WA":
        dic[p][1] += 1

correct = 0
penalty = 0

for v in dic.values():
    if v[0]:
        correct += 1
        penalty += v[1]

print(correct, penalty)


Measured memory_bytes: 66648
n = gets.to_i
scores = readlines.map(&:to_i)
max_score = scores.inject(:+)
if max_score % 10 == 0
  non_10_scores = scores.map { |s| s % 10 == 0 ? nil : s }.compact
  if non_10_scores.empty?
    answer = 0
  else
    answer = max_score - non_10_scores.min
  end
else
  answer = max_score
end
puts answer


Measured memory_bytes: 1788
N = int(input())
H = list(map(int, input().split()))

ans = [[] for i in range(N)]
ans[0] = 0
ans[1] = abs(H[0]-H[1])
for i in range(2,N):
    ans[i] = min(ans[i-2] + abs(H[i-2]-H[i]), ans[i-1] + abs(H[i-1]-H[i]))
print(ans[N-1])

Measured memory_bytes: 14824
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
const int INF = 1 << 28;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}

int main() {
    int n, k;
    cin >> n >> k;
    vl a(n, 0);
    ll sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sum += a[i];
    }
    sort(a.begin(), a.end());

    auto noneed = [&](ll mid) {
        vector<vector<bool>> dp(n + 1, vector<bool>(k + 1, false));
        dp[0][0] = true;
        for (int j = 1; j <= n; ++j) {
            if (j - 1 == mid) {
                for (int i = 0; i <= k; ++i) {
                    dp[j][i] = dp[j - 1][i];
                }
            } else {
                for (int i = 0; i <= k; ++i) {
                    dp[j][i] = dp[j - 1][i];
                    if (i - a[j - 1] >= 0)
                        dp[j][i] = dp[j][i] || dp[j - 1][i - a[j - 1]];
                }
            }
        }
        bool noneed = true;
        for (int i = max(0LL, k - a[mid]); i < k; ++i) {
            if (dp[n][i]) {
                noneed = false;
                break;
            }
        }
        return noneed;
    };

    if (!noneed(0)) {
        cout << 0 << "\n";
        return 0;
    }
    if (noneed(n - 1)) {
        cout << n << "\n";
        return 0;
    }
    ll ng = 0;
    ll ok = n - 1;
    while (ng + 1 != ok) {
        ll mid = (ok + ng) / 2;

        if (noneed(mid))
            ng = mid;
        else
            ok = mid;
    }
    cout << ng + 1 << "\n";
    return 0;
}

Measured memory_bytes: 3592
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
         
        Scanner sc = new Scanner(System.in);
         String W = sc.next();
         W = W.toUpperCase();
         int count=0;

        while( true ){
            String T = sc.next();
            if( T.equals( "END_OF_TEXT" ) )
                break;
            T = T.toUpperCase();
            if(T.equals(W)){
                count++;
            }
        }
        System.out.println(count);
        sc.close();
    }
}




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




int main(){
    ll h,w;
    cin >> h >> w;
    ll res = h*w;
    ll s1,s2,s3;
    
    if(w>=3){
        ll s1_w = w/3;
        s1 = h*(s1_w);
        s2 = h*((w-s1_w)/2);
        s3 = h*w - s1 - s2;
        
        //cout << s1 << s2 << s3 << endl;

        ll temp = max(s1,max(s2,s3))-min(s1,min(s2,s3));
        res = min(res,temp);
    }

    if(h>=3){
        ll s1_h = h/3;
        s1 = w*(s1_h);
        s2 = w*((h-s1_h)/2);
        s3 = h*w - s1 - s2;
        
        //cout << s1 << s2 << s3 << endl;

        ll temp = max(s1,max(s2,s3))-min(s1,min(s2,s3));
        res = min(res,temp);

    }

    //s1 min
    if(h>=2&&w>=2){
        ll s1_w = w/3;
        s1 = h*s1_w;
        s2 = (h/2)*(w-s1_w);
        s3 = h*w-s1-s2;

        //cout << s1 << s2 << s3 << endl;

        ll temp = max(s1,max(s2,s3))-min(s1,min(s2,s3));
        res = min(res,temp);
    }
    if(h>=2&&w>=2){
        ll s1_w = w/3+1;
        s1 = h*s1_w;
        s2 = (h/2)*(w-s1_w);
        s3 = h*w-s1-s2;

        //cout << s1 << s2 << s3 << endl;

        ll temp = max(s1,max(s2,s3))-min(s1,min(s2,s3));
        res = min(res,temp);
    }

    if(h>=2&&w>=2){
        ll s1_h = h/3;
        s1 = w*s1_h;
        s2 = (w/2)*(h-s1_h);
        s3 = h*w-s1-s2;

        //cout << s1 << s2 << s3 << endl;

        ll temp = max(s1,max(s2,s3))-min(s1,min(s2,s3));
        res = min(res,temp);
    }

    if(h>=2&&w>=2){
        ll s1_h = h/3+1;
        s1 = w*s1_h;
        s2 = (w/2)*(h-s1_h);
        s3 = h*w-s1-s2;

        //cout << s1 << s2 << s3 << endl;

        ll temp = max(s1,max(s2,s3))-min(s1,min(s2,s3));
        res = min(res,temp);
    }

    cout << res << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
typedef long long ll;

ll dp[400][400]; vector<ll> v;

inline ll query(int i, int j) { return i ? v[j] - v[i - 1] : v[j]; }

int main() {
	int n; cin >> n; v.resize(n);
	for (auto &x : v) { cin >> x; }
	partial_sum(v.begin(), v.end(), v.begin());
	fill(dp[0], dp[0] + 400 * 400, 1ll << 60);
	for (int i = 0; i < n; i++) dp[i][i] = 0;
	for (int l = 1; l < n; l++)	
		for (int i = 0; i < n - l; i++) {
			dp[i][i + l] = query(i, i + l); ll res = 1ll << 60;
			for (int j = i; j < i + l; j++)
				res = min(res, dp[i][j] + dp[j + 1][i + l]);
			dp[i][i + l] += res;
		}

	cout << dp[0][n - 1] << '\n';
	cin.ignore(2); return 0;
}

Measured memory_bytes: 4836
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iomanip>
#include <map>
#include <set>
#include <tuple>
#include <unordered_map>
#include <iterator>
#include <string>
#include <limits>

using namespace std;

using i64 = int64_t;
using P = pair<i64, i64>;
i64 mod = 1000000007;
int int_max = 2147483647;
int max_n = 1e5;


int main(int argc, char **argv) {
    i64 n, k;
    cin >> n >> k;

    i64 mod_k = n % k;

    i64 ans = min(mod_k, abs(mod_k-k));
    cout << ans << endl;

    return 0;
}

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

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

  int l = (int)S.length();

  int out = 0;
  int color = S[0] - '0';

  for (int i=1; i<l; i++){
    // 交互になるようにすれば良い
    // next_color = 1 - color
    // cout << S[i] << color << endl;
    if (S[i] - '0' == color){
      out += 1;
    }
    color = 1 - color;
  }

  cout << out << endl;
  return 0;
}


Measured memory_bytes: 512
#![allow(unused_imports)]
#![allow(dead_code)]

use proconio::input;
use proconio::marker::{Bytes, Chars};
use std::collections::*;

fn main() {
    input! {
        h:usize,
        w:usize,
        ch:usize,
        cw:usize,
        dh:usize,
        dw:usize,
        s:[Chars;h],
    }
    let (ch, cw) = (ch - 1, cw - 1);
    let (dh, dw) = (dh - 1, dw - 1);
    let mut dist = vec![vec![std::i32::MAX; w]; h];
    dist[ch][cw] = 0;
    let mut bfs = VecDeque::new();
    bfs.push_back(State {
        now: (ch, cw),
        cost: 0,
    });
    let directions = vec![(1, 0), (-1, 0), (0, 1), (0, -1)];
    while let Some(State {
        now: (x, y),
        cost: c,
    }) = bfs.pop_front()
    {
        if dist[x][y] < c {
            continue;
        }
        for &d in directions.iter() {
            match next((x, y), d, h, w) {
                Some((nx, ny)) => {
                    if s[nx][ny] == '#' {
                        continue;
                    } else {
                        if dist[nx][ny] > dist[x][y] {
                            dist[nx][ny] = dist[x][y];
                            bfs.push_front(State {
                                now: (nx, ny),
                                cost: dist[x][y],
                            });
                        }
                    }
                }
                None => {}
            }
        }
        for dx in -2..=2 {
            for dy in -2..=2 {
                match next((x, y), (dx, dy), h, w) {
                    Some((nx, ny)) => {
                        if s[nx][ny] == '#' {
                            continue;
                        } else {
                            if dist[nx][ny] > dist[x][y] + 1 {
                                dist[nx][ny] = dist[x][y] + 1;
                                bfs.push_back(State {
                                    now: (nx, ny),
                                    cost: dist[x][y],
                                });
                            }
                        }
                    }
                    None => {}
                }
            }
        }
    }
    let ans = dist[dh][dw];
    if ans == std::i32::MAX {
        println!("{}", -1);
    } else {
        println!("{}", ans);
    }
}

struct State {
    now: (usize, usize),
    cost: i32,
}

fn next(from: (usize, usize), to: (i32, i32), h: usize, w: usize) -> Option<(usize, usize)> {
    let (h, w) = (h as i32, w as i32);
    let (x, y) = (from.0 as i32, from.1 as i32);
    let (dx, dy) = to;
    let (nx, ny) = (x + dx, y + dy);
    let det = nx >= 0 && nx < h && ny >= 0 && ny < w;
    if det {
        Some((nx as usize, ny as usize))
    } else {
        None
    }
}

Measured memory_bytes: 11240
#include <stdio.h>
int main(void){
	int x,y;
	while(1){
		scanf("%d%d",&x,&y);
		if(x == 0&&y == 0)break;
		if(x > y){
			printf("%d %d\n",y,x);
		}else{
			printf("%d %d\n",x,y);
		}
	}
    return 0;
}

Measured memory_bytes: 600
N = int(input())
d = sorted(list(map(int, input().split())))

num = d[N // 2 - 1]
ans = 0
for i in range(10**5):
    num += 1
    if d[N // 2 - 1] < num <= d[N//2]:
        ans += 1
    if num > d[N//2]:
        break
print(ans)


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

int main() {
	int n,k;
	cin>>n>>k;
	vector<int> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	sort(a.begin(),a.end());
	bool dp[k+1];
	dp[0]=0;
	for(int i=0;i<n;i++){
		dp[a[i]]=1;
	}
	for(int i=1;i<=k;i++){
		for(int j=0;j<n;j++){
			if(i<a[j]){dp[i]=0;break;}
			if(dp[i-a[j]]){
				dp[i]=0;
			}
			else {dp[i]=1;break;}
		}
	}
	if(dp[k])cout<<"First";
	else cout<<"Second";
	return 0;
}

Measured memory_bytes: 384
#include<stdio.h>

int main(){
  int a,cou=3,sum=1;

  do{
    scanf("%d",&a);
  }while(a<1&&a>9);


  while(cou!=0){
    sum=sum*a;
    --cou;
  }

  printf("%d\n",sum);

  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define ff first
#define ss second
#define P 1000000007
#define in(x, a, b) (a <= x && x < b)

using namespace std;
using ll = long long;
typedef pair<int, int> ii;
typedef vector<ii> vii; 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
const ll inf = 1000000001, INF = (ll)1e18 + 1;

void solve() {
	int x;
	cin >> x;
	cout << !x << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	solve();
    return 0;
}

Measured memory_bytes: 3608
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int i,j,a,b,a2,b2;
int gcm=1,lcm;

int main(){
	while(scanf("%d %d",&a,&b)!=EOF){
		for(i=2;i<=a && i<=b;i+=0){
			if(a%i==0 && b%i==0){
				gcm=gcm*i;
				a/=i;b/=i;
			}else i++;
		}
		lcm=a*b*gcm;
		printf("%d %d\n",gcm,lcm);
		gcm=1;
	}
	
	return 0;
}

Measured memory_bytes: 0
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn tcnt(level: usize) -> usize {
    let mut ret = 1;
    for _ in 0..level {
        ret = ret * 2 + 3;
    }
    return ret;
}
fn pcnt(level: usize) -> usize {
    let mut ret = 1;
    for _i in 0..level {
        ret = ret * 2 + 1;
    }
    return ret;
}

fn calc(level: usize, x: usize) -> usize {
    if x == 0 {
        return 0;
    }
    if level == 0 {
        return 1;
    }
    let mut ret = 0;
    let x = x - 1;
    let cnt = tcnt(level - 1);
    if x < cnt {
        ret = calc(level - 1, x);
    } else {
        ret += pcnt(level - 1);
        if x > cnt {
            ret += 1;
            let nx = x - cnt - 1;
            ret += calc(level - 1, nx);
        }
    }
    return ret;
}

fn main() {
    let n = read::<usize>();
    let x = read::<usize>();
    let ans = calc(n, x);
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,val=30;
  cin >> N;
  for(int i=0; i<N; i++){
    int A, temp=0;
    cin >> A;
    while(true){
      if(A%2==0){
      temp++;
      A/=2;
      }
      else break;
    }
    if(temp<val) val=temp;
  }
  cout << val << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef pair<int, int> p;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    int ans = 0, cnt = 0;

    REP(i, s.size())
    {
        char c = s[i];
        if(c == 'A' or c == 'C' or c == 'G' or c == 'T')
        {
            cnt++;
        }
        else
        {
            cnt = 0;
        }

        ans = max(ans, cnt);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <queue>

//
// Input
// N K
// A1 A2 ... An
//  * N is Num of Data, K is NUms of Acceptable Kindness
// Output
// N ... Need to Replace Nums

int main () {

    int size = 0;
    int kind = 0;
    int result = 0;

    std::cin >> size;
    std::cin >> kind;
    std::map<int,int> map{}; // 入力された値をKeyに、何回追加されたかnumsにカウントする

    for (int idx = 0; idx< size; idx++) {
        int x;
        std::cin >> x;
        map[x] = map[x] + 1;
    }

    std::priority_queue<int> queue;
    for (auto x : map) {
        queue.push(x.second);
    }

    while(!queue.empty() && kind > 0) {
        queue.pop();
        kind--;
    }

    while(!queue.empty()) {
        result = result + queue.top();
        queue.pop();
    }

    std::cout << result << std::endl;

    return 0;
}


Measured memory_bytes: 10748
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int dy[4]={1,0,-1,0};
int dx[4]={0,1,0,-1};
vector<vector<int>> graph;

bool sort_sec(const pair<int,int> &a,const pair<int,int> &b){
   if(a.second<b.second){
      return true;
   }
   return false;
}

void swap(int *a,int *b){
   int temp=*a;
   *a=*b;
   *b=temp;
}

int main(void){
   int N;
   cin>>N;
   vector<long long> A(N),B(N);
   for(int i=0;i<N;i++){
      cin>>A[i]>>B[i];
   }
   long long ans=0;
   for(int i=N-1;i>=0;i--){
      A[i]+=ans;
      if(A[i]%B[i]>=1){
         ans+=(B[i]-A[i]%B[i]);
      }
   }
   cout<<ans<<endl;
   return 0;
}


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

int main(){
    int a;
    int b;
    cin >> a >> b;
    if (a > b)
        cout << "a > b" << endl;
    else if(a == b)
        cout << "a == b" << endl;
    else if(a<b)
        cout << "a < b" << endl;
}


Measured memory_bytes: 3080
#include<iostream>
using namespace std;
int main()
{
  int N,M,A[101];
  int i,j;
  int tmp;

  cin >> N >> M;
  for(i=0;i<N;i++)
    cin >> A[i];
  
  for(i=0;i<M;i++){
    for(j=0;j<N-1;j++){
      if(A[j]%(i+1) > A[j+1]%(i+1)){
	tmp = A[j];
	A[j] = A[j+1];
	A[j+1] = tmp;
      }
    }
  }
  
  for(i=0;i<N;i++)
    cout << A[i] << '\n';

  return 0;
}

Measured memory_bytes: 3096
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main() {
    ll a,b,x,temp;
    cin>>a>>b>>x;
    temp=a/x;
    if(a%x!=0)
    {
        a=(temp+1);
    }
    else
        a=temp;
   // cout<<a<<endl;
    b=b/x;
      cout<<b-a+1<<endl;
    return 0;
    }


Measured memory_bytes: 3600
#include<bits/stdc++.h>
#define maxn 100005
#define ll long long
using namespace std;
int n,m;
int g[16][16];
int block[1<<15],f[1<<15][16];
int main()
{
	scanf("%d%d",&n,&m);
	int u,v,w,sum=0;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		sum+=w;g[u][v]=g[v][u]=w;
	}
	for(int s=0;s<(1<<n);s++)
	{
		for(int j=1;j<=n;j++)
		{
			if((!(s>>(j-1))&1)&&block[s|(1<<(j-1))]==0)
			{
				block[s|(1<<(j-1))]=block[s];
				for(int k=1;k<=n;k++)
				{
					if((s>>(k-1))&1)
						block[s|(1<<(j-1))]+=g[j][k];
				}
			}
		}
	}
	memset(f,-1,sizeof(f));
	f[1][1]=0;
	for(int s=0;s<(1<<n);s++)
	{
		for(int j=1;j<=n;j++)
		{
			if(f[s][j]!=-1&&((s>>(j-1))&1))
			{
				for(int k=1;k<=n;k++)
				{
					if(!((s>>(k-1))&1)&&g[j][k])
						f[s|(1<<(k-1))][k]=max(f[s|(1<<(k-1))][k],f[s][j]+g[j][k]);
				}
				int ss=(((1<<n)-1)^s)|(1<<(j-1));
				for(int k=ss;k;k=(k-1)&ss)
				{
					if((k>>(j-1))&1)
						f[s|k][j]=max(f[s|k][j],f[s][j]+block[k]);
				}
			}
		}
	}
	printf("%d\n",sum-f[(1<<n)-1][n]);
	return 0;
}

Measured memory_bytes: 2432
import java.util.Scanner;
public class Main{
	static long mod=1_000_000_007;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();
		int k = sc.nextInt();
		long[][] dp = new long[h+1][w+2];
		dp[0][1]=1;
		for(int i = 0; i<h; i++){
			for(int j = 1; j<=w; j++){
				long left = j-2;
				long right = w-j-1;
				long straight = bit(left)*bit(right);
				long Left = bit(left-1)*bit(right);
				long Right = bit(left)*bit(right-1);
				dp[i+1][j]=(dp[i][j]*straight+dp[i][j-1]*Left+dp[i][j+1]*Right)%mod;
			}
		}
		System.out.println(dp[h][k]);
	}
	public static long bit(long number){
		if(number<=0){
			return 1;
		}
		long ans=0;

	as:for(long i=0; i<Math.pow(2,number); i++){
			for(long k = 0; k<number; k++){
				if(k!=0){
					if((i>>k & 1)==1 && (i>>k-1 & 1)==1 ){
						continue as;
					}
				}
			}
			ans++;
		}
		return ans;
	}
}

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

int main() {
  int N;
  vector<tuple<string, int, int>> v;
  string city;
  int score;
  cin >> N;
  for(int i=0;i<N;i++) {
    cin >> city >> score;
    v.push_back(make_tuple(city,score, i));
  }
  
  sort(v.begin(), v.end(), [](const tuple<string, int, int>& t1, const tuple<string,int,int>& t2) {
    string city1;
    int score1;
    tie(city1, score1, ignore) = t1;
    
    string city2;
    int score2;
    tie(city2, score2, ignore) = t2;

    
    if (city1 < city2) return true;
    else if (city1 == city2) return score1 > score2;
    return false;
  });
  
  for(int i=0;i<N;i++) {
    cout << get<2>(v[i]) + 1<< endl;
  }
  
}

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

int n;
char a[105];

signed main()
{
	string s;
	cin>>s;
	n=s.size();
	for (int i=0;i<=n-1;i++)  a[i+1]=s[i];
	
	for (int i=1;i<=n/2;i++)
	{
		if (a[i]!=a[n+1-i])  return cout<<"No"<<endl,0;
	}
	for (int i=1;i<=(n-1)/2;i++)
	{
		if (a[i]!=a[(n+1)/2-i])  return cout<<"No"<<endl,0;
	}
	for (int i=(n+3)/2;i<=n;i++)
	{
		if (a[i]!=a[((3*n+3)/2)-i])  return cout<<"No"<<endl,0;
	}
	cout<<"Yes"<<endl;
	
	return 0;
}

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

int main() {
	int hour, hour_price, fix_price, calc;
  	cin >> hour >> hour_price >> fix_price;
  
  	calc = hour * hour_price;
    if(calc > fix_price){
    	cout << fix_price << endl;
    } else {
      cout << calc << endl;
    }
}
  

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

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

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

  vector<string> youbi = {"SUN","MON","TUE","WED","THU","FRI","SAT"};
  int now=0;
  rep(i,7){
    if(youbi.at(i)==s) now=i;
  }

  cout << 7-now;
}

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

int main()
{
  int A, B, C, X;
  int count = 0;
  cin >> A >> B >> C >> X;
  for (int a = 0; a <= A; a++)
  {
    for (int b = 0; b <= B; b++)
    {
      for (int c = 0; c <= C; c++)
      {
        int total = 500 * a + 100 * b + 50 * c;
        if (total == X) 
          count++;
      }
    }
  }
  cout << count << endl;
}


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

#define LOOP(val,times) for(val = 0;val < (times);++val)

int main(){
  set <int> st;
  int i,n,a;
  scanf("%d",&n);
  LOOP(i,n){
    scanf("%d",&a);
    st.insert(a);
  }
  printf("%d\n",st.size());
}
  

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

#define forn(i, n) for (int i = 0; i < int(n); i++)
#define nfor(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define fore(i, l, r) for (int i = int(l); i < int(r); i++)
#define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
#define all(a) (a).begin(), (a).end()
#define sz(a) int((a).size())
#define pb(a) push_back(a)
#define mp(x, y) make_pair((x), (y))
#define x first
#define y second

using namespace std;

typedef long long li;
typedef long double ld;
typedef pair<int, int> pti;

template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

template<typename A, typename B> inline ostream& operator<< (ostream& out, const pair<A, B>& p) { return out << "(" << p.x << ", " << p.y << ")"; }
template<typename T> inline ostream& operator<< (ostream& out, const vector<T>& a) { out << "["; forn(i, sz(a)) { if (i) out << ','; out << ' ' << a[i]; } return out << " ]"; }
template<typename T> inline ostream& operator<< (ostream& out, const set<T>& a) { return out << vector<T>(all(a)); }
template<typename X, typename Y> inline ostream& operator<< (ostream& out, const map<X, Y>& a) { return out << vector<pair<X, Y>>(all(a)); }
template<typename T> inline ostream& operator<< (ostream& out, const pair<T*, int>& a) { return out << vector<T>(a.x, a.x + a.y); }

inline ld gett() { return ld(clock()) / CLOCKS_PER_SEC; }

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;

#ifdef SU1
//#define GEN
#ifndef GEN
#define LOG
#endif
#endif

const int N = 100100;

int n;
char buf[20];
string a[N];

bool read() {
  if (!(cin >> n)) return false;
  forn(i, n) {
    assert(scanf("%s", buf) == 1);
    a[i] = buf;
  }
  return true;
}

void solve() {
  string s("MARCH");
  map<char, int> cnt;
  forn(i, n) cnt[a[i][0]]++;

  set<string> dic;
  sort(all(s));
  do {
    string c = s.substr(0, 3);
    sort(all(c));
    dic.insert(c);
  } while (next_permutation(all(s)));

  li ans = 0;
  for (auto c : dic) {
    li cur = 1;
    forn(i, sz(c)) cur *= cnt[c[i]];
    ans += cur;
  }
  cout << ans << endl;
}

int main() {
#ifdef SU1
  assert(freopen("input.txt", "rt", stdin));
  //assert(freopen("output.txt", "wt", stdout));
#endif

  cout << setprecision(10) << fixed;
  cerr << setprecision(5) << fixed;

  while (read()) {
    ld stime = gett();
    solve();
#ifdef SU1
    cerr << "Time: " << gett() - stime << endl;
#endif
    //break;
  }

  return 0;
}


Measured memory_bytes: 5760
from sys import stdin

class Node:
    def __init__(self, v, parent=None, left=None, right=None):
        self.value = v
        self.parent = parent
        self.left = left
        self.right = right

class BST:
    def __init__(self):
        self.root = None

    def insert(self, v):
        cur = self.root
        cur_p = None
        while cur != None:
            cur_p = cur
            if v < cur.value:
                cur = cur.left
            elif v > cur.value:
                cur = cur.right

        n = Node(v, cur_p)
        if cur_p == None:
            self.root = n
        elif v < cur_p.value:
            cur_p.left = n
        else:
            cur_p.right = n

    def preorder(self):

        def rec_preorder(t=self.root):
            if t != None:
                print(" ", t.value, sep="", end="")
                rec_preorder(t.left)
                rec_preorder(t.right)

        rec_preorder()
        print()

    def inorder(self):

        def rec_inorder(t=self.root):
            if t != None:
                rec_inorder(t.left)
                print(" ", t.value, sep="", end="")
                rec_inorder(t.right)

        rec_inorder()
        print()

    def find(self, x):

        def rec_find(t=self.root):
            if t == None:
                return False
            elif x > t.value:
                return rec_find(t.right)
            elif x < t.value:
                return rec_find(t.left)
            else:
                return True

        return rec_find()

m = int(stdin.readline().rstrip())
t = BST()
for _ in range(m):
    q = stdin.readline().rstrip().split()
    if q[0] == "insert":
        t.insert(int(q[1]))
    elif q[0] == "find":
        if t.find(int(q[1])):
            print("yes")
        else:
            print("no")
    elif q[0] == "print":
        t.inorder()
        t.preorder()


Measured memory_bytes: 85636
from fractions import gcd

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

A,B,C,D = [int(zz) for zz in input().split()]

bc = B//C
ac = (A-1)//C
bd = B//D
ad = (A-1)//D
bcd = B//lcm(C,D)
acd = (A-1)//lcm(C,D)

print(B-A-bc+ac-bd+ad+bcd-acd+1)


Measured memory_bytes: 5076
import java.util.Scanner;

public class Main{
	static int c[][];
	static int h,w;
	private static void land(int x, int y){
		c[x][y] = 0;

		for(int i = x-1; i <= x+1; i++){
			if(i < 0 || i >= h) continue;
			for(int j = y-1; j <= y+1; j++){
				if(j < 0 || j >= w) continue;
				if(c[i][j] == 1) land(i, j);
			}
		}
	}
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		while(true){
			int count = 0;
			w = sc.nextInt();
			h = sc.nextInt();
			if(w == 0 && h == 0) break;
			c = new int[h][w];
			for(int i = 0; i < h; i++){
				for(int j = 0; j < w; j++){
					c[i][j] = sc.nextInt();
				}
			}
			for(int i = 0; i < h; i++){
				for(int j = 0; j < w; j++){
					if(c[i][j] == 1){
						land(i, j);
						count++;
					}
				}
			}
			System.out.println(count);
		}
	}
}


Measured memory_bytes: 44404
let count lst = 
  let is_digit x = "0" <= x && x <= "9" in
  let (x, y) = List.fold_left (fun (x, y) z -> if is_digit z then (10 * x + int_of_string z, y) else (0, x + y)) (0, 0) lst in
  x + y

let rec loop n =
  try
    let slst = Str.split (Str.regexp "") @@ read_line () in
    let x = count slst in
    loop (n + x)
  with
    End_of_file -> Printf.printf "%d\n" n

let _ = loop 0

Measured memory_bytes: 2436
import java.util.Scanner;

public class Main {
	public static void main(String[] args)  {
		Scanner sc = new Scanner(System.in);
		String s = sc.nextLine();
		sc.close();
		char[] c = s.toCharArray();
		int count = 0;
		for(int i = 0; i < c.length; i++) {
			for(int j = 0; j < c.length; j ++) {
				if(c[i] == c[j]) {
					count++;
				}
			}
			if(count % 2 != 0) {
				System.out.println("No");
				return;
			}
			count = 0;
		}
		System.out.println("Yes");
	}
}

Measured memory_bytes: 23892
#include<stdio.h>
int main()
{
	int n,x;
	while(~scanf("%d%d",&n,&x))
{
	int a[n+1],b[n];
	int i;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	b[0]=0;
	for(i=1;i<=n;i++)
	 {
	 	b[i]=b[i-1]+a[i];
	 }
	 int t=0;
	 for(i=0;i<=n;i++)
	 {
	 	if(b[i]<=x)
	 	t=t+1;
	 }
	 printf("%d\n",t);
}
	 return 0;
}

Measured memory_bytes: 256
fn read<T: std::str::FromStr>(
    stdin_lock: &mut std::io::StdinLock,
    buf: &mut Vec<u8>,
    delimiter: u8,
) -> T {
    buf.clear();
    let l = std::io::BufRead::read_until(stdin_lock, delimiter, buf).unwrap();
    buf.truncate(l - 1); // remove delimiter
    let s = unsafe { std::str::from_utf8_unchecked(&buf) };
    s.parse().unwrap_or_else(|_| panic!("read"))
}

fn main() {
    let stdin = std::io::stdin();
    let mut stdin_lock = stdin.lock();
    let mut buf: Vec<u8> = Vec::new();
    let n: usize = read(&mut stdin_lock, &mut buf, b'\n');
    let mut av = vec![0i32; n];
    for i in 0..n - 1 {
        av[i] = read(&mut stdin_lock, &mut buf, b' ');
    }
    av[n - 1] = read(&mut stdin_lock, &mut buf, b'\n');

    let mut cv = vec![(0i32, 0usize); n];
    for i in 0..n {
        cv[i].0 = av[i];
        cv[i].1 = i + 1;
    }
    cv.sort();
    for i in 0..n - 1 {
        print!("{} ", cv[i].1)
    }
    println!("{}", cv[n - 1].1)
}


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

#define int long long
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define vcopy(v1,v2) copy((v1).begin(), (v1).end(), back_inserter((v2)));
#define pb(n) push_back(n);

int n;
vector<int> v;

main() {
    cin >> n;
    rep1(i,31622) v.pb(pow(i,2));
    auto it = upper_bound(all(v),n);
    ct(v[it-v.begin()-1])
}

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

#define fir first
#define sec second

using namespace std;

typedef long long LL;
typedef pair<LL, LL> pll;

const int M = 87;
const int mod = 1e9 + 7;

int T, type;
LL f[M + 5];
vector<pll> exc[90];

inline void Dec(int& x)
{ x >= mod ? x -= mod : 0; }

void Init()
{
    f[0] = f[1] = 1;
    for (int i = 2; i <= M; ++i)
        f[i] = f[i - 1] + f[i - 2];
    exc[0].push_back(pll(1, 1));
    for (int i = 0; i < M; ++i)
    {
        for (auto j : exc[i])
            exc[i + 1].push_back(pll(j.sec, j.fir + j.sec));
        exc[i + 1].push_back(pll(exc[i][0].sec, exc[i][0].fir + exc[i][0].sec * 2));
    }
}

inline int Level(LL x, LL y)
{
    int pos = upper_bound(f + 1, f + M + 1, x) - f - 1;
    return pos - (f[pos + 1] > y);
}

inline LL Calc(LL limx, LL limy, pll gre)
{
    if (gre.sec > limx or gre.fir + gre.sec > limy)
        return 0;
    return (limy - gre.fir) / gre.sec % mod;
}

int main()
{
    ios::sync_with_stdio(false);
    Init();
    type = 1;
    cin >> T;
    if (type == 1)
    {
        while (T--)
        {
            LL x, y;
            int ans, k;
            cin >> x >> y;
            if (x > y)
                swap(x, y);
            if (x == 1)
                k = 1, ans = y % mod;
            else if (y == 2)
                k = 1, ans = 4;
            else
            {
                ans = 0, k = Level(x, y);
                for (auto i : exc[k - 1])
                    Dec(ans += Calc(x, y, i)), Dec(ans += Calc(y, x, i));
            }
            cout << k << ' ' << ans << endl;
        }
    }
    else
    {
        while (T--)
        {
            LL x, y;
            cin >> x >> y;
            if (x > y)
                swap(x, y);
            int ans = (x + y - (x == 1)) % mod, k = Level(x, y);
            for (int i = 1; i <= k; ++i)
            {
                for (int j = 0; j < i; ++j)
                {
                    Dec(ans += Calc(x, y, exc[i][j]));
                    Dec(ans += Calc(y, x, exc[i][j]));
                }
                pll t = exc[i][i];
                if (t.sec <= x and t.fir + t.sec <= y)
                    Dec(++ans);
                if (t.sec <= y and t.fir + t.sec <= x)
                    Dec(++ans);
            }
            cout << ans << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T> using Graph = vector<vector<T>>;

#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) REP(i, 0, a)
#define EACH(i, a) for (auto i: a)
#define ITR(x, a) for (__typeof(a.begin()) x = a.begin(); x != a.end(); x++)
#define ALL(a) (a.begin()), (a.end())
#define HAS(a, x) (a.find(x) != a.end())
#define endl '\n'

int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

int Y, X, K;
char A[805][805];
int sx, sy;

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  // breath deeply and calm down

  cin >> Y >> X >> K;
  rep(y, Y) rep(x, X) cin >> A[y][x];
  rep(y, Y) rep(x, X) if (A[y][x] == 'S') sx = x, sy = y;

  queue<pair<int, int>> que;
  que.push(make_pair(sx, sy));
  rep(loop, K) {
    queue<pair<int, int>> nque;
    while (!que.empty()) {
      auto p = que.front(); que.pop();
      int x = p.first, y = p.second;
      rep(i, 4) {
          int nx = x + dx[i], ny = y + dy[i];
          if (!(0 <= nx && nx < X && 0 <= ny && ny < Y)) continue;
          if (A[ny][nx] == '#') continue;
          if (A[ny][nx] == 'S') continue;
          A[ny][nx] = 'S';
          nque.push(make_pair(nx, ny));
      }
    }
    que = nque;
  }
 

  int ans = 10000;
  rep(y, Y) rep(x, X) {
    if (A[y][x] == 'S') ans = min(ans, (min(min(x, X - x - 1), min(y, Y - y - 1)) + K - 1)/K + 1);
  }
  
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
int max(int p,int q){
    if(p>q) return p;
    else return q;
}
int main(void){
    int n,m,x,y,i,ans=0;
    scanf("%d%d",&n,&m);
    int a[n],h[n];
    for(i=0;i<n;i++){
        scanf("%d",&h[i]);
        a[i]=0;
    }
    for(i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        a[x-1] = max(a[x-1],h[y-1]);
        a[y-1] = max(a[y-1],h[x-1]);
    }
    for(i=0;i<n;i++){
        if(h[i]>a[i]) ans++;
    }
    printf("%d",ans);
    return 0;
}

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

using namespace std;

int main(void){
    
    int n;
    cin >> n;
    
    map<int,int> mp;
    
    for (int i = 0; i < n; i++){
        int a;
        cin >> a;
        
        mp[a] = i + 1;
    }
    
    for (auto p : mp){
        cout << p.second << " ";
    }
    cout << endl;
    
}


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

using namespace std;

#define int long long

#ifndef bhupixb
    #define var(...)
    #define stl(...)
#endif

#define single_test

const int maxn = 3e5 + 3;

set<pair<int,int>> st;
int freq[maxn];

inline void add(int x) {
    st.erase({freq[x], x});
    freq[x]++;
    st.insert({freq[x], x});
}

inline void remove(int x) {
    st.erase({freq[x], x});
    freq[x]--;
    st.insert({freq[x], x});
}

int ask(vector<array<int,2>> v) {
    sort(v.begin(), v.end());
    st.clear();
    memset(freq, 0, sizeof freq);
    const int N = v.size();
    for (auto &it: v) {
        freq[it[1]]++;
    }

    for (int i = 1; i < maxn; ++i) {
        if (freq[i]) {
            st.insert({freq[i], i});
        }
    }
    int ret = 0;
    for (int i = 0; i < N; ) {
        int cur = v[i][0], cnt = 0;
        int index = i;
        while (i < N && v[i][0] == cur) {
            remove(v[i][1]);
            ++i;
            ++cnt;
        }
        int ans = cnt;
        if (!st.empty()) {
            auto it = --st.end();
            ans += it->first;
        }
        ret = max(ret, ans);
        i = index;
        while (i < N && v[i][0] == cur) {
            add(v[i][1]);
            ++i;
        }
    }
    return ret;
}

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<array<int, 2>> v(q);
    for (int i = 0; i < q; ++i) {
        cin >> v[i][0] >> v[i][1];
    }
    int ans = ask(v);
    for (auto &it: v) {
        swap(it[0], it[1]);
    }
    ans = max(ans, ask(v));
    cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    #ifndef single_test
        cin >> t;
    #endif
    for (int i = 1; i <= t; ++i) {
        // cout << "Case #" << i << ": ";
        solve();
    }

    return 0;
}

Measured memory_bytes: 33816
#include <iomanip>
#include <random>
#include <time.h>
#include <vector>
#include <queue>
#include <functional>
#include <map>
#include <string>
#include <cstdlib>
#include <typeinfo>
#include <math.h>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

int main() {
	ll n, l[100];
	l[0] = 2, l[1] = 1;
	cin >> n;
	for (int i = 2; i <= n; i++) {
		l[i] = l[i - 1] + l[i - 2];
	}
	cout << l[n] << endl;
	return 0;
}


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

int main() {
  int N;
  cin >> N;
  map<string,int> S;
  string s;
  for(int i=0; i<N; i++) {
    cin >> s;
    if(S.count(s)==0){
      S[s] = 1;
    }
  }
  cout << S.size() << endl;
}

Measured memory_bytes: 19116