akhauriyash/Code-Regression huggingface dataset:
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void) {
    int n, b, f, r, v, a[4][3][10] = {0};
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d%d", &b, &f,&r,&v);
        a[b-1][f-1][r-1]+=v;
        
    }
    for (int i = 0; i <= 3; i++) {
        for (int j = 0; j <= 2; j++) {
            for (int k = 0; k <= 9; k++) {
                printf(" %d", a[i][j][k]);
            }
            printf("\n");
        }
        if (i == 3)break;
        printf("####################\n");
    }
    return 0;
}


Measured memory_bytes: 2120
import math
n = int(input())
def f(n):
  g = float('inf')
  for i in [j for j in range(1,math.ceil(n**0.5)+1) if n%j == 0]:
    if g > len(str(max(i,n//i))):
      g = len(str(max(i,n//i)))
    if g == float('inf'):
        g = 1
  return g
print(f(n))

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,a,n)  for (int i=(int)(a); i<=(int)(n); ++i)
#define rrep(i,a,n) for (int i=(int)(a); i>=(int)(n); --i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) rep(i, x.size()) cerr << x[i] << (i == x.size() - 1 ? "\n" : " ")
#define all(x) x.begin(),x.end()
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = ((1LL << 30) + (1LL << 29));
const int MOD = 1000000007;

//=============================
int N,M,K;
string S,T;
vector<int> A;
vector<int> B;
//=============================
void input()
{
    cin>>M;

}
//=============================
void func(){}
//=============================
void solve()
{
    cout<<24+(24-M)<<endl;

}
//=============================
signed main()
{
    input();
    solve();
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
bool check(int n)
{
	int t=n;
	while(t!=0)
	{
		int k=t%10;
		if(k==7)
			return true;
		t/=10;
	}
	return false;
}
int main()
{
	int n;
	cin>>n;
	if(check(n))
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 3588
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N =sc.nextInt();
		for (int i=0;i*4<=N;i++) {
			if ((N-i*4)%7==0) {
				System.out.println("Yes");
				return ;
			}
		}
		System.out.println("No");
	}
}

Measured memory_bytes: 35668
#include<cstdio>
#include<cstdlib>
#include<string>
#include<iostream>
using namespace std;
struct Node{
    int key;
    Node *parent,*left,*right;
};
Node *root,*NIL;
void insert(int k){
    Node *y=NIL;
    Node *x=root;
    Node *z;

    z=(Node *)malloc(sizeof(Node));
    z->key=k;
    z->left=NIL;
    z->right=NIL;

    while(x!=NIL){
        y=x;
        if(z->key<x->key) x=x->left;
        else x=x->right;
    }
    z->parent=y;
    if(y==NIL) root=z;
    else{
        if(z->key<y->key) y->left=z;
        else y->right=z;
    }
}
Node * treeMinimum(Node *x){
    while(x->left!=NIL) x=x->left;
    return x;
}
void treeDelete(Node *z){
    Node *y;
    Node *x;
    if(z->left==NIL||z->right==NIL) y=z;
    else y=treeMinimum(z->right);

    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;
    free(y);
}
Node * find(Node *u,int k){
    while(u!=NIL&&k!=u->key){
        if(k<u->key) u=u->left;
        else u=u->right;
    }
    return u;
}
void inorder(Node *u){
    if(u==NIL) return;
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
}
void preorder(Node *u){
    if(u==NIL) return;
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
}
int main(){
    int n,x;
    string com;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        cin>>com;
        if(com=="insert"){
            scanf("%d",&x);
            insert(x);
        }
        else if(com=="print"){
            inorder(root);
            cout<<endl;
            preorder(root);
            cout<<endl;
        }
        else if(com=="find"){
            scanf("%d",&x);
            Node *t=find(root,x);
            if(t!=NIL) cout<<"yes"<<endl;
            else cout<<"no"<<endl;
        }
        else{
            scanf("%d",&x);
            treeDelete(find(root,x));
        }
    }
    return 0;
}


Measured memory_bytes: 22024
#pragma region 
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<cstring>
#include<string>
typedef long long ll;
template <typename T>void read(T &x){x=0;char ch=getchar();ll f=1;while(!isdigit(ch)){if(ch=='-')f*=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}x*=f;}
#define IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
#pragma endregion

int main() {
    IO;
    ll x;
    cin >> x;
    int cnt = 0;
    ll now = 100;
    while (now<x) {
        now = (ll)(1.0 * now * 1.01);
        cnt++;
    }
    cout << cnt << endl;
}

Measured memory_bytes: 3656
#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(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x)x
#define rep(...)MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c)c.begin(),c.end()
#define write(x)cout<<(x)<<'\n'
using namespace std; typedef long long ll; template<class T>using vv = vector<vector<T>>;
template<class T>auto vvec(int n, int m, T v) { return vv<T>(n, vector<T>(m, v)); }
constexpr int INF = 1 << 29, MOD = int(1e9) + 7; constexpr ll LINF = 1LL << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(10); }; }aaaa;

int N;
vv<pair<int, int>> tree;

bool dfs(int v, int p, int target, vector<int>& path) {
    if (v == target) {
        return true;
    }
    for (auto&& u : tree[v]) {
        if (u.first == p) continue;
        path.push_back(u.second);
        if (dfs(u.first, v, target, path)) {
            return true;
        }
        path.pop_back();
    }
    return false;
}

int main() {
    cin >> N;
    tree.resize(N);
    rep(i, N - 1) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        tree[a].emplace_back(b, i);
        tree[b].emplace_back(a, i);
    }

    int M;
    cin >> M;
    vector<int> path;
    vector<int> cond(N - 1);
    rep(i, M) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        path.clear();
        dfs(u, -1, v, path);
        for (int e : path) {
            cond[e] |= 1 << i;
        }
    }

    int H = (N - 1) / 2, I = N - 1 - H;
    vector<int> dp1(1 << H);
    rep(bit, (1 << H) - 1) {
        rep(b, H) {
            if (bit >> b & 1) continue;
            dp1[bit | 1 << b] = dp1[bit] | cond[b];
        }
    }
    vector<int> dp2(1 << I);
    rep(bit, (1 << I) - 1) {
        rep(b, I) {
            if (bit >> b & 1) continue;
            dp2[bit | 1 << b] = dp2[bit] | cond[H + b];
        }
    }

    vector<int> cnt(1 << M);
    rep(bit, 1 << I) {
        cnt[dp2[bit]]++;
    }
    rep(b, M) rep(bit, 1 << M) {
        if (bit >> b & 1) continue;
        cnt[bit] += cnt[bit | 1 << b];
    }

    ll ans = 0;
    rep(bit, 1 << H) {
        ans += cnt[((1 << M) - 1) ^ dp1[bit]];
    }
    write(ans);
}

