akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

string s;
int p = 0;

bool is_digit(char c){
    return '0' <= c && c <= '9';
}

int dfs(){
    vector<int> v;
    while( p < s.size() ){
        if( is_digit(s[p]) ){
            int res = 0;
            while( is_digit(s[p]) ){
                res *= 10;
                res += s[p] - '0';
                p++;
            }
            p++;
            return (res+1)/2;
        }else if( s[p] == '[' ){
            p++;
            v.push_back( dfs() );
        }else if( s[p] == ']' ){
            p++;
            int n = v.size();
            vector<int> a = v;
            sort(v.begin(), v.end());
            int res = 0;
            for(int i = 0; i <= n/2; i++){
                res += v[i];
            }
            return res;
        }
    }
    return 0;
}

int main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> s;
        p = 1;
        cout << dfs() << endl;
    }
}

Measured memory_bytes: 1288
#include <bits/stdc++.h>
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define reprrev(i,a,b) for(int i=b-1;i>=a;i--) // [a, b)
#define reprev(i,n) reprrev(i,0,n)
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    cin.tie(0);
    ios::sync_with_stdio(false);<- これら、printfとかと併用しない方が良さそう

*/

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n==0) return 1;
    ll res=modpow(x, n/2);

    if(n%2==0) return res*res%mod;
    else return res*res%mod*x%mod;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };

ll gcd(ll a, ll b) {
    if (a<b) swap(a, b);
    while(b!=0) {
        ll t = a;
        a = b;
        b = t%b;
    }
    return a;
}

ll lcm(ll a, ll b) { return a/gcd(a, b)*b; }

// 線分 ab の偏角 返り値は[-π, π]
double argument(const pair<double, double> &a, const pair<double, double> &b){
    double ax=a.first, ay=a.second, bx=b.first, by=b.second;
    return atan2(by-ay, bx-ax);
}

/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */
/* <-----------------------------------------------------------------------------------> */


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

    int a, b, c; cin >> a >> b >> c;
    swap(a, b); swap(a, c);
    cout << a << " " << b << " " << c << endl;
    
    return 0;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define RREP(i, n) for (int i = n - 1; 0 <= i; i--)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define RFOR(i, start, end) for (int i = start - 1; 0 <= i; i--)
#define ALL(a) a.begin(), a.end()
using ll = long long;
using namespace std;
constexpr int INF32       = 1'050'000'000;
constexpr long long INF64 = 4'000'000'000'000'000'000;
constexpr int MOD7        = 1'000'000'007;
constexpr int MOD9        = 1'000'000'009;
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;
}
void print() { std::cout << '\n'; }
template <class H, class... T> void print(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << ' ';
    print(std::forward<T>(args)...);
}
template <class T> void print(std::vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i];
        i == v.size() - 1 ? std::cout << '\n' : std::cout << ' ';
    }
}
template <class T> void print(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            j == v[i].size() - 1 ? std::cout << '\n' : std::cout << ' ';
        }
    }
}
void debug() { std::cerr << '\n'; }
template <class H, class... T> void debug(H &&head, T &&... args) {
    std::cerr << head;
    sizeof...(args) == 0 ? std::cerr << "" : std::cerr << ' ';
    debug(std::forward<T>(args)...);
}
template <class T> void debug(std::vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        std::cerr << v[i];
        i == v.size() - 1 ? std::cerr << '\n' : std::cerr << ' ';
    }
}
template <class T> void debug(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cerr << v[i][j];
            j == v[i].size() - 1 ? std::cerr << '\n' : std::cerr << ' ';
        }
    }
}

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

    int K, T;
    cin >> K >> T;
    vector<int> v(T);
    for (auto &&i : v) {
        cin >> i;
    }
    RSORT(v);
    int mx  = v[0];
    int ot  = K - mx;
    int ans = max(0, mx - ot - 1);
    print(ans);

    return 0;
}

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

#define ff                  first
#define sf                  scanf
#define pf                  printf
#define ss                  second
#define ppb                 pop_back
#define pb                  push_back
#define MP                  make_pair
#define MAXN                10000
#define MOD                 100000007
#define inf                 0x3f3f3f3f
#define PI                  (2.0*acos(0.0))
#define INF                 0x3f3f3f3f3f3f3f3f
#define rev(v)              reverse(all(v))
#define all(v)              v.begin(), v.end()
#define __lcm(x, y)         (x * y) / __gcd(x, y)
#define FOR(i, x, y)        for(int i = x; i < y; i++)
#define RFOR(i, x, y)       for(int i = x; i >= y; i--)
#define MEM(arr, val)       memset(arr, val, sizeof(arr));
#define unq(v)              (v).resize(unique(all(v)) - v.begin())
#define READ()              freopen("input.txt", "r", stdin)
#define WRITE()             freopen("output.txt", "w", stdout)
#define si(n)               scanf("%d", &n)
#define sl(n)               scanf("%lld", &n)
#define sii(a, b)           scanf("%d %d", &a, &b)
#define sll(a, b)           scanf("%lld %lld", &a, &b)
#define siii(a, b, c)       scanf("%d %d %d", &a, &b, &c)
#define slll(a, b, c)       scanf("%lld %lld %lld", &a, &b, &c)
#define siiii(a, b, c, d)   scanf("%d %d %d %d", &a, &b, &c, &d)
#define sllll(a, b, c, d)   scanf("%lld %lld %lld %lld", &a, &b, &c, &d)
#define vout(v)             for(int i = 0; i < v.size(); i++) {cout << v[i]; if(i < v.size() - 1) cout << ' '; else cout << endl;}

vll v(100);
ll n, a, tot, res = 0;
ll dp[99][99][3000];

ll call(ll pos, ll cnt, ll sum){
    if(pos == n){
        if((double)sum / cnt == a) return 1;
        return 0;
    }
    if(dp[pos][cnt][sum] != -1) return dp[pos][cnt][sum];
    
    ll val1 = 0, val2 = 0;
    val1 = call(pos + 1, cnt + 1, sum + v[pos]);
    val2 = call(pos + 1, cnt, sum);
    return dp[pos][cnt][sum] = val1 + val2;
}

