akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll, ll> Pll;
#define debug(var)  do{std::cout << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }
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; }

const int MOD = 1000000007;
const int INF = 1e9;

const int mod = 1000000007;
const int inf = 1e9;
#define PI acos(-1);
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};


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

    auto calc = [&](ll x) {
        ll cnt = 0, tot = 0;
        for(int i = 0; i < n; i++) {
            int j = lower_bound(a.begin(), a.end(), x-a[i]) - a.begin();
            cnt += n-j;
            tot += sum[n] - sum[j];
            tot += a[i] * (n-j);
        }
        return Pll(cnt, tot);
        
    };

    ll l = 0, r = 1e12;
    while(r-l>1) {
        ll mid = (r+l)/2;
        if(calc(mid).first >= m) l = mid;
        else r = mid;
    }
    Pll p = calc(l);
    ll ans = p.second - (p.first - m) * l;
    cout << ans << endl;

}

Measured memory_bytes: 1792
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
P = np.array(lr())
P_min = np.minimum.accumulate(P)

answer = np.count_nonzero(P_min >= P)
print(answer)


Measured memory_bytes: 34140
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>
#define MAXN 1000
#define hlq 1000000007

using namespace std;
int c,d,C[MAXN+8][MAXN+8],dp[MAXN+8][MAXN+8],fac[MAXN+8];
int DP(int l,int r,int res)
{
	if(res==0)
		return 1;
	if(r<l)
		return 0;
	if(~dp[r][res])
		return dp[r][res];
	dp[r][res]=DP(l,r-1,res);
	int i,k=min(d,res/r),f=1,t=res,tmp=0;
	if(c>k)
		return dp[r][res];
	for(i=1;i<c&&t>=r;i++)
	{
		f=(1LL*f*C[t][r])%hlq;
		t-=r;
	}
	for(i=c;i<=k&&t>=r;i++)
	{
		f=(1LL*f*C[t][r])%hlq;
		t-=r;
		tmp=1LL*DP(l,r-1,t)*f%hlq;
		tmp=1LL*tmp*fac[i]%hlq;
		dp[r][res]=(tmp+dp[r][res])%hlq;
	}
	return dp[r][res];
}
int pow_mod(long long a,int x)
{
	long long ans=1;
	while(x)
	{
		if(x&1)
			ans=ans*a%hlq;
		a=a*a%hlq;
		x>>=1;
	}
	return (int)ans;
}
int main()
{
	int n,a,b,i,j;
	scanf("%d%d%d%d%d",&n,&a,&b,&c,&d);
	memset(dp,-1,sizeof(dp));
	for(i=0;i<=n;i++)
	{
		C[i][0]=1;
		for(j=1;j<=i;j++)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%hlq;
	}
	fac[0]=1;
	for(i=1;i<=n;i++)
		fac[i]=1LL*fac[i-1]*pow_mod(i,hlq-2)%hlq;
	printf("%d",DP(a,b,n));
	return 0;
}

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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using WGraph = vector<vector<pair<int, ll>>>;

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

constexpr int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
constexpr int INF = 1e9;
constexpr int MOD = 1e9 + 7;
constexpr long long LINF = 1e18;
constexpr double EPS = 1e-10;
constexpr double PI = M_PI;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i=0; i<n; ++i) {
        cin >> a.at(i);
    }

    ll res = 0;
    int cur = 1;
    for (int i=0; i<n; ++i) {
        if (a.at(i) == cur) {
            ++cur;
        } else {
            res += (a.at(i) - 1) / cur;
            if (cur == 1) ++cur;
        }
    }
    cout << res << '\n';
}

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

    solve();

    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define EPS (1e-10)
#define equals(a,b)(fabs((a)-(b))<EPS)
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;

struct Point {
	double x, y;
	Point(double x = 0, double y = 0) :x(x), y(y) {}
	Point operator*(double a) { return Point(a*x, a*y); }
	Point operator-(Point p) { return Point(x - p.x, y - p.y); }
	Point operator+(Point p) { return Point(x + p.x, y + p.y); }
	double norm() { return x*x + y*y; }
};
typedef vector<Point>Polygon;
struct Segment {
	Point p1, p2;
};
double cross(Point a, Point b) {
	return a.x*b.y - a.y*b.x;
}
double dot(Point a, Point b) {
	return a.x*b.x + a.y*b.y;
}
bool isPrallel(Segment s1, Segment s2) {
	return equals(cross(s1.p2 - s1.p1, s2.p2 - s2.p1), 0.0);
}
bool isOrthogonal(Segment s1, Segment s2) {
	return equals(dot(s1.p2 - s1.p1, s2.p2 - s2.p1), 0.0);
}
int contains(Polygon g, Point p) {
	int n = g.size();
	bool x = false;
	rep(i, n) {
		Point a = g[i] - p, b = g[(i + 1) % n] - p;
		if (abs(cross(a, b)) < EPS&&dot(a, b) < EPS)return 1;
		if (a.y > b.y)swap(a, b);
		if (a.y < EPS&&EPS<b.y&&cross(a, b)>EPS)x = !x;
	}
	return x ? 2 : 0;
}
int ccw(Point p0, Point p1, Point p2) {
	Point a = p1 - p0;
	Point b = p2 - p0;
	if (cross(a, b) > EPS)return 1;
	if (cross(a, b) < -EPS)return -1;
	if (dot(a, b) < -EPS)return 2;
	if (a.norm() < b.norm())return -2;
	return 0;
}
bool intersect(Point p1, Point p2, Point p3, Point p4) {
	return (ccw(p1, p2, p3)*ccw(p1, p2, p4) <= 0 &&
		ccw(p3, p4, p1)*ccw(p3, p4, p2) <= 0);
}
bool intersect(Segment s1, Segment s2) {
	return intersect(s1.p1, s1.p2, s2.p1, s2.p2);
}
Point project(Segment s, Point p) {
	Point base = s.p2 - s.p1;
	double r = dot(p - s.p1, base) / base.norm();
	return s.p1 + base*r;
}
Point reflect(Segment s, Point p) {
	return p + (project(s, p) - p)*2.0;
}
int main() {
	double x1, y1, x2, y2, xq, yq;
	while (~scanf("%lf,%lf,%lf,%lf,%lf,%lf", &x1, &y1, &x2, &y2, &xq, &yq)) {
		Point p = reflect({ {x1,y1},{x2,y2} }, { xq,yq });
		printf("%.6lf %.6lf\n", p.x, p.y);
	}
}