Measured memory_bytes: 201088
n, m = (int(_) for _ in input().split())
x = [int(input()) for i in range(m)]
xi = 0

if m == 0:
    x = [999999]

a = [1,1]
if x[xi] == 1:
    xi = min(len(x)-1,xi+1)
    a[1] = 0

for i in range(n-1):
    if x[xi]-2 == i:
        a.append(0)
        xi = min(len(x)-1,xi+1)
    else:
        a.append(a[i+1]+a[i])

print(a[n]%1000000007)

Measured memory_bytes: 460020
#include<stdio.h>
int main(){
  int N,i,j,minj,temp,cout=0;
  scanf("%d",&N);
  int A[N];
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
  }
  for(i=0;i<N-1;i++){
    minj=i;
    for(j=i;j<N;j++){
      if(A[j]<A[minj])minj=j;
    }
    if(minj!=i){
      temp=A[i];
      A[i]=A[minj];
      A[minj]=temp;
      cout++;
    }
  }
  printf("%d",A[0]);
  for(i=1;i<N;i++){
    printf(" %d",A[i]);
  }
  printf("\n");
  printf("%d\n",cout);
  return 0;
}



Measured memory_bytes: 2672
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1e9+7;
const int INF = 2e9;
template<class T> void print(const T& t){ cout << t << endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main(){
  ll x, y;
  cin >> x >> y;
  ll ans = 1;
  ll num = x;
  while(x*2<=y){
    ans++;
    x *= 2;
  }
  print(ans);
}

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

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

  double r;
  cin >> r;

  double ans = 2 * M_PI * r;
  
  cout << setprecision(12);
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3792
#include<stdio.h>
int main(void)
{
    int a[45],b[45],z[45],i;
	for(i=0;i<7;i++){
	    scanf("%d %d",&a[i],&b[i]);
		z[i]=a[i]-b[i];
	}
	for(i=0;i<7;i++){
	    printf("%d\n",z[i]);
	}
	return 0;
}

Measured memory_bytes: 1032
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cstdio>
#include <string>

using namespace std;

int main(){
    int A,P;
    scanf("%d %d", &A, &P);
    int ret = (P+3*A)/2;
    printf("%d", ret);
    fflush(stdout);
    
    return 0;
}

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

int main(){
    int n;
    cin >> n;
    vector<vector<int> > A(3, vector<int>(10));
    vector<vector<int> > B(3, vector<int>(10));
    vector<vector<int> > C(3, vector<int>(10));
    vector<vector<int> > D(3, vector<int>(10));
    
    for(int i = 0; i < n; i++){
        int b,f,r,v;
        cin >> b >> f >> r >> v;
        
        if(b == 1){
            A[f-1][r-1] += v;
        }else if(b == 2){
            B[f-1][r-1] += v;
        }else if(b == 3){
            C[f-1][r-1] += v;
        }else if(b == 4){
            D[f-1][r-1] += v;
        }
        
    }
    
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 10; j++){
            cout << " " << A[i][j] ;
        }
        cout << endl;
    }
    cout << "####################" << endl;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 10; j++){
            cout << " "<< B[i][j] ;
        }
        cout << endl;
    }
    cout << "####################" << endl;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 10; j++){
            cout << " " << C[i][j] ;
        }
        cout << endl;
    }
    cout << "####################" << endl;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 10; j++){
            cout << " "<< D[i][j];
        }
        cout << endl;
    }

}



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