int main(){
    #ifndef ONLINE_JUDGE
        double start = clock(); READ(); WRITE();
    #endif
        cin >> n >> a;
        v.resize(n);

        FOR(i, 0, n) cin >> v[i];
        MEM(dp, -1);
        cout << call(0, 0, 0) << endl;


    return 0;
}

Measured memory_bytes: 233304
#include <bits/stdc++.h>
using namespace std;
//for(int i = 0; i < n; i++){}

int main()
{
    int n;
    cin >> n;
    int w[105];
    int sum = 0;
    for(int i = 0; i < n; i++) {
        cin >> w[i];
        sum += w[i];
    }
    int mini = 200000;
    for(int i = 0; i < n; i++){
        sum -= w[i] * 2;
        mini = min(mini, abs(sum));
        
        
    }
    cout << mini << endl;
    return 0;
}

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

using namespace std;

#define pb push_back
#define mp make_pair
#define lli long long int
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define mii map<lli,lli>
#define msi map<string,lli>
#define pii pair<lli,lli> 
#define vi vector<lli> 
#define vvi vector< vector<lli> >
#define sz(x) (lli)x.size()
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define MAX1 998244353
#define MAX2 1000000007
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    std::cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#define input(data,n,command) for(lli i=0;i<n;i++){lli tmp;cin>>tmp;data.pb(tmp);command}
#define sort_asc(a) sort(a.begin(),a.end());
//#define sort_desc(a) sort(a.begin(),a.end(),greater<lli>());
#define display(a) for(lli i = 0 ;i<a.size();i++){cout<<a[i]<<" ";} cout<<endl;
#define rep(i,a,b) for(lli i = a;i < b;i++)
#define endl "\n"

//Written By MUDIT BHARDWAJ...
/*--------------------------------------------------------------------*/
//vector<pair<lli,lli>>adj[300010];

lli solve()
{
    //start from here
    lli n;
    cin>>n;
    std::vector<lli> v;
    rep(i,0,n)
    {
    	lli a;
    	cin>>a;
    	v.pb(a);
    }
    sort(all(v),greater<lli>());
    lli ans = v[0];
    lli ind = 1;
    lli times = 0;
    rep(i,2,n)
    {
    	ans += v[ind];
    	times++;
    	if(times == 2)
    	{
    		times = 0;
    		ind++;
    	}
    }
    cout<<ans;
    return 0;
}

