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

using namespace std;


void solve() {
    int x,y,u,v;
    cin >> x >> y >> u >> v;
    //int res = u+v - x-y;
    //res = res*4 + 8;
    //cout << res;
    x = u-x;
    y = v-y;
    string res;
    for (int _ = 0; _ < x; _++) {
        res.push_back('R');
    }
    for (int _ = 0; _ < y; _++) {
        res.push_back('U');
    }
    for (int _ = 0; _ < x; _++) {
        res.push_back('L');
    }
    for (int _ = 0; _ < y; _++) {
        res.push_back('D');
    }
    res.push_back('L');
    for (int _ = 0; _ <= y; _++) {
        res.push_back('U');
    }
    for (int _ = 0; _ <= x; _++) {
        res.push_back('R');
    }
    res.push_back('D');
    res.push_back('R');
    for (int _ = 0; _ <= y; _++) {
        res.push_back('D');
    }
    for (int _ = 0; _ <= x; _++) {
        res.push_back('L');
    }
    res.push_back('U');
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


Measured memory_bytes: 256
def dijkstra_al(s, n, ALcost, start_index = 0):
    '''
    ダイクストラ法 O(|E|log|V|)
    グラフを隣接リストで表す場合
    始点sから各頂点への最短距離
    n: 頂点の数、s: 始点
    ALcost[head] = [(tail, cost), ..., (tail, cost)]
    cost存在しないときはinf
    start_index: 0のときvertexは0, 1, ..., n-1
                 1のときvertexは1, 2, ..., n
    '''
    import heapq
    INF = float('inf')

    fixed = [False] * (n + 1) # 重み確定したかどうか
    nfixed = 0 # 確定した数
    vertex_cost = [INF] * (n + 1)  # 始点sから各頂点への重み
    prev_vertex = [None] * (n + 1) #  各頂点までの最短経路上での１つ前の頂点

    # 1. 始点に0を書き込む
    vertex_cost[s] = 0
    prev_vertex[s] = None
    H = []  # (cost, vertex)のheap
    heapq.heappush(H, (0, s))

    while(H): # Hが空になるまで
        # 2. 未確定の地点の中からもっとも小さい値を持つ地点を1つ選び、その値を確定させる
        u_cost, u = heapq.heappop(H)
        if fixed[u]: continue  # 取り出した頂点がすでに決まっている（古い情報）
        fixed[u] = True
        nfixed += 1

        # 3. 2で確定した地点から直接繋がっていて、かつ未確定な地点に対し、
        #    重みを計算し、書き込まれている値より小さければ更新する
        for v, edge_cost in ALcost[u]:
            if fixed[v]: continue
            newcost = u_cost + edge_cost
            if newcost < vertex_cost[v]:
                vertex_cost[v] = newcost
                heapq.heappush(H, (newcost, v))
                prev_vertex[v] = u

        # 4. 全ての地点が確定していれば終了。そうでなければ2に戻る
        if nfixed == n: break

    if start_index == 0:
        return vertex_cost[:n], prev_vertex[:n]
    else:
        return vertex_cost, prev_vertex # index 0はダミー

# 入力
N, M = [int(x) for x in input().split()]
ALcost = [[] for _ in range(N + 1)]
for i in range(M):
    u, v = [int(x) for x in input().split()]
    ALcost[u].append((v, 1))
    ALcost[v].append((u, 1))

print("Yes")
vertex_cost, prev_vertex = dijkstra_al(1, N, ALcost, 1)
for i in range(2, N + 1):
    print(prev_vertex[i])

Measured memory_bytes: 64796
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
  cin >> n;
  vector<int64_t> data(n+1);
  data.at(0) = 2;
  data.at(1) = 1;
  for(int i = 0; i < n-1; i++) {
    data.at(i+2) = data.at(i+1) + data.at(i);
}
cout << data.at(n) << endl;
}

Measured memory_bytes: 256
M,K = map(int,input().split())
L = list(map(int,input().split()))
L.sort()
ANS = 0
 
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 
mod = 10**9+7 #出力の制限
N = 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
 
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
 
for j in range(M-K+1):
    ANS += (L[K-1+j] - L[M-K-j])*cmb(K-1+j,K-1,mod)
 
print(ANS % mod)

Measured memory_bytes: 19908
#include<bits/stdc++.h>
//#define Min(a,b,c) min((a),min((b),(c)))
#define mp(a,b) make_pair((a),(b))
#define pii pair<int,int>
#define pdd pair<double,double>
#define pll pair<LL,LL>
#define pb(x) push_back(x)
#define x first
#define y second
#define sqr(x) ((x)*(x))
#define EPS 1e-11
#define MEM(x) memset(x,0,sizeof(x))
#define N 200005
#define pi 3.14159265359
using namespace std;
typedef long long LL;
int main(){
 	int r,C,n;
 	scanf("%d %d %d",&r,&C,&n);
 	vector<pair<pii,int> > v;
 	for(int i=0;i<n;i++){
 		int a,b,c,d;
 		scanf("%d %d %d %d",&a,&b,&c,&d);
 		if((a==0||a==r||b==0||b==C)&&(c==0||c==r||d==0||d==C)){
 			if(a==0){
 				v.pb(mp(mp(0,b),i));
			}	
			else if(a==r){
				v.pb(mp(mp(2,-b),i));
			} 
			else if(b==0){
				v.pb(mp(mp(3,-a),i));
			} 
			else if(b==C){
				v.pb(mp(mp(1,a),i));
			}
			if(c==0){
 				v.pb(mp(mp(0,d),i));
			}	
			else if(c==r){
				v.pb(mp(mp(2,-d),i));
			} 
			else if(d==0){
				v.pb(mp(mp(3,-c),i));
			} 
			else if(d==C){
				v.pb(mp(mp(1,c),i));
			}
		}
	}
	sort(v.begin(),v.end());
	vector<int> vv;
	int instk[100005];
	MEM(instk);
	for(vector<pair<pii,int> > ::iterator it=v.begin();it!=v.end();it++){
		if(instk[it->y]){
			if(vv.back()!=it->y){
				printf("NO");
				return 0;
			}
			vv.pop_back();
		} 
		else{
			vv.push_back(it->y);
			instk[it->y]=1;
		}
	}
	printf("YES\n");
	return 0;
}