class Program
{
    static void Main(string[] args) {
#if DEBUG
        MyDebugger.Test(process);
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static object process(TextReader input) {
        var s     = input.ReadLine();
        var spl   = s.Split(' ');
        int k     = int.Parse(spl[0]);
        int x     = int.Parse(spl[1]);

        StringBuilder buil = new StringBuilder();

        for(int i=x-k+1; i<x+k; i++) {
            buil.Append(i);
            buil.Append(' ');
        }
        return buil.ToString();
    }
}

Measured memory_bytes: 11092
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

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

void solve7a(int m, int f, int r) {
    if (m == -1 || f == -1) {
        cout << "F" << endl;
    }else if (m+f >= 80) {
        cout << "A" << endl;
    }else if (m+f >= 65) {
        cout << "B" << endl;
    }else if (m+f >= 50) {
        cout << "C" << endl;
    }else if (m+f >= 30) {
        if (r >= 50) {
            cout << "C" << endl;
        }else {
            cout << "D" << endl;
        }
    }else {
        cout << "F" << endl;
    }
}

int main() {
    int m, f, r;
    while(cin >> m >> f >> r, m+f+r+3) {
        solve7a(m,f,r);
    }
    return 0;
}

Measured memory_bytes: 1156
#include<iostream>
   

using namespace std;

int main(){
  int A,B; cin >> A >> B;
  int sum = 0;
  if( A > B){ sum += A; sum += A - 1;}
  else if(A < B){ sum += B; sum += B - 1;}
  else if( A == B){ sum += 2*A;}
  
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 256
/*
 *
 * Author : fcbruce <fcbruce8964@gmail.com>
 *
 * Time : Sun 21 Aug 2016 20:01:11
 *
 */
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <cctype>
#include <cmath>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>
#define sqr(x) ((x)*(x))
#ifdef _WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif

const int INF = 0x3f3f3f3f;
const long long INFLL = 0x3f3f3f3f3f3f3f3fll;
const double PI = acos(-1.0);
const double eps = 1e-10;

typedef long long LL;
typedef int itn;

const int maxn = 0;
const int maxm = 0;

bool ok(int n, int s, int e, int w)
{
  if (n == 0 && s == 0)
  {
    if (e == 0 && w == 0) return true;
    if (e != 0 && w != 0) return true;
    return false;
  }
  if (n != 0 && s != 0)
  {
    if (e == 0 && w == 0) return true;
    if (e != 0 && w != 0) return true;
    return false;
  }
  return false;
}

int main()
{
#ifdef FCBRUCE
#endif // FCBRUCE

  char S[1007];
  scanf("%s", S);

  int n, s, e, w;
  n = s = e = w = 0;
  for (char *p = S; *p; p++)
  {
    switch (*p)
    {
      case 'N': n++; break;
      case 'S': s++; break;
      case 'E': e++; break;
      case 'W': w++; break;
    }
  }

  if (ok(n, s, e, w)) puts("Yes");
  else puts("No");



  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;++i)

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int hlt = 0;
vector<P> times;
vector<vector<int>> node;
vector<bool> searched;

void solve(int index){
    if(!searched[index])searched[index]=true;else return;
    times[index].first=++hlt;
    REP(i,(int)node[index].size())
        solve(node[index][i]-1);
    times[index].second=++hlt;
}

int main(){
    int n; cin>>n;
   node.resize(n);
   times.resize(n,P(0,0));
   searched.resize(n,false);
   REP(i,n){
    int index,size; cin >> index >> size; index--;
    if(size==0)continue;
    node[index].resize(size);
        REP(j,size)cin >> node[index][j];
    sort(node[index].begin(),node[index].end());
   }
   REP(i,n)
    if(!searched[i])
        solve(i);
   REP(i,n)
    cout<<i+1<<" "<<times[i].first<<" "<<times[i].second<<endl;
}


Measured memory_bytes: 3096
from collections import deque

h, w = map(int, input().split())

s = [[] for _ in range(h)]
dis = [[-1] * w for _ in range(h)]

for i in range(h):
    s[i] = input()

white_cnt = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            white_cnt += 1

q = deque()
q.append([0, 0, 1])  # x,y,d
dis[0][0] = 1

while len(q) > 0:
    x, y, d = q.popleft()
    dxy = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    for dx, dy in dxy:
        nx = x + dx
        ny = y + dy
        if 0 > nx or w <= nx or 0 > ny or h <= ny:
            continue
        if dis[ny][nx] != -1 or s[ny][nx] == "#":
            continue
        q.append([nx, ny, d + 1])
        dis[ny][nx] = d + 1

if dis[h - 1][w - 1] == -1:
    print(-1)
else:
    print(white_cnt - dis[h - 1][w - 1])



Measured memory_bytes: 74488
import math
N,K = map(int,input().split())
ans = 0
 
for i in range(1,N+1):
    if i >= K:
        ans += (1/N)
        continue
    X = int(math.log((K/i), 2))
    if (K/i) % 2**X == 0:
        pass
    else:
        X += 1
    ans += (1/N) * (1/2) ** X
print(ans)

Measured memory_bytes: 39792
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <array>
#include <unordered_set>
#include <math.h>
using namespace std;
using s64 = int64_t;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep2(i, x, n) for(int i=x;i<n;++i)

int main()
{
    int a,b,k;
    cin >> a >> b >> k;

    vector<int> vec;
    rep2(i,1,101)
    {
        if(a%i == 0 && b%i==0) vec.push_back(i);
    }

    reverse(vec.begin(),vec.end());

    cout << vec[k-1] << endl;
    return 0;
}

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


int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if(a == b && b == c && (a&1) == 0 && (b&1)==0 && (c&1)==0){
        cout << -1 << endl;
        return 0;
    }
    int cou = 0;
    while( (a&1) == 0 && (b&1)==0 && (c&1)==0 ){
        cou++;
        int tempA = a, tempB = b, tempC = c;
        a = (tempB/2)+(tempC/2);
        b = (tempA/2)+(tempC/2);
        c = (tempA/2)+(tempB/2);
    }

    cout << cou << endl;
    return 0;
}


Measured memory_bytes: 256
N=int(input())
L=[[0 for i in range(N)]for j in range(26)]
A=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

for i in range(N):
    S=input()
    for j in range(len(S)):
        for k in range(26):
            if S[j]==A[k]:
                L[k][i]+=1
l=[100 for i in range(26)]

for a in range(26):
    for b in range(N):
        if L[a][b]<l[a]:
            l[a]=L[a][b]
#print(l)
ans=""
for c in range(26):
    ans+=A[c]*l[c]
print(ans)

Measured memory_bytes: 3064
import math
n, a, b = map(int, input().split())

if abs(a-b) % 2 == 0:
    print(abs(a-b)//2)
else:
    ans1 = abs(1 - (b - abs(1 - a) - 1)) // 2 + abs(1 - a) + 1
    ans2 = abs(n - (a + abs(n - b) + 1)) // 2 + abs(n - b) + 1
    print(min(ans1, ans2))


Measured memory_bytes: 3060
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<cmath>
#define ll long long
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
static const int MAX = 1000000007;

ll B[1000001];

long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

void C(int x){
    int y = x;
    for(int i = 2; i*i <= x; i++){
        int a = 0;
        while(y % i == 0){
            y /= i;
            a++;
        }
        if(B[i] < a) B[i] = a;
    }
    if(y > 1 && B[y] < 1) B[y] = 1;
}

int main(){
    int N;
    cin >> N;
    vector<ll> A(N);
    rep(i,N){
        cin >> A[i];
    }
    rep(i,N){
        C(A[i]);
    }
    ll a = 1;
    rep(i, 1000001){
        rep(j,B[i]){
            a = (a * i) % MAX;
        }
    }
    ll ans = 0;
    rep(i,N){
        ans = ( (a * modinv(A[i], MAX) ) % MAX + ans ) % MAX; 
    }
    cout << ans << endl;
    return 0;
}

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

#define ll long long
#define ar array
#define vi vector<int>
#define INF 1000000000

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;
	int digit = n % 10;
	int digits[4] = {0,1,6,8};
	int digits2[5] = {2,4,5,7,9};
	if(n % 10 == 3) cout << "bon" << endl;
	if(count(digits, digits+4, digit)) 
		cout << "pon" << endl;
	if(count(digits2, digits2+5,digit)) 
		cout << "hon" << endl;

	return 0;	
}


Measured memory_bytes: 3648
#include <iostream>
#include <tuple>
using namespace std;
int main(void){
    // Your code here!
    int n=1,x=1;
    while(true)
    {
        int count=0;
        cin >> n >> x;
        if(n==0 && x==0) break; //終了条件
        for(int a=1; a<=n; a++) //Aの組
        {
            for(int b=1; b<=n; b++) //Bの組
            {
                int c = x - a - b;
                if(1<=c && c<=n && a<b && b<c)
                {
                    //cout << a << b << c << endl;
                    count++;
                }
                
            }
        }
        cout << count << endl;
    }
}


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

#include <boost/multiprecision/cpp_int.hpp>

namespace mp = boost::multiprecision;
using namespace std;
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

long long  gcd(long long  a, long long b) {
	if (a < b) return gcd(b, a);
	long long  r;
	while ((r = a % b)) {
		a = b;
		b = r;
	}
	return b;
}

int main() {
	mp::cpp_int H, ans=0,bit=0;
	int count = 0;
	cin >> H;
	vector<mp::cpp_int> S(50);
	S.at(0) = 1;
for(int i=1;i<40;i++){
S.at(i)+=S.at(i-1)*2;
}
	while (H != 1) {
bit=bit+H%2;
		H = (H + 1) / 2;
ans+=S.at(count);
		count++;
        
	}
if(bit==0)ans+=S.at(count);

	
	 cout << ans;

}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <stdlib.h>
using namespace std;

string s;
vector<string> vec;

int main(){
	while(cin >> s){
		vec = vector<string>();
		int st = 0;
		if(s[0] == '@'){
			st = -1;
		}
		for(int i = 0; i < s.size(); i++){
			if(s[i] == '@'){
				if(st >= 0){
					vec.push_back(s.substr(st,i-st));
				}
				if(s[i + 3] != '@'){
					st = i + 3;
				}
				else{
					st = -1;
				}
				string rep = "";
				char length[2] = {s[i+1],'\0'};
				for(int j = 0; j < atoi(length); j++){
					rep += s[i+2];
				}
				vec.push_back(rep);
				i += 2;
			}
		}
		if(st >= 0){
			vec.push_back(s.substr(st,s.size()-st));
		}
		string ans = "";
		for(int i = 0; i < vec.size(); i++){
			ans += vec[i];
		}
		cout << ans << endl;
	}
	return 0;
}

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

int main()
{
  int N ;
  cin>>N ;
  
  int ans ;
  if(N%2==0) ans=N ;
  else ans=N+1 ;
  for(;;ans+=2) if(ans%N==0) break ;
  
  cout<<ans<<endl ;
  
  return 0 ;
}


Measured memory_bytes: 256
#include <iostream>
#include <utility>
#include <tuple>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <functional>
#include <climits>
#include <numeric>
#include <queue>
#include <cmath>
#include <iomanip>
#include <array>
#include <string>
#include <stack>
#include <cassert>
#include <memory>
#include <random>
#include <fstream>
#include <cfloat>

char is_same(const int pattern) {
	auto same = ((pattern >> 2) & pattern & 1) == (((pattern >> 2) | pattern) & 1);
	if ((pattern & 2) == 0) {
		return same ? 'o' : 'x';
	}
	else {
		return same ? 'x' : 'o';
	}
}
std::unique_ptr<std::string> make_str(const std::vector<std::vector<bool>> can_make) {
	auto last = std::distance(can_make[1].begin(), std::find(can_make[1].begin(), can_make[1].end(), true));
	if (last == can_make[1].size()) return nullptr;
	last >>= 1;
	for (int j = 0; j < 2; ++j) {
		if (can_make[0][(j << 1) + last]) {
			last = j;
			break;
		}
	}
	std::string result; result.push_back(last == 0 ? 'S' : 'W');
	for (int i = can_make.size() - 1; i > 0; --i) {
		for (int j = 0; j < 2; ++j) {
			if (can_make[i][(j << 1) + last]) {
				result.push_back(j == 0 ? 'S' : 'W');
				last = j;
				break;
			}
		}
	}
	std::reverse(result.begin(), result.end());
	return std::make_unique<std::string>(std::move(result));
}
std::unique_ptr<std::string> make_pattern(const std::string& str, const int first_two) {
	std::vector<std::vector<bool>> can_make(str.size(), std::vector<bool>(4, false));
	can_make[1][first_two] = true;
	for (auto i = 2; i <= str.size(); ++i) {
		for (auto prev = 0; prev < 4; ++prev) if (can_make[i - 1][prev]) {
			for (auto j = 0; j < 2; ++j) {
				can_make[i % str.size()][((prev << 1) + j) & 3] = can_make[i % str.size()][((prev << 1) + j) & 3] || (str[i - 1] == is_same((prev << 1) + j));
			}
		}
	}
	can_make[1][first_two] = false;
	for (auto j = 0; j < 2; ++j) if (can_make[0][(j << 1) + (first_two >> 1)]) {
		can_make[1][first_two] = can_make[1][first_two] || is_same((j << 2) + first_two) == str[0];
	}
	return make_str(std::move(can_make));
}

int main() {
	int n; std::cin >> n;
	std::string str; std::cin >> str;
	std::unique_ptr<std::string> result{ nullptr };
	for (auto i = 0; i < 4; ++i) {
		result = make_pattern(str, i);
		if (result != nullptr) break;
	}
	if (result == nullptr) {
		std::cout << "-1\n";
	}
	else {
		std::cout << *result << '\n';
	}
}

Measured memory_bytes: 10964
import sys
sys.setrecursionlimit(10**9)
N,M=map(int,input().split())

def find_negative_loop(n,w,es):
  dist=[float("inf")]*n
  #この始点はどこでもよい
  dist[1]=0
  
