akhauriyash/Code-Regression huggingface dataset:
N, X = map(int, input().split())
x = [int(i) for i in input().split()]

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

for i in range(0,N):
    x[i] = x[i] - X

D = x[0]

for i in range(0,N):
    D = gcd(D,x[i])

D = abs(D)
print(D)

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

Measured memory_bytes: 128
// g++ -I ~/Documents/programming/cppLib -std=gnu++14 -o test ~/Documents/programming/cppLib/test.cpp && ./test && rm test
#include <bits/stdc++.h>
using namespace std;
template <typename T> using vector2 = vector <vector  <T>>;
template <typename T> using vector3 = vector <vector2 <T>>;
template <typename T> using vector4 = vector <vector3 <T>>;
using lint = long long;
#define FOR( i, a, b ) for( lint i=(a) ; i <= (b) ; ++i )
#define REP( i, n )    for( lint i= 0  ; i <  (n) ; ++i )
#define ALL( v )       (v).begin(), (v).end()

//	cinからvectorへ入力
template<typename T>
istream& operator >> ( istream& is, vector<T>& vec ) {
    for( T& x: vec ) {
        is >> x;
    }
    return is;
}

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

    vector<int> W(N);
    cin >> W;

    int left = 0, right = accumulate( ALL(W), 0 );
    int ans = INT_MAX;

    FOR(i, 0, N-1) {
        left += W[i];
        right -= W[i];
        ans = min(ans, abs(left-right));
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
import math
from collections import deque

memo = deque([1, 2])
floor = 1
def search(x):
    global memo, floor
    while x > floor:
        memo.append(memo[-1] + memo[-2])
        floor += 1
    return memo[x-1]

CONST = 1000000007
n,m = map(int,input().split())
lis = []
prev = -1
for _ in range(m):
    a = int(input())
    if prev + 1 == a:
        print(0)
        exit()
    lis.append(a-prev-2)
    prev = a
lis.append(n-prev-1)


ans = 1
for v in lis:
    if v == 0: continue
    ans = (ans * search(v)) % CONST
print(ans)


Measured memory_bytes: 460492
#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>;
void chmax(int& a, int b) { a = max(a, b);}

int dp[2005][2005];

int main() {
  int n;
  cin >> n;
  int n3 = n*3;
  vector<int> A(n3);
  rep(i,n3) cin >> A[i], --A[i];
  int m = n+1;
  rep(i,m)rep(j,m) dp[i][j] = -1e9;
  auto upd = [&](int i, int j, int x) {
    chmax(dp[i][j], x);
    chmax(dp[j][i], x);
    chmax(dp[i][n], x);
    chmax(dp[n][i], x);
    chmax(dp[n][j], x);
    chmax(dp[j][n], x);
    chmax(dp[n][n], x);
  };
  upd(A[0],A[1],0);

  int base = 0;
  for (int ai = 2; ai < n3-1; ai += 3) {
    int x = A[ai], y = A[ai+1], z = A[ai+2];
    if (x == y && y == z) {
      ++base;
      continue;
    }
    vector<tuple<int,int,int>> q;
    rep(ri,3) {
      {
        rep(a,m) {
          int now = dp[a][n];
          if (y == z) chmax(now, dp[a][y]+1);
          q.emplace_back(a,x,now);
        }
      }
      {
        int now = max(dp[n][n],dp[z][z]+1);
        q.emplace_back(x,y,now);
      }
      swap(x,y); swap(y,z);
    }

    for (auto t : q) {
      int i, j, x;
      tie(i,j,x) = t;
      upd(i,j,x);
    }
  }

  int ans = dp[n][n];
  int l = A[n3-1];
  chmax(ans, dp[l][l]+1);
  ans += base;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 19384
#include<iostream>
using namespace std;
int main(){
	int N,flag=0;

	cin >> N;
	int big,small;
	big = N/10;
	small = N-big*10;


	if(big==9){
		flag = 1;
	}
	if(small==9){
		flag = 1;
	}

	if(flag == 1){
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}

	


Measured memory_bytes: 256
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq

#全点最短距離(d[i][i]<0だと負閉路あり)
def warshall_floyd(n):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if(d[i][k] == INF or d[k][j] == INF):
          pass
        else:
          d[i][j] = min(d[i][j], d[i][k] + d[k][j])
  return

#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

INF = 1001001
H, W = map(int, input().split())
ans = 0

d = [list(map(int, input().split())) for _ in range(10)]
A = [list(map(int, input().split())) for _ in range(H)]
#G = [[INF for _ in range(10)] for _ in range(10)]
#for i in range(10):
#  for j in range(10):
#    G[i][j] = d[i][j]

warshall_floyd(10)

for i in range(H):
  for j in range(W):
    if(A[i][j] != -1):
      ans += d[A[i][j]][1]

print(ans)


Measured memory_bytes: 40732
#include<stdio.h>
int main(){
	int n_snuke;
	scanf("%d", &n_snuke);
	int has_trts[n_snuke+1];

	//お菓子を持っている->0;持っていない->1
	for(int snuke = 1; snuke <= n_snuke; snuke++)
		has_trts[snuke] = 1;

	int n_trtkinds;
	scanf("%d", &n_trtkinds);
	for(int trt_i = 1; trt_i <= n_trtkinds; trt_i++){
		int n_trt_i, trt_i_to;
		scanf("%d", &n_trt_i);
		for(int trt_i_index = 1; trt_i_index <= n_trt_i; trt_i_index++){
			scanf("%d", &trt_i_to);
			has_trts[trt_i_to] = 0;
		}
	}

	int ans = 0;
	for(int snuke = 1; snuke <= n_snuke; snuke++)
		ans += has_trts[snuke];
	printf("%d", ans);

	return 0;
}

Measured memory_bytes: 1732
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define ll long long
const ll MOD=1000000007;
const long double PI=3.14159265358979;
const ll MAX=0;

int main() {
  ll N;
  cin>>N;
  N%=10;
  if(N==2||N==4||N==5||N==7||N==9){
    cout<<"hon";
  }
  else if(N==3){
    cout<<"bon";
  }
  else{
    cout<<"pon";
  }
}

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        int buf;
        cin >> buf;
        a.at(buf-1) = i+1;
    }
    for(int i = 0; i < n; i++){
        cout << a.at(i);
        if(i != n-1){
            cout << " ";
        }else{
            cout << endl;
        }
    }
}

Measured memory_bytes: 1152
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
	int N; cin >> N;
	if (N % 2 == 0) cout << N << endl;
	else cout << N * 2 << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
//---------------------------
using namespace std;
//---------------------------
#define REP(i,n) for(int i = 0; i < (n); i++)
#define P(x) cout << (x) << "\n"

#define MOD 1e9+7
#define PI acos(-1.0)
#define ll long long
//---------------------------

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


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

  // ifstream in("input.txt");
  // cin.rdbuf(in.rdbuf());

  int H,W;
  cin>>H>>W;
  char s[100][100];
  int d[100][100];
  int e[100][100];
  int black=0;
  queue<int> qx,qy;
  for(int i=1;i<=H;i++){
    for(int j=1;j<=W;j++){
      cin>>s[i][j];
      if(s[i][j]=='.'){
        d[i][j]=0;
      }
      if(s[i][j]=='#'){
        d[i][j]=1;
        black++;
      }
    }
  }
  qx.push(1);qy.push(1);
  e[1][1]=1;
  while(!qx.empty()){
    int x=qx.front();qx.pop();
    int y=qy.front();qy.pop();
    if(x==H &&y==W){
      P(H*W - black - e[x][y]);
      return 0;
    }
    REP(i,4){
      int xx=x+dx[i];
      int yy=y+dy[i];
      if(xx>=1&&xx<=H&&yy>=1&&yy<=W&&e[xx][yy]==0&&d[xx][yy]==0){
        qx.push(xx);qy.push(yy);
        e[xx][yy]=e[x][y]+1;
      }
    }
  }

  P(-1);
  return 0;
}


