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

using namespace std;

int main() {
    unsigned long int h;

    cin >> h;

    unsigned long int count=0;
    unsigned long int i = 0;

    do{
        unsigned long int tmp=1;

        for(int k = 0; k < i; k++) {
            tmp = tmp + tmp;
        }
        count += tmp;

        h = h/2;
        i++;
        //cout<<h <<endl;
    }while(h>=1);

    cout << count << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

int main(void){
  double r,menseki,ensyu;

  scanf("%lf",&r);
  menseki=r*r*M_PI;  ensyu=2.0*r*M_PI;
  printf("%.10f %.10f\n",menseki,ensyu);

  return 0;
}

Measured memory_bytes: 652
#include <iostream>

using namespace std;

int days[10] = {20, 19, 20, 19, 20, 19, 20, 19, 20, 19};
void solve()
{
	int n;
	cin >> n;
	while(n--)
	{
		int y, m, d;
		cin >> y >> m >> d;
		int sum = 0;
		for(int i = y + 1; i < 1000; ++i)
		{
			if(i % 3 == 0)
			{
				sum += 200;
			}
			else
			{
				sum += 195;
			}
		}
		if(y % 3 == 0)
		{
			for(int i = m; i < 10; ++i)
			{
				sum += 20;
			}
			sum += 20 - d;
		}
		else
		{
			for(int i = m; i < 10; ++i)
			{
				sum += days[i];
			}
			if(m % 2 == 0)
			{
				sum += 19 - d;
			}
			else
			{
				sum += 20 - d;
			}
		}
		cout << sum + 1 << endl;
	}
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 1160
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
 
int door[20][20],sw[20][20],light[20],check[40000][20],prev[40000][20][2],q[500000][4];
int N,M,SET,GOAL,FR,TO,EXIT;
char stp[500000][40];

int mark(int code,int now,int from){
	if(check[code][now]!=SET){
		check[code][now]=SET;
		prev[code][now][0]=q[FR][0];
		prev[code][now][1]=q[FR][1];
		q[TO][0]=code;
		q[TO][1]=now;
		q[TO][2]=q[FR][2]+1;
		q[TO][3]=from;
		TO++;
		if(now==N){
			EXIT=1;
			if(code==GOAL)return 1;
		}
	}
	return 0;
}

int search(int code,int now,int from){
	int i;

	for(i=0;i<N;i++){
		if( (code>>i & 1) && (door[now][i+1]==SET) ){
			if(mark(code,i+1,0))return 1;
		}
	}

	for(i=from-1;i<N;i++){
		if(now!=(i+1) && (sw[now][i+1])==SET ){
			if(mark(code^(1<<i),now,i+2))return 1;
		}
	}

	return 0;
}

void write(int code,int now,int pcode,int pre){
	if(now != pre){
		sprintf(stp[TO],"Move to room %d.\n",now);
	}
	else{
		int i;
		for(i=N-1;i>=0;i--){
			if( (code>>i) != (pcode>>i) ){
				sprintf(stp[TO],"Switch %s room %d.\n",(code>>i&1)?"on":"off",i+1);
				return;
			}
		}
	}
}
 
int main(){
    int i,j,k,x,y,code;
 
    while(scanf("%d %d",&N,&M)*(N+M)){
		SET++;

		GOAL=1<<N-1;

		for(i=0;i<M;i++){
			scanf("%d %d",&x,&y);
			door[x][y]=SET;
			door[y][x]=SET;
		}

		for(i=1;i<=N;i++){
			scanf("%d",&light[i]);
		}

		for(i=1;i<=N;i++){
			for(scanf("%d",&k);k>0;k--){
				scanf("%d",&x);
				sw[i][x]=SET;
			}
		}

		code=0;
		
		for(i=N;i>0;i--){
			code=code*2+light[i];
		}

		q[0][0]=code;q[0][1]=1;q[0][2]=0;q[0][3]=1;
		FR=0;TO=1;EXIT=0;

		while(FR<TO){
			if(search(q[FR][0],q[FR][1],q[FR][3])){EXIT=2;break;}
			FR++;
		}

		if(EXIT==2){
			printf("You can go home in %d steps.\n",q[TO-1][2]);
			code=q[TO-1][0];x=q[TO-1][1];FR=q[TO-1][2];
			for(TO=FR-1;TO>=0;TO--){
				y=prev[code][x][1];
				i=prev[code][x][0];
				write(code,x,i,y);
				x=y;code=i;
			}
			for(TO=0;TO<FR;TO++){
				printf("%s",stp[TO]);
			}

		}
		else if(EXIT==1)printf("You can not switch off all lights.\n");
		else printf("Help me!\n");
    }
  
    return 0;
}

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

int n, s, D, Q, l, r, a[30], b[400][30], la[400], u[400];
bool v[400][26];

int f(int p, int q1, int q2) {
	int sz = q2 - q1 + 1;
	return p * sz * (sz + 1) / 2;
}

int main()
{
	int i, j, t, x, t1, t2;
	cin >> D;
	for (i = 0; i < 26; i++) {
		scanf ("%d", &a[i]);
	}
	for (i = 1; i <= D; i++) {
		for (j = 0; j < 26; j++) {
			scanf ("%d", &b[i][j]);
		}
	}
	for (i = 1; i <= D; i++){
		scanf ("%d", &t);
		t--;
		u[i] = t;
		s += b[i][t];
		la[t] = i;
		for (j = 0; j < 26;j++) {
			s -= a[j] * (i - la[j]);
		}
		v[i][t] = 1;
	}
	cin >> Q;
	for (i =0; i < 26; i++) {
		v[0][i] = 1;
		v[D + 1][i] = 1;
	}
	while (Q--) {
		scanf ("%d %d", &t1, &t2);
		t2--;
		x = u[t1];
		s -= b[t1][x];
		v[t1][x] = 0;
		v[t1][t2] = 1;
		u[t1] = t2;
		s += b[t1][t2];
		for (l = t1 - 1; l >= 0; l--) if (v[l][x]) break;
		for (r = t1 + 1; r <= D + 1; r++) if (v[r][x]) break;
		s += f(a[x], l + 1, t1 - 1);
		s += f(a[x], t1 + 1, r - 1);
		s -= f(a[x], l + 1, r - 1);
		for (l = t1 - 1; l >= 0; l--) if (v[l][t2]) break;
		for (r = t1 + 1; r <= D +1; r++) if (v[r][t2]) break;
		s += f(a[t2], l + 1, r - 1);
		s -= f(a[t2], l + 1, t1 - 1);
		s -= f(a[t2], t1 + 1, r - 1);
		printf("%d\n", s);
	}
    return 0;
}


Measured memory_bytes: 3780
/* code by AbhiTaker
         ____
        /    \
       /  __  \              _______      __       _   _    _____    _____
      /  /  \  \            |__   __|    /  \     | | / /  |  ___|  |  _  \
     /  /____\  \     ___      | |      / /\ \    | |/ /   | |__    | |_)  )
    /  /______\  \   |___|     | |     / /__\ \   |   /    |  __|   |    _/
   /  /        \  \            | |    / /----\ \  | |\ \   | |___   | |\ \
  /__/          \__\           |_|   /_/      \_\ |_| \_\  |_____|  |_| \_\
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define M 1000000007
#define N 1001016
#define ff first.first
#define fs first.second
#define sf second.first
#define ss second.second
#define f first
#define s second
#define inf 9000000000000000000
vector<pair<ll, pair<ll, char> >> v[N];
ll vis[N],val[N],flag = 0;
map<pair<ll, ll>, ll > mymap;
unordered_set<ll> lef;

void dfs(ll x)
{
    vis[x] = 1;

    for(auto node: v[x])
    {
        if(!vis[node.f])
        {
            if(node.ss=='R')
                val[node.f] = val[x] + node.sf;
            else
                val[node.f] = val[x] - node.sf;

            dfs(node.f);
        }
        else
        {
            if(abs(val[x] - val[node.f])!=node.sf)
            {
                flag = 1;
                break;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll n,m,i;

    cin>>n>>m;

    for(i=0; i<m; i++)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        if(mymap.find({a,b})!=mymap.end())
        {
            if(mymap[{a,b}] !=c)
                flag = 1;
        }
        else if(mymap.find({b,a})!=mymap.end())
        {
            if(mymap[{b,a}] !=c)
                flag = 1;
        }
        else
        {
            v[a].push_back({b,{c, 'R'}});
            v[b].push_back({a,{c, 'L'}});
            mymap[{a,b}] = c;
            lef.insert(a);
        }

    }

    if(flag)
    {
        cout<<"No\n";
        return 0;
    }

    for(auto i: lef)
    {
        if(!vis[i])
        {
            val[i] = 0;
            dfs(i);
        }
    }

    if(flag)
        cout<<"No\n";
    else
        cout<<"Yes\n";

    return 0;
}


Measured memory_bytes: 61092
n = int(input())
v = list(map(int, input().split()))


even = [0] * (10 ** 5)
odd = [0] * (10 ** 5)

for i in range(0, n, 2):
    even[v[i] - 1] += 1

for i in range(1, n, 2):
    odd[v[i] - 1] += 1

even_max = max(even)
odd_max = max(odd)

even_max_i = even.index(even_max)
odd_max_i = odd.index(odd_max)

if even_max_i == odd_max_i:
    even[even_max_i] = 0
    odd[odd_max_i] = 0

    even_max_2 = max(even)
    odd_max_2 = max(odd)

    ans = n - max(even_max + odd_max_2, even_max_2 + odd_max)
else:
    ans = n - (even_max + odd_max)

print(ans)


Measured memory_bytes: 14404
import statistics
import itertools

n, a, b = map(int, input().split())
v = sorted(list(map(int, input().split())), reverse=True)
mean = statistics.mean(v[:a])


# 組み合わせ数を数え上げる
def count_table(n):
    c = [[0 for _ in range(n+1)] for _ in range(n+1)]
    for i in range(n+1):
        for j in range(i + 1):
            if j == 0 or j == i:
                c[i][j] = 1
            else:
                c[i][j] = c[i-1][j-1] + c[i-1][j]
    return c


count_v_a = 0
pos_v_a = 0
for i in range(n):
    if v[i] == v[a-1]:
        count_v_a += 1
        if i < a:
            pos_v_a += 1

c = count_table(n)
count = 0
if pos_v_a == a:
    for pos in range(a, b + 1):
        count += c[count_v_a][pos]
else:
    count += c[count_v_a][pos_v_a]

print(mean)
print(count)


Measured memory_bytes: 5144
# -*- coding: utf-8 -*-
"""
C - Grid Repainting 2
https://abc096.contest.atcoder.jp/tasks/abc096_c

"""
import sys
from sys import stdin
input = stdin.readline


def is_possible(h, w, pict):
    moves = [(0, -1), (0, 1), (-1, 0), (1, 0)]
    check = True

    ans = [['.'] * w for _ in range(h)]
    for cy in range(h):
        for cx in range(w):
            if ans[cy][cx] != pict[cy][cx]:
                check = False
                for dxy in moves:
                    nx = cx + dxy[0]
                    ny = cy + dxy[1]

                    if 0<= nx <= w-1 and 0 <= ny <= h-1:
                        if pict[ny][nx] == '#':
                            ans[ny][nx] = '#'
                            check = True
                            break
                if check != True:
                    return 'No'
    return 'Yes'


def main(args):
    h, w = map(int, input().split())
    pict = []
    for _ in range(h):
        pict.append(list(input().strip()))

    ans = is_possible(h, w, pict)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


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

using namespace std;

typedef long long lo;
typedef pair< lo,lo > PII;

#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo MAX = -1000000000000000000;
const lo MIN = 1000000000000000000;
const lo inf = 1000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;

int n,m,b[li],a[li],k,flag,t,c[li],dp[li][5];
int cev;
string s;
vector<int> v;

main(void){
	scanf("%lld",&n);
	FOR{
		scanf("%lld %lld %lld",&a[i],&b[i],&c[i]);
	}
	dp[1][1]=a[1];
	dp[1][2]=b[1];
	dp[1][3]=c[1];
	for(int i=2;i<=n;i++){
		dp[i][1]=max(dp[i-1][2]+a[i],dp[i-1][3]+a[i]);
		dp[i][2]=max(dp[i-1][3]+b[i],dp[i-1][1]+b[i]);
		dp[i][3]=max(dp[i-1][2]+c[i],dp[i-1][1]+c[i]);
	}
	printf("%lld\n",max(dp[n][1],max(dp[n][2],dp[n][3])));
	return 0;
}


Measured memory_bytes: 10496
N = int(input())
XL = [list(map(int, input().split())) for _ in range(N)]
RL = [[0, 0] for _ in range(N)]
for i in range(N):
    left = XL[i][0] - XL[i][1]
    right = XL[i][0] + XL[i][1]
    RL[i][0] = left
    RL[i][1] = right

RL.sort(key=lambda x: x[1])
now_right = RL[0][1]
cnt = 0
for i in range(1, N):
    if now_right <= RL[i][0]:
        now_right = RL[i][1]
    else:
        cnt += 1
print(N - cnt)

Measured memory_bytes: 42616
import sys
input = sys.stdin.readline().rstrip

"""
まず一般に剰余込みでの組み合わせの計算。
n!, (n!)^{-1} mod pの値を配列にまとめておき、nCr = (n!)/(r!)((n-r)!)をO(1)で計算する。

max = (用意する配列の最大長)
mod = （剰余）

(n!)^{-1}の計算は¥Prod_i i^{-1}を計算して求める。
i^{-1} mod pの計算はフェルマーの小定理より、mod pにおいて
0 = p = (p // i) * i + (p % i)
0 = (p // i) + (p % i) * i^{-1}
i^{-1} = -(p // i) * (p % i)^{-1}
"""

max = 10**6 * 2 + 3 # ここでRE出しまくってた。。。
mod = 10**9+7
fact = [1, 1] # fact[n] = (n! mod p)
factinv = [1, 1] # factinv[n] = ((n!)^{-1} mod p)
inv = [0, 1] # inv[n] = (n^{-1} mod p)

for i in range(2, max+1):
    fact.append(fact[-1] * i % mod)
    inv.append(-inv[mod % i] * (mod // i) % mod)
    factinv.append(factinv[-1] * inv[-1] % mod)

def cmb(n, r):
    if r < 0 or r > n:
        return 0
    else:
        r = min(r, n-r)
        return fact[n] * factinv[r] * factinv[n-r] % mod


"""
いよいよ本題。
まずは¥Sum_{0¥le i¥le x, 0¥le j¥le y} _{i+j}C_iを計算する。
実際今回の問題は容易にこれに帰着可能。

¥Sum_{0¥le i¥le x, 0¥le j¥le y} _{i+j}C_i
    = ¥Sum_i (¥Sum_j _{i+j}C_i)
    = ¥Sum_i {(T+1)^i + (T+1)^{i+1} + ... + (T+1)^{i+y})のT^iの係数}
    = ¥Sum_i {¥frac{(1+T)^{i+y+1} - (1+T)^i}{T}のT^iの係数}
    = ¥Sum_i _{i+y+1}C_{i+1}

    = ¥Sum_i _{i+y+1}C_y
    = _{y+1}C_y + _{y+2}C_y + ... + _{y+x+1}C_y
    = {(1+T)^{y+1} + (1+T)^{y+2} + ... (1+T)^{y+x+1}のT^yの係数}
    = {¥frac{(1+T)^{x+y+2} - (1+T)^{y+1}}{T}のT^yの係数}
    = _{x+y+2}C_{y+1} - 1
"""
r1, c1, r2, c2 = map(int, input().split())
a = cmb(r2+c2+2, c2+1) - 1
b = cmb(r1+c2+1, c2+1) - 1
c = cmb(r2+c1+1, r2+1) - 1
d = cmb(r1+c1, r1) - 1
ans = a - b - c + d
print(ans % mod)


Measured memory_bytes: 133516
#include<bits/stdc++.h>
using namespace std;
int f[100005];
int vis[100005];
int main() {
    int n; cin >> n;
    for(int i=1; i<=n; i++) {
        cin >> f[i];
    }
 
    int res = 0;
   for(int i=1; i<=n; i++) {
       int a = f[i];
       if(f[a] == i) res++;
 }
  cout << res/2 << endl;
 
}

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

#define INF 1e9
#define LLINF 1e18
#define pi 3.14159265358979323
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;

int gcd(int a, int b) {
    if(a % b == 0) {
        return b;
    }
    else {
        return(gcd(b, a % b));
    }
}


int main() {
    string s;
    cin >> s;
    if (s.size() == 2) {
        cout << s << endl;
        return 0;
    }
    else {
        reverse(s.begin(), s.end());
        cout << s << endl;
        return 0;
    }
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n;i>=0;i--)
#define INF 100000005
#define MAX 1002
#define mp make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;
//__gcd(a,b), __builtin_popcount(a);

int solve(){
	
}

int main(){
	int a[6], t1, t2, t3;
	rep(i,3){
		rep(j,6)scanf("%d", &a[j]);
		t1 = a[0]*3600+a[1]*60+a[2];
		t2 = a[3]*3600+a[4]*60+a[5];
		t3 = t2-t1;t1 = t3/3600;t2 = (t3-t1*3600)/60;
		printf("%d %d %d\n", t1, t2, t3%60);
	}
	return 0;
}

Measured memory_bytes: 3228
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; 
#define INF 1000000000
#define mod 1000000007
typedef long long ll;
const ll LINF = 1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int n;
vector<vector<int>> g;
pair<ll,ll> dfs(int pre,int now){
    ll w=1,b=1;
    for(auto x:g[now])if(x!=pre){
        auto y=dfs(now,x);
        b=(b*y.first)%mod;
        w=(w*(y.first+y.second))%mod;
    }
    return make_pair(w,b);
}

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

    cin>>n;
    g.resize(n);
    rep(i,n-1){
        int u,v;cin>>u>>v;u--,v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    auto ans=dfs(-1,0);
    cout<<(ans.first+ans.second)%mod<<endl;
    return 0;
}


Measured memory_bytes: 12672
n, m = map(int, input().split())
wars = {}
for i in range(m):
  a, b = map(int, input().split())
  if a in wars.keys():
    wars[a] = min(wars[a], b)
  else:
    wars[a] = b

cuts = 0
antis = 10**6

for i in range(1, n):
  if i in wars.keys():
    antis = min(antis, wars[i])
  if i + 1 == antis:
    cuts += 1
    antis = 10**6
    
print(cuts)


Measured memory_bytes: 17892
n, l = map(int, input().split())
taste = [(l + i - 1) for i in range(1, n+1)]

ans = 10 ** 9
ans2 = 0
tmp = sum(taste)


for i in range(n):

    tmp2 = sum(taste) - taste[i]

    if abs(tmp - tmp2) < ans:

        ans = abs(tmp - tmp2)
        ans2 = tmp2



print(ans2)


Measured memory_bytes: 3060
import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy

def main():
    n = int(input())
    p_list = list(map(int, input().split()))
    count = 0
    for i in range(0,n-2):
        if ((p_list[i] < p_list[i+1] < p_list[i+2]) or (p_list[i+2] < p_list[i+1] < p_list[i])):
            count += 1
    print(count)

if __name__ == "__main__":
    main()

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

int main(){
  string s;
  cin >> s;
  if(s[1]==s[2]){
    if((s[0]==s[1])||(s[2]==s[3]))
      cout << "Yes" <<endl;
    else cout << "No" <<endl;
  }
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <unordered_map>
#include <cassert>
#include <limits>

using namespace std;
typedef long long ll;

struct Network {
private:
    vector<unordered_map<ll, ll>> adj;
    bool directed;
public:
    explicit Network(bool directed) : directed(directed) {}

    void add_edge(ll from, ll to, ll weight){
        assert(from >= 0);
        assert(to >= 0);
        assert(weight >= 0);
        if(adj.size() < max(from, to) + 1){
            adj.resize(max(from, to) + 1);
        }
        adj.at(from)[to] = weight;

        if(!directed){
            adj.at(to)[from] = weight;
        }
    }

    ll get_weight(ll from, ll to) const {
        return adj.at(from).at(to);
    }

    void floyd_warhsall(vector<vector<ll>>& out){
        const ll n = adj.size();
        out.resize(adj.size(), vector<ll>(n, -1));
        for(ll i = 0; i < n; ++i){
            for(auto p : adj.at(i)){
                out.at(i).at(p.first) = p.second;
            }
            out.at(i).at(i) = 0;
        }

        for(ll k = 0; k < n; ++k){
            for(ll i = 0; i < n; ++i){
                if(out.at(i).at(k) == -1){
                    continue;
                }
                const ll dik = out.at(i).at(k);
                for(ll j = 0; j < n; ++j){
                    if(out.at(k).at(j) == -1){
                        continue;
                    }
                    const ll dkj = out.at(k).at(j);
                    const ll dij = out.at(i).at(j);

                    if(dij == -1 || dij > dik + dkj){
                        out.at(i).at(j) = dik + dkj;
                    }
                }
            }
        }
    }
};

Network net(false);
vector<ll> city;
vector<vector<ll>> dist;

vector<bool> visited;
vector<ll> path;

ll search(ll pos){
    if(pos == city.size()){
        ll ret = 0;
        for(int i = 1; i < city.size(); ++i){
            ret += dist.at(path.at(i - 1)).at(path.at(i));
        }
        return ret;
    }else{
        ll ret = numeric_limits<ll>::max();
        for(ll nxt = 0; nxt < city.size(); ++nxt){
            if(visited.at(nxt)){ continue; }
            visited.at(nxt) = true;
            path.at(pos) = city.at(nxt);
            ret = min(ret, search(pos + 1));
            path.at(pos) = -1;
            visited.at(nxt) = false;
        }
        return ret;
    }
}

int main(){
    ll n, m, r;
    cin >> n >> m >> r;

    city.resize(r);
    for(int i = 0; i < r; ++i){
        cin >> city.at(i);
        city.at(i)--;
    }

    for(int i = 0; i < m; ++i){
        ll ai, bi, ci;
        cin >> ai >> bi >> ci;
        ai--; bi--;
        net.add_edge(ai, bi, ci);
    }
    net.floyd_warhsall(dist);

    visited.resize(r, false);
    path.resize(r, -1);
    cout << search(0) << endl;
    return 0;
}


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

#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fst first
#define scd second

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

inline int read(){
	int f=1,x=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline ll readll(){
	ll f=1,x=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int MAXN=105;
const ll LINF=(1ll<<62)+4e18;
struct EDGE{int nxt,to;}edge[MAXN<<1];
int head[MAXN],tot;
inline void add_edge(int u,int v){edge[++tot].nxt=head[u];edge[tot].to=v;head[u]=tot;}
int dep[MAXN],x,f[MAXN],g[MAXN],fa[MAXN];
void dfs(int u,int fa){
	dep[u]=dep[fa]+1;
	if(dep[u]>dep[x])x=u;
	f[u]=0;
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==fa)continue;
		f[u]++;
		dfs(v,u);
	}
}
void dfs(int u){
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==fa[u])continue;
		fa[v]=u;
		dfs(v);
	}
}
int n;
int main() {
	n=read();
	for(int i=1,u,v;i<n;++i)u=read(),v=read(),add_edge(u,v),add_edge(v,u);
	x=0;dfs(1,0);int xx=x;x=0;dfs(xx,0);cout<<(dep[x]+1)/2<<" ";//cout<<endl;
	int mind=n;ll ans=LINF;
	for(int rt=1;rt<=n;++rt){
		x=0;dfs(rt,0);
		int md=dep[x];if(md>mind)continue;
		for(int i=1;i<md;++i)g[i]=-1;
		for(int i=1;i<=n;++i)g[dep[i]]=max(g[dep[i]],f[i]);
		ll tmp=1;
		for(int i=1;i<md;++i){
			assert(g[i]!=-1);
			if(LINF/tmp<g[i]){tmp=-1;break;}
			tmp*=g[i];
		}
		if(tmp!=-1){
			if(md<mind||tmp<ans){
				//cout<<rt<<" "<<md<<" "<<tmp<<endl;
				mind=md;
				ans=tmp;
			}
		}
	}
	//cout<<ans<<endl;
	dfs(1);
	for(int u=2;u<=n;++u){
		dep[fa[u]]=0;x=0;dfs(u,fa[u]);
		int md1=dep[x];if(md1>mind)continue;
		dep[u]=0;x=0;dfs(fa[u],u);dep[u]=1;
		int md2=dep[x];if(max(md1,md2)>mind)continue;
		for(int i=1;i<max(md1,md2);++i)g[i]=-1;
		for(int i=1;i<=n;++i)g[dep[i]]=max(g[dep[i]],f[i]);
		ll tmp=1;
		for(int i=1;i<max(md1,md2);++i){
			assert(g[i]!=-1);
			if(LINF/tmp<g[i]){tmp=-1;break;}
			tmp*=g[i];
		}
		if(tmp!=-1){
			if(LINF/2LL<tmp)continue;
			tmp*=2LL;
			//cout<<u<<" "<<fa[u]<<" "<<max(md1,md2)<<" "<<tmp<<endl;
			if(max(md1,md2)<mind||tmp<ans){
				mind=max(md1,md2);
				ans=tmp;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>


int main(int argc, char **argv){
    int n,x;
    x = 0;
    scanf("%d",&n);
    int a[n];
    int i;
    for(i = 0 ; i < n ; i++){
        scanf("%d",&a[i]);
    }
    int xxx;
    for(i = 0 ; i < n ; i++){
        xxx = 1;
        while(xxx == 1){
            if(a[i] % 2 == 0){
                a[i] = a[i] / 2;
                x++;
            }
            else
                xxx = 0;
        }
    }
    printf("%d\n",x);

    return 0;
}


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


using namespace std;

int main() {
	long long a[7];

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

	long long at = a[1] * 2;
	long long ans = 0;

	ans = (a[3]/2)*4 + (a[4]/2)*4 + (a[0]/2)*4;
	ans = max(ans, (a[3]>=1 && a[4]>=1 && a[0]>=1)*6 + ((a[3]-1)/2)*4 + ((a[4]-1)/2)*4 + ((a[0]-1)/2)*4);

	ans += at;

	cout << ans/2 << '\n';

}

Measured memory_bytes: 256
import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
          return  False
    return True

A  = int(input())

j = A
ans = False

while ans == False:
  if is_prime(j) == True:
    print(j)
    ans = True
  else:
    j += 1



Measured memory_bytes: 3060
#include<iostream>
#include<iomanip>
#include<vector>
#include<set>
#include<string>
#include<algorithm>
#include<math.h>
#include<queue>
#include<unordered_set>
using namespace std;

const int MAX = 1010;

int H, W, K;
bool table[MAX * MAX] = { false };

void solve() {
	for (int i = 0; i <= H; i++) {
		for (int j = 0; j <= W; j++) {
			int n = (j * (H - i)) + (i * (W - j));
			table[n] = true;
		}
	}
}

int main() {

	cin >> W >> H >> K;
	solve();
	if (table[K])cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}


Measured memory_bytes: 1280
using System;
using System.Linq;

namespace D
{
    class Program
    {
        private static readonly long MOD = 1000000007;

        static void Main(string[] args)
        {
            string S = Console.ReadLine();
            long[,] dp = new long[S.Length + 1, 4];
            dp[0, 0] = 1;
            for (var i = 1; i <= S.Length; i++)
            {
                if ('A' == S[i - 1])
                    dp[i, 1] += dp[i - 1, 0];
                if ('B' == S[i - 1])
                    dp[i, 2] += dp[i - 1, 1];
                if ('C' == S[i - 1])
                    dp[i, 3] += dp[i - 1, 2];
                if (S[i - 1] == '?')
                {
                    dp[i, 0] += 3 * dp[i - 1, 0];
                    dp[i, 1] += 3 * dp[i - 1, 1];
                    dp[i, 2] += 3 * dp[i - 1, 2];
                    dp[i, 3] += 3 * dp[i - 1, 3];
                    dp[i, 1] += dp[i - 1, 0];
                    dp[i, 2] += dp[i - 1, 1];
                    dp[i, 3] += dp[i - 1, 2];
                }
                else
                {
                    dp[i, 0] += dp[i - 1, 0];
                    dp[i, 1] += dp[i - 1, 1];
                    dp[i, 2] += dp[i - 1, 2];
                    dp[i, 3] += dp[i - 1, 3];
                }

                dp[i, 0] %= MOD;
                dp[i, 1] %= MOD;
                dp[i, 2] %= MOD;
                dp[i, 3] %= MOD;
            }
            Console.WriteLine(dp[S.Length, 3]);
        }
    }
}


Measured memory_bytes: 14432
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
s=sum(b)

for i in range(n-1):
    if a[i]+1==a[i+1]:
        s+=c[a[i]-1]

print(s)

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

constexpr int inf = 0x3f3f3f3f;
constexpr ll linf = 0x3f3f3f3f3f3f3f3fLL;

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

    int n; cin >> n;
    cout << (1 << __lg(n)) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using ll = long long;
using ull = unsigned long long;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
const ll md = 1000000007;
vector<ll> fact(1e6 + 7), invfact(1e6 + 7);

ll fn(ll a, ll r, ll n, ll mod = md) {
    ll res = 1, x = r%mod;
    ll ans = 0;
    while(n) {
        if(n&1) ans = (x*ans + res)%mod;
        res = ((res*x)%mod + res%mod)%mod;
        x = (x*x)%mod;
        n = n/2;
    }
    ans = (ans*a)%mod;
    return ans;
}

ll nCr(ll n, ll r) {
    if(r == 0) return 1;
    ll num = fact[n];
    ll den = (invfact[r] % md *invfact[n-r] % md)%md;
    return (num*den)%md;
}

ll mul(ll a, ll b, ll mod = md) {
    ll res = (a%mod * b%mod)%mod;
    return res;
}

ll mulm(ll a, ll b, ll mod = md) {
    ll r = 0;
    a %= mod;
    while (b) {
        if (b & 1) r = (r+a)%mod;
        a = (a+a)%mod;
        b = b/2;
    }
    r %= mod;
    return r;
}

ll power(ll x, ll n, ll mod = md) {
    ll res = 1;
    x %= mod;
    while (n) {
        if (n & 1)  res = (res*x)%mod;
        n = n/2;
        x = (x*x)%mod;
    }
    return res;
}

ll power2(ll x, ll n) {
    ll res = 1;
    while (n)  
    {  
        if (n & 1)  res = (res*x);  
        n = n/2; 
        x = (x*x);  
    }  
    return res;
}

bool is_prime(ll x) {
    if(x == 1 || x == 0) return false;
    for(int i=2; i*i <= x; i++) {
        if(x%i == 0) return false;
    }
    return true;
}

ll compgcd(ll n, vector<ll> const &primes) { 
    ll res = n; 
    for (ll i=0; primes[i]*primes[i] <= n; i++) {
        if (n % primes[i]== 0) { 
            res -= (res / primes[i]); 
            while (n%primes[i]== 0) {
               n/=primes[i]; 
            }
        } 
    } 
    if (n > 1) {
       res -= (res / n); 
    }
    return res; 
} 

void sieve(vector<bool> &prime, vector<ll> &primes, ll lim) {
    for(int i = 2; i*i <= lim; i++) {
        if(prime[i]) {
            for(int j = 2; j*i <= lim; j++) {
                prime[j*i] = false;
            }
        }
    }
    for(int i = 2; i <= lim; i++) {
        if(prime[i]) {
            primes.push_back(i);
        }
    }
}

void sieveGCD(ll lim, vector<ll> &tab, vector<ll> const &primes) {
    for(int  i = 1; i <= lim; i++) {
        tab[i] = i;
    }
    for(int i = 0; i<primes.size() && primes[i] <= lim; i++) {
        tab[primes[i]] = primes[i]-1;
        for(int j = 2; primes[i]*j <= lim; j++) {
            tab[primes[i]*j] = (tab[primes[i]*j]/primes[i])*(primes[i]-1);
        }
    }
}

ll calc(ll a, ll b, ll r) {
    ll total = r+1;
    ll tmp = a*b;
    ll count = (r/tmp)*max(a,b) + max(a,b);
    if((r/tmp)*tmp + max(a,b) > r) {
        count -= ((r/tmp)*tmp + max(a,b) - r - 1);
    }
    total -= count;
    return total;
}

int main() 
{ 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    for(int i = 0; i < n; i++) {
        cout << s[i] << t[i];
    }
    cout << endl;
    return 0;
}

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

//vector…可変長、データの大きさに合わせてサイズを変える
//list…双方向リスト、要素を挿入、削除の多いとき
//forward_list
//array…固定長配列
//set…集合
//multiset
//bitset…2進数、固定長ビット列
//map…連想配列、キーと値を関連付ける
//multimap
//deque
//stack…FILO
//queue…FIFO
//priority_queue…格納された最大値から順に取り出す
//pair…二つの値を一組
//tuple…複数の値を一組

template<typename T>
void remove(std::vector<T>& vector, char index) {
    vector.erase(vector.begin() + index);
}

template<class T>
T ma(std::vector<T> &v) {
    T maxi = 0;
    for(auto &i:v) maxi = max(maxi, i);
    return maxi;
}

template<class T>
T mi(std::vector<T> &v) {
    T mini = 0;
    for(auto &i:v) mini = min(mini, i);
    return mini;
}

template <class T>
T pow(T x, T y, T n = numeric_limits<T>::max()) {
    if(y == 0) return 1;
    if(y % 2 == 0) return pow((x * x) % n, y / 2);
    return (x * pow(x, y - 1)) % n;
}

#define rep(i, n, m) for (int i = n; i <= m; i++)
#define Rep(i, n, m) for (int i = m; i >= 1; i--)

typedef long long ll;
typedef unsigned long long ull;

ll ans = 0;
/*
int gcd(int x, int y) {
    if (x < y) swap(x, y);
    return !y ? x : gcd(x % y, y);
}
*/
int main() {
    int x, a;
    cin >> x >> a;
    if (x < a) cout << 0 << endl;
    else cout << 10 << endl;
}

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		try (Scanner sc = new Scanner(System.in);) {

			int n = Integer.parseInt(sc.next());

			int stock = 0;

			int counter = 0;

			for (int i = 0; i < n; i++) {
				int ad = Integer.parseInt(sc.next());
				if (stock == ad) {
					counter++;
					stock = 0;
					continue;
				}
				stock = ad;

			}

			System.out.println(counter);
		}
	}
}