  for i in range(n):
    for j in range(w):
      e=es[j]
      if dist[e[1]]>dist[e[0]]+e[2]:
        dist[e[1]]=dist[e[0]]+e[2]
        if i==n-1:
          return True
  return False

def shortest_path(s,n,w,es):
  #s→iの最短距離
  #s:始点, n:頂点数, w:辺の数, es[i]:[辺の始点,辺の終点,辺のコスト]
  dist=[float("inf")]*n
  #d[i]: s→iの最短距離
  dist[s]=0

  while True:
    update=False
    for p,q,r in es:
      # e: 辺iについて [from,to,cost]
      if dist[p]!=float("inf") and dist[q]>dist[p]+r:
        dist[q]=dist[p]+r
        update=True
    if not update:
      break
      
  return dist

graph=[[] for _ in range(N+1)]
elist=[]
for _ in range(M):
  a,b,c=map(int,input().split())
  graph[a].append(b)
  elist.append((a,b,-c))
  
#remove unnecessary vertex and edge
visited=[None]*(N+1)
def check_reachable(u):
  visited[u]=True
  if u==N:
    reachable[u]=True
    return True
  elif reachable[u]!=None:
    return reachable[u]  

  cnt=0
  for v in graph[u]:
    if not visited[v]:
      ret=check_reachable(v)
      if ret:
        cnt+=1
        