Measured memory_bytes: 384
h, w = map(int, input().split())
rb = [['#'] * (w + 2)]
a = rb + [list('#' + input() + '#') for _ in range(h)] + rb
p = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1) if a[i][j] == '#']
d = (-1, 0), (1, 0), (0, -1), (0, 1)
r = -1
while p:
    r += 1
    s = []
    for di, dj in d:
        for i, j in p:
            i += di
            j += dj
            if a[i][j] == '.':
                a[i][j] = '#'
                s.append((i, j))
    p = s
print(r)

Measured memory_bytes: 132688
#include <bits/stdc++.h>
template <long long mod>
class Combination
{
    std::vector<long long> fact, finv, inv;
public:
    Combination(int sz)
    {
        fact.resize(sz);
        finv.resize(sz);
        inv.resize(sz);
        fact[0] = 1;
        for (int i = 1; i < sz; ++i)
        {
            fact[i] = fact[i - 1] * i % mod;
        }
        inv[0] = 0;
        inv[1] = 1;
        for (int i = 2; i < sz; ++i)
        {
            inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        }
        finv[0] = 1;
        for (int i = 1; i < sz; ++i)
        {
            finv[i] = finv[i - 1] * inv[i] % mod;
        }
    }
    long long C(long long n, long long k)
    {
        if (n < k)
            return 0;
        if (n < 0 || k < 0)
            return 0;
        return (fact[n] * finv[k] % mod) * finv[n - k] % mod;
    }
    long long P(long long n, long long k)
    {
        if (n < k)
            return 0;
        if (n < 0 || k < 0)
            return 0;
        return fact[n] * finv[n - k] % mod;
    }
    long long H(long long n, long long k)
    {
        return this->C(n + k - 1, k);
    }
    long long getfact(int i)
    {
        return fact[i];
    }
    long long getinv(int i)
    {
        return inv[i];
    }
    long long getfinv(int i)
    {
        return finv[i];
    }
};
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const ll MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;
template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}
template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int n; cin >> n;
  vll a(n);
  for(int i=0;i<n;++i) {
    cin >> a[i];
  }
  Combination<MOD> comb(1000000);
  vll suinv(n+1);
  suinv[1] = 1;
  for(int i=2;i<=n;++i) {
    suinv[i] = suinv[i-1] + comb.getinv(i);
    suinv[i] %= MOD;
  }
  ll ans = 0;
  for(int i=0;i<n-1;++i) {
    ll now = a[i+1] - a[i];
    ans += now * suinv[i+1] % MOD;
    ans %= MOD;
  }
  cout << ans * comb.getfact(n-1) % MOD << endl;
}


