akhauriyash/Code-Regression huggingface dataset:
//includes
#include<iostream>
#include<vector>
#include<set>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<string>
#include<stack>
#include<map>
#include<queue>
#include<iomanip>
#include<numeric>
#include<assert.h>
#include<cstring>
#include<unordered_map>
#include<bitset>

//macros and consts
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(),(a).end()
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define FORE(i,a) for(auto &i : a)
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define accm accumulate
#define Fi first
#define Se second
#define INF 1e9
#define llINF (1LL<<60)
#define mINF -1e9
#define mllINF -(1LL<<60)
#define endl "\n"
#define CONT continue
#define BRK break
#define modulo(n, m) (((n)%(m)+(m))%m)

//shorter types
using namespace std;
using ll = long long;
using vi = std::vector<int>;
using vc = std::vector<char>;
using vll = std::vector<long long>;
using vs = std::vector<string>;
using Mi = map<int,int>;
using Mll = map<ll,ll>;
using UMi = unordered_map<int,int>;
using UMll = unordered_map<ll,ll>;
using Pi = pair<int,int>;
using Pll = pair<ll,ll>;
using vPi = vector<Pi>;
using vPll = vector<Pll>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
using vvc = vector<vector<char>>;
using vvs = vector<vector<string>>;
using pqgi = priority_queue<int,vector<int>,greater<int>>;
using pqsi = priority_queue<int,vector<int>,less<int>>;
using pqgll = priority_queue<int,vector<int>,greater<int>>;
using pssll = priority_queue<int,vector<int>,less<int>>;
template<class T>
using vec = vector<T>;

//here begins your code
signed main(){
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  string S;
  cin >> S;
  int l = S.length();
  int res = 0;
  if(l % 2 == 0){
  	for(int i = 0 ; i <= (l/2) - 1 ;i++){
  		if(S[i] == S[l-1 - i]){
  			continue;
  		}
  		else{
  			res++;
  		}
  	}
  }
  else{
  	for(int i = 0 ; i < (l-1)/2 ; i++){
  		if(S[i] == S[l - 1 -i]) continue;
  		else{
  			res++;
  		}
  	}
  }
  cout << res << endl;
  //check types
  //do not eb if you resize
  //resize before you access by idx
  return 0;
} 

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

int main(){
    int N;
    cin >> N;
    vector<double> v(N);

    for(int i = 0; i < N; i++){
        cin >> v.at(i);
    }

    double sum = 0.0;
    sort( v.begin(), v.end());

    sum = (v.at(0) + v.at(1))/2;

    for(int i = 2; i < v.size(); i++){
        sum = (sum + v.at(i))/2;
    }

    cout << sum << endl;

}

Measured memory_bytes: 3696
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPL(i, n) for (long long i = 0; i < n; i++)
typedef long long ll;
using namespace std;
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll A, B, M;
    vector<pair<ll, ll>> a, b;
    vector<ll> x, y, c;
    cin >> A >> B >> M;
    REPL(i, A)
    {
        ll k;
        cin >> k;
        a.push_back(pair<ll, ll>(k, i));
    }
    REPL(i, B)
    {
        ll k;
        cin >> k;
        b.push_back(pair<ll, ll>(k, i));
    }
    ll m=100000000;
    REPL(i, M)
    {
        ll k, j, l;
        cin >> k >> j >> l;
        x.push_back(k);
        y.push_back(j);
        c.push_back(l);
        m = min(m, a[k-1].first+b[j-1].first-l);
    }
        sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    ll mi;
    ll s = 0;
    int flag = 0;
    mi = a[0].first + b[0].first;
    REP(i, M)
    {
        if (a[0].second == x[i]-1 && b[0].second == y[i]-1)
        {
            s = max(s, c[i]);
            flag = 1;
        }
    }
    mi -= s;
    if(mi>m) {
        cout << m << endl;
    }else {
        cout << mi << endl;
    }
}

Measured memory_bytes: 7024
import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        int c = in.nextInt();
        if(a+b==c||b+c==a||a+c==b){
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 9812
from collections import defaultdict
from itertools import permutations
def solve():
    n = int(input())
    XY = [list(map(int, input().split())) for _ in range(n)]
    if n == 1:
        return 1
    m = defaultdict(int)
    for i, j in permutations(range(n), 2):
        m[(XY[i][0] - XY[j][0], XY[i][1] - XY[j][1])] += 1
    return n - max(m.items(), key=lambda x: x[1])[1]
print(solve())


Measured memory_bytes: 3828
#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>;

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; }
const ll llINF = 1LL << 60;
const int iINF = 1e8;