  if cnt>0:
    reachable[u]=True
    return True
  else:
    reachable[u]=False
    return False

reachable=[None]*(N+1)
for i in range(1,N+1):
  if reachable[i]==None:
    visited=[False]*(N+1)
    check_reachable(i)
#print(reachable)
  
elist2=[]
for a,b,nc in elist:
  if reachable[b]:
    elist2.append((a,b,nc))
  
M2=len(elist2)
res1=find_negative_loop(N+1,M2,elist2)

if res1:
  print("inf")
else:
  res2=shortest_path(1,N+1,M2,elist2)
  print(-res2[N])

Measured memory_bytes: 4212
import java.util.Scanner;

public class Main {
	public static void main(String args[]){
		Scanner scan = new Scanner(System.in); 
		
		int H, W;
		
		for(;;){

			H = scan.nextInt();
			W = scan.nextInt();
			
			if(H == 0 && W == 0){
				break;
			}
			for(int i = 0; i < H; i++){
				if(i % 2 != 0){
					evenNumberLine(W);
				}else{
					oddNumberLine(W);
				}
			}
			System.out.println();
		}
	}
	
	static void evenNumberLine(int w){
		for(int i = 0; i < w; i++){
			if(i % 2 != 0){
				System.out.print("#");
			}else{
				System.out.print(".");
			}
		}
		System.out.println();
	}
	