Measured memory_bytes: 25344
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {

    private static Scanner in = new Scanner(System.in);
    private static PrintWriter out = new PrintWriter(System.out);

    private static final int MOD = 2019;

    public static void main(String[] args) {
        solve();
        out.flush();
    }

    private static void solve() {
        int l = in.nextInt();
        int r = in.nextInt();

        int ans = Integer.MAX_VALUE;
        for (int i=l; i <= Math.min(l+2018, r-1); i++) {
            for (int j=l+1; j <= Math.min(l+2019, r); j++) {
                int n = ((i % MOD) * (j % MOD)) % MOD;
                ans = Math.min(ans, n);
            }
        }

        out.println(ans);
    }
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

#if DEBUG && !ONLINE_JUDGE
    ifstream input_from_file("input.txt");
    #define cin input_from_file
#else

#endif



int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); // Togliere nei problemi con query online

    for (int i = 1; i <= 5; i++) {
        int x;
        cin >> x;
        if (x == 0) {
            cout << i << "\n";
            return 0;
        } 
    }
}


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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2019/03/11  Problem: ABC 087 C / Link: http://abc087.contest.atcoder.jp/tasks/abc087_c  ----- */


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

	LL N;
	cin >> N;
	VVL a(2, VL(N));
	FOR(i, 0, 2) {
		FOR(j, 0, N) {
			cin >> a[i][j];
		}
	}
	VVL dp(2, VL(N + 1, 0));

	FOR(j, 0, N) {
		dp[0][j] += a[0][j];
		dp[0][j + 1] = max(dp[0][j + 1], dp[0][j]);
		dp[1][j] = max(dp[1][j], dp[0][j]);

		dp[1][j] += a[1][j];
		dp[1][j + 1] = max(dp[1][j + 1], dp[1][j]);
	}
	LL ans = dp[1][N - 1];

	cout << (ans) << "\n";

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) _MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define pb push_back
#define all(x) begin(x),end(x)
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#ifdef LOCAL
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cerr<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cerr<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.first<<","<<p.second<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
#else
#define dbg(...) {}
#endif

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

  vector<int> a(m);
  rep(i,m) cin>>a[i];
  sort(all(a));

  vector<int> costs = {-1,2,5,5,4,5,6,3,7,6};

  vector<int> dig(n+1, -1);
  dig[0] = 0;

  rep(i,n) if(dig[i] >= 0){
    rep(j,m){
      int ni = i + costs[a[j]];
      if(ni <= n) dig[ni] = max(dig[ni], dig[i] + 1);
    }
  }

  string ans;
  int p = n;
  while(p > 0){
    int nx = -1;
    rep(j,m) if(p-costs[a[j]] >= 0 && dig[p-costs[a[j]]]+1 == dig[p]) nx = a[j];
    assert(nx > 0);
    ans += (char)('0' + nx);
    p -= costs[nx];
  }

  cout << ans << endl;  

  return 0;
}


Measured memory_bytes: 256
///////////////////////////////////////////////////
/* __                                       __   */
/*|  |--.-----.---.-.----.----.-----.-----.|  |_ */
/*|  _  |  -__|  _  |  __|  __|  -__|  _  ||   _|*/
/*|_____|_____|___._|____|____|_____|   __||____|*/
/*                                  |__|         */
///////////////////////////////////////////////////
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<utility>
#include<vector>
typedef long long lint; using namespace std;
#define rep(counter, limit) for (int counter = 0; counter < (limit); counter++)
#define INF 1000000000000
#define MOD 10000007
int gcd(int a, int b) { if (a % b == 0) { return(b); } else { return(gcd(b, a % b)); } }
int lcm(int a, int b) { return a * b / gcd(a, b); }
bool primenum(int a) { if (a == 1) { return false; }if (a == 2) { return true; }if (a % 2 == 0) { return false; }for (int i = 3; i < sqrt(a) + 1; i += 2) { if (a != i) { if (a % i == 0) { return false; } } }return true; }
struct setupios{setupios(){cin.tie(0);ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);};}setupios;
int main() {

  int s,w;
  cin>>s>>w;
  if(s<=w){
    cout<<"unsafe"<<endl;
  }else{
    cout<<"safe"<<endl;
  }

}


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

// Binary Indexed Tree (Fenwick Tree)
// https://youtu.be/lyHk98daDJo?t=7960
template <typename T>
struct BIT {
    int n;
    vector<T> d;
    BIT(int n = 0) : n(n), d(n + 1) {}
    void add(int i, T x = 1) {
        for (i++; i <= n; i += i & -i) {
            d[i] += x;
        }
    }
    T sum(int i) {
        T x = 0;
        for (i++; i; i -= i & -i) {
            x += d[i];
        }
        return x;
    }
    T sum(int l, int r) {
        return sum(r - 1) - sum(l - 1);
    }
};

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    vector<int> pi(n + 1, -1);
    vector<vector<int>> ps(n);
    rep(i, n) {
        int l = pi[a[i]];
        if (l != -1) ps[l].emplace_back(i);
        pi[a[i]] = i;
    }

    vector<vector<P>> qs(n);
    rep(qi, q) {
        int l, r;
        cin >> l >> r;
        --l, --r;
        qs[l].emplace_back(r, qi);
    }

    vector<int> ans(q);
    BIT<int> d(n);
    for (int x = n - 1; x >= 0; --x) {
        for (int y : ps[x]) d.add(y, 1);
        for (P query : qs[x]) {
            int r = query.first, i = query.second;
            ans[i] = (r - x + 1) - d.sum(r);
        }
    }

    rep(i, q) cout << ans[i] << endl;
    return 0;
}