Measured memory_bytes: 4596
n = int(input())
s = list(input())

mod = 10**9+7
query = "abcdefghijklmnopqrstuvwxyz"
ans = 1

for i in range(26):
    if s.count(query[i]) >= 1:
        ans *= 1 + s.count(query[i])
        ans %= mod
print((ans-1)%mod)

Measured memory_bytes: 3956
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <limits>
#include <cmath>
#include <iomanip>
#include <functional>
#include <random>
#include <set>
using namespace std;
using ll = long long;

const long long BASE_NUM = 1000000007;

ll bsearch(vector<ll> &A, ll K, ll l, ll r)
{
  if (l + 1 == r)
  {
    return r;
  }
  ll center = (l+r)/2;
  ll cuts = 0;
  for(auto &a:A){
    cuts += (a+center-1)/center - 1;
  }
  if (cuts > K){
    return bsearch(A,K,center,r);
  }else{
    return bsearch(A,K,l,center);
  }
}
int main()
{
  // 整数の入力
  ll N, K;
  cin >> N >> K;
  vector<ll> A(N);
  for (size_t i = 0; i < N; i++)
  {
    cin >> A[i];
  }
  cout << bsearch(A,K,0,BASE_NUM) << endl;
  return 0;
}


Measured memory_bytes: 4780
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef pair<double,int> PDI;
const double eps=1e-12;
const int INF=0x3f3f3f3f;
const LL inf=1e18;
const double pi=acos(-1.0);
const int mod=1e9+7;
//LL powmod(LL a,LL b) {LL res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
vector<PII>g;

const int MAXN=200010;
int a[MAXN],b[MAXN];

int Search(int num,int low,int high)
{
    int mid;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(num>=b[mid])  low=mid+1;
        else   high=mid-1;
    }
    return low;
}
int DP(int n)
{
    if(n==0) return 0;
    int i,len,pos;
    b[1]=a[1];
    len=1;
    for(i=2; i<=n; i++)
    {
        if(a[i]>=b[len])//如果a[i]比b[]数组中最大还大直接插入到后面即可
        {
            len=len+1;
            b[len]=a[i];
        }
        else
        {
            pos=Search(a[i],1,len);
            b[pos]=a[i];
        }
    }
    return len;
}
int main(){
//    freopen("in.txt","r",stdin);
//    freopen("outt.txt","w",stdout);
    int t;
    int sx,sy,ex,ey,n,x,y;
    cin>>sx>>sy>>ex>>ey>>n;
    if(sx>ex){
        swap(sx,ex);
        swap(sy,ey);
    }
    int f=1;
    if(sy>ey) f=-1;
    sy*=f;
    ey*=f;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        y*=f;
        if(x>=sx&&x<=ex&&y>=sy&&y<=ey) g.pb({x,y});
    }
    sort(all(g));
    n=0;
    for(auto i:g) a[++n]=i.se;
    int m=DP(n);
//    cout<<m<<endl;
    double ans=(ex-sx+ey-sy)*100.0;
//    ans-=20.0*m;
//    ans+=pi*5*m;
//    ans+=(min(ex-sx,ey-sy)+1==m?pi*5:0);
    if(ex-sx+1==m||ey-sy+1==m) ans+=pi*5;
    ans-=m*20.0;
    ans+=pi*5*m;
    printf("%.16f\n",ans);
    return 0;
}
/*
6 1 1 5
2
3 3
5 2
*/


Measured memory_bytes: 3440
#!/usr/bin/env python
# -*- coding: utf-8 -*-

H, W = map(int, input().split())
# 2次元配列を作る
grid = []
for _n in range(H):
    grid.append(list(input()))


def is_bomb(h, w):
    """指定されたマスが爆弾か調べる"""
    try:
        # マイナス位置は全部0扱い
        if h < 0 or w < 0:
            return 0
        if grid[h][w] == "#":
            return 1
        else:
            return 0
    except IndexError:
        return 0


def search_bomb(h, w):
    """指定されたマスの周囲8マスが爆弾か調べて爆弾の数を返す"""
    if grid[h][w] == "#":
        return "#"
    bomb_count = sum(
        [
            is_bomb(h - 1, w - 1),
            is_bomb(h - 1, w),
            is_bomb(h - 1, w + 1),
            is_bomb(h, w - 1),
            is_bomb(h, w + 1),
            is_bomb(h + 1, w - 1),
            is_bomb(h + 1, w),
            is_bomb(h + 1, w + 1),
        ]
    )
    return str(bomb_count)


# 置換後の2次元配列作成
for h in range(H):
    for w in range(W):
        print(search_bomb(h, w), end="")
    # 行が終わったら改行
    print()


Measured memory_bytes: 3444
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 3000000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)
#define seg_size 524288
long long go_right[200000][21] = {};
int main(){
	long long n,l;
	cin >> n;
	vector<long long> hotels;
	REP(i,n){
		long long a;
		cin >> a;
		hotels.push_back(a);
	}
	cin >> l;
	for(int i = 0;i < n;++i){
		long long bot = i;
		long long top = n-1;
		while(top - bot > 1){
			long long mid = (top + bot) /2 ;
			if(abs(hotels[mid] - hotels[i]) <= l) bot = mid;
			else top = mid;
		}
		if(abs(hotels[top] - hotels[i])<=l){
			go_right[i][0] = top;
		}else go_right[i][0] = bot;
	}
	for(int i = 1;i <= 20;++i){
		for(int q = 0;q < n;++q){
			go_right[q][i] = go_right[go_right[q][i-1]][i-1];
		}
	}
	int query;
	cin >> query;
	REP(i,query){
		int a,b;
		cin >> a >> b;
		a--;
		b--;
		if(a > b) swap(a,b);
		long long ans = 0;
		while(a < b){
			long long bot = 0;
			long long top = 20;
			while(top - bot > 1){
				long long mid = (top+bot)/2;
				if(go_right[a][mid] < b) bot = mid;
				else top = mid;
			}
			if(go_right[a][top] < b){
				ans += (1 << top);
				a = go_right[a][top];
			}else{
				ans += (1 << bot);
				a = go_right[a][bot];
			}
		}
		cout << ans << endl;
	}
	return 0;
}

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

