akhauriyash/Code-Regression huggingface dataset:
from heapq import heappush, heappop

R_next = tuple((x, y) for x in range(-3, 0) for y in range(-2, 3) if abs(x) + abs(y) <= 3)
L_next = tuple((x, y) for x in range(1, 4) for y in range(-2, 3) if abs(x) + abs(y) <= 3)
c_num = tuple(str(i) for i in range(10))
L, R = 0, 1
INF = 10 ** 20

def conv(c):
  if c in c_num:
    return int(c)
  if c in ("T", "S"):
    return 0
  return -1

while True:
  w, h = map(int, input().split())
  if w == 0:
    break
  mp = [[-1] * 3 + input().split() + [-1] * 3 for _ in range(h)]
  for i in range(h):
    mp[i] = list(map(conv, mp[i]))
  mp.insert(0, [-1] * (w + 6))
  mp.insert(0, [-1] * (w + 6))
  mp.append([-1] * (w + 6))
  mp.append([-1] * (w + 6))

  def search():
    start = []
    goal = []
    for x in range(3, w + 3):
      if mp[h + 1][x] == 0:
        start.append((x, h + 1))
      if mp[2][x] == 0:
        goal.append((x, 2))

    que = []
    visited = {}
    for x, y, in start:
      heappush(que, (0, x, y, L))
      heappush(que, (0, x, y, R))
      visited[(x, y, L)] = True
      visited[(x, y, R)] = True
 
    while que:
      total, x, y, foot = heappop(que)
      if foot == R:
        direct = R_next
        next_foot = L
      else:
        direct = L_next
        next_foot = R

      for dx, dy in direct:
        nx, ny = x + dx, y + dy
        if (nx, ny) in goal:
          return total
        cost = mp[ny][nx]
        if cost == -1:
          continue
        if not (nx, ny, next_foot) in visited:
          visited[(nx, ny, next_foot)] = True
          heappush(que, (total + cost, nx, ny, next_foot))
    else:
      return -1
  
  print(search()) 


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

int main() {
	int sum = 0;
	int N;
	cin >> N;
	
	vector<int> A;
	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		A.push_back(tmp);
	}
	
	vector <int> B;
	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		B.push_back(tmp);
	}

	vector <int> C;
	for (int i = 0; i < N-1; i++) {
		int tmp;
		cin >> tmp;
		C.push_back(tmp);
	}

	for (int i = 0; i < N; i++) {
		int A_index = A[i] -1;
		int B_point = B[A_index];
		sum += B_point;

		if (i != 0) {
			if (A_index == (A[i - 1])) {
				sum += C[A[i - 1] -1];
			}
		}
	}

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=0;(i)<(n);i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define MOD 1000000007
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; }
#define ALL(v) v.begin(), v.end()
typedef long long ll;


int main(){

int n,m;
cin >> n >> m;
int a[m],b[m];
rep(i,m)cin >> a[i] >> b[i];
int c[n];
rep(i,n)c[i] =0;

rep(i,m){
    c[a[i]-1] += 1;
    c[b[i]-1] += 1;
}

rep(i,n)cout << c[i] << endl;
return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
#include<math.h>
#include<bitset>
#include<queue>
#include<set>
#include<iomanip>
#include<math.h>
#include<assert.h>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long INF = 1LL << 40;
const double INFD = 1e100;
const ll mod = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
// ----------------------------------------------------------------------------

int main(){
  int cnt = 1;
  while(1){
    int N;
    cin >> N;
    if(N == 0){
      break;
    }
    cout << "Case " << cnt << ": " << N << endl;
    cnt++;
  }
  return 0;
}



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


#define off ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define lmax1 9223372036854775807
#define max1 2147483647
#define lmin1 -9223372036854775808
#define pi 3.141592653589793116
#define mod 1e9+7

int main() {
    off;
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    cout<<(a-c)*(b-d)<<'\n';
      return 0;
}

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

ll m,d,n,p;

int main()
{
	cin>>m>>d;
	cin>>n>>p;
	if(m==1 && d==31) cout<<"1\n";
	else if(m==2 && d==28) cout<<"1\n";
	else if(m==3 && d==31) cout<<"1\n";
	else if(m==4 && d==30) cout<<"1\n";
	else if(m==5 && d==31) cout<<"1\n";
	else if(m==6 && d==30) cout<<"1\n";
	else if(m==7 && d==31) cout<<"1\n";
	else if(m==8 && d==31) cout<<"1\n";
	else if(m==9 && d==30) cout<<"1\n";
	else if(m==10 && d==31) cout<<"1\n";
	else if(m==11 && d==30) cout<<"1\n";
	else if(m==12 && d==31) cout<<"1\n";
	else cout<<"0\n";
	return 0;
	
}

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

int a, b, k, ans;

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

    ans = min(a, b);

    int count = 0;
    while(count != k) {
        if (a%ans==0 && b%ans==0) count++;
        if (count!=k) ans--;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[List[int]]"):
    answer = 0

    for i in range(N):
        a = sum(A[0][:i+1])+sum(A[1][i:])
        answer = max(a,answer)
    print(answer)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N)] for _ in range(2)]  # type: "List[List[int]]"
    solve(N, A)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
s=input()
i=0
for c in s:
    i+=1
    if i%2:
        if not(c=='R' or c=='U' or c=='D'):
            print("No")
            break
    else:
        if not(c=='L' or c=='U' or c=='D'):
            print("No")
            break
else: print("Yes")
            