Measured memory_bytes: 3132
import numpy as np


def main():
    h, w = map(int, input().split())
    l = []
    for _ in range(h):
        a = list(input())
        if not '#' in a:
            continue
        l.append(a)
    l = np.array(l)
    m = np.rot90(l)
    n = []
    for a in m:
        if not '#' in a:
            continue
        n.append(a)
    ans = np.array(n)
    ans = np.rot90(ans, -1)
    for i in ans:
        print(*i, sep='')


if __name__ == "__main__":
    main()

Measured memory_bytes: 13896
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout
	cnt := 0

	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
		cnt = 2
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)
	solve(scanner, writer)
	for i := 0; i < cnt; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
	writer.Flush()
}

func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	n := getNextInt(scanner)
	s := make([]int, n)
	for i := 0; i < n; i++ {
		s[i] = getNextInt(scanner)
	}
	q := getNextInt(scanner)
	t := make([]int, q)
	for i := 0; i < q; i++ {
		t[i] = getNextInt(scanner)
	}
	ans := 0

	for i := 0; i < q; i++ {
		l := -1
		r := n
		for l+1 < r {
			m := (l + r) >> 1
			if s[m] < t[i] {
				l = m
				continue
			}
			r = m
		}
		if r == n {
			continue
		}
		if s[r] == t[i] {
			ans++
		}
	}
	fmt.Fprintln(writer, ans)
}



Measured memory_bytes: 4008
#include <iostream>
using namespace std;
int main() {
  int a, b, result;
  cin >> a >> b;
  if(a==b){
      result=a+b;
  }else if(a>b){
      result=2*a-1;
  }else{
      result=2*b-1;
  }
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n; string str; cin>>n>>str;
	for(int i=0,len = str.length();i<len;i++){
		if(i < n)cout<<str[i];
		else{ cout<<"..."; break;}
	}
}

Measured memory_bytes: 3104
// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

ll read() {
	ll X=0,w=1; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
	while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
	return X*w;
}

int main() {
	ll k=read(); int n=50;
	ll c=k/n,r=k%n;
	printf("%d\n",n);
	for (int i=1;i<=n;++i) {
		if (i<=r) printf("%lld ",n-1+c+n-(r-1));
		else printf("%lld ",n-1+c-r);
	}
	return 0;
}

Measured memory_bytes: 3804
while True:
	n = int(input())
	if n == 0: break
	tbl = {}
	for i in range(n):
		a, b = input().split()
		tbl[a] = b
	ans = ''
	m = int(input())
	for i in range(m):
		a = input()[0]
		ans += tbl[a] if a in tbl else a
	print(ans)



Measured memory_bytes: 5716
N = int(input())
evi = [[] for _ in range(N)]
ans = 0
for i in range(N):
    a = int(input())
    for j in range(a):
        x,y = map(int,input().split())
        evi[i].append((x,y))

for i in range(1 << N):
    count = 0
    flag = True
    for j in range(N):
        if (i >> j) & 1 == 1:
            count += 1
            for x,y in evi[j]:
                if (i >> x-1) & 1 != y:
                    flag = False
                    break
            if flag == False:
                break
    if flag:
        if ans < count:
            ans = count
print(ans)




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

using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define REP(i, l, n) for(int i=(l), i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

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;}

