akhauriyash/Code-Regression huggingface dataset:
#場合分け尺取り


n,k=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
nc=0
zc=0
pc=0
for i in range(n):
  if arr[i]<0:
    nc+=1
  elif arr[i]==0:
    zc+=1
  else:
    pc+=1
ncc=nc*pc
zcc=zc*(nc+pc)+(zc*(zc-1))//2
pcc=(nc*(nc-1))//2+(pc*(pc-1))//2
if k<=ncc:
  arr1=[]
  arr2=[]
  for i in range(n):
    if arr[i]<0:
      arr1.append(-arr[i])
    elif arr[i]>0:
      arr2.append(arr[i])
  arr1=arr1[::-1]
  c1=len(arr1)
  c2=len(arr2)
  l=0
  r=10**18+1
  k=ncc-k
  while r-l!=1:
    mid=(l+r)//2
    cnt=0
    pos=c2-1
    for i in range(c1):
      while pos!=-1:
        if arr2[pos]>mid//arr1[i]:
          pos-=1
        else:
          break        
      cnt+=pos+1
    if cnt>k:
      r=mid
    else:
      l=mid
  print(-r)
elif k<=(ncc+zcc):
  print(0)
else:
  arr1=[]
  arr2=[]
  for i in range(n):
    if arr[i]<0:
      arr1.append(-arr[i])
    elif arr[i]>0:
      arr2.append(arr[i])
  arr1=arr1[::-1]
  c1=len(arr1)
  c2=len(arr2)
  l=0
  r=10**18+1
  k-=(ncc+zcc)
  while r-l!=1:
    mid=(l+r)//2
    cnt1=0
    pos1=c1-1
    for i in range(c1):
      tmp=0
      while pos1!=-1:
        if arr1[pos1]>mid//arr1[i]:
          pos1-=1
        else:
          break
      tmp+=pos1+1
      if arr1[i]**2<mid:
        tmp-=1
      cnt1+=tmp
    cnt1=cnt1//2
    cnt2=0
    pos2=c2-1
    for i in range(c2):
      tmp=0
      while pos2!=-1:
        if arr2[pos2]>mid//arr2[i]:
          pos2-=1
        else:
          break
      tmp+=pos2+1
      if arr2[i]**2<mid:
        tmp-=1
      cnt2+=tmp
    cnt2=cnt2//2
    cnt=cnt1+cnt2
    if cnt>=k:
      r=mid
    else:
      l=mid
  print(r)



Measured memory_bytes: 101588
#include <stdio.h>
#include <limits.h>

#define INF INT_MAX/2

