akhauriyash/Code-Regression huggingface dataset:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
a = [list(map(lambda x: int(x) - 1, readline().split())) for _ in range(n)]
q = list(range(n))
cnt = 0
while q:
    cnt += 1
    qq = set()
    while q:
        x = q.pop()
        if a[a[x][0]][0] == x:
            qq.add(x)
            qq.add(a[x][0])
    if qq:
        for x in qq:
            a[x].pop(0)
            if a[x]:
                q.append(x)
    else:
        print(-1)
        exit()
print(cnt)


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

int main() {
  int A,B;
  cin >> A >> B;
  if(A==B){
    cout << "Draw" << endl;
  }else if(A==1 || (A>B && B != 1)){
    cout << "Alice" << endl;
  }else{
    cout << "Bob" << endl;
  }
}


Measured memory_bytes: 256
# 数のbitに含まれる1の数をカウント
def bitsoncount(x):
    return bin(x).count('1')

def solve(x):
    global ans
    bx = bitsoncount(x)
    if bx == 0:
        return ans
    else:
        ans += 1
        x = x % bx
        solve(x)


N = int(input())
X = input()

Xb = bitsoncount(int(X, 2))
if (Xb - 1) != 0:
    X0 = int(X, 2) % (Xb-1)
X1 = int(X, 2) % (Xb+1)

for x, i in zip(X, reversed(range(N))):
    x = int(x)
    if x == 0:
        temp = (X1 + pow(2, i, Xb+1)) % (Xb+1)
        ans = 1
    else:
        if Xb - 1 == 0:
            print(0)
            continue
        temp = (X0 - pow(2, i, Xb-1)) % (Xb-1)
        ans = 1
    
    solve(temp)
    print(ans)

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