int main () {
    string s, t; cin >> s >> t;
    sort(s.begin(), s.end());
    sort(t.begin(), t.end(), greater<char>());
    if (s < t) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

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

#define N_MAX 100002
#define ll long long

using namespace std;

int n;

struct Pile
{
    ll cnt;
    int cntBigger;
    ll sumBigger;
    int index;
};

ll sum;

bool cmpCnt (const Pile &a, const Pile &b)
{
    return make_pair(a.cnt, a.index) > make_pair(b.cnt, b.index);
}
bool cmpIndex (const Pile &a, const Pile &b)
{
    return a.index < b.index;
}

Pile a[N_MAX];

set <int> s;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i].cnt;
        a[i].index = i;
        sum += a[i].cnt;
    }
    sort(a + 1, a + n + 1, cmpCnt);
    for(int i = 1; i <= n; i++)
    {
        a[i].cntBigger = i;
        a[i].sumBigger = a[i - 1].sumBigger + a[i].cnt;
    }
    sort(a + 1, a + n + 1, cmpIndex);
    ll sumAns = 0;
    for(int i = 1; i <= n; i++)
    {
        ll ans = max(0LL, sum - (a[i].sumBigger - a[i].cntBigger * a[i].cnt) - sumAns);
        sumAns += ans;
        cout << ans << "\n";
    }
    return 0;
}


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

int main() {
  int H, W, cntH, cntW;
  char tmp;
  cin >> H >> W;

  bool is_black[H][W], is_remain[2][max(H, W)];
  loop(i, H) {
    loop(j, W) {
      cin >> tmp;
      tmp == '#' ? is_black[i][j] = true : is_black[i][j] = false;
    }
  }

  loop(i, 2) {
    loop(j, max(H, W)) {
      is_remain[i][j] = false;
    }
  }

  loop(i, H){
    loop(j, W) {
      is_black[i][j] ? is_remain[0][i] = true : 0;
      is_black[i][j] ? is_remain[1][j] = true : 0;
    }
  }

  loop(i, H) {
    if (is_remain[0][i]) {
      loop(j, W) {
        if (is_remain[1][j]) {
          cout << (is_black[i][j] ? "#" : ".");
        }
      }
      cout << endl;
    }
  }

  return 0;
}


Measured memory_bytes: 256
n = int(input())
a = [int(input()) for _ in range(n)]

a.sort()

suma = sum(a)

if suma % 10 != 0:
  print(suma)
  exit()
else:
  for i in a:
    if i % 10 != 0:
      print(suma - i)
      exit()
print(0)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
  int n, m;
  cin >> n >> m;

  vector<int> target(n, -1);
  for (int i = 0; i < m; i++)
  {
    int s, c;
    cin >> s >> c;
    s--;

    if (target[s] == -1)
    {
      target[s] = c;
    }
    else if (target[s] != c)
    {
      cout << -1 << endl;
      return 0;
    }
  }

  if (target[0] == 0)
  {
    if (n > 1)
    {
      cout << -1 << endl;
      return 0;
    }
    else
    {
      cout << 0 << endl;
      return 0;
    }
  }
  else if (target[0] == -1)
  {
    if (n > 1)
    {
      target[0] = 1;
    }
    else
    {
      target[0] = 0;
    }
  }

  int ans = 0;
  for (int i = 0; i < n; i++)
  {
    if (target[i] != -1)
    {
      ans += target[i] * pow(10, n - i - 1);
    }
  }

  cout << ans << endl;
}

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

int main(){
  int n;
  cin>>n;
  int num[26][16];
  for(int i=0;i<26;i++){
    for(int j=0;j<16;j++){
      num[i][j] = 4*i + 7*j;
    }
  }
  for(int i=0;i<26;i++){
    for(int j=0;j<16;j++){
      if(num[i][j] == n){
        cout<<"Yes"<<endl;
        return 0;
      }
    }
  }
  cout<<"No"<<endl;
}


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

typedef long long ll;


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

    ll cur = 0, pre = 0;
    int px = 0;
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);

        cur = pre + min(1LL * (x - px) * a, ll(b));
        if (i == 0) cur = 0;
        pre = cur;
        px = x;
    }

    cout << cur << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define pi 3.141592653589793238
#define int long long
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

string a[500];
int vis[500][500];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int lol[500][500];
int n,m;
int tot[2];

void dfs(int x,int y,int col)
{
    if(x<1||x>n||y<1||y>m)
        return ;
    if(col!=lol[x][y])
        return ;
    vis[x][y]=1;
    tot[col]++;
    for(int i=0;i<4;i++)
    {
        if(!vis[x+dx[i]][y+dy[i]])
            dfs(x+dx[i],y+dy[i],(col+1)&1);
    }
}

signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);  
cout.tie(0);   

#ifndef ONLINE_JUDGE
    if(fopen("INPUT.txt","r"))
    {
    freopen ("INPUT.txt" , "r" , stdin);
    freopen ("OUTPUT.txt" , "w" , stdout);
    }
#endif  


    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]="@"+a[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]=='#')
                lol[i][j]=1;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(!vis[i][j])
            {
                tot[0]=0;
                tot[1]=0;
                dfs(i,j,lol[i][j]);
                ans+=tot[0]*tot[1];
            }
        }
    }
    cout<<ans;
    

} 
    
 


Measured memory_bytes: 11008
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();

		for (int ans = Math.min(a * 7, b * 9); ans <= Math.max(a * 13, b * 11); ans++) {
			if ((int)(ans * 0.08) == a && (int)(ans * 0.1) == b) {
				System.out.println(ans);
				return;
			}
		}
		System.out.println(-1);

	}

}