int main()
{
    ios
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    lli T=1;
    //cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}
/*-----------------------------------------------------------------------*/

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

int N;
set<int> ratings;
int M = 0;

int main() {
//	freopen("data.txt", "r", stdin);
	cin >> N;
	for (int i = 0; i < N; ++i) {
		int temp = 0; cin >> temp;
		if (temp >= 3200) {
			++M;
		} else {
			int r = temp / 400;
			ratings.insert(r);
		}
	}
	cout << max((int)ratings.size(), 1) << " " << (ratings.size() + M) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define repone(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define Rep(j,n) for(int j=0;j<(int)(n);++j)
#define Repo(j,o,n) for(int j=o;j<(int)(n);++j)
#define Repone(j,n) for(int j=1;j<(int)(n);++j)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define int long long
#define pb(a) push_back(a)
#define eraser(v,i) (v).erase(v.begin()+(i))
#define pbpair(a,b) push_back(make_pair(a,b))
#define MOD 1000000007
const long long INF = 1LL<<60;
#define pairint pair<int,int>
signed main(){
int x=0,y=0,z=0,w=0,n=0,m=0;
string s;
std::cin >> s;
if(s=="AAA"||s=="BBB")std::cout << "No" << '\n';
else std::cout << "Yes" << '\n';
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<queue>
#include<utility>
using namespace std;
int main(){
        queue<pair<string,int>> a;
        int n,q,t,time=0;
        string s;
        cin>>n>>q;
        for(int i=0;i<n;i++) {
                cin >>s>>t;
                a.push(make_pair(s,t));
        }
        while(a.size()>0){
                pair<string, int>tmp = a.front(); a.pop();
                if(tmp.second>q){
                        tmp.second -= q;
                        a.push(tmp);
                        time += q;
                }else{
                        time += tmp.second;
                        cout<<tmp.first<<" "<<time<<endl;
                }
        }
        return 0;
}


Measured memory_bytes: 6232
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define mp make_pair
#define ff first
#define ss second
#define setbits(x) __builtin_popcount(x)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<db, db> pdd;
typedef vector<int> vi;
#define m1 make_pair
#define in insert
#define pb push_back
#define IOS                           \
    std::ios::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define endl "\n"
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

inline ll gcd(ll a, ll b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
inline ll power(ll a, ll n, ll m)
{
    if (n == 0)
        return 1;
    ll p = power(a, n / 2, m);
    p = (p * p) % m;
    if (n % 2)
        return (p * a) % m;
    else
        return p;
}
const ll MOD = 1000000007;
const int N = int(3e5) + 999;
#define int long long int

vector<string> a;
int n,m;
int dp1[21][21],dp2[21][21];
int dist[4][2] = {{1,0},{-1,0},{0,-1},{0,1}};

bool ch(int x,int y){
	if(x>=n or y>=m or x<0 or y<0 )
		return false;
	if(a[x][y]=='#')
		return false;
	if(dp2[x][y]==1)
		return false;
	return true;
}


int bfs2(int x,int y){

	pair<pair<int,int>,int> mx = {{x,y},0};
	queue<pair<pair<int,int>,int>> q;
	q.push({{x,y},0});
	dp2[x][y]=1;
	while(!q.empty()){	
		auto it = q.front();
		q.pop();
		int nx = it.ff.ff,ny = it.ff.ss,dpar = it.ss;
		
		for(int p=0;p<4;p++){
			int i = dist[p][0],j=dist[p][1];
			if(ch(nx+i,ny+j)){
				dp2[nx+i][ny+j]=1;
				if(mx.ss<dpar+1){
					mx = {{nx+i,ny+j},dpar+1};
				}
				q.push({{nx+i,ny+j},dpar+1});
			}
		}

	}

	return mx.ss;
}

int32_t main(){
    IOS;
    
    cin>>n>>m;
    a.resize(n);
    
    memset(dp2,-1,sizeof dp2);

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

    for(int i =0;i<n;i++){
    	for(int j=0;j<m;j++){
    		if(a[i][j]!='#'){
    			memset(dp2,-1,sizeof dp2);
    			ans = max(ans,bfs2(i,j));
    			
    		}
    	}
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007

using namespace std;

int main(void){
  ll n;
  cin >> n;

  ll m = 1e13;
  for (ll i = 1; i <= sqrt(n); i++){
    if (n % i == 0)
      m = min(m, i + n / i - 2);
  } 


  cout << m << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <tuple>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <numeric>
#include <string.h>
using namespace std;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const long long INFL = 1e18;
const int MOD = 1000000007;
const int MAX = 210000;

int gcd(int a, int b) {
    return b != 0 ? gcd(b, a % b) : a;
}

//逆元を求める関数
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
      fac[i] = fac[i-1] * i % MOD;
      inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
      finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
//組み合わせ
long long COM (int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

void solve() {
	int n; cin >> n;
	vector<int> c(n - 1), s(n - 1), f(n - 1);
	for (int i = 0; i < (n - 1); ++i) {
		cin >> c[i] >> s[i] >> f[i];
	}
	for (int i = 0; i < n - 1; ++i) {
		int require_t = s[i] + c[i];
		for (int j = i + 1; j < (n - 1); ++j) {
			if (require_t < s[j]) {
				require_t += (s[j] - require_t);
			} else {
				if (require_t % f[j] != 0) {
					require_t += (f[j] - (require_t % f[j]));
				}
			}
			require_t += c[j];
		}
		cout << require_t << endl;
	}
	cout << 0 << endl;
    return;
}

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



Measured memory_bytes: 256
X,N = map(int,input().split())
p= list(map(int,input().split()))

cnt = 0
aflg = False
bflg = False
flg=False

while True:
    
    x = X+cnt
    x_min = X-cnt
    
    if x not in p:
        flg=True
        aflg = True
    
    if x_min not in p:
        flg=True
        bflg=True
        
        
    if flg==True:
        
        if aflg == True and bflg == True:
            print(x_min)
        elif aflg == True:
            print(x)
        elif bflg == True:
            print(x_min)
            
        break
    else:
        cnt+=1

Measured memory_bytes: 9212
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    n, m = map(int, input().split())
    tree = [[] for _ in range(n)]
    for _ in range(m):
        i, j, k = map(int, input().split())
        i -= 1
        j -= 1
        tree[i].append((k, j))
        tree[j].append((k, i))

    # dijkstra
    import heapq
    from numpy import zeros

    ans = 0
    for i in range(n):
        for j in tree[i]:
            seen = zeros(n)
            goal = j[1]
            base = j[0]
            seen[i] = 1
            todo = []
            heapq.heapify(todo)
            for k in tree[i]:
                if k[0] < base and k != j:
                    heapq.heappush(todo, k)
            while len(todo) > 0:
                k = heapq.heappop(todo)
                if k[1] == goal:
                    if k[0] < base:
                        ans += 1
                    break
                seen[k[1]] = 1
                for l in tree[k[1]]:
                    if seen[l[1]] == 0 and k[0] + l[0] < base:
                        heapq.heappush(todo, (k[0] + l[0], l[1]))

    print(ans // 2)

main()

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

int main()
{
    int N;
    int Alice = 0;
    int Bob = 0;
    vector<int> data;

    cin >> N;

    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        data.push_back(a);
    }

    sort(data.begin(), data.end(), greater<int>());

    for (int i = 0; i < N; i++) {
        if(i % 2 == 0) {
            Alice += data[i];
        } else {
            Bob += data[i];
        }
    }

    cout << Alice - Bob << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
#include<numeric>
#define rep(i,n) for(int i=0;i<(n);i++)
#define ll long long
using namespace std;
int main() {
	int a,b,ans=0;
	cin >> a>>b;
	if (a == 1 && b == 1)ans = 1000000;
	else {
		if (a == 1)ans += 300000;
		if (a == 2)ans += 200000;
		if (a == 3)ans += 100000;
		if (b == 1)ans += 300000;
		if (b == 2)ans += 200000;
		if (b == 3)ans += 100000;
	}
	cout << ans << endl;
		return 0;
}

Measured memory_bytes: 256
def main():
    from itertools import cycle
    from operator import add, sub

    N = int(input())
    *A, = map(int, input().split())

    cycl_oper = cycle((add, sub))

    M0 = 0  # 山0(0-ind)への降雨量
    for op, x in zip(cycl_oper, A):
        M0 = op(M0, x)

    ans = [0] * N
    ans[0] = M0
    for i in range(1, N):
        ans[i] = A[i - 1] * 2 - ans[i - 1]

    print(*ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 14864
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<functional>
#include<map>
#include<unordered_set>
using namespace std;
//int p = 998244353;
long long p = 1000000007;
#define int long long
#define vel vector<long long>
#define vvel vector<vel>
#define rep(i,n) for(int i=0;i<n;i++)
#define sor(v) sort(v.begin(),v.end())
#define mmax(a,b) a=max(a,b)
#define mmin(a,b) a=min(a,b)
#define mkp make_pair
#define pin pair<int,int>
#define qin pair<int,pin>
#define V vector
#define Endl endl
#define veb vector<bool>
#define rev(s) reverse(s.begin(),s.end())
#define lower(h,val) lower_bound(h.begin(),h.end(),val)-h.begin()
#define upper(h,val) upper_bound(h.begin(),h.end(),val)-h.begin()
int max_kai = 150000;
vel kai(max_kai, 1);
vel inv_kai;
int rui(int a, int n) {
	if (n == 0) { return 1; }
	int x = rui(a, n / 2);
	x *= x; x %= p;
	if (n % 2 == 1) { x *= a; x %= p; }
	return x;
}
int inv(int a) { return rui(a, p - 2); }
void make_kai() {
	for (int i = 1; i < max_kai; i++) { kai[i] = kai[i - 1] * i; kai[i] %= p; }
	inv_kai = kai;
	rep(i, max_kai) { inv_kai[i] = inv(kai[i]); }
}
int nCr(int n, int r) {
	int a = kai[n] * inv_kai[r]; a %= p;
	a *= inv_kai[n - r]; a %= p;
	return a;
}
vel pa;
int root(int x) {
	if (pa[x] == -1) { return x; }
	int ans = root(pa[x]); pa[x] = ans;
	return ans;
}
void marge(int x, int y) {
	x = root(x);
	y = root(y);
	if (x != y) {pa[x] = y;}
}


#define T vel
T mul(T &a,T &b) {//calcureate a(b(x))
	int sz = a.size();
	vel c(sz);
	rep(i, sz) { c[i] = a[b[i]]; }
	return c;
}
T rui1(T &a, int n) {
	if (n == 1) { return a; }
	T x = rui1(a, n / 2);
	x = mul(x, x);
	if (n % 2 == 1) { x = mul(x, a); }
	return x;
}
int solve(string s) {
	int n = s.size();
	vel list(1,0);
	for (int i = 1; i < n; i++) {
		if (s[i] != s[i - 1]) { list.push_back(i); }
	}
	list.push_back(n);
	int sz = list.size();
	int ans = 0;
	rep(i, sz-1) {
		ans += (list[i + 1] - list[i]) / 2;
	}
	return ans;
}
signed main(){
	string s; cin >> s;
	int n=s.size();
	bool fl = true;
	rep(i, n) {
		if (s[i] != s[0]) { fl = false; }
	}
	if (fl) { int k; cin >> k; cout << (n*k) / 2 << endl; return 0; }
	int k; cin >> k;
	int a = solve(s);
	int diff = solve(s + s) - a;
	cout << a + diff * (k - 1) << endl;
	return 0;
}

Measured memory_bytes: 1408
#!/usr/bin/env python3
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n = int(readline())
p = list(map(int,input().split()))
ans = 1 # initialization of p[0]
min_i = p[0]
for i in range(1,n):
    if p[i] <= min_i:
        ans += 1
        min_i = p[i]
    else: pass
print(ans)

Measured memory_bytes: 25900
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define showmap(is, js, x) {rep(i, is){rep(j, js){cout << x[i][j] << " ";}cout << endl;}}
#define show(x) {for(auto i: x){cout << i << " ";} cout<<endl;}
#define showm(m) {for(auto i: m){cout << m.x << " ";} cout<<endl;}
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> llP;
ll gcd(int x, int y){ return y?gcd(y, x%y):x;}
ll lcm(ll x, ll y){ return (x*y)/gcd(x,y);}


long mod = 1000000007;
/* C++の構造体 メンバがpublicなclass */
typedef struct mint
{
    ll x;
    mint(ll x = 0) : x(x % mod) {} //コンストラクタ
    /* 演算子オーバーロード */
    mint &operator+=(const mint a)
    {
        if ((x += a.x) >= mod)
            x -= mod;
        return *this;
    }
    mint &operator-=(const mint a)
    {
        if ((x += mod - a.x) >= mod)
            x -= mod;
        return *this;
    }
    mint &operator*=(const mint a)
    {
        (x *= a.x) %= mod;
        return *this;
    }
    mint operator+(const mint a) const
    {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint a) const
    {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint a) const
    {
        mint res(*this);
        return res *= a;
    }
    mint pow(ll t) const
    {
        if (!t)
            return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1)
            a *= *this;
        return a;
    }
    // for prime mod
    mint inv() const
    {
        return pow(mod - 2);
    }
    mint &operator/=(const mint a)
    {
        return (*this) *= a.inv();
    }
    mint operator/(const mint a) const
    {
        mint res(*this);
        return res /= a;
    }
} mint_t;

ll intpow(mint_t m, int n)
{
    if (n == 0) return 1;
    mint_t ans(1);
    while (n >= 1)
    {
        if ((n % 2) == 0){
            m *= m.x;
            n /= 2;
        }else {
            ans *= m.x;
            n -= 1;
        }
    }
    return ans.x;
}

struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

int main()
{
    int k;
    string s;
    cin >> k >> s;
    int l = s.length();
    int L = k + l;
    combination  cb(L);

    mint ans(0);
    // rep(i, k+1){
    //     mint m26(26); 
    //     mint m25(25);
    //     mint tans(0);
    //     tans = m25.pow(k-i) * m26.pow(i) * cb(l-1+k-i, l-1);
    //     ans += tans;
    // }

    for (int i = l; i <= L; i++)
    {
        mint m25(25);
        ans += cb(L, i) * m25.pow(L-i);
    }

    cout << ans.x << endl;
}



Measured memory_bytes: 35664
#include <iostream>
#include <array>

int main(){
  std::array<int, 4> a = {};
  std::array<int, 4> b = {};
  int hit = 0;
  int blow = 0;
  int N = 0;

  while(N <= 50 && std::cin >> a[0] >> a[1] >> a[2] >> a[3] && std::cin >> b[0] >> b[1] >> b[2] >> b[3]){
    for(int i = 0;i < 4;++i){
      for(int j = 0;j < 4;++j){
          if(a[i] == b[j] && i == j)
              ++hit;
          if(a[i] == b[j] && i != j)
              ++blow;
            }
        }
    std::cout << hit << " " << blow << std::endl;

    hit = 0;
    blow = 0;
    ++N;
  }
}



Measured memory_bytes: 3052
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//余りを切り上げる =>  (a + b - 1) / b 

signed main(){
	string s; cin>>s;
	int n=s.size();
	if(s[0]!='A'){
		cout<<"WA"<<endl;
		return 0;
	}
	int cnt=0;
	rep(i,2,n-1){
		if(s[i]=='C')cnt++;
	}
	
	if(cnt!=1){
		cout<<"WA"<<endl;
		return 0;
	}
	set<char> k;
	rep(i,0,26) k.insert('A'+i);
	rep(i,0,n){
		if(i==0)continue;
		if(k.count(s[i]) && s[i]!='C'){
			cout<<"WA"<<endl;
			return 0;
		}
	}
	cout<<"AC"<<endl;
		
	
	return 0;
}

Measured memory_bytes: 3588
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#ifndef print
#define print(...)
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl = 0x3f3f3f3f3f3f3f3fLL;
const int infi = 0x3f3f3f3f;
//const int mod=998244353;
const int mod = 1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk = clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) { uniform_int_distribution<int> uid(0, lim - 1); return uid(rang); }
int powm(int a, int b) { int res = 1; while (b) { if (b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1; } return res; }

std::vector<int> find(int a, int b, int n) {
	if (__builtin_popcountll(a) % 2 == __builtin_popcount(b) % 2) return {-1};
	if (n == 1) {
		if (a == 1) return {1, 0}; 
		else return {0, 1};
	}
	// print(a, b);
	int in = 0;
	for (int i = 0; i < n; ++i) {
		if ((a ^ b) & (1 << i)) {
			in = i;
			break;
		}
	}
	int aprime = (a & ((1 << in) - 1)) | ((a & (~((1 << (in + 1)) - 1))) >> 1);
	int bprime = (b & ((1 << in) - 1)) | ((b & (~((1 << (in + 1)) - 1))) >> 1);
	int ai = a & (1 << in);
	int bi = b & (1 << in);
	int c = aprime ^ 1;
	auto v1 = find(aprime, c, n - 1);
	auto v2 = find(c, bprime, n - 1);
	// print(aprime, c, v1);
	// print(c, bprime, v2);
	std::vector<int> v;
	for (int i = 0; i < (1 << (n - 1)); ++i) {
		int x = v1[i];
		v.pb((x & ((1 << in) - 1)) | ai | ((x & (~((1 << in) - 1))) << 1));
	}
	for (int i = 0; i < (1 << (n - 1)); ++i) {
		int x = v2[i];
		v.pb((x & ((1 << in) - 1)) | bi | ((x & (~((1 << in) - 1))) << 1));
	}
	// print(v);
	return v;
}

int32_t main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.precision(10); srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	int n; cin >> n;
	int a; cin >> a;
	int b; cin >> b;
	auto re = find(a, b, n);
	if (re[0] == -1) {
		cout << "NO" << '\n';
	} else {
		cout << "YES" << '\n';
		for (int i = 0; i < (1 << n); ++i) 
			cout << re[i] << ' ';
		// for (int i = 0; i < ((1 << n) - 1); ++i) 
		// 	print(re[i] ^ re[i + 1]);
	}
}

Measured memory_bytes: 2392
#include <stdio.h>
int main()
{
    double a,b,c,d,e,f;
    double x,y;
    while(scanf("%lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f) != EOF){
        y = (c * d - a * f) / (b * d - a * e);
        x = (c - (b * y)) / a;
        printf("%.3lf %.3lf\n",x,y);
    }
    return 0;
}

Measured memory_bytes: 648
"use strict";

const main = arg => {
    const input = arg.trim().split(" ");

    let a = parseInt(input[0]);
    let b = parseInt(input[1]);
    let c = parseInt(input[2]);
    let k = parseInt(input[3]);

    let sum = 0

    if(a >= k){
      	sum = k
        console.log(sum)
    } else {
        k = k - a
        sum = a
        if(b >= k){
            console.log(sum)
        } else {
            k = k - b
            console.log(sum - k)
        }
    }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));  

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

char S[123456];
int K;

int main() {
	scanf("%s", &S);
	scanf("%d", &K);

	// fixed code
	int weight = strlen(S);
	for (int i = 0; i < weight; ++i){
		if (S[i] == 'a'){
			continue;
		}
		else if (K >= 'z' - S[i] + 1){
			K -= 'z' - S[i] + 1;
			S[i] = 'a';
		}
		
	}
	S[weight - 1] += K % 26;

	// Original code
	/*int weight = strlen(S);
	for (int i = 0; i < weight; ++i) {
		s[i] = S[i] - 96;
	}
	for (int i = 0; i < weight && K>0; ++i) {
		if (s[i] - 1 <= K) {
			K -= s[i] - 1;
			S[i] = 'a';
		}
		else {
			for (int j = i; j < weight; j++) {
				if (j == i) {.;p,gvhjk
					memo = j, tmp = s[j] - 1;
				}
				else if (tmp > j - i) {
					memo = j, tmp = s[j] - 1;
				}
			}
			S[i] = (char)((s[memo] + K + 1) % 26 + 96);
			K = 0;
		}
	}*/

	printf("%s\n", S);

	return 0;
}

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

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); ++i){    
        if ((i+1)%2){
            if (s[i] != 'R' && s[i] != 'U' && s[i] != 'D'){
                cout << "No";
                return 0;
            }
        }
    }
    for (int i = 0; i < s.length(); ++i){    
        if (!((i+1)%2)){
            if (s[i] != 'L' && s[i] != 'U' && s[i] != 'D'){
                cout << "No";
                return 0;
            }
        }
    }
    cout << "Yes";
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x1,y1,x2,y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int x3,y3,x4,y4;

    x3 = x2 - (y2 - y1);
    y3 = y2 + (x2 - x1);
    x4 = x3 - (x2 - x1);
    y4 = y3 - (y2 - y1);

    cout << x3 << ' ' << y3 << ' ' << x4 << ' ' << y4;
}

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

#define ull unsigned long long
#define MOD 998244353
using namespace std;


ull power(ull a, ull b)
{
	ull res = 1;
	while (b > 0)
	{
		if (b & 1)
			res = (res * a) % MOD;
		b = b / 2;
		a = (a * a) % MOD;
	}
	return res;
}

ull modi(ull a)
{
	return power(a, MOD - 2);
}

int main()
{
	ull N, S;
	cin >> N >> S;
	vector<ull> v(N + 1);
	for (int i = 1; i <= N; ++i)
		cin >> v[i];
	vector<vector<ull>> dp(N + 1, vector<ull>(S + 1, 0));
	dp[0][0] = power(2, N);
	ull inv2 = modi(2);
	for (ull i = 1; i <= N; ++i)
	{
		for (ull j = 0; j <= S; ++j)
		{
			dp[i][j] = dp[i - 1][j];

			if (j >= v[i])
			{
				dp[i][j] += (dp[i - 1][j - v[i]] * inv2) % MOD;
				dp[i][j] %= MOD;
			}
		}
	}
	cout << dp[N][S];
	return 0;
}

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

using namespace std;
 
int main() {
int r,g,b;
cin >> r >> g >> b;

int x = r * 100 + g * 10 + b;

if (x % 4 == 0)
{
    cout << "YES" << endl;
}
else
{
    cout << "NO" << endl;
}

}

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

int main(){
  string a,b;
  cin >> a >> b;
  int x,y;
  x = stoi(a);
  y= stoi(b);
  string s(y,a.at(0));
  string t(x,b.at(0));
  if(s <= t){
    cout << s << endl;
  }
  else{
    cout << t << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pint = pair<int,int>;
ll mod = 1000000007,mod2 = 998244353;

void chmin(long long &a, long long b) { if (a > b) a = b; }
void chmax(long long &a, long long b) { if (a < b) a = b; }
const long long INF = 1LL<<60;
ll gcd(ll a,ll b){
    if(b == 0) return a;
    else return gcd(b,a%b);
}

//重みある時
using Edge = pair<int,int>;
using Graph = vector<vector<Edge> >;

vector<ll> cntac,cntwa;

int main() {
    ll n,m;
    cin >> n >> m;
    vector<ll> p(100010);
    cntac.resize(100010);
    cntwa.resize(100010);
    vector<string> s(m);
    for (int i = 0; i < m; ++i) {
        cin >> p[i] >> s[i];
        if(s[i] == "AC") cntac[p[i]]++;
        else{
            if(cntac[p[i]] == 0){  // acしてなかったら、waをふやす
                cntwa[p[i]]++;
            }
        }
    }
    ll ans1 = 0,ans2 = 0;
    for (int i = 0; i <= n; ++i) {
        if(cntac[i] > 0) ans1++;
        if(cntac[i] > 0) ans2 += cntwa[i];
    }
    cout << ans1 << " " << ans2 << endl;
    return 0;
}

Measured memory_bytes: 8064
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;


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

	int n, m, i, j, k, corr = 0, penalty = 0, id, ans;
	string s;

	cin >> n >> m;

	vector<bool> solved(n + 1, false);
	vector<int> ct(n + 1, 0);

	while (m--) {
		cin >> id >> s;
		if (s == "AC") {
			if (solved[id]) continue;
			corr++;
			solved[id] = true;
			penalty += ct[id];
		}
		else {
			if (solved[id]) continue;
			ct[id]++;
		}
	}
	cout << corr << " " << penalty << "\n";


	return 0;
}


Measured memory_bytes: 888
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long n = sc.nextLong();
		long a = sc.nextLong();
		long b = sc.nextLong();
		long mod = 1_000_000_007L;
		long n2 = modPow(2, n, mod);
		long nCa = modCombination(n, a, mod);
		long nCb = modCombination(n, b, mod);
		long result = (n2 - nCa - nCb - 1)%mod;
		if(result < 0) {
			result = result + mod;
		}
		System.out.println(result);
	}
	public static long modPow(long base, long exp, long mod) {
		if (exp == 0)
			return 1;
		if (exp == 1)
			return base % mod;
		if (exp % 2 == 1)
			return (base * modPow(base, exp - 1, mod) % mod);
		long tmp = modPow(base, exp / 2, mod);
		return (tmp * tmp) % mod;
	}

	// nCrの値を引数で渡したmodで割った余りをlong型で返す。
	public static long modCombination(long n, long r, long mod) {
		long top = 1;
		long bottom = 1;
		for (int i = 1; i <= r; i++) {
			top *= n;
			top %= mod;
			n--;
			bottom *= i;
			bottom %= mod;
		}
		bottom = modPow(bottom, mod-2, mod);
		return (top * bottom) % mod;
	}
}


Measured memory_bytes: 21844
//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;  typedef long long ll;
inline int qr(){
	int ret=0,f=0,c=getchar();
	while(!isdigit(c))f|=c==45,c=getchar();
	while(isdigit(c)) ret=ret*10+c-48,c=getchar();
	return f?-ret:ret;
}
const int maxn=1<<19|1;
const int mod=924844033;
typedef vector<int> poly;
poly buk(maxn),c(maxn),ans;
int inv[maxn],siz[maxn],r[maxn],jc[maxn],n;

inline int MOD(const int&x){return x-mod>=0?x-mod:x;}
inline int MOD(const int&x,const int&y){return 1ll*x*y%mod;}
inline int MOD(const vector<int>&ve){int ret=1;for(const auto&t:ve) ret=MOD(ret,t); return ret;}

inline int ksm(const int&ba,const int&p){
	int ret=1;
	for(int t=p,b=ba;t;t>>=1,b=MOD(b,b))
		if(t&1) ret=MOD(ret,b);
	return ret;
}
const int g=5;
const int gi=ksm(5,mod-2);

void pre(const int&n){
	jc[0]=inv[0]=1;
	for(int t=1;t<=n;++t) jc[t]=MOD(jc[t-1],t);
	inv[n]=ksm(jc[n],mod-2);
	for(int t=n-1;t;--t) inv[t]=MOD(inv[t+1],t+1);
}

void NTT(poly&a,const int&tag){
	static int r[maxn];
	int len=a.size();
	for(int t=1;t<len;++t)
		if((r[t]=r[t>>1]>>1|(t&1?len>>1:0))>t)
			swap(a[t],a[r[t]]);
	for(int t=1,wn,s=tag==1?g:gi;t<len;t<<=1){
		wn=ksm(s,(mod-1)/(t<<1));
		for(int i=0;i<len;i+=t<<1)
			for(int j=0,w=1,p;j<t;++j,w=MOD(w,wn))
				p=MOD(a[i+j+t],w),a[i+j+t]=MOD(a[i+j]-p+mod),a[i+j]=MOD(a[i+j]+p);
	}
	if(tag!=1)
		for(int t=0,i=mod-(mod-1)/len;t<len;++t)
			a[t]=MOD(a[t],i);
}

poly operator * (poly a,poly b){
	int t1=a.size()+b.size()-1,len=1;
	while(len<t1) len<<=1;
	a.resize(len); b.resize(len);
	NTT(a,1); NTT(b,1);
	for(int t=0;t<len;++t) a[t]=MOD(a[t],b[t]);
	NTT(a,-1); a.resize(t1);
	return a;
}

poly e[maxn];
void add(int fr,int to){
	e[fr].push_back(to);
	e[to].push_back(fr);
}

void dfs(int now,int last){
	siz[now]=1;
	for(auto t:e[now])
		if(t^last)
			dfs(t,now),++buk[siz[t]],siz[now]+=siz[t];
	if(n-siz[now]>=0) ++buk[n-siz[now]];
}

int main(){
	n=qr();
	buk.resize(n+1);
	c.resize(n+1);
	for(int t=1;t<n;++t) add(qr(),qr());
	dfs(1,0); pre(2e5);
	for(int t=1;t<=n;++t) buk[t]=MOD(buk[t],jc[t]);
	reverse(buk.begin(),buk.end());
	for(int t=0;t<=n;++t) c[t]=inv[t];
	ans=buk*c;
	ans.resize(n+1);
	reverse(ans.begin(),ans.end());
	for(int t=1;t<=n;++t) printf("%d\n",MOD(MOD(MOD(jc[n],inv[t]),MOD(inv[n-t],n))-MOD(ans[t],inv[t])+mod));
	return 0;
}



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

#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;

using ll    = long long;
using vll   = vector<ll>;
using pll   = pair<ll,ll>;
using ld    = long double;

const ll mod = (ll)1e9 + 7;
const ll mxN = (ll)4e5 + 3;

void solve() {
	ll a,b;cin>>a>>b;
	cout<<max({2*a-1,2*b-1,a+b});
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.precision(20);
	cout << fixed;
//	pre();
//	ll t;cin>>t;while (t--)
		solve();
}


Measured memory_bytes: 3620
def floorsqrt(x):
  max_ok = 0
  min_ng = x+1
  while min_ng-max_ok>1:
    tgt = (max_ok+min_ng)//2
    if tgt*tgt<=x:
      max_ok = tgt
    else:
      min_ng = tgt
  return max_ok

def K1(C, r):
  max_ok = 0
  min_ng = C
  while min_ng-max_ok>1:
    tgt = (max_ok+min_ng)//2
    if C-tgt>r+tgt*tgt:
      max_ok = tgt
    else:
      min_ng = tgt
  return max_ok

def K2(C, r):
  max_ok = 0
  min_ng = C
  while min_ng-max_ok>1:
    tgt = (max_ok+min_ng)//2
    if C-tgt>r+tgt*(tgt+1):
      max_ok = tgt
    else:
      min_ng = tgt
  return max_ok

Q = int(input())
for _ in range(Q):
  A, B = map(int, input().split())
  if A*B==1:
    print(0)
    continue
  if B<A: A,B = B,A
  
  C = floorsqrt(A*B-1)
  #print(A, B, C, C*C, A*B-1, C*C+2*C+1)
  
  # C:= floor(sqrt(AB-1))
  
  q = (A*B-1)//C
  r = (A*B-1)%C

  if q==C:
    # Case 1: (AB-1)//C == C ... r
    # a :    1 ... C     AB-1
    # b : AB-1     C ...    1
    #
    # (AB-1)//(C-k) == C+k ... r+k*k
    # K = max{k | C-k>r+k*k}
    K = K1(C, r)
    ans = 2*C-3 if B<=C+K else 2*C-2
    #print(K, B, C+K)
  
  elif q==C+1:
    # Case 2: (AB-1)//C == C+1 ... r
    # a :    1 ... C   C+1     AB-1
    # b : AB-1     C+1   C...     1
    #
    # (AB-1)//(C-k) == C+k+1 ... r+k*(k+1)
    # K = max{k | C-k>r+k*(k+1)}
    K = K2(C, r)
    ans = 2*C-2 if B<=C+K+1 else 2*C-1
 
  else:
    # Case 3: (AB-1)//C == C+2
    # a :    1 ... C   C+2     AB-1
    # b : AB-1     C+2   C...     1
    ans = 2*C if A==B else 2*C-1
    
  print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define pb           push_back
#define pii          pair<int,int>
#define vi           vector<int>
#define vii         vector<pair<int,int>>
#define mp           make_pair
#define FOR(i, n) for (int i = 0; i <  (int)(n); i++)
#define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
#define FORD0(i, n) for (int i = (int)n; i >= 0; i--)
#define FORD1(i, n) for (int i = (int)n; i >= 1; i--)
#define debug(X) { cout << #X << " = " << (X) << endl; }
#define endl '\n'
#define int long long int
using namespace std;
vector<vi> mat(2001, vi(2001, 0));
vector<vi> hor(2001, vi(2001, 0));
vector<vi> vert(2001, vi(2001, 0));
vector<vi> cnt(2001, vi(2001, 0));
int rect(int x1, int x2, int y1, int y2, vector<vi>& arr){
    if(x2 < x1 || y2 < y1)return 0;
    assert(x2 >= x1);
    assert(y2 >= y1);
    int ans = arr[x2][y2];
    if(x1 > 0)ans -= arr[x1-1][y2];
    if(y1 > 0)ans -= arr[x2][y1-1];
    if(x1 > 0 && y1 > 0 ){
        ans += arr[x1-1][y1-1];
    }
    return ans;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    
    int n, m, q;cin >> n >> m >> q;
    FOR(i, n){
        string s;cin >> s;
        FOR(j, m)mat[i][j] = s[j] == '1';
    }
    FOR(r, n){
        FOR(c, m){
            cnt[r][c] = mat[r][c] + (c > 0 ? cnt[r][c-1] : 0);
        }
        FOR(c, m){
            if(r == 0)break;
            cnt[r][c] += cnt[r-1][c]; 
        }
    }
    FOR(i, n){
        FOR1(j, m-1){
            hor[i][j] = hor[i][j-1];
            if(mat[i][j -1] == 1 && mat[i][j] == 1){
                 hor[i][j]++ ; 
            }
        }
        FOR1(j, m-1){
            if(i == 0)break;
            hor[i][j] += hor[i-1][j];
        }
        
    }
    FOR1(j, n-1){
        FOR(i, m){
            vert[j][i] = i > 0 ? vert[j][i-1]: 0;
            if(mat[j][i] == 1 && mat[j-1][i] == 1){
                vert[j][i]++;  
            }
        }
        FOR(i, m){
            vert[j][i] += vert[j-1][i];
         
        }
        //cout << endl;
    }
    
    while(q--){
        int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;
        x1--, y1--, x2--, y2--;
        int ans = rect(x1,x2,y1,y2, cnt);
        ans -= rect(x1, x2, y1 + 1,y2, hor);
        ans -= rect(x1+1, x2, y1,y2, vert);
        cout << ans << endl;
    }

}


Measured memory_bytes: 128256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i ,n) for(int i = 0 ; i < (n) ; i ++ )
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using vin=vector<int>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;

int main() {
  int n,m;
  cin>>n>>m;
 /////////
  vector<pair<int,int>> vp(n);//()問題番号、ac、wa
  rep(i,m){
   int p;
    
    string s;
    cin>>p>>s;
    p--;
    if(s=="AC"){
    //  cout<<p<<endl;
       vp[p].first=3;
    }
    else{
      if(vp[p].first!=3)
     vp[p].second++; 
    }
  }
  int ac=0;
  int wa=0;
  for(auto v:vp){
   if(v.first==3){
     ac++;
     wa+=v.second;
   }   
  }
  cout<<ac<<" "<<wa<<endl;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<map>
using namespace std;
const int maxn = 1e5;
int cmp(char A,char B){
	return A>B;
}
int main(){
	int i ,j,flag = 0;
	bool ans = false;
	char a[maxn+5],b[maxn+5];
	cin >> a >> b;
	int a_len = strlen(a) , b_len = strlen(b);
	sort(a,a+a_len);
	sort(b,b+b_len,cmp);
	if(strcmp(a,b)<0)
		printf("Yes\n");
	else
		printf("No\n");
	return 0;
}

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

const string YES = "Yes";
const string NO = "No";

void solve(std::string S){
    auto res = (S[2] == S[3]) && (S[4] == S[5]);
    cout << (res ? YES : NO) << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    std::string S;
    std::cin >> S;
    solve(S);
    return 0;
}


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

int main(){
  int N;
  cin >>N;
  vector<int> a(N);
  for(int i=0;i<N;i++){
    cin >> a[i];
  }
  
  int s=0;
  for(int i=0;i<N;i++){
    s ^=a[i];
  }
  for(int i=0;i<N;i++){
    a[i] ^=s;
  }
  for(int i=0;i<N;i++){
    cout << a[i] <<endl;
  }
}

  
  
  
  

Measured memory_bytes: 4032
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0,i##_max=(N);i<i##_max;++i)
#define repp(i,l,r) for(int i=(l),i##_max=(r);i<i##_max;++i)
#define per(i,N) for(int i=(N)-1;i>=0;--i)
#define perr(i,l,r) for(int i=r-1,i##_min(l);i>=i##_min;--i)
#define all(arr) (arr).begin(), (arr).end()
#define SP << " " <<
#define SPF << " "
#define SPEEDUP cin.tie(0);ios::sync_with_stdio(false);
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

inline void YesNo(bool b){ cout << (b?"Yes" : "No") << endl;}
inline void YESNO(bool b){ cout << (b?"YES" : "NO") << endl;}
inline void Yay(bool b){ cout << (b?"Yay!" : ":(") << endl;}

int main(void){
  SPEEDUP
  cout << setprecision(15);
  int A,B,M;cin >> A >> B >> M;
  vector<int> a(A);
  vector<int> b(B);
  rep(i,A)cin >> a[i];
  rep(i,B)cin >> b[i];
  int ans = 1e6;
  rep(i,M){
    int x,y,c;cin >> x >> y >> c;
    --x;--y;
    ans = min(ans,a[x]+b[y]-c);
  }
  sort(all(a));
  sort(all(b));
  ans = min(ans,a[0]+b[0]);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define meow(args...) fprintf(stderr, args)
template<class T1, class T2> inline bool cmin(T1 &a, const T2 &b) {return b<a?(a=b, true):false;}
template<class T1, class T2> inline bool cmax(T1 &a, const T2 &b) {return a<b?(a=b, true):false;}
template<class Type> Type read() {
	Type a;
	bool b;
	unsigned char c;
	while(c=getchar()-48, (c>9)&(c!=253));
	for(a=(b=c==253)?0:c; (c=getchar()-48)<=9; a=a*10+c);
	return b?-a:a;
}
auto rd=read<int>;

void construct(int m, int x, int y) {
	if(m==0) {
		puts("");
		return;
	}
	int d=1<<--m;
	if(abs(x)>abs(y)) {
		if(x>0) printf("R"), construct(m, x-d, y);
		if(x<0) printf("L"), construct(m, x+d, y);
	} else {
		if(y>0) printf("U"), construct(m, x, y-d);
		if(y<0) printf("D"), construct(m, x, y+d);
	}
}
int main() {
	int n=rd(), max=0;
	std::vector<int> x(n), y(n);
	for(int i=0; i<n; ++i) {
		x[i]=rd(), y[i]=rd();
		cmax(max, abs(x[i])+abs(y[i]));
	}
	for(int i=1; i<n; ++i)
		if((x[i]^y[i]^x[0]^y[0])&1) {
			puts("-1");
			return 0;
		}
	if((x[0]^y[0])&1) {
		puts("31");
		for(int i=31; i--; ) printf("%d%c", 1<<i, " \n"[!i]);
		for(int i=0; i<n; ++i) construct(31, x[i], y[i]);
	} else {
		printf("32\n1");
		for(int i=31; i--; ) printf(" %d", 1<<i);
		printf("\n");
		for(int i=0; i<n; ++i) {
			printf("R");
			construct(31, x[i]-1, y[i]);
		}
	}
	return 0;
}


Measured memory_bytes: 256