int main(void) {
	int n, i, p;
	scanf("%d", &n);
	int min = INF;
	int count = 0;
	for(i = 0; i < n; i++) {
		scanf("%d", &p);
		if(p < min) {
			min = p;
			count++;
		}
	}
	printf("%d\n", count);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define reps(i, a, n) for (int i = (a); i < (n); ++i)
#define rep(i, n) reps(i, 0, n)
#define deps(i, a, n) for (int i = (a); i >= (n); --i)
#define dep(i, n) deps(i, n, 0)
#define inf 2147483647
#define int long long

signed main(void)
{
	string s, t; cin >> s; cin >> t;
	int sl, tl; sl = s.length(); tl = t.length();
	int n = sl - tl + 1;
	int ans = inf;
	rep (i, n)
	{
		int ans2 = 0;
		rep (j, tl)
		{
			if (s[j + i] != t[j]) ans2++;
		}
		if (ans2 < ans) ans = ans2;
	}
	cout << ans << endl;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
#include<string>
#include<cmath>
#include<iomanip>
#define fast ios_base::sync_with_stdio(0)
#define fast_in cin.tie(0)
#define fast_out cout.tie(0)
#define ll long long
#define MAX 1000000
#define MAX_MAX 10000000000
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
using namespace std;

ll knapsack(ll W,ll val[],ll wt[],ll N)
{
    ll k[N+1][W+1];
    for(ll i=0;i<=N;i++)
    {
        for(ll j=0;j<=W;j++)
        {
            if(i==0||j==0)
                k[i][j]=0;
            else if(wt[i-1]<=j)
                k[i][j]=max(val[i-1]+k[i-1][j-wt[i-1]],k[i-1][j]);
            else
                k[i][j]=k[i-1][j];
        }
    }
    return k[N][W];
}

int main()
{
    fast;fast_in;fast_out;
    ll N,W;
    cin>>N>>W;
    ll val[N],wt[N];
    for(ll i=0;i<N;i++)
        cin>>wt[i]>>val[i];
    cout<<knapsack(W,val,wt,N)<<endl;
    return 0;
}


Measured memory_bytes: 79232
(defun prime-factorization (n)
  (let ((ans '()))
    (labels ((divide (m i c)
		     (unless (zerop (rem m i))
		       (return-from divide (values m (cons i c))))
		     (divide (/ m i) i (1+ c)))
	     (take-apart (m i)
			 (when (= m 1)
			   (return-from take-apart ans))

			 (when (< (sqrt m) i)
			   (return-from take-apart
			     (setf ans (append ans (list (cons m 1))))))

			 (if (zerop (rem m i))
			    (multiple-value-bind (m2 part) (divide m i 0)
			      (setf ans (append ans (list part)))
			      (take-apart m2 (1+ i)))
			    (take-apart m (1+ i)))))
      (take-apart n 2)
      ans)))

(defun abc142d ()
  (let* ((a (read))
	 (b (read)))
    (format t "~a~%"
	    (1+
	     (length
	       (intersection
		 (mapcar #'car (prime-factorization a))
		 (mapcar #'car (prime-factorization b))))))))

(abc142d)

Measured memory_bytes: 15844
#include <bits/stdc++.h>
#define MAX 100005
#define ll long long
#define upperlimit 1000100
#define INF 1e18
#define eps 1e-8
#define endl '\n'
#define pcc pair<char,char>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define tr(container,it) for(typeof(container.begin()) it=container.begin();it!=container.end();it++)
#define MOD 1000000007
#define slld(t) scanf("%lld",&t)
#define sd(t) scanf("%d",&t)
#define pd(t) printf("%d\n",t)
#define plld(t) printf("%lld\n",t)
#define mp(a,b) make_pair(a,b)
#define FF first
#define SS second
#define pb(x) push_back(x)
#define vi vector<int>
#define clr(a) memset(a,0,sizeof(a))
#define debug(a) printf("check%d\n",a)
#define csl ios::sync_with_stdio(false);cin.tie(0);
#define fi(a,b,c) for(int i=a;i<b;i=i+c)
#define fj(a,b,c) for(int j=a;j<b;j+=c)
using namespace std;
 
ll gcd(ll n1,ll n2) {
	if(n1%n2==0)return n2;
	return gcd(n2,n1%n2);
}
ll powmod(ll base,ll exponent) {
	ll ans=1;
	while(exponent){
		if(exponent&1)ans=(ans*base)%MOD;
		base=(base*base)%MOD;
		exponent/=2;
	}
	return ans;
}
ll max(ll a,ll b,ll c) {
	return max(a,max(b,c));
}
int max(int a,int b,int c) {
	return max(a,max(b,c));
}

int main()
{
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	cout<<max(a*c, max(a*d, b*c, b*d));
}

Measured memory_bytes: 3620
#include <stdio.h>

int main () {
  double r;
  double s;
  double l;
  double p;
  scanf("%lf", &r);
  p = 3.14159265358979323846;
  l = 2 * p * r;
  s = p * r * r;
  
  printf("%f %f\n", s , l);
  return 0;
}

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

public static class Program
{
    public static void Main(string[] args)
    {
        var s = Console.ReadLine().ToCharArray();
        Console.WriteLine(s[2] == s[3] && s[4] == s[5] ? "Yes" : "No");
    }
}

Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 int a,b;
  cin >> a >> b;
  //cout << a << b << endl;
  
  int x = a * b;
  if(x%2 == 0){
    cout << "Even" << endl;
  }else{
    cout << "Odd" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define _69e27 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 1e2+5, M=1e5+5, oo=0x3f3f3f3f, mod = 1e9+7;

int n, w, arrw[N], arrv[N], mem[N][M], ans;

int solve(int i, int v){
    if(v == 0) return 0;
   if(i == n)
        return oo;
    if(mem[i][v] != -1)
        return mem[i][v];
   int op1 = solve(i+1, v);
   int op2 = oo;
   if(arrv[i] <= v)
        op2 = solve(i+1, v-arrv[i])+arrw[i];
   return mem[i][v] = min(op1, op2);
 }

int main()
{
    _69e27
    memset(mem, -1, sizeof mem);
    cin >> n >> w;
    for(int i=0; i<n; i++)
        cin >> arrw[i] >> arrv[i];
    for(int i=1; i<=100000; i++){
        if(solve(0, i) <= w)
            ans = i;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 41344
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());

		int W=Integer.parseInt(st.nextToken());
		int H=Integer.parseInt(st.nextToken());
		int x=Integer.parseInt(st.nextToken());
		int y=Integer.parseInt(st.nextToken());
		int r=Integer.parseInt(st.nextToken());

		int maxx=W-r;
		int maxy=H-r;

		//判定を行う処理
		if(r<=x && x<=maxx && r<=y && y<=maxy) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}
	}

}


Measured memory_bytes: 24428
def main():
    N,A,B,C=map(int,input().split())
    d={'AB':(0,1),'AC':(0,2),'BC':(1,2)}
    s=[d[input()] for _ in range(N)]
    abc=[A,B,C]
    ABC='ABC'
    ans=[]
    for i in range(N):
        x,y=s[i]
        # 強制終了
        if abc[x] == abc[y] == 0:
            print('No')
            exit()
        if abc[x] == abc[y] == 1:
            # 最後の要素 or 次に今回選ぶ可能性があるものがあるかどうか
            if (i == N-1) or (x in s[i+1]):
                ans.append(ABC[x])
                abc[x]+=1
                abc[y]-=1
            else:
                ans.append(ABC[y])
                abc[x]-=1
                abc[y]+=1
        # 2数の和が1 or 3以上の場合は大きい方をインクリメント, 小さい方をデクリメントする.
        # 2数が同じ場合には 後半の文字に対応する番号を優先する.
        else:
            if abc[x] > abc[y]:
                ans.append(ABC[y])
                abc[x]-=1
                abc[y]+=1
            else:
                ans.append(ABC[x])
                abc[x]+=1
                abc[y]-=1
    print('Yes')
    for a in ans:
        print(a)

main()


Measured memory_bytes: 10824
package main

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

//=====I/O=====

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func scanInt() int {
	sc.Scan()
	a,_ := strconv.Atoi(sc.Text())
	return a
}

func scanInt64() int64 {
	sc.Scan()
	a,_ := strconv.ParseInt(sc.Text(),10,64)
	return a
}

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ { res[i] = scanInt() }
	return res
}

func scanText() string {
	sc.Scan()
	return sc.Text()
}

func printInts(a ...int) {
	for i, e := range a {
		fmt.Fprint(wr, e)
		if i != len(a)-1 { fmt.Fprint(wr, " ") }
	}
	fmt.Fprintln(wr)
	wr.Flush()
}

//=====main=====

func main() {
	sc.Split(bufio.ScanWords)

	n, m, l := scanInt(), scanInt(), scanInt()

	g := make([][]int, n)
	for i := 0; i < n; i++ {
		g[i] = make([]int, n)
		for j := 0; j < n; j++ {
			g[i][j] = 1 << 31 - 1
		}
	}

	for i := 0; i < m; i++ {
		a,b,c := scanInt()-1, scanInt()-1, scanInt()
		g[a][b] = c
		g[b][a] = c
	}

	for k := 0; k < n; k++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				g[i][j] = min(g[i][j], g[i][k] + g[k][j])
			}
		}
	}

	g2 := make([][]int, n)
	for i := 0; i < n; i++ {
		g2[i] = make([]int, n)
		for j := 0; j < n; j++ {
			g2[i][j] = 1 << 31 -1
		}
	}

	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			if g[i][j] <= l {
				g2[i][j] = 1
			}
		}
	}

	for k := 0; k < n; k++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				g2[i][j] = min(g2[i][j], g2[i][k] + g2[k][j])
			}
		}
	}

	q := scanInt()

	for i := 0; i < q; i++ {
		s,t := scanInt()-1, scanInt()-1
		if g2[s][t] == (1<<31-1) {
			fmt.Println(-1)
		} else {
			fmt.Println(g2[s][t]-1)
		}
	}

	// fmt.Println(g2)
}

func min(a ...int) int {
	res := a[0]
	for i := 1; i < len(a); i++ {
		if res > a[i] { res = a[i] }
	}
	return res
}

func max(a ...int) int {
	res := a[0]
	for i := 1; i < len(a); i++ {
		if res < a[i] { res = a[i] }
	}
	return res
}


Measured memory_bytes: 4608
#include <bits/stdc++.h>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)
#define vall(x) (x).begin(), (x).end()
using namespace std;
using lli = long long int;
void YESNO(bool), YesNo(bool);
template <class T1, class T2> bool chmin(T1 &l, const T2 &r);
template <class T1, class T2> bool chmax(T1 &l, const T2 &r);
template <class T1, class T2> void vadd(vector<T1> &v, T2 x);

#define int long long int

void solve(long long X, long long Y) {
  rep(A, 1000) {
    rep(B, 1000) {
      if (2 * A + 4 * B == Y && A + B == X) {
        cout << "Yes" << endl;
        return;
      }
    }
  }
  cout << "No" << endl;
}

signed main() {
  long long X;
  scanf("%lld", &X);
  long long Y;
  scanf("%lld", &Y);
  solve(X, Y);
  return 0;
}

// -- lib
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }

template <class T1, class T2> bool chmin(T1 &l, const T2 &r) {
  return (l > r) ? (l = r, true) : false;
}

template <class T1, class T2> bool chmax(T1 &l, const T2 &r) {
  return (l < r) ? (l = r, true) : false;
}

template <class T1, class T2> void vadd(vector<T1> &v, T2 x) {
  for (auto &s : v)
    s += T2(x);
}


Measured memory_bytes: 3760
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define all(a) (a).begin(), (a).end()

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

using ll = long long;

ll N;
ll A[200010];
std::multiset<ll> ms;
ll ans;

int main()
{
  scanf( "%lld", &N );

  rep( i, N )
  {
    scanf( "%lld", A+i );  
    ms.insert( A[i] );
  }

  while( !ms.empty() )
  {
    ll a = *ms.rbegin();
    ms.erase( ms.find(a) );

    ll b;

    for( int i = 32; i >= 0; --i ) if( (1<<i)-a > 0 )
      b = (1<<i)-a;

    auto it = ms.find( b );
    
    if( it != ms.end() )
    {
      ++ans;
      ms.erase( it );
    }
  }

  printf( "%lld\n", ans );

  return 0;
}

Measured memory_bytes: 11136
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define rep2(i,n) for(int i=1; i<=(n); ++i)
#define all(x) (x).begin(),(x).end()
#define Sort(x) sort((x).begin(),(x).end())
#define Sort2(x) sort((x).begin(),(x).end(), greater<int>())
#define pb push_back
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;

int main()
{
    ll a; double b; cin >> a >> b;
    ll b2 = b*100+0.5;
    ll c = a*b2;
    cout << c/100 << endl;
}

/*
g++ c.cpp
./a.out

oj d https://atcoder.jp/contests/abc169/tasks/abc169_b
oj t
*/


Measured memory_bytes: 3724
import math
#def main(S, b):
if __name__ == '__main__':
    #a, b, c, d = map(int, input().split())

    x = int(input())
    #a, b = map(int, input().split())

    # a = list(map(int, input().split()))

    ans = 100
    cnt = 0
    while (True):
        ans += int(ans * 0.01)
        cnt += 1
        if (ans >= x):
            break
    print(cnt)
    # s = sum(a)

    # flug = 1
    # for i in range(1000):
    #     if (k * i >= a and k * i <= b):
    #         flug = 0
    #         break
    # #print(n * 2 * pi)

    # if (flug == 1):
    #     print("NG")
    # else:
    #     print("OK")


Measured memory_bytes: 9160
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

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

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

void solve(int n,int m){
	int d,v;
	ll ans=0;
	vector<priority_queue<int>> vv(m);
	rep(i,n){
		cin>>d>>v;
		vv[d-1].push(v);
	}
	rep(i,m)ans+=vv[i].top();
	cout<<ans<<endl;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,m;
	while(cin>>n>>m,n)solve(n,m);
}


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

int main(){
    int N;
    std::cin >> N;
    std::vector< int > A(N);
    for(int i=0; i<N; i++){
        std::cin >> A[i];
    }
    
    int ans = 0;
    for(int i=0; i<N; i++){
        if(i % 2 == 0 && A[i] % 2 == 1){
            ans++;
        }
    }
    
    std::cout << ans << std::endl;
    
    return 0;
}



Measured memory_bytes: 3624
#include <stdio.h>

int main(void)
{
  long n;
  long a[200001];
  long b[200001] = {0};
  long i, j, cnt = 0, idx = 1, m = 0;
  
  scanf("%ld", &n);
  for (i = 1; i <= n; i++)
    scanf("%ld", &a[i]);
  
  for (i = n; i > 0; i--) {
    cnt = 0;
    for (j = i*2; j <= n; j+=i)
        cnt += b[j];
    if (cnt % 2 != a[i])
      b[i]++;
  }
    
  for (i = 1; i <= n; i++)
    if (b[i] % 2){
      b[idx++] = i;
      m++;
    }
  
  printf("%ld\n", m);
  for (i = 1; i <= m; i++)
    printf("%ld ", b[i]);
  
  return 0;
}


Measured memory_bytes: 4096
/*
String[]の初期化、整数の型がlongになっているか
関数（splitとかcontainsとか）内では"+"とかは正規表現となされるので"\\+"とする
配列のコピーはarr1=arr.clone()
HashSet<>[]はおのおの初期化した？？？？？
負の数の割り算は絶対値が小さいほうに切り捨てられるex.-1/2=0ので、ある値>kみたいな式だとバグらせやすいので注意
ある値>=kとして、切り上げた値をとるべき
toLowerCase()はアルファベット以外に対して行ってもエラーにはならない
ArrayDequeではpopとpushはStackと同じ操作になる
*/
//入力終了→Ctrl+D
import java.util.*;
import java.awt.*;
import java.awt.geom.Point2D;
import static java.lang.System.*;
import static java.lang.Math.*;
public class Main {
    public static void main(String[] $) {
        Scanner sc = new Scanner(in);
        ST.Init();
        int n=sc.nextInt(),q=sc.nextInt();
        for (int i = 0; i < q; i++) {
            int com=sc.nextInt();
            int x=sc.nextInt(),y=sc.nextInt();
            if(com==0)ST.update(x,y);
            else out.println(ST.query(x,y+1,0,0,ST.n));
        }
    }

    static class ST {
        //0-indexed
        //親:(n-1)/2,子:2*n+1,2*n+2
        //i番目のindex→n+i-1
        static int INF = Integer.MAX_VALUE;
        static int n = 1048576;
        static int[] d = new int[n * 2 - 1];

        static void Init() {
            for (int i = 0; i < n * 2 - 1; i++) d[i] = INF;
        }

        //i番目の要素をxに変更（この関数はnが2の累乗でないと機能しない）
        static void update(int i, int x) {
            i += n - 1;
            d[i] = x;
            while (i > 0) {
                i = (i - 1) / 2;
                d[i] = min(d[i * 2 + 1], d[i * 2 + 2]);
            }
        }

        //[a,b)の最小値,l,rにはノードkに対応付く区間を与える
        static int query(int a, int b, int k, int l, int r) {
            if (r <= a || b <= l) return INF;
            if (a <= l && r <= b) return d[k];
            int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
            int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return min(vl, vr);
        }
        /*
        ex.[a,b)のmin→query(a,b,0,0,n)
         */
    }
}


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repi(i, a, b) for (int i = (a); i < int(b); i++)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ull << (b))
#define uniq(v) (v).erase(unique(all(v)), (v).end())