Measured memory_bytes: 35680
/*                         _
                        _ooOoo_
                       o8888888o
                       88" . "88
                       (| -_- |)
                       O\  =  /O
                    ____/`---'\____
                  .'  \\|     |//  `.
                 /  \\|||  :  |||//  \
                /  _||||| -:- |||||_  \
                |   | \\\  -  /'| |   |
                | \_|  `\`---'//  |_/ |
                \  .-\__ `-. -'__/-.  /
              ___`. .'  /--.--\  `. .'___
           ."" '<  `.___\_<|>_/___.' _> \"".
          | | :  `- \`. ;`. _/; .'/ /  .' ; |
          \  \ `-.   \_\_`. _.'_/_/  -' _.' /
===========`-.`___`-.__\ \___  /__.-'_.'_.-'================

                  Please give me AC.
*/

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <complex>
#include <bitset>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <chrono>
#include <random>

using namespace std;

using int64 = long long;
using uint64 = unsigned long long;
using vi = vector<int>;
using vl = vector<int64>;
using pii = pair<int, int>;
using pll = pair<int64, int64>;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define print(x) cout << (x) << '\n'
#define print2(x, y) cout << (x) << ' ' << (y) << '\n'
#define print3(x, y, z) cout << (x) << ' ' << (y) << ' ' << (z) << '\n'
#define printn(v) rep(i, (v).size() - 1) cout << (v)[i] << ' '; cout << (v)[n - 1] << '\n';
#define debug(x) cerr << #x << ": " << (x) << '\n'
#define debug2(x, y) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v) for (size_t _ = 0; _ < v.size(); ++_){cerr << #v << "[" << _ << "] : " << v[_] << '\n';}
// constant
const int INF = (1<<30) - 1;
const int64 INF64 = (1LL<<62) - 1;

template<typename T> T gcd(T a, T b) {
    if (a < b) return gcd(b, a);
    T r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

template<typename T> T lcm(const T a, const T b) {
    return a / gcd(a, b) * b;
}

template<typename T> bool chmin(T& a, const T& b) {
    if (a > b) return a = b, true; else return false;
}

template<typename T> bool chmax(T& a, const T& b) {
    if (a < b) return a = b, true; else return false;
}

// End of template.

int main() {
    cout << fixed << setprecision(15);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // cin.read(buf, sizeof buf); // 注意: ./a.out < in か pbp | ./a.out で入力すること

    int k;
    int a[] = {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};
    cin >> k;
    print(a[k - 1]);

    return 0;
}



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

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

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

        String az = "abcdefghijklmnopqrstuvwxyz";
        for (int i = 0; i < az.length(); i++) {
            String f = az.substring(i, i+1);
            if (s.indexOf(f) == -1) {
                System.out.println(f);
                System.exit(0);
            }
        }

        System.out.println("None");
    }

}

Measured memory_bytes: 23508
#include<bits/stdc++.h>
using namespace std;
int main(){
  bool flag = true;
  while(flag){
      int n, x;
      int count = 0;
      cin >> n >> x;
    if(n == 0 && x==0)break;
      for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
           for(int k = 1;k<=n;k++){
              if(i+j+k == x && i<j && j < k)count++;
            }
        }
      }
      cout << count << endl;
  }
}


Measured memory_bytes: 3096
#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;

ll power(ll x, int n){
    ll ret=1;
    while(n>0){
        if(n&1){
            ret*=x;
            ret%=MOD;
        }
        x*=x;
        x%=MOD;
        n>>=1;
    }
    return ret%MOD;
}

template<typename T>
void cout_vec(vector<T> &vec){
    for(int i=0; i<vec.size(); i++){
        if (i!=0){
            cout << ' ';
        }
        cout << vec[i];
    }
    cout << endl;
}

int main(){
    int N, K;
    cin >> N >> K;
    ll ans=0;

    vector<ll> vec(K+1,0);

    for(int i=K; i>0; i--){
        vec[i]=power(K/i,N);

        for(int j=2; j*i<=K; j++){
            vec[i]-=vec[j*i];
            vec[i]+=MOD;
            vec[i]%=MOD;
        }
        ans+=vec[i]*i;
        ans%=MOD;
        
    }
    //cout_vec(vec);
    cout << ans << endl;
}

Measured memory_bytes: 3964
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const long long INF = 1e15;

int main(){
    ll n,d;
    cin >> n >> d;
    ll ans = 0;
    for(ll i = 0; i < n; i++){
        ll x,y;
        cin >> x >> y;
        if(sqrt(x*x+y*y) <= d) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3676
def run(N, lists):
    sorted_items = sorted(
        lists,
        key=lambda x: (x['P']),
        reverse=True
    )
    sorted_items = sorted(
        sorted_items,
        key=lambda x: (x['S']),
    )
    return sorted_items


def main():
    N = int(input())
    lists = []
    for i in range(N):
        S, P = input().split()
        P = int(P)
        lists.append({'id': i+1, 'S': S, 'P': P})
    sorted_lists = run(N, lists)
    for item in sorted_lists:
        print(item['id'])


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using i64 = long long;

template <class T = long long int>
class Bit {
    private:
    int len;
    T *arr;
    T init;

    public:
    Bit(int l, T initialValue = 0) : len(l), init(initialValue) {
        arr = new T[l+1];
        for (int i = 0; i < l + 1; i++) {
            arr[i] = initialValue;
        }
    }
    ~Bit() {
        delete[] arr;
    }
    void update(int a, T newval) {
        for (int x = a; x <= len; x += x & -x) arr[x] += newval;
    }
    T query(int a) const {
        if (!a) return init;
        T ret = 0;
        for (int x = a; x > 0; x -= x & -x) ret += arr[x];
        return ret;
    }
};

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::pair<int, int>> v;
    for (int i = 0; i < n; i++) {
        int l, r;
        std::cin >> l >> r;
        v.emplace_back(l, r + 1);
    }

    std::sort(v.begin(), v.end(), [](auto &lhs, auto &rhs) {
        return lhs.second - lhs.first < rhs.second - rhs.first;
    });

    auto it = v.begin();
    Bit<int> bit(m + 2);
    for (int d = 1; d <= m; d++) {
        while (it != v.end() && it->second - it->first <= d) {
            bit.update(it->first, 1);
            bit.update(it->second, -1);
            it++;
        }
        int ret = 0;
        for (int i = d; i <= m; i += d) {
            ret += bit.query(i);
        }
        std::cout << ret + (v.end() - it) << std::endl;
    }

    return 0;
}


Measured memory_bytes: 6512
/* BISMILLAHIR RAHMANIR RAHIM */
#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
   string s;
    cin>>s;
    if(s[s.size()-1]=='s')
      cout<<s<<"es"<<endl;
     else
          cout<<s<<'s'<<endl;

   

    return 0;
}