int main() {
  ll n, k;
  cin >> n >> k;
  int d = 0;
  while ((1LL << d) <= k) d++;

  ll nums[61] = {};
  for (int i = 0; i < n; i++) {
    ll a;
    cin >> a;
    for (int j = 0; j < 61; j++) {
      nums[j] += (a & (1LL << j)) >> j;
    }
  }

  ll dp_limit = 0, ans = 0;
  bool limit = true;

  for (int i = 60; i >= 0; i--) {
    if (i < d) {
      if ((k & (1LL << i)) == 0) {
        if (!limit) {
          if (nums[i] >= n - nums[i]) ans += nums[i] * (1LL << i);  // select 0
          else ans += (n - nums[i]) * (1LL << i);   //select 1
        }
        dp_limit += nums[i] * (1LL << i);   // select 0
      }
      else {
        if (nums[i] >= n - nums[i]) {   // select 0
          ans = max(ans, dp_limit) + nums[i] * (1LL << i);
          dp_limit += nums[i] * (1LL << i);
          limit = false;
        }
        else {    // select 1
          if (!limit) ans += (n - nums[i]) * (1LL << i);
          else {
            ans = dp_limit + nums[i] * (1LL << i);  // select 0
            limit = false;
          }
          dp_limit += (n - nums[i]) * (1LL << i);
        }
      }

    }
    else {
      dp_limit += nums[i] * (1LL << i);
    }
  }

  cout << max(ans, dp_limit) << endl;

  return 0;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class AtCoderD
{
    static void Main()
    {
        string s = Console.ReadLine();
        int q = int.Parse(Console.ReadLine());

        bool isReverse = false;
        StringBuilder sbAfter = new StringBuilder();
        StringBuilder sbBefore = new StringBuilder();
        for (int i = 0; i < q; i++)
        {
            string line = Console.ReadLine();
            var words = line.Split(' ');
            int type1 = int.Parse(words[0]);
            if (type1 == 1)
            {
                isReverse = !isReverse;
            }
            else
            {
                int type2 = int.Parse(words[1]);
                string str = words[2];
                if ((!isReverse && (type2 == 2)) || (isReverse && (type2 == 1)))
                {
                    sbAfter.Append(str);
                }
                else
                {
                    sbBefore.Append(str);
                }
            }
        }
        string answer = "";
        if (isReverse)
        {
            answer = Reverse(sbAfter.ToString()) + Reverse(s) + sbBefore.ToString();
        }
        else
        {
            answer = Reverse(sbBefore.ToString()) + s + sbAfter.ToString();
        }

        Console.WriteLine(answer);
    }

    private static string Reverse(string s)
    {
        return string.Join("", s.Reverse());
    }
}

Measured memory_bytes: 17976
n,m = map(int,input().split())
cake = [[int(i) for i in input().split()] for _ in range(n)]
ans = 0
for i in range(2<<3):
    s = []
    for j in range(n):
        cnt = 0
        for k in range(3):
            if i>>k & 1: cnt += cake[j][k]
            else: cnt -= cake[j][k]
        s.append(cnt)
    s.sort(reverse=True)
    ans = max(ans, sum(s[:m]))
print(ans)

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

int f(int bfr){
    int ret;
    if(bfr%2 == 0){
        ret = bfr / 2;
    }else{
        ret = 3*bfr + 1;
    }
    return(ret);
}

int main(void){
    int res, i;
    int flag = 0;
    int a, old_a;

    cin >> old_a;

    if(old_a == 1 || old_a == 2 || old_a == 4){
        i = 2;
    }else{
        for(i = 1;; i++){
            a = f(old_a);
            //cout << a << endl;

            if(a==1) break;
            old_a = a;
        }
    }
    cout << i+2;
    return 0;
}

Measured memory_bytes: 256
from collections import deque

s = input()
q = int(input())

reverse = False
count = 0
s = deque(s)
for i in range(q):
    qu = input()
    if qu[0] == "1":
        count += 1
        if reverse:
            reverse = False
        else:
            reverse = True
    else:
        _, f, c = qu.split()
        if reverse:
            if f == "1":
                s.append(c)
            else:
                s.appendleft(c)
        else:
            if f == "1":
                s.appendleft(c)
            else:
                s.append(c)

s = "".join(s)

if count % 2:
    print(s[::-1])
else:
    print(s)


Measured memory_bytes: 8436
import sys
sys.setrecursionlimit(10 ** 7)

n, a, b, c = map(int, input().split())
s = [input() for _ in range(n)]

ans = []

d = {"A": a, "B": b, "C": c}


def dfs(i):
    if min(d.values()) < 0:
        return

    if i == n:
        print("Yes")
        print(*ans, sep="\n")
        exit()

    k1, k2 = s[i]

    d[k1] += 1
    d[k2] -= 1
    ans.append(k1)
    dfs(i+1)
    d[k1] -= 1
    d[k2] += 1
    ans.pop()

    d[k2] += 1
    d[k1] -= 1
    ans.append(k2)
    dfs(i+1)
    d[k2] -= 1
    d[k1] += 1
    ans.pop()


dfs(0)

print("No")


Measured memory_bytes: 105184
n = int(input())
s = input()
tmp = s

while True:
    if tmp.count("()") == 0:
        break
    tmp = "".join(tmp.split("()"))

x = 0
y = 0
for c in tmp:
    if c == ")":
        x += 1
    else:
        y += 1

ans = "("*x + s + ")"*y
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <set>
#include <functional>
#include <utility>
#include <fstream>

using namespace std;

#define ll long long
#define INF 2000000000
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define dum(x) cout<<#x<<'='<<x<<endl
#define darr(arr,n) rep(i,(n-arr)){cout<<*(arr+i)<<' ';}cout<<endl;



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

    if (S.size() == 1) {
        cout << 0 << endl;
        return 0;
    }
    int cou = 0;
    rep(i, S.size()-1) {
        if (S[i] != S[i + 1]) {
            cou++;
        }
    }
    cout << cou << endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
long long ans;
int main()
{
	long long n;
	scanf("%lld",&n);
	for(long long i=1;i<=sqrt(n);i++)
	 if(n%i==0){
	 	long long m=n/i-1;
	 	if(i<m)ans+=m;
	 }
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define MXN 101
#define MXW 100010
long long dp[MXN][MXW], v[MXN], w[MXN];

long long knapsack(long long ind, long long weight)
{
	if(ind==1) 
	{
		if(weight<w[ind]) return 0ll;
		else return v[ind];
	}
	if(dp[ind][weight]!=0ll) return dp[ind][weight];
	if(weight<w[ind]) return dp[ind][weight] = knapsack(ind-1ll, weight);
	return dp[ind][weight] = max(knapsack(ind-1ll, weight), v[ind]+knapsack(ind-1ll, weight-w[ind]));
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	long long N; cin>>N;
	long long W; cin>>W;
	for(long long i=1ll; i<=N; i++) cin>>w[i]>>v[i];

	cout << knapsack(N, W) << '\n';
	return 0;
}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define collect(arr, size) rep(i,size) cin >> arr[i];
#define int long long

signed main(){
    int H,W; cin >> H >> W;
    int lh = H/2, lw = W/2, sh = H/2, sw = W/2;
    if(H%2==1) lh++;
    if(W%2==1) lw++;
    int ans = (W==1 || H==1) ? 1 : lh*lw + sh*sw;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
    int N;
    cin >> N;

    int count = 0;
    int now_num = 1;
    int64_t sum = 0;
    while (count < N) {
        if (now_num % 3 == 0 || now_num % 5 == 0) {
        } else {
            sum += now_num;
        }
        count += 1;
        now_num += 1;
    }

    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 3592
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <numeric>
#include <unordered_map>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <memory>
#include <iomanip>
#include <type_traits>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
//constexpr long long MOD = 1e9 + 7;
//constexpr long long MAX = 1000000;

//long long MOD = 998244353;
constexpr ll INF = 1e17;
constexpr double PI = 3.141592653589793;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

ll h, w;
vector<ll> dx = { -1, 0, 1, 0 };
vector<ll> dy = { 0, -1, 0, 1 };


bool isInField(ll x, ll y) {
    bool f = x >= 0 && x < w && y >= 0 && y < h;
    return f;
}

bool compare_first(pair<ll, ll> x, pair<ll, ll> y)
{
    if (x.first != y.first) {
        return x.first < y.first;
    }
    else {
        return x.second < y.second;
    }
}

bool compare_second(pair<ll, ll> x, pair<ll, ll> y)
{
    if (x.second != y.second) {
        return x.second < y.second;
    }
    else {
        return x.first < y.first;
    }
}

struct {
    bool operator()(pair<string, int> x, pair<string, int> y) const
    {
        return x.second <= y.second && x.first < y.first;
    }
} compare_map;

const ll MAX = 500000000;
const ll MOD = 1000000007;

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

    int n, m;
    cin >> n >> m;
    vector<int> s(m);
    vector<char> c(m);
    for (int i = 0; i < m; i++)
    {
        cin >> s[i] >> c[i];
        s[i]--;
    }

    for (int i = 0; i < 1000; i++)
    {
        bool ok = true;
        string is = to_string(i);
        if (is.size() != n) {
            continue;
        }

        for (int j = 0; j < m; j++)
        {
            if (is[s[j]] != c[j]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            cout << is << "\n";
            return 0;
        }
    }

    cout << -1 << "\n";

    return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {

		Scanner s = new Scanner(System.in);
		String str = s.next();
		char[] cha = new char[str.length()];
		int count = 0;
		loop: for (int i = str.length() - 1; i >= 0; i--) {
			if (str.charAt(i) != 'B') {
				cha[count] = str.charAt(i);
				count++;
			} else {
				int bcount = 0;
				while (str.charAt(i) == 'B') {
					if (i > 0) {
						bcount++;
						i--;
					} else {
						break loop;
					}
				}
				i -= bcount - 1;
			}
		}
		char[] cha2 = new char[count];
		for (int i = 0; i < count; i++) {
			cha2[i] = cha[count - i - 1];
		}
		System.out.println(String.valueOf(cha2));
	}
}

Measured memory_bytes: 9428
#include <iostream>
#include <set>
#include <map>
using namespace std;

class Point{
public:
  int x,y,z;
  bool operator<(const Point &a)const{
    if(x!=a.x) return x<a.x;
    else if(y!=a.y) return y<a.y;
    else return z<a.z;
  }
};

int main(void){
  int n,h;
  while(cin>>n>>h,n||h){
    set<Point> ps;
    for(int i=0,a,b;i<h;++i){
      string c;
      cin>>c>>a>>b;
      if(c=="xy"){
        for(int i=0;i<n;++i){
          Point p={a,b,i+1};
          ps.insert(p);
        }
      }else if(c=="xz"){
        for(int i=0;i<n;++i){
          Point p={a,i+1,b};
          ps.insert(p);
        }
      }else if(c=="yz"){
        for(int i=0;i<n;++i){
          Point p={i+1,a,b};
          ps.insert(p);
        }
      }
    }
    cout<<(n*n*n-ps.size())<<endl;
  }
  return 0;
}

Measured memory_bytes: 4328
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

typedef pair<int, int> P;

const int INF = 330000;
int n, m, s, t;
vector<int> edge[330000];
bool done[330000];

int bfs(int u) {
  queue<P> q;
  
  q.push(P(u, 0));
  
  while (q.size()) {
    P p = q.front();
    q.pop();
    u = p.first;
    int dist = p.second;
    for (int v: edge[u]) {
      if (v == t) return (dist + 1) / 3;
      if (done[v]) continue;
      q.push(P(v, dist + 1));
      done[v] = true;
    }
  }
  
  return -1;
}

int main() {
  cin >> n >> m;
  
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--;
    v--;
    edge[u].push_back(v+n);
    edge[u+n].push_back(v+2*n);
    edge[u+2*n].push_back(v);
  }
  
  cin >> s >> t;
  s--;
  t--;
  
  cout << bfs(s) << endl;
  return 0;
}


Measured memory_bytes: 17664
//FA専用
#include <bits/stdc++.h>
using namespace std;
#define int long long
const long long LINF=1e18;
using ld=long double;
template<typename T>
void chmax(T &a,T b){
  if(a<b)a=b;
}
template<typename T>
void chmin(T &a,T b){
  if(a>b)a=b;
}
template<typename T>
void fin(T a){
  cout<<a<<endl;
  exit(0);
}

typedef pair<int,int> P;
int d[2345];

signed main(){
  int x,y,a,b,c;cin>>x>>y>>a>>b>>c;
  vector<int> r(a),g(b),w(c);
  for(int i=0;i<a;i++)cin>>r[i];
  for(int i=0;i<b;i++)cin>>g[i];
  for(int i=0;i<c;i++)cin>>w[i];
  int ans=0;
  sort(r.rbegin(),r.rend());
  sort(g.rbegin(),g.rend());
  for(int i=0;i<x;i++)w.push_back(r[i]);
  for(int i=0;i<y;i++)w.push_back(g[i]);
  sort(w.rbegin(),w.rend());
  for(int i=0;i<x+y;i++)ans+=w[i];
  cout<<ans<<endl;
}


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

int main()
{
	cout << fixed << setprecision(10);
	int N;
	cin >> N;
	vector<vector<ld>> dp(N + 1, vector<ld>(N + 1));
	dp[0][0] = 1;
	for (int i = 0; i < N; i++) {
		ld p;
		cin >> p;
		for (int j = 0; j <= N; j++) {
			if (j + 1 <= N) dp[i + 1][j + 1] += dp[i][j] * p;
			dp[i + 1][j] += dp[i][j] * (1 - p);
		}
	}
	cout << accumulate(dp[N].begin() + (N + 1) / 2, dp[N].end(), (ld)0) << endl;
	return 0;
}


Measured memory_bytes: 141056
function main()
    n = parse(Int, readline())
    ans = 0
    a = zeros(Int, n)
    for i in 1:n
        for j in i:i:n
            a[j] += 1
        end
    end

    for i in 1:n
        ans += i*a[i]
    end
    println(ans)
end

main()

Measured memory_bytes: 236440
n = int(input())
a = list(map(int, input().split()))
c = 0
flag = True
while flag:
    flag = False
    for j in range(n - 1, 0, -1):
        if a[j] < a[j - 1]:
            t = a[j]
            a[j] = a[j - 1]
            a[j - 1] = t
            c += 1
            flag = True
print(*a)
print(c)

Measured memory_bytes: 5600
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int board[2][101];
int d[2][101];
int n;
int go(int x,int y){
    
    if(x>1 || y>n-1) return -987654321;
    
    if(x==1 && y==n-1) return board[x][y];
    
    int &ans = d[x][y];
    if(ans != -1) return ans;
    ans = 0;
    ans = max(go(x+1,y), go(x,y+1)) + board[x][y];
    
    return ans;
    
}
int main(int argc, const char * argv[]) {
   
    
    scanf("%d",&n);
    
    for(int i=0;i<2;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&board[i][j]);
        }
    }
    
    memset(d,-1,sizeof(d));
    
    printf("%d\n",go(0,0));
    
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include <cmath>
using namespace std;
int main(void){
    int a,b,c,d;
    while(cin>>a>>b>>c>>d){
        if(abs(a-c)<=d || (abs(a-b)<=d&&abs(b-c)<=d)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

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

using namespace std;

#define REP(i,m) for(long long i=0; i<m; i++)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define INF 1000000001
#define INFL (1LL << 60)
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int
#define P pair<ll, ll>

int main() {
  int n;
  cin >> n;
  int a[n], b[n];
  REP(i, n) cin >> a[i];
  REP(i, n) b[i] = a[i];
  sort(b, b+n);
  int r = b[n/2-1], l = b[n/2];
  REP(i, n){
    if(a[i] <= r) cout << l << endl;
    else cout << r << endl; 
  }
  return 0;
}


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

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

  for(int i = 0; i < 10; ++i) {
    for(int j = 9; j > i; --j) {
      if(a[j] < a [j - 1]) {
        int t = a[j];
        a[j] = a[j - 1];
        a[j - 1] = t;
      }
    }
  }

  for(int i = 9; i > 6 ; --i) {
    cout << a[i] << endl;
  }
}

Measured memory_bytes: 3088
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ll long long
#define lld long double
#define ALL(x) x.begin(), x.end()
#ifdef DEBUG
#define line() cerr << "[" << __LINE__ << "] ";
#define dump(i) cerr << #i ": " << i << " ";
#define dumpl(i) cerr << #i ": " << i << endl;
#else
#define line(i)
#define dump(i)
#define dumpl(i)
#endif
using namespace std;

int main(int argc, char const *argv[])
{
    ll n;
    cin >> n;
    ll i = 1;
    ll ans = (1ll << 60);
    while (i * i <= n)
    {
        if (n % i == 0)
        {
            ans = min(ans, (i - 1) + (n / i - 1));
        }
        i++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
//#define _GRIBCXX_DEBUG
#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;


// 基本テンプレート
#pragma region MACRO
#define P(x) cout << (x) << endl
#define p(x) cout << (x)
#define PED cout << "\n"
#define rep(i,n) for(int i=0; i<(int)n; ++i)
#define REP(i,x,n) for(int i=x; i<(int)n; ++i)
#define repi(i,n) for(int i=0; i<=(int)n; ++i)
#define REPI(i,x,n) for(int i=x; i<=(int)n; ++i)
#define ILP while(true)
#define FOR(i,c) for(__typeof((c).begin())!=(c).begin(); i!=(c).end(); ++i)
#define ALL(c) (c).begin(), (c).end()
#define mp make_pair
#pragma endregion

// 型
#pragma region TYPE_DEF
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
typedef pair<string, int> psi;
typedef pair<int, string> pis;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long> vl;
typedef vector<long long> vll;
typedef vector<string> vs;
#pragma endregion

// Effective std
#pragma region ESTD
template<typename C, typename T>
int count(C& c, T t) { return count(ALL(c), t); }
template<typename C, typename F>
int count_if(C& c, F f) { return count_if(ALL(c), f); }
template<typename C, typename T>
void erase(C& c, T t) { remove(ALL(c), t), c.end(); }
template<typename C>
void remove(vector<C>& c, unsigned int index) { c.erase(c.begin()+index); }
template<typename C, typename T, typename U>
void replace(C& c, T t, U u) { replace(ALL(c), t, u); }
template<typename C, typename F, typename U>
void replace_if(C& c, F f, U u) { (ALL(c), f, u); }
template<typename C>
void reverse(C& c) { reverse(ALL(c)); }
template<typename C>
void sort(C& c) { sort(ALL(c)); }
template<typename C, typename Pred>
void sort(C& c, Pred p) { sort(ALL(c), p); }
#pragma endregion

// 定数
#pragma region CONST_VAL
#define PI (2*acos(0.0))
#define EPS (1e-9)
#define MOD (int)(1e9+7)
#pragma endregion


int main()
{
    string s;
    cin >> s;
    vi ret(100000, 0);
    rep(i,s.size()) {
        ret[s[i]]++;
    }

    rep(i,ret.size()) {
        if(ret[i]%2!=0) {
            P("No");
            return 0;
        }
    }
    P("Yes");
    return 0;
}



Measured memory_bytes: 640
import java.util.Scanner;

class Main
{
	public static void main(String args[])
	{
		Scanner sc = new Scanner(System.in);
		
		while (true)
		{
			double x = sc.nextInt();
			double h = sc.nextInt();
			if (x == 0.0 && h == 0.0) break;
			double a = Math.sqrt((x / 2)*(x / 2) + h * h);
			System.out.println(x * x + x * a * 2);
		}
	}
}

Measured memory_bytes: 12000
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    int n; cin>>n;
    if(n%2) cout<<n/2<<endl;
    else cout<<n/2-1<<endl;
}


Measured memory_bytes: 3612
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
/*int main()
{
	int n; cin>>n;
	int a[n];
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a,a+n);
//	for(int i=0;i<n;i++) cout<<a[i];
	int sum=0;
	for(int i=n-1;i>1;i--)
	{
		for(int j=i-1;j>0;j--)
		{
			if(a[i]==a[j]) continue;
			for(int k=j-1;k>=0;k--)
			{
				if(a[k]!=a[i] and a[k]!=a[j] and a[i] < (a[k] + a[j])) 
				{
					sum++;
				}
				
				if(a[k]!=a[i] and a[k]!=a[j] and a[i] >= (a[k] + a[j])) 
				{
					break;
				}
				
			}
		}
	}
	
	cout<<sum;
}

int main()
{
	int n,d,ans=0;
	cin>>n>>d;
	while(n--)
	{
		int a,b; cin>>a>>b;
		long long int fl=a*a + b*b;
		float sum=sqrt(fl);
		if(sum<=d) ans++;
		
	}
	cout<<ans;
}*/
int main()
{
	int n,k; cin>>n>>k;
	int a[n],sum=0;
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a,a+n);
	for(int i=0;i<k;i++) sum+=a[i];
	cout<<sum; 
}


Measured memory_bytes: 3184
#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)
using namespace std;
using ll = long long;
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(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U& u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U& u,const V... v){for(auto& e:u)fill_v<T>(e,v...);}

struct edge { int to; long long weight;};
vector<vector<edge>> g;

vector<long long> dijkstra(int s) {
    vector<long long> dist(g.size(), numeric_limits<long long>::max());
    dist[s] = 0;
    using P = pair<long long, long long>;
    priority_queue<P, vector<P>, greater<P>> que;
    que.push(P(0, s));
    while (!que.empty()) {
        P p = que.top();
        que.pop();
        int v = p.second;
        if (dist[v] < p.first) continue;
        for (edge e : g[v]) {
            if (dist[e.to] > dist[v] + e.weight) {
                dist[e.to] = dist[v] + e.weight;
                que.push(P(dist[e.to], e.to));
            }
        }
    }
    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    cin >> n >> m;
    g.resize(n);
    rep(i, m) {
        int l, r, c;
        cin >> l >> r >> c;
        l--; r--;
        g[l].push_back({r, c});
        g[r].push_back({l, c});
    }
    rep(i, n-1) g[i+1].push_back({i, 0});
    auto dist = dijkstra(0);
    ll ans = dist[n-1];
    cout << (ans == numeric_limits<ll>::max() ? -1 : ans) << endl;
}


Measured memory_bytes: 15308
#include<stdio.h>
#include<iostream>
using namespace std;
 
int main()
{
    long N,K;
    long min;
  	cin>>N>>K;
 
	min=N%K;
 
    if(min>K-min)
      	min=K-min;
 
 
	cout<<min<<endl;
  
    return 0;
}

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

int main(){
    int a, b, m;
    cin >> a >> b >> m;
    vector<int> x(a);
    for (int i = 0; i < a; i++) cin >> x[i];
    vector<int> y(b);
    for (int i = 0; i < b; i++) cin >> y[i];
    int ans = 2e9;
    int p, q, r;
    for (int i = 0; i < m; i++)
    {
        cin >> p >> q >> r;
        ans = min(ans, x[p - 1] + y[q - 1] - r);
    }
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    ans = min(ans, x[0] + y[0]);
    cout << ans << endl;
}


Measured memory_bytes: 1024
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def solve(K: int, N: int, A: "List[int]"):

    B = [abs((A[i]-A[i-1]) % K) for i in range(N)]
    print(K-max(B))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(K, N, A)


if __name__ == '__main__':
    main()


Measured memory_bytes: 27764
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int n;
  cin>>n;
  map<int,int> m;
  for(int i=0;i<n;i++){
    int x;
    cin>>x;
    m[x]++;
  }
  int ans=0;
  for(auto p:m){
    int x=p.first;
    int t=0;
    t+=m.count(x-1)?m[x-1]:0LL;
    t+=m.count(x)?m[x]:0LL;
    t+=m.count(x+1)?m[x+1]:0LL;
    ans=max(ans,t);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 4224
#include<bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=100000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};


int main() {

	int a,b,c;
	int x=0,y=0;

	cin>>a>>b>>c;

	if(a==5){
		x++;;
	}
	if(a==7){
		y++;
	}

	if(b==5){
		x++;;
	}
	if(b==7){
		y++;
	}
	if(c==5){
		x++;;
	}
	if(c==7){
		y++;
	}

	if(x==2&&y==1){
		cout<<"YES"<<endl;
	}else{
		cout<<"NO"<<endl;
	}



	return 0;
}


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

int main(){
    int x,n;
    cin >> x >> n;
    vector <int> a;
    int i,j;
    for(i=0;i<n;i++){
        cin >> j;
        a.push_back(j);
    }
    int ans;
    for(i=0;i<100;i++){
        if(find(a.begin(),a.end(),x-i)==a.end()){
            ans=x-i;
            break;
        }
        if(find(a.begin(),a.end(),x+i)==a.end()){
            ans=x+i;
            break;
        }
    }
    /*
    for(i=0;i<n;i++)
        cout << a[i];
        */
    cout << ans;
}


Measured memory_bytes: 3628
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;

class Program
{
    static void Main(string[] args)
    {
        var input = Console.ReadLine().Split(" ");
        var N = int.Parse(input[0]);
        var K = long.Parse(input[1]);

        var line = Console.ReadLine().Split(" ");
        var A = new List<int>();
        var seenA = new List<bool>();
        seenA.Add(false);

        for (int i = 0; i < N; i++)
        {
           A.Add(int.Parse(line[i]));
            seenA.Add(false);
        };

        seenA[1] = true;
        int pos = -1;
        var log = new List<int>();
        log.Add(1);

        var next = A[0];
        while (true)
        {
            if (seenA[next])
            {
                pos = next;
                break;
            }
            seenA[next] = true;
            log.Add(next);

            next = A[next - 1];
        }

        var count = log.IndexOf(pos);
        for (int i = 0; i < count; i++)
        {
            K--;
            log.RemoveAt(0);

            if (K == 0) break;
        }
        if (K == 0) Console.WriteLine(log[0]);
        else Console.WriteLine(log.ElementAt((int)(K % log.Count)));
    }
}

Measured memory_bytes: 46052
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left
from itertools import product
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def LF(): return list(map(float, input().split()))
def LC(): return [c for c in input().split()]
def LLI(n): return [LI() for _ in range(n)]
def NSTR(n): return [input() for _ in range(n)]

def array2d(N, M, initial=0):
    return [[initial]*M for _ in range(N)]

def copy2d(orig, N, M):
    ret = array2d(N, M)
    for i in range(N):
        for j in range(M):
            ret[i][j] = orig[i][j]
    return ret


INF = float("inf")
MOD = 10**9 + 7


def main():
    N = INT()
    L = LI()
    L.sort()
    counter = 0
    for i in range(N):
        for j in range(i+1, N):
            for k in range(j+1, N):
                if L[i] == L[j] or L[j] == L[k]:
                    continue
                if L[i]+L[j] > L[k]:
                    counter += 1
                    # print(L[i], L[j], L[k])
    print(counter)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 9256
#include <iostream>
#include<math.h>
#include <algorithm>
#include<string>
using namespace std;

int reverse(int num)
{
        int rev = 0;
        while (num > 0) {
                rev = rev * 10 + num % 10;
                num /= 10;
        }
        return rev;
}

int main() {
        int A,B;
        int Ans = 0;

        cin >> A >> B;

        for(int i=A; i<=B; i++){
                int revNum = reverse(i);
                if(i==revNum) Ans++;
        }

        cout << Ans << endl;

        return 0;
}


Measured memory_bytes: 256
import java.util.*;

@SuppressWarnings("unchecked")
public class Main {
	// public static void printArray(int[] a) {
	// 	for (int i = 0; i < a.length; i++) {
	// 		System.out.print(a[i] + ", ");
	// 	}
	// 	System.out.println();
	// }

	// public static<T> void printArrayT(T[] a) {
	// 	for (int i = 0; i < a.length; i++) {
	// 		System.out.print(a[i] + ", ");
	// 	}
	// 	System.out.println();
	// }

	public static String joinInt(int[] a, String separator) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < a.length; i++) {
			if (i > 0) {
				sb.append(separator);
			}
			sb.append(a[i]);
		}
		return sb.toString();		
	}

	static int[] nextIntArray(Scanner sc, int N) {
		int[] arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}
		return arr;
	}

	static int UNDEF = -1;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		ArrayList<Integer>[] edges = new ArrayList[N + 1];
		for (int i = 0; i < M; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			if (edges[x] == null) {
				edges[x] = new ArrayList<>();
			}
			edges[x].add(y);
		}
		Stack<Integer> stack = new Stack<>();
		int[] L = new int[N + 1];
		Arrays.fill(L, UNDEF);
		for (int i = 1; i <= N; i++) {
			stack.push(i);
			while (stack.size() > 0) {
				int peek = stack.peek();
				if (L[peek] != UNDEF) {
					stack.pop();
					continue;
				}
				if (edges[peek] == null) {
					L[peek] = 0;
					stack.pop();
					continue;
				}
				boolean solved = true;
				for (int child : edges[peek]) {
					if (L[child] == UNDEF) {
						stack.push(child);
						solved = false;
					}
				}
				if (solved) {
					int max = 0;
					for (int child : edges[peek]) {
						assert L[child] != UNDEF;
						max = Math.max(max, L[child]);
					}
					L[peek] = max + 1;
					stack.pop();
				}
			}
		}
		int max = 0;
		for (int i = 1; i <= N; i++) {
			max = Math.max(max, L[i]);
		}
		System.out.println(max);
	}
}