using namespace std;
using i32 = int;
using i64 = long long;
using f64 = double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf64 = vector<f64>;
using vstr = vector<string>;

template<typename T, typename S> void amax(T &x, S y) { if (x < y) x = y; }
template<typename T, typename S> void amin(T &x, S y) { if (y < x) x = y; }

template<int mod> struct modint {
  int x;
  modint(): x(0) {}
  modint(int a) { x = a % mod; if (x < 0) x += mod; }
  modint &operator+=(modint that) { x = (x + that.x) % mod; return *this; }
  modint &operator-=(modint that) { x = (x + mod - that.x) % mod; return *this; }
  modint &operator*=(modint that) { x = (i64) x * that.x % mod; return *this; }
  modint &operator/=(modint that) { return *this *= that.inverse(); }
  modint operator-() { return modint(-this->x); }
  friend ostream& operator<<(ostream &out, modint m) { return out << m.x; }
  modint inverse() {
    int a = x, b = mod, u = 1, v = 0;
    while (b) { int t = a / b; a -= t * b; u -= t * v; swap(a, b); swap(u, v); }
    return modint(u);
  }
  #define op(o, p) modint operator o(modint that) { return modint(*this) p that; }
    op(+, +=) op(-, -=) op(*, *=) op(/, /=)
  #undef op
  #define op(o) bool operator o(modint that) const { return x o that.x; }
    op(==) op(!=) op(<) op(<=) op(>) op(>=)
  #undef op
};