	static void oddNumberLine(int w){
		for(int i = 0; i < w; i++){
			if(i % 2 == 0){
				System.out.print("#");
			}else{
				System.out.print(".");
			}
		}
		System.out.println();
	}
}

Measured memory_bytes: 35480
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <utility>

#define INF 9999999999
#define mod 1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define MOD(x) (x%(mod))
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int>pi;

/*---------------------------------------------------*/

bool used[10];
int d[10][10];
int n,m;

int dfs(int now,int cnt){
  int sum=0;
  //cout<<"now"<<now<<" cnt"<<cnt<<endl;

  if(cnt==n)return 1;
  for(int i=1;i<=n;i++){
    if(d[now][i]&&!used[i]){
      used[i]=true;
      //cout<<"now"<<now<<" cnt"<<cnt<<endl;
      sum+=dfs(i,cnt+1);
      used[i]=false;
    }
  }
  return sum;
}

int main(){
  cin>>n>>m;
  int a,b;
  rep(i,m){
    cin>>a>>b;
    d[a][b]=1;
    d[b][a]=1;
  }
  used[1]=true;
  cout<<dfs(1,1)<<endl;
  return 0;
}


Measured memory_bytes: 256
K,A,B=map(int,input().split())
num=1
count=0
num+=A-1
count+=A-1
if B-A>=2:
  val=(K-count)//2
  num+=val*(B-A)
  count+=2*val

if count!=K:
  val2=K-count
  num+=val2
  count+=val2
print(num)

Measured memory_bytes: 38384
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <array>
#include <cstdio>

using namespace std;

int main()
{
    int N, K;
    if (scanf("%d%d", &N, &K) < 2) return 0;

    array<bool, 200000> boolAry;
    boolAry.fill(false);

    array<int, 200000> intAry;
    intAry.fill(0);

    int A;
    int cnt = 0;
    for (int i = 0; i < N; i++)
    {
        if (scanf("%d", &A) < 1) return 0;
        if (!boolAry[A])
        {
            cnt++;
            boolAry[A] = true;
            intAry[A]++;
        }
        else intAry[A]++;
    }

    if (cnt <= K)
    {
        printf("%d\n", 0);
        return 0;
    }

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

    int ans = 0;
    int c = 0;
    int div = cnt - K;
    for (int i = 0; i < 200000; i++)
    {
        if (intAry[i] != 0)
        {
            ans += intAry[i];
            c++;
        }
        if (div == c) break;
    }

    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 1152
program main
integer N,sup_w!supはsupremum(上限)の略
integer,allocatable,dimension(:)::w,v
integer(16),allocatable,dimension(:,:)::DP
read*,N,sup_w
allocate(w(n),v(n))
allocate(DP(0:N,0:sup_w))
do i=1,n
  read*,w(i),v(i)
end do

DP(:,:)=0
do i=1,N
  do j=0,sup_w
    if(j-w(i)>=0)DP(i,j)=DP(i-1,j-w(i))+v(i)
    DP(i,j)=max(DP(i,j),DP(i-1,j))
  end do
end do

print"(i0)",DP(N,sup_w)
end program main

Measured memory_bytes: 158080
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cmath>
using namespace std;
#define MOD 1000000007
#define INF 1<<30
#define LINF (ll)1<<62
#define MAX 510000
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
#define uni(q) unique(all(q)),q.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;
ll dy[4] = {1,0,-1,0};
ll dx[4] = {0,1,0,-1};


int main(){
    string s; cin >> s;
    ll k; cin >> k;
    ll cnt=0;
    if(s.size()==1){
        cout << k/2 << endl;
        return 0;
    }
    bool flag = true;
    rep(i,s.size()-1){
        if(s[i]!=s[i+1]) flag = false;
    }
    ll first=1;
    rep(i,s.size()-1){
        if(s[i]==s[i+1]){
            first++;
        }else{
            break;
        }
    }
    rep(i,s.size()-1){
        if(s[i]==s[i+1]){
            s[i+1] = '.';
            cnt++;
        }
    }
    //cout << flag << endl;
    ll ans = k*cnt;
    if(s[s.size()-1]==s[0]){
        if(first%2!=0) ans += k-1;
    }
    //cout << ans << endl;
    if(flag && (k*s.size())%2==1) ans-=k/2;
    cout << ans << endl;
    //cout << first << endl;
}


Measured memory_bytes: 256
X = int(input())

if X <= 599:
    print(8)
elif X <= 799:
    print(7)
elif X <= 999:
    print(6)
elif X <= 1199:
    print(5)
elif X <= 1399:
    print(4)
elif X <= 1599:
    print(3)
elif X <= 1799:
    print(2)
else:
    print(1)


Measured memory_bytes: 9176
#include <bits/stdc++.h>
 using namespace std;
 int N, A[3][3], b[10];
 bool appear[3][3];
 int main() {
 for(int i = 0; i < 3; i++) {
 for(int j = 0; j < 3; j++) cin >> A[i][j];
 }
 cin >> N;
 for(int i = 0; i < N; i++) cin >> b[i];
 for(int i = 0; i < N; i++) {
 for(int j = 0; j < N; j++) {
 appear[i][j] = false;
 for(int k = 0; k < N; k++) {
 if(A[i][j] == b[k]) appear[i][j] = true;
 }
 }
 }
 string ANS = "No";
 for(int i = 0; i < 3; i++) {
 if(appear[i][0] and appear[i][1] and appear[i][2]) ANS = "Yes";
 }
 for(int i = 0; i < 3; i++) {
 if(appear[0][i] and appear[1][i] and appear[2][i]) ANS = "Yes";
 }
if(appear[0][0] and appear[1][1] and appear[2][2]) ANS = "Yes";
if(appear[0][2] and appear[1][1] and appear[2][0]) ANS = "Yes";
cout << ANS << endl;
return 0;}

Measured memory_bytes: 256
import Control.Monad (replicateM)

main :: IO ()
main = do
  [a,_,_,_,e,k] <- map (read :: String -> Int) <$> getNLine_ 6
  if e - a <= k then putStrLn "Yay!" else putStrLn ":("

getNLine_ :: Int -> IO [String]
getNLine_ n = replicateM n getLine

Measured memory_bytes: 508
//***Little by little one travels far***
 
#include<bits/stdc++.h>
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i,n) for(i=0;i<n;i++)
#define forn(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define for1(i, n) for (ll i = 1; i <= (ll)(n); ++i)
#define ford(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); ++i)
#define fora(it,x) for(auto it:x)
#define PI 3.14159265
#define sync ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl "\n"
 
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef long double ld;
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

pair<ll,ll> p[2*100001];

bool comp(pair<ll,ll>a,pair<ll,ll> b){
    if(a.se<b.se) return(1);
    else return(0);
}

int main()
{
    ll n,t=0;
    cin>>n;

    forn(i,n){
        ll a,b;
        cin>>a>>b;
        p[i]=mp(a,b);
    }
    
    sort(p,p+n,comp);

    for(ll i=0;i<n;i++){
        if((p[i].fi +t)>p[i].se){
            cout<<"No";
            return 0;
        }
        t=t+p[i].fi;
    }
    cout<<"Yes";
}



Measured memory_bytes: 3328
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <locale>
#include <iostream>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> int len(const T &x) { return x.size(); }

template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
  auto val = table(args...);
  return vector<decltype(val)>(n, move(val));
}

struct yes_no : numpunct<char> {
  string_type do_truename()  const { return "YES"; }
  string_type do_falsename() const { return "NO"; }
};

void solve(ll A, ll B, ll C, ll D) {
  cout << max(0LL, min(B, D) - max(A, C)) << endl;
}

int main() {
  locale loc(locale(), new yes_no);
  cout << boolalpha << setprecision(12) << fixed;
  cout.imbue(loc);
	ll B;
	ll A;
	ll C;
	ll D;
	scanf("%lld", &A);
	scanf("%lld", &B);
	scanf("%lld", &C);
	scanf("%lld", &D);
	solve(A, B, C, D);
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner std = new Scanner(System.in);
        long w = std.nextLong();
        long h = std.nextLong();
        long x = std.nextLong();
        long y = std.nextLong();

        double sq = w * h / 2.0;
        if (w / 2.0 == x && h / 2.0 == y) {
            System.out.println(sq + " 1");
        } else {
            System.out.println(sq + " 0");
        }
    }
}


