akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>

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

using i32 = int;
using i64 = long long;
using ll = long long;

using namespace std;

template<class T> class Graph{
public:
    struct edge{
        int to;
        T cost;
        edge(int to,T cost):to(to),cost(cost){}
    };
    int N,M;
    vector<vector<edge>> g;
    Graph(int N,int M):N(N),g(N),M(M){}
    void add_edge(int a,int b,T cost = 1){
       g[a].emplace_back(b,cost);
    }
    void input(bool undirected = true,bool unweighted = true){
        for(int i = 0;i < M;i++){
            int a,b;
            T c = 1;
            cin >> a >> b;
            if(!unweighted) cin >> c;
            g[a].emplace_back(b,c);
            if(undirected) g[b].emplace_back(a,c);
        }
    }

};
template<class T> class LCA : public Graph<T>{
private:
    vector<vector<int>> par;
    vector<int> depth;
    int root;
public:
    LCA(int N): Graph<T>(N,N-1),par(40,vector<int>(N,-1)),depth(N){}
    void add_edge(int a,int b){
        Graph<T>::add_edge(a,b);
    }
    void input(){
        Graph<T>::input(true,true);
    }
    void dfs(int,int,int);
    void init(int);
    int lca(int,int);
};

template<class T>
void LCA<T>::dfs(int v,int p,int d) {
    par[0][v] = p;
    depth[v] = d;
    for(int i = 0;i < Graph<T>::g[v].size();i++){
        if(Graph<T>::g[v][i].to != p) dfs(Graph<T>::g[v][i].to,v,d+1);
    }
}

template<class T>
void LCA<T>::init(int root){
    dfs(root,-1,0);
    // initialize parent
    for(int k = 0;k + 1 < 40;k++){
        for(int v = 0;v < Graph<T>::N;v++){
            if(par[k][v] < 0) par[k+1][v] = -1;
            else par[k+1][v] = par[k][par[k][v]];
        }
    }
}

template<class T>
int LCA<T>::lca(int u,int v) {
    if(depth[u] > depth[v]) swap(u,v);
    for(int k = 0;k < 40;k++){
        if((depth[v] - depth[u]) >> k & 1){
            v = par[k][v];
        }
    }
    if(u == v) return u;
    for(int k = 39;k >= 0;k--){
        if(par[k][u] != par[k][v]){
            u = par[k][u];
            v = par[k][v];
        }
    }
    return par[0][u];
}

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

    int n;cin >> n;
    LCA<int> G(n);
    for(int i = 0;i < n;i++){
       int k;cin >> k;
       for(int j = 0;j < k;j++){
           int c;cin >> c;
           G.add_edge(i,c);
           G.add_edge(c,i);
       }
    }
    G.init(0);
    int q;cin >> q;
    while(q--){
        int u,v;cin >> u >> v;
        cout << G.lca(u,v) << '\n';
    }

}



Measured memory_bytes: 30776
n, money = map(int, input().split())

x = 0 #10000yen
y = 0 #5000yen
z = 0 #1000yen
check = 0

for x in range (n + 1) :
  for y in range (n + 1 - x) :
    z = n - x - y
    if check == 1 :
      check = 1
    elif 10000 * x + 5000 * y + 1000 * z == money :
      check += 1
      print(x,y,z)

if check == 0 :
  print ("-1 -1 -1")

Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<algorithm>
#include<cstdio>
#include<stdio.h>
#include<stack>
#include<sstream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<list>
#include<numeric>
typedef long long ll;

#define pi 3.14159265358979323846
#define VI vector<int>
#define VLL vector<long long>
#define MAX max_element
#define MIN min_element
#define all(v) v.begin(), v.end()
const ll MOD = 1e9 + 7;
using namespace std;
template<typename T>
T gcd(T a, T b) {
	return b ? gcd(b, a % b) : a;
}
template<typename T>
T lcm(T a, T b) {
	return a * b / gcd(a, b);
}

template<typename T>
T binarysearch(vector<T> A, T key) {
	ll left = 0;ll right = 4;ll mid;
	while (left < right) {
		mid = (left + right) / 2;
		if (key == A[mid]) return 1;
		if (key > A[mid]) left = mid + 1;
		else if (key < A[mid]) right = mid;
	}
	return 0;
}

template<typename T>
T finder(vector<T> vec, T number) {
	auto itr = find(vec.begin(), vec.end(), number);
	size_t index = distance(vec.begin(), itr);
	if (index != vec.size()) { // 発見できたとき
		return 1;
	}
	else { // 発見できなかったとき
		return 0;
	}
}
ll frac(ll n)//階乗
{
	if (n == 0) {
		return 1;
	}
	return (n * frac(n - 1)) % MOD;
}

template<typename T>
T keta(T a) {
	ll kazu = 1;
	while (1) {
		if (a / 10 != 0) { a /= 10;kazu++; }
		else break;
	}
	return kazu;
}//桁数


template<typename T>
T nCr(ll n, T r) {
	ll ans = 1;
	for (int i = n; i > n - r; --i) {
		ans = ans * i;
	}
	for (int i = 1; i < r + 1; ++i) {
		ans = ans / i;
	}
	return ans;
}
/*char r[4];
int yaju[4];
char op[3];
int sum = 0;
scanf("%s", r);
for (int i = 0;i < 4;i++) {
	yaju[i] = r[i] - '0';
}
*///map < string, ll> s;

/*if (N % 2 != 0)a = N / 2;
else a = N / 2 - 1;
for (int i = 1;i <= a;i++) {
	for (int j = 0;j < N - (i * 2);j++) {
		if (S[j] != S[j + i] && S[j + i * 2] != S[j] && S[j + i] != S[j + i * 2]) sum--;
		if (sum == 0)break;
	}
}*/