Measured memory_bytes: 59916
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[200010];
int cf[200010];
int fir;
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]>=i-1){
			fir++;
		}
		if(i-a[i]>=2){
			cf[i-a[i]]++;
		}
		if(i+a[i]+1<=n){
			cf[i+a[i]+1]--;
		}
	}
	while(k--){
		a[1]=fir;
		int cnt=0;
		for(int i=2;i<=n;i++){
			a[i]=a[i-1]+cf[i];
			cf[i]=0;
			cnt+=(a[i]>=n);
		}
		cnt+=(a[1]>=n); 
		fir=0;
		if(cnt>=n){
			break;
		}
		for(int i=1;i<=n;i++){
			if(a[i]>=i-1){
				fir++;
			}
			if(i-a[i]>=2){
				cf[i-a[i]]++;
			}
			if(i+a[i]+1<=n){
				cf[i+a[i]+1]--;
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<a[i]<<' ';
	}
	return 0; 
}

Measured memory_bytes: 5192
// A.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char* argv[]) {
    int x;
    cin >> x;
    string ans = x >= 30 ? "Yes" : "No";
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3588
import sys
sys.setrecursionlimit(10**6)

a=int(input())
b=int(input())
c=int(input())
x=int(input())

ans=0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if x==500*i+100*j+50*k:
                ans+=1
print(ans)




Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <string>
#include <cstring>

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

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

constexpr ull mod = 1e9+7;
constexpr int N = 13;
ull dp[100010][N];

int myPower(int a, int n) { // aのn乗の計算
	int x = 1;
	while (n > 0) { // 全てのbitが捨てられるまで
		if ( n & 1) { // 一番右のbitが１のとき
			x *= a;
		}
		a *= a;
		n >>= 1; // bit全体を右に1つシフトして一番右を捨てる
	}
	return x;
}

int main() {
	ll n, i, j;
	cin >> n;
	ll ans = 1LL << 62;
	for (i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			ans = min(ans, i + n / i);
		}
	}
	cout << ans - 2;
	return 0;
}

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

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

    int n;
    cin >> n;
    vector<int> A(n);
    REP(i, n) cin >> A[i];

    int maxi = -1e9;
    int mini = 1e9;
    REP(i, n){
        maxi = max(maxi, A[i]);
        mini = min(mini, A[i]);
    }
    cout << abs(maxi - mini) << endl;

    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;

using ll = long long int;
using ha = pair<ll, ll>;
struct RollingHash {
	static const ll mul0 = 10009, mul1 = 10007;
	static const ll add0 = 1000010007, add1 = 1003333331;
	size_t len;
	//vector<ll> hash_, hash2_;
	vector<ha>hash_;
	//static vector<ll> pmo_, pmo2_;
	static vector<ha>pmo_;
	void init(const vector<ll>& s) {
		len = s.size();
		hash_.resize(len + 1);
		hash_[0] = make_pair(0, 0);

		if (pmo_.empty()) {
			pmo_.push_back(make_pair(1, 1));
		}
		while (pmo_.size() <= len) {
			pmo_.push_back(make_pair(pmo_.back().first*mul0, pmo_.back().second*mul1));
		}
		for (unsigned int i = 0; i < len; ++i) {
			hash_[i + 1] = make_pair((hash_[i].first * mul0 + s[i]), (hash_[i].second*mul1 + s[i]));
		}
		return;
	}
	void init(const string& s) {
		vector<ll>v;
		for (char c : s) {
			v.push_back(c);
		}
		init(v);
	}
	ha hash(const int l, const int r)const { // s[l..r]
		return make_pair(hash_[r + 1].first - hash_[l].first * pmo_[r + 1 - l].first,
			hash_[r + 1].second - hash_[l].second * pmo_[r + 1 - l].second);
	}
	ha  hash()const { // s[all]
		return hash(0, len - 1);
	}

	//hash????????????
	static ha concat(const ha L, const ha R, const int RLength) { // hash(L+R) 
		return make_pair((R.first + L.first*pmo_[RLength].first), (R.second + L.second*pmo_[RLength].second));
	}

	//index????????????from??????to????????????????????????????????\????????????
	ha get_changed_hash(const int index, const ll from, const ll to)const {
		const ha p(hash());
		return make_pair(
			p.first + (to - from) * pmo_[len - index - 1].first,
			p.second + (to - from) * pmo_[len - index - 1].second);
	}
};
vector<ha> RollingHash::pmo_;

int main() {
	int H, W; cin >> H >> W;
	vector<RollingHash>rhs(H);
	vector<string>sts(H);
	for (int i = 0; i < H; ++i) {
		cin >> sts[i];
		rhs[i].init(sts[i]);
	}
	int R, C; cin >> R >> C;
	vector<ha>hashes(R);
	for (int i = 0; i < R; ++i) {
		string st; cin >> st;
		RollingHash rh;
		rh.init(st);
		hashes[i] = rh.hash();
	}
	for (int u = 0; u <= H - R; ++u) {
		for (int l = 0; l <= W - C; ++l) {
			bool ok = true;
			for (int y = u; y < u + R; ++y) {
				if (hashes[y - u] == rhs[y].hash(l, l + C-1)) {

				}
				else {
					ok = false;
				}
			}
			if (ok) {
				cout << u << " " << l << endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 19812
import java.util.Scanner;

public class Main {

    public static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = Long.parseLong(sc.next());
        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            long mod = n % 26;
            if (mod == 0) {
                n--;
                mod = 25;
            } else {
                mod--;
            }
            sb.append((char) ('a' + mod));
            n /= 26;
        }
        System.out.println(sb.reverse().toString());
    }
}

Measured memory_bytes: 35788
#include <iostream>
using namespace std;
int main(void){
    int t,n,s,f,i;
    
    while(true){
        cin >> t >> n;
        int sum = 0;
        if(t == 0){
            break;
        }
        
        for(i = 0; i < n; i++){
            cin >> s >> f;
            sum += f - s;
        }
        if(sum >= t){
            cout << "OK" << endl;
        }
        else{
            cout << t - sum << endl;
        }
    }
    
}


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

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

    uint64_t tmp = 0, sum = 0, ans = 0;
    for (auto i = 0; i < (1 << s.size() - 1); i++) {
        sum = 0;
        tmp = 0;
        for (auto j = 0; j < s.size(); j++) {
            tmp = tmp * 10 + (s[j] - '0');
            if(i & (1 << j)) {
                sum += tmp;
                tmp = 0;
            }
        }
        ans += tmp + sum;
    }

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

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

int main() {
  int N;
  cin >> N;
  int existY = 0;
  for (int i = 0; i < N; i++) {
    string color;
    cin >> color;
    existY += (color == "Y");
  }
  if (existY) {
    cout << "Four" << endl;
  } else {
    cout << "Three" << endl;
  }
}

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

int main()
{
  int x, y ,z;
  cin >> x >> y >> z;
  int a, b, c;
  a = z;
  b = x;
  c = y;

  cout << a << " " << b << " " << c << endl;
}


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

using namespace std;

int n;
int arr[3] = {};
double memo[301][301][301] = {};

double dp(int a, int b, int c)
{
    if (a < 0 || b < 0 || c < 0)
        return 0;
    if (a + b + c == 0)
        return 0;
    if (memo[a][b][c] > 0)
        return memo[a][b][c];
    double ex = 1;
    ex += ((double) a / n) * dp(a - 1, b, c);
    ex += ((double) b / n) * dp(a + 1, b - 1, c);
    ex += ((double) c / n) * dp(a, b + 1, c - 1);
    ex = ex / ((a + b + c) / (double) n);
    memo[a][b][c] = ex;
    return ex;
    
}

int main(void)
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    int ipt;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &ipt);
        arr[ipt - 1]++;
    }
    double res;
    res = dp(arr[0], arr[1], arr[2]);
    cout.precision(13);
    cout << res << endl;
    
}

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