//---main---------------------------------------------
int main(){
    //main
    int N,X,T;
    cin >> N >> X >> T;

    int ans;
    ans = (N/X)*T + (N%X>0)*T;

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3632
import java.util.Scanner;

class Main
{
	public static void main(String[]args){
	Scanner scan = new Scanner(System.in);
	
	int X = 0;
	String[] str = new String[10];
	char[] kari = new char[200];
	int[] m = new int[10];
	int[][] h = new int[10][200];
	String kekka;
	int i, x, z, j, q, r;
	String a = "";
	String kari2;
		
	while(scan.hasNext()){
		str[X] = scan.next();
		if(str[X].equals("-")){
			break;}
		kari2 = scan.next();
		m[X] = Integer.parseInt(kari2);
		for(i=0; i<m[X]; i++){
			kari2 = scan.next();
			h[X][i] = Integer.parseInt(kari2);}


		kekka = "";
		char[] tan = str[X].toCharArray();
		for(z=0; z<tan.length; z++){}
		for(i=0; i<m[X]; i++){
			for(j=0; j<h[X][i]; j++){
				kari[j] = tan[j];}
			for(q=0; q<z-j; q++){
				tan[q] = tan[j+q];}
			for(r=q; r<z; r++){
				tan[r] = kari[r-q];}}
		for(j=0; j<tan.length; j++){
				kekka += tan[j];}
		System.out.println(kekka);}
	}
}


Measured memory_bytes: 26168
#include<bits/stdc++.h>
#define PI acos(-1.0)
#define pb push_back
#define F first
#define S second
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int MOD=1e9+7;
ll a[N];
ll sum[N];
//ll ans[N];
map<string,ll> mp;
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    string s;
    for(int i=0;i<3;i++){
        cin >> s;
        cout << s[i];
    }
    puts("");

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d", &x)
#define sz(v) (int) v.size()
#define pr(v) For(i, 0, sz(v)) {cout<<v[i]<<" ";} cout<<endl;
#define slld(x) scanf("%lld", &x)
#define all(x) x.begin(), x.end()
#define For(i, st, en) for(ll i=st; i<en; i++)
#define tr(x) for(auto it=x.begin(); it!=x.end(); it++)
#define fast std::ios::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define ll long long
#define ld long double
#define int long long
#define double long double
#define mp make_pair
#define F first
#define S second
typedef pair<int, int> pii;
typedef vector<int> vi;
#define pi 3.141592653589793238
const int MOD = 1e9+7;
const int INF = 1LL<<60;


const int N = 1e7+5;

// it's swapnil07 ;)
 
#ifdef SWAPNIL07
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
int begtime = clock();
#define end_routine() cout << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";
#else
#define endl '\n'
#define trace(...)
#define end_routine()
#endif


int spf[N];


void precompute(){
    For(i, 2, N){
        if(spf[i])
            continue;
        spf[i]=i;
        for(int j=i*i; j<N; j+=i){
            if(!spf[j])
                spf[j]=i;
        }
    }
}

vector<int> vect;

void solve(){
    int n; cin>>n;
    int ans = 1;
    For(k, 2, n+1){
        int j = k;
        vect.clear();
        while(j!=1){
            vect.pb(spf[j]);
            j /= spf[j];
        }
        int cur = 1;
        int p = 0;
        int ct = 0;
        For(i, 0, sz(vect)){
            if(vect[i]!=p){
                cur = cur*(ct+1);
                ct = 1;
                p = vect[i];
            }
            else{
                ct++;
            }
        }
        cur = cur*(ct+1);
        ans += (cur*k);
    }
    cout<<ans;
}


signed main()
{
    fast
    #ifdef SWAPNIL07
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    int t=1; 
    precompute();
    // cin>>t;
    while(t--){
        solve();
        cout<<"\n";
    }
    return 0;
}



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

using namespace std;
int main(){
    string s;
    cin>>s;
    int ret = 0;
    for(int i=0;i<s.length();i++){
        if(s[i]!=s[s.length()-1-i])
            ret++;
    }
    cout<<ret/2;
}

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

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> vll;


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


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);



int main(){
  int n;
  cin >> n;
  int ans = n/3;

  cout << ans << endl; 
  return 0;
}


Measured memory_bytes: 3600
#include <stdio.h>
#include <string.h>
int main(){
    char s1[4],s2[4];
    scanf("%s",s1);
    scanf("%s",s2);
    int a=strlen(s1);
    if(a==1){
        if(s1[0]==s2[0]){
            printf("YES");
        }
        else{
            printf("NO");
        }
    }
    else if(a==2){
        if(s1[0]==s2[1]&&s1[1]==s2[0]){
            printf("YES");
        }
        else{
            printf("NO");
        }
    }
    else{
        if(s1[0]==s2[2]&&s1[1]==s2[1]&&s1[2]==s2[0]){
            printf("YES");
        }
        else{
            printf("NO");
        }
    }
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
bool a[100001];
int  c[100001];
void se(){
    a[0] = true;
    a[1] = true;
    for(int i=2;i<sqrt(100001);i++){
        if(!a[i]){
            for(int j=i+i;j<100001;j = j + i){
                a[j] = true;
            }
        }
    }
}
int main()
{

    se();
    for(int i=0;i<100001;i++){
        if(!a[i] && !a[(i+1)/2])c[i] = 1;
    }
    for(int i=1;i<100001;i++){
        c[i] = c[i] + c[i-1];
    }
    int m ;
    cin>>m;
    while(m--){
        int c1,c2;
        cin>>c1>>c2;
        cout<<c[c2]-c[c1-1]<<endl;
    }
    return 0 ;
}


Measured memory_bytes: 1152
#include<iostream>
#include<cmath>
using namespace std;
double h[100001],b,n,t,a;
int main()
{
	cin>>n;
	cin>>t>>a;
	for(int i=1;i<=n;i++) cin>>h[i];
	for(int i=1;i<=n;i++) h[i]=t-h[i]*0.006;
	int ans=1;
	for(int i=2;i<=n;i++) 
	{
		if(abs((a-h[i]))<abs((a-h[ans]))) ans=i;
	}
	cout<<ans;
 } 

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

int n, a[100005], v, ans;

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        if(i == 0)continue;
        if(a[i] > a[i - 1]){
            if(v == 0){
                v = 1;
            }
            else if(v == 2){
                ans++;
                v = 0;
            }
        }
        else if(a[i] < a[i - 1]){
            if(v == 0){
                v = 2;
            }
            else if(v == 1){
                ans++;
                v = 0;
            }
        }
    }
    cout << ans + 1 << endl;


    return 0;
}


Measured memory_bytes: 640
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <queue> //C++
#include <string> //C++
#include <iostream> //C++
#include <vector> //C++
#include <algorithm> //C++
using namespace std; //C++
#define rep(i, a, n) for (i = (a); i < (n); i++)

//C++で提出