Measured memory_bytes: 100200
#include <cstdio>
#include <vector>
#include <iostream>

const int STEP_NUM = 4;
const int STEP[STEP_NUM][STEP_NUM] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

const int MAX_SIZE = 1000;
char field[MAX_SIZE + 1][MAX_SIZE + 1];

using Position = std::pair<int,int>;

const int MAXN = 10;
Position locations[MAXN];
 
int H, W, N;

int get_shortest_distance(int current_HP)
{
	int sx = locations[current_HP-1].first;
	int sy = locations[current_HP-1].second;
	int ex = locations[current_HP].first;
	int ey = locations[current_HP].second;

	bool is_visit[MAX_SIZE + 1][MAX_SIZE + 1]={};
	is_visit[sx][sy]=true;

	std::vector<Position> frontier;
	frontier.push_back(Position{sx,sy});
	for(int step=0;step<W*H;step++)
	{
		std::vector<Position> next_frontier;
		for(auto p:frontier)
			for(int i=0;i<STEP_NUM;i++)
			{
				int nx = p.first+STEP[i][0];
				int ny = p.second+STEP[i][1];
				if(nx<0 || H<=nx) 		continue;
				if(ny<0 || W<=ny) 		continue;
				if(field[nx][ny]=='X') 	continue;
				if(is_visit[nx][ny]) 	continue;
				next_frontier.push_back(std::make_pair(nx,ny));
				is_visit[nx][ny] = true;
				if(nx==ex && ny==ey)	return step+1;
			}
		frontier = next_frontier;
	}
	return -1;
}