Measured memory_bytes: 3648
#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if (y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if (x < y) x = y; }

struct UnionFind {
	vector<int> data;
	void init(int n) { data.assign(n, -1); }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) { return root(x) == root(y); }
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
	int size(int x) { return -data[root(x)]; }
};

int main() {
	int N;
	while (~scanf("%d", &N)) {
		vector<int> p(N);
		for (int i = 0; i < N; ++ i)
			scanf("%d", &p[i]), -- p[i];
		vector<int> deg(N);
		rep(i, N)
			++ deg[p[i]];
		vector<int> que;
		rep(i, N) if(deg[i] == 0)
			que.push_back(i);
		for (int qh = 0; qh != que.size(); ++ qh) {
			int i = que[qh];
			if(-- deg[p[i]] == 0)
				que.push_back(p[i]);
		}
		vector<vi> children(N);
		rep(i, N)
			children[p[i]].push_back(i);
		vector<bool> vis(N);
		vector<int> xs(N, -1);
		for (int i : que) {
			for (int j : children[i])
				vis[xs[j]] = true;
			int x = 0;
			for (; vis[x]; ++ x);
			xs[i] = x;
			for (int j : children[i])
				vis[xs[j]] = false;
		}
		vector<int> cycle;
		rep(i, N) if (xs[i] == -1) {
			int j = i;
			do {
				cycle.push_back(j);
				j = p[j];
			} while (j != i);
			break;
		}
		int K = (int)cycle.size();
		vector<int> A(K), B(K);
		rep(k, K) {
			int i = cycle[k];
			for (int j : children[i]) if(xs[j] != -1)
				vis[xs[j]] = true;
			int x = 0;
			for (; vis[x]; ++ x);
			A[k] = x;
			++ x;
			for (; vis[x]; ++ x);
			B[k] = x;
			for (int j : children[i]) if (xs[j] != -1)
				vis[xs[j]] = false;
		}
		UnionFind uf;
		uf.init(K * 2 + 2);
		rep(k, K) {
			int l = (k + K - 1) % K;
			if (A[k] == A[l]) {
				//(x_l = 0) <-> (x_k = 1)
				uf.unionSet(k * 2 + 0, l * 2 + 1);
				uf.unionSet(k * 2 + 1, l * 2 + 0);
			} else if (A[k] == B[l]) {
				//(x_l = 1) <-> (x_k = 1)
				uf.unionSet(k * 2 + 0, l * 2 + 0);
				uf.unionSet(k * 2 + 1, l * 2 + 1);
			} else {
				//x_k = 0
				uf.unionSet(k * 2 + 0, K * 2 + 0);
				uf.unionSet(k * 2 + 1, K * 2 + 1);
			}
		}
		bool ans = true;
		rep(k, K + 1)
			ans &= !uf.findSet(k * 2 + 0, k * 2 + 1);
		puts(ans ? "POSSIBLE" : "IMPOSSIBLE");
	}
	return 0;
}


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

typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef pair<int,int> pii;
typedef pair<long long, int> pli;

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

ll mod = 998244353;


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

  int a,b,c;
  cin >> a >> b >> c;
  if(a+b+c <= 21)cout << "win" << endl;
  else cout << "bust" << endl;
}


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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using ll = long long;
long long mod = 1000000000+7;

int main(){

	int n;
	cin>>n;
	ll a[n];
	rep(i,n)cin>>a[i];

	ll lim = (mod-7)*(mod-7);
	ll ans=1,pre,flag=0;
	rep(i,n){
		pre=ans;
		ans*=a[i];
		if(ans>lim || ans<0 || ans<pre){
			flag=1;
		}
		if(a[i]==0){
			cout<<0<<endl;
			return 0;
		}
	}

	if(flag==0)cout<<ans<<endl;
	else cout<<-1<<endl;

	return 0;
}



Measured memory_bytes: 4404
# coding: utf-8
# Your code here!
mo = 10**9+7

def C(n,a):
  d = 1
  u = 1
  for i in range(n-a+1,n+1):
    d *= i
    d %= mo
  for j in range(1,a+1):
    u *= j
    u %= mo
  return d*(pow(u,mo-2,mo))

n,a,b = map(int,input().split())
p = pow(2,n,mo) - 1

print((p-C(n,a)-C(n,b))%mo)

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

using namespace std;