using mint = modint<998244353>;

int n;
vi32 a;
int sum, half;
mint dp[90010];

mint modpow(mint x, int n) {
  mint ret = 1;
  while (n-- > 0) ret *= x;
  return ret;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(16);
  cin >> n;
  a = vi32(n);
  rep(i, n) cin >> a[i];
  sum = accumulate(all(a), 0);
  half = (sum + 1) / 2;
  dp[0] = 1;
  rep(i, n) rrep(j, sum) {
    dp[j + a[i]] += dp[j];
    dp[j] *= 2;
  }
  mint ans = modpow(3, n);
  reps(j, sum) {
    if (j >= half) {
      ans -= dp[j] * 3;
    } 
  }
  dp[0] = 1;
  reps(j, sum) dp[j] = 0;
  rep(i, n) rrep(j, sum) {
    dp[j + a[i]] += dp[j];
  }
  if (sum % 2 == 0) {
    cout << ans + dp[half] * 3 << endl;
  } else {
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 640
MAX_R = 100
MAX_C = 100
n = int(input())
mat_list = [list(map(int, input().split())) for _ in range(n)]
dp = [[-1] * (MAX_C + 1) for _ in range(MAX_R + 1)]

def get_min(i, j):
    ans = float('inf')
    if dp[i][j] != -1:
        return dp[i][j]
    if i == j:
        ans = 0
    else:
        for k in range(i, j):
            p = mat_list[i][0]
            q = mat_list[k][1]
            r = mat_list[j][1]
            tmp = get_min(i, k) + get_min(k+1, j) + p*q*r
            if tmp < ans:
                ans = tmp
    dp[i][j] = ans
    return ans

print(get_min(0, n-1))


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

int main()
{
    int d;
    cin >> d;
    int c[26];
    for(int i = 0; i < 26; i++) cin >> c[i];
    int s[400][26];
    for(int i = 0; i < d; i++){
        for(int j = 0; j < 26; j++) cin >> s[i][j];
    }
    for(int i = 0; i < d; i++){
        int l = 0;
        for(int j = 0; j < 26; j++){
            if(s[i][j] > s[i][l]) l = j;
        }
        cout << l + 1 << endl;
    }
}


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

int main() {
  int N, K, x, S;
  cin >> N >> K;
  S = 0;
  for (int i = 0; i < N; i++) {
    cin >> x;
    if (x <= K - x) {
      S += 2 * x;
    }
    else {
      S += 2 * (K - x);
    }
  }
  cout << S << endl;
}

Measured memory_bytes: 256
<?php 
fscanf(STDIN, "%s", $s);
fscanf(STDIN, "%s", $t);

$sArr = str_split($s);
$tArr = str_split($t);
$cnt = 0;
for ($i=0; $i < 3; $i++) {
  if ($sArr[$i] == $tArr[$i]) {
    $cnt++;
  }
}
echo $cnt;
?>

Measured memory_bytes: 3700
#include <iostream>
typedef long long ll;
using namespace std;

ll cnt[100010]={};

int main() {
	int N;
	cin >> N;
	ll ans=0;
	for(int i=0; i<N; ++i){
		ll A;
		cin >> A;
		ans += A;
		++cnt[A];
	}
	int Q;
	cin >> Q;
	for(int i=0; i<Q; ++i){
		ll B, C;
		cin >> B >> C;
		ans += cnt[B]*(C-B);
		cout << ans << endl;
		cnt[C] += cnt[B];
		cnt[B]=0;
	}
	return 0;
}

Measured memory_bytes: 4428
#include <stdio.h>
int main(void){
   
   int c1,c5,c10,c50,c100,c500,sum;
   
   scanf("%d %d %d %d %d %d",&c1,&c5,&c10,&c50,&c100,&c500);
   
   sum=c1*1+c5*5+c10*10+c50*50+c100*100+c500*500;
   if(sum>=1000){
       printf("1\n");
       
   }
   else{
       printf("0\n");
   }
   
}


Measured memory_bytes: 2056
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

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

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

const int MAX_SIZE = 100;
const int SEATS = 17;

int* calc() {
  queue<int> q;
  int *a = new int[MAX_SIZE]();
  int g, n, s[SEATS] = {};
  for (int t = 0; ; ++t) {
    for (int i = 0; i < SEATS; ++i) {
      if (s[i]) s[i]--;
    }
    if (t % 5 == 0) q.push(t / 5);
    while (!q.empty()) {
      bool c = false;
      g = q.front();
      n = g % 5 == 1 ? 5 : 2;
      for (int i = 0; i < SEATS - n + 1; ++i) {
        if (n == 2 && !(s[i] || s[i + 1])) {
          s[i] = s[i + 1] = 17 * (g % 2) + 3 * (g % 3) + 19;
          c = true;
          break;
        }
        if (n == 5 && !(s[i] || s[i + 1] || s[i + 2] || s[i + 3] || s[i + 4])) {
          s[i] = s[i + 1] = s[i + 2] = s[i + 3] = s[i + 4] = 17 * (g % 2) + 3 * (g % 3) + 19;
          c = true;
          break;
        }
      }
      if (c) {
        a[g] = t - g * 5;
        if (g == MAX_SIZE - 1) return a;
        q.pop();
      } else {
        break;
      }
    }
  }
  return a;
}

int main() {
  int n;
  int *a = calc();
  while (true) {
    cin >> n;
    if (cin.eof()) break;
    cout << a[n] << endl;
  }
}

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

struct edge {
	int from, to;
	ld cost;
	edge() {}
	edge(int from, int to, ld cost) : from(from), to(to), cost(cost) {}
};

bool operator<(const edge& l, const edge& r){
	return l.cost < r.cost;
}

class UnionFind {
	vector<int> data;
	vector<int> rank;
	int root(int a) {
		return data[a] < 0 ? a : data[a] = root(data[a]);
	}
public:
	UnionFind(int n) : data(n, -1), rank(n, 1) {}
	bool Find(int a, int b) {
		return root(a) == root(b);
	}
	void Union(int a, int b) {
		a = root(a);
		b = root(b);
		if (a == b) return;
		if (rank[a] < rank[b]) {
			data[a] += data[b];
			data[b] = a;
		}
		else {
			data[b] += data[a];
			data[a] = b;
			if (rank[a] == rank[b]) rank[b]++;
		}
	}
	int Size(int a) {
		return -data[root(a)];
	}
	int Rank(int a) {
		return rank[root(a)];
	}
};

int main()
{
	cin.sync_with_stdio(false);
	cout << fixed << setprecision(3);
	int n;
	while (cin >> n, n) {
		vector<ld> x(n), y(n), z(n), r(n);
		for (int i = 0; i < n; i++) {
			cin >> x[i] >> y[i] >> z[i] >> r[i];
		}
		vector<edge> es;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				ld dx = x[j] - x[i], dy = y[j] - y[i], dz = z[j] - z[i];
				es.emplace_back(i, j, max((ld)0, sqrtl(dx * dx + dy * dy + dz * dz) - r[i] - r[j]));
			}
		}
		sort(es.begin(), es.end());
		ld res = 0;
		UnionFind uf(n);
		for (auto e : es) {
			if (uf.Find(e.from, e.to)) {
				continue;
			}
			res += e.cost;
			uf.Union(e.from, e.to);
		}
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 3532
import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner scan = new Scanner(System.in);
        String input;
        int n, m, l, k, a, h;
        int inf = 10000000;
        while(true){
            n = scan.nextInt();
            m = scan.nextInt();
            l = scan.nextInt();
            k = scan.nextInt();
            a = scan.nextInt();
            h = scan.nextInt();
            if(n == 0 && m == 0 && l == 0 && k== 0 && a == 0 && h == 0){
                break;
            }
            int[] bloodCenters = new int[l + 2];
            int[][] path = new int[n][n];
            int[][] newpath = new int[l + 2][l + 2];
            bloodCenters[0] = a;
            bloodCenters[1] = h;
            for(int i=2; i<l+2; i++){
                bloodCenters[i] = scan.nextInt();
            }

            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    if(i==j) path[i][j] = 0;
                    else path[i][j] = inf;
                }
            }

            for(int i=0; i<l+2; i++){
                for(int j=0; j<l+2; j++){
                    if(i==j) newpath[i][j] = 0;
                    else newpath[i][j] = inf;
                }
            }

            for(int i=0; i<k; i++){
                int start = scan.nextInt(), end = scan.nextInt(), dist = scan.nextInt();
                path[start][end] = dist;
                path[end][start] = dist;
            }

            for(int i=0; i<bloodCenters.length; i++){
                for(int j=i+1; j<bloodCenters.length; j++){
                    int dist = dijkstra(path, bloodCenters[i], bloodCenters[j]);
                    if(dist <= m) {
                        newpath[i][j] = dist;
                        newpath[j][i] = dist;
                    }
                }
            }

            int dist = dijkstra(newpath, 0, 1);
            if(dist == inf){
                System.out.println("Help!");
            } else {
                System.out.println((dist-m)>0?(dist-m)*2+m: dist);
            }
        }
    }

    private static int dijkstra(int[][] path, int start, int end){
        int current = start;
        int inf = 10000000;
        int[] distances = new int[path.length];
        boolean[] decided = new boolean[path.length];
        for(int i=0; i<distances.length; i++){
            distances[i] = inf;
        }
        distances[start] = 0;
        decided[start] = true;
        while(current != end) {
            int next = -1;
            int min = inf;
            for (int i = 0; i < path.length; i++) {
                if(distances[i] > path[i][current] + distances[current]){
                    distances[i] = path[i][current] + distances[current];

                }
                if(distances[i] < min && !decided[i]){
                    min = distances[i];
                    next = i;
                }
            }
            if(next == -1){
                break;
            }
            current = next;
            decided[next] = true;
        }

        return distances[end];
    }

}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long