int main()
{
	int w;
	int x, y;
	cin >> w;
	int i;

	rep(i, 1, 10) {
		if (w % i == 0) {
			if ((w / i) < 10) {
				cout << "Yes";
				return 0;
			}
		}

	}
	cout << "No";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
     
int main() {

    // 変数を宣言
    int N, H, W;

    cin >> N >> H >> W;
    int P = 0;
 
    vector<vector<int>> data(N, vector<int>(2));

    // 配列に値を代入
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 2; j++) {
            cin >> data.at(i).at(j);
        }
    }

    // 素材が得られるかを判定
     for (int i = 0; i < N; i++) {

      // 上からi番目において、左から1番目がHで割り切れ、かつ2番目がWで割り切れる場合はpossibleをインクリメント
        if (data.at(i).at(0)  >= H  && data.at(i).at(1) >= W ) {
            P++;
        }
    } 

    cout << P << endl;

}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
	static void Main()
	{
		int.Parse(Console.ReadLine());
		var t = Array.ConvertAll(Console.ReadLine().Split(new[] { ' ' }), number => int.Parse(number));

		var nums = new Dictionary<int, int>();
		foreach (var a in t) {
			if (nums.ContainsKey(a)) {
				nums[a] += 1;
			} else {
				nums.Add(a, 1);
			}
		}

		var maxNum = 0;
		var maxSum = 0;
		foreach (var num in nums) {
			var sum = num.Value;
			if (nums.ContainsKey(num.Key - 1)) {
				sum += nums[num.Key - 1];
			}

			if (nums.ContainsKey(num.Key + 1)) {
				sum += nums[num.Key + 1];
			}

			if (sum > maxSum) {
				maxNum = num.Key;
				maxSum = sum;
			}
		}

		Console.WriteLine(maxSum);

		//デバッグ実行での確認用。そのまま提出しても問題なし		
		Console.ReadKey();
	}
}


Measured memory_bytes: 28124
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        String[] lines = getStdin();
        String str = lines[0];
        String[] str1 = str.split(" ");
        int a = Integer.parseInt(str1[0]);
        int b = Integer.parseInt(str1[1]);
        int c = Integer.parseInt(str1[2]);
        int count = 0;

        for (int i = a; i <= b; i++){
         if (c % i == 0){
            count++;
         }
        }
        System.out.println(count);
        
    }
  
  private static String[] getStdin() {
    Scanner scanner = new Scanner(System.in);
    ArrayList<String> lines = new ArrayList<>();
    while (scanner.hasNext()) {
      lines.add(scanner.nextLine());
    }
    return lines.toArray(new String[lines.size()]);
  }
  
}



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

int main(){
	int h,w;
	cin >> h >> w;
	int a,b;
	cin >> a >> b;
	int ans[1005][1005];
	
	rep(i,h){
		rep(j,w){
			if(i<b && j<a){
				ans[i][j] = 1;
			} else if (i < b && j >= a){
				ans[i][j] = 0;
			} else if (i >= b && j < a){
				ans[i][j] = 0;
			}else{
				ans[i][j] = 1;
			}
		}
	}
	
	rep(i,h){
		rep(j,w){
			cout << ans[i][j];
		}
		cout << endl;
	}
    return 0;
}



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

int n,m,p,sum;
int x[105];

int main(){
  int i;
  while(1){
    cin >> n >> m >> p;
    if(n+m+p==0)break;
    sum=0;
    for(i=1;i<=n;i++){
      cin >> x[i];
      sum+=x[i];
    }
    if(x[m]==0)cout << 0 << endl;
    else cout << sum*(100-p)/x[m] << endl;
  }
  return 0;
}



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

int main(void){
    // Your code here!
    char str[100001];
    char *test[4] = {"dreamer","dream","eraser","erase"};
    
    scanf("%100000s",str);
    
    for(int i = strlen(str)-1;i >= 4;){
        int j,flag = 0;
        for(j = 0;j<4;j++){
            int k,len = strlen(test[j]);
            for(k=0;test[j][k]!='\0';k++){
                if(test[j][len-k-1] != str[i-k]){
                    break;
                }
            }
            if(k==len){
                //printf("j_%d\n",j);
                flag = 1;
                break;
            }
        }
        if(flag != 1){
            printf("NO\n");
            return 0;
        }
        i -= strlen(test[j]);
    }
    
    printf("YES\n");
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;

namespace C
{
    class Program
    {
        static void Main(string[] args)
        {
            var c = new List<List<int>>();

            for (int i = 0; i < 3; i++)
            {
                c.Add(Console.ReadLine().Split().Select(int.Parse).ToList());
            }

            foreach (var item in c) item.AddRange(item);

            var ansCheckList = new List<int>();
            for(int i=0;i<3;i++)
            {
                ansCheckList.Add(c[0][i]+c[1][i+1]+c[2][i+2]);
            }

            var ans = ansCheckList[0] == ansCheckList[1] && ansCheckList[1] == ansCheckList[2];
            
            Console.WriteLine(ans?"Yes":"No");
        }
    }
}


Measured memory_bytes: 13396
import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(new BufferedInputStream(System.in));
        int a=sc.nextInt();
        String b=sc.next();
        char m[]=b.toCharArray();
        if(a<3)
            System.out.println("0");
        else{
            int count=0;
            for(int i=2;i<m.length;i++){
                if(m[i-2]=='A'&&m[i-1]=='B'&&m[i]=='C')
                    count++;
            }
            System.out.println(count);
        }

    }
}


Measured memory_bytes: 21972
function Main(input) {
    input = input.trim().split("\n").map(function(x) { return x.split(" ")});
    let S = input[0][0];
    let ans = 0;
    if (S === 'RSR' || S === 'RSS'|| S === 'SRS' || S === 'SSR') ans = 1;
    else if (S === 'RRS' || S === 'SRR') ans = 2;
    else if (S === 'RRR') ans = 3;
    console.log(ans);

}


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


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

using namespace std;