const long long mod = 1e9 + 7;
long long a[200020];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> a[i];
    long long ans = 0;
    for (int i = 2; i <= n; i++) {
        ans = ans + (a[i] * a[i - 1] % mod);
        a[i] += a[i - 1];
        a[i] %= mod;
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5192
#include<bits/stdc++.h>
#include <math.h>
#include <cmath>
#include <limits>
#include <iostream>
#include <assert.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

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

int a[301][301]={};
int main(){

	int h,w,k;
	cin>>h>>w>>k;
	char c[301][301];

	int t=1,t2=0,t3=-1;
	rep(i,h){
		rep(j,w){
			cin>>c[j][i];
			if(c[j][i]=='#'){
				a[j][i]=t;
				t++;
			}
		}
	}
	rep(i,h){
		rep(j,w){
			if(a[j][i]==0)continue;
			if(a[j][i]>0){
				for(int k=t2; k<j; k++)a[k][i]=a[j][i];
				for(int k=j+1; k<w; k++){
					if(a[k][i]>0){
						t2=k;
						break;
					}
					a[k][i]=a[j][i];
				}
			}
		}
		t2=0;
		if(a[w-1][i]==0&&t3==-1)t3=i;
		if(t3>-1&&a[w-1][i]>0){
			for(int l=t3; l<i; l++){
				for(int k=0; k<w; k++){
					a[k][l]=a[k][i];
				}
			}
			t3=-1;
		}
	}
	if(t3>-1){
		for(int l=t3-1; l<h; l++){
			for(int k=0; k<w; k++){
				a[k][l]=a[k][t3-1];
			}
		}
	}

	rep(i,h){
		rep(j,w-1){
			cout<<a[j][i]<<" ";
		}
		cout<<a[w-1][i];
		cout<<endl;
	}

	return 0;

}


Measured memory_bytes: 1152
/* Simplicity and Goodness */

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

// using namespace __gnu_pbds;
using namespace std;
// typedef tree<int, null_type, less<int>, rb_tree_tag,
//             tree_order_statistics_node_update> indexed_set;

void my_dbg() { cout << endl; }
template<typename Arg, typename... Args> void my_dbg(Arg A, Args... B)
{ cout << ' ' << A; my_dbg(B...); }
#define dbg(...)  cout << "(" << #__VA_ARGS__ << "):", my_dbg(__VA_ARGS__)

#define scn(n) scanf("%d", &n)
#define lscn(n) scanf("%lld", &n)
#define pri(n) printf("%d ", (int)(n))
#define prin(n) printf("%d\n", (int)(n))
#define lpri(n) printf("%lld ", n)
#define lprin(n) printf("%lld\n", n)
#define rep(i,a,b) for(int i=(int)(a); i<(int)(b); i++)
#define pb push_back
#define mp make_pair
#define F first
#define S second

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;

const int inf = INT_MAX;
const int ninf = INT_MIN;
const int mod = 1e9+7;
const int maxN = 2e5+2;


void solve()
{
    int h, w, a, b;
    scanf("%d%d%d%d", &h, &w, &a, &b);

    char x = '0', y = '1';

    rep(i, 0, h)  {
        if(i == b) swap(x, y);
        cout << string(a, x) << string(w - a, y) << '\n';
    }
}

int main()
{
    int t = 1;
    // scn(t);
    while(t --) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3668
# coding: utf-8


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A = [a-1 for a in A]  # 0-index

    cnt = 0
    i = 0
    # appeared = [0]
    appeared = [False] * N
    appeared[0] = True
    arrive = [None] * (N+1)
    arrive[0] = 0
    roop_s = None
    n_roop = None
    for k in range(N):
        i = A[i]
        cnt += 1

        if cnt == K:
            return i+1

        if appeared[i]:
            for j in range(N+1):
                if arrive[j] == i:
                    roop_s = j
                    n_roop = (k+1) - roop_s
                    break
        # if i in appeared:
            # for j in range(len(appeared)):
            #     if appeared[j] == i:
            #         roop_s = j
            #         n_roop = len(appeared) - roop_s
            #         break

            break

        # appeared.append(i)
        appeared[i] = True
        arrive[k+1] = i

    # K > cnt
    rest = (K-roop_s) % n_roop
    # i = appeared[roop_s]
    i = arrive[roop_s]
    for _ in range(rest):
        i = A[i]

    return i+1


print(main())


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

int main()
{
  int H, W;
  cin >> H >> W;
  vector<string> data(H);

  for (int i = 0; i < H; i++)
  {
    cin >> data.at(i);
  }
  vector<bool> row(H,false);
  vector<bool> col(W,false);

  for(int i = 0 ; i < H ; i++ ){
    for(int j = 0 ; j < W ; j++ ){
      if(data[i][j] == '#'){
        row.at(i) = true;
        col.at(j) = true;
      }
    }
  }
  for(int i = 0 ; i < H ; i++ ){
    if(row.at(i) == true){
      for(int j = 0 ; j < W ; j++ ){
        if(col.at(j) == true){
          cout << data[i][j];
        }
      }
      cout << endl;
    }
  }

  return (0);
}


Measured memory_bytes: 256
//   PIGMEISTER™   //

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

#define ll long long
#define sidha(i,x,n) for(ll i=(ll)(x);i<(ll)(n);++i)
#define ulta(i,x,n) for(ll i=(ll)(x);i>=(ll)(n);--i)
#define sab(a) a.begin(),a.end()
#define bas(a) a.rbegin(),a.rend()
#define test ll _;cin>>_;while(_--)
#define jaldi ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define MOD (ll)1000000007
//#define MOD (ll)998244353
#define MAX 100005

int main()
{
    jaldi;
    
    ll n, k;
    cin >> n >> k;

    ll x, a;
    set<ll> s;
    sidha (i, 0, k) {
        cin >> x;
        while (x--) {
            cin >> a;
            s.insert(a);
        }
    }

    cout << n-s.size();
    
    return 0;
}


Measured memory_bytes: 3640
#include <iostream>
#include <vector>
#include <map>

using std::cout;
using std::endl;
using std::cin;

int main(int argc, char* argv[])
{
  int n,m;
  cin >> n >> m;
  int result = n * (n - 1)/2 + m * (m-1)/2;
  cout << result << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>

using namespace std;
typedef long long LL;
template <typename F, typename S> std::ostream& operator<<(ostream& os, const pair<F,S>& p) {
    os << "(" << p.first << "," << p.second << ")"; return os; }
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "["; for(const T& a: v){ os << a << ", "; } os << "]"; return os; }
template <typename K, typename V> ostream& operator<<(ostream& os, const map<K,V>& m) {
    os << "{"; for(const auto& p: m){ os << p.first <<":"<< p.second << ", "; } os << "}"; return os; }


LL solve(string s, string t){
    vector<set<LL>> index(256);
    for(LL i = 0; i < s.size(); ++i){
        index[s[i]].insert(i);
    }
    LL ans = 0;
    LL cur = 0;
    for(char c: t){
        if(index[c].lower_bound(cur) == index[c].end()){
            if(index[c].empty()) return -1;
            ans += s.size();
            cur = *index[c].begin()+1;
        }else{
            cur = *index[c].lower_bound(cur)+1;
        }
    }
    return ans + cur;
}

int main(){
    string s, t;
    cin >> s >> t;
    cout << solve(s, t) << endl;
    return 0;
}



Measured memory_bytes: 5376
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
 
int main() {
    // string s;
    // cin >> s;
 
    // VI a[4];
    // REP(i,4) a[i] = s[i] - '0';
 
    ll n;
    cin >> n;
    VL a(n+1);
    a[0] = 2;
    a[1] = 1;
    FOR(i,2,n){
        a[i] = a[i-1] + a[i-2];
    }
    cout<< a[n] << endl;
 
    return 0;
}

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

#define int long long
#define fi first
#define se second
#define otp(n) cout << n;
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define ctv(v) rep(i,(v).size()) ct(v[i])
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define repv(i,v) for(int i=0;i<(v).size();i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define pb(n) push_back(n);

int n,a[100000],b[100000],takahashi,aoki;
vector<pair<int,int>> v;

main() {
    cin >> n;
    rep(i,n) cin >> a[i] >> b[i],v.pb(make_pair(a[i]+b[i],i))
    sort(all(v));
    rep(i,n) {
        if (i%2) aoki += b[v.back().se];
        else takahashi += a[v.back().se];
        v.pop_back();
    }
    ct(takahashi-aoki)
}

Measured memory_bytes: 3444
#16D8104007J kanehiro Maho

def LCSSolver():
    X   = raw_input()
    Y   = raw_input()
    XN  = len(X)
    YN  = len(Y)
    LCS1 = [0 for i in range(YN+1)]
 
    for i in range(1, XN + 1):
        LCS2 = LCS1 + []
        for j in range(1, YN + 1):
            if X[i - 1] == Y[j - 1]:
                LCS1[j] =LCS2[j - 1] + 1
            elif LCS2[j] < LCS1[j - 1]:
                LCS1[j] = LCS1[j - 1]
    print LCS1[j]
 
Rep = input()
for c in range(Rep):
    LCSSolver()


Measured memory_bytes: 4712
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF=1e18;

ll N,A,B,C,D;
unordered_map<ll,ll> dp;

ll dfs(ll n){
    if (dp.count(n)) return dp[n];
    if (!n) return 0;
    dp[n]=n>INF/D?INF:D*n;
    dp[n]=min(dp[n],dfs(n/2)+A+n%2*D);
    dp[n]=min(dp[n],dfs((n+1)/2)+A+(2-n%2)%2*D);
    dp[n]=min(dp[n],dfs(n/3)+B+n%3*D);
    dp[n]=min(dp[n],dfs((n+2)/3)+B+(3-n%3)%3*D);
    dp[n]=min(dp[n],dfs(n/5)+C+n%5*D);
    dp[n]=min(dp[n],dfs((n+4)/5)+C+(5-n%5)%5*D);
    return dp[n];
}

void solve(){
    dp.clear();
    cout << dfs(N) << '\n';
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T; cin >> T;
    for (;T--;){
        cin >> N >> A >> B >> C >> D;
        solve();
    }
}

Measured memory_bytes: 4120
#include <iostream>

int main() {
  char S[3];

  for (int i=0; i<3; i++) std::cin >> S[i];

  bool isExist = false;
  if (S[0] != S[1]) isExist = true;
  if (S[0] != S[2]) isExist = true;
  if (S[1] != S[2]) isExist = true;


  if (isExist) std::cout << "Yes" << std::endl;
  else std::cout << "No" << std::endl;
}



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

#define testcases int t; cin>>t; while(t--)
#define int long long
const int MOD =  1e9 + 7;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"

string s;
int d;

int dp[10002][102][2];

int solve(int idx, int cur, int tight)
{
	if (idx == s.length())
	{
		return cur == 0;
	}

	int & ans = dp[idx][cur][tight];
	if (ans != -1) return ans;

	ans = 0;
	int end = tight ? s[idx] - '0' : 9;

	for (int i = 0; i <= end; i++)
	{
		ans += solve(idx + 1, (cur + i % d) % d, tight & (i == end));
		ans %= MOD;
	}

	return ans;
}

int32_t main()
{

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	FASTIO;

	cin >> s;
	cin >> d;

	memset(dp, -1, sizeof dp);
	int ans = solve(0, 0, 1);
	cout << (ans - 1 + MOD) % MOD;

}

Measured memory_bytes: 20372
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <algorithm>
#include <functional>

using namespace std;

#define rep(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(itr,c) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
template<class T> void pp(T a, T b){ for(T i = a; i != b; ++i) cout << *i << ' '; cout << endl; }

int N;
int mp[410][410];
const int xx = 205, yy = 205;

int main(){
  int t,i,j;

  while(1){
    scanf("%d",&N);
    if(N == 0) break;
    rep(i,410) rep(j,410) mp[i][j] = -1;

    mp[xx][yy] = 0;
    rep(t,N-1){
      int n,d;
      scanf("%d %d",&n,&d);
      rep(i,410) rep(j,410) if(mp[i][j] == n){
        if(d == 0) mp[i][j-1] = t+1;
        if(d == 1) mp[i+1][j] = t+1;
        if(d == 2) mp[i][j+1] = t+1;
        if(d == 3) mp[i-1][j] = t+1;
      }
    }

    int imn,imx,jmn,jmx;
    imn = imx = jmn = jmx = xx;
    rep(i,410) rep(j,410){
      if(mp[i][j] != -1){
        imn = min(imn,i);
        imx = max(imx,i);
        jmn = min(jmn,j);
        jmx = max(jmx,j);
      }
    }

    printf("%d %d\n",abs(jmn - jmx) + 1, abs(imn - imx) + 1);
  }

  return 0;
}

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

#define fr(i,b,e) for(int i=(b); i!=(e); ++i)
#define rep(i,e) for(int i=0; i!=(e); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long int li;
typedef long long int ll;
using graph = vector<vector<int>>;
using edgedp = vector<vector<pair<int,ll>>>;
constexpr int INF=1000000;
//constexpr int MOD=998244353;
constexpr int MOD=1e9+7;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll x;
    ll k;
    ll d;
    cin >> x >> k >> d;
    x=abs(x);
    if(x/d<k){
        k-=x/d;
        x=x%d;
        if(x>abs(x-d)){
            x=abs(x-d);
            --k;
        }
        if(k%2==0){
            cout << x << "\n";
        }else{
            cout << min(abs(x+d),abs(x-d)) << "\n";
        }   
    }else{
        cout << abs(x)-k*d << "\n";
    }
} 

Measured memory_bytes: 3564
#include<cstdio>
using namespace std;
typedef long long ll;
ll k,a,b;
int main()
{
	scanf("%lld%lld%lld",&k,&a,&b);
	k++;
	if(b-a>2)
	{
		if(k<a+2)printf("%lld\n",k);
		else printf("%lld\n",a+(k-a)/2*(b-a)+(k-a)%2);
	}
	else printf("%lld\n",k); 
	return 0;
 } 

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define F(i,n) for (int i = 0; i < n; ++i)
#define F1(i,n) for (int i = 1; i <= n; ++i)
#define dbg(x) cerr << #x << " = " << x << endl
#define dbgg(x) cerr << #x << " = " << x << ' '
#define T(x) x[pool]
#define mineq(x,y) { if ((x) > (y)) (x) = (y); }
#define maxeq(x,y) { if ((x) < (y)) (x) = (y); }
#define MEOW cout << "meowwwww" << '\n'; system("pause");
#define int long long
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;

template<typename T>
ostream& operator <<(ostream &s, const vector<T> &c)
{
	s << "[ "; for (auto it : c) s << it << " "; s << "\b]\n";
	return s;
}

template<typename T>
ostream& operator <<(ostream &s, const pair<int, T> &c)
{
	s << "[ "; cout << c.fi << " , " << c.se << " ] ";
	return s;
}

const int maxn = 1234567;
int n;
pii a[maxn];

void input()
{
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	F (i, 1 << n)
	{
		cin >> a[i].fi; 
		a[i].se = 0;
	}
}

pii add(pii x, pii y)
{
	pii ret;
	ret.fi = max(x.fi, y.fi);
	bool hao = false;
	if (x.fi == ret.fi) x.fi = 0, hao = true;
	if (!hao && y.fi == ret.fi) y.fi = 0;
	ret.se = max(max(x.fi, x.se), max(y.fi, y.se)); 
	return ret;
}

void zeta(int l, int r)
{
	if (l == r) return;
	int mid = (l + r) / 2;
	zeta(l, mid);
	zeta(mid + 1, r);
	for (int i = l, m = mid + 1; i <= mid; ++i, ++m)
	{
		a[m] = add(a[m], a[i]);
	}
}

void solve()
{
	zeta(0, (1 << n) - 1);
	int cur = 0;
	F1 (i, (1 << n) - 1) 
	{
		cur = max(cur, a[i].fi + a[i].se);
		cout << cur << '\n';
	}
}

main()
{
	input();
	solve();
}


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

const int MAX = 100000;
pair<int, char> A[MAX];
pair<int, char> B[MAX];
pair<int, char> L[MAX];
pair<int, char> R[MAX];
const int SENTINEL = 2000000000;

void merge(pair<int, char> a[], int left, int mid, int right){
  int n1 = mid - left;
  int n2 = right - mid;

  // create new arrays L, R
  for (int i = 0; i < n1; i++) {
    L[i] = a[left + i];
  }

  for (int i = 0; i < n2; i++) {
    R[i] = a[mid + i];
  }

  // SENTINEL
  L[n1].first = SENTINEL;
  R[n2].first = SENTINEL;

  int i {0}, j {0};
  for (int k = left; k < right; k++) {
    if (L[i].first <= R[j].first) {
      a[k] = L[i];
      i++;
    } else {
      a[k] = R[j];
      j++;
    }
  }
}


void mergeSort(pair<int, char> a[], int left, int right) {
  if ((left + 1) < right) {
    int mid = (right + left) / 2;
    mergeSort(a, left, mid);
    mergeSort(a, mid, right);
    merge(a, left, mid, right);
  }
}

int parition(pair<int, char> a[], int p, int r) {
  int x = a[r].first;
  int i = p - 1;
  pair<int, char> tmp;
  for (int j = p; j < r; j++) {
    if (a[j].first <= x) {
      i++;
      tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
    }
  }
  tmp = a[r];
  a[r] = a[i+1];
  a[i+1] = tmp;
  return i+1;
}

void quickSort(pair<int, char> a[], int p, int r) {
  if (p < r) {
    int q = parition(a, p, r);
    quickSort(a, p, q-1);
    quickSort(a, q+1, r);
  }
}

int main() {
  int n {0};
  cin >> n;
  int num {0};
  char suit;

  for (int i = 0; i < n; i++) {
    cin >> suit >> num;
    A[i] = make_pair(num, suit);
    B[i] = make_pair(num, suit);
  }
  quickSort(A, 0, n-1);
  mergeSort(B, 0, n);
  bool is_stable = true;
  for (int i = 0; i < n; i++) {
    if (A[i] != B[i]) {
      is_stable = false;
      break;
    }
  }
  if (is_stable) {
    cout << "Stable" << endl;
  } else {
    cout << "Not stable" << endl;
  }
  for (int i = 0; i < n; i++) {
    cout << A[i].second << " " << A[i].first << endl;
  }
  return 0;
}



Measured memory_bytes: 6216
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define pb push_back
#define all(v) v.begin(), v.end()
#define bigger (char)toupper
#define smaller (char)tolower
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;

int main() {
    //a.erase(unique(a.begin(), a.end()), a.end());
    int N,D;
    scanf("%d%d",&N,&D);
    vector<vi> X(N,vector<int>(D));
    rep(i,N) {
        rep(j,D) {
            cin>>X.at(i).at(j);
        }
    }
    int counter=0;
    rep(i,N) {
        for(int j=i+1; j<N; j++) {
            int square=0;
            rep(k,D) {
                int distance=abs(X.at(i).at(k)-X.at(j).at(k));
                square+=(distance*distance);
            }
            bool ok=false;
            for(int k=0; k<=square; k++) {
                if(k*k==square) ok=true;
            }
            if(ok) counter++;
        }
    }
    printf("%d\n",counter);
}

Measured memory_bytes: 256