using namespace std;

int main()
{
    int N, K;
    int x;

    cin >> N >> K;

    int d = 0;

    for(int i=0; i<N; i++){
        cin >> x;

        int dx = abs(x - K);

        if(x < dx){
            d += x;
        }
        else{
            d += dx;
        }
    }

    cout << d*2 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
struct t{
	string name;
	int len;
	t(){
		len=0;
	}
}re[4];
int main(){
	int n;
	cin>>n;
	while(n--){
		string r;
		cin>>r;
		re[0].name="AC";
		re[1].name="WA";
		re[2].name="TLE";
		re[3].name="RE";
		if(r=="AC"){
		
			re[0].len++;
		}else if(r=="WA"){
			
			re[1].len++;
		}else if(r=="TLE"){
		
			re[2].len++;
		}else{
			
			re[3].len++;
		}
	}
	for(int i=0;i<4;i++){
		cout<<re[i].name<<" x "<<re[i].len<<endl;
	}
}

Measured memory_bytes: 3632
#include "bits/stdc++.h"

#define ed cout<<"\n";
#define speed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long 
#define ffor(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(i, n) ffor(i,0,n)
#define All(obj) (obj).begin(),(obj).end()
#define INF ((ll)1e9+7)
#define c(a) cout<<a<<"\n";
using namespace std;
const int N = 100005;



int main() {
	speed;
	cout << fixed << setprecision(6);
	/*start*/
	string s;
	cin >> s;
	int ans = 0;
	if (s == "SUN")ans = 7;
	else if (s == "MON")ans = 6;
	else if (s == "TUE")ans = 5;
	else if (s == "WED")ans = 4;
	else if (s == "THU")ans = 3;
	else if (s == "FRI")ans = 2;
	else if (s == "SAT")ans = 1;
	c(ans);
	ed;
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define Mid (l+r)/2
#define ll long long
const int maxn=55,inf=0x3f3f3f3f,mod=1e9+7;
int n,m,T,Q;
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;
}
signed main(){
    int k,a,b;
    k=read();a=read(),b=read();
    if(a%k==0||b%k==0){puts("OK");return 0;}
    int aa=a/k,bb=b/k;
    if(aa==bb)puts("NG");
    else puts("OK");


    return 0;
}

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

#define int long long
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

/* short */
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define gcd __gcd
#define SIZE(x) ll((x).size())
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define SUM(x) accumulate(ALL(x), 0)

/* REPmacro*/
#define FOR(i, a, b) for (int i = (a); i < (int)(b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for (int i = (a); i >= (int)(b); --i)
#define RREP(i, n) RFOR(i, n, 0)
#define EACH(i, n) for (auto&& i : n)

/* alias */
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using str = string;


/* const */
const int INF = 1001001001;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

/* func */
template <typename T = int> inline T in(){T x; cin >> x; return x;}
template <typename T> inline void print(const T& x){cout << x << "\n";}
inline void printvec(const vi& vec){REP(i, SIZE(vec)) cout << vec.at(i) << ((i == SIZE(vec)) ? "\n" : " ");}
inline int lcm(int a, int b){return a / gcd(a, b) * b;}
bool is_prime(int n){if (n < 2) return false;FOR(i, 2, (int)(sqrt(n) + 1)){if (n % i == 0) return false;}return true;}


signed main(){
  int N = in();
  vi H(N); EACH(x, H) x = in();
 
  int c = 0, m = N != 1 ? -INF : 0;
  REP(i, N-1){
    if ((H[i+1]-H[i]) <= 0) ++c;
    else c = 0;
    m = max(m, c);
  }
  print(m);
    
}

Measured memory_bytes: 1024
#include <stdio.h>
#define MAX 500000

int H[MAX + 1];

void maxHeepify(int, int);
void buildMaxHeep(int);
void swap(int, int);

int main()
{
    int i;
    int n;

    scanf("%d", &n);
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &H[i]);
        // printf(" %d",H[i]);
    }

    buildMaxHeep(n);

    for (i = 1; i <= n; i++)
    {
        printf(" %d", H[i]);
    }

    printf("\n");

    return 0;
}