char alpha[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

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

int main(){
    int a; cin >> a;
    cout << 3 * a * a << endl;
}

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

int main(){
    int n, k; 
    cin >> n >> k;
    vector<int>a(n);

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

    for(int i=0; i<n-k; i++){
        if(a[i]<a[i+k]){
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 4044
// 2020-08-11 20:39:11
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
using P = pair<int, int>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

const int MX = 100010;
priority_queue<P> que, que2; // d, t
int kind_count, ate_count[MX];
priority_queue<P, vector<P>, greater<P> > ate; // d, t
void answer() {
  int n, k;
  cin >> n >> k;
  rep(i, n) {
    int t, d;
    cin >> t >> d;
    que.emplace(P(d, t));
  }
  ll ans = 0;
  while(!que.empty()) {
    int d, t;
    tie(d, t) = que.top(); que.pop();
    if(ate_count[t] == 0) {
      if(kind_count < k) {
        ans += d;
        ate_count[t]++;
        kind_count++;
        ate.emplace(P(d, t));
      }
    } else {
      que2.emplace(P(d, t));
    }
  }
  int ki = kind_count;
  while(!que2.empty()) {
    int d, t;
    tie(d, t) = que2.top(); que2.pop();
    if(ki < k) {
      ki++;
      ans += d;
      ate_count[t]++;
    } else {
      int d2, t2;
      tie(d2, t2) = ate.top(); ate.pop();
      if(kind_count * 2 - 1 + d2 <= d) {
        ans -= d2;
        ate_count[t2]--;
        kind_count--;
        ans += d;
        ate_count[t]++;
      } else break;
    }
  }
  cout << ans + ll(kind_count) * kind_count << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

Measured memory_bytes: 5620
#include<stdio.h>
int main()
{
  int x1,x2,x3,x4,x5;
  scanf("%d%d%d%d%d",&x1,&x2,&x3,&x4,&x5);
  if(x1==0){
    printf("1");
  }
  else if(x2==0){
    printf("2");
  }
  else if(x3==0){
    printf("3");
  }
  else if(x4==0){
    printf("4");
  }
  else if(x5==0){
    printf("5");
  }
  return 0;
}
  

Measured memory_bytes: 1644
#include<bits/stdc++.h>
#define ll long long
#define pi acos(-1.0)
#define pb push_back
#define vi vector<int>
#define mapii map<int , int>
#define mapci map<char, int>
#define mapsi map<string,int>
#define FOR(i,n) for(int i = 0;i<n;i++)
#define CP(n) cout<<"Case "<<n<<": "
#define fr freopen("input.txt","r",stdin)
#define fw freopen("output.txt","w",stdout)
#define MAX 1000007
#define all(x)(x.begin(),x.end())
#define debug(x,c) cout<<x<<": "<<c<<" ";
#define fast_io ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
int main()
{
	int n;
	cin>>n;
	string s;
	cin>>s;
	if(s.size()>n)
	{
		FOR(i,n)cout<<s[i];
		cout<<"..."<<endl;
	}
	else
		cout<<s<<endl;
	return 0;
}


Measured memory_bytes: 3612
def suffix_array(s):
    def k(a):
        return s[a:]
    
    x = list(range(len(s)))
    x.sort(key=k)
    return x

def main():
    s = input()
    k = int(input())

    a = suffix_array(s)
    v = set()

    for i in a:
        for j in range(i + 1, len(s) + 1):
            v.add(s[i:j])
            if len(v) == k:
                print(s[i:j])
                return

main()

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

int main(){
  string s[3];
  cin >> s[0] >> s[1] >> s[2];
  
  int x = 0, i[3] = {0};
  while(1){
    if(i[x] == s[x].size()){
      char c = 'A' + x;
      cout << c << endl;
      return 0;
    }
    
    if(s[x][i[x]] == 'a'){
      i[x]++;
      x = 0;
    }else if(s[x][i[x]] == 'b'){
      i[x]++;
      x = 1;
    }else if(s[x][i[x]] == 'c'){
      i[x]++;
      x = 2;
    }
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define zero_pad(num) setfill('0') << std::right << setw(num)
const int MOD=1e9+7;
const int INF=1e18;

signed main(){
    map<int,int>memo;
    REP(i,3){
        int a;cin>>a;
        memo[a]++;
    }
    if(memo[5]==2&&memo[7]==1)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}

Measured memory_bytes: 256
n, k = map(int, input().split())
a = [int(_) for _ in input().split()]
a = [0] + a

rep_check = 0
now = 1
place = dict()
place2 = []

if now == a[1]:
    print(1)
    exit()

while now not in place:
    place[now] = 1
    place2.append(now)
    now = a[now]
    rep_check += 1
    if rep_check == k:
        print(now)
        exit()

rep_start = 0
for i in enumerate(place):
    if i[1] == now:
        rep_start = i[0]
        break

k -= rep_start
rep_cnt = len(place) - rep_start

place2 = place2[rep_start:]
k %= rep_cnt
print(place2[k])

Measured memory_bytes: 115496
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <functional>
#include <utility>
#include <queue>
#include <vector>
#include <string>
#include <stack>
#include <map>
#define rep(i,n) for(ll i=0;i<n;i++)
using namespace std;
typedef long long int ll;
const ll  MOD = 1000000007;
typedef pair<ll,ll> P;
const ll INF = 100100100100100100;

ll N,A,B,C,D;
int main(){
  cin >> N >> A >> B >> C >> D;
  ll a = abs(A-B);
  rep(i,N-1){
    if((N-i-1)*C - i*D <= a && (N-i-1)*D - i*C >= a){
      cout << "YES" << endl;
      return 0;
    }
  }
  cout << "NO" << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

#define REP(i,N) for(int i = 0; i < (int)(N); ++i)
#define ALL(v) (v).begin(), (v).end()
template<class T> void pv(T a, T b){for(T i=a;i!=b;++i)cout<<*i<<" ";cout<<endl;}

const int dr[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dc[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

struct State {
	int N;
	char table[5][5];
	bool valid(int r, int c) {
		return 0 <= r && r < N && 0 <= c && c < N;
	}
	void print() {
		REP(i, N) {
			REP(j, N) cout << table[i][j];
			cout << endl;
		}
	}
	bool operator<(const State& t) const {
		REP(i, N) REP(j, N) if( table[i][j] != t.table[i][j] ) return table[i][j] < t.table[i][j];
	}
	
	bool finish() {
		REP(i, N) REP(j, N) if( table[i][j] == '#' ) return 0;
		return 1;
	}
	
	vector<State> get_next() {
		vector<State> res;
		
		int x, y;
		REP(i, N) REP(j, N) if( table[i][j] == '@' ) {
			x = i;
			y = j;
			break;
		}
		
		REP(k, 8) {
			int nx = x + dr[k];
			int ny = y + dc[k];
			if( !valid(nx, ny) || table[nx][ny] == '#' ) continue;
			State t = *this;
			swap( t.table[x][y], t.table[nx][ny] );
			t.trans();
			res.push_back(t);
		}
		return res;
	}
	
	void trans() {
		int next[5][5];
		REP(i, N) REP(j, N) next[i][j] = '.';
		REP(i, N) REP(j, N) {
			if( table[i][j] == '@' ) next[i][j] = '@';
			else if( table[i][j] == '.' ) {
				int adj = count(i, j);
				if( adj == 3 ) next[i][j] = '#';
			}
			else if( table[i][j] == '#') {
				int adj = count(i, j);
				if( adj == 2 || adj == 3 ) 
					next[i][j] = '#';
			}
		}
		REP(i, N) REP(j, N) table[i][j] = next[i][j];
	}
	int count(int x, int y) {
		int cnt = 0;
		REP(k, 8) {
			int nx = x + dr[k];
			int ny = y + dc[k];
			if( valid(nx, ny) && table[nx][ny] != '.' ) cnt++;
		}
		return cnt;
	}
};

int bfs(State s) {
	map<State, int> memo;
	queue<State> q;
	q.push(s);
	memo[s] = 0;
	while( !q.empty() ) {
		s = q.front(); q.pop();
		int cost = memo[s];
		if( s.finish() ) return cost;
		
		vector<State> next = s.get_next();
		for(int i = 0; i < next.size(); i++) {
			if( memo.find(next[i]) == memo.end() ) {
				memo[next[i]] = cost + 1;
				q.push(next[i]);
			}
		}
	}
	return -1;
}

int main() {
	for(int N; scanf("%d", &N) && N; ) {
		State start;
		start.N = N;
		REP(i, N) REP(j, N) {
			scanf(" %c", &start.table[i][j]);
		}
		cout << bfs(start) << endl;
	}
}

Measured memory_bytes: 2424
import java.util.*;

public class Main {
	
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		String in = sc.nextLine();
		String [] array = in.split(" ");
		List<Integer> candyList = new ArrayList<Integer>();
		for (int i = 0; i < array.length; i++) {
			candyList.add(new Integer(array[i]));
		}
		Collections.sort(candyList);
		int a = candyList.get(0).intValue() + candyList.get(1).intValue();
		int b = candyList.get(2).intValue();
		if (a == b) {
			System.out.println("Yes");
		} else {
			System.out.println("No");

		}
	}	
}

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

long long n, a, b;

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

	cin >> n >> a >> b;
	long long kali = n / (a + b);
	long long sisa = n % (a + b);

	cout << kali * a + min(sisa, a) << '\n';

	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("O2")
#pragma GCC ("unroll-loops")
#pragma GCC ("avx,sse,sse2,ssse3,sse4.1,fma,tune=native")
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using vi = vector<int>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1<<18, maxa = 4040, mod = 1e9 + 7;
int nck[2*maxa][maxa];
int n;
inline __attribute__ (( always_inline )) void add(int &a, int b) {
	a += b;
	if(a >= mod) a -= mod;
}
void pre() {
	for(int i = 0; i < 2*maxa; i++)
		for(int j = 0; j <= min(i, maxa-1); j++) {
			if(i == 0 || j == 0) nck[i][j] = 1;
			else nck[i][j] = nck[i-1][j-1], add(nck[i][j], nck[i-1][j]);
		}
}
int val[maxa][maxa], x[maxn], y[maxn];
int main() {
	cin.tie(0)->sync_with_stdio(0);
	pre();
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
		val[maxa/2 - x[i]][maxa/2 - y[i]]++;
	}
	for(int i = 0; i+1 < maxa; i++) {
		for(int j = 0; j+1 < maxa; j++) {
			add(val[i][j+1], val[i][j]);
			add(val[i+1][j], val[i][j]);
		}
	}
	int ans = 0;
	for(int i = 0; i < n; i++)
		add(ans, val[maxa/2 + x[i]][maxa/2 + y[i]]);
	for(int i = 0; i < n; i++)
		add(ans, mod - nck[x[i]+x[i]+y[i]+y[i]][x[i]+x[i]]);
	ans = ans * 1ll * ((mod+1)/2) % mod;
	cout << ans;
}


Measured memory_bytes: 193152
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

int main() {
    string dat[3];
    for (int i = 0; i < 3; i++) {
        cin >> dat[i];
    }

    cout << dat[0][0] << dat[1][1] << dat[2][2] << endl;
    return 0;
}


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

int n ;
const int nmax = 23 ;
int mat[nmax][nmax];
const int nn = (1<<nmax);
int dp[nmax][nn];
const int mod = 1e9+7;
ll cal( int id , int mask){
  //cout << id << " " << mask << "\n";
  if(id==n){
    return  1;
  }
  if(dp[id][mask]!=-1) return dp[id][mask] ;
  ll res = 0 ;
  for( int i = 0 ; i < n ;i++){
    if(mat[id][i]==1 && (mask&(1<<i))==0){
        res+= cal(id+1,(mask|(1<<i)));
        if(res>=mod) res-=mod;
    }
  }
  dp[id][mask] = res;
  return res;
}
/////////////////////////////////////////////////////
void solve(int no){
  cin >> n;

  for( int i = 0 ; i < n ; i++) for( int j = 0 ; j < n ; j++) cin >> mat[i][j] ;
  memset(dp,-1,sizeof dp);
  cout << cal(0,0)%mod;
}
int main()
 {
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll q=1;
    //cin >> q ;
    for( int i = 1 ; i <= q ; i++)
      solve(i);
}
// aaaaaa
// aa
// 011111
// 012345

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

int main()
{
  int N;
  cin >> N;
  int ans = 0;
  for(int i = 1; i <= N; i++) {
    if (i % 2 == 0) {
      continue;
    }
    int count = 0;
    for(int j = 1; j <= i; j++) {
      if(i % j == 0) {
        count++;
      }
    }
    if (count == 8) {
      ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T>
using vec = std::vector<T>;

int main() {
    double pi = 3.1415926535897932384626;

    double A,B;
    double H,M;
    cin >> A >> B >> H >> M;
    double S = H*30.0+M/2;
    double L = M*6;
    double diff = S-L;

    double p = (double)diff*pi/180.0;

    double ans = A*A+B*B-2.0*A*B*cos(p);

    cout << fixed << setprecision(15);
    cout << sqrt(ans) << endl;
}


Measured memory_bytes: 4212
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <list>
#include <stack>
#include <string>
#include <functional>
#include <numeric>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
using namespace std;
#define INT_MAX 2147483647
#define INT_MIN (-2147483647 - 1)
#define INF (int)1e8
#define _INF (int)-1e8
#define INFLL (long long)1e14
#define _INFLL (long long)-1e14
#define Loop(i, n) for(int i = 0; i < (int)n; i++)
#define Loop1(i, n) for(int i = 1; i <= (int)n; i++)
#define Loopr(i, n) for(int i = (int)n - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = (int)n; i >= 1; i--)
#define bitmanip(m,val) static_cast<bitset<(int)m>>(val)
typedef long long int ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<ll, int> P;

//素数の是非を判定する
bool judge_prime_numbers(ll n) {
	if (n == 1) return false;
	if (n == 2) return true;
	else if (n % 2 == 0) return false;
	else {
		bool judge = true;
		for (int i = 3; i <= sqrt(n); i = i + 2) {
			if (n%i == 0) {
				judge = false;
				break;
			}
		}
		return judge;
	}
}

//nまでの素数を作る
vll make_prime_numbers(ll n) {
	vll ret;
	Loop1(i, n) {
		if (judge_prime_numbers(i)) ret.push_back(i);
	}
	return ret;
}


int main() {
	int n; cin >> n;
	vll a = make_prime_numbers(n);
	vi b(a.size(), 0);
	Loop1(i, n) {
		int k = i;
		int j = 0;
		while (k > 1) {
			if (k%a[j] == 0) {
				k /= a[j];
				b[j]++;
			}
			else j++;
		}
	}
	ll ans = 1;
	Loop(i, b.size()) {
		ans = ans*(b[i] + 1) % (int)(1e9 + 7);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 384
#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.at(i);
  int a=1;
  for(int i=0;i<N;i++){
  if(A.at(i)==a)
    a++;
  }if(a==1)
    cout<<-1<<endl;
  else
    cout<<N+1-a<<endl;
    return 0;
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k,t,u,v,l;
  cin>>n>>k>>t>>u>>v>>l;
  int i,j;
  set<int> s;
  for(i=0;i<n;i++){
    cin >> j;
    s.insert(j);
  }
  int p=0,h=0,x=0;
  double ans=0;
  for(i=1;i<=l;i++){
    if(x==0){
      if(h>0){
	x=v*t-1;h--;
	ans+=1.0/v;
      }else ans+=1.0/u;
    }else{
      ans+=1.0/v;
      x--;
    }
    if(s.find(i)!=s.end())
      if(h<k) h++;
      else x=v*t;
  }
  printf("%.9lf\n",ans);
  return 0;
}

Measured memory_bytes: 1232
import java.util.*;
public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int x = sc.nextInt();
		int xx = x;

		int a_5 = 0;
		int b_5 = 0;
		int a = 0;
		int b = 0;

		for (int i = -120;i<=120 ;i++ ) {
			for (int j = 120;j>=-120 ;j-- ) {
				a = i;
				b = j;
				if (Math.pow(a,5)-Math.pow(b,5)==x) {
					System.out.println(a+" "+b);
					System.exit(0);
				}
			}

		}

	}
}


Measured memory_bytes: 38804
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_CITY_MAX		100000									// 最大市数

// 内部構造体 - 市情報
typedef struct City {
	int miNo;													// 配列番号 0～
	int miPref;													// 県
	int miYear;													// 誕生年
} City;

// 内部変数
static FILE *szpFpI;											// 入力
static City sz1City[D_CITY_MAX + 5];							// 市
static int siCCnt;												// 市数

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpA;
#endif

// ソート関数 - 県昇順・誕生年昇順
int
fSortFncPY(
	const void *pzpVal1			// <I> 値１
	, const void *pzpVal2		// <I> 値２
)
{
	City *lzpVal1 = (City *)pzpVal1;
	City *lzpVal2 = (City *)pzpVal2;

	// 県昇順
	if (lzpVal1->miPref > lzpVal2->miPref) {
		return(1);
	}
	else if (lzpVal1->miPref < lzpVal2->miPref) {
		return(-1);
	}

	// 誕生年昇順
	if (lzpVal1->miYear > lzpVal2->miYear) {
		return(1);
	}
	else if (lzpVal1->miYear < lzpVal2->miYear) {
		return(-1);
	}

	return 0;
}

// ソート関数 - 配列番号昇順
int
fSortFncN(
	const void *pzpVal1			// <I> 値１
	, const void *pzpVal2		// <I> 値２
)
{
	City *lzpVal1 = (City *)pzpVal1;
	City *lzpVal2 = (City *)pzpVal2;

	// 配列番号昇順
	if (lzpVal1->miNo > lzpVal2->miNo) {
		return(1);
	}
	else if (lzpVal1->miNo < lzpVal2->miNo) {
		return(-1);
	}

	return 0;
}

// 実行メイン
int
fMain(
	int piTNo					// <I> テスト番号 1～
)
{
	int i, liWork;
	char lc1Buf[1024], lc1Out[1024];

	// データ - 初期化
	memset(sz1City, 0, sizeof(sz1City));						// 市

	// 入力 - セット
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", piTNo);
	szpFpI = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", piTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#else
	szpFpI = stdin;
#endif

	// 県数・市数 - 取得
	fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
	sscanf(lc1Buf, "%d%d", &liWork, &siCCnt);

	// 市 - 取得
	for (i = 1; i <= siCCnt; i++) {
		fgets(lc1Buf, sizeof(lc1Buf), szpFpI);
		sscanf(lc1Buf, "%d%d", &sz1City[i].miPref, &sz1City[i].miYear);
		sz1City[i].miNo = i;
	}

	// 市 - ソート
	qsort(&sz1City[1], siCCnt, sizeof(City), fSortFncPY);

	// 誕生年 - 更新
	for (i = 1; i <= siCCnt; i++) {
		if (sz1City[i].miPref == sz1City[i - 1].miPref) {		// 県が一致
			sz1City[i].miYear = sz1City[i - 1].miYear + 1;
		}
		else {													// 県が不一致
			sz1City[i].miYear = 1;
		}
	}

	// 市 - ソート
	qsort(&sz1City[1], siCCnt, sizeof(City), fSortFncN);

	// 結果
	for (i = 1; i <= siCCnt; i++) {
		sprintf(lc1Out, "%06d%06d\n", sz1City[i].miPref, sz1City[i].miYear);
#ifdef D_TEST
		fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
		if (strcmp(lc1Buf, lc1Out)) {
			siRes = -1;
		}
#else
		printf("%s", lc1Out);
#endif
	}

	// 残データ有無
#ifdef D_TEST
	lc1Buf[0] = '\0';
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, "")) {
		siRes = -1;
	}
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpI);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", piTNo);
	}
	else {
		printf("NG %d\n", piTNo);
	}
#endif

	return 0;
}

int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		fMain(i);
	}
#else
	fMain(0);
#endif

	return 0;
}



Measured memory_bytes: 3820
// E.

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

using namespace std;

int main(int argc, char* argv[]) {
#ifdef _MSC_VER
	while (true)
#endif
	{
		string a, b, c;
		getline(cin, a);
		getline(cin, b);
		getline(cin, c);
		if (a.empty() || b.empty() || c.empty()) return 0;
		vector<bool> ab(20000), bc(20000), ca(20000);
		auto fill = [](const string& a, const string& b, vector<bool> &f) {
			for (size_t i = 0; i < a.length(); ++i) {
				for (size_t j = 0; j < b.length(); ++j) {
					if (!(a[i] == '?' || b[j] == '?' || a[i] == b[j])) {
						f[10000 + i - j] = true;
					}
				}
			}
		};
		fill(a, b, ab);
		fill(b, c, bc);
		fill(c, a, ca);
		int ans = 1 << 30;
		for (int i = -4000; i <= 4000; ++i) {
			for (int j = -4000; j <= 4000; ++j) {
				if (!ab[10000 + i] && !bc[10000 - i + j] && !ca[10000 - j]) {
					int left = min({ 0, i, j });
					int right = max({ (int)a.length(), i + (int)b.length(), j + (int)c.length() });
					ans = min(ans, right - left);
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 256
class UnionFind:
    def __init__(self, n: int):
        self.n = n
        self.parents = [-1] * n
    
    def find(self, x: int):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x: int, y: int):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        if self.parents[y] < self.parents[x]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x: int):
        return -self.parents[self.find(x)]
    
    def same(self, x: int, y: int):
        return self.find(x) == self.find(y)
    
    def members(self, x: int):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    
    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def solve():
    N, M = map(int, input().split())
    p = list(map(lambda a: int(a) - 1, input().split()))
    uf_tree = UnionFind(N)
    for _ in range(M):
        x, y = map(lambda a: int(a) - 1, input().split())
        uf_tree.union(x, y)
    
    ans = 0
    for pi in p:
        if uf_tree.same(pi, p[pi]):
            ans += 1
    print(ans)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 13940
import collections
n = int(input())
v = list(map(int, input().split()))

v_index_odds = []
v_index_evens = []

for i in range(0,n,2):
    v_index_evens.append(v[i])
    v_index_odds.append(v[i+1])

evens_counter = collections.Counter(v_index_evens).most_common()
odds_counter = collections.Counter(v_index_odds).most_common()

if evens_counter[0][0] != odds_counter[0][0]:
    ans = n - evens_counter[0][1] - odds_counter[0][1]
else:
    if n - evens_counter[0][1] - odds_counter[0][1] == 0:
        ans = n // 2
    else:
        if n // 2 - evens_counter[0][1] == 0:
            ans = n // 2 - evens_counter[1][1]
        elif n // 2 - odds_counter[0][1] == 0:
            ans = n // 2 - evens_counter[1][1]
        else:
            a = n - evens_counter[0][1] - odds_counter[1][1]
            b = n - evens_counter[1][1] - odds_counter[0][1]
            ans = min(a, b)
print(ans)

Measured memory_bytes: 21084
#include<bits/stdc++.h>
#define lint long long int
#define rep(i,n) for(int i=0;i<int(n);i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define arep(i,a,n) for(int i=a;i<n;i++)
#define sort(a) sort(a.begin(),a.end())
#define reverse(a) reverse(a.begin(),a.end())
#define fill(a,x) fill(a.begin(),a.end(),x)
#define eb(data) emplace_back(data)
#define pb(data) emplace_back(data)
#define mp make_pair
#define ALNUM 26
#define vint vector<int>
#define vlint vector<lint>
#define F first
#define S second
#define ALL(data) data.begin(),data.end()
#define GEts(s) getline(cin,s);
#define UNIQUE(vec) vec.erase(unique(vec.begin(), vec.end()), vec.end())

using namespace std;
template<typename Rast>inline void out(Rast rast){cout<<rast<<"\n";return;}
template<typename Rast>inline void in(Rast& rast){cin>>rast;return;}
template<typename T>istream& operator >> (istream& is, vector<T>& vec){for(T& x: vec) is >> x;return is;}
template<typename First, typename... Rest>void in(First& first, Rest&... rest){cin >> first;in(rest...);return;}
template<typename First, typename... Rest>void out(First first, Rest... rest){cout << first<<" ";out(rest...);return;}
template<typename T>T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template<typename T1,typename T2>bool chmax(T1& a,T2 b){if(a<b){a=b;return true;}else{return false;}}
template<typename T1,typename T2>bool chmin(T1& a,T2 b){if(a>b){a=b;return true;}else{return false;}}
template<typename T>T lcm(T a, T b){return a * b / gcd(a, b);}
static const double pi = 3.141592653589793;
lint modpow(lint a,lint n,lint p){if (n==0)return 1%p; if(n==1)return a%p;if(n%2==1)return (a*modpow(a,n-1,p))%p;lint t=modpow(a,n/2,p);return (t*t)%p;}//a^n%p
lint MOD=pow(10,9)+7;
//lint MOD=998244353;
lint inf=pow(2,50);
int intinf=pow(2,30);
/**int dirx[]={1,0};int diry[]={0,1};//*///右、下
/**int dirx[]={0,1,0,-1};int diry[]={-1,0,1,0};//*///四方位
/**int dirx[]={-1,0,1,1,1,0,-1,-1};int diry[]={-1,-1,-1,0,1,1,1,0};//*///八方位


class unionfind{
public:
	vector<int> table;
	void init(int size){
		table.resize(size);
		rep(i,size)table[i]=i;
	};
	int root(int index){
		if(table[index]==index)return index;
		else{
			int hoge=root(table[index]);
			table[index]=hoge;
			return hoge;
		}
	};
	bool same(int x,int y){
		return(root(x)==root(y));
	};
	int marge(int x,int y){
		int yroot=root(y);
		int xroot=root(x);
		if(xroot==yroot)return 0;
		table[yroot]=xroot;
		return 0;
	}
};

int main(){
	cin.tie(0);ios::sync_with_stdio(false);cout<<std::fixed<<std::setprecision(19);
	lint n;
	in(n);
	lint ans=n-1;
	arep(i,2,2000000)if(n%i==0)chmin(ans,i-2+(n/i));

	out(ans);
	return 0;
}


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

int main () {
  string S;
  cin >> S;
  int s = S.size();
  string ans = "AC";
  if (S.at(0) != 'A') ans = "WA";
  int cnt = 0;
  for (int i = 1; i < s; i++) {
    if (isupper(S.at(i))) {
      if (i == 1 || i == s-1 || S.at(i) != 'C') ans = "WA";
      else cnt++;
    }
  }
  if (cnt != 1) ans = "WA";
  cout << ans << endl;
}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define each(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define all(v) v.begin(), v.end()
#define mset(a, n) memset(a, n, sizeof(a))

typedef long long ll;

const int INF = 1000000000;
const int MOD = 1000000007;

int main () {
	int n;
	cin >> n;
	
	if (n == 0) { cout << 0 << endl; return 0;}
	
	int i = 0;
	string s;
	while (n) {
		if (n % 2) {
			s += '1';
			if (i % 2) ++n;
			else --n;
		} else {
			s += '0';
		}
		n /= 2;
		++i;
	}
	
	reverse(s.begin(), s.end());
	cout << s << endl;
}



Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main(void){
    int n;
    while(1){
        cin>>n;
        if(!n)break;
        int a[40100],b[40100];
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        for(int i=0;i<n;i++){
            cin>>b[i];
        }
        sort(a,a+n),reverse(a,a+n);
        sort(b,b+n),reverse(b,b+n);
        int win=0,ans=0;
        int ai=0,bi=0;
        for(int i=0;i<n-1;i++){
            if(a[ai]>b[bi])ai++,win++;
            else if(a[ai]<b[bi])ai++,bi++;
            else ai++,bi++;
            if(win>(i+1)/2){
                ans=i+1;
                break;
            }
        }
        !ans ? cout<<"NA"<<endl : cout<<ans<<endl;
    }
    return 0;
}

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

int main(){
    int x[3000],y[3000];
    
    int n=0;
    while(true){
        cin >> x[n] >> y[n];
        
        if(x[n] == 0 && y[n] == 0) break;
        
        ++n;
    }
    
    for(int i=0;i<n;++i){
       if(x[i] > y[i]) cout << y[i]<<" "<< x[i] << endl;
       else cout << x[i] <<" " << y[i] << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3036
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.IntStream;

/**
 * 解説どおりに作成したソースコード
 * 
 * https://atcoder.jp/contests/abc091/submissions/5275478 にも参考
 */
public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt();
			int[] a = new int[n], b = new int[n];
			int[] na = new int[n], nb = new int[n];
			IntStream.range(0, n).forEach(i -> a[i] = scanner.nextInt());
			IntStream.range(0, n).forEach(i -> b[i] = scanner.nextInt());
			int answer = 0;
			for (int k = 0; k < 30; k++) {
				int mask = (1 << (k + 1)) - 1;
				for (int i = 0; i < n; i++) {
					na[i] = a[i] & mask;
					nb[i] = b[i] & mask;
				}
				Arrays.sort(nb);
				int count = 0;
				for (int i = 0; i < n; i++) {
					count += lowerBound(nb, (2 << k) - na[i]) - lowerBound(nb, (1 << k) - na[i]);
					count += n - lowerBound(nb, (3 << k) - na[i]);
					count &= 1;
				}
				if (1 == (count & 1)) {
					answer |= 1 << k;
				}
			}
			System.out.println(answer);
		}
	}

	/**
	 * 配列aにおける値vのlowerBoundを計算する
	 * 
	 * @param a
	 * @param v
	 * @return 配列aにおける値vのlowerBound
	 */
	private static int lowerBound(int a[], int v) {
		int l = 0, r = a.length - 1;
		while (r - l >= 0) {
			int c = (l + r) / 2;
			if (v <= a[c]) {
				r = c - 1;
			} else {
				l = c + 1;
			}
		}
		return l;
	}
}


Measured memory_bytes: 106200
#include<bits/stdc++.h>
using namespace std;
 
using ll = long long;
using pll = pair<ll, ll>;
#define all(x) (x).begin(), (x).end()
#define call(x) (x).cbegin(), (x).cend()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define sz(x) ((x).size())
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define rep(i, a, b) for(ll i = ll(a); i < ll(b); i++)
const double PI = acos(-1);
const int mod = 1e9+7;
const long long INF = (1LL << 60);
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a / gcd(a,b) * b;}
ll stringcount(string s, char c){return count(s.cbegin(), s.cend(), c);}
bool isInteger(double x){return floor(x) == x;}
ll ceil(ll a, ll b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmax(T &a, const T &b){ if(a < b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b){ if(a > b){ a=b; return 1; } return 0; }



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

  ll n, a, b;
  cin >> n >> a >> b;
  vector<ll> x(n);
  rep(i, 0, n) cin >> x[i];

  ll now = x[0];
  ll ans = 0;
  rep(i, 1, n){
    ll dis = x[i] - now;
    now = x[i];
    if(dis*a > b){
      ans += b;
    }else{
      ans += dis*a;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3988
#include <bits/stdc++.h>
typedef long long ll;
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 invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)
const int MOD=1e9+7;
 
int main() {
    ll n;
    cin >> n;
    ll a,total=0;
    vector<ll> b;
    b.push_back(total);
    rep(i,n) {
        cin >> a;
        total+=a;
        b.push_back(total);
    }
    sort(b.begin(),b.end());
    ll ans=0;
    ll cnt=0;
    rep(i,n) {
        if (b[i]==b[i+1]) {
            ++cnt;
        } else {
            ++cnt;
            ans+=cnt*(cnt-1)/2;
            cnt=0;
        }
    }
    ++cnt;
    ans+=cnt*(cnt-1)/2;
    cout << ans << endl;
}

Measured memory_bytes: 2420
import itertools
N,M,Q=map(int,input().split())
a=[0 for i in range(Q)]
b=[0 for i in range(Q)]
c=[0 for i in range(Q)]
d=[0 for i in range(Q)]
for i in range(Q):
    a[i],b[i],c[i],d[i]=map(int,input().split())
    b[i]-=1;a[i]-=1
ans=0
for seq in itertools.combinations_with_replacement(range(M),N):
    tmp=0
    for i in range(Q):
        if seq[b[i]]-seq[a[i]]==c[i]:
            tmp+=d[i]
    ans=max(ans,tmp)
print(ans)


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

using namespace std;

char alphas[26] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};

int main(){
    int N,Q;
    cin >> N;
    string S;
    cin >> S;
    cin >> Q;

    vector<vector<int>> sum(N+1,vector<int>(26,0));
    vector<pair<char,char>> change;
    vector<int> changenum;

    for(int i=0;i<N;i++){
        sum[i+1] = sum[i];
        sum[i+1][S[i]-'a']++;
    }

    for(int i=0;i<Q;i++){
        int num;
        cin >> num;

        if(num==1){

            int iq;
            char c;
            cin >> iq >> c;
            changenum.push_back(iq);
            change.push_back({S[iq-1],c});
            S[iq-1] = c;

        }else{

            int ans = 0,l,q;
            vector<int> anssum(26,0);
            cin >> l >> q;

            for(int j=0;j<26;j++){
                anssum[j] = sum[q][j]-sum[l-1][j];
            }

            for(int j=0;j<change.size();j++){
                if(l<=changenum[j] && changenum[j]<=q){
                    anssum[change[j].first-'a']--;
                    anssum[change[j].second-'a']++;
                }
            }

            for(int j=0;j<26;j++){
                if(0<anssum[j]){
                    ans++;
                }
            }

            cout << ans << endl;
        }
    }
}

Measured memory_bytes: 67332
import sys
def main():
    def input():
        return sys.stdin.readline()[:-1]
    K, A, B = map(int,input().split())
    if A+2 >= B:
        print(K+1)
    else:
        t = (K-A+1)//2
        if (K-A+1)%2 == 0:
            print(max(K+1, A+(B-A)*t))
        else:
            print(max(K+1, 1+A+(B-A)*t))

if __name__ == '__main__':
    main()


Measured memory_bytes: 38256
#include<bits/stdc++.h>
using namespace std;
// make pair, tuple
// __gcd(int, int)
// bool isPrime(int n){
//       if(n <= 1)return false;
//       if(n <= 3)return true;
//       if(n % 2 == 0 || n % 3 == 0)return false;
//       for(int i = 5;i * i <= n;i += 6){
//             if(n % i == 0 || n % (i + 2) == 0)return false;
//       }
//       return true;
// }
// int countSubString(string s, string temp){
//       int ans = 0;
//       size_t f = s.find(temp);
//       while(f != string::npos){
//             ans++;
//             f = s.find(temp, f + 1);
//       }
//       return ans;
// }

int main(){
    long long int n,s;cin >> n >> s;
    if(s >= n)return cout << 0, 0;
    vector<long long int> v;
    for(int i = 0;i < n;i++){
        int t;cin >> t;
        v.push_back(t);
    }
    sort(v.rbegin(), v.rend());
    long long int ans = 0;
    for(int i = s;i < n;i++){
        ans += v[i];
    }
    cout << ans;
}

Measured memory_bytes: 2420
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

char st[3];
int check[3];

int main(void) {
	int n, m;
	scanf("%d %d", &n, &m);

	if (n != 1) {
		st[0] = '1';
	}
	else st[0] = '0';
	st[1] = '0';
	st[2] = '0';
	for (int i = 1; i <= m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		if (check[a - 1] == 0) {
			check[a - 1] = 1;
			st[a - 1] = '0' + b;
		}
		else if (st[a - 1] == '0' + b) {
			continue;
		}
		else {
			printf("-1");
			return 0;
		}
	}
	
	
	if (n > 1 && st[0] == '0') printf("-1");
	else {
		for (int i = 0; i < n; i++) {
			printf("%c", st[i]);
		}
	}

	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using Map = map<ll,ll>;
using T = tuple<ll,ll,ll>;
using vvl = vector<vector<ll>>;
#define all(v) v.begin(), v.end()
#define print(v) cout<<v<<endl
#define first(v) get<0>(v)
#define second(v) get<1>(v)
#define third(v) get<2>(v)
template <typename T> bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template <typename T> bool chmin(T &a, const T &b){if (a>b){a=b;return 1;}return 0;}
const ll INF=1LL<<60;
const ll MOD=1000000007;



int main(){
    ll N;
    cin >> N;
    vector<ll> X(N,0);
    for(ll i=0;i<N;i++){
        cin>>X[i]
    ;}
    vl Y=X;
    sort(Y.begin(), Y.end());
    ll z=Y[N/2-1];
    ll w=Y[N/2];
    for(ll i=0;i<N;i++){
        if(X[i]>=w)print(z);
        else print(w);
    ;}
    return 0;
}


Measured memory_bytes: 5376
#include <cstdio>
#include <complex>
using namespace std;

typedef complex<double> Point;

#define X real()
#define Y imag()

Point ps[4];

double dot(Point a, Point b) {
  return (conj(a)*b).X;
}

double cross(Point a, Point b) {
  return (conj(a)*b).Y;
}

bool ccw(Point a, Point b, Point c) {
  return cross(c-b, a-b) > 0.0;
}

int main() {
  while (1) {
    for (int i=0; i<4; i++) {
      double x, y;
      if (scanf("%lf,%lf", &x, &y) != 2) return 0;
      getchar();
      ps[i] = Point(x, y);
    }
  
    bool base = ccw(ps[0], ps[1], ps[2]);
    bool is_convex = true;
    for (int i=1; i<4; i++) {
      is_convex &= (base == ccw(ps[i], ps[(i+1)%4], ps[(i+2)%4]));
    }

    if (is_convex) puts("YES");
    else puts("NO");
  }
}

Measured memory_bytes: 2632