Measured memory_bytes: 3060
/*######################################################
#########~~~~~####~~~~###~~##~~##~~##~~##~~##~~#########
#########~~##~~##~~##~~##~~~#~~##~~~#~~##~~##~~#########
#~~~~~~##~~~~~###~~~~~~##~~#~~~##~~#~~~##~~##~~##~~~~~~#
#########~~######~~##~~##~~##~~##~~##~~##~~##~~#########
#########~~######~~##~~##~~##~~##~~##~~###~~~~##########
######################################################*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;

#pragma GCC optimize("O3")
#define rtn return
#define endl '\n'
#define F first
#define S second
#define mt make_tuple
#define pb push_back
#define MOD 1000000007
#define INF 1e18
#define EPS 1e-15
#define int long long
#define value_at find_by_order
#define index_of order_of_key
#define fill(a, v) memset(a,v,sizeof(a))
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i, n) for(int i=0;i<(int)n;++i)
#define per(i, n) for(int i=(int)n-1;i>=0;--i)
#define loop1(i, n) for(int i=1;i<=(int)n;++i)
#define loop(i, begin, end) for(int i=(begin)-((begin)>(end));i!=(end)-((begin)>(end));i+=1-2*((begin)>(end)))
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " = " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << " = " << arg1 << " |";
  __f(comma+1, args...);
}
#else
#define trace(...)
#endif

typedef string str;
typedef pair<int, int> pll;
typedef vector<int> vll;
typedef vector<pll> vpll;	
typedef long double db;

template<class T, class V> void remin(T &a, V b) { a > b ? a = b : a = a; }
template<class T, class V> void remax(T &a, V b) { a < b ? a = b : a = a; }
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define N 100005

//

int32_t main() {
	FAST_IO;
	
	int x;
	cin >> x;
	cout << 3*x*x;
	rtn 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
using ll = long long;
using P = pair<int, int>;
#include<algorithm>
#include<math.h>
#include<map>
#include<queue>
#include<set>

int main() {
	int n, k;
	cin >> n >> k;
	vector<int>a(n);

	rep(i,n) {
		cin >> a[i];
	}
	
	rep(i, n - k) {
		int s = a[i];
		int buf;
		buf = a[k + i];
		if (buf > s) {
			cout << "Yes" << endl;;
		}
		else {
			cout << "No" << endl;;
		}
		//s = buf;
	}
	return 0;
}

Measured memory_bytes: 4012
import math

n,m = map(int, input().split())
ans = 0
if n >= 2:
  ans += math.factorial(n) // (math.factorial(n - 2) * math.factorial(2))
if m >= 2:
  ans += math.factorial(m) // (math.factorial(m - 2) * math.factorial(2))
print(ans)

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

using namespace std;

int main(void){
    int N; cin >> N;
    int A[N];
    for(int i = 0; i < N; i++){cin >> A[i];}
    bool frag = true;
    int numOfChanged = 0;
    while(frag){
        frag = false;
        for(int i = N-1; 0 < i; i--){
            if(A[i] < A[i-1]){
                int temp = A[i];
                A[i] = A[i-1];
                A[i-1] = temp;
                frag = true;
                numOfChanged ++;
            }
        }
    }
    cout << A[0];
    for(int i = 1; i < N; i++){
        cout <<" " << A[i];
    }
    cout << endl << numOfChanged << endl;
}


Measured memory_bytes: 3084
#include<iostream>
using namespace std;
int main(){
  	int x;
  	int a = 0;
  	cin>>x;
  	int y=x;
  	while(x>0){
      	a+=x%10;
        x/=10;
    }
  	if(y%a==0){
    	cout<<"Yes\n";
    }
  	else
      	cout<<"No\n";
	return 0;
}

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

int main(void){

  int a,hit = 0,blow = 0;
  vector<int> A(4,0),B(4,0);

  while(cin >> a){

    A[0] = a;
    for(int i = 1;i < 4 ;i++){
      cin >> A[i];
    }
    for(int i = 0;i < 4;i++){
      cin >> B[i];
      if(A[i] == B[i]){
          hit++;
      }
      for(int j = 0;j < 4;j++){
        if(B[i] == A[j] && i != j){
          blow++;
        }
      }
    }
    cout << hit << " " << blow << endl;
    hit = 0;blow = 0;
  }



    return 0;
}

Measured memory_bytes: 3100
import math


N, M = map(int, input().split())
A = list(map(int, input().split()))

MAX_N = int(1e4)
dp = [-1 for i in range(MAX_N + 20)]
dp[0] = 0

mc = [2, 5, 5, 4, 5, 6, 3, 7, 6]

for i in range(N + 1):
    for j in A:
        tmp = dp[i]
        if tmp == -1:
            continue
        if tmp == 0:
            dp[i + mc[j - 1]] = max(dp[i + mc[j - 1]], j)
        else:
            dp[i + mc[j - 1]] = max(dp[i + mc[j - 1]], tmp * 10 + j)

ans = dp[N]
print(ans)


Measured memory_bytes: 14692
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,sum[1000100],summ[1000100];
char s[1000010]; 
int main(){
	cin>>n;
	scanf("%s",s+1);
	for(register int i=1;i<=n;++i)
	{
		sum[i]+=sum[i-1];
		if(s[i]=='W') sum[i]++;
	}
	for(register int i=n;i>=1;--i)
	{
		summ[i]+=summ[i+1];
		if(s[i]=='E') summ[i]++;
	}
	int ans=1e9;
	for(register int i=1;i<=n;++i)
	{
		int tmp=sum[i-1]+summ[i+1];
		ans=min(ans,tmp); 
	}
	cout<<ans;
	return 0;
}

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

int main(int argc, char const *argv[]) {
  int x;
  cin>>x;
  int max=0;
  for(int i=1;i<=x;i++){
    for(int j=2;j<10;j++){
      int a=pow(i,j);
      if(a>max&&a<=x) max=a;
    }
  }
  cout<<max<<endl;
  return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#define ld long double
#define ll long long int
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define Ln 20
#define mp make_pair
#define INF (ll)1e9+5
#define dif 0.0000000001
#define pp pair<ll,ll> 
#define sp set<pp>
#define vv vector< pair<ll ,ll> > 
#define vi vector<ll> 
#define SZ 100005
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;

//vi adj[100005];

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

int main() {
    fastio;
    int n,m;
    cin>>n>>m;
    cout<<(n-1)*(m-1);
  
    
    
   
    // your code goes here
	return 0;
}

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

#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)

using namespace std;

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

int n;

ll dfs(string s, int digit) {
  if (s.size() == digit) {
    if (stoi(s) <= n) {
      if (s.find('7') != string::npos
          && s.find('5') != string::npos
          && s.find('3') != string::npos) {
        return 1;
      } else {
        return 0;
      }
    } else {
      return 0;
    }
  }
  int count = 0;
  vector<char> c = {'7', '5', '3'};
  for (char cc : c) {
    count += dfs(s + cc, digit);
  }
  return count;
}

int main() {
  cin >> n;
  ll res = 0;
  for (int i = 3; i <= to_string(n).size(); i++) {
    res += dfs("", i);
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

int a[20], b[20], c[20];
int n, m;

int solve(int a[], int b[], int n) {
  int p[20], vis[20];
  for (int i = 0; i < n; ++ i) p[i] = -1, vis[i] = 0;
  for (int i = 0; i < n; ++ i) {
    for (int j = 0; j < n; ++ j) if (!vis[j] && a[i] == b[j]) {
      p[i] = j; vis[j] = 1; break;
    }
    if (p[i] == -1) return 1e9;
  }
  int ret(0);
  for (int i = 0; i < n; ++ i) {
    for (int j = i + 1; j < n; ++ j) {
      ret += p[i] > p[j];
    }
  }
  return ret;
}

int main() {
  while (scanf("%d%d", &n, &m) == 2) {
    for (int i = 0; i < n; ++ i) scanf("%d", a + i);
    for (int i = 0; i < m; ++ i) scanf("%d", b + i);
    for (int i = 0, t(0); i < m; ++ i) {
      for (int j = 0; j < b[i]; ++ j) {
        c[t ++] = i & 1;
      }
    }
    int ret = solve(a, c, n);
    for (int i = 0; i < n; ++ i) c[i] ^= 1;
    ret = min(ret, solve(a, c, n));
    printf("%d\n", ret);
  }
  return 0;
}

Measured memory_bytes: 1176
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int N;
string S;
int Q;
int k[100];
ll D[1000010];
ll M[1000010];
ll C[1000010];
ll sum[1000010];
ll ans[100];

void input(){
    cin >> N >> S >> Q;
    for(int i = 0; i < Q; i++){
        cin >> k[i];
    }
}

void solve(){
    for(int i = 0; i < N; i++){
        if(S[i] == 'M') M[i]++;
        M[i + 1] = M[i];
        if(S[i] == 'C') C[i]++;
        C[i + 1] = C[i];
    }

    for(int i = 1; i < N; i++){
        sum[i] = sum[i - 1];
        if(S[i] == 'C') sum[i] += M[i];
    }

    for(int i = 0; i < Q; i++){
        for(int j = 0; j < N; j++){
            if(S[j] != 'D') continue;
            int nd = min(j + k[i] - 1, N - 1);
            ll res = sum[nd] - sum[j] - M[j] * (C[nd] - C[j]);
            ans[i] += res;
        }
    }
}

void output(){
    for(int i = 0; i < Q; i++){
        cout << ans[i] << endl;
    }
}

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

Measured memory_bytes: 25988
N = int(input())
A = map(int, input().split())

ans = 0
m = 10 ** 9 + 1
cnt = 0
for a in A:
    if a < 0:
        cnt ^= 1
        a *= -1
    m = min(m, a)
    ans += a

if cnt:
    ans -= 2 * m

print(ans)


Measured memory_bytes: 11192
N, K = map(int, input().split())
hs = []
for i in range(N):
    hs.append(int(input()))
hs = sorted(hs)

diff = hs[-1]
for i in range(N - K + 1):
    diff = min(hs[i+K-1] - hs[i], diff)
print(diff)

Measured memory_bytes: 8280
#include "iostream"
using namespace std;

int main()
{
	int cards[4][13];

	int m;//枚数
	cin >> m;

	char e;//絵柄
	int rank;//ランク

	for (int i = 1; i <= 13; i++){//全カード
	
		cards[0][i-1] = i;

	}
	for (int i = 1; i <= 13; i++){

		cards[1][i - 1] = i;
		
	}
	for (int i = 1; i <= 13; i++){

		cards[2][i - 1] = i;

	}
	for (int i = 1; i <= 13; i++){

		cards[3][i - 1] = i;

	}

	for (int i = 1; i <= m;i++){//持ってるカードを消す
		cin >> e >>rank ;
		if (e=='S'){
			cards[0][rank-1]=0;
		}
		if (e == 'H'){
			cards[1][rank - 1] = 0;
		}
		if (e == 'C'){
			cards[2][rank - 1] = 0;
		}
		if (e == 'D'){
			cards[3][rank - 1] = 0;
		}
	}



	for (int i = 1; i <= 13; i++){//足りないカードの出力
		if (cards[0][i - 1] != 0){

			cout << "S " << cards[0][i - 1] << endl;

		}
	}
	
	for (int i = 1; i <= 13; i++){//足りないカードの出力
		if (cards[1][i - 1] != 0){

			cout << "H " << cards[1][i - 1] << endl;

		}
	}
	for (int i = 1; i <= 13; i++){//足りないカードの出力
		if (cards[2][i - 1] != 0){

			cout << "C " << cards[2][i - 1] << endl;

		}
	}
	for (int i = 1; i <= 13; i++){//足りないカードの出力
		if (cards[3][i - 1] != 0){

			cout << "D " << cards[3][i - 1] << endl;

		}
	}


	return 0;
}



Measured memory_bytes: 3068
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).begin(), (c).end())

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;
typedef map<int, int> M;

constexpr ll INF = 1e18;
constexpr ll MOD = 1e9 + 7;
constexpr double PI = 3.14159265358979323846;
constexpr int di[] = {0, 0, 1, -1};
constexpr int dj[] = {1, -1, 0, 0};

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

    int n;
    ll m, v, p, a[112345];

    cin >> n >> m >> v >> p;
    REP(i, n)
    cin >> a[i];

    sort(a, a + n);

    int l = -1;
    int r = n - p;

    while (r - l > 1)
    {
        int mid = (r + l) / 2;

        ll aa[112345];

        REP(i, n)
        aa[i] = a[i];

        int fc = 0;

        int i = max(0LL, mid - v + 1);
        while (i <= mid)
            aa[i] += m, fc++, i++;

        i = n - (p - 1);
        while (i < n)
        {
            if (fc < v)
                aa[i] += m, fc++;
            i++;
        }

        ll re = (v - fc) * m;

        bool ng = false;

        for (int i = mid + 1; i < n - (p - 1); i++)
        {
            re -= max(0LL, min(m, aa[mid] - aa[i]));
            if (aa[mid] < aa[i])
                ng = true;
        }

        if (ng || (re > 0))
        {
            l = mid;
        }
        else
        {
            r = mid;
        }
    }

    cout << n - r << endl;

    return 0;
}


Measured memory_bytes: 1792
#import sys
#input = sys.stdin.readline
from collections import Counter
from itertools import accumulate
def main():
    s = input()
    t = input()
    S = Counter(s)
    T = Counter(t)
    N = len(t)
    M = len(s)
    d = dict()
    for i in range(26):
        d[ chr( ord("a") + i)] = i
    for key in T:
        if S[key] == 0:
            print(-1)
            return
    Al = [[0]*M for _ in range(26)]
    a = ord("a")
    for i in range(M):
        Al[d[s[i]]][i] = 1
    Ac = [[0]*M for _ in range(26)]
    for i in range(26):
        now = -1
        for j in range(M-1,-1,-1):
            Ac[i][j] = now
            if Al[i][j] == 1:
                now = j
    ans = 1
    for i in range(M):
        if t[0] == s[i]:
            now = i
            break
    first = d[s[0]]
    for cnt in range(1,N):
        g = d[t[cnt]]
        if Ac[g][now] == -1:
            ans += 1
            if g == first:
                now = 0
            else:
                now = Ac[g][0]
        else:
            now = Ac[g][now]
    print(M*(ans-1)+now+1)
    
if __name__ == '__main__':
    main()


Measured memory_bytes: 81648
#include <bits/stdc++.h>
#define ll long long int
const ll mod=1e9+7;
using namespace std;
 
ll power(ll a,ll n)
{
    if(n==0)
        return 1;
    if(n%2!=0)
    {
        return (a*power((a*a)%mod,n/2))%mod;
    }
    return power((a*a)%mod,n/2)%mod;
}
 
int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  ll n,ans;
  cin>>n;
  ans = (power(10,n) - (2*power(9,n))%mod + mod + power(8,n)+mod)%mod;
  cout<<ans<<endl;
}

Measured memory_bytes: 3628
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n = input()
    aa = list(map(int, input().split()))
    ans = 0
    b = 2
    while 1:
        for a in aa:
            if a % b:
                print(ans)
                exit()
        ans += 1
        b *= 2

main()


Measured memory_bytes: 3060
#include <stdio.h>
#include <iostream>
#include <string>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <stdexcept>
#include <vector>
using namespace std;


#define abs(N) ((N>0)?N:-1*N)
#define lt(A,B) ((A>B)?B:A)
#define gt(A,B) ((A<B)?B:A)
#define print(S) (cout << S)
#define println(S) (cout << S << endl)
#define ll long long int

int main(){
	int n,q;
	cin >> n;
	ll S[n];
	for (int i = 0; i < n; ++i) {
		cin >> S[i];
	}
	cin >> q;
	int cnt=0;
	for (int i = 0; i < q; ++i) {
		ll Q;
		cin >> Q;
		for (int j = 0; j < n; ++j) {
			if(Q == S[j]){
				cnt++;
				break;
			}
		}
	}
	println(cnt);

	return 0;
}



Measured memory_bytes: 3180
#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#define priority_queue __gnu_pbds::priority_queue
using namespace std;
#define ri register int
#define fi first
#define se second
#define pb push_back
#define mid ((l + r) >> 1)
#define ls (i << 1)
#define rs (i << 1 | 1)
typedef long long LL;
typedef long double LD;
typedef unsigned int ui;
typedef unsigned long long ul;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef vector<int> vi;
#define ae(x) for(node *p = h[x]; p; p = p->nxt)
#define adde(x, y) { e[++z].v = y; e[z].nxt = h[x]; h[x] = &e[z]; }
#define addrev(x, y) { adde(x, y); adde(y, x); }
#define FO(x) { freopen("#x.in", "r", stdin); freopen("#x.out", "w", stdout); }
inline int read() // ret >= 0
{
	int ret = 0; char ch = getchar();
	while('0' <= ch && ch <= '9')
		ch = getchar();
	do {
		ret = ret * 10 + ch - '0';
		ch = getchar();
	} while('0' <= ch && ch <= '9');
	return ret;
}
inline void write(int x) // x >= 0
{
	if(x < 10)
	{
		putchar(x + '0');
		return ;
	}
	write(x / 10);
	putchar(x % 10 + '0');
}
#define maxn 100100
int n;
int a[maxn], b[maxn];
LL sa, sb;
multiset<int> st;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i ++)
	{
		cin >> a[i] >> b[i];
		sa += a[i];
		sb += b[i];
		if(a[i] < b[i])
			swap(a[i], b[i]);
	}
	for(int i = 1; i <= n; i ++)
	{
		st.insert(a[i]);
		st.insert(b[i]);
	}
	LL sum = 0;
	for(int i = 0; i < n - 2; i ++)
	{
		auto it = st.begin();
		sum += *it;
		st.erase(it);
	}
	LL r = min(sa, sb);
	for(int i = 1; i <= n; i ++)
	{
		LL Ans = sum + a[i] + b[i];
		vi tmp;
//		bool f1 = st.count(a[i]), f2 = st.count(b[i]);
//		if(f1)
//			st.erase(a[i]);
//		if(f2)
//			st.erase(b[i]);
//		cout << Ans << endl;
		if(a[i] <= *st.begin())
		{
			auto it = st.begin();
			tmp.pb(*it);
			Ans += *it - a[i];
			st.erase(it);
		}
		if(b[i] <= *st.begin())
		{
			auto it = st.begin();
			tmp.pb(*it);
			Ans += *it - b[i];
			st.erase(it);
		}
		r = min(r, Ans);
		for(int x : tmp)
			st.insert(x);
//		cout << i << ' ' << Ans << endl;
	}
//	cout << st.size() << ' ' << *st.begin() << endl;
	cout << r << endl;
	return 0;
}

Measured memory_bytes: 10368
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Random;
import java.util.Scanner;
 


public class Main {
	private static Scanner sc = new Scanner(System.in);
	//result = Math.pow(num1, num3)
	//StringBuffer str = new StringBuffer(hoge1);
	//String hoge2 = str.reverse().toString();
	//map.containsKey(A)

	//Map<String, Integer> map = new HashMap<String, Integer>(n);
	/*for ( キーのデータ型 key : マップの名前.keySet() ) {
		データのデータ型 data = マップの名前.get( key );
		
		// keyやdataを使った処理;
	}*/
	//int i = Integer.parseInt(s);
	//Queue<String> qq=new ArrayDeque<>(); //add,poll,peek
	//Deque<String> qq=new ArrayDeque<>();//push,pop,peek
	//ArrayList<String> cc = new ArrayList<>(n);
	//Collections.sort(list);
	//Array.sort(list);   cc.contains(tmp)
	//Arrays.asList(c).contains("a")
	//list.set(1,"walk");//1 1 2 3 5
	//static long mod =1000000007;
	//static 	ArrayList<Integer> cc = new ArrayList<>(100);
	
	
	
	
	public static void main(String[] args) {
		//int N=sc.nextInt();for(int i=0;i<N;i++) {}
		//int a[]=new int[N];
		//Ae2+Be2=Ce2
		int N=sc.nextInt();
		long T[]=new long[N];
		long ll=1;
		for(int i=0;i<N;i++) {
			
			T[i]=sc.nextLong();
			ll=lcm(ll,T[i]);
			
		}
		p(ll);
		}
		
		
	
	
	
	public static long lcm(long a, long b) {
        return a / gcd(a, b) * b;
	}
	
	public static long gcd(long a, long b) {
        return b == 0 ? a: gcd(b, a % b);
	}

	


	
	static void p(String ans) {System.out.println(ans);};
	static void p(int ans) {System.out.println(ans);};
	static void p() {System.out.println();};
	static void p(long ans) {System.out.println(ans);};
	static void p(double ans) {System.out.println(ans);};
	
}
	