int solve()
{
	int total_step = 0;
	for(int i=1;i<N+1;i++)
		total_step += get_shortest_distance(i);
	return total_step;
}

int main()
{
	scanf("%d %d %d", &H, &W, &N);
	for(int i=0; i<H; i++)
		scanf("%s", field[i]);
	for(int i=0; i<H; i++)
		for(int j=0; j<W; j++)
		{
			int HP=-1;
			if(field[i][j]=='S')	HP=0;
			if(field[i][j]=='1')	HP=1;
			if(field[i][j]=='2')	HP=2;
			if(field[i][j]=='3')	HP=3;
			if(field[i][j]=='4')	HP=4;
			if(field[i][j]=='5')	HP=5;
			if(field[i][j]=='6')	HP=6;
			if(field[i][j]=='7')	HP=7;
			if(field[i][j]=='8')	HP=8;
			if(field[i][j]=='9')	HP=9;
			if(HP!=-1)
				locations[HP] = std::make_pair(i,j);
		}
	printf("%d\n", solve());
	return 0;
}

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

int main() {
  ll n;
  cin >> n;
  // vector<ll> v(n);
  // vector<ll> p(n);
  // rep(i,n){
  //   v[i] = i+1;
  //   p[i] = i+2;
  // }
  // rep(i,n-1) {
  //   ans += (i+1) % (i+2);
  // }
  cout << n * (n-1)/2  << endl;
  // cout << ans << endl;
  return 0;
}


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