Measured memory_bytes: 21844
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner stdIn = new Scanner(System.in);
		long A = stdIn.nextLong();
		long B = stdIn.nextLong();
		long K = stdIn.nextLong();
		if(A >= K){
			System.out.println((A - K) + " "  + B);
		}
		else{
			K = K - A;
			if(B >= K){
				System.out.println(0 + " " + (B - K));
			}
			else{
				System.out.println("0 0");
			}
		}
		stdIn.close();
	}
}


Measured memory_bytes: 38568
L = int(input())
b = format(L, 'b')
n = len(b)
m = 2 * (n - 1) + b.count('1') - 1
print(n, m)
for i in range(1, n):
    print(i, i + 1, 0)
    print(i, i + 1, 2 ** (i - 1))
w = 2 ** (n - 1)
for j in range(20,-1,-1):
    if (L - w) >> j & 1:
        print(j + 1, n, w)
        w += 2 ** j

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

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

    string S, T;

    int count = 0;

    cin >> S;
    cin >> T;

    vector<char> s;
    vector<char> t;

    for(int i = 0; i < S.size(); i++){
        s.push_back(S[i]);
    }

    for(int i = 0; i < T.size(); i++){
        t.push_back(T[i]);
    }

    for(int i = 0; i < t.size(); i++){
        if (s[i] == t[i]){
            count = count + 1;
        }
    }

    cout << count;

}

Measured memory_bytes: 256
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
satis = 0
pre = -9
for i in a:
	satis += b[i - 1]
	if i - 1 == pre:
		satis += c[i - 2]
	pre = i
print (satis)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i, n)     for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n)    for (int i = 1; i <= (int)(n); ++i)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define rrep(i, n)    for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n)   for (int i = (int)(n); i >= 1; --i)
#define allrep(V, v)  for (auto &&V : v)
#define all(x)        (x).begin(), (x).end()
using lint = long long;
constexpr int    INF  = 1 << 30;
constexpr lint   INFL = 1LL << 62;
constexpr int    MOD  = 1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;

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

  int n;
  cin >> n;
  map<lint, lint, greater<lint>> ab;
  lint asum = 0;
  rep (i, n) {
    lint a, b;
    cin >> a >> b;
    ab[b] += a;
    asum  += a;
  }
  bool check = true;
  allrep (AB, ab) {
    if (asum > AB.first) {
      check = false;
      break;
    }
    asum -= AB.second;
  }
  cout << (check ? "Yes" : "No") << endl;
  return 0;
}

Measured memory_bytes: 12800
import java.util.Scanner;

/**
 * A3
 */
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len = Integer.parseInt(sc.nextLine());
        int result = 0;
        for(int i=0; i<len; i++){
            if(check(sc.nextInt())){
                result++;
            }
        }
        sc.close();
        System.out.println(result);
    }

    private static Boolean check(int n){
        int max = (int)Math.sqrt(n);
        for(int i=2; i<=max; i++){
            if(n%i == 0){
               return false;
            }
        }
        return true;
    }
}


Measured memory_bytes: 41180
n, s = map(int, input().split())
a = list(map(int, input().split()))

mod = 998244353

dp = [[0] * n for _ in range(3000 + 1)]

# init
dp[a[0]][0] = 1

for i in range(1, s + 1):
    for j in range(1, n):
        if i == a[j]:
            dp[i][j] = (dp[i][j-1] + j + 1) % mod
        elif i - a[j] > 0:
            dp[i][j] = (dp[i][j-1] + dp[i - a[j]][j - 1]) % mod
        else:
            dp[i][j] = dp[i][j-1] % mod



ans = 0
for j in range(n):
    ans += dp[s][j]

print(ans % mod)


Measured memory_bytes: 112860
#include<iostream>
#include<cmath>
#define ll long long int
using namespace std;

int main()
{
  ll n,a,b;
  cin>>n;
  //cout<<n<<endl;
  for(ll i=(ll)sqrt(n);i>0;i--)
  {
    //cout<<(n%i)<<endl;
    if((n%i)==0){
      a=i;
      b=n/i;
      break;
    }
  }
  cout<<(a+b-2)<<endl;
  
  return 0;
}
    	

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <stack>
#include <functional>
#include <queue>
#include <cmath>

#define rep(i,j,k) for(int i=j;i<k;i++)
#define drep(n,m) for(int i=0;i<n;i++)for(int j=0;j<m;j++)
#define fi first
#define se second
#define vi vector<int>
#define INF 1000000000
#define MOD 1000000009
#define pb push_back
#define mp make_pair
typedef long long ll;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

using namespace std;

ll gcd(ll a,ll b){
    if(a<b){
        int t=a;a=b;b=t;
    }
    int c=a%b;
    while(c!=0){
        a=b;
        b=c;
        c=a%b;
    }
    return b;
}

ll lcm(ll a,ll b){
    return a*b/gcd(a,b);
}

bool isPrime(int x){
    if(x==1)return false;
    if(x==2)return true;
    if(x%2==0)return false;
    for(int i=3;i<=sqrt(x);i+=2){
        if(x%i==0)return false;
    }
    return true;
}

int main() {
    string day[7]={"Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"};
    int t=3;
    int v[12]={31,29,31,30,31,30,31,31,30,31,30,31};
    int mo,da;
    while(cin>>mo>>da){
        if(mo==0&&da==0)break;
        rep(i,1,12+1){
            rep(j,1,v[i-1]+1){
                if(i==mo&&j==da){
                    cout<<day[t]<<endl;
                    goto AWAY;   
                }
                t++;
                if(t==7)t=0;
            }
        }
        AWAY:;
        t=3;
    }
    
  
    return 0;
}



Measured memory_bytes: 3160
from math import *