#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)

const int N=1e5+5;
const int mod=1e9+7;

int32_t main() {
IOS;
string s;
cin>>s;
int cnt=0;
    for (int i = 0; i < s.size() / 2; ++i) {


        string t=s.substr(0,i);
        t+=t;
        bool ok=true;
        for (int j = 0; j < t.size(); ++j) {
            if(t[j]!=s[j]){ok=false;break;}
        }
        if(ok)cnt=t.size();
    }
    cout<<cnt;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>
#include<string.h>

typedef int32_t i32;
typedef int64_t i64;

const i32 mod = 1000000007;

i32 mod_pow (i32 r, i32 n) {
  i32 t = 1;
  i32 s = r;
  while (n > 0) {
    if (n & 1) t = (i64) t * s % mod;
    s = (i64) s * s % mod;
    n >>= 1;
  }
  return t;
}

#define ALLOC(size,type) ((type*)calloc((size),sizeof(type)))

void run (void) {
  char *s = ALLOC (100000 + 1, char);
  scanf ("%s", s);
  i32 n = strlen (s);
  i64 ans = 0;
  i32 cnt = 0;
  for (i32 i = 0; i < n; ++i) {
    if (s[i] == '0') continue;
    ans += (i64) mod_pow (2, cnt) * mod_pow (3, n - 1 - i) % mod;
    cnt++;
  }
  ans = (ans + mod_pow (2, cnt)) % mod;
  printf ("%" PRIi64 "\n", ans);
}

int main (void) {
  run();
  return 0;
}


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

using namespace std;

typedef pair<int,int> P;
typedef long long ll; 

#define int ll

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

	cin >> a >> b >> c;
	cin >> k;

	for(int i=0;i<k;i++){
		if(a>=b){
			b *= 2;
		}else if(b>=c){
			c *= 2;
		}else{
			c *= 2;
		}
	}

	if(a<b && b<c){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}

	return 0;
}