int main() {
	ll H,a;cin >> H;
	ll ans = 1;
	ll mon = 1;
	if (H == 1) ans = 1;
	else {
	while (1) {
		H = H / 2;
		mon *= 2;
		ans += mon;
		if (H == 1) break;
	}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
      
int main()
{
  int N;
  string S;
  cin >> N >> S;
  
  //初期値の設定
  int N0=0;
  int del = 0;
  int NE = 0;
  int NS = 0;
  if(S.at(0) == 'W') NS += 1;
  
  for(int i=1; i<N; i++)
  {
    if(S.at(i) == 'E')
    {
      NE++;
      N0++;
    }
    
    del = min(del,NS-NE);
    if(S.at(i) == 'W') NS++;
  }
  
  cout << N0 + del << endl;
}
  
  
  
  

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

int main(){
  long n;
  cin >> n;
  long a[n];
  rep(i,n)cin >> a[i];
  long all = 0;
  rep(i,n)all ^= a[i];
  rep(i,n){
    long tmp = a[i]^all;
    cout << tmp << " ";
  }
  return 0;
}

Measured memory_bytes: 5124
#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <stdio.h>
#include <complex>
#include <cstdint>
#include <tuple>

#define M_PI       3.14159265358979323846

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }
inline int readInt() { int x; scanf("%d", &x); return x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;

//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SQ(a) ((a)*(a))
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,s,n) for(int i=s;i<(int)n;++i)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007

int cnt[100005];

int main() {
	int n, q;
	string str;
	cin >> n>>q>>str;
	REP(i, n-1) {
		cnt[i + 2] = cnt[i + 1];
		if (str.substr(i, 2) == "AC")cnt[i + 2]++;
	}
	REP(i, q) {
		int l, r;
		scanf("%d%d", &l, &r);
		l--;
		int ret = cnt[r] - cnt[l];
		if (l != 0) {
			if (str.substr(l - 1, 2) == "AC")ret--;
		}
		printf("%d\n", ret);
	}
	return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <set>
#include <queue>
#include <map>
#include <numeric>
#include <functional>
#include <math.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

#define INF ((int)1e9)
#define INFLL ((ll)1e18)
#define MOD (1000000007LL)


int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    int A, B, C;
    cin >> A >> B >> C;
    int R = C - (A-B);
    cout << (R > 0 ? R : 0) << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
  std::string s;
  std::string t;
  cin >> s;
  cin >> t;
  long int count = 0;
  int idx = 0;

  for(int i=0; i<t.length(); i++) {
    if(s.find(t[i]) == std::string::npos) {
      cout << -1;
      exit(0);
    }
    else if(s.substr(idx).find(t[i]) != std::string::npos) {
      idx += s.substr(idx).find(t[i]) + 1;
    }
    else {
      idx = s.find(t[i]) + 1;
      count += s.length();
    }  
  }
  cout << count + idx;
    
  return 0;
}

Measured memory_bytes: 640
H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
 
 
def enclose_field(field, outline="#"):
    """
    迷路等の外周をoutlineで埋めることで、IndexErrorを回避できます。
    [0, 0] → [1, 1]、[H-1, W-1] → [H, W]となります。
    """
    for i in range(len(field)):
        field[i] = [outline] + field[i] + [outline]
    field.append([outline] * (len(field[0])))
    field.insert(0, [outline] * (len(field[0])))
    return field
 
 
S = enclose_field(S, outline="a")
 
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            adj = [S[i+1][j], S[i-1][j], S[i][j+1], S[i][j-1]]
            if "#" not in adj:
                print("No")
                exit()
else:
    print("Yes")

Measured memory_bytes: 39536
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){
  while (x->left != NIL){
    x = x->left;
  }
  return x;

}

Node treeMaximum(Node x){
  while (x->right != NIL)
    {x = x->right;}
  return x;

}

Node treeSearch(Node x, int k){
  if (x == NIL || k == x->key)
    return x;
  if (k < x->key)
    return treeSearch(x->left, k);
  else
    return treeSearch(x->right, k);


}

Node treeSuccessor(Node x){
  Node y;
  if (x->right != NIL)
    return treeMinimum(x->right); // case 1
  y = x->parent;
  while (y != NIL && x == y->right){
    x = y;
    y = y->parent;
  }
  return y; // case 2

}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
  if (z->left == NIL || z->right == NIL)
    y = z;
  y = treeSuccessor(z);
  if (y->left != NIL)x = y->left;
  else
    x = y->right;
  if (x != NIL)
    x->parent = y->parent;

  if (y->parent == NIL)
    root = x;
  else if (y == y->parent->left)
    y->parent->left = x;
  else
    y->parent->right = x;
  if (y != z)
    z->key = y->key;







       
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
  x = root;
  while (x != NIL){
    y = x;
    if (z->key < x->key)
      x = x->left;
    else
      x = x->right;
  }
  z->parent = y;
  if( y == NIL )// Tree is empty
    root = z;
  else if (z->key < y->key)
    y->left = z;
  else
    y->right = z;



}

void inorder(Node u){
  if (u != NIL){
    inorder(u->left);
    printf (" %d",u->key);
    inorder(u->right);
  }
}
void preorder(Node u){
  if(u == NULL){
    return;
  }
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}

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

typedef long long ll;

const ll INF = 10e9;
int N, A, B, C;
vector<int>l(8);

ll dfs(int cur, int a, int b, int c) {
    int ret0, ret1, ret2, ret3;
    if (cur == N) {
        if (min({a, b, c}) > 0) {
            return abs(a-A) + abs(b-B) + abs(c-C)-30;
        } else {
            return INF;
        }
    }
    ret0 = dfs(cur+1, a, b, c);
    ret1 = dfs(cur+1, a+l[cur], b, c) + 10;
    ret2 = dfs(cur+1, a, b+l[cur], c) + 10;
    ret3 = dfs(cur+1, a, b, c+l[cur]) + 10;
    return min({ret0, ret1, ret2, ret3});
}

int main() {
    cin >> N >> A >> B >> C;
    for (int i = 0; i < N; i++) {
        cin >> l[i];
    }
    
    ll ans;
    ans = dfs(0, 0, 0, 0);
    cout << ans << endl;
}


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

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf  1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