Measured memory_bytes: 24020
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
using namespace std;

typedef long long ll;

const int MAX = 1000000;
ll cnt;
int l;
int A[MAX];
int n;
vector<int> G;

void insertionSort(int A[], int n, int g) {
    for (int i = g; i < n; i++) {
        int t = A[i];
        int j = i - g;
        while (j >= 0 && A[j] > t) {
            A[j+g] = A[j];
            cnt++;
            j -= g;
        }
        A[j+g] = t;
    }
}

void shellSort(int A[], int n) {
    int h = 1;
    while (h <= n) {
        G.push_back(h);
        h = 3 * h + 1;
    }
    for (int i = G.size() - 1; i >= 0; i--) {
        insertionSort(A, n, G[i]);
    }
}

int main() {
    //freopen("in.txt", "r", "stdin");
    //freopen("out.txt", "w", "stdout");
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &A[i]);
    }
    shellSort(A, n);
    printf("%lu\n", G.size());
    for (int i = G.size() - 1; i >= 0; i--) {
        if (i < G.size()-1) printf(" ");
        printf("%d", G[i]);
    }
    printf("\n");
    printf("%lld\n", cnt);
    for (int i = 0; i < n; i++) {
        printf("%d\n", A[i]);
    }
    return 0;
}

Measured memory_bytes: 7176
#include <bits/stdc++.h>
#define ll long long
#define INF 999999999
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<n;++i)