Measured memory_bytes: 3604
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define inf 1000000007
#define LINF 100000000000000007LL
#define ll long long
using namespace std;
signed main(){
	int n;
	cin>>n;
	int ans = 0;
	for(int k=1;k*k<=n;k++){
		if( (n-k)%k == 0 ){
			int m = (n-k)/k;
			if( m > k )ans += m;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<fstream>
#include<iostream>
#include<cmath>

using namespace std;

int main()
{
	int n, k;
	int i, j;
	int intArray[100000];
	int intArrayCostLR[100000];
	int intArrayCostRL[100000];
	int minimumCost;
	
	cin >> n >> k;

	cin >> intArray[0];
	for (i = 1; i < n; i++)
	{
		cin >> intArray[i];
		intArrayCostLR[i] = 0;
		intArrayCostRL[i] = 0;
	}
	minimumCost = 0x7FFFFFFF;
	for (i = k - 1; i < n; i++)
	{
		intArrayCostLR[i] = abs(intArray[i - k + 1]) + abs(intArray[i - k + 1] - intArray[i]);
		if (minimumCost > intArrayCostLR[i])
		{
			minimumCost = intArrayCostLR[i];
		}
	}
	for (i = 0; i < n - k + 1; i++)
	{
		intArrayCostRL[i] = abs(intArray[i + k - 1]) + abs(intArray[i + k - 1] - intArray[i]);
		if (minimumCost > intArrayCostRL[i])
		{
			minimumCost = intArrayCostRL[i];
		}
	}
	

	cout << minimumCost;

	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,k;
  string s;
  cin>>n>>s>>k;
  char c=s[k-1];
  for(int i=0;i<n;i++){
    if(s[i]!=c){cout<<'*';}
    else{cout<<c;}
  }
}

Measured memory_bytes: 256
#pragma target("avx")
#pragma optimize("O3")
#include<bits/stdc++.h>
using ll = int_fast64_t;
using P = std::pair<ll,ll>;
using PP = std::pair<ll,P>;
using V = std::vector<ll>;
template<typename T> using pq = std::priority_queue<T>;
template<typename T> using rpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#define REP(i,b,e) for(ll i=b; i<e; i++)
#define ALL(vec) vec.begin(),vec.end()
#define PRINT(vec) printf("[ ");for(auto &i:vec)printf("%ld ",i);puts("]");
#define SCAN(vec) for(auto &i:vec)scanf("%ld",&i)
#define fi first
#define se second

const int MOD = 1e9+7;
const ll INF = 1e18;
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

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

	std::vector<char> ans;
	for(char c: s){
		if(c=='B'){
			if(ans.size()) ans.pop_back();
		}else ans.push_back(c);
	}
	for(char c: ans) putchar(c);
	putchar('\n');	
	return 0;
}



Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b;
  int n;
  while(cin>>a>>b>>n){
    int sum=0;
    int t=a%b*10;
    for(int i=0;i<n;i++){
      sum += t/b;
      t = t%b*10;
    }
    cout<<sum<<endl;
  }
}

	

Measured memory_bytes: 1160
def f(n, x, m)
  if n == 0
    puts x.map{|y| ('a'.ord+y).chr }.join
  else
    (0..(m+1)).each do |y|
      f(n - 1, [*x, y], [m, y].max)
    end
  end
end

n = gets.to_i
f(n, [], -1)

Measured memory_bytes: 3068
S = list(input())
ACGT = []
tmp = ""
for i, s in enumerate(S):
    if s == "A" or s == "C" or s == "G" or s == "T":
        tmp += s
        if i == len(S)-1:
            ACGT.append(tmp)
            break
    else:
        ACGT.append(tmp)
        tmp = ""

print(len(sorted(ACGT, key=lambda x: len(x))[len(ACGT)-1]))


Measured memory_bytes: 3060
R, G, B, N = map(int, input().split())

cnt = 0
for r in range(0, N + 1):
  for g in range(0, N + 1):
    tmp_N = r * R + g * G
    if tmp_N > N:
      continue
    if (N - tmp_N) % B == 0:
      cnt += 1
print(cnt)


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

int main(){ 
  int n, a, b;
  cin >> n >> a >> b;
  string s;
  cin >> s;
  int cnta = 0, cntb = 0;
  for (int i = 0; i < s.length(); i++) {
    if (s[i] == 'c') cout << "No" << endl;
    if (s[i] == 'a') {
      if (cnta + cntb < a + b) {
        cnta++;
        cout << "Yes" << endl;
      } else cout << "No" << endl;
    }
    if (s[i] == 'b') {
      if (cnta + cntb < a + b && cntb < b) {
        cntb++;
        cout << "Yes" << endl;
      } else cout << "No" << endl;
    }
  }
  return 0;
} 

Measured memory_bytes: 896
N, K = map(int, input().split())
a = list(map(int, input().split()))

a = sorted(a)
ans = N
psum = 0
for i in range(N-1, -1, -1) :
    if psum+a[i] < K :
        psum += a[i]
    else :
        ans = min(ans, i)

print(ans)


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

using namespace std;
typedef long long ll;
typedef long long int lli;
typedef long double ld;
const int oo = 1e9;
const int mod = 1e9+9;



const int nax = 1e5+3;
int n;
int dp[nax];
int a[nax];


int f(int i){
	if (i==n-1) return 0;
	if(dp[i]!=-1) return dp[i];
	int ans = abs(a[i]-a[i+1])+f(i+1);
	if(i!=n-2) ans = min(ans, abs(a[i]-a[i+2])+f(i+2));
	return dp[i]=ans;
}



int main(){
	cin>>n;
	for(int i=0; i<n; i++) cin>>a[i];
	memset(dp, -1, sizeof dp);
	cout<<f(0)<<endl;
	return 0;
}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, B, ans;
  cin >> A >> B;

  ans = 0;
  for (int i = A; i <= B; i++) {
    if ((i % 10000) / 1000 != (i % 100) / 10)
      continue;

    if (i / 10000 != i % 10)
      continue;

    ans++;
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>

using namespace std;
int main(){
  int a,b,c;
  cin >> a >> b >> c;
  if((c > a && c < b ) ||
     (c > b && c < a)){
    cout << "Yes"  << endl;
  }
  else{
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict

N,A,B,C=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(N) ]

L=[]    #i回目の選択で1を足す変数の名前を順番に格納

for i,s in enumerate(S): #0-indexed
    if s=="AB":
        if A<B:
            A+=1
            B-=1
            L.append("A")
        elif B<A:
            A-=1
            B+=1
            L.append("B")
        elif A==B==0:
            print "No"
            quit()
        elif A==B:
            if i<N-1: #next_sが取れるときは
                next_s=S[i+1]
                if next_s=="AB":    #次が2文字とも一致している場合は、どっちの文字に1を足しても良い
                    A+=1
                    B-=1
                    L.append("A")
                elif next_s=="AC":    #次に同じ文字が1文字出てくる場合は、その文字の方に+1
                    A+=1
                    B-=1
                    L.append("A")
                elif next_s=="BC":    #次に同じ文字が1文字出てくる場合は、その文字の方に+1
                    A-=1
                    B+=1
                    L.append("B")
            else: #最終行のときはどっちを取っても良い
                A+=1
                B-=1
                L.append("A")
    elif s=="AC":
        if A<C:
            A+=1
            C-=1
            L.append("A")
        elif C<A:
            A-=1
            C+=1
            L.append("C")
        elif A==C==0:
            print "No"
            quit()
        elif A==C:
            if i<N-1: #next_sが取れるときは
                next_s=S[i+1]
                if next_s=="AC":    #次が2文字とも一致している場合は、どっちの文字に1を足しても良い
                    A+=1
                    C-=1
                    L.append("A")
                elif next_s=="AB":    #次に同じ文字が1文字出てくる場合は、その文字の方に+1
                    A+=1
                    C-=1
                    L.append("A")
                elif next_s=="BC":    #次に同じ文字が1文字出てくる場合は、その文字の方に+1
                    A-=1
                    C+=1
                    L.append("C")
            else: #最終行のときはどっちを取っても良い
                A+=1
                C-=1
                L.append("A")
    elif s=="BC":
        if B<C:
            C-=1
            B+=1
            L.append("B")
        elif C<B:
            B-=1
            C+=1
            L.append("C")
        elif B==C==0:
            print "No"
            quit()
        elif B==C:
            if i<N-1: #next_sが取れるときは
                next_s=S[i+1]
                if next_s=="BC":    #次が2文字とも一致している場合は、どっちの文字に1を足しても良い
                    B+=1
                    C-=1
                    L.append("B")
                elif next_s=="AB":    #次に同じ文字が1文字出てくる場合は、その文字の方に+1
                    B+=1
                    C-=1
                    L.append("B")
                elif next_s=="AC":    #次に同じ文字が1文字出てくる場合は、その文字の方に+1
                    B-=1
                    C+=1
                    L.append("C")
            else: #最終行のときはどっちを取っても良い
                A+=1
                C-=1
                L.append("A")
print "Yes"
for x in L:
    print x

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    double sum_ = 0.0;
    for (int i = 0; i < N; i++) {
        sum_ += A[i];
    }
    int flag = 1;
    for (int i = 0; i < M; i++) {
        if (A[N-1-i]/sum_ < 1.0/(4*M)) {
            cout << "No" << endl;
            flag = 0;
            break;
        }
    }
    if (flag) cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int G[666][666], len[666][666];
char s[666];

int main(){
    int N;
    scanf("%d", &N);
    for(int i = 1; i <= N; ++i){
        scanf("%s", s + 1);
        for(int j = 1; j <= N; ++j) G[i][j] = s[j] - 'a' + 1;
    }
    for(int i = 1; i <= N; ++i){
        for(int j = 1; j <= N; ++j){
            G[i+N][j] = G[i][j+N] = G[i+N][j+N] = G[i][j];
        }
    }
    for(int i = 1; i <= N + N; ++i){
        for(int j = 1; j <= N + N; ++j){
            int l = 1;
            while(i + l <= N + N && j + l <= N + N && G[i][j+l] == G[i+l][j]) l++;
            len[i][j] = l;
        }
    }
    int ans = 0;
    for(int i = 1; i <= N; ++i){
        for(int j = 1; j <= N; ++j){
            int ok = 1;
            for(int k = 0; k < N; ++k){
                if(len[i+k][j+k] < N - k) {ok = 0; break;}
            }
            ans += ok;
        }
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 3328
using System;

class Menseki{
  static void Main(){
    string input = Console.ReadLine();
    long hankei = long.Parse(input);
    if (hankei > 0){
      double Ans = hankei * hankei;
      Console.WriteLine(Ans);
    }
    else{
      Console.WriteLine("0");
    }
  }
}


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

using namespace std;

int main(){
  int n,x;
  cin >> n >> x;
  vector<int> s(n);
  int m=1000000000;
  for(int i=0;i<n;i++){
    cin >> s[i];
    m=min(m,abs(s[i]-x));
  }
  if(n==1){
      cout << abs(s[0]-x) << endl;
      return 0;
  }
  int ans=-1;
  for(int i=2;i<=m;i++){
    bool flag=true;
    for(int j=0;j<n;j++){
      if(abs(s[j]-x)%i!=0){
        flag=false;
        break;
      }
    }
    if(flag) ans=i;
  }
  if(ans==-1){
      cout << 1 << endl;
      return 0;
  }
  cout << ans << endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string str1,str2;
  int count=0;
  cin>>str1;
  cin>>str2;
  for(int i=0;i<str1.size();i++)
  {
    if(str1[i]!=str2[i])
    {
      count++;
    }
  }
  cout<<count;
  return 0;
}

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

const ll LINF = 1e18;
const int INF = 1e9;
const ll MOD = 1000000007;

int main(){

    string s;
    cin >> s;
    int ans = 0; 
    int cnt = 0;
    for(int i = 0; i < (int)s.size(); i++){
        if((s[i] == 'A') ||
            (s[i] == 'C') ||
            (s[i] == 'G') ||
            (s[i] == 'T')){
            cnt++;
        }
        else{
            cnt = 0;
        }
        ans = max(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
N,D=map(int,input().split())
X=[list(map(int,input().split())) for i in range(N)]
#print(X)

cnt=0
for i in range(N):
    for j in range(N):
        if i!=j:
            val=0
            for k in range(D):
                val+=(X[i][k]-X[j][k])**2
            if val**0.5==int(val**0.5):
                cnt+=1

print(cnt//2)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define SIZE 300005
#define MOD 1000000007LL
#define EPS 1e-10
#define INF 1<<29
#define LLINF 1LL<<60
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)
#define SET(a,c) memset(a,c,sizeof a)
#define BIT(i,j) ((i)>>(j))&1
#define ALL(o) (o).begin(), (o).end()
#define ERASE(o) (o).erase(unique((o).begin(),(o).end()), (o).end())
#define SQ(x) ((x)*(x))
using namespace std;
typedef long long ll;
typedef pair<ll,ll> Pll;
typedef pair<int, int> Pii;
typedef pair<double, double> Pdd;
typedef complex<double> dcomplex;
template<typename T> inline void priv(vector<T>a){REP(i,a.size()){cerr<<a[i]<<((i==a.size()-1)?"\n":" ");}}
ll gcd(ll a,ll b){int c=max(a,b);int d=min(a,b);return c==0||d==0?c:gcd(c%d,d);}
ll lcm(ll a,ll b){return a==0||b==0?0:a*b/gcd(a,b);}
ll modfact(ll a){ll b=1;FOR(i,2,a)b=b*i%MOD;return b;}
ll modpow(ll a, ll n) {ll b=1;while (n>0){if(n&1)b=b*a%MOD;a=a*a%MOD;n>>=1;}return b;}
ll modcomb(ll n, ll k) {ll b=1;DOWN(i,n,n-k+1)b=b*i%MOD;return b*modpow(modfact(k),MOD-2)%MOD;}

ll N, M;

int main() {
    cin >> N >> M;
    map<ll, ll> B;
    ll f = 2;
    while(M > 1) {
        if(M % f == 0) B[f] = 0;
        while(M % f == 0) {
            B[f]++;
            M /= f;
        }
        if(f==2) f++;
        else f += 2;
    }
    ll ans = 1;
    for (auto b : B){
        ans = ans*modcomb(b.second+N-1, b.second)%MOD;
        // cerr << ans << endl;
    }
    cout << ans << endl;
	return 0;
}

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

int main() {
  string s; cin >> s;
  int aloc, zloc;
  bool is_a_finded = false;
  for (int i = 0; i < s.size(); i++) {
    if (!is_a_finded) {
      if (s.at(i) == 'A') {
        aloc = i;
        is_a_finded = true;
      }
    }
    if (s.at(i) == 'Z') zloc = i;
  }
  cout << zloc - aloc + 1 << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repn(i,n) for(ll i=0;i<=(ll)(n);i++)
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
//cin.tie(0);
//ios::sync_with_stdio(false);



signed main(){
    string s;cin>>s;
    ll ans=0;
    for(int i=1;i < siz(s);i++)
    {
        if(s[i-1]!=s[i])ans++;
    }
    cout<<ans<<endl;
}


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

const double PI = acos(-1);
int main(){
    double a, b, h, m;
    cin >> a >> b >> h >> m;
    auto A = polar(a, 2 * PI * (h * 60 + m) / 60 / 12);
    auto B = polar(b, 2 * PI * m / 60);
    printf("%.20f", abs(A - B));
}

Measured memory_bytes: 4132
l=[];A=abs;r=range(101)
for _ in range(int(input())):
	*t,=map(int,input().split())
	l+=[t]
	if t[2]:a,b,c=t
for i in r:
	for j in r:
		H=c+A(i-a)+A(j-b)
		if all(h==max(0,H-A(i-x)-A(j-y))for x,y,h in l):
			print(i,j,H)

Measured memory_bytes: 3064
import java.util.Scanner

object Main {
  def solve2(sc: => Scanner, N: Int): Int = {
    if (N == 0) (0) else (
      solve2(sc, N - 1) + ((sc.nextInt, sc.nextInt, sc.nextInt, sc.nextInt) match {
        case (x, y, h, w) if (x + y + h <= 60 && w <= 2) => 600
        case (x, y, h, w) if (x + y + h <= 80 && w <= 5) => 800
        case (x, y, h, w) if (x + y + h <= 100 && w <= 10) => 1000
        case (x, y, h, w) if (x + y + h <= 120 && w <= 15) => 1200
        case (x, y, h, w) if (x + y + h <= 140 && w <= 20) => 1400
        case (x, y, h, w) if (x + y + h <= 160 && w <= 25) => 1600
        case _ => 0
      }))
  }

  def solve(sc: => Scanner): Unit = {
    val N = sc.nextInt
    if (N != 0) {
      println(solve2(sc, N))
      solve(sc)
    }
  }

  def main(args: Array[String]): Unit = {
    val sc: Scanner = new Scanner(System.in)
    solve(sc)
  }
}

Measured memory_bytes: 86344