akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        double ans = 0.0;
        for (int i = 1; i <= n; i++) {
            int sum = i;
            double tmp = 1.0 / (double)n;
            while(sum < k) {
                sum *= 2;
                tmp /= 2.0;
            }
            ans += tmp;
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 35876
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] a = new int[]{sc.nextInt(), sc.nextInt(), sc.nextInt()};
        int[][] x = new int[a[0]][a[1]];
        int[][] y = new int[a[1]][a[2]];
        long[][] z = new long[a[0]][a[2]];
        for (int i = 0; i < a[0]; i++) {
            for (int j = 0; j < a[1]; j++) {
                x[i][j] = sc.nextInt();
            }
        }
        for (int i = 0; i < a[1]; i++) {
            for (int j = 0; j < a[2]; j++) {
                y[i][j] = sc.nextInt();
            }
        }

        for (int i = 0; i < a[0]; i++) {
            for (int j = 0; j < a[2]; j++) {
                long sum = 0;
                for (int k = 0; k < a[1]; k++) {
                    sum += x[i][k] * y[k][j];
                }
                z[i][j] = sum;
            }
        }
        print2DArray(z);
    }

    private static void print2DArray(long[][] array) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                sb.append(array[i][j]);
                if (j != array[i].length - 1) {
                    sb.append(" ");
                }
            }
            sb.append("\n");
        }
        System.out.print(sb);
    }
}

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

int k,x,y,nowx,nowy,a=-1;
struct r2{int x,y;};
vector<r2> ans;
void move(int x,int y){
  nowx+=x;nowy+=y;
  ans.push_back({nowx,nowy});
}

int main(){
  cin>>k>>x>>y;
  int X=abs(x),Y=abs(y); if(X>Y)swap(X,Y);

  if( !(k&1) && ((X+Y)&1) ) {cout<<-1<<endl;return 0;}
  if(X+Y==k){cout<<1<<endl<<x<<" "<<y<<endl;return 0;}

  for(int i=k*2-(X+Y);a<0;i+=k) if(!(i&1)) a=i/2;

  while(a>=k)move(0,-k),a-=k;
  move(-a,k-a);
  while(nowx+k<=X)move(k,0);
  while(nowy+k<=Y)move(0,k);
  if(nowx!=X||nowy!=Y)ans.push_back({X,Y});

  cout<<ans.size()<<endl;
  for(r2 p:ans){
    int ansx=p.x,ansy=p.y;
    if(abs(x)>abs(y))swap(ansx,ansy);
    if(x<0)ansx*=-1; if(y<0)ansy*=-1;
    cout<<ansx<<" "<<ansy<<endl;
  }
}


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

public class Main{
	public static void main(String args[]) throws IOException{
		Scanner bf = new Scanner(System.in);
		while(true){
			int n = bf.nextInt();
			int a = bf.nextInt();
			int b = bf.nextInt();
			if(n == 0 && a == 0 && b == 0) break;
			int[] list = new int[n+1];
			for(int i=0; i<n+1; i++) list[i] = 0;
			list[0] = 1;
			int counter = 0;
			for(int i=0; i<n+1; i++){
				if(list[i] == 1){
					if(i+a < n+1) list[i+a] = 1;
					if(i+b < n+1) list[i+b] = 1;
				}else counter++;
			}
			System.out.println(counter);
		}
	}
}

Measured memory_bytes: 37980
K = int(input())
A, B = [int(i) for i in input().split()]

min_multi = int((A / K) + 1)
noKiri = K * min_multi
Kiri = K * ( min_multi - 1 )
if ( A <= noKiri <= B ) or (A <= Kiri <= B) :
  print('OK')
else :
  print('NG')


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

using namespace std;

#define rep(i, a) for (int i = 0; i < (int) (a); i++)
#define reps(i, a) for (int i = (int) (a); i < (int) (b); i++)
#define RS resize

vector<vector<int> > a;
int h, w;

int calc(int r, int c)
{
	int res = 0;
	rep(i, h) {
		rep(j, w) {
			res += a[i][j] * min(abs(i-r), abs(j-c));
		}
	}
	return res;
}

int main()
{
	cin >> h >> w;
	a.RS(h, vector<int>(w, 0));
	int res = INT_MAX;
	rep(i, h) rep(j, w) cin >> a[i][j];
	rep(i, h) {
		rep(j, w) {
			res = min(res, calc(i, j));
		}
	}
	cout << res << endl;
}