int main(){
    int n;
    cin >> n;
    vector<ll>v(n);
    rep(i,n)cin >> v[i];
    if(v[0]!=0){
        cout << -1 << endl;
        return 0;
    }
    reverse(v.begin(),v.end());
    ll ans = 0;
    bool flag = 0;
    rep(i,n){
        if(i==0){
            ans += v[i];
        }
        if(i!=0){
            if(v[i]<max(v[i-1]-1,(ll)0)){
                flag = 1;
                break;
            }
            if(v[i]>max(v[i-1]-1,(ll)0)){
                ans += v[i];
            }
        }
    }
    if(flag){
        cout << -1 << endl;
    }else{
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 1792
#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
 
using namespace std;

int main()
{
    string phone[10] = {".,!? ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    int n;
    string input;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> input;
        int l = input.length();
        int j = 0;
        while(1){
            int c1 = 0;
            while(c1 == 0 && j < l){
                c1 = input[j] - '0';
                j++;
            }
            if(j == l) break;
            int l2 = phone[c1 - 1].length();
            int k = 0;
            while(c1 == input[j] - '0'){
                j++;
                k++;
            }
            cout << phone[c1 - 1][k % l2];
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 1212
import itertools


N,M,R = map(int,input().split())
r = list(map(int,input().split()))
INF = float('inf')
D = [[INF]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
    D[i][i] = 0

for _ in range(M):
    a,b,c = map(int,input().split())
    D[a][b] = c
    D[b][a] = c

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            D[i][j] = min(D[i][j], D[i][k] + D[k][j])

loads = list(itertools.permutations(r))
# for load in loads:
#     print(load)
ans = INF
#ans_load = None
for load in loads:
    temp = 0
    for i in range(R-1):
        temp += D[load[i]][load[i+1]]
    #print(load,temp)
    ans = min(temp,ans)
    # if temp < ans:
    #     ans = temp
    #     ans_load = load

print(ans)
#print(ans_load)

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

public class MainClass
{
	public const long Giri = 1000000007;
	public const long DpInf = 99999999999999;

	public static void Main(string[] args)
	{
		var p = Input().ToInt();
		var n = p[0];
		var m = p[1];
		var a = Input().ToInt();
		
		int k = 0;
		long wa = 0;
		for(int i = 0; i < n; i++)
		{
			wa += a[i];
		}
		double op = (double)wa / (4 * m);
		for(int i = 0; i < n; i++)
		{
			if(a[i] >= op)
				k++;
		}
		Console.WriteLine(k >= m ? "Yes" : "No");
	}
	

	
	static long GCD(long a, long b)
	{
		var v = new[] { a, b };
		while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
		return v[0];
	}
	public static string[] Input() { return Console.ReadLine().Split(); }
}

public static class Smarter
{
	public static int ToInt(this string str) { return int.Parse(str); }
	public static long ToLong(this string str) { return long.Parse(str); }
	public static int[] ToInt(this string[] str, int offset = 0)
	{
		var r = new int[str.Length];
		for(int i = 0; i < str.Length; i++) r[i] = str[i].ToInt() + offset;
		return r;
	}
}

Measured memory_bytes: 11092
n = int(input())
a = list(map(int, input().split()))
flg = 0

a.sort()
if n % 2 == 0:
  if a[0] == 1 and a[1] == 1:
    for i in range(2, n, 2):
      if a[i] == a[i + 1] and a[i - 1] + 2 == a[i]:
        continue
      else:
        flg = 1
        break
  else:
    flg = 1
else:
  if a[0] == 0:
    for i in range(1, n, 2):
      if a[i] == a[i + 1] and a[i - 1] + 2 == a[i]:
        continue
      else:
        flg = 1
        break
  else:
    flg = 1

if flg == 1:
  print(0)
else:
  print((2 ** (n // 2)) % (10 ** 9 + 7))

Measured memory_bytes: 20732
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
using namespace std;

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

  sort(a+1, a+n+1);
  int c = a[n], d, e;
  d = *(lower_bound(a+1, a+n+1, c/2));
  e = *(lower_bound(a+1, a+n+1, c/2)-1);

  if(abs(c - 2*d) < abs(c - 2*e)){
    cout << c << " " << d << endl;
  }
  else{
    cout << c << " " << e << endl;
  }
  return 0;
}


Measured memory_bytes: 640
a1 = list(map(int, input().split()))
a2 = list(map(int, input().split()))
a3 = list(map(int, input().split()))
n = int(input())
s = list(map(int, [input() for i in range(n)]))
l = [
  [0, 0, 0]
  , [0, 0, 0]
  , [0, 0, 0]
]
for i in range(0, 3):
  for j in range(0, n):
    if a1[i] == s[j]:
      l[0][i] = i+1
for i in range(0, 3):
  for j in range(0, n):
    if a2[i] == s[j]:
      l[1][i] = i+1
for i in range(0, 3):
  for j in range(0, n):
    if a3[i] == s[j]:
      l[2][i] = i+1
n = []
for i in l:
  for j in i:
    if j != 0:
      n.append(j)
count = 0
for i in range(0, 3):
  if l[i][0] and l[i][1] and l[i][2]:
    count += 1
if (l[0][0] and l[1][1] and l[2][2]) or (l[2][0] and l[1][1] and l[0][2]):
  count += 1
else:
  for i in range(1, 4):
    if n.count(i) == 3:
      count += 1
print('Yes' if count >= 1 else 'No')

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

using namespace std;

const int MOD = 1e9 + 7;
const long long INF = 1e18;
const int MaxN = 1e3 + 13;
const int MaxW = 1e4 + 14;

long long dp[MaxW];

struct box{
    int w, s, v;

    bool operator < (const box & oth) const
    {
        return s + w > oth.s + oth.w;
    }
};

void upMax(long long & x, long long y)
{
    if(x < y)
        x = y;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("input.txt", "r", stdin);

    int n;
    cin >> n;

    vector <box> v(n);
    for(box & b : v)
        cin >> b.w >> b.s >> b.v;

    sort(v.begin(), v.end());

    for(box & b : v)
    {
        for(int i = b.w; i < MaxW; ++i)
            if(dp[i])
                upMax(dp[min(b.s, i - b.w)], dp[i] + b.v);

        upMax(dp[b.s], b.v);
    }

    long long ans = 0;

    for(int i = 0; i < MaxW; ++i)
        upMax(ans, dp[i]);

    cout << ans << '\n';

    return 0;
}



Measured memory_bytes: 384
#include"bits/stdc++.h"
#define F(i,j,n) for(register int i=j;i<=n;i++)
#define D(i,j,n) for(register int i=j;i>=n;i--)
#define ll long long
using namespace std;
namespace io{
	const int L=(1<<19)+1;
	char ibuf[L],*iS,*iT,c;int f;
	char gc(){
		if(iS==iT){
			iT=(iS=ibuf)+fread(ibuf,1,L,stdin);
			return iS==iT?EOF:*iS++;
		}
		return*iS++;
	}
	template<class I>void gi(I&x){
		for(f=1,c=gc();c<'0'||c>'9';c=gc())if(c=='-')f=-1;
		for(x=0;c<='9'&&c>='0';c=gc())x=x*10+(c&15);x*=f;
	}
};
using io::gi;
using io::gc;
ll k,a,b;
int main(){
	#ifdef JHR
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	#endif
	gi(k);gi(a);gi(b);
	if(b-a<=2||a+1>k){printf("%lld\n",k+1);return 0;}
	b-=a;k-=a-1;a+=k&1;k/=2;
	printf("%lld\n",k*b+a);
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <string.h>

#define rep(i,n) for(int i = 0; i < n; i++)
#define rrep(i,n) for(int i = n - 1; i >= 0; i--)
#define REP(i,k,n) for(int i = k; i < n; i++)

#define vi vector<int>
#define pb push_back
using namespace std;

const int MAX_N = 300010;
vi prime;
bool is_prime[MAX_N + 1];
void sieve(){
    memset(is_prime,false,sizeof(is_prime));
    for(int i = 1; i * 7 < MAX_N; i++) {
        int bef = i * 7 - 1;
        int aft = i * 7 + 1;
        is_prime[bef] = true;
        is_prime[aft] = true;
    }
    for(int i = 1; i * 7 <= MAX_N; i++) {
        int bef = i * 7 - 1;
        int aft = i * 7 + 1;
        if(is_prime[bef]) {
            for(int j = 2 * bef; j <= MAX_N; j += bef) is_prime[j] = false;
        }
        if(is_prime[aft]) {
            for(int j = 2 * aft; j <= MAX_N; j += aft) is_prime[j] = false;
        }
    }
    rep(i,MAX_N) if(is_prime[i]) prime.pb(i);
}

int main(){
    int n;
    sieve();
    while(cin >> n, n != 1) {
        cout << n << ":";
        rep(i,prime.size()){
            if(n % prime[i] == 0) cout << " " << prime[i];
        }
        cout << endl;
    }

    return 0;

}



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

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  cout << (c - (a - b) >= 0 ? c - (a - b) : 0) << endl;
}

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

using namespace std;

int n, v[20], c[20], f[20];

void input() {
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> v[i];
	for (int i = 0; i < n; ++i) cin >> c[i];
}

void genInput() {
	n = 4;
	for (int i = 0; i < n; ++i) {
		v[i] = rand() % 5 + 1;
		c[i] = rand() % 5 + 1;
	}
}

int bruteForce() {
	int res = 0;
	for (int state = 0; state < (1 << n); ++state) {
		int tmp = 0;
		for (int j = 0; j < n; ++j)
			if (state & (1 << j))
				tmp += v[j] - c[j];
		res = max(res, tmp);
	}
	return res;
}

int dp() {
	f[0] = max(0, v[0] - c[0]);
	for (int i = 1; i < n; ++i)
		f[i] = max(f[i - 1], f[i - 1] + v[i] - c[i]);
	return f[n - 1];
}

int Greedy() {
	int res = 0;
	for (int i = 0; i < n; ++i)
		if (v[i] - c[i] > 0)
			res += v[i] - c[i];
	return res;
}

int main() {
	/*
	int Case = 0;
	while (true) {
		genInput();
		int res1 = bruteForce();
		int res2 = Greedy();
		if (res1 != res2) {
			printf("FAIL\n");
			for (int i = 0; i < n; ++i)
				printf("%d: [v = %d, c = %d]\n", i, v[i], c[i]);
			break;
		}
		printf("Passed case %d\n", ++Case);
	}
	*/
	input();
	cout << Greedy();
	return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 5;
char str[N];
int cnt[3];
int main(){
	scanf("%s" , str);
	for(int i = 0 ; str[i] ; ++i){
		++cnt[str[i] - 'a'];
	}
	sort(cnt , cnt + 3);
	printf(cnt[2] - cnt[0] > 1 ? "NO\n" : "YES\n");
}

Measured memory_bytes: 384
### H を超えない2の累乗 * 2 - 1
H = int(input())
two_exps = []
two_exp = 2 ** 0
limit = 10 ** 12

while two_exp <= limit:
    two_exps += [two_exp]
    two_exp *= 2

for i, v in enumerate(two_exps):
    if v > H:
        print(two_exps[i - 1] * 2 - 1)
        break
else:
    print(two_exps[-1] * 2 - 1)

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

#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lch (o << 1)
#define rch (o << 1 | 1)

typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int, int> pint;
typedef tuple<int, int, int> tint;

const int N = (1 << 18) + 5;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;

vector<int> son[N];
int p[N];
ll s[N], prod[N], iprod[N];
int h, n;
ll ans;

ll QPow(ll bas, int t) {
	ll ret = 1;
	while (t) {
		if (t & 1) ret = ret * bas % MOD;
		bas = bas * bas % MOD;
		t >>= 1;
	}
	return ret;
}

void DFS(int o) {
	if (lch > n) {
		son[o].push_back(o);
		return;
	}
	DFS(lch);
	DFS(rch);

	// tag lch
	for (auto u: son[lch]) {
		int v = p[u];
		ll w = prod[u] * prod[v] % MOD;
		while (v) {
			s[v] = (s[v] + w) % MOD;
			v /= 2;
		}
	}

	// cal rch
	ll sum = 0;
	for (auto u: son[rch]) {
		int v = p[u];
		ll w = prod[u] * prod[v] % MOD;
		ll pre = 0;
		while (v) {
			sum = (sum + w * (s[v] - pre) % MOD * iprod[v] % MOD * iprod[v / 2]) % MOD;
			pre = s[v];
			v /= 2;
		}
	}
	ans = (ans + sum * iprod[o] % MOD * iprod[o / 2]) % MOD;

	// clear tag
	for (auto u: son[lch]) {
		int v = p[u];
		while (v) {
			s[v] = 0;
			v /= 2;
		}
	}

	son[o].insert(son[o].end(), all(son[lch]));
	son[o].insert(son[o].end(), all(son[rch]));
}

int main() {
	ios::sync_with_stdio(0);

	prod[0] = iprod[0] = 1;
	for (int i = 1; i < N; i++) {
		prod[i] = prod[i / 2] * i % MOD;
		iprod[i] = QPow(prod[i], MOD - 2);
	}

	cin >> h;
	n = (1 << h) - 1;
	for (int i = 1; i <= n / 2 + 1; i++) {
		int pos;
		cin >> pos;
		p[i + n / 2] = pos + n / 2;
	}
	DFS(1);
	ans = (ans % MOD + MOD) % MOD;
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 31932
#include <iostream>
#include <iomanip>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
#include <utility>
#include <deque>
#include <queue>
#include <functional>

#define rep(i, n) for(int i = 0; i < n; ++i)
#define REP(i, m, n) for(int i = m; i < n; ++i)
#define rrep(i,n) for(int i = n; i >= 0; --i)
#define RREP(i, m, n) for(int i = n; i >= m; --i)
#define llrep(i, n) for(ll i = 0; i < n; ++i)
#define llREP(i, m, n) for(ll i = m; i < n; ++i)
#define llrrep(i,n) for(ll i = n; i >= 0; --i)
#define llRREP(i, m, n) for(ll i = n; i >= m; --i)

using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<long long, long long>;

using namespace std;

const long long _MOD = 1000000007;
const long long MOD = 998244353;

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

	string s;
	cin >> s;

	ll dp[13] = { 0 }, pre[13] = { 0 };
	ll tens = 10;

	if (s[s.length() - 1] == '?') {
		rep(i, 10) {
			pre[i] = 1;
		}
	}
	else {
		pre[s[s.length() - 1] - '0'] = 1;
	}

	rrep(i, s.length() - 2) {
		memset(dp, 0, sizeof(ll) * 13);
		
		if (s[i] == '?') {
			rep(j, 10) {
				ll num = (j*tens) % 13;
				rep(k, 13) dp[(k + num) % 13] += pre[k];
			}
		}
		else {
			ll num = s[i] - '0';
			num = (num*tens) % 13;
			rep(j, 13) {
				if (pre[j] != 0) dp[(j + num) % 13] = pre[j];
			}
		}

		rep(j, 13) pre[j] = dp[j] % _MOD;

		tens *= 10;
		tens %= 13;
	}

	cout << pre[5] << "\n";

	return 0;
}


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

// def
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
#define repeat(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
const int M = 1e9 + 7;
const int INF = 1e9;
const int MAX_V = 300 + 5;
const int MAX_N = 1e5 + 5;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> ans(n);
    rep(ri, 2) {
        int cnt = 0;
        rep(i, n) {
            if (s[i] == 'R') {
                cnt++;
            } else {
                ans[i - 1] += (cnt + 1) / 2;
                ans[i] += cnt / 2;
                cnt = 0;
            }
        }
        reverse(ans.begin(), ans.end());
        reverse(s.begin(), s.end());
        rep(i, n) {
            if (s[i] == 'L')
                s[i] = 'R';
            else
                s[i] = 'L';
        }
    }
    rep(i, n) cout << ans[i] << " ";
    cout << endl;
}


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

int main(int argc, char *argv[]) {
	int A = 0;
	int B = 0;
	int C = 0;
	int K = 0;
	std::cin >> A >> B >> C >> K;

	int max = std::max({A, B, C});
	double max_exp = std::pow(2, K);
	if (max == A) {
		std::cout << (max_exp * A) + B + C << std::endl;
	} else if (max == B) {
		std::cout << (max_exp * B) + A + C << std::endl;
	} else if (max == C) {
		std::cout << (max_exp * C) + A + B << std::endl;
	}
	
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,w;
    cin>>n>>w;
    long long int dp[w+1];
    int wt[n];
    long long int vl[n];
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;i++)
    {
        cin>>wt[i]>>vl[i];
    }
    for(int i=0;i<n;i++)
    {
        for(int j=w;j>=wt[i];j--)
        {
            dp[j]=max(dp[j],vl[i]+dp[j-wt[i]]);
        }
    }
    cout<<dp[w];
}

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

const int SIZE = 1000000000;

int main() {
    int N;
    int ans = 0;
    cin >> N;
    vector<pair<int, int>> A_B(N);

    for (int i = 0; i < N; i++) {
        cin >> A_B[i].first >> A_B[i].second;
    }
    sort(A_B.begin(), A_B.end());
    
    ans += A_B[0].first;
    for (int i = 1; i < N; i++) {
        ans += min((A_B[i].first-A_B[i-1].first), (A_B[i-1].second-A_B[i].second));
    }
    ans += A_B[N-1].second;

    cout << ans << endl;
}


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

int main() {
  string s;
  cin>>s;
  if(s=="abc"||s=="bac"||s=="cab"||
    s=="acb"||s=="bca"||s=="cba")puts("Yes");
  else puts("No");
  return 0;
}


Measured memory_bytes: 256
//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
//~ #pragma GCC optimize("O3")
//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define pb push_back
#define SZ(x) ((int)(x).size())
#define ALL(x) x.begin(),x.end()
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define _upgrade ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define erase_duplicates(x) sort(all(x)); (x).resize(distance((x).begin(), unique(all(x))));


using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;

//X.find_by_order(k); - zwraca iterator na k-ty element (numeracja od zerowego)
//X.order_of_key(k); - zwraca liczbę elementów ostro mniejszych niż k

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;
typedef vector<LL> VLL;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<char> VC;
typedef long double LD;
typedef pair<LD,LD> PLD;
typedef vector<LD> VLD;
typedef vector<PLD> VPLD;

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<" = "<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;
  cerr<<" = "<<h<<", "; _dbg(sdbg+1, a...);
}

#ifdef LOCAL
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...)
#define cerr if(0)cout
#endif

const int maxn = (1e6)+7;
const int maxk = 20;
const int inf = (1e9)+7;
const LL LLinf = ((LL)1e18)+7LL;
const LD eps = 1e-9;
const LL mod = 1e9+7;

// ***************************** CODE ***************************** //

VI in[maxn], out[maxn];
int st[maxn];
int f[maxn];
int deep[maxn];

int main()
{
	_upgrade
  int n, m;
  cin>>n>>m;
  for(int i = 1;i < n + m;i++)
  {
    int a, b;
    cin>>a>>b;
    out[a].pb(b);
    in[b].pb(a);
    st[b]++;
  }
  queue<int> q;
  for(int i = 1;i <= n;i++)
    if(st[i] == 0)
      q.push(i);
  set<int> zb;
  while(SZ(q))
  {
    int a = q.front();
    for(auto s : in[a])
      if(zb.count(s) && deep[s] >= deep[a])
      {
        f[a] = s;
        deep[a] = deep[s] + 1;
      }
    zb.insert(a);
    q.pop();
    for(auto s : out[a])
    {
      st[s]--;
      if(st[s] == 0)
        q.push(s);
    }
  }
  for(int i = 1;i <= n;i++)
    cout<<f[i]<<"\n";

	return 0;
}


Measured memory_bytes: 68736
local Deque={}

Deque.lpush=function(self,value)
    local first=self.first-1
    self.first=first
    self[first]=value
end

Deque.rpush=function(self,value)
    local last=self.last+1
    self.last=last
    self[last]=value
end

Deque.lpop=function(self)
    local first=self.first
    local value=self[first]
    self[first]=nil
    self.first=first+1
    return value
end

Deque.rpop=function(self)
    local last=self.last
    local value=self[last]
    self[last]=nil
    self.last=last-1
    return value
end

Deque.size=function(self)
    return self.last-self.first+1
end

Deque.empty=function(self)
    return self.first>self.last
end

Deque.new=function()
    local obj={first=0,last=-1}
    setmetatable(obj,{__index=Deque})
    return obj
end

----------

local n,m=io.read("n","n")
local g={}
local h={}
local dp={}
for i=1,n do
    g[i]={}
    h[i]=0
    dp[i]=0
end
for i=1,m do
    local x,y=io.read("n","n")
    table.insert(g[x],y)
    h[y]=h[y]+1
end

local que=Deque:new()
for x=1,n do
    if h[x]==0 then
        que:rpush(x)
    end
end
while not que:empty() do
    local x=que:lpop()
    for i=1,#g[x] do
        local y=g[x][i]
        h[y]=h[y]-1
        if h[y]==0 then
            que:rpush(y)
            dp[y]=math.max(dp[y],dp[x]+1)
        end
    end
end
local length=0
for i=1,n do
    length=math.max(length,dp[i])
end
print(length)

Measured memory_bytes: 19240
import numpy as np
def is_square(n):
    for i in range(200):
        if i*i == n:
            return True
    return False
n,d = map(int, input().split())
x = []
for i in range(n):
    x.append(list(map(int,input().split())))

x = np.array(x)

count = 0
for i in range(n):
    for j in range(i+1,n):
        l = x[i] - x[j]
        l = np.square(l)
        l = np.sum(l)
        flag = is_square(l)
        if(flag) :
            count +=1

print(count)

Measured memory_bytes: 12428
#include "cstdio"
#include "vector"
#include "queue"
using namespace std;

const int maxm=100;
struct edge{int to,w;};
edge edges[maxm];
vector<int>g[maxm];

int n,m,p;
int vis[maxm],dis[maxm];

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

void add(int u,int v,int w)
{
	edges[++p].to=v;
	edges[p].w=w;
	g[u].push_back(p);
}

void spfa(int s)
{
	for(int i=0;i<=50;i++)
		dis[i]=0x3f3f3f3f,vis[i]=0;
	
	queue<int>qn;
	qn.push(s);
	dis[s]=0;
	vis[s]=1;
	
	while(!qn.empty())
	{
		int nn=qn.front();qn.pop();
		vis[nn]=0;
		for(int i=0,d=g[nn].size();i<d;i++)
		{
			edge &e=edges[g[nn][i]];
			if(dis[e.to]>dis[nn]+e.w)
			{
				dis[e.to]=dis[nn]+e.w;
				if(!vis[e.to])
				{
					qn.push(e.to);
					vis[e.to]=1;
				}
			} 
		}
	}
	
}

int main()
{
	//freopen("r.txt","r",stdin);
	while(~scanf("%d",&m))
	{
		if(m==0)break;
		for(int i=0;i<=12;i++)
			g[i].clear();
		n=p=0;
		int u,v,w;
		for(int i=0;i<m;i++)
		{
			scanf("%d%d%d",&u,&v,&w);
			add(u,v,w);
			add(v,u,w);
			n=max(max(n,v),u);
		}
		
		int tot=0,ans=0x3f3f3f3f;
		for(int i=0;i<=n;i++)
		{
			spfa(i);
			int res=0;
			for(int j=0;j<=n;j++)
				res+=dis[j];
			if(res<ans)
			{
				ans=res;
				tot=i;
			}
		}
			
		printf("%d %d\n",tot,ans);
	}
	return 0;
} 


Measured memory_bytes: 2784
from collections import deque

N = int(input())

colors = [-1] * N
trees = [{} for _ in range(N)]
for _ in range(N-1):
    u, v, w = list(map(int, input().split()))
    trees[u-1][v-1] = (w % 2 == 0)
    trees[v-1][u-1] = (w % 2 == 0)

targets = deque([0])
colors[0] = 0
while len(targets) > 0:
    target = targets.popleft()
    next_targets = trees[target]
    for next_target, is_even in next_targets.items():
        if colors[next_target] != -1:
            continue
        if is_even:
            colors[next_target] = colors[target]
        else:
            colors[next_target] = 1 - colors[target]
        targets.append(next_target)

for c in colors:
    print(c)


Measured memory_bytes: 42224
// ------------------------------------
// Date:2018/ 2/23
// Problem:ABC 047 Snuke'sColoring2 b.cpp
//
// ------------------------------------

#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto&& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()

using ll = long long;

#define MOD 1000000007

int main()
{
  int W,H,N,x,y,a,res = 0;
  cin >> W >> H >> N;
  
  vector<vector<int>> Ans(H, vector<int>(W,0));
  REP(i,N) {
    cin >> x >> y >> a;
    if (a == 1) {
      REP(j,H) {
        REP(k,x) {
          ++Ans[j][k];
        }
      }
    } else if (a == 2) {
      REP(j,H) {
        FOR(k,x,W) {
          ++Ans[j][k];
        }
      }
    } else if (a == 3) {
      REP(j,y) {
        REP(k,W) {
          ++Ans[j][k];
        }
      }
    } else if (a == 4) {
      FOR(j,y,H) {
        REP(k,W) {
          ++Ans[j][k];
        }
      }
    }
  }
  REP(l,H) {
    REP(m,W) {
      if (Ans[l][m] == 0) ++res;
    }
  }
  cout << res << endl;
  return 0;
}



Measured memory_bytes: 256
let n = stdin.ReadLine() |> int
let h = stdin.ReadLine().Split() |> Array.map int64 |> Array.toList 

let rec f hairetu j i =
 match hairetu with
 | hd :: sd :: tl -> if hd >= sd then f (sd :: tl) (max j (i+1)) (i + 1)
                     else f (sd :: tl) j 0
 | _ -> j

f h 0 0
|>stdout.WriteLine

Measured memory_bytes: 35164
program prime_numbers
    implicit none
    integer(8) i, j,k, n,y
    
    integer(8) :: x(5) = (/3,5,7,11,13/)
    read (*,*)n
    y=0
    do i=3,5
                 
        if (x(i)*15<=n)then
         y=y+1
        end if

    end do
    do i=2,5
        if (x(i)*27<=n)then
            y=y+1
        end if   
    end do
    write(*,*)y
    stop
end program prime_numbers

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
const int MX = 200005;
int n, a[MX], b[MX], c[MX], pr, nx;
long long cnt;
stack<int> st;
int main(){
	scanf("%d", &n);
	rep(i,n) scanf("%d", a+i);
	rep(i,n){
		scanf("%d", b+i);
		pr = i ? i-1 : n-1;
		nx = i != n-1 ? i+1 : 0;
		c[pr] += b[i];
		c[nx] += b[i];
		b[i] -= a[i];
	}
	rep(i,n) if(b[i] >= c[i]) st.push(i);
	while(!st.empty()){
		int t = st.top(); st.pop();
		int d = b[t] / c[t] * c[t];
		cnt += b[t] / c[t];
		pr = t ? t-1 : n-1;
		nx = t != n-1 ? t+1 : 0;
		c[pr] -= d; if(b[pr] >= c[pr]) st.push(pr);
		c[nx] -= d; if(b[nx] >= c[nx]) st.push(nx);
		b[t] -= d;
	}
	rep(i,n) if(b[i]) return 0*puts("-1");
	printf("%lld\n", cnt);
}

Measured memory_bytes: 2944
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

enum P = 10L^^9+7;

void main()
{
    auto S = readln.chomp.to!(char[]);
    auto DP = new long[][](S.length, 13);

    foreach (i, c; S) {
        foreach (n; 0..10) {
            if (c == '?' || n == c-'0') {
                if (i == 0) {
                    DP[i][n] = 1;
                } else {
                    foreach (j; 0..13) {
                        auto m = (j*10 + n) % 13;
                        DP[i][m] = (DP[i][m] + DP[i-1][j]) % P;
                    }
                }
            }
        }
    }

    writeln(DP[$-1][5]);
}

Measured memory_bytes: 18200
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#include <cmath>

#define INF_LL 9000000000000000000
#define INF 2000000000

#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)

using namespace std;

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

class Union_find{
private:
	vector<int> par;
	vector<int> rank;
	int n;

public:
	Union_find(int a){
		n = a;
		for(int i = 0;i < n;i++){
			par.push_back(i);
			rank.push_back(0);
		}
	}

	int find(int x){
		if(par[x] == x){
			return x;
		}else{
			return par[x] = find(par[x]);
		}
	}

	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;

		if(rank[x] < rank[y]){
			par[x] = y;
		}else{
			par[y] = x;
			if(rank[x] == rank[y]) rank[x]++;
		}
	}

	bool same(int x, int y){
		return find(x) == find(y);
	}
};

int main(void){
	int n, t;
	int a[100000];
	int m[100000];
	int sub = 0;
	int res = 0;
	cin >> n >> t;
	REP(i, n){
		cin >> a[i];
	}
	m[0] = a[0];
	for(int i = 1;i < n;i++){
		m[i] = min(m[i-1], a[i]);
	}

	REP(i, n){
		if(a[i] - m[i] > sub){
			sub = a[i]-m[i];
			res = 1;
		}else if(a[i] - m[i] == sub){
			res++;
		}
	}
	cout <<res << endl;
	return 0;

}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define foi(i,k,n) for(int i = (int)k; i < (int)n; ++i)

using namespace std;

int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int a,b; cin >> a >> b;
    foi(c,1,4) if((a*b*c) % 2 != 0) {cout << "Yes\n"; return 0;}
    cout << "No\n";
    return 0;
}


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


int main(){
  int a,b,c,k; cin >> a >> b >> c >> k;
  //string s,t ; cin >> s >> t;
  //int n = s.size();
  int ans = 0;
    
  for (int i=0; i<k; i++){
    if(a>0){
      ans++;
      a--;
      continue;
    }
    else if(b>0){
      b--;
      continue;
    }
    else if(c>0){
      ans--;
      c--;
      continue;
    }
  }
  
  cout << ans << endl;
  /*
  if(ans){
    cout << "Yes" << endl;;
  }
  else{
    cout << "No" << endl;
  }
  */
   
}

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

int main() {
  
    int X,Y;
    cin >> X >> Y;
    
    int n = 4 * X;
    
    for(int i=0;i<=X;i++){
        if(n == Y){
            cout << "Yes" <<endl;
            break;
        }
        n-= 2;
        if(i == X) cout << "No" <<endl;
    }
}

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

using namespace std;
using ll = long long;
using ii = pair<ll, ll>;

const int MAX { 200010 };
const ll MOD { 1000000007 }, oo { 1LL << 62 };

ll mod_pow(ll a, ll n)
{
    ll res = 1, base = a;

    while (n)
    {
        if (n & 1)
            res = (res * base) % MOD;

        base = (base * base) % MOD;
        n >>= 1;
    }

    return res;
}

ll mod(ll a)
{
    return (((a % MOD) + MOD) % MOD);
}

ll binom(ll n, ll m)
{
    ll a = min(m, n - m);
    ll b = max(m, n - m);

    ll num = 1;

    for (ll i = n; i > b; --i)
        num = mod(num * i);

    ll den = 1;

    for (ll i = 2; i <= a; ++i)
        den = mod(den * i);

    auto inv = mod_pow(den, MOD - 2);

#ifdef DEBUG
cout << "a = " << a << ", b = " << b << endl;
cout << "num = " << num << ", den = " << den << endl;
cout << "inv = " << inv << endl;
#endif
    return mod(num * inv);
}

ll solve(ll N, ll a, ll b)
{
    ll ans = mod_pow(2, N);

#ifdef DEBUG
cout << "ans = " << ans << endl;
cout << "binom(" << N << ", " << a << ") = " << binom(N, a) << endl;
cout << "binom(" << N << ", " << b << ") = " << binom(N, b) << endl;
#endif
    ans = mod(ans - binom(N, a));
    ans = mod(ans - binom(N, b));
    ans = mod(ans - 1);

    return ans;
}

int main()
{
    ios::sync_with_stdio(false);

    ll N, a, b;
    cin >> N >> a >> b;

    auto ans = solve(N, a, b);

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.nextLine();
		String s = sc.nextLine();
		sc.close();
		int ans = 0;
		for(int i=n-1; i>0; i--) {
			if(s.charAt(i) != s.charAt(i-1)) {
				ans ++;
			}
		}

		System.out.println(ans+1);

	}

}


Measured memory_bytes: 26068
#include<bits/stdc++.h>
 
#define ll long long 
#define in freopen("input.txt", "r", stdin)
#define out freopen("output.txt", "w", stdout)
#define skorost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL) 

using namespace std ;
 
ll z , o , ans ;

ll N = 1e9 + 7 ;

int code(  ){

	for( int i = 1 ; i <= 5 ; i ++ ){

		int k ;

		cin >> k ;

		if( k == 0 ){

			cout << i << endl;

			return 0 ;

		}

	}	

	return 0 ;

}

int main(){ skorost ;

	int tjk = 1 ;

	// cin >> tjk ;

	while( tjk -- ){

		code( ) ;

	}

}

Measured memory_bytes: 3584
#include <math.h>
#include <iostream>
using namespace std;

int main() {
  int N;
  double T, A;
  cin >> N >> T >> A;
  double H[N];
  for (int i = 0; i < N; i++) {
    cin >> H[i];
  }
  double mi = abs(A - (T - H[0] * 0.006));
  int place = 0;
  for (int i = 1; i < N; i++) {
    if (mi > abs(A - (T - H[i] * 0.006))) {
      mi    = abs(A - (T - H[i] * 0.006));
      place = i;
    }
  }
  cout << place + 1 << endl;
  return 0;
}

Measured memory_bytes: 256
d, g = gets.chomp.split(" ").map(&:to_i)
problems = []
d.times do
  problems << gets.chomp.split(" ").map(&:to_i)
end
problems.each_with_index do |problem, index|
  problem << (problem[0] * (index + 1) * 100 + problem[1])
  problem << index
end

combinations = []
0.upto(d) do |num|
  combinations << problems.combination(num).to_a
end
answers = []

combinations.each_with_index do |combination, index_1|
  combination.each_with_index do |combi, index_2|
    sum = 0
    count = 0
    selected = []
    combi.each_with_index do |c, index_3|
      sum += c[2]
      count += c[0]
      selected << c[3]
    end
    if sum >= g
      answers << count
    else
      (d - 1).downto(0) do |index_4|
        unless selected.include?(index_4)
          (problems[index_4][0] - 1).times do
            sum += 100 * (index_4 + 1)
            count += 1
            break if sum >= g
          end
          break
        end
      end
      if sum >= g
        answers << count
      end
    end
  end
end
p answers.min

Measured memory_bytes: 2044
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <set>
#include <tuple>
#include <deque>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <chrono>
#include <random>
#include <limits>
#include <iterator>
#include <functional>
#include <sstream>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, double> Pid;
typedef pair<double, int> Pdi;
typedef pair<ll, int> Pl;
const double PI = 3.1415926535897932;   // acos(-1)
const double EPS = 1e-15;
const int INF = 1001001001;
const ll mod = 1e+9 + 7;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define chadd(x, y) x = (x + y) % mod

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

    int n;
    cin >> n;
    ll res = 0;
    for(int i = 0; i < n; ++i){
        int a;
        cin >> a;
        while(a % 2 == 0){
            ++res;
            a /= 2;
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 256
#include <iostream>

int main()
{
	int n;
	while (true) {
		std::cin >> n;
		if (n==0) break;
		int count = 0;
		while (n>1) {
			if ((n&1)==1) n = 3*n+1;
			else n /= 2;
			count++;
		}
		std::cout << count << std::endl;
	}
	return 0;
}



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

int main() {
  string S;
  int a=-1, z=0;
  cin >> S;
  for (int i=0; i<S.size(); i++){
    if (a==-1 && S.at(i)=='A'){
      a=i;
    }
    else if (a!=-1 && S.at(i)=='Z'){
      z=i;
    }
  }
  cout << z-(a-1) << endl;
}

Measured memory_bytes: 640