void maxHeepify(int i, int n)
{
    int l, r;
    int largest;

    l = i * 2;
    r = i * 2 + 1;
    //左の子、自分、右の子で値が最大のノードを選ぶ

    if (l <= n && H[l] > H[i])
        largest = l;
    else
        largest = i;

    if (r <= n && H[r] > H[largest])
        largest = r;

    if (largest != i)
    {
        swap(i, largest);
        maxHeepify(largest, n);
    }
}

void buildMaxHeep(int n)
{
    int i;

    for (i = n / 2; i >= 1; i--)
    {
        maxHeepify(i, n);
    }
}

void swap(int a, int b)
{

    int tmp;
    tmp = H[a];
    H[a] = H[b];
    H[b] = tmp;
}



Measured memory_bytes: 3724
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INFLL LLONG_MAX // 9223372036854775807
#define EPS 1e-9
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
template<class T>bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
using namespace std;

// 連長圧縮（ランレングス圧縮）：sの連長部分を{文字,個数}の配列で返す。
vector<pair<char, long long>> RunLengthEncoding(string s){
    vector<pair<char, long long>> ret;
    long long i = 0, n = s.size();
    while(i<n){
        char tmp = s[i];
        long long cnt = 1;
        while(i<n){
            i++;
            if(tmp == s[i]) cnt++;
            else break;
        }
        ret.push_back(make_pair(tmp, cnt));
    }
    return ret;
}

int main(){
    Init();
    string s; ll k;
    cin >> s >> k;
    
    auto rle = RunLengthEncoding(s);
    if(rle.size() == 1){
        // 全部同じ文字の場合
        cout << (s.size()*k)/2 << endl;
    }
    else{
        ll loopCnt = 0;
        rep(i, s.size()-1){
            if(s[i] == s[i+1]){
                loopCnt++;
                i++;
            }
        }
        if(rle[0].first != rle[rle.size()-1].first){
            // 最初の文字と最後の文字が異なる場合
            cout << loopCnt*k << endl;

        }
        else{
            // 最初の文字と最後の文字が同じ場合
            ll sub = (rle[0].second/2 + rle[rle.size()-1].second/2 - (rle[0].second+rle[rle.size()-1].second)/2)*(k-1);
            cout << loopCnt*k-sub << endl;
        }
    }
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)

using namespace std;

const double INF = numeric_limits<double>::max();
const int MAX_L = 50;

inline void update(double& x, const double& y) {
    if(x > y) {
        x = y;
    }
}

int main(){
    int n;
    while(cin >> n && n > 0) {
        vector<double> p;
        double cnt = 0;
        REP(i, n) {
            double x;
            cin >> x;
            if(x != 1.00) {
                if(cnt > 0){
                    p.push_back(cnt);
                    cnt = 0;
                }
                p.push_back(x);
            } else {
                cnt += 1.0;
            }
        }

        if(cnt > 0) {
            p.push_back(cnt);
        }

        n = p.size();

        vector<double> dp(n + 1, INF);
        dp[0] = 0;

        for(int i = 0; i < n; i++) {
            double cost = 0;
            for(int j = 0; j < MAX_L && i + j < n; j++) {
                if(p[i + j] < 1.0) {
                    cost = (cost + 1) / p[i + j];
                } else {
                    cost = (cost + p[i + j]) / 1.0;
                }
                update(dp[i + j + 1], dp[i] + cost + (i + j + 1 == n ? 0.0 : 1.0));
            }
        }

        printf("%.12f\n", dp[n]);
    }
    return 0;
}

Measured memory_bytes: 2960
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph= vector<vector<int>>; 
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
int main(){
  int n ;cin>>n ;
  vector<ll> A(n) ,B(n) ;
  rep(i,n) cin>>A[i] >>B[i] ;
 ll ans=0 ;
  rep3(i,n-1,0){
   int k=(A[i]+ans)%B[i] ;
   if(k==0 ) continue ;
   ans+=B[i]-k ;
  }
  
  cout<< ans <<endl ;
     return 0;
  }

Measured memory_bytes: 1792
#include <iostream>
#define rep(i, n) for (int i = 0; i < n; i++)

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

int main() {
  int h, w;
  std::cin >> h >> w;

  bool tar[50][50];
  rep(i, h) rep(j, w) {
    char ch;
    std::cin >> ch;
    tar[i][j] = (ch == '#');
  }

  bool res = false;
  rep(i, h) rep(j, w) {
    if (tar[i][j]) {
      bool flag = false;
      rep(k, 4) {
        if (tar[i + dx[k]][j + dy[k]]) {
          flag = true;
          break;
        }
      }
      if (!flag) goto no;
    }
  }
  res = true;
no:
  std::cout << (res ? "Yes" : "No") << std::endl;

  return 0;
}

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

#define BR "\n"
#define SP " "
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << SP; } cout << BR;
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << BR;

int main() {
  string S;
  cin >> S;
  int s = S.size();

  vector<ll> dp2(13, 0);

  int r = 10;
  ll MOD = 1e9+7;

  if (S[s-1] == '?') {
    for (int i = 0; i < 10; i++) {
      dp2[i] = 1;
    }
  } else {
    dp2[S[s-1] - '0'] = 1;
  }

  for (int i = 1; i < s; i++) {
    vector<ll> dp1(13, 0);
    for (int j = 0; j < 13; j++) {

      if (S[s-1-i] == '?') {
        for (int k = 0; k < 10; k++) {
          dp1[(j + k * r) % 13] = (dp1[(j + k * r) % 13] + dp2[j]) % MOD;
        }
      } else {
        int k = S[s - 1 - i] - '0';
        dp1[(j + k * r) % 13] = (dp1[(j + k * r) % 13] + dp2[j]) % MOD;
      }
    }
    r = (r * 10) % 13;
    dp2 = dp1;
  }

  cout << dp2[5] << "\n";
  return 0;
}

Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<queue>