using namespace std;

typedef pair<int,int>P;

const int MAX_N = 100005;

vector<int> p[MAX_N];
int pp[MAX_N];
int par[MAX_N];
char c[MAX_N];
int num[MAX_N];
int a[MAX_N];
int first[MAX_N];

void initial(int n){		//?????????
	for(int i=0;i<n;i++){
		par[i] = i;
	}
}

int find(int x){		//??¨??????????±???????
	if(par[x] == x){
		return x;
	}else{
		return par[x] = find(par[x]);
	}
}

void unite(int x,int y){
	x = find(x);
	y = find(y);
	if(x == y) return;
	par[y] = x;
}

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

void dfs(int v,int anc)
{
	if(a[v]==1){
		rep(i,p[v].size()){
			dfs(p[v][i],v);
		}
	}else{
		unite(anc,v);
		rep(i,p[v].size()){
			dfs(p[v][i],anc);
		}
	}
}

int main()
{
	while(1){
		int n,q;
		cin >> n >> q;
		if(n==0&&q==0){
			break;
		}
		rep(i,n){
			p[i].clear();
		}
		rep(i,n-1){
			int x;
			scanf("%d",&x);
			p[x-1].push_back(i+1);
			pp[i+1] = x-1;
		}
		initial(n);
		fill(a,a+n,0);
		a[0] = 1;
		rep(i,q){
			cin >> c[i] >> num[i];
			if(c[i]=='M'){
				if(a[num[i]-1] == 0){
					a[num[i]-1] = 1;
					first[num[i]-1] = i;
				}
			}
		}
		dfs(0,0);
		ll ans = 0;
		for(int i=q-1;i>=0;--i){
			if(c[i] == 'M' && i == first[num[i]-1]){
				unite(pp[num[i]-1],num[i]-1);
			}else if(c[i] == 'Q'){
				ans += find(num[i]-1)+1;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

Measured memory_bytes: 14348
#include <stdio.h>

void dump_arr(int arr[], int n){
    int i;
    for(i = 0; i < n; i++){
        printf("%d%s", arr[i], (i == n - 1) ? "\n" : " ");
    }
}

void insertion_sort(int arr[], int n){
    int i, j;
    for(i = 1; i < n; i++){
        int tmp = arr[i];
        for(j = i - 1; j >= 0 && arr[j] > tmp; j--){
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = tmp;

        dump_arr(arr, n);
    }
}

int main(){
    int i, n, arr[100];
    
    scanf("%d", &n);
    for(i = 0; i < n; i++){
        getchar();
        scanf("%d", &arr[i]);
    }
    
    dump_arr(arr, n);
    insertion_sort(arr, n);
}


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

bool uru(int y){
    return (y%4==0 && (y%100!=0 || y%400==0) )? true : false ;
}

int main(){
	int a,b;
	bool flag, iniFlag=false;
	
	while(1){
		cin >> a >> b;
		if(a==0 && b==0) break;
		if(iniFlag)cout << endl;
		iniFlag = true;
		flag = true;

		for(int i=a ; i<=b ; i++){
			if( uru(i) ){
				flag = false;
				cout << i << endl;
			}
		}
		if( flag ) cout << "NA" << endl;
		
	}
}

Measured memory_bytes: 0
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL;
LL n,cnt,a[20];
int main(){
	scanf("%lld",&n);
	cnt=0;
	while (n)
		a[++cnt]=n%10,n/=10;
	int ans=0;
	for (int i=cnt,tot=0;i>=1;i--){
		if (a[i])
			ans=max(ans,(int)(tot+a[i]-1+9*(i-1)));
		tot+=a[i];
	}
	int sum=0;
	for (int i=1;i<=cnt;i++)
		sum+=a[i];
	printf("%d",max(sum,ans));
	return 0;
}

Measured memory_bytes: 128
N, M, C = map(int,input().split())
B = list(input().split())
A = []
count = 0
for i in range(N) :
    A.append(list(input().split()))

for i in range(N) :
    sum = 0
    for j in range(M) :
        sum += int(A[i][j]) * int(B[j])
        if j == M-1 :
            if sum + C > 0 :
                count += 1

print(count)

Measured memory_bytes: 3064
//#include<bits/stdc++.h> using namespace std;
#include<iostream>
using namespace std;
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<stack>
#include<queue> //priority_queue inside queue
#include<deque>
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define nl '\n'
typedef long long ll;
typedef unsigned long long ull;
#define f(i,start,end) for(i=start;i<=end;i++)
#define min_heap priority_queue<int, vector<int>, greater<int> >
#define max_heap priority_queue<int>

bool isPrime(int n)
{
    for(int i=2; i*i<=n; i++)
    {
        if(n%i==0) return false;
    }
    return true;
} //returns true if prime!


int main()
{
fast;
//int t=0,tc=0; cin >> tc; f(t,1,tc) //testcases
{
   int i=0, j=0, n=0, tmp=0;
   ll a,b,c,k; cin >> a >> b >> c >> k;
   ll ans = 0;
   if(k>=a) ans +=a;
   else ans += k;
   k -= a;
   if(k>0) k-= b;
   if(k>0){
      ans -= k;
   }
   cout << ans << nl;
}
return 0;
}
    

Measured memory_bytes: 3584
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>
#include <bitset>

using namespace std;
#define int long long

#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(), (x).end()

template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; abort();}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
//SOLVE


void solve (void)
{
  int N;cin>>N;
  vector<int> vec (N,0);
  for (int i = 0; i < N; i++)
  {
     cin>>vec[i];
  }
  auto src = vec;
  sort(ALL(vec));
  int mid1 = vec[N/2-1];
  int mid2 = vec[N/2];
  for (int i = 0; i < N; i++)
  {
    int X = src[i];
    if(X <= mid1)
    {
      cout<<mid2<<endl;
    }
    else
    {
      cout<<mid1<<endl;
    }
    
  }
  
  
  return;
}
int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(9);
  solve();

  return 0;
}


Measured memory_bytes: 5376
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define wh while
#define op return
using namespace std;
int a,b,c;
int main(){
	cin>>a>>b>>c;
	bool ok=1;
	if(a==b&&b==c&&c==a){
	}else ok=0;
	if(ok)cout<<"Yes\n";else cout<<"No\n";
	op 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>
#define ll long long

using namespace std;

long long MOD = 1000000007;

void dijkstra(int s, vector<vector<int> > &edge, vector<vector<int> > &dist){

    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > que;
    que.push(make_pair(0,s));
    while((int)que.size()>0){
        int c, x;
        c=que.top().first;
        x=que.top().second;
        que.pop();
        if(dist[s][x]>c){
            dist[s][x]=c;
        }else{
            continue;
        }

        for(auto nx:edge[x]){
            if(dist[s][nx]>c+1){
                que.push(make_pair(c+1,nx));
            }
        }
    }
}

int main(){
    int N, X, Y;
    cin >> N >> X >> Y;
    X--;Y--;

    vector<vector<int> > dist(N,vector<int>(N,MOD));
    vector<vector<int> > edge(N,vector<int>(0));
    for(int i=0; i<N-1; i++){
        edge[i].push_back(i+1);
        edge[i+1].push_back(i);
    }
    edge[X].push_back(Y);
    edge[Y].push_back(X);

    for(int i=0; i<N; i++){
        dijkstra(i, edge, dist);
    }
    vector<int> ans(N-1,0);
    for(int i=0; i<N; i++){
        for(int j=0; j<i; j++){
            int x=dist[i][j];
            ans[x-1]++;
        }
    }

    for(int i=0; i<N-1; i++){
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 18048
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int main(int argc , char **argv)
{
	(void)argc;
	(void)argv;

	char s[101] = {};
	cin >> s;

	size_t lng = strlen(s);
	cout << s[0] << lng -2 << s[lng-1] << endl;

	return 0;
}


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

using namespace std;
typedef long long ll;

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

    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 0; i < n; ++i) cin >> a[i];

    for(int i = 0; i < n; ++i) {
        a.insert(lower_bound(a.begin(), a.begin() + i, a[i]), a[i]);
        a.erase(a.begin() + i + 1);
        for(int j = 0; j < n; ++j) {
            printf("%d", a[j]);
            printf(j == n - 1 ? "\n" : " ");
        }
    }

    return 0;
}


Measured memory_bytes: 3296
#include<iostream>
#include<algorithm>
using namespace std;
int a[40]={0,1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
int main()
{
    int n;
    cin>>n;
    cout<<a[n];
}


Measured memory_bytes: 256
#include <iostream>
    #include <cstring>
    #include <cstdlib>
    #include <cmath>
    #include <algorithm>
    #include <functional>
    #include <vector>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
    #include <bitset>
    #include <cassert>
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    typedef vector<int> vi;
    typedef vector<ll> vll;
    typedef pair<int,int> P;
    #define rep(i,a,n) for(ll i = (a);i < (n);i++)
    #define per(i,a,n) for(ll i = (a);i > (n);i--)
    #define lep(i,a,n) for(ll i = (a);i <= (n);i++)
    #define pel(i,a,n) for(ll i = (a);i >= (n);i--)
    #define clr(a,b) memset((a),(b),sizeof(a))
    #define pb push_back
    #define mp make_pair
    #define all(c) (c).begin(),(c).end()
    #define sz size()
    #define print(X) cout << (X) << endl
    const ll INF = 1e+15+7;
    ll n,m,l;
    string s,t;
    ll d[100000],dp[100][100];
     
    int main(){
      cin >> s;
      s[0] = '2';
      s[1] = '0';
      s[2] = '1';
      s[3] = '8';
      print(s);
      return 0;
    }


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
signed main(){
  int N; cin>>N;
  vi A(N);
  double av=0;
  rep(i,0,N){
    cin>>A[i];
    av+=A[i];
  }
  av=av*1.0/N;
  double memo=MOD;
  int ans;
  rep(i,0,N){
    if(memo>abs(av-(double)A[i])){
      memo=abs(av-(double)A[i]);
      ans=i;
    }
  }
  cout<<ans<<endl;
  }


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;
    if(a<b){
        cout<<"a"<<" "<<"< b"<<endl;
    }
    else if (a>b){
        cout<<"a"<<" "<<"> b"<<endl;
    }
    else{cout<<"a"<<" "<<"== b"<<endl;
        
    }
}


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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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


int f(int n){
    if(n%2){
        return 3*n + 1;
    }else{
        return n/2;
    }
}

void solve() {
    int s; cin >> s;
    unordered_map<int, int> um;
    um[s]=1;
    int tmp = s;
    int res = 1;
    while(1){
        tmp = f(tmp);
        res++;
        if(um[tmp] == 1){
            break;
        }else{
            um[tmp] = 1;
        }
    }

    cout << res << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


Measured memory_bytes: 4352
import java.util.*;

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

		while(true){
			int n = sc.nextInt();
			if(n == 0) break;

			price = new HashMap<String,Integer>();
			while(n-- > 0){
				price.put(sc.next(),sc.nextInt());
			}

			n = sc.nextInt();
			map = new HashMap<String,ArrayList<String>>();
			while(n-- > 0){
				String s = sc.next();
				int m = sc.nextInt();
				map.put(s,new ArrayList<String>());
				while(m-- > 0){
					map.get(s).add(sc.next());
				}
			}

			dp = new HashMap<String,Integer>();
			System.out.println(minCost(sc.next()));
		}
	}

	private static HashMap<String,Integer> price;
	private static HashMap<String,ArrayList<String>> map;
	private static HashMap<String,Integer> dp;

	private static int minCost(String s){
		if(map.get(s) == null) return price.get(s) == null ? -1 : price.get(s);
		if(dp.get(s) != null) return dp.get(s);

		int sum = 0;
		boolean nothingFlg = false;

		for(String tmp : map.get(s)){
			int res = minCost(tmp);
			if(res == -1){
				nothingFlg = true;
				break;
			}
			sum += minCost(tmp);
		}

		dp.put(s, price.get(s) == null ? nothingFlg ? -1 : sum : Math.min(sum,price.get(s)));

		return dp.get(s);
	}
}

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

int ds[51];
int N;

int main() {
  cin >> N;
  rep(i, N) {
    cin >> ds[i];
  }
  int sum = 0;
  int sum2 = 0;
  rep(i, N) {
    sum += ds[i];
    sum2 += ds[i] * ds[i];
  }
  cout << (sum * sum - sum2) / 2 << endl;
  return 0;
}



Measured memory_bytes: 256
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    difA = [0]*N

    for i in range(N):
        difA[i] = A[i]-(i+1)

    difA.sort()
    if N%2 == 0:
        g1 = difA[N//2]
        g2 = difA[N//2-1]
        a1 = 0
        a2 = 0
        for i in range(N):
            a1 += abs(difA[i]-g1)
            a2 += abs(difA[i]-g2)
        print(min(a1,a2))
            
    else:
        g = difA[N//2]
        a = 0
        for i in range(N):
            a += abs(difA[i]-g)
        print(a)
    return


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

if __name__ == '__main__':
    main()


Measured memory_bytes: 36640
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <map>

#define reps(i,s,n) for(int (i) = (s); (i) < (n); (i)++)
#define rep(i,n) reps(i,0,n)
using namespace std;
using ll = long long;

int main(){
    ll n,m;
    cin >> n >> m;
    if(n > m/2){
        cout << m/2 << endl;
        return 0;
    }else{
        ll tmp = n;
        m -= 2*n;
        tmp += m/4;
        cout << tmp << endl;
        return 0;
    }
    return 0;
}

Measured memory_bytes: 3504
#include<bits/stdc++.h>
#define forr(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = 1; i <= (n); i++)
#define ALL(a) (a.begin()),(a.end())
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll, ll> LP;
const ll LINF = 1LL<<60;
const int INF = 1001001001;
const int MOD = 1000000007;

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

int main() {
    int n, q;
    cin >> n;
    vector<int> A(n);
    map<ll, ll> memo;
    rep(i, n) {
        ll a;
        cin >> a;
        memo[a]++;
    }
    cin >> q;
    ll ans = 0;
    for(auto x : memo) ans += x.second * x.first;

    vector<ll> res;
    rep(i, q) {
        ll b, c;
        cin >> b >> c;
        ll v = memo[b];
        memo.erase(b);
        memo[c] += v;
        res.push_back(ans - v * (b - c));
        ans = ans - v * (b - c);
    }
    
    for(auto x : res) cout << x << endl;

    return 0;
}

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

int main(){
  long long n,a,b;
  cin >> n >> a >> b;
  if (a%2 == b%2){
    cout << (b-a)/2 << endl;
  }
  else{
    cout << min(a-1,n-b)+1+(b-a-1)/2 << endl;
  }
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
    static double[] x,y;
    static int n;
    static int max;

    public static void main(String[] args){
	Scanner sc = new Scanner(System.in);

	n = sc.nextInt();

	while(n!=0){
	    max = 1;
	    x = new double[n];
	    y = new double[n];

	    for(int i=0; i<n; i++){
		x[i] = sc.nextDouble();
		y[i] = sc.nextDouble();
	    }

	    solve();
	    System.out.println(max);

	    n = sc.nextInt();
	}
    }

   public static void solve(){
	for(int i=0; i<n; i++){
	    for(int j=i+1; j<n; j++){
		double ab = getDist(x[i],y[i],x[j],y[j]);
		if(ab<=2){
		    double mx = (x[i]+x[j])/2;//点aと点bの中点m
		    double my = (y[i]+y[j])/2;
		    double mc = Math.sqrt(1-(ab*ab)/4);//中点mから中心cまでの距離
		    double[][] nv = getNormalVector(x[i]-x[j],y[i]-y[j]);

		    int count = 0;
		    for(int l=0; l<2; l++){
			double cx = mx + nv[l][0]*mc;//中点cの座標
			double cy = my + nv[l][1]*mc;
			for(int k=0; k<n; k++){
			    if(getDist2(cx,cy,x[k],y[k])<1.0+(1e-6)){count++;}
			}
			if(count>max){max = count;}
			count = 0;
		    }
		}
	    }
	}
    }
    //a-bの絶対値（ab間の距離）
    public static double getDist(double x1,double y1,double x2,double y2){
	return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    }

    //絶対値なしの比較用　絶対値取る処理は重いため
    public static double getDist2(double x1,double y1,double x2,double y2){
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
    }

    //単位法線ベクトルを求める
    public static double[][] getNormalVector(double x, double y){
	
	double d = Math.sqrt(x*x+y*y);//|a|
	
	double[][] nv = new double[2][2];
	
	nv[0][0] = -y/d;
	nv[0][1] = x/d;
	nv[1][0] = y/d;
	nv[1][1] = -x/d;
	
	return nv;
    }
}

Measured memory_bytes: 13000