Measured memory_bytes: 23252
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: usize = iterator.next().unwrap().parse().unwrap();
    let m: usize = iterator.next().unwrap().parse().unwrap();

    let mut uf = union_find::UnionFind::new(n);
    for _ in 0..m {
        let ai: usize = iterator.next().unwrap().parse().unwrap();
        let bi: usize = iterator.next().unwrap().parse().unwrap();
        let ai = ai - 1;
        let bi = bi - 1;
        uf.unite(ai, bi);
    }

    let ans = uf.len() - 1;
    ans.to_string()
}


#[allow(dead_code)]
mod union_find {
    pub struct UnionFind {
        parent: Vec<usize>,
        sizes: Vec<usize>,
        len: usize,
    }

    impl UnionFind {
        pub fn new(n: usize) -> UnionFind {
            UnionFind {
                parent: (0..n).map(|i| i).collect(),
                sizes: vec![1; n],
                len: n,
            }
        }

        pub fn find(&mut self, x: usize) -> usize {
            if self.parent[x] == x {
                x
            } else {
                let px = self.parent[x];
                self.parent[x] = self.find(px);
                self.parent[x]
            }
        }

        pub fn unite(&mut self, x: usize, y: usize) {
            let px = self.find(x);
            let py = self.find(y);

            if px == py {
                return;
            }

            let (large, small) = if self.sizes[px] < self.sizes[py] {
                (py, px)
            } else {
                (px, py)
            };

            self.parent[small] = large;
            self.sizes[large] += self.sizes[small];
            self.sizes[small] = 0;
            self.len -= 1;
        }