typedef long long ll;
const ll InF = 1e15;

int main() {
  int N,N1;
  cin>>N;
  N1 = N;
  vector<ll> A(N);
  for (int i = 0; i < N; i++) cin>>A[i];
  ll ans;
  while (1) {
    int res; res = 0;
    sort(A.begin(),A.end());
    ll first = A[0];
    bool flag = true;
    for (int i = 1; i < N1; i++) {
      if (A[i]%first != 0) {
        flag = false;
        A[i] = A[i]%first;
      } else {
        A[i] = InF;
        res++;
      }
    }
    if (flag) {
      ans = first;
      break;
    }
    N1 -= res;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define REP(i, n) for(int i = 1; i < (int)(n); ++i)
using namespace std;

struct SegmentTree {
private:
    int length;
    vector<int> node;
public:
    SegmentTree(int N) {
        length = 1;
        while (length < N) length *= 2;
        node.resize(2 * length - 1, 0);
    }
    void update(int idx, int val) {
        idx += (length - 1);
        node[idx] = val;
        while (idx > 0) {
            idx = (idx - 1) / 2;
            node[idx] = node[2 * idx + 1] || node[2 * idx + 2];
        }
    }
    int getsum(int a, int b, int now = 0, int l = 0, int r = -1) {
        if (r < 0) r = length;
        if (r <= a || b <= l) return 0;
        if (a <= l && r <= b) return node[now];
        int vl = getsum(a, b, 2 * now + 1, l, (l + r) / 2);
        int vr = getsum(a, b, 2 * now + 2, (l + r) / 2, r);
        return vl || vr;
    }
};

int main() {
    int N;
    cin >> N;
    vector<SegmentTree> STT;
    rep(i, 26) {
        SegmentTree ST(N);
        STT.push_back(ST);
    }
    string S;
    cin >> S;
    rep(i, N) {
        STT[S[i] - 'a'].update(i, 1);
    }
    int Q;
    cin >> Q;
    rep(q, Q) {
        int x;
        cin >> x;
        if (x == 1) {
            int i;
            char c;
            cin >> i >> c;
            rep(j, 26) {
                if (STT[j].getsum(i - 1, i)) STT[j].update(i - 1, 0);
            }
            STT[c - 'a'].update(i - 1, 1);
        } else {
            int l, r;
            cin >> l >> r;
            int ans = 0;
            rep(j, 26) {
                if (STT[j].getsum(l - 1 , r)) ++ans;
            }
            cout << ans << "\n";
        }
    }
    return 0;
}


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

using ll = long long;
using P = pair<ll, char>;

const int INF = 1e9;
const int MOD = 1e9 + 7;

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

// 最大公約数（a > b）
ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}

// 最小公倍数（a > b）
ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

int main() {
  int N, M;
  cin >> N >> M;
  string s, t;
  cin >> s >> t;

  ll lcm_num = lcm(max(N, M), min(N, M));
  ll n = lcm_num / N;
  ll m = lcm_num / M;

  for (int i = 0; i < gcd(max(N, M), min(N, M)); i++) {
    if (s[i*m] != t[i*n]) {
      cout << -1 << endl;
      return 0;
    }
  }

  cout << lcm_num << endl;
  return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <assert.h>
#include <map>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <set>
#include <climits>

using namespace std;

const int N = 4;
const int N2 = 16;

static const int dx[4] = {0, -1, 0, 1};
static const int dy[4] = {1, 0, -1, 0};
static const char dir[4] = {'r', 'u', 'l', 'd'}; 


struct Node
{
	vector<int> puzzle;
	int space;
	int md;
};

class Npuzzle
{
private:
	Node s_node;
	int limit;
	vector<vector<int> > md;
	vector<int> path;
	int ans;
public:
	Npuzzle() {
		s_node = Node();
		vector<int> in;
		for (int i = 0; i < N2; ++i)
		{
			int tmp;
			cin >> tmp;
			if(tmp == 0) {
				tmp = N2;
				s_node.space = i;
			}
			in.push_back(tmp);
		}
		s_node.puzzle = in;
		set_md();
		s_node.md = get_md_sum(s_node.puzzle);
	}

	int get_md_sum(const vector<int>& puzzle) {
		int sum = 0;
		for (int i = 0; i < N2; ++i)
		{
			if(puzzle[i] == N2) continue;
			sum += md[i][puzzle[i]-1];
		}
		return sum;
	}

	void set_md() {
		md = vector<vector<int> >(N2, vector<int>(N2, 0));
		for (int i = 0; i < N2; ++i)
		{
			for (int j = 0; j < N2; ++j)
			{
				md[i][j] = abs(i / N - j / N) + abs(i % N - j % N);
			}
		}
	}

	bool dfs(Node cur_n, int depth, int pre) {
		if(cur_n.md == 0 ) {
			ans = depth;
			return true;
		}
		if(depth + cur_n.md > limit) return false;
		int s_x = cur_n.space / N;
		int s_y = cur_n.space % N;
		for (int i = 0; i < 4; ++i)
		{
			Node new_n = cur_n;
			int new_x = s_x + dx[i];
			int new_y = s_y + dy[i];
			if(new_x < 0  || new_y < 0 || new_x >= N || new_y >= N) continue; 
			if(max(pre, i) - min(pre, i) == 2) continue;
			int num = new_n.puzzle[new_x * N + new_y] - 1;
			// cout << dir[i] << endl;
			new_n.md -= md[new_x * N + new_y][new_n.puzzle[new_x * N + new_y] - 1];
			new_n.md += md[s_x * N + s_y][new_n.puzzle[new_x * N + new_y] - 1];
			swap(new_n.puzzle[new_x * N + new_y], new_n.puzzle[s_x * N + s_y]);
			// cout << new_n.space << endl;
			// cout << s_x << " "<< s_y << endl;
			// cout << new_x << " "<< new_y << endl;
			new_n.space = new_x * N + new_y;
			assert(get_md_sum(new_n.puzzle) == new_n.md);
			// return dfs(new_n, depth+1, i);
			if(dfs(new_n, depth + 1, i)){
				path[depth] = i;
				return true;
			}
		}
		return false;
	}

	void ida_star() {
		for (limit = s_node.md; limit < 1000; ++limit)
		{
			path.resize(limit);
			if(dfs(s_node, 0, -10)) {
				cout << limit << endl;
				string str = "";
				for (int i = 0; i < limit; ++i)
				{
					str += dir[path[i]];
				}
				// cout << str << endl;
				return;
			}
		}
	}

	void exec() {
		ida_star();
	}
};


int main() {
	Npuzzle np = Npuzzle();
	np.exec(); 
}

Measured memory_bytes: 3164
import numpy as np

S=np.asarray(list(input()))
cond1=(S[0]=="A") # 先頭が"A"であるかどうか
ci=(S=="C") # "C"かどうか
cond2=(ci[2:-1].sum()==1) # [2:-1]の間にちょうど1個出現するかどうか
Snac=S[np.logical_not(ci)][1:] # 先頭と"C"を除く
cond3=np.char.islower(Snac).all() # 上が全て小文字かどうか

if (cond1 and cond2 and cond3): # 全ての条件を満たすならOK
    print("AC")
else: # 満たさないならNG
    print("WA")

Measured memory_bytes: 12504
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
constexpr int mod=1000000007;
constexpr int mod1=998244353;
vector<int> dx={0,-1,0,1},dy={1,0,-1,0};
bool inside(int y,int x,int h,int w){
	if(y<h && y>=0 && x<w && x>=0) return true;
	return false;
}



int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	vector<pii> a(n);
	rep(i,n) cin >> a.at(i).second >> a.at(i).first;
	sort(a.begin(),a.end());
	ll sum=0;
	bool flg=true;
	rep(i,n){
		sum+=a.at(i).second;
		if(sum>a.at(i).first) flg=false;
	}
	if(flg) cout << "Yes" << endl;
	else cout << "No" << endl;
}


Measured memory_bytes: 1792
#include <cstdio>
#include <algorithm>
#include <queue>

const int INF = 0x1f1f1f1f;

const int N = 200100;

const int lgN = 20;

typedef int ST[lgN][N];

ST st[2];

int p[N];

int lg[N];

int inv[N];

int qi;
int q[N];

int n;

void build(int d) {
	for (int x = 0; (1 << x) <= n; x++) {
		int y = 1 << x;
		int h = y >> 1;
		for (int i = 0; i <= n - y; i++) {
			if (x == 0)
				st[d][x][i] = i % 2 == d ? p[i] : INF;
			else
				st[d][x][i] = std::min(st[d][x - 1][i], st[d][x - 1][i + h]);
		}
	}
}

int query(int l, int r) {
	int x = lg[r - l + 1];
	return std::min(st[l % 2][x][l], st[l % 2][x][r - (1 << x) + 1]);
}

void init() {
	for (int i = 0; (1 << i) + 1 <= n; i++)
		lg[1 << i] = i;
	for (int i = 2; i <= n; i++)
		lg[i] = lg[i] == 0 ? lg[i - 1] : lg[i];
}

struct pair {
	int l, r, val;
	friend bool operator < (const pair& a, const pair& b) {
		return a.val > b.val;
	}
};

pair make_pair(int l, int r) {
	return (pair){l, r, query(l, r)};
}

std::priority_queue<pair> pq;

void solve() {

	pq.push(make_pair(0, n - 1));

	while (!pq.empty()) {

		pair t = pq.top();
		pq.pop();

		q[qi++] = t.val;

		int i = inv[t.val];

		int j_ = query(i + 1, t.r);

		q[qi++] = j_;

		int j = inv[j_];

		if (t.l < i - 1) pq.push(make_pair(t.l, i - 1));
		if (i + 1 < j - 1) pq.push(make_pair(i + 1, j - 1));
		if (j + 1 < t.r) pq.push(make_pair(j + 1, t.r));

	}

}

int main(int argc, char *argv[]) {
	
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &p[i]);
		inv[p[i]] = i;
	}
		
	init();
	
	build(0);
	build(1);
	
	solve();
	
	for (int i = 0; i < qi; i++)
		printf("%d ", q[i]);
	putchar('\n');
	
	return 0;

}