using ll = long long;
using namespace std;

const int INF = 1001001001;
const int MOD = 1000000007;

int main(void){
	int s, w;
	cin >> s >> w;
	if (s > w){
		cout << "safe" << endl;
	}else{
		cout << "unsafe" << endl;
	}

	return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#define debug(x) cerr << #x << ':' << x << endl
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define ALL(c) (c).begin(), (c).end()
using namespace std;
typedef long long ll;

int main(){
    string s;
    cin >> s;
    int n = s.size();
    rep(i,n){
        cout << s[n-i-1];
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 3132
#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(n) begin(n),end(n)
using namespace std;
using ll = long long;

int main()
{  
    int k;
    cin >> k;
    string s;
    cin >> s;
    string ans;
    if(s.length()<=k){
        ans = s;
    }else{
        ans = s.substr(0,k) + "...";
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3620
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

using P = pair<int, int>;

vector<P> runlength(const string& a) {
  vector<P> res;
  for (int i = 0; i < a.size(); i++) {
    if (i == 0 || a[i - 1] != a[i]) {
      res.push_back(P(a[i], i));
    }
  }
  return res;
}

int main() {
#ifdef DEBUG
  ifstream cin("in.txt");
#endif
  int N, K;
  string S;
  while (cin >> N >> K >> S) {
    auto R = runlength(S);
    int res = 0;
    for (int i = 0; i < R.size(); i++) {
      int j = i + 2 * K + (R[i].fst == '1');
      int score = (j >= R.size() ? N : R[j].snd) - R[i].snd;
      chmax(res, score);
    }
    cout << res << endl;
  }
  return 0;
}


Measured memory_bytes: 1528
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        
        int ans=0;
        for(int i=1;i<=N;i++){
            int count=0;
            if(i%2==1){
                for(int j=1;j<=i;j++){
                    if(i%j==0){
                        count++;
                    }
                }
                if(count==8){
                    ans++;
                }
            }
        }
        
        System.out.println(ans);
    }
}


Measured memory_bytes: 22612
#include <bits/stdc++.h>
#include <stdio.h>
#include <math.h>
#include <cmath>
using namespace std;
#define vsort(vec) sort(vec.begin(), vec.end())
#define vreverse(vec) reverse(vec.begin(), vec.end())
using ll =long long;
using ull =unsigned long long;
const ll INF =1001001001;

//10億7。　　　100000007

//最大公約数
ll gcd(ll a, ll b){
   if (a%b==0){
       return(b);
   }else{
       return(gcd(b,a%b));
   }
}
//最小公倍数
ll lcm(ll a, ll b){
   return a*b/gcd(a,b);
}


int main(){
cout<<fixed<<setprecision(10);
//cin.tie(0); ios::sync_with_stdio(false);

  int S,W;
  cin>>S>>W;
  if(W>=S){
    cout<<"unsafe"<<endl;
  }else{
    cout<<"safe"<<endl;
  }
  
}



Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define brep(i,n) for(int i=n-1;i>=0;i--)
#define rep1(i,n) for(int i=1;i<n;i++)
#define cY cout<<"Yes"<<endl
#define cN cout<<"No"<<endl
#define ll long long

unsigned const int MOD = 1e9+7;


int main(void){
    ll n,ans;
    double sum = 0;
    cin >> n;
    int a[n];
    rep(i,n){
        cin >> a[i];
        sum +=a[i];
    }
    sum/=n;
    double sa = INT_MAX;
    rep(i,n){
        if(abs(a[i]-sum)<sa){ans=i;sa=abs(a[i]-sum);}
    }
    
    cout << ans << endl;
}


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

static const int N = 1000;

int lcs(string X, string Y){
  int c[N+1][N+1];
  int m = X.size();
  int n = Y.size();
  int maxl = 0;
  X = ' ' + X;
  Y = ' ' + Y;
  for(int i=0;i<=m;i++) c[i][0] = 0;
  for(int j = 1;j<=n;j++) c[0][j] = 0;

  for(int i = 1;i <= m;i++){
    for(int j = 1;j <= n;j++){
      if(X[i] == Y[j]){
	c[i][j] = c[i-1][j-1] + 1;
      }else{
	c[i][j] = max(c[i-1][j], c[i][j-1]);
      }
      maxl = max(maxl, c[i][j]);
    }
  }

  return maxl;
}

int main(){
  string s1,s2;
  int n;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> s1 >> s2;
    cout << lcs(s1,s2) << endl;
  }
  return 0;
}
	 
			       



Measured memory_bytes: 7124
import math
import sys

def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()

    
    array_result.append(data.split(" "))

    flg = 1

    try:


        while flg:

            data = input()

            array_temp = []

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:


        return array_result





arr_data = getinputdata()

n = int(arr_data[0][0])


maxdata=0


seq=1

for v in range(1,1+n):
    
#    print(v)
    
    vtemp=v
    cnt=0
    while(vtemp%2==0):
#        
    
        cnt+=1
#        print(v,vtemp,cnt,maxdata)
        vtemp=vtemp/2
    
    else:   
        
#        print(maxdata,cnt,v)
        if maxdata<cnt:

            maxdata=cnt
            seq=v

        

print(seq)
            

Measured memory_bytes: 3188
N = int(input())
A=[int(i) for i in input().split()]
L = []
asum=A[0]
ans = 0
r=1
for i in range(N):
    while True:
        if (r==N):
            break
        if (asum & A[r])>0:
            break
        asum += A[r]   
        r += 1
    asum -= A[i]
    ans += r-i
print(ans)

Measured memory_bytes: 23560
x1,y1,x2,y2=map(float,raw_input().split(" "))
if y1==y2 or x1==x2:
    if y1==y2:
        t0=0
        t1=-1
    if x1==x2:
        t1=0
        t0=-1
else:
    t0=(y2-y1)/(x2-x1)
    b0=y1-t0*x1
    t1=-(x2-x1)/(y2-y1)

for i in xrange(int(raw_input())):
    px,py=map(float,raw_input().split(" "))
    if t0==0 or t1==0:
        if t0==0:
            a=1.0
            b=-t0
            c=y1
            d=0.0
            e=-t1
            f=px
        if t1==0:
            a=0.0
            b=-t0
            c=x1
            d=1.0
            e=-t0
            f=py
    else:
        b1=py-t1*px
        a,b,c,d,e,f=1.0,-t0,b0,1.0,-t1,b1
    kouten_y=(c*e-f*b)/(a*e-b*d)
    kouten_x=(a*f-c*d)/(a*e-b*d)
    print "{0:.10f} {1:.10f}".format(kouten_x,kouten_y)

Measured memory_bytes: 4320
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <map>

int main(){
  int N, K;
  scanf("%d",&N);
  scanf("%d",&K);
  std::vector<int > p(N);
  std::vector<int > sum(N+1);
  sum[0]=0;
  for (int i=0; i<N; i++){
    scanf("%d",&p[i]);
    sum[i+1] = sum[i]+p[i];
  }
  double temp;
  int index = -1;
  for (int i=K; i<=N; i++){
    if (sum[i]-sum[i-K]>temp){
      index = i;
      temp = sum[i]-sum[i-K];
    }
  }
  printf("%lf\n",temp*0.5+K/2.0);
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
const double PI=acos(-1);

template<typename T>
istream& operator>> (istream& is, vector<T> &vec){
    for(T& x: vec) is >> x;
    return is;
}

const ll mod = 1000000007;
const ll contest = 26;

int main(){
    ll d, csum = 0; cin >> d;
    vector<ll> c(contest);
    vector<vector<ll>> s(d, vector<ll>(contest));
    rep(i, contest){
        cin >> c[i];
        csum += c[i];
    }
    rep(i, d) rep(j, contest) cin >> s[i][j];
    vector<ll> last(contest, 0);
    vector<ll> result(d, 0);
    ll sum = 0;
    rep(i, d){
        ll maxx = 0, tt = 1, score = 0;
        rep(t, contest){
            score = sum + s[i][t];
            rep(j, contest){
                if(t == j) continue;
                score -= c[j]*((i+1)-last[j]);
            }
            if(score > maxx){
                tt = t;
                maxx = score;
            }
        }
        last[tt] = i+1;
        result[i] = tt;
        sum += maxx % mod;
        //cout << tt+1 << endl;
    }

    fill(last.begin(), last.end(), 0);
    sum = 0;
    rep(i, d){
        sum += s[i][result[i]];
        last[result[i]] = i+1;
        rep(j, contest){
            if(result[i] == j) continue;
            sum -= c[j]*((i+1)-last[j]);
        }
    }
    
    rep(a, d){
        rep(b, 100){
            random_device rd;
            mt19937 mt(rd());
            ll tt = a, cc = mt()%contest;
            double p = mt()%1000000/999999.0;
            ll bak = result[tt];
            result[tt] = cc;

            fill(last.begin(), last.end(), 0);
            ll old = sum;
            sum = 0;
            rep(i, d){
                sum += s[i][result[i]];
                last[result[i]] = i+1;
                rep(j, contest){
                    if(result[i] == j) continue;
                    sum -= c[j]*((i+1)-last[j]);
                }
            }
            if(sum < old){
                result[tt] = bak;
                sum = old;
            }
        }
    }
    for(auto i : result){
        cout << i+1 << endl;
    }
    return 0;
}

Measured memory_bytes: 3636
package main

import (
	"fmt"
)

func dfs(m byte, n int, s []byte) {
	if n == len(s) {
		fmt.Println(string(s))
		return
	}
	for i := byte(0); i < m-'a'+1; i++ {
		s[n] = i + 'a'
		dfs(m, n+1, s)
	}
	s[n] = m + 1
	dfs(m+1, n+1, s)
}

func main() {
	var n int
	fmt.Scan(&n)
	s := make([]byte, n)
	s[0] = 'a'
	dfs('a', 1, s)
}


Measured memory_bytes: 5504
#include <bits/stdc++.h>
 
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
using pll = pair <ll, ll>;
using ld = long double;
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int mod = 1e9 + 7;
const ll inf = 1e9;
const ll INF = 2e18; 
const int N = 6e6 + 66;
const int M = 1015;

int l[N], r[N];

void solve () {
	int n;
	cin >> n;
	for (int i = 1 ; i <= n ; ++ i) cin >> l[i] >> r[i];
	sort (l + 1, l + 1 + n), sort (r + 1, r + 1 + n), reverse (r + 1, r + 1 + n);
	int h = (n + 1) / 2;
	int L = (n % 2 ? l[h] : l[h] + l[h + 1]), R = (n % 2 ? r[h] : r[h] + r[h + 1]);
	cout << R - L + 1;
}

int main (/*UwU*/) {
	ios;
	int tt = 1;
	// cin >> tt;
	while (tt-- || 0) {
		solve();
		cout << "\n";
	}
}

Measured memory_bytes: 5132
from decimal import Decimal
from math import ceil

n = int(input())
ratio = [list(map(int, input().split())) for _ in range(n)]

t_voted = a_voted = 1
for t, a in ratio:
    val = max(ceil(Decimal(t_voted) / Decimal(t)), ceil(Decimal(a_voted) / Decimal(a)))
    t_voted = t * val
    a_voted = a * val

print(t_voted + a_voted)


Measured memory_bytes: 5204