x, y, a, b, c = map(int, input().split())
p = [int(i) for i in input().split()]
q = [int(i) for i in input().split()]
r = [int(i) for i in input().split()]
p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)
cres = sum(p[:x]) + sum(q[:y])
x -= 1
y -= 1
#print(cres, p, q, x, y)
for i in range(min(x + y + 2, c)):
    if x >= 0 and r[i] > p[x] and (y < 0 or p[x] <= q[y]):
        cres += r[i] - p[x]
        x -= 1
    elif y >= 0 and r[i] > q[y]:
        cres += r[i] - q[y]
        y -= 1
print(cres)


Measured memory_bytes: 104548
#include <bits/stdc++.h>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

int main(void)
{
    ll x;
    cin >> x;
    if(x <= 6){
        pr(1);
        return 0;
    }
    if(x <= 11){
        pr(2);
        return 0;
    }
    if((x%11) == 0){
        pr((x/11)*2);
        return 0;
    }
    ll ans = x/11;
    if(x%11 <= 6){
        pr(ans*2+1);
    }else{
        pr(ans*2+2);
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <utility>
#include <deque>
#include <stack>
#include <bitset>
#include <ctime>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
#define rep(i,n) for (int i=0;i<n;++i)
#define REP(i,n) for (int i=1;i<=n;++i)
#define all(x) x.begin(),x.end()
#define mp make_pair
#define pb push_back
#define pf push_front
#define F first
#define S second
#define read(x) scanf("%d",&x)
string S,T;
string S2,S3;
const ll P=1e9+21,MOD=1e9+7;
const ll H=32323;
int maxMatch[4500005];
ll Hpow[4500005];
int Tsize;
int main(){
	ios::sync_with_stdio(false);
	cin>>S>>T;Tsize=T.size();
	Hpow[0]=1;
	for (int i=1;i<4500005;++i) Hpow[i]=Hpow[i-1]*H%MOD;
	while(S2.size()<=Tsize+S.size()) S2+=S;
	// max len of S=1.5e6
	S3=S2;S2+=S2;S3+=S2;
	ll hashT=0;
	for (int i=0;i<Tsize;++i){
		hashT+=T[i];hashT*=H;hashT%=MOD;
	}
	ll hashS=0;
	for (int i=0;i<Tsize;++i){
		hashS+=S2[i];hashS*=H;hashS%=MOD;
	}
	if (hashS==hashT) maxMatch[Tsize-1]=1;// end pos
	int ans2=maxMatch[Tsize-1];
	for (int i=Tsize;i<S2.size();++i){
		hashS-=S2[i-Tsize]*Hpow[Tsize]%MOD;
		hashS+=S2[i];
		if (hashS<0) hashS+=MOD;
		hashS*=H;
		hashS%=MOD;
		if (hashS==hashT) maxMatch[i]=maxMatch[i-Tsize]+1;
		ans2=max(ans2,maxMatch[i]);
	}
	int ans3=ans2;
	for (int i=S2.size();i<S3.size();++i){
		hashS-=S3[i-Tsize]*Hpow[Tsize]%MOD;
		hashS+=S3[i];
		if (hashS<0) hashS+=MOD;
		hashS*=H;
		hashS%=MOD;
		if (hashS==hashT) maxMatch[i]=maxMatch[i-Tsize]+1;
		ans3=max(ans3,maxMatch[i]);
	}
	if (ans3!=ans2) cout<<-1<<endl;
	else cout<<ans2<<endl;
	return 0; 
}

Measured memory_bytes: 62860
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            int N = in.nextInt();
            int Q = in.nextInt();
            String S = in.next();
            int[] l = new int[Q];
            int[] r = new int[Q];
            for (int i = 0; i < Q; i++) {
                l[i] = in.nextInt() - 1;
                r[i] = in.nextInt() - 1;
            }

            boolean[] isAC = new boolean[N];
            for (int i = 1; i < N; i++) {
                if (S.charAt(i - 1) == 'A' && S.charAt(i) == 'C') {
                    isAC[i] = true;
                }
            }

            int[] count = new int[N];
            for (int i = 1; i < N; i++) {
                count[i] = (isAC[i] ? 1 : 0) + count[i - 1];
            }

            for (int i = 0; i < Q; i++) {
                System.out.println(count[r[i]] - (l[i] - 1 < 0 ? 0 : count[l[i]]));
            }
        }
    }
}


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

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    int a, b;
    cin >> a >> b;
    if((a+b)%3==0 || a%3==0 | b%3==0) cout << "Possible" << endl;
    else cout << "Impossible" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main() {
    short int n;
    scanf("%hi", &n);
    long long sum = 1000, A[80], stocks = 0;
    for (short int i = 0; i < n; i++) {
        scanf("%lli", A + i);
    }
    for (short int i = 0; i < n; i++) {
        // Buy
        if (i < n - 1 && A[i] < A[i + 1]) {
            stocks += sum / A[i];
            sum %= A[i];
        }
        // Sell
        if (i == n - 1 || A[i] > A[i + 1]) {
            sum += stocks * A[i];
            stocks = 0;
        }
    }
    printf("%lli", sum);
}


Measured memory_bytes: 1732
N = input()
L = len(N)
K = int(input())
dp = [[[0] * 2 for _ in range(K + 1)] for _ in range(L + 1)]
dp[0][0][1] = 1
for i, x in zip(range(L), map(int, N)):
    for k in range(K):
        dp[i+1][k][0] += dp[i][k][0]  # d == 0
        if x == 0:
            dp[i+1][k][1] += dp[i][k][1]
        elif x > 0:
            dp[i+1][k][0] += dp[i][k][1]
        # d != 0
        for d in range(1, 10):
            dp[i+1][k+1][0] += dp[i][k][0]
            if d == x:
                dp[i+1][k+1][1] += dp[i][k][1]
            elif d < x:
                dp[i+1][k+1][0] += dp[i][k][1]
    dp[i+1][K][0] += dp[i][K][0]  # k == K and d == 0
    if x == 0:
        dp[i+1][K][1] += dp[i][K][1]
    elif x > 0:
        dp[i+1][K][0] += dp[i][K][1]
print(sum(dp[-1][K]))


Measured memory_bytes: 3192