Measured memory_bytes: 34808
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
  private static final int MAX = 44;

  public static void main(String[] args) {
    int[] fib = new int[MAX + 1];
    fib[0] = 1;
    fib[1] = 1;

    for(int i = 2; i <= MAX; i++) {
      fib[i] = fib[i - 1] + fib[i - 2];
    }

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    try {
      while(true) {
        int num = Integer.parseInt(br.readLine());
        if (num <= 0) { break; }
        System.out.println(fib[num]);
      }
    } catch (Exception e) {
      System.exit(0);
    }
  }
}

Measured memory_bytes: 24428
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define int long long
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vvi bit(2, vi(n+1));
    auto add = [&](int i, int x, int wh) {
        while(i <= n) {
            bit[wh][i] += x;
            i += i&-i;
        }
    };
    auto sum = [&](int i, int wh) {
        int res = 0;
        while(i) {
            res += bit[wh][i];
            i &= i-1;
        }
        return res;
    };
    auto get = [&](int i) {
        return i*sum(i, 0) + sum(i, 1);
    };
    auto plus = [&](int s, int t, int x) {
        add(s, x, 0);
        add(s, -x*(s-1), 1);
        add(t, -x, 0);
        add(t, x*(t-1), 1);
    };

    while(q--) {
        int t;
        cin >> t;
        if(t) {
            int s;
            cin >> s >> t;
            cout << get(t) - get(s-1) << '\n';
        } else {
            int s, x;
            cin >> s >> t >> x;
            plus(s, t+1, x);
        }
    }
}


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


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

  for (int i = 0; i <= n; ++i) {
    for (int j = 0; i + j <= n; ++j) {
      int num = i * 10000 + j * 5000;
      int num2 = n - (i + j);
      if ((y - num) / 1000 == num2) {
        cout << i << ' ' << j << ' ' << num2 << endl;
        return 0;
      }
    }
  }

  cout << -1 << ' ' << -1 << ' ' << -1 << endl;
  
  return 0;
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
typedef long long ll;
const int MOD = 10000;
//dp[i][j][k]はi日目にパスタjを食べて、i-1日目にパスタkを食べた時のi日目までのメニューの総数
ll dp[105][3][3];
int main(){
  char b;
  cin >> b;
  if(b=='A'){
    cout << 'T' << endl;
  }
  if(b == 'T'){
     cout << 'A' << endl;
  }
  if(b == 'C'){
    cout << 'G' << endl;
  }
  if(b == 'G'){
    cout << 'C' << endl;
  }
}


Measured memory_bytes: 256