int main()
{
    int N, X, m, Sum = 0, Ingredient, Max;
    cin >> N >> X;
    vector<int> v;

    for (int i = 0; i < N; i++)
    {
        cin >> m;
        v.push_back(m);
        Sum += m;
    }

    if (Sum - X != 0)
    {

        sort(v.begin(), v.end());
        Ingredient = v[0];

        Max = ((X - Sum) / Ingredient) + N;
        cout << Max;
    }

    if (Sum - X == 0)
    {
        cout << N;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7,MAX = 1e5;

int main()
{
   string s;
   cin >> s;
   int n, q;
   cin >> q;
   n = s.size();
   deque<char> ans;
   for(int i = 0;i< n ;i++)
   {
      ans.push_back(s[i]);
   }
   bool re = false;
   
   for(int i = 0;i<q;i++)
   {
      int qq;
      cin >> qq;
      if(qq == 1)
      {
         if(re)re=false;
         else re = true;
      }
      else
      {
         int t;
         char f;
         cin >> t >> f;
         if(t==1)
         {
            if(re)ans.push_back(f);
            else ans.push_front(f);
         }
         else
         {
            if(re) ans.push_front(f);
            else ans.push_back(f);
         }
      }
      //<<re<<endl;
   }
   
   if(re)
   {
   for(int i=ans.size()-1;i>=0;i--)
   {
      cout<<ans[i];
   }
   }
   else
   {
    for(int i =0;i<ans.size();i++)
   {
      cout<<ans[i];
   }
   }
   cout<<endl;
   return 0;
}

Measured memory_bytes: 896
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 100+15
typedef long long ll;
ll a[MAXN]={0};
int main(){
  ll n,x;
  cin>>n>>x;
  for(int i = 0;i < n;i++){
    cin>>a[i];
  }
  sort(a,a+n);
  int count = 0;
  for(int i = 0;i < n-1;i++){
    if(a[i]<=x){
      x-=a[i];
      count++;
    }
  }
  if(x==a[n-1]){
    count++;
  }
  cout<<count;

}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

const double EPS = 1e-10;

bool intersect(double xa, double ya, double xb, double yb, double xc, double yc, double xd, double yd,
               double &r, double &s){
    double g = (xb - xa)*(yd - yc) - (yb - ya)*(xd - xc);
    if (fabs(g) < EPS) return false;
    r = ((yd - yc)*(xc - xa) - (xd - xc)*(yc - ya)) / g;
    s = ((yb - ya)*(xc - xa) - (xb - xa)*(yc - ya)) / g;
    return true;
}

const int N = 50;
const double INF = 1e9;
int n;
double x[N], y[N];

double calc(double px, double py){
    double ret = 0;
    REP(i,n){
        double d = sqrt((px - x[i]) * (px - x[i]) + (py - y[i]) * (py - y[i]));
        chmax(ret, d);
    }
    return ret;
}

pair<double, double> circumcenter(double x1, double y1, double x2, double y2, double x3, double y3){
    double xc1 = (x1 + x2) / 2, yc1 = (y1 + y2) / 2;
    double xc2 = (x1 + x3) / 2, yc2 = (y1 + y3) / 2;
    double xd1 = xc1 - (y2 - y1), yd1 = yc1 + (x2 - x1);
    double xd2 = xc2 - (y3 - y1), yd2 = yc2 + (x3 - x1);
    double r, s;
    bool f = intersect(xc1, yc1, xd1, yd1, xc2, yc2, xd2, yd2, r, s);
    if (!f) return make_pair(INF, INF);
    double x = xc1 + (xd1 - xc1) * r;
    double y = yc1 + (yd1 - yc1) * r;
    return make_pair(x, y);
}

int main(void){
    cin >> n;
    REP(i,n) cin >> x[i] >> y[i];
    double ans = INF;
    REP(i,n) REP(j,i){
        double px = 0.5 * (x[i] + x[j]);
        double py = 0.5 * (y[i] + y[j]);
        chmin(ans, calc(px, py));
    }
    REP(i,n) REP(j,i) REP(k,j){
        auto tmp = circumcenter(x[i], y[i], x[j], y[j], x[k], y[k]);
        double px = tmp.first, py = tmp.second;
        if (px == INF) continue;
        chmin(ans, calc(px, py));
    }

    printf("%.15f\n", ans);
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<math.h>
#include<map>
#include<iomanip>
#include<functional>

using namespace std;
using  ull = unsigned long long int;

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

bool check(string word) {

	bool flag = true;
	rep(i, 0, word.size()) {
		if (word[0] != word[i]) {
			flag = false;
			return flag;
		}
	}
	return flag;

}

int main() {

	string base,str,tmp;

	cin >> str;
	base = str;

	vector<long long int>alpha(26, 0);

	rep(i, 0, str.size()) alpha[str[i] - 'a']++;
	
	vector<long long int>::iterator maxIt = max_element(alpha.begin(), alpha.end());
	size_t maxIndex = std::distance(alpha.begin(), maxIt);
	
	vector<long long int>mL;
	/*rep(i, 0, alpha.size()) {
		if (alpha[i] == alpha[maxIndex])mL.push_back(i);
	}*/

	rep(i, 0, alpha.size()) {
		if (0<alpha[i])mL.push_back(i);
	}


	vector<long long int>cnt(mL.size(), 0);
	rep(i, 0, mL.size()) {
		str = base;
		maxIndex = mL[i];
		while (!check(str)) {
			tmp = str;
			tmp.pop_back();
			rep(i, 0, tmp.size()) {
				if (str[i] == 'a' + (char)maxIndex || str[i + 1] == 'a' + (char)maxIndex) tmp[i] = 'a' + (char)maxIndex;
				else tmp[i] = str[i];
			}

			str = tmp;
			
			cnt[i]++;
		}
	}

	
	cout << *min_element(cnt.begin(), cnt.end()) << endl;


	return 0;
}

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

int dp[MAX];

int fib(int n) {
  int x;
  if (dp[n] != 0) return dp[n];
  if ( n == 0 || n == 1) return 1;
  else {
    x = fib(n-1) + fib(n-2);
    dp[n] = x;
    return x;
  }
}

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

  for (int i = 0; i <= n; i++) {
    dp[i] = 0;
  }

  ans = fib(n);

  cout << ans << endl;
}


Measured memory_bytes: 3100
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

// CHECK THE LIMITS
typedef long long ll;

static const int NMAX = 1e5;

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

    string s;
    cin >> s;
    int count[2];

    count[0] = 0;
    count[1] = 0;

    int lastPair = -1;
    char cur = 'R';
    int N = (int)s.length();
    int ans[N];
    for(int i = 0; i < N; ++i)
    {
        ans[i] = 0;
    }
    for(int i =0; i< N; ++i)
    {
        if(s[i] == cur)
        {
            count[i%2]++;
        }
        else
        {
            if(s[i] == 'L')
            {
                lastPair = i-1;
                ans[lastPair] += count[lastPair%2];
                ans[lastPair+1] += count[(lastPair+1)%2];
            }
            else
            {
                ans[lastPair] += count[lastPair%2];
                ans[lastPair+1] += count[(lastPair+1) %2];
            }
            count[0] = 0;
            count[1] = 0;
            count[i%2]++;
            cur = s[i];
        }
    }
    ans[lastPair] += count[lastPair%2];
    ans[lastPair+1] += count[(lastPair+1) %2];

    for(int i =0; i <N; ++i)
    {
        cout << ans[i] << " ";
    }
    cout << '\n';
    
    return 0;
}

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

using namespace std;

const int mod = 998244353;
int add(int a, int b) {
	return a + b < mod ? a + b : a + b - mod;
}
int mul(int a, int b) {
	return int(1LL * a * b % mod);
}
int fexp(int b, int e = mod - 2) {
	int ans = 1;
	while(e) {
		if(e & 1) ans = mul(ans, b);
		b = mul(b, b);
		e /= 2;
	}
	return ans;
}

const int N = 200005;

int fat[N], ifat[N];

int C(int n, int k) {
	if(k > n) return 0;
	return mul(mul(fat[n], ifat[k]), ifat[n - k]);
}

int n, m, k;
int dp[N];

int main() {
	fat[0] = 1;
	for(int i = 1; i < N; i++) fat[i] = mul(fat[i - 1], i);
	ifat[N - 1] = fexp(fat[N - 1]);
	for(int i = N - 2; i >= 0; i--) ifat[i] = mul(ifat[i + 1], i + 1);

	scanf("%d %d %d", &n, &m, &k);

	int ans = 0;

	for(int s = 0; s <= k; s++) {
		ans = add(ans, mul(C(n - 1, s), mul(m, fexp(m - 1, (n - 1) - s))));
	}

	printf("%d\n", ans);
}


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

#define min(a,b)	(a<b?a:b)

int main(){
	unsigned char S[100000];
	unsigned char odd,even;
	int diff[2];
	int size;
	int i,j;
	
	scanf("%s",&S);
	
	size=strlen(S);
	
	if(size==1){
		printf("0");
		return 0;
	}
	
	for(i=0;i<2;i++){
		diff[i]=0;
		
		for(j=0;j<size;j++){
			if(j%2==0){
				if(i==0){
					if(S[j]!=S[0])	diff[i]++;
				}else{
					if(S[j]==S[1])	diff[i]++;
				}
			}else{
				if(i==0){
					if(S[j]==S[0])	diff[i]++;
				}else{
					if(S[j]!=S[1])	diff[i]++;
				}
			}
		}
	}
	
	printf("%d",min(diff[0],diff[1]));
	
	return 0;
}

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

int main(){
  int A,B;
  cin >> A >> B;
  if (A + B > A - B){
    if (A + B > A * B)cout << A + B << endl;
    else cout << A * B << endl;
  }
  else{
    if (A - B > A * B)cout << A - B << endl;
    else cout << A * B << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    double v[n], x=0;
    for(int i=0; i<n; i++){
        cin>>v[i];
    }
    sort(v, v+n);
    x=(v[0]+v[1])/2;
    for(int i=2; i<n; i++){
        x=(x+v[i])/2;
    }
    cout<<x<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using intl = long long;
using itnl = long long;
using itn = int;
using ld = long double;
using namespace std;
#define rep(i, n) for(intl i = 0; i < (intl)(n); i++)
#define rrep(i, n) for(intl i = (intl)(n) - 1; i >= 0; i--)
#define repi(i, a, b) for(intl i = (intl)(a); i < (intl)(b); i++)
#define rrepi(i, a, b) for(intl i = (intl)(a); i > (intl)(b); i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,1,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define alength(a) (sizeof(a) / sizeof(a[0]))
#define cin(i, a) rep(i, alength(a))cin >> a[i]
#define ccin(i, j, a) rep(i, alength(a))rep(j, alength(a[i]))cin >> a[i][j]
#define debug(x) cout << #x << ":" << x << endl
#define rdebug(i,x) rep(i, alength(x))cout << #x << "[" << i << "]:" << x[i] << endl
#define rrdebug(i, j, x) rep(i, alength(x))rep(j, alength(x[i]))cout << #x << "[" << i << "][" << j << "]:" << x[i][j] << endl
#define sqrt sqrtl
#define itn int
#define double ld
#define pb push_back
#define mp make_pair
#define pii pair<intl,intl>
const intl INF = 1e9;
const intl MOD = 1e9+7;
const ld EPS = 1.0e-14;//-9
const ld PI = acos(-1);
void fp(bool f){cout << (f ? "Yes" : "No") << endl;}
void fp(bool f, string s, string t){cout << (f ? s : t) << endl;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) {a = b; return true;} return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) {a = b; return true;} return false; }
intl kai(intl k){
    intl a = 1;
    for(int i = 2; i <= k; i++){
        a *= i;
    }
    return a;
}
intl gcd(intl a, intl b){ if(!b)return a; return gcd(b, a % b); }
intl lcm(intl a,intl b){ return a / gcd(a, b) * b; }
intl digit10(intl a){
    intl b = 0;
    do{
        a /= 10;
        b++;
    }while(a);
    return b;
}
//-------------------------------------------------------------------------------

intl n,m,x;
intl c[12];
intl a[12][12];

void input_var(){
    cin >> n >> m >> x;
    rep(i,n){
        cin >> c[i];
        rep(j,m){
            cin >> a[i][j];
        }
    }
}
//-------------------------------------------------------------------------------

signed main(){
    cout << fixed << setprecision(10);
    input_var();
    intl mi = INF;
    bool flag = false;
    for(intl i = 0; i < (0b1 << n); i++){
        bool f = true;
        intl b[m];
        m0(b);
        intl d = 0;
        rep(j,n){
            if(i & (1 << j)){
                rep(k,m){
                    b[k] += a[j][k];
                }
                d += c[j];
            }
        }
        rep(j,m)if(b[j] < x)f = false;
        if(f){
            flag  = true;
            mi = min(mi,d);
        }
    }
    if(!flag)mi = -1;
    cout << mi << endl;
    return 0;
}

Measured memory_bytes: 3624
# -*- coding:utf-8 -*-

first = 0
second = 0
third = 0
i = 0

for i in range(0,10):
    line = int(input())
    
    if first < int(line):
        third = second
        second = first
        first = int(line)
    elif second < int(line):
        third = second
        second = int(line)
    elif third < int(line):
        third = int(line)
print(first)
print(second)
print(third)

Measured memory_bytes: 7636
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
char s[111];
int main()
{
	int l;
	bool c=false;
	scanf("%s",s);
	l=strlen(s);
	for(int i=0;i<l;i++)
		if(s[i]=='C')
			c=true;
		else if(c&&s[i]=='F')
		{
			printf("Yes\n");
			return 0;
		}
	printf("No\n");
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <stack>
#include <string>
#include <vector>
 
using namespace std;
typedef long long ll;
using gra = vector<vector<ll>>;
using gram = vector<unordered_map<ll,ll>>;
 
typedef unsigned long long ull;
 
template <class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template <class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
 
template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template <class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template <class T> T dup(T a, T b) { return (a + b - 1) / b; }
template <class T> T modpow(T x, T p, T m) { T a=1; while(p){ if(p%2)a =a*x%m; x = x+x%m; p/=2; } return a; }
// template <class T> void prim(T a) { for(ll i=0;i<a.size();++i) { cout << a[i]; } cout << "\n"; }
 
#define mod 1000000007LL
#define INF 10000000000000000LL
 
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rep1(i, n) for (int i = 1; i <= n; ++i)
#define rrep(i, n) for (int i = (n - 1); i >= 0; --i)
#define rrep1(i, n) for (int i = n; i > 0; --i)
 
#define pri(x) cout << (x) << "\n"
#define pri2(x, y) cout << (x) << " " << (y) << "\n"
#define pri3(x, y, z) cout << (x) << " " << (y) << " " << (z) << "\n"
//#define modpow(x, p, m) { ll a=1; while(p){ if(p%2)a =a*x%m; x = x+x%m; p/=2; } return a; }
 
#define m0(h) memset(h, 0, sizeof(h))
#define m1(h) memset(h, 1, sizeof(h))
#define m(h, n) memset(h, (n), sizeof(h))
#define all(n) (n).begin(),(n).end()
#define bit(n) (1LL << (n))
#define pb push_back
 
//#ifdef LOCAL
//
//#define dpri(...) fprintf(stderr, __VA_ARGS__)
//#define pria(g) rep(i,g.size()){ cout << i << "{"; rep(j,g[i].size()) cout << g[i][j] << " "; cout << "}" << "\n"; }
//#else
//#define dpri(...) 42
//#define pria(g) 42
//#endif
 
 
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  // ---------------------
  // コーディング開始
  // ---------------------
  ll h,w,k;
  cin >> h >> w >> k;
  string s;
  ll gn = 1;
  string line = "";
  string lasttadasiiline = "";
  bool flag =false;
  ll fst = 1;


  rep(i,h){
    cin >> s;
    flag=false;
    rep(j,w){
      // # はイチゴである 
      // 一つでもあったか
      if(s[j]=='#'){
        //イチゴがのってるよ！
        if(flag){
          gn++;
        }else{
          // みつかったよ！
          flag=true;
        }
      }else{
      }
      line = line + ' ' + to_string(gn);
    }
    // 一列終わり
    if(flag){
      rep(i,fst){
        pri(line);
      }
      fst=1;
      lasttadasiiline = line;
      gn++;
    }else{
      //いちごなかった？
      //じゃあ最後のラインと同じにしておくね。
      if(lasttadasiiline!=""){
        pri(lasttadasiiline);
      }else{
        //一回もみつかってないならスタックさせる
        fst++;
      }
    }
    line = "";
  }


  return 0;
}


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

int main(){
	int h,w,n,c,sum,x[10000],y[10000];
	cin>>h>>w>>n;
	x[0]=1;
	y[0]=1;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	sum=0;
	for(int i=1;i<n;i++){
		c=0;
		if((x[i+1]>=x[i] && y[i+1]>=y[i]) || (x[i+1]<=x[i] && y[i+1]<=y[i])){
			c=max(abs(x[i+1]-x[i]),abs(y[i+1]-y[i]));
		}
		else{
			c=abs(x[i]-x[i+1])+abs(y[i]-y[i+1]);
		}
		sum += c;
	}
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 1176
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007, INF=mod*mod*3LL;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

struct RollingHash {
    static const int base1 = 1007, base2 = 2009;
    static const int mod1 = 1000000007, mod2 = 1000000009;
    vector<long long> hash1, hash2, power1, power2;
 
    // construct
    RollingHash(const string &S) {
        int n = (int)S.size();
        hash1.assign(n+1, 0);
        hash2.assign(n+1, 0);
        power1.assign(n+1, 1);
        power2.assign(n+1, 1);
        for (int i = 0; i < n; ++i) {
            hash1[i+1] = (hash1[i] * base1 + S[i]) % mod1;
            hash2[i+1] = (hash2[i] * base2 + S[i]) % mod2;
            power1[i+1] = (power1[i] * base1) % mod1;
            power2[i+1] = (power2[i] * base2) % mod2;
        }
    }
    
    // get hash of S[left:right)
    inline pair<long long, long long> get(int l, int r) const {
        long long res1 = hash1[r] - hash1[l] * power1[r-l] % mod1;
        if (res1 < 0) res1 += mod1;
        long long res2 = hash2[r] - hash2[l] * power2[r-l] % mod2;
        if (res2 < 0) res2 += mod2;
        return {res1, res2};
    }

    // get lcp of S[a:) and T[b:)
    inline int getLCP(int a, int b) const {
        int len = min((int)hash1.size()-a, (int)hash1.size()-b);
        int low = -1, high = len;
        while (high - low > 1) {
            int mid = (low + high) / 2;
            if (get(a, a+mid) != get(b, b+mid)) high = mid;
            else low = mid;
        }
        return low;
    }
};

struct UnionFind {
    vector<int> par;
    UnionFind(int n) :par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    bool connect(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    int size(int x) {
        return -par[root(x)];
    }
};

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    string s,t;
    cin >> s >> t;
    UnionFind uf(2000000);
    ll m = t.length();
    ll n = s.length();
    while(n<m)n*=2,s+=s;
    s+=s;
    RollingHash T(t);
    RollingHash S(s);
    for(int i=0;i<n;i++){
    	if(S.get(i,i+m)==T.get(0,m)){
    		if(uf.root(i%n) == uf.root((i+m)%n)){
    			cout << -1 << endl;
    			return 0;
    		}
    		uf.connect(i%n,(i+m)%n);
    	}
    }
    int ans = 0;
    for(int i=0;i<n;i++){
    	ans = max(ans,uf.size(i));
    }
    cout << ans-1 << endl;
    return 0;
}


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

using namespace std;

int main()
{
  int n;
  while(cin >> n, n) {
    vector<int> vote;
    for(int i = 0; i < n; i++) {
      char c; cin >> c;
      vote.push_back(c-'A');
    }
    vector<int> num(26, 0);
    for(int i = 0; i < n; i++) {
      num[vote[i]]++;
      int maxi = max_element(num.begin(), num.end()) - num.begin();
      int seci = -1;
      for(int j = 0; j < 26; j++) {
	if(j == maxi) continue;
	if(seci == -1 || num[seci] < num[j]) seci = j;
      }
      if(num[maxi] > num[seci] + n-i-1) {
	cout << (char)(maxi+'A') << " " << i+1 << endl;
	break;
      } else if(i == n-1) {
	cout << "TIE" << endl;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 3108
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cmath>
#include <climits>
#include <ctime>
#include <fstream>
#include <functional>
#define endl '\n'
#define ll long long
#define mod 1000000007
#define NCONS 1000000000
//#define NCONS 100001
//#define NCONS 1001
//#define NCONS 101
#define MCONS 2001
#define LIMIT 1000000000
#define TRUE 1
#define FALSE 0
#define toRadian(degree) ((degree) * (M_PI / 180.))
#define toDegree(radian) ((radian) * (180. / M_PI))
using namespace std;
struct Point{int x; int y;};
struct PPoint{Point x; Point y;};
inline ll gcd(ll a, ll b) { if(a < b) swap(a, b); if(b <= 0) return a; return gcd(b, a % b); }



ll get_times(ll i, ll K)
{
    ll ret = 0;
    
    ll cur = i;
    while(cur < K)
    {
        ret += 1;
        cur *= 2;
    }
    
    return ret;
}

int main(void)
{
 //   cin.tie(NULL); ios_base::sync_with_stdio(false);
    ll N, K; cin >> N >> K;
    ll total_times = 0;
    double ret = 0;
    
    for(ll i = 1; i <= N; i++)
    {
        ll times = get_times(i, K);
        
        ret += 1 / pow(2, times) / N;
    }

    printf("%.9lf", ret);
    return 0;
}


Measured memory_bytes: 256
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define inf 1000000000
#define MOD 1000000007
inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;}
inline ll readl(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
inline ll power(ll a,ll b){ll ans=1;while(b){if(b&1){ans=ans*a%MOD;--b;}b>>=1;a=a*a%MOD;}return ans%MOD;}
/*================Header Template==============*/
ll c,d;
int main(){
	int q=read();
	while(q--){
		int a=read(),b=read();
		if(a==1&&b==1){puts("0");continue;}
		if(a>b) a^=b^=a^=b;c=1ll*a*b-1;d=(ll)sqrt(c)+1e-13;
		if(d*d>c) d--;
		ll ans=2*d-1;
		if(a==b) ans++;
		if(d==c/d) ans--;
		if(c/d==a&&d!=a) ans--;
		writeln(ans);
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
 
#define int long long
 
using namespace std;
 
const int N = 1e5 + 10;
 
__gnu_pbds::priority_queue<int, greater<int>, __gnu_pbds::pairing_heap_tag> val[N];
int n, m, fa[N], ans, cnt, tot, vis[N];
pair<int, int> tmp[N];
 
int find(int x) {
	return fa[x] = x == fa[x] ? x : find(fa[x]);
}	
 
signed main() {
	//freopen("apc001d.in", "r", stdin);
	//freopen("apc001d.out", "w", stdout);
	int x, y, now;
	scanf("%lld%lld", &n, &m);
	for(int i = 1; i <= n; ++ i) 
		scanf("%lld", &x), val[fa[i] = i].push(x);
	for(int i = 1; i <= m; ++ i) {
		scanf("%lld%lld", &x, &y);
		++ x, ++ y;
		x = find(x), y = find(y);
		if(x != y) ++ cnt, fa[y] = x, val[x].join(val[y]);
	}
	if(cnt + n / 2 < n - 1) return puts("Impossible"), 0;
	for(int i = 1; i <= n; vis[find(i)] = 1, ++ i)
		if(!vis[find(i)]) 
			tmp[++ tot] = make_pair(val[find(i)].size(), find(i));
	sort(tmp + 1, tmp + tot + 1);
	now = find(tmp[tot].second);
	for(int i = tot - 1; i; -- i) {
		int u = now, v = tmp[i].second;
		if(u == v || val[v].empty()) continue;
		ans += val[u].top() + val[v].top();
		val[u].pop(), val[v].pop();
		val[u].join(val[v]), fa[v] = u;
		++ cnt;
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 9600
#include <iostream>
#include <iomanip>
#include <stdio.h>
using namespace std;

int main()
{
	int h[100], w[100];
	int n=0;
	
	while(1){
		cin >> h[n] >> w[n];
		if(h[n] == 0 && w[n] == 0)	break;
		n++;
	}
	
	for(int i=0; i<n; i++){
		for(int j=1; j<=h[i]; j++){
			if(j%2 != 0){
				for(int m=1; m<=w[i]; m++)
					if(m%2 == 0)
						cout << '.';
					else
						cout << '#';
			}
			else{
				for(int m=1; m<=w[i]; m++){
					if(m%2 == 0)
						cout << '#';
					else
						cout << '.';
				}
			}
			cout << endl;
		}
		if(i<= n)
			cout << endl;
	}
	
	return 0;
}



Measured memory_bytes: 3104
import numpy as np
def python_list_sub(in1, in2):
    wrk = np.array(in1) + np.array(in2)
    return wrk.tolist()


n, k, q = map(int,input().split())
#A = []
Po = []
De = [1 for i in range(n)]

A = [int(input()) for i in range(q)]
#print(A)

# はじめからポイント減らしておく
for i in range(n):
    Po.append(int(k-q))
#print(Po)
# 入力はOK

#計算
for j in A:
    #print(j,A[j])
    Po[j-1] += 1
#print(Po)

for i in range(n):
    if Po[i] >0:
        print('Yes')
    else: print('No')

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

#define ll long long
#define pb push_back

const int maxn = 2e5 + 20;

vector<int> adj[maxn];

bool visited[maxn];

void dfs(int v)
{
	visited[v] = 1;
	for(auto u : adj[v])
		if(!visited[u])
			dfs(u);
}

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

	int n ;
	cin >> n ;

	for(int i = 1; i < n; i++)
	{
		int a ;
		cin >> a;
		a-- ;

		adj[a].pb(i);
	}
	for (int i = 0; i < n; i++)
	{
		cout << adj[i].size() << endl;
	}
	return 0;
	
}

Measured memory_bytes: 14532
#include <stdio.h>
int main(void){
    int s;
    scanf("%d",&s);
    
    int check[1000000],a=s,counter=2;
    
    for(int i=0;i<1000000;i++){
        check[i] = 0;
    }
    
    check[s-1] = 1;
    
    while(1){
        if(a % 2 == 0){
            a = a/2;
        } else {
            a = 3*a + 1;
        }
        if(check[a-1] == 0) check[a-1] = 1;
        else {
            printf("%d",counter);
            return 0;
        }
        counter++;
    }
    
    return 0;
    
}


Measured memory_bytes: 4096
def main():
    N = int(input())
    H = [int(i) for i in input().split()]
    pre = H[-1]
    for i, h in enumerate(H[::-1], start=1):
        if i == 1:
            continue
        if h - pre > 1:
            return print("No")
        elif h - pre == 1:
            pre = h - 1
        else:
            pre = h
    print("Yes")


if __name__ == '__main__':
    main()


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

int main(){
    int a,b,c,d;

    cin >> a >> b >> c >> d;

    if((a + b) > (c + d)){
        cout << "Left" << endl;
    }
    else if((a + b) < (c + d)){
        cout << "Right" << endl;
    }
    else{
        cout << "Balanced" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define vii vector<int>
#define task "ABC"
#define pll pair<ll, ll>
#define pii pair< ll, pair< ll, ll > >
#define fi first
#define se second

using ll = long long;
using ld = long double;
using ull = unsigned long long;
const ll mod = 1e9 + 7;
using namespace std;
const int N = 1e6+5;
ll tong, m, n, k, t, T, ntest, ans, u, v, b[N], lab[N];
string s;
ll a[N], d[N], c[N];
vector<pii> kq;
vector<pll> adj[N], adt[N];
bool check;
ll findp(ll u)
{
    return lab[u] < 0 ? u : lab[u] = findp(lab[u]);
}
void hop(ll u, ll v)
{
    if(lab[u] > lab[v])swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
    ans = max(ans, -lab[u]);
}
inline void sol()
{
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> b[i];
    }
    check = true;
    for(int i = 1; i <= n; i ++)
    {
        t = b[i];
        if(t == 1)continue;
        if(a[t])
        {
            check = false;
            break;
        }
        ++a[t];
        for(int j = 2; j  * j <= t; j ++)
        {
            if(t % j == 0)
            {
                if(a[j])
                {
                    check = false;
                    break;
                }
                ++a[j];
                if(j * j != t)
                {
                    if(a[t/j])
                    {
                        check = false;
                        break;
                    }
                    ++a[t/j];
                }
            }
        }
        if(!check)break;
    }

    if(check)
    {
           cout << "pairwise coprime" ;
           return;
    }
    ans = b[1];
    for(int i = 2; i <= n; i ++)
    {
        ans = __gcd(ans, b[i]);
        if(ans == 1)
        {
            cout << "setwise coprime";
            return;
        }
    }
        if(ans == 1)
        {
            cout << "setwise coprime";
            return;
        }
    cout << "not coprime";
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    sol();

}





Measured memory_bytes: 58884
import math

x =input()
X = int(x)

if X == 1:
    output = 1
    print(output)
else:
    mylist = []
    for i in range(2,X+1):
        bekijo = i
        count = 0
        while bekijo <= X:
            bekijo = bekijo * i
            count = count +1
        if count > 1:
            mylist.append(int(bekijo/i))
    print(max(mylist))

Measured memory_bytes: 3060