        pub fn same(&mut self, x: usize, y: usize) -> bool {
            self.find(x) == self.find(y)
        }

        pub fn size(&mut self, x: usize) -> usize {
            let px = self.find(x);
            self.sizes[px]
        }

        pub fn len(&self) -> usize {
            self.len
        }
    }
}


Measured memory_bytes: 4768
#include <stdio.h>
#include <math.h>
#define N 10000

int main(){
  
  int n, i, j;
  int a[N];
  int sum, count = 0;

  scanf("%d",&n);
  
  for(i = 0; i < n; i++){
    scanf("%d", &a[i]);
  }

  for(i = 0; i < n; i++){

    sum = 2;    

    if(a[i] == 2){
      count++;
    }
    else if(a[i] % 2 != 0){
      
      for(j = 3; j <= sqrt(a[i]) ; j += 2){

	if(a[i] % j == 0){
	  sum++;
	  break;

	}
	
      }
      
      if(sum == 2) count++;

    }
    

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

Measured memory_bytes: 628
#include <iostream>
using namespace std;
 
int main()
{
  int x, n, i, j, k, C;
 
  while(1)
    {
      C=0;
      cin >> n >> x;
 
      if(n==0 && x==0)
    break;
       
      for(i=1;i<=n-2;i++)
    for(j=1+i;j<=n-1;j++)
      for(k=1+j;k<=n;k++)
        if(i+j+k==x)
          C += 1;
 
      cout << C << endl;
    }
}

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

int main(){
  long long X;
  cin >> X;
  long long ng = 0, ok = X;
  while(ok-ng > 1){
    long long mid = (ok+ng)/2;
    long long Y = (mid+1)*mid/2;
    if(Y >= X) ok = mid;
    else ng = mid;
  }
  cout << ok << endl;
}


Measured memory_bytes: 256
using System;

class Program {
    static void Main(string[] args) {
        int a = int.Parse(Console.ReadLine());
        int b = int.Parse(Console.ReadLine());
        int c = int.Parse(Console.ReadLine());
        int x = int.Parse(Console.ReadLine());
        int count = 0;
        for (int i = 0; i <= a; i++) {
            for (int j = 0; j <= b; j++) {
                for (int k = 0; k <= c; k++) {
                    if (500 * i + 100 * j + 50 * k == x) {
                        count++;
                    }
                }
            }
        }
        Console.WriteLine(count);
    }
}

Measured memory_bytes: 11092
#include<vector>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<cctype>
#include<cassert>
#include<cmath>

#define MAX_V 1000
#define MAX_E 10000
#define INF (1<<29)
#define all(c) (c).begin(),(c).end()
#define D(x) cout << #x " is " << (x) << endl
#define rep(i,n) for(int i = 0; i < n; i++)
#define foreach(it,c) for(__typeof__((c).begin()) it=(c).begin();it!=(c).end();it++)

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef pair<int,int>pii;
typedef pair<int,pii>piii;

string toStr(int num){
  if(num==0)return "0";
  string res = "";
  while(num){
    res+=(num%10)+'0';
    num/=10;
  }
  reverse(res.begin(),res.end());
  return res;
}

int toInt(string s){return atoi(s.c_str());}

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

int par[MAX_V],rank[MAX_V];

void init(int n){
  for(int i=0;i<n;i++){
    par[i]=i;
    rank[i]=0;
  }
}

int find(int x){
  if(par[x]==x)return x;
  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);
}

struct edge{int u,v,cost;};

bool cmp(const edge &e1,const edge &e2){
  return e1.cost<e2.cost;
}

vector<edge> es;
int V,E;

int kruskal(){
  
  vector<int>res;

  init(V);
 
  rep(i,E){
    edge e=es[i];
    if(!same(e.u,e.v)){
      unite(e.u,e.v);
      res.push_back(e.cost);
    }
  }
  sort(all(res));
  if(res.size()%2==0)return round((double)((double)res[res.size()/2-1]+(double)res[res.size()/2])/2);
  return res[res.size()/2];
}

bool ok(){
  bool fg=true;
  for(int i=0;i<V;i++){
    for(int j=0;j<V;j++){
      fg&=same(i,j);
    }
  }
  return fg;
}

int main(void){

  while(cin >> V >> E,V|E){
    es.clear();
  
    rep(i,E){
      int a,b,c;
      cin >> a >> b >> c;
      es.push_back((edge){a-1,b-1,c});
    }

    sort(all(es),cmp);
    /*
    int l=0,r=es.size(),ans=0;
    while(r-l>1){
      int m=(l+r)/2;
      kruskal(m);
      
      if(ok())r=m,ans=m;
      else l=m;
    }
    if(es.size()%2==0)cout << (es[ans].cost+es[ans+1].cost)/2 << endl;
    else cout << es[ans].cost << endl;
    */
    cout << kruskal() << endl;
  }
  return 0;
}

Measured memory_bytes: 1448
#ifndef ONLINE_JUDGE
    #include "debug.cpp"
#endif

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long

const int inf = 1e18 + 5;

void solve()
{
    string s, t;
    cin >> s >> t;
    int ans = inf;
    for(int i = 0; i + t.size() <= s.size(); i++)
    {
        int cnt = 0;
        for(int j = i; j < i + t.size(); j++)
        {
            if(s[j] != t[j - i])
                cnt++;
        }
        // deb(cnt);
        ans = min(ans, cnt);
    }
    cout << ans << endl;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}


Measured memory_bytes: 3616
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <functional>
#include <ctime>
#include <cmath>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iomanip>
#include <float.h>
#include <math.h>
using namespace std;
using ll = long long;
unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

ll ll_gcd(ll a, ll b) {
    if (a < b) return ll_gcd(b, a);
    ll r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

class UnionFind {
public:
    vector <ll> par;
    vector <ll> siz;
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    ll root(ll x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

int main() {
    ll n;
    string s;
    ll t;
    cin >> n >> s >> t;
    for (int i = 0; i < n; i++) {
        if (s[i] != s[t - 1])s[i] = '*';
    }
    cout << s << endl;
}

Measured memory_bytes: 3620
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <tuple>
#include <unordered_map>
#include <list>
#include <numeric>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <ctime>
#include <cassert>
#include <random>

#define INF 1000000000
#define LINF 9000000000000000000
#define mod  1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;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 mp make_pair

using namespace std;

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

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

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

int main(){
  set<int> se;
  int n;
  for(int i = 0; i < 28; i++){
    cin >> n;
    se.insert(n);
  }

  for(int i = 1; i <= 30; i++){
    if(se.find(i) == se.end()) cout << i << endl;
  }
  return 0;
}



Measured memory_bytes: 3132
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>
#include<math.h>

#define DIV 1000000007
using namespace std;
using ll = long long;

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

	int N = S.size();
	vector<ll> amari(N + 1);
	vector<ll> rem(2019);
	ll temp = 1;
	for (int i = 1; i <= N; i++) {
		amari[i] = amari[i - 1] + (S[N-i]-'0')*temp;
		amari[i] %= 2019;
		temp *= 10;
		temp %= 2019;
		rem[amari[i]]++;
	}
	rem[0]++;
	ll ans = 0;
	for (int i = 0; i < 2019; i++) {
		//printf("rem[%d]=", i);
		//cout << rem[i] << endl;
		ans += rem[i] * (rem[i] - 1) / 2;
	}

	cout << ans << endl;
}


Measured memory_bytes: 5188
L = gets.to_i
a = []
L.times do 
  a << gets.to_i
end

dp = Array.new(L+1){[10**16]*5}
dp[0][0] = 0
L.times do |i|
  dp[i+1][0] = dp[i][0] + a[i]
  dp[i+1][1] = [dp[i][1],dp[i][0]].min + (a[i] == 0 ? 2 : (a[i].even? ? 0 : 1))
  dp[i+1][2] = [dp[i][2],dp[i][1],dp[i][0]].min + (a[i].odd? ? 0 : 1)
  dp[i+1][3] = [dp[i][3],dp[i][2],dp[i][1]].min + (a[i] == 0 ? 2 : (a[i].even? ? 0 : 1))
  dp[i+1][4] = dp[i].min + a[i]
end
p dp[L].min


Measured memory_bytes: 35124
#include <cstdio>
#include <vector>
#include <stack>
#include <iostream>
#include <string>
#include <tuple>
#include <random>
#include <map>
#include <queue>
#include <set>
#include <complex>
#include <algorithm>
#include <cassert>
#include <iterator>
#include <numeric>
#include <cmath>
#include <stdio.h>
#include <functional>

using namespace std;
using ll = long long;
using ld = double;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
const ll INF = 1e17;
const ld eps = 1e-10;
const ll MOD = 1e9 + 7;

const double pi = acos(-1.0);
vector<vector<ll>> es;
vector<ll> dim;
vector<bool> visited;
map<P, bool> rev;

void dfs(ll now) {
	visited[now] = true;
	for (auto e : es[now]) {
		if (!visited[e]) {
			dfs(e);
			if (dim[e] % 2) {
				rev[P(min(now, e), max(now, e))] ^= true;
				dim[e]++;
				dim[now]++;
			}
		}
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll N;
	cin >> N;
	ll high = 1;
	while (high * 2 <= N)
		high *= 2;
	if (high == N)
		cout << "No" << endl;
	else {
		cout << "Yes" << endl;
		vector<P> es;
		set<ll> part;
		for (ll i = 0;i < (N + 1) / 4;i++) {
			part.insert(i);
			for (ll j = i * 4;j < i * 4 + 3;j++) {
				if (j == 0)
					continue;
				es.push_back(P(j, j+1));
				es.push_back(P(j + N, j + N + 1));
			}
			es.push_back(P(i * 4 + 3, max(1LL, i * 4) + N));
		}
		if (N % 4 == 0) {
			ll rest = N - high;
			part.erase(part.find(rest / 4));
			es.push_back(P(rest, high));
			es.push_back(P(N, rest));
			es.push_back(P(N + N, high));
		}
		else if (N % 4 == 1) {
			es.push_back(P(N-1, N));
			es.push_back(P(N, 1));
			es.push_back(P(1, N-1+N));
			es.push_back(P(N-1+N, N + N));
		}
		else if (N % 4 == 2) {
			es.push_back(P(N - 2, N-1));
			es.push_back(P(N-1, 1+N));
			es.push_back(P(1+N, N - 2 + N));
			es.push_back(P(N - 2 + N, N -1 + N));
			es.push_back(P(N, N - 2 + N));
			es.push_back(P(N+N, 3));
		}
		while (part.size() > 1) {
			auto ite = part.begin();
			ll f = *ite;
			ite++;
			es.push_back(P(max(1LL, f * 4), max(1LL, *ite * 4)));
			part.erase(ite);
		}
		for (auto e : es) {
			ll a, b;
			tie(a, b) = e;
			cout << a << " " << b << endl;
		}
	}
	return 0;
}



/*
7 6
2 1
2 4
5 2
1 3
3 6
7 3
*/


Measured memory_bytes: 7948
//** aman**/
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define dl          double
#define hell        1000000007
#define endl        '\n'
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define lb lower_bound
#define ub upper_bound
#define bs          binary_search
#define ios         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int main(){
	ll n;cin>>n;
	ll a[n+1];
	for(ll i=1;i<=n;i++)cin>>a[i];
	ll dp[n+1][n+1]={0};
	for(ll i=1;i<=n;i++){
		if(n%2==1)
		dp[i][i]=a[i];
		else 
		dp[i][i]=-a[i];
	}
	for(ll i=n;i>=1;i--){
		for(ll j=i+1;j<=n;j++){
			if(n%2==(j-i+1)%2)
			dp[i][j]=max(dp[i+1][j]+a[i],dp[i][j-1]+a[j]);
			else
			dp[i][j]=min(dp[i+1][j]-a[i],dp[i][j-1]-a[j]);			
		}
	}
	cout<<dp[1][n]<<endl;
}

Measured memory_bytes: 70656
def solve():
    l,r = map(int, input().split())
    if r-l<2019:
        arr = [i*j%2019 for i in range(l,r) for j in range(i+1,r+1)]
        return min(arr)
    else:
        return 0


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

Measured memory_bytes: 75332
#include<stdio.h>

#define N 100
#define INF 100000
#define WHITE 1
#define BLACK 0

int main(){

  int d[N], color[N], w[N][N];
  int i, j, v;
  int n, u;
  int mincost;
  int count = 0;

  scanf("%d",&n);

  for(i = 0; i < n; i++){
	for(j = 0; j < n; j++){
	  scanf("%d",&w[i][j]);
	}
  }
 
  for(i = 0; i < n; i++){
	d[i] = INF;
	color[i] = WHITE;
  }
  d[0] = 0;

  while(1){
	mincost = INF;
	for(i = 0; i < n; i++){
	  if(d[i] < mincost && color[i] ==WHITE){
		mincost = d[i];
		u = i;
	  }
	}

	if(mincost == INF)break;
	color[u] = BLACK;
	count += mincost;
	
	for(v = 0; v < n; v++){
	  if(w[u][v] == -1) continue;
	  if(d[v] >  w[u][v]) d[v] =  w[u][v];
	}
  }   
  printf("%d\n", count);

  return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

const double EPS = 1.0e-10;

class Point
{
public:
    double y, x;
    Point(){
        y = x = 0.0;
    }
    Point(double y0, double x0){
        y = y0;
        x = x0;
    }
};

int main()
{
    int sequenceNum = 0;
    for(;;){
        int n;
        cin >> n;
        if(n == 0)
            return 0;

        vector<double> x(2*n), y(2*n);
        vector<Point> p1(n), p2(n);
        for(int i=0; i<n; ++i){
            double x0, y0, r;
            cin >> x0 >> y0 >> r;
            x[2*i] = p1[i].x = x0 - r;
            x[2*i+1] = p2[i].x = x0 + r;
            y[2*i] = p1[i].y = y0 - r;
            y[2*i+1] = p2[i].y = y0 + r;
        }
        sort(x.begin(), x.end());
        sort(y.begin(), y.end());

        double ret = 0.0;
        for(int i=0; i<2*n-1; ++i){
            for(int j=0; j<2*n-1; ++j){
                for(int k=0; k<n; ++k){
                    if(p1[k].x <= x[i] && x[i+1] <= p2[k].x && p1[k].y <= y[j] && y[j+1] <= p2[k].y){
                        ret += (y[j+1] - y[j]) * (x[i+1] - x[i]);
                        break;
                    }
                }
            }
        }
        printf("%d %.02f\n", ++sequenceNum, ret);
    }
}

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

inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') f = -1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
	return x * f;
}

const int N = 305;
int f[N][N][N];

int main()
{
	int n = read(), k = read(), P = read();
	
	f[0][1][0] = 1;
	for (int i = 0; i <= n; ++i)
		for (int j = 1; j <= k; ++j)
			for (int k = i; k >= 0; --k)
			{
				if (k) (f[i][j][k - 1] += f[i][j][k]) %= P;
					else (f[i][j + 1][i] += f[i][j][k]) %= P;
				(f[i + 1][j][k] += 1LL * (k + 1) * f[i][j][k] % P) %= P;
			}
	printf("%d\n", f[n][k][0]);
	
	return 0;
}


Measured memory_bytes: 113016