Measured memory_bytes: 3156
import math
import collections
def main():

    N, K = map(int, input().split())
    mod = pow(10, 9) + 7

    p = collections.defaultdict(int)

    def fast_pow(x, y, mod):
        if y == 0: return 1
        if y % 2 == 0: return pow(fast_pow(x, y//2, mod), 2) % mod
        if y % 2 == 1: return (x * pow(fast_pow(x, y//2, mod), 2)) % mod

    ans = 0
    for i in range(K, 0, -1):
        v = fast_pow(K//i, N, mod) % mod
        u = v - p[i]
        tmp = (u * i) % mod
        for j in range(1, int(math.sqrt(i))+1):
            if i % j == 0:
                p[j] += u
                p[j] %= mod
                if i//j != j:
                    p[i//j] += u
                    p[i//j] %= mod
        ans += tmp
        ans %= mod
        # print(i, ans)
    return ans

if __name__ == '__main__':
    print(main())

Measured memory_bytes: 94336
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#include<stack>
using namespace std;

int a[100010],b[100010],n;
map<int,int> mp,mp1;
int cnt,tot,fa[200010];
int sz;

int get(int x)
{
	int i=x,j;
	while(fa[x]!=x)	x=fa[x];
	while(fa[i]!=x)	j=fa[i],fa[i]=x,i=j;
	return x;
}

void merge(int x,int y)
{
	x=get(x),y=get(y);
	if(x!=y)	fa[x]=y;
}

int main()
{
	int i,j,k,x=0,ans=1;
	scanf("%d",&n);
	for(i=1;i<=n;i++)	scanf("%d",&a[i]),x^=a[i],mp[a[i]]++;
	mp[x]++;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
		if(!mp[b[i]])	ans=0;
		else	mp[b[i]]--;
	}
	if(!ans)
	{
		printf("-1\n");
		return 0;
	}
	else
	{
		ans=0;
		for(i=1;i<=(n<<1)+1;i++)	fa[i]=i;
		for(i=1;i<=n;i++)
		{
			if(a[i]!=b[i])
			{
				ans++;
				if(!mp1[a[i]])	mp1[a[i]]=++cnt;
				if(!mp1[b[i]])	mp1[b[i]]=++cnt;
				merge(mp1[a[i]],mp1[b[i]]);
			}
		}
		if(!ans)
		{
			printf("0\n");
			return 0;
		}
		if(!mp1[x])	mp1[x]=++cnt;
		for(i=1;i<=cnt;i++)	if(get(i)==i)	ans++;
		printf("%d\n",ans-1);
	}
	return 0;
}

Measured memory_bytes: 11264
#include <iostream>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <deque>  
#include <iomanip>

using namespace std;

#define ll long long
#define INF 1e9
#define MOD 1e9 + 7
#define rep(i, n) for(int i = 0; i < n; i++)
#define loop(i, a, n) for(int i = a; i < n; i++)
#define all(in) in.begin(), in.end()

bool squre(ll dist){
    for(ll i = 0; i <= 300; i++){
        if(i * i == dist) return true;
    }
    return false;
}
int main(){
    int N, D;
    cin >> N >> D;
    double X[N][D];
    rep(i, N)rep(k, D) cin >> X[i][k];
    int ans = 0;
    rep(i, N){
        for(int k = i + 1; k < N; k++){
            ll dist = 0;
            rep(j, D){
                dist += (X[i][j] - X[k][j]) * (X[i][j] - X[k][j]);
            }
            if(squre(dist)) ans++;

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

Measured memory_bytes: 256
//
//  atcoder.cpp
//
//
///
#include <bits/stdc++.h>
#include <boost/optional.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/bimap/bimap.hpp>
#include <boost/bimap/multiset_of.hpp>
#include <boost/multi_array.hpp>
#include <boost/integer/common_factor_rt.hpp>
#include <boost/algorithm/string.hpp>

#define REP(i, N) for(int i=0; i<(N); i++)
#define REC(f, ...) (void)0; const auto f = [&](const auto f, __VA_ARGS__)
using namespace std;
using namespace boost::integer;

using ll = long long;
namespace bst = boost;
template<typename T> class in {
    T value;
public:
    in() { cin >> value; }
    operator const T&() const { return value; }
    operator T&() { return value; }
    in& operator=(T source) { value = source; return *this; }
};
template<> class in<string> : public string {
public:
    in() { cin >> *this; }
};
template<class T> class inseq : public T {
public:
    template<typename... Arg> inseq(Arg... arg) : T(forward<Arg>(arg)...) { for (auto&& i : *this) cin >> i; }
};
template<class T> using invec = inseq<vector<T>>;

auto solve() {
  in<ll> K;
  in<string> S;

  if (S.length() > K) {
    S.resize(K);
    S += "...";
  }

  return S;
}

template<typename T> void plot(const T& func) { cout << func() << endl; }
template<> void plot<void()>(void(&func)()) { func(); }
template<> void plot<double()>(double(&func)()) { cout << setprecision(9) << func() << endl; }

int main() {
  plot(solve);

  return 0;
}



Measured memory_bytes: 3628
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    a,b = MI()
    c,d = MI()
    if a!=c:
        print(1)
    else:
        print(0)
if __name__ == '__main__':
    main()

Measured memory_bytes: 3572
function bomb(a,b,i){
   if(i==n){
      min=Math.min(min,Math.abs(a-b));
      return;
   }
   bomb(a+arr[i],b,i+1);
   bomb(a,b+arr[i],i+1);
}
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.trim()).split("\n");
while(true){
   var n=Arr.shift()-0;
   if(n==0)break;
   var arr=Arr.shift().split(" ").map(Number);
   var min=Infinity;
   bomb(0,0,0);
   console.log(min);
}

Measured memory_bytes: 8976
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    def df(c, d):
        res = c // d
        if res * d > c: res -= 1
        return res

    q = int(input())
    L = [list(map(int, input().split())) for _ in range(q)]
    for a, b in L:
        if (a, b) == (1, 1):
            print(0)
            continue
        c = a * b - 1
        rc = int(c ** 0.5)
        rc -= 1
        while (rc + 1) ** 2 <= c:
            rc += 1
        ans = rc * 2
        if rc * (rc + 1) > c:
            ans -= 1
        ab = [a, b]
        for k in ab:
            ans -= 1
            if k > rc:
                y = df(c, k)
                if y == 0:
                    ans += 1
                else:
                    x = df(c, y)
                    if x != k or (df(c, k) == df(c, k - 1)):
                        ans += 1
        print(ans)

main()


Measured memory_bytes: 3064
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w = LI()
ch, cw = LI()
dh, dw = LI()
s = [input() for _ in range(h)]

dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
que = deque([(cw-1, ch-1)])
d = [[10**10] * w for _ in range(h)]
d[ch-1][cw-1] = 0
while que:
    x, y = que.popleft()
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if s[ny][nx] == '.' and d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.appendleft((nx, ny))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx, ny = x + i, y + j
            if 0 <= nx < w and 0 <= ny < h:
                if s[ny][nx] == '.' and d[ny][nx] > d[y][x] + 1:
                    d[ny][nx] = d[y][x] + 1
                    que.append((nx, ny))
if d[dh-1][dw-1] == 10**10:
    print(-1)
else:
    print(d[dh-1][dw-1])


Measured memory_bytes: 91408
import qualified Data.ByteString.Char8 as C
import Data.Maybe (fromJust)
import Control.Monad (replicateM)

cReadLn :: IO Int
cReadLn = fst . fromJust . C.readInt <$> C.getLine

getParms :: IO [Int]
getParms = map (fst . fromJust . C.readInt) . C.words <$> C.getLine

main :: IO ()
main = do
  [w,h,n] <- getParms
  xya     <- replicateM n getParms
  print $ area $ f w h xya

initialize
  :: Int -> Int -> ([Int],[Int])
initialize w h = ([0 .. w-1], [0 .. h-1])

cut :: ([Int],[Int]) -> [Int] -> ([Int], [Int])
cut (xs,ys) [x,y,a]
  | a == 1 = (xs1, ys)
  | a == 2 = (xs2, ys)
  | a == 3 = (xs,  ys3)
  | a == 4 = (xs,  ys4)
  where
    xs1 = dropWhile (< x) xs
    xs2 = takeWhile (< x) xs
    ys3 = dropWhile (< y) ys
    ys4 = takeWhile (< y) ys

f :: Int -> Int -> [[Int]] -> ([Int], [Int])
f w h = foldl cut (initialize w h) 

area (xs,ys) = length xs * length ys

Measured memory_bytes: 636
n,k,q = map(int,input().split())
h = [k]*n

for i in range(q):
    a = int(input())
    h[a-1] += 1
h = [ h[i] - q for i in range(n)]

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

Measured memory_bytes: 9844
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<complex>
#include<cstdlib>
#include<cstring>
#include<numeric>
#include<sstream>
#include<iostream>
#include<algorithm>
#include<functional>

#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const double EPS=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
queue<pii> que;
int main(){
	for(int i = 0;i < 4;i++){
		int t,n;
		cin>>t>>n;
		que.push(pii(t,n));
	}
	while(!que.empty()){
		int d = que.front().second;
		int num = que.front().first;
		if(num==1)
			cout <<6000*d<<endl;
		if(num==2)
			cout <<4000*d<<endl;
		if(num==3)
			cout <<3000*d<<endl;
		if(num==4)
			cout <<2000*d<<endl;
		que.pop();
	}
	return 0;
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18
#define PI 3.14159265358979

using namespace std;

int main(void){
  int n, x;
  cin >> n >> x;

  int num = 1;


  int l, d = 0;
  for (int i = 0; i < n; i++){
    cin >> l;
    d += l;
    if (d <= x)
      num++;
  }
  cout << num << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>
#include <set>

using namespace std;
struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
#define debug(v) {cerr<<"\033[1;36m[debug]\033[m "<<#v<<" : "<<v<<endl;}

using int64 = long long;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    for (int i=0; i<n; i++) {
        cout << (s[i]!=','? s[i] : ' ');
    }
    cout << endl;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int X;
    cin >> X;
    vector<bool> expo(X+1);

    expo.at(1) = 1;

    for (int i = 2; i <= X; i ++){
        int v = i * i;
        while (v <= X){
            expo.at(v) = 1;
            v *= i;
        }
    } 

    for (int i = X; i >= 1; i--){
        if(expo.at(i)){
            cout << i << endl;
            break;
        }
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i=0;i < (int)(n);i++)

int math[101][101];

int main(){
    int h,w,n;
    cin >> h >> w >> n;
    vector<int> v(n);
    rep(i,n){
        cin >> v[i];
    }
    int id = 0;
    int cnt = v[0];

    for (int i = 0;i < h;i++){
        for (int j = 0; j < w;j++){
            if (cnt > 0) {
                math[i][j] = id+1;
                cnt--;
            }
            else{
                id++;
                math[i][j] = id+1;
                cnt = v[id]-1;
            }
        }
        if (i%2 == 1) reverse(math[i],math[i]+w);
    }

    rep(i,h){
        rep(j,w){
            cout << math[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define Lim 9999991
#define Jmp 100003

int dic[Lim];

int toint(string s) {
    int ret = 0;
    for (int i = 0; i < s.size(); ++i) {
        ret *= 5;
        switch (s[i]) {
            case 'A':
                ret += 1;
                break;
            case 'T':
                ret += 2;
                break;
            case 'G':
                ret += 3;
                break;
            case 'C':
                ret += 4;
                break;
        }
    }
    return ret;
}

void push(string s) {
    int a = toint(s);
    int i = a;
    while (true) {
        if (!dic[i]) {
            dic[i] = a;
            return;
        }
        i += Jmp;
    }
}

int find(string s) {
    int a = toint(s);
    int i = a;
    while (true) {
        if (!dic[i]) {
            return 0;
        }
        if (dic[i] == a) {
            return 1;
        }
        i += Jmp;
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        string s, t;
        cin >> s >> t;
        if (s == "insert") {
            push(t);
        }
        else {
            if (find(t)) {
                printf("yes\n");
            }
            else {
                printf("no\n");
            }
        }
    }
    return 0;
}

Measured memory_bytes: 31016
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    string S; cin >> S;
    bool j1 = true, j2 = false, j3 = true, j4 = false;
    int cp = 0;
    for (int i = 0; i < S.length(); ++i) {
        if (i == 0 && S[i] != 'A') j1 = false;
        if (2 <= i && i <= S.length() - 2 && S[i] == 'C') {
            if (j4 == false) j2 = true, j4 = true, cp = i;
            else j2 = false;
        }
        if (i != 0 && i != cp && 'A' <= S[i] && S[i] <= 'Z') j3 = false;
    }
    if (j1 && j2 && j3) printf("%s\n", "AC");
    else printf("%s\n", "WA");
}


Measured memory_bytes: 3620
#include <iostream>
#include <map>

using namespace std;

int main()
{
    int n;

    while (cin >> n, n) {
        int ans = 0;

        for (int a = 0; a * a <= n; a++) {
            for (int b = a; b * b <= n; b++) {
                for (int c = b; c * c <= n; c++) {
                    for (int d = c; d * d <= n; d++) {
                        if (a * a + b * b + c * c + d * d == n) 
                            ans++;
                        else if (a * a + b * b + c * c + d * d > n)
                            break;
                    }
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using ll = long long;
using P = pair<ll, ll>;
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; }

string n;
int K;

ll dp[110][2][5];

int main() {
    cin >> n >> K;
    int nlen = n.length();
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;

    for(int i = 0; i < nlen; ++i) {
        int limit = n.at(i) - '0';
        for(int j = 0; j < 2; ++j) {
            for(int k = 0; k <= K; ++k) {
                for(int d = 0; d <= (j ? 9 : limit); ++d) {
                    if(d == 0) {
                        // kは増えない
                        dp[i+1][j || (d<limit)][k] += dp[i][j][k];
                    }else {
                        dp[i+1][j || (d<limit)][k+1] += dp[i][j][k];
                    }
                }
            }
        }
    }
    
    cout << dp[nlen][0][K] + dp[nlen][1][K] << endl;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
using namespace std;  
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;

double x[10], y[10];

double dist(int i, int j){
  double dx = x[i] - x[j];
  double dy = y[i] - y[j];
  return pow(dx*dx + dy*dy, 0.5);
}

int main() {
  double n; cin >> n;
  rep(i, 0, n) cin >> x[i] >> y[i];
  vector<int> v(n);
  rep(i, 0, n) v[i] = i;
  double ans = 0.0;
  do{
    rep(i, 0, n-1) ans += dist(v[i], v[i+1]);
  }while(next_permutation(ALL(v)));

  int factorial = 1;
  Rep(i, 2, n) factorial *= i;
  ans /= factorial;
  cout << fixed << setprecision(10) << ans << endl;

  return 0;
}


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

using namespace std;

typedef long long ll;

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, s = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int t;
        cin >> t;
        s += t % 2;
    }
    if (s % 2) {
        cout << "NO";
    } else {
        cout << "YES";
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <string>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#include <math.h>
#include <limits.h>
using namespace std;

int main() {
	string s, t;
	cin >> s >> t;
	int a, b;
	cin >> a >> b;
	string r;
	cin >> r;
	if (r == s) {
		cout << (a - 1) << " " << b << endl;
	}
	else cout << a << " " << (b - 1) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(v) (v).begin(), (v).end()
#define INF 1e9
#define pb push_back
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
using namespace std;
typedef long long ll;
typedef long double ld;
using pil = pair<ll, ll>;
template<class T>using numr=std::numeric_limits<T>;
#define MOD 1000000007
#define MOD2 998244353

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, m;
    cin >> n >> m;
    ll a;
    for(ll i = 0; i < m ; i++){
        cin >> a; 
        n -= a;
    }
    if(n < 0) cout << "-1" << endl;
    else cout << n << endl;
}

Measured memory_bytes: 3656
while True:
    N, X = map(int, input().split())
    if N == 0:
        break
    res = 0
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            for k in range(j+1, N+1):
                if i + j + k == X:
                    res += 1
    print(res)


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

int main(){
    int N;cin>>N;
    long array[N];
    for(int i=0;i<N;i++)cin>>array[i];
    long ans=array[0];
    for(int i=1;i<N;i++){
      ans=ans^array[i];
    }
    if(ans==0)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
bool possible(vector<queue<int>> A, int k){
  int N = A.size();
  int M = A[0].size();
  vector<bool> use(M, true);
  for (int i = 0; i < M - 1; i++){
    map<int, int> freq;
    int next = -1;
    for (int j = 0; j < N; j++){
      while (!use[A[j].front()]){
        A[j].pop();
      }
      freq[A[j].front()]++;
      if (freq[A[j].front()] > k){
        next = A[j].front();
      }
    }
    if (next == -1){
      return true;
    } else {
      use[next] = false;
    }
  }
  return false;
}
int main(){
  int N, M;
  cin >> N >> M;
  vector<queue<int>> A(N);
  for (int i = 0; i < N; i++){
    for (int j = 0; j < M; j++){
      int a;
      cin >> a;
      a--;
      A[i].push(a);
    }
  }
  int tv = N;
  int fv = 0;
  while (tv - fv > 1){
    int mv = (tv + fv) / 2;
    if (possible(A, mv)){
      tv = mv;
    } else {
      fv = mv;
    }
  }
  cout << tv << endl;
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
using namespace std;
string to_string(const string& s) {
	return '"' + s + '"';
}
string to_string(const bool b) {
	return (b ? "true" : "false");
}
string to_string(const char* s) {
	return to_string((string)s);
}
string to_string(const char c) {
	string s = "'";
	s += c;
	s += "'";
	return s;
}
template<class T, class U>
string to_string(const pair<T, U>& p) {
	string s = "(";
	s += to_string(p.first);
	s += ", ";
	s += to_string(p.second);
	s += ")";
	return s;
}
template<class T>
string to_string(const T& a) {
	bool first = true;
	string s = "{";
	for (const auto& x : a) {
		if(!first){
			s += ", ";
		}
		first = false;
		s += to_string(x);
	}
	s += "}";
	return s;
}
void debug_out() {cerr << '\n';}
template<class Head, class... Tail>
void debug_out(Head head, Tail... tail) {
	cerr << ' ' << to_string(head);
	debug_out(tail...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "] = ", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
using ll = long long;
using ld = long double;
const int mod = 1e9 + 7;
const int inf = 2e9;
const ll inf64 = 7e18l;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(20);
	int n;
	cin >> n;
	string s;
	cin >> s;
	map<char, int> cnt;
	for (char c : s) {
		++cnt[c];
	}
	int x = 'R' ^ 'G' ^ 'B';
	ll answer = 0;
	ll bad = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (s[i] == s[j]) {
				continue;
			}
			char last = s[i] ^ s[j] ^ x;
			answer += cnt[last];
			int next = j + (j - i);
			if (next < n && s[next] == last) {
				++bad;
			}
		}
	}
	cout << answer / 3 - bad << '\n';
	
 	return 0;
}


Measured memory_bytes: 3644
# ABC107C - Candles (ARC101C)
def main():
    N, K, *X = map(int, open(0).read().split())
    ans = float("inf")
    for l, r in zip(X, X[K - 1 :]):
        x = r - l + min(abs(l), abs(r))
        ans = x if x < ans else ans
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 14052
#include <stdio.h>

int main(){
  int a,b,c,m;
  scanf("%d %d %d",&a,&b,&c);
  m=a;
  if(m<b) m=b;
  if(m<c) m=c;
  printf("%d\n",a+b+c-m);
  return 0;
}

Measured memory_bytes: 1696
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define P pair<ll, ll>
#define Graph vector<vector<ll>>
#define fi first
#define se second
constexpr ll mod = 1000000007;
constexpr ll INF = (1ll << 60);
constexpr double pi = 3.14159265358979323846;
template <typename T>
inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}

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

    if (s == "zyxwvutsrqponmlkjihgfedcba") {
        cout << -1 << endl;
        return 0;
    }
    vector<ll> snum(s.size());
    vector<bool> check(26, false);
    rep(i, s.size()) { snum[i] = (ll)(s[i] - 'a'); }

    rep(i, s.size()) { check[(ll)(s[i] - 'a')] = true; }

    bool all = true;
    ll key = -1;
    rep(i, 26) {
        if (check[i] == false) {
            all = false;
            key = i;
            break;
        }
    }

    if (key != -1) {
        cout << s << (char)('a' + key) << endl;
    } else {
        rep(i, 26) snum.push_back(-1ll);
        while (next_permutation(snum.begin(), snum.end())) {
            vector<ll> ins = snum;
            sort(ins.begin(), ins.end());
            bool B = true;
            rep(i, ins.size() - 1) {
                if (ins[i] == ins[i + 1]) B = false;
            }

            break;
        }

        rep(i, s.size()) {
            if (snum[i] != -1) cout << (char)('a' + snum[i]);
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 3632
def double_helix(b: str)->str:
    if b == 'A':
        return 'T'
    if b == 'T':
        return 'A'
    if b == 'C':
        return 'G'
    return 'C'


if __name__ == "__main__":
    b = input()
    ans = double_helix(b)
    print(ans)


Measured memory_bytes: 2940
#include <cstdio>
#include <map>
using namespace std;
int a[100005];
map<int,int>f;
int main()
{
	int i,n,ans=0;
	scanf ("%d",&n);
	for (i=1; i<=n; i++) scanf ("%d",&a[i]),f[a[i]]++;
	for (i=1; i<=n; i++)
		if (f[a[i]]<a[i]) ans+=f[a[i]],f[a[i]]=a[i];
		else if (f[a[i]]>a[i]) ans+=(f[a[i]]-a[i]),f[a[i]]=a[i];
	printf ("%d\n",ans);
	return 0;
}

Measured memory_bytes: 5120
import java.util.Scanner;
import java.util.Arrays;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int number=3;
    int array[]=new int[number];
    for(int i=0;i<number;i++){
      array[i]=sc.nextInt();
    }
    Arrays.sort(array);
    for(int i=0;i<number-1;i++) System.out.print(array[i]+" ");
    System.out.println(array[number-1]);
      sc.close();
  }
}


Measured memory_bytes: 26320
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

// ??????????????§??????????????¢?´¢?????????????????????

int main(){
	
	map<string, vector<int> > m;
	map<string, vector<int> >::iterator ite;
	
	string str;
	int p;
	
	while(true){
		cin >> str;
		if(cin.eof()){
			break;
		}
		cin >> p;
		vector<int> v;
		ite = m.find(str);
		if(ite != m.end()){
			(ite -> second).push_back(p);
		}else{
			v.push_back(p);
			m.insert(make_pair(str, v));
			v.erase(v.begin(), v.end());
		}
	}
	
	for(ite = m.begin(); ite != m.end(); ite++){
		cout << ite -> first << endl;
		sort((ite -> second).begin(), (ite -> second).end());
		printf("%d", (ite -> second).at(0));
		for(int i = 1; i < (ite -> second).size(); i++){
			printf(" %d", (ite -> second).at(i));
		}
		printf("\n");
	}
	
	return 0;
}

Measured memory_bytes: 1268
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
template<typename T> using v2 = vector<vector<T>>;
template<typename T> inline v2<T> fill(int r, int c, T t){return v2<T>(r, vector<T>(c, t));}

void solve(){
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    vector<pair<int, int>> q(m);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> q[i].second >> q[i].first;

    priority_queue<int, vector<int>, greater<int>> pq(a.begin(), a.end());
    sort(q.begin(), q.end(), greater<pair<int, int>>());

    for(int i = 0; i < m; i++){
        for(int j = 0; j < q[i].second; j++){
            int top = pq.top();
            if(top >= q[i].first) goto end;
            pq.pop();
            pq.push(q[i].first);
        }
    }

    end:
    ll ans = 0;
    while(!pq.empty()){
        ans += pq.top();
        pq.pop();
    }
    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}


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


int gcd(long long n1, long long n2) {
  if(n1 == 1 || n2 == 1) return 1;
  if(n1 == 0 || n2 == 0) return max(n1,n2);
  if(n1 > n2) return gcd(n1%n2, n2);
  return gcd(n1,n2%n1);
}




int main() {
  int n;
  cin >> n;
  long long values[n];
  long long gcd_start[n];
  long long gcd_end[n];
  for(int i = 0; i < n; i++) cin >> values[i];
  long long x = values[0];
  gcd_start[0] = x;
  for(int i = 1; i < n;i++) {
    gcd_start[i] = gcd(gcd_start[i-1], values[i]);
  }
  long long y = values[n-1];
  gcd_end[n-1] = y;
  for(int i = n-2; i >= 0; i--) {
    gcd_end[i] = gcd(gcd_end[i+1],values[i]);
  }
  int large = 0;
  for(int i = 1; i < n-1; i++) {
    int x;
    x = gcd(gcd_start[i-1],gcd_end[i+1]);
    if(x > large) large = x;
  }
  if(gcd_end[1] > large) large = gcd_end[1];
  if(gcd_start[n-2] > large) large = gcd_start[n-2];
  cout << large;


}

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

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define LOOP(i) while(i--)
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

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

	double W;
	while(cin>>W){
		if(W<=48.0){
			out("light fly");
		}
		else if(W<=51.0){
			out("fly");
		}
		else if(W<=54.0){
			out("bantam");
		}
		else if(W<=57.0){
			out("feather");
		}
		else if(W<=60.0){
			out("light");
		}
		else if(W<=64.0){
			out("light welter");
		}
		else if(W<=69.0){
			out("welter");
		}
		else if(W<=75.0){
			out("light middle");
		}
		else if(W<=81.0){
			out("middle");
		}
		else if(W<=91.0){
			out("light heavy");
		}
		else{
			out("heavy");
		}
	}
	
	return 0;
}


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

int M, K;
int N;

void input_init(void) {
	cin >> M >> K;
	N = (1 << M);
}

void solve(void) {
	if (K >= N) {
		cout << "-1" << '\n';
		return;
	}
	if (M == 0) {
		if (K == 0)
			cout << "0 0" << '\n';
		else
			cout << "-1" << '\n';
		return;
	}
	if (M == 1) {
		if (K == 0)
			cout << "0 0 1 1" << '\n';
		else
			cout << "-1" << '\n';
		return;
	}
	for (int i = 0; i < N; ++i) {
		if (i == K) continue;
		cout << i << ' ';
	}
	cout << K << ' ';
	for (int i = N - 1; i >= 0; --i) {
		if (i == K) continue;
		cout << i << ' ';
	}
	cout << K << '\n';
}

int main(void) {
	input_init();
	solve();

	return 0;
}


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

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

	map<string, long long> m;
	for(int i = 0; i < N; i++){
		string s; cin >> s;
                sort(s.begin(), s.end());
                m[s]++;
    	}

	long long ans = 0;
	for(auto a : m){
		if(a.second != 1) ans += a.second * (a.second - 1) /2;
    }

	cout << ans;
	return 0;
}


Measured memory_bytes: 11136
import java.util.*;

public class Main {
    public static void main(String... args){

        Scanner scanner = new Scanner(System.in);

        // 展望台の数, 道の数
        int num_tenbou = scanner.nextInt();
        int num_michi = scanner.nextInt();

        //　展望台の高さの配列
        ArrayList<Double> arr_high = new ArrayList<Double>();
        // 自分が「良い展望台 = True」とする
        //      それを記録するリスト
        ArrayList<Boolean> arr_isGood = new ArrayList<Boolean>(num_tenbou);
        for(int i = 0; i < num_tenbou; i++){
            arr_isGood.add(true);
        }

        // 高さの入力
        for(int i = 0; i < num_tenbou; i++){
            double high = scanner.nextDouble();
            arr_high.add(high);
        }
        // 道の入力
        for(int i = 0; i < num_michi; i++){
            // 展望台Aと展望台Bが繋がっている
            int tenbou_a = scanner.nextInt();
            int tenbou_b = scanner.nextInt();

            // AとBの高さを比べて低い方を悪い展望にする;
            if (arr_high.get(tenbou_a - 1) > arr_high.get(tenbou_b - 1)){
                arr_isGood.set(tenbou_b - 1, false);
            } else if (arr_high.get(tenbou_a - 1) < arr_high.get(tenbou_b - 1)) {
                arr_isGood.set(tenbou_a - 1, false);
            } else {
                arr_isGood.set(tenbou_b - 1, false);
                arr_isGood.set(tenbou_a - 1, false);
            }

        }

        // 残っている良い展望台を数え上げて出力
        int ans = 0;
        for (int i = 0; i < num_tenbou ; i++){
            if(arr_isGood.get(i)){
                ans++;
            }
        }

        System.out.println(ans);

    }
}


Measured memory_bytes: 74572
#include<iostream>
using namespace std;
int main()
{
  int n,A,B;
  cin >> n >> A >> B;
  char a[n];
  cin>>a;
  int c1=0,c2=0;
  for(int i=0;i<n;i++)
  {
    if(a[i]=='c')
    {
      cout<<"No"<<endl;
      continue;
    }
    if(a[i]=='a')
    {
      if(c1< A+B)
      {
        c1++;
        cout<<"Yes"<<endl;
        continue;
      }
      else
        cout<<"No"<<endl;
    }
    if(a[i]=='b')
    {
      //c2++;
      if(c1< A+B && c2<B)
      {
        c1++;c2++;
        cout<<"Yes"<<endl;
        continue;
      }
      else
        cout<<"No"<<endl;
    }
  }
  return 0;
}
      


Measured memory_bytes: 3696
h,w = map(int, input().split())
a = [list(map(int,input().split())) for _ in range(h)]
mani = [[0,0,0,0] for _ in range(h*w)]

cnt=0
for i in range(h):
    for j in range(w):
        if j!=(w-1):
            if a[i][j]%2==1 and a[i][j]!=0:
                mani[cnt] = [i,j,i,j+1]
                cnt +=1
                a[i][j+1] +=1
        elif i!=(h-1):
            if a[i][j]%2==1 and a[i][j]!=0 :
                mani[cnt] = [i,j,i+1,j]
                cnt +=1
                a[i+1][j]+=1
print(cnt)
for k in range(cnt):
    print("{} {} {} {}".format(mani[k][0]+1, mani[k][1]+1, mani[k][2]+1, mani[k][3]+1))
                

Measured memory_bytes: 40952
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

#define DEBUG
#ifdef DEBUG
#define debug_printf printf
#else
#define debug_printf 1 ? 0 : printf
#endif

typedef long long int ll;
typedef vector<ll> Vl;
typedef vector<int> Vi;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pl;

#define FST first
#define SND second

const int MAX_N = 200000;                  // 10^5
// const int MAX_N = 100000;                  // 10^5
// const int MAX_N = 1000000000;              // 10^9
// const ll  MAX_N = 1000000000000000000;     // 10^18
// const int BASE  = 1000000000 + 7;          // 10^9 + 7
// const int INFI  = 1000000000 + 7;          // 10^9 + 7
const ll INFL  = 1000000000000000000 + 7; // 10^18 + 7

int N;
ll S[MAX_N + 1];

void solve() {
  ll ans = INFL;
  for (int i = 1; i < N; i++) {
    ans = min(ans, abs(S[N] - 2 * S[i]));
  }
  cout << ans << endl;
}

int main() {
  cin >> N;
  S[0] = 0;
  for (int i = 0; i < N; i++) {
    cin >> S[i + 1];
    S[i + 1] += S[i];
  }

  solve();

  return 0;
}


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

// macro
#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define all(v) v.begin(), v.end()

// code starts
int main()
{
  int n,k;cin>>n>>k;
  vector<int> a(n);
  int i,j;
  rep(i,n)cin>>a[i];
  vector<bool> first_win(k+1,false);
  rep(i,a[0])first_win[i]=false;
  for(i=a[0];i<=k;i++)
  {
    rep(j,n)
    {
      if(i-a[j]<0)break;
      if(!first_win[i-a[j]])
      {
        first_win[i]=true;
      }
    }
  }
  if(first_win[k])cout<<"First"<<endl;
  else cout<<"Second"<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SORT(x) sort(x.begin(),x.end())
#define ALL(x) x.begin(),x.end()
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define repr(i, m, n) for(int i = m; i >= n; i--)
#define INF 1000000007 //1000000000000000003
#define PI (acos(-1))
#define MOD 1000000007
using namespace std;
typedef long long ll;

void Main(){

  int a,b,c;
  cin>>a>>b>>c;

  if(a==b) cout<< c<<"\n";
  if(a==c) cout<< b<<"\n";
  if(b==c) cout<< a<<"\n";

}

//-----------------------------------
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}
//-----------------------------------


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  long N, X;

  std::cin >> N;
  std::cin >> X;

  std::vector<long> M(N);

  long ans = 0;

  for (size_t i=0; i<N; i++) {
    std::cin >> M[i];
    ans += 1;
    X -= M[i];
  }

  std::sort(M.begin(), M.end());

  for (auto const& m : M) {
    if (X < m) break;
    ans += X / m;
    X = X % m;
  }

  std::cout << ans << std::endl;

  return 0;
}


Measured memory_bytes: 256
s = int(input())
S = [s]

for i in range(1000000):
    if S[-1] % 2 == 0:
        x = S[-1]  // 2
    else:
        x = 3 * S[-1] + 1
    
    if x in S:
        break
    else:
        S.append(x)
        
print(i + 2)

Measured memory_bytes: 2940
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder.Contest.B
{
	class Program
	{
		public static void Main(string[] args)
		{
			var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
			Console.SetOut(sw);

			Scanner cin = new Scanner();

			long a = cin.nextLong();
			long b = cin.nextLong();
			long c = cin.nextLong();
			long k = cin.nextLong();

			long ans = Math.Min(k, a);
			if (k > a + b) ans -= (k - a - b);

			Console.WriteLine(ans);

			Console.Out.Flush();
		}
	}

	class Scanner
	{
		string[] s;
		int i;

		char[] cs = new char[] { ' ' };

		public Scanner()
		{
			s = new string[0];
			i = 0;
		}

		public string next()
		{
			if (i < s.Length) return s[i++];
			string st = Console.ReadLine();
			while (st == "") st = Console.ReadLine();
			s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
			if (s.Length == 0) return next();
			i = 0;
			return s[i++];
		}

		public int nextInt()
		{
			return int.Parse(next());
		}

		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = nextInt() + add;
			}
			return Array;
		}

		public long nextLong()
		{
			return long.Parse(next());
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = nextLong() + add;
			}
			return Array;
		}

		public double nextDouble()
		{
			return double.Parse(next());
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = nextDouble() + add;
			}
			return Array;
		}
	}
}

Measured memory_bytes: 27532
#include <string>
#include <algorithm>
#include <iostream>

using namespace std;

int main(void) {
	string s; cin >> s;
	sort(s.begin(), s.end());
	if (s[0] == s[1] && s[1] != s[2] && s[2] == s[3]) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
def main():
    n = int(input())
    d = list(map(int, input().split()))
    
    ans = 0

    for i in range(n - 1):
      for j in range(i + 1, n):
        ans += d[i] * d[j]

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
n, a, b = gets.split.map(&:to_i)
MOD = 10 ** 9 + 7

def power(x, n)
    return 1 if n == 0
    (n.even? ? 1 : x) * power(x ** 2 % MOD, n / 2) % MOD
end

def mul(s, t)
    (s..t).each.inject(1) {|r, v| r * v % MOD}
end

def comb(a, b)
    mul(a - b + 1, a) * power(mul(1, b), MOD - 2) % MOD 
end

puts (power(2, n) - 1 - comb(n, a) - comb(n, b)) % MOD

Measured memory_bytes: 1788
n, m, l = gets.split.map(&:to_i)
A = Array.new(n).map{Array.new(m)}
B = Array.new(m).map{Array.new(l)}
C = Array.new(n).map{Array.new(l,0)}
n.times do |i|
    A[i] = gets.split.map(&:to_i)
end
m.times do |i|
    B[i] = gets.split.map(&:to_i)
end
n.times do |i|
    l.times do |j|
        x = 0
        m.times do |k|
            x += A[i][k]*B[k][j]
        end
        C[i][j] = x
    end
end
C.each{|c| puts c.join(' ')}


Measured memory_bytes: 7508
#include <iostream>
#include <string>
#include <cstdint>
#include <algorithm>
#include <cmath>
#include <limits>
#include <numeric>
#include <map>
#include <tuple>
namespace math{
	std::map<uint64_t,uint32_t> g_tmp;
	uint32_t gcd(uint32_t a, uint32_t b) {
		//const auto key = (uint64_t)a | ((uint64_t)b) << 32;
		//const auto end_it = g_tmp.end();
		//auto it = g_tmp.find(key);
		//if (it != end_it) {
		//	return it->second; 
		//}
		for (;;) {
			if (a < b) {
				std::swap(a, b);
			}
			
			{
				if (a==b || b==0) {
//					g_tmp.insert(std::make_pair(key, a));
					return a;
				}
				//const uint64_t key2 = (uint64_t)a| ((uint64_t)b)<<32;
				//auto it = g_tmp.find(key2);
				//if (it != end_it){
				//	g_tmp.insert(std::make_pair(key, it->second));
				//	return it->second;
				//}
			}

			int32_t v = a - b;
			const auto tmp = a;
			a = b;
			if (v > 0) {
				b = v;
			}
			else {
				b = tmp % b;
			}
		}
	}

	uint32_t gcd(uint32_t a, uint32_t b, uint32_t c) {
		const auto tmp_v= gcd(a, b);
		return tmp_v==c?c:gcd(tmp_v, c);
	}
}

int main()
{
	uint32_t n = 0;
    std::cin >> n;
	uint64_t result = 0;
	std::map<std::tuple<uint32_t, uint32_t, uint32_t>, uint32_t> vals_tbl;

	for (uint32_t a = 1; a <= n;++a) {
		for (uint32_t b = 1; b <= n; ++b) {
			for (uint32_t c = 1; c <= n; ++c) {
				uint32_t tmp[]{ a,b,c };
				std::sort(std::begin(tmp), std::end(tmp));
				//const auto key = std::make_tuple(tmp[0], tmp[1], tmp[2]);
				//auto it = vals_tbl.find(key);
				//if (it != vals_tbl.end()) {
				//	result += it->second;
				//}
				//else {
					const auto ret = math::gcd(tmp[0], tmp[1], tmp[2]);
					result += ret;
				//	vals_tbl.insert(std::make_pair(key, ret));
				//}
				
			}
		}
	}
	std::cout << result << std::endl;
	return 0;
}



Measured memory_bytes: 3196
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
const int MAX = 1e5 + 10;
const double exps = 1e-8;

inline int max(int a, int b) { return a > b ? a : b; }
inline int min(int a, int b) { return a > b ? b : a; }

int main() {
    ll x;
    cin >> x;
    ll a = 1000 * (x / 500);
    x = x - (x / 500) * 500;
    cout << a + 5 * (x / 5);
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
using namespace std;
typedef long long ll;
#define ALL(v) (v).begin(), (v).end()
const int mod = 1e9+7;

int main() {
    string S;
    cin >> S;
    bool flg = false;
    for (int i = 0; i < (int)S.size()-1; i++) {
        if (S[i] == S[i+1]) {
            cout << i+1 << " " << i+2 << endl;
            return 0;
        }
    }

    for (int i = 0; i < (int)S.size()-1; i++) {
        if (S[i] == S[i+2]) {
            cout << i+1 << " " << i+3 << endl;
            return 0;
        }
    }
    
    cout << "-1 -1" << endl;
    return 0;
}


Measured memory_bytes: 512
import sys
# import numpy as np
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))
# import profile

def solve():
	n, w = read(); 
	dp = [[0 for i in range(w+1)] for j in range(n)]
	w_v_list = [read() for i in range(n)]
	# for i in dp:print(*i)
	# print("\n")
	# print(w_v_list)
	for i in range(n):
		for j in range(w+1):
			elem_w, elem_v = w_v_list[i]
			if elem_w <= j:
				dp[i][j] = max(elem_v + dp[i-1][j - elem_w], dp[i][j-1], dp[i-1][j])
				# w_v_list[i][1] = 0
			else:
				dp[i][j] = max(dp[i][j-1], dp[i-1][j])
	# for i in dp:print(*i)
	print(dp[n-1][w])




if __name__ == "__main__":
	solve()

Measured memory_bytes: 111208