akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cmath>
#include <cstdint>
#include <cinttypes>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    long total = (t / a) * b;
    cout << total << endl;

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N=100010;

int n,a[N],b[N];
ll tot;

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<=n;i++){
		if(a[i]<b[i]){
			tot+=(b[i]-a[i]+1)/2;
			if(b[i]-a[i]&1) tot--;
		}
		else{
			tot-=a[i]-b[i];
		}
	}
	puts(tot<0?"No":"Yes");
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<vector<int>> A;
  for(int i=0;i<N;i++){
    int a;
    cin >> a;
    A.push_back({a,i+1});
  }
  sort(A.begin(), A.end());
  for(int i=0;i<N;i++){
    cout << A[i][1] << " " << endl;
  }
  return 0;
}
  

Measured memory_bytes: 7088
//* AuThOr GaRyMr *//
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define niv vector<int>
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define KEEP while(1)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define ff fflush(stdout)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
typedef pair<mp,mp> superpair;
LL gcd(LL a,LL b){
//	cout<<a<<" "<<b<<endl;
	if(b==0) return a;
	return gcd(b,a%b);
}
void solve(){
	LL a,b,c,d;
	cin>>a>>b>>c>>d;
	//初始 每天买 小于c时加d
	if(a<b){
		puts("No");
		return;
	}
	if(b>d){
		puts("No");
		return ;
	} 
	 LL g = __gcd(b, d), t = a % g - g;
  	if(t<c-b+1){
  		puts("Yes");
  	}
  	else{
  		puts("No");
  	}
}
int main(){
	int t;
	cin>>t;
	while(t--){solve();	}
	return 0;
}


Measured memory_bytes: 256
N, M = map(int, input().split())

X = list(map(int, input().split()))

X.sort()

buff = []

for i in range(M-1):
    buff.append(abs(X[i+1]-X[i]))


buff.sort()
buff = buff[::-1]

for i in range(min(N-1, len(buff))):
    buff.pop(0)

print(sum(buff))

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

using ll = long long;

// 組合せを素数で割った値を求める
const int MAX = 510000;
const int MOD = 998244353;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++) {
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

// 二項係数計算
long long COM(int n, int k) {
  if (n < k || n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  ll n, a, b, k;
  cin >> n >> a >> b >> k;
  
  COMinit();
  
  ll ans = 0;
  for (ll i = 0; i <= n; i++) {
    ll j = (k - i * a) / b;
    if (i * a + j * b != k) continue;
    ans += (COM(n, i) * COM(n, j)) % MOD;
    ans %= MOD;
  }
  
  cout << ans << '\n';
}

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

typedef long long ll;
typedef long double Double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

// chmax, chmin
template <class T> inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T> inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}

void solve(long long N, long long M, std::vector<long long> A,
           std::vector<long long> B) {
  vector< pair<ll,ll> > C;
  for(int i = 0 ; i < N ; i++){
    C.push_back({A[i], B[i]});
  }
  sort(C.begin(), C.end());
  ll ans = 0;
  for(auto p : C){
    ll a = p.first;
    ll b = p.second;
    ll u = min(b, M);
    M -= u;
    ans += a * u;
  }
  cout << ans << endl;
}

int main() {
  long long N;
  scanf("%lld", &N);
  long long M;
  scanf("%lld", &M);
  std::vector<long long> A(N);
  std::vector<long long> B(N);
  for (int i = 0; i < N; i++) {
    scanf("%lld", &A[i]);
    scanf("%lld", &B[i]);
  }
  solve(N, M, std::move(A), std::move(B));
  return 0;
}


Measured memory_bytes: 3956
/**
*	  Name: Ajay Subhash Jadhav
*	  Institute: International Institute of Technology Hyderabad 
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <string.h>
#define LL long long
#define inf 0x7fffffff
#define mod 1000000007
#define pb push_back
#define ppi pair<int,int>
#define vi vector<int>
#define vii vector<ppi>
#define vll vector<LL>
#define mp make_pair
using namespace std;

void fastio()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}
void inputread()
{
  #ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  #endif
}

int main(){
      
  fastio();
  int n,m,i,j,t;
  cin>>n;
  int a[n];
  for(i=0;i<n;i++)
  	cin>>a[i];

  sort(a,a+n);
  int cost=a[n-1]/2;
  for(i=n-2;i>=0;i--)
  {
  	cost+=a[i];
  }
  cout<<cost;
  return 0;
}

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

#define int long long
#define fast ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
const int M = 1e9+7;
const int SZ = 50;
int c,w,h;

int add(int a, int b)
{
	int res = a + b;
	if(res >= M)
		return res - M;
	return res;
}

int mult(int a, int b)
{
	long long res = a;
	res *= b;
	if(res >= M)
		return res % M;
	return res;
}

struct matrix
{
	int arr[SZ][SZ];

    matrix()
    {
      reset();   
    }
    
	void reset()
	{
        for(int i=0;i<SZ;i++)
            for(int j=0;j<SZ;j++)
                 arr[i][j] = 0;
	}

	void makeiden()
	{
		reset();
		for(int i=0;i<SZ;i++)
		{
			arr[i][i] = 1;
		}
	}

	matrix operator + (const matrix &o) const 
	{
		matrix res;
		for(int i=0;i<SZ;i++)
		{
			for(int j=0;j<SZ;j++)
			{
				res.arr[i][j] = add(arr[i][j], o.arr[i][j]);
			}
		}
		return res;
	}

	matrix operator * (const matrix &o) const 
	{
		matrix res;
		for(int i=0;i<SZ;i++)
		{
			for(int j=0;j<SZ;j++)
			{
				res.arr[i][j] = 0;
				for(int k=0;k<SZ;k++)
				{
					res.arr[i][j] = add(res.arr[i][j] , mult(arr[i][k] , o.arr[k][j]));
				}
			}
		}
		return res;
	}
};

matrix power(matrix a, int b)
{
	matrix res;
	res.makeiden();
	while(b)
	{
		if(b & 1)
		{
			res = res * a;
		}
		a = a * a;
		b >>= 1;
	}
	return res;
}

signed main()
{
    fast;
    int n , k;
    cin >> n >> k;
    matrix jt;
    for(int i=0; i<n ; i++ )
    {
        for(int j=0 ; j<n ; j++ )
            cin >> jt.arr[i][j];
    }
    jt = power( jt,k );
    int ans = 0;
    for(int i=0; i<n ; i++ )
    {
        for(int j=0 ; j<n ; j++ )
            ans = add(ans , jt.arr[i][j]) ;
    }
    cout << ans;
}


Measured memory_bytes: 384
#include <stdio.h>
#include <string.h>

int main()
{
  char x[1001];
  int n;

  do
  {
    scanf("%s", x);

    // calculate n
    n = 0;
    for (int i = 0; i < strlen(x); i++)
    {
      n = n + x[i] - '0';
    }

    if (n != 0)
    {
      printf("%d\n", n);
    }
  } while (n != 0);

  return 0;
}


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

typedef long long ll;
#define rep(i, n) for(int i = 0; i < n; i++)

const int lim = 1000000007;
const int INF = 1000000000;

int main(){
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    rep(i, H) cin >> S[i];

    //移動するときの単位を定義
    //右・下・左・上の順番
    const vector<int> di = {1, 0, -1, 0};
    const vector<int> dj = {0, 1, 0, -1};

    //最長経路の長さを取得
    int mx = 0;
    rep(i, H){
        rep(j, W){
            //開始点が壁の時はやめる
            if(S[i][j] == '#') continue;
            //BFSで用いるqueue
            queue<pair<int, int>> q;
            //始点(i, j)からの経路長を格納する2次元配列
            vector<vector<int>> dist(H, vector<int>(W, INF));
            //情報の更新関数
            auto update = [&](int x, int y, int z){
                if(dist[x][y] != INF) return;
                dist[x][y] = z;
                q.emplace(x, y);
            };
            update(i, j, 0);
            //BFS開始
            while(!q.empty()){
                int vi = q.front().first;
                int vj = q.front().second;
                q.pop();

                //上下左右への移動
                rep(dir, 4){
                    int nvi = vi + di[dir];
                    int nvj = vj + dj[dir];
                    //終了条件
                    if(nvi < 0 || nvj < 0 || nvi >= H || nvj >= W) continue;
                    if(S[nvi][nvj] == '#') continue;
                    //発見した場所のdist更新
                    update(nvi, nvj, dist[vi][vj] + 1);
                }
            }
            rep(vi, H){
                rep(vj, W){
                    if(dist[vi][vj] == INF) continue;
                    mx = max(mx, dist[vi][vj]);
                }
            }
        }
    }
    cout << mx << endl;
    return 0;
}

Measured memory_bytes: 3640
/* In the name of Allah */

#include<bits/stdc++.h>
using namespace std;
int a, b, c, d;

int main(){
	int n;
	cin >> n;
	while(n--){
		string s;
		cin >> s;
		if(s == "AC"){
			a++;
		}else if(s == "WA"){
			b++;
		}else if(s == "TLE"){
			c++;
		}else{
			d++;
		}
	
	}
	cout << "AC x " << a << endl;
	cout << "WA x " << b << endl;
	cout << "TLE x " << c << endl;
	cout << "RE x " << d << endl;	
	
	return 0;
}

Measured memory_bytes: 3636
/*input
10
AC
AC
AC
AC
AC
AC
AC
AC
AC
AC
*/
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>
#include <iomanip>

using namespace std; 

int GCD(int x,int y){return y?GCD(y,x%y):x;}
#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#define rep(i,n) for(int i=0;i<(n);i++)
#define repl(i,a,b) for(int i=(a);i<(b);i++)
#define repm(i,a,b) for(int i=(a);i>(b);i--)
#define rept(v) for(auto it=v.begin();it<v.end();it++)
#define all(v) v.begin(),v.end()
const int INF = 1<<30;
typedef long long ll;
typedef pair<int,int> pii;


  
int main() {
	ll n;
	cin>>n;
	int arr[4];
	rep(i,4){
		arr[i] = 0;
	}
	rep(i,n){
		string a;
		cin>>a;
		if(a=="AC"){
			arr[0]++;
		}
		else if(a == "WA"){
			arr[1]++;
		}
		else if(a == "TLE"){
			arr[2]++;
		}
		else{
			arr[3]++;
		}
	}
	cout<<"AC x "<< arr[0]<<endl;
	cout<<"WA x "<< arr[1]<<endl;
	cout<<"TLE x "<< arr[2]<<endl;
	cout<<"RE x "<< arr[3]<<endl;
}



Measured memory_bytes: 3600
s=list(input())
n=len(s)
ans=[1]*n
x=0
for i in range(n-1):
    if s[i]=="L":
        continue
    if s[i]=="R":
        x+=1
    if s[i]=="R" and s[i+1]=="R":
        ans[i]=0
    else:
        if x%2==1:
            ans[i]+=(x-1)//2
            ans[i+1]+=(x-1)//2
            x=0
        else:
            ans[i]+=(x-1)//2
            ans[i+1]+=((x-1)//2+1)
            x=0
x=0
for i in range(n-1,0,-1):
    if s[i]=="R":
        continue
    if s[i]=="L":
        x+=1
    if s[i]=="L" and s[i-1]=="L":
        ans[i]=0
    else:
        if x%2==1:
            ans[i]+=(x-1)//2
            ans[i-1]+=(x-1)//2
            x=0
        else:
            ans[i]+=(x-1)//2
            ans[i-1]+=((x-1)//2+1)
            x=0



print(" ".join(map(str,ans)))


Measured memory_bytes: 55180
<?php
$s=trim(fgets(STDIN));
$t=trim(fgets(STDIN));
$n=strlen($s);
$i=0;
while($i<$n){
  $ans="Yes";
  $j=0;
  while($j<$n){
    $c=$i+$j;
    if($c>=$n){
      $c-=$n;
    }
	if($s[$j]!=$t[$c]){
      $ans="No";
	    }
    	++$j;
  	}
  	if($ans=="Yes"){
    	echo $ans;
    	exit;
  	}
  	++$i;
}
echo $ans;

Measured memory_bytes: 4856
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int R = sc.nextInt();
		
		if (N >= 10){
			System.out.println(R);
		} else {
			System.out.println(R + 100 * (10 - N));
		}
	}
}

Measured memory_bytes: 22612
#include<bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
typedef long long ll;
using namespace std;
int static fast = [](){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0); return 0;
}();

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> grid(h,"");

    for(int i =0; i < h; i++)
        cin >> grid[i];
    unordered_set<int> skip_row;
    unordered_set<int> skip_col;
    for(int i = 0; i < h; i++) {
        int cnt = 0;
        for(int j = 0; j < w; j++) {
            cnt += (grid[i][j] == '.') ? 1 : 0;
        }
        if (cnt == w)
            skip_row.insert(i);
    }
    for(int j =0; j < w; j++) {
        int cnt = 0;
        for(int i = 0; i < h; i++) {
            cnt += (grid[i][j] == '.') ? 1 : 0;
        }
        if (cnt == h)
            skip_col.insert(j);
    }
    for(int i = 0; i < h; i++) {
        if (skip_row.count(i) == 0) {
            for(int j = 0; j < w; j++) {
                if (skip_col.count(j) == 0)
                    cout << grid[i][j];
            }
            cout << endl;
        }
    }
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
signed main(){
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++) cin>>a[i];
  int ans=1,res=1;
  for(int i=0;i<n;i++) ans*=3;
  for(int i=0;i<n;i++){
    if(a[i]%2==0){
      res*=2;
    }else{
      res*=1;
    }
  }
  cout<<ans-res<<endl;
  return 0;
}


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

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
// pll pp; -> (pp.first,pp.second)
// vector<vl> pp(n,vl(2)); sort(pp.begin(),pp.end(),[](vl a,vl b){return a[0]<b[0];});

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define RREP(i,n) for(ll (i)=(n)-1;(i)>=0;(i)--)
#define FOR(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
#define FORR(i,a,b) for(ll (i)=(b)-1;(i)>=(a);(i)--)
#define DEBUG(x) cout << #x << ": " << x << endl
#define CHMAX(a,b) a=max((a),(b))
#define CHMIN(a,b) a=min((a),(b))
/*}}}*/

vl cnt;
ll V = 1e5+5;
vector<vl> edge(2*V);
vector<bool> visited(2*V,false);
void dfs(ll v){
  if(visited[v]) return;
  visited[v] = true;
  cnt[v/V]++;
  REP(i,edge[v].size()) dfs(edge[v][i]);
}
int main() {
  ll n;
  cin >> n;
  REP(i,n){
    ll x,y;
    cin >> x >> y;
    y += V;
    edge[x].push_back(y);
    edge[y].push_back(x);
  }
  ll ans = -n;
  REP(i,2*V){
    cnt = vl(2,0);
    dfs(i);
    ans += cnt[0]*cnt[1];
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 9984
s = input()

dp1 = {'A': 0, 'AB': 0, 'ABC': 0}
dp2 = {'A': 0, 'AB': 0, 'ABC': 0}

c = 1000000000 + 7
n = len(s)
tmp = [1]*n
for i in range(1, n):
    tmp[i] = (tmp[i-1] * 3)%c

count = 0
for i in range(n):
    if s[i] == '?':
        dp2['A'] = dp1['A']*3 + tmp[count]
        dp2['AB'] = dp1['AB']*3 + dp1['A']
        dp2['ABC'] = dp1['ABC']*3 + dp1['AB']
        count += 1
    elif s[i] == 'A':
        dp2['A'] = dp1['A'] + tmp[count]
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'B':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB'] + dp1['A']
        dp2['ABC'] = dp1['ABC']
    elif s[i] == 'C':
        dp2['A'] = dp1['A']
        dp2['AB'] = dp1['AB']
        dp2['ABC'] = dp1['ABC'] + dp1['AB']

    dp1['ABC'] = dp2['ABC'] % c
    dp1['AB'] = dp2['AB'] % c
    dp1['A'] = dp2['A'] % c

    #print(i, dp1)

print(dp1['ABC'])


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

int main() {
    int n,k;
    cin>>n>>k;
    vector<int> vec(n);
    int ans = 0;
    rep(i,k) {
        int d;cin>>d;
        rep(i,d) {
            int t;
            cin>>t;
            vec[t-1]++;
        }
    }
    rep(i,n) {
        if (vec[i] == 0) {
            ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

int main() {
	int A, B;
	cin >> A >> B;

	for (int i = 1; i <= 1250; i++) {
		int Q = i * 0.08;
		int W = i * 0.1;

		if (Q == A && W == B) {
			cout << i << endl;
			return 0;
		}
	}

	cout << -1 << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

int main() {
  int N;
  int A[200];
  cin >> N;
  for(int i = 0;i<N;i++) cin >> A[i]; 

  int j = 0;
  while(true) {
    for (int i = 0;i<N;i++) {
      if (A[i] % 2 != 0) {
        cout << j << endl;
        return 0;
      }
      A[i] /= 2;
    }
    j++;
  }
  return 0;
}


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

#define ll long long
#define INF 99999999
int main()
{
    int a,b,c;
    cin >> a >> b >> c;
    vector<int> d (b);
    for(int i = 0;i < b;i++) cin >> d[i];
    vector<vector<int> > e (a,vector<int>(b));
    for(int i = 0; i < a;i ++)
    {
        for(int j = 0;j < b;j++)
        {
            cin >> e[i][j];
        }
    }
    int tmp = 0;
    int ans = 0;
    for(int i = 0;i < a;i ++)
    {
        tmp = 0;
        for(int j = 0;j < b;j++)
        {
            tmp += d[j] * e[i][j];
            //cout << tmp << endl;
        }
        tmp += c;
        if(tmp > 0) ans++;
        //cout << "tmp is " << tmp << endl;
    }
    cout <<  ans << endl;
}


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

int main() {
    map<int, int> factors = 
    { {1,1}, {3,1}, {5,1}, {7,1}, {8,1}, {10,1}, {12,1},
      {4,2}, {6,2}, {9,2}, {11,2}, {2,3} };
    int x, y;
    cin >> x >> y;
    if (factors[x] == factors[y]){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
using namespace std;
#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
void solve()
{
int n;
int k;
cin>>n;
int arr[n];
long long sum=0;
for(int i=0;i<n;i++)
{
  cin>>arr[i];
  sum+=arr[i];
}
cin>>k;
int fre[100001]={0};
for(int i=0;i<n;i++)
fre[arr[i]]++;
for(int i=0;i<k;i++)
{
  int a,b;
  cin>>a>>b;
  int oc=fre[a];
  sum=sum+(b-a)*oc;
  fre[b]+=fre[a];
  fre[a]=0;
  cout<<sum<<endl;
}
}
int main()
{
solve();
  return 0;
}


Measured memory_bytes: 4404
#include<bits/stdc++.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 rep2(i,s,n) for (int i = (s); i < (n); ++i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vd vector<double>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<P>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using LP = pair<ll,ll>;
template<class T> istream& operator>>(istream& is,vector<T>& v) { for(T& t:v){is>>t;} return is; }
template<class T> ostream& operator<<(ostream& os,const vector<T>& v) { rep(i,v.size())os<<v[i]<<(i==v.size()-1?"\n":" "); return os; }
void Yes(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YES(bool b) { cout << (b ? "YES" : "NO") << endl; }
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;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

ll a,b,c,d;
map<ll,ll> m;

ll dfs(ll n) {
    if(m.count(n)) return m[n];
    if(n == 0) return 0;
    if(n == 1) return d;
    ll ret = linf;
    if(1e18/d+1 >= n) ret = d*n;
    chmin(ret,dfs(n/2)+a+abs(n-n/2*2)*d);
    chmin(ret,dfs((n+1)/2)+a+abs(n-(n+1)/2*2)*d);
    chmin(ret,dfs(n/3)+b+abs(n-n/3*3)*d);
    chmin(ret,dfs((n+2)/3)+b+abs(n-(n+2)/3*3)*d);
    chmin(ret,dfs(n/5)+c+abs(n-n/5*5)*d);
    chmin(ret,dfs((n+4)/5)+c+abs(n-(n+4)/5*5)*d);
    return m[n] = ret;
}

void solve() {
    ll n;
    cin >> n >> a >> b >> c >> d;
    m.clear();
    cout << dfs(n) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int t;
    cin >> t;
    rep(i,t) solve();
}

Measured memory_bytes: 4460
#include <malloc.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//00c
//00b
//00a
int main(void) {
  int n, k, i, cou=0, tmp, r, d;
  scanf("%d %d %d", &n, &r, &d);
  for(i=n; i<=r; i++){
    if(i%d==0) cou++;
  }
  printf("%d", cou);
}


Measured memory_bytes: 1728
#include <cstdio>
#include <cstdlib>
#include <utility>
#include <typeinfo>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <stack>
#include <string>
#define REP(i,n) for(int i=0;i<n;i++)
typedef long long ll;
using namespace std;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;


int r[16][16][16][257]={};
int ii[257]={};
int xx[16][16][16][257]={};

int main() 
{
	REP(i,16)REP(j,16)REP(k,16)REP(l,257){if(l==0)r[i][j][k][l]=i;else{r[i][j][k][l]=(j*r[i][j][k][l-1]+k)%256;}}

	int n;
	while(cin>>n&&n)
	{

		REP(i,16)REP(j,16)REP(k,16)REP(l,257){xx[i][j][k][l]=0;ii[l]=0;}
		REP(i,n)
		{
			cin>>ii[i+1];
			REP(j,16)REP(k,16)REP(l,16)
			{
						xx[j][k][l][(ii[i+1]+r[j][k][l][i+1])%256]++;
			}
		}
		
		double ans(0);
		int x(0),y(0),z(0);
		
		REP(i,16)REP(j,16)REP(k,16)
		{
			double tmp(0);
			REP(l,256)
			{
				if(xx[i][j][k][l]!=0)
				{
					tmp += xx[i][j][k][l]*log(xx[i][j][k][l]);
				}
			}
			if(tmp>ans)
			{
				ans = tmp;
				x=i;
				y=j;
				z=k;
			}
		}
		
		cout<<x<<" "<<y<<" "<<z<<endl;
	}
	return 0;
}

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

int main() {
  int n; cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];

  deque<int> ans;
  int p = n % 2;

  rep(i,n) {
    if (i%2 != p) ans.push_front(a[i]);
    else ans.push_back(a[i]);
  }

  while(ans.size()!=1) {
    cout << ans.front() << " ";
    ans.pop_front();
  }
  cout << ans.front() << endl;

  return 0;
}

Measured memory_bytes: 4764
/*Function Template*/
#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
#define rep(i, n) for(long long int i = 0; i < (n); i++)


int Len(int n) {
  int s=0;
  while(n!=0) s++, n/=10;
  return s;
}


int Sint(int n) {
  int m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(int i=s-1;i>=0;i--) m+=n/((int)pow(10,i))-(n/((int)pow(10,i+1)))*10;
  return m;
}


long long int Svec(vector<long long int> v){
  long long int n=0;
  for(long long int i=0;i<v.size();i++) n+=v[i];
  return n;
}


int GCD(int a,int b){
  int r,tmp;
/*自然数 a > b を確認・入替*/
  if(a<b){
    tmp=a,a=b,b=tmp;
  }
/*ユークリッドの互除法*/
  r=a%b;
  while(r!=0){
    a=b,b=r,r=a%b;
  }
  return b;
}


int LCM(int a,int b){
  int c=a,d=b,r,tmp;
/*自然数 a > b を確認・入替*/
  if(a<b){
    tmp=a,a=b,b=tmp;
  }
/*ユークリッドの互除法*/
  r=a%b;
  while(r!=0){
    a=b,b=r,r=a%b;
  }
  return c/b*d;
}


int Factorial(int n){
  int m=1;
  while(n>=1) m*=n,n--;
  return m;
}


/*↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓*/
int main() {
  long long int n,k;
  cin>>k>>n;
  if(n==1){
    cout<<0<<endl;
    return 0;
  }
  vector<long long int> v(n),w(n-1);
  rep(i,n) cin>>v[i];
  
  sort(v.begin(),v.end());
  rep(i,n-1){
    w[i]=v[i+1]-v[i];
  }
  sort(w.begin(),w.end(),greater<int>());
  long long int ans=Svec(w);
  if(k==1){
    cout<<ans<<endl;
    return 0;
  }
  if(k-1>=w.size()){
    cout<<0<<endl;
    return 0;
  }
  rep(i,k-1){
    ans-=w[i];
  }
  cout<<ans<<endl;
}



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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
template<typename T> using v = vector<T>;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto& i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
void dump_debug(T list) {
#ifdef MY_DEBUG
    each(e, list) cout << e << " ";
    printf("\n");
#endif
}

inline ll inl() {
    ll x;
    cin >> x;
    return x;
}

inline string ins() {
    string x;
    cin >> x;
    return x;
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */
struct edge {
    ll cost;
    ll to;

    edge(ll to, ll cost) : to(to), cost(cost) {};
};

typedef vector<edge> ve;
typedef vector<ve> vve;

class DAG {
private:
    ll v, e;
    vve table;
    vl pre; // 最短路の直前の頂点
    vl d;
public:
    // v: 頂点数
    // e: 辺の数
    DAG(ll v, ll e) : v(v), e(e) {
        table.resize(v);
        pre.resize(v, -1);
        d.resize(v, inf);
    }

    void add(ll from, ll to, ll cost = 1) {
        table[from].eb(edge(to, cost));
    }

    // O(e * logv)
    vl dijkstra(ll s) {
        // pairを使っているのは、比較関数を利用するため
        priority_queue<P, vector<P>, greater<>> que;
        d[s] = 0;
        que.push(P(0, s));

        while (!que.empty()) {
            P p = que.top();
            que.pop();
            ll min_v = p.S;
            if (d[min_v] < p.F) continue;
            each(ele, table[min_v]) {
                if (d[ele.to] > d[min_v] + ele.cost) {
                    d[ele.to] = d[min_v] + ele.cost;
                    pre[ele.to] = min_v;
                    que.push(P(d[ele.to], ele.to));
                }
            }
        }
        return move(d);
    }

    // 頂点tへの最短路
    vector<int> get_path(int t) {
        vector<int> path;
        for (; t != -1; t = pre[t]) path.emplace_back(t); // tがsになるまでpre[t]をたどっていく
        reverse(path.begin(), path.end());
        return move(path);
    }
};

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        ll n, m;
        cin >> n >> m;
        DAG dag(e5 * 3, m);
        rep(i, m) {
            ll u, v;
            cin >> u >> v;
            u--, v--;
            dag.add(u, v + e5, 1);
            dag.add(u + e5, v + 2 * e5, 1);
            dag.add(u + 2 * e5, v, 1);
        }
        ll s, t;
        cin >> s >> t;
        s--, t--;
        vl ans = dag.dijkstra(s);
        cout << (ans[t] < inf ? ans[t] / 3 : -1) << endl;


#ifdef MY_DEBUG
    }
#endif
    return 0;
}


Measured memory_bytes: 21376
#include<stdio.h>
int main(void)
{
    int H,N;
    int i;
    scanf("%d",&H);
    scanf("%d",&N);
    for(i=0;i<N;i++)
    {
        int A;
        scanf("%d",&A);
        H = H-A;
    }
    if(H<=0){
        puts("Yes");
    }
    else puts("No");
}

Measured memory_bytes: 128
fn main() {
	let mut s = String::new();
	use std::io::Read;
	std::io::stdin().read_to_string(&mut s).unwrap();
	let mut s = s.split_whitespace();
	let n: usize = s.next().unwrap().parse().unwrap();
	let k: usize = s.next().unwrap().parse().unwrap();
	let p: Vec<i32> = s.by_ref().take(3).map(|a| a.parse().unwrap()).collect();
	let t: Vec<_> = s.next().unwrap().chars().collect();
	let mut dp = vec![vec![0; 3]; n];
	for m in 0..k {
		for hand in 0..3 {
			dp[m][hand] = match hand {
				0 if t[m] == 's' => p[0],
				1 if t[m] == 'p' => p[1],
				2 if t[m] == 'r' => p[2],
				_ => 0,
			};
		}
		for i in (1..).map(|i| m + i * k).take_while(|&i| i < n) {
			for last in 0..3 {
				for hand in 0..3 {
					if last == hand {
						continue;
					}
					let t = match hand {
						0 if t[i] == 's' => p[0],
						1 if t[i] == 'p' => p[1],
						2 if t[i] == 'r' => p[2],
						_ => 0,
					};
					if dp[i][hand] < t + dp[i - k][last] {
						dp[i][hand] = t + dp[i - k][last];
					}
				}
			}
		}
	}
	println!("{}", dp.iter().rev().take(k).fold(0, |r, a| { r + std::cmp::max(std::cmp::max(a[0], a[1]), a[2]) }));
}


Measured memory_bytes: 10492
# E - Crested Ibis vs Monster
def main():
    INF = 1 << 30

    H, N, *AB = map(int, open(0).read().split())
    dp = [INF] * (H + 10001)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for a, b in zip(*[iter(AB)] * 2):
        for i in range(H):
            if dp[i] + b < dp[i + a]:
                dp[i + a] = dp[i] + b
    print(min(dp[H:]))


if __name__ == "__main__":
    main()


Measured memory_bytes: 39536
N = int(input())
LN = list(map(int, str(N)))
dig = len(LN)
Ans = 0

if N <= 99:print(0)
else:
    Ans += 0
    if N >= 1000:
        for i in range(3, dig):
            Ans += 3**i - 3 * 2**i + 3
    def base3(i, dig):
        t = i
        lt = []
        while t > 0:
            lt.append(t%3)
            t //= 3
        while len(lt) < dig:
            lt.append(0)
        out = 0
        for i in range(dig):
            out *= 10
            out += (3 if lt[i] == 0 else 5 if lt[i]==1 else 7)
        return out
    for i in range(3**dig + 1):
        num = base3(i, dig)
        if len(set(str(num))) == 3 and num <= N: Ans += 1
    print(Ans)



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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int n;
  cin >> n;
  vector<ll> l(n);
  rep(i,n) cin >> l[i];
  sort(l.begin(), l.end());
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = i+1; j < n; ++j) {
      for (int k = j + 1; k < n; ++k) {
        if (l[i] == l[j] || l[j] == l[k] || l[k] == l[i]) continue;
        if (l[i] + l[j] > l[k]) ++ans;
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3676
/*================================================
# ~  file:D.cpp
# ~~ date:2020-03-14
# ~~~author: SoMnus_L
#        |everybody finds love,in the end|
#   人の運命か,人の希望は悲しみにつづられているね
=================================================*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#define ll long long
const int N=1e6+10;
using namespace std;
typedef pair<int,int>PII;

int n;
int p=0,dif=0;
char s[N];

void dfs(int u){
   if(u==n){
      puts(s);
      return;
   }
  
   for(char i=0;i<=dif;++i){
     s[p++]=i+'a';
     int tmp=dif;
     if(i==dif) dif++;
     dfs(u+1);
     p--;
     dif=tmp;
   }

}

int main(){
 ios::sync_with_stdio(false);
  cin>>n;
  dfs(0);
  return 0;
}


Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
int a[300000];
int main()
{
	int k,n;
	cin>>k>>n;

	for (int i = 0; i < n; ++i)
	{
		cin>>a[i];
	}
	int max = a[0] + (k - a[n-1]);

	for (int i = 1; i < n; ++i)
	{
		if(a[i]-a[i-1] > max)
		{
			max = a[i] - a[i-1];
		}
	}
	cout<<k-max<<endl;

	
	return 0;
}

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

int main() {
  string input;
  cin >> input;
  
  map<char, int> dic;
  for (int i = 0; i < input.size(); i++) {
    char key = input.at(i);
    dic[key]++;
  }
  if (dic.size() != 2) {
    cout << "No" << endl;
    return 0;
  }
  for (auto itr = dic.begin(); itr != dic.end(); itr++) {
    if (itr->second != 2) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <ctime>
////
//#include <random>//
/////////

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;

////定数
const int INF = (int)1e9 + 10;
const LL MOD = (LL)1e9 + 7;
const LL LINF = (LL)4e18 + 20;
const LD PI = acos(-1.0);
const double EPS = 1e-9; 
/////////
using namespace::std;
void chmax(LL& a, LL b) {
	a = max(a, b);
}
void chmin(LL& a, LL b) {
	a = min(a, b);
}
//////////////

void solve() {
	int N,T;
	cin >> N>>T;
	vector<int> c(N), t(N);
	int ans = INF;
	for (int i = 0; i < N; ++i) {
		cin >> c[i] >> t[i];
		if (t[i] <= T) {
			ans = min(ans, c[i]);
		}
	}
	if (ans == INF) {
		cout << "TLE" << endl;
	}
	else {
		cout << ans << endl;
	}
}

signed main(void) {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <numeric>
#include <sstream>
#include <iomanip>
#define ALL(X) X.begin(), X.end()
using lint = long long;
template <typename T>
void print_container(std::vector<T> vec)
{
    for (auto iter = vec.begin(); iter != vec.end(); ++iter)
    {
        std::cout << *iter << " ";
    }
    std::cout << std::endl;
}

int main()
{
    lint n;
    scanf("%lld", &n);

    std::string s1;
    std::cin >> s1;

    std::string s2;
    std::cin >> s2;

    lint idx = 0;

    lint ans = 1;
    lint mod = 1e9 + 7;

    lint pat;

    if (s1[0] != s2[0])
    {
        pat = 2;
        idx += 2;
        ans *= 6;
    }
    else
    {
        pat = 1;
        idx++;
        ans *= 3;
    }

    while (idx < s1.size())
    {
        if (pat == 1 && s1[idx] == s2[idx])
        {
            ans *= 2;
            ans %= mod;
            idx++;
            pat = 1;
        }
        else if (pat == 1 && s1[idx] != s2[idx])
        {
            ans *= 2;
            ans %= mod;
            idx += 2;
            pat = 2;
        }
        else if (pat == 2 && s1[idx] == s2[idx])
        {
            ans *= 1;
            idx++;
            pat = 1;
        }
        else
        {
            ans *= 3;
            ans %= mod;
            idx += 2;
            pat = 2;
        }
    }

    std::cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>

using namespace std;

const int MAXN = (int)1e5 + 5;
int h[MAXN];
int f[MAXN];

void solve(int n) {
  f[1] = 0;
  f[2] = abs(h[2] - h[1]);
  for (int i = 3; i <= n; ++i) {
    f[i] = min(f[i - 1] + abs(h[i - 1] - h[i]), f[i - 2] + abs(h[i - 2] - h[i]));
  }
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", h + i);
  }
  solve(n);
  printf("%d\n", f[n]);
  return 0;
}


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

typedef long long int ll;

int main()
{
    string s;
    cin >> s;
    ll ans = 0;
    
    if(s[0] == 'R' && s[1] == 'R' && s[2] == 'R'){
        ans = 3;
    }
    else if(s[0] == 'R' && s[1] == 'R' || s[1] == 'R' && s[2] == 'R'){
        ans = 2;
    }
    else if(s[0] == 'R' || s[1] == 'R' || s[2] == 'R'){
        ans = 1;
    }
    else{
        ans = 0;
    }

    cout << ans;

    return 0;
    
}


Measured memory_bytes: 3616
import sys
input = sys.stdin.readline

from math import factorial
from itertools import combinations
from collections import Counter
from copy import deepcopy
from operator import mul
from functools import reduce

def main():
    a = int(input())
    b = int(input())
    c = int(input())
    x = int(input())
    r = 0
    for ia in range(a + 1):
        for ib in range(min(b + 1, (x - ia * 500)//100 + 1)):
            for ic in range(min(c + 1, (x - ia * 500 - ib * 100)//50 + 1)):
                r +=  ia * 500 + ib * 100 + ic * 50 == x


    print(r)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3700
N = input()
l = N[len(N)-1]
if l == "2" or l == "4" or l == "5" or l == "7" or l == "9":
    print("hon")
elif l == "0" or l == "1" or l == "6" or l == "8":
    print("pon")
else:
    print("bon")


Measured memory_bytes: 9100
/**
 * @author karayuu
 */

fun main(args: Array<String>) {
    while (true) {
        val n = readLine()!!.toInt()

        if (n == 0) return

        val map = readLine()!!.split(" ").map { it.toInt() }
        println(map.filter { it <= map.average() }.count())
    }
}


Measured memory_bytes: 44572
#include<bits/stdc++.h>
using namespace std;
#define FasterIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

typedef unsigned long long ull;
typedef long long ll;
typedef double db;

#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pi pair<int,int>
#define vi vector<int>
#define pL pair<ll,ll>
#define vL vector<ll>
#define vp vector<pi>
#define vpL vector<pL>

const int MX=1000000;
const ll inf=1e18;
const ll mod=1e9+7;

int main()
{
    FasterIO;
    ll n, m, k;
    string s;
    cin>>s;
    sort(s.begin(), s.end());
    if(s[0]==s[2]) cout<<"No"<<endl;
    else           cout<<"Yes"<<endl;

    return 0;
}



Measured memory_bytes: 256
void main()
{
    int[] tmp = readln.split.to!(int[]);
    int n = tmp[0], a = tmp[1], b = tmp[2];
    string s = readln.chomp;

    int pass, oversea;
    foreach (c; s)
    {
        if (c == 'a' && pass < a + b)
        {
            "Yes".writeln;
            ++pass;
        }
        else if (c == 'b' && pass < a + b && oversea < b)
        {
            "Yes".writeln;
            ++pass;
            ++oversea;
        }
        else
        {
            "No".writeln;
        }
    }
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.container;
import std.typecons;
import std.ascii;
import std.uni;

Measured memory_bytes: 2684
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a*b/gcd(a,b);
}

typedef vector<vi> vvi;

void printMatrix(vvi a){
    rep(i,a.size()){
        rep(j,a[0].size())cout << a[i][j] << " " ;
        cout << endl;
    }
}

vvi product(vvi a, vvi b, int mod){//ret = a * b % mod
    vvi ret(a.size(), vi(b[0].size(),0));
    rep(i,a.size())rep(j,b[0].size()){
        rep(k,a[0].size()) (ret[i][j] += a[i][k]*b[k][j]) %= mod;
    }
    return ret;
}


vvi powMatrix(vvi a, int t, int mod){// A^t % mod
    int n = a.size();

    vvi ret(n, vi(n,0));
    rep(i,n)ret[i][i] = 1; // 単位行列

    while(t > 0){ //繰り返し自乗法
        if(t&1) ret = product(ret, a, mod);
        a = product(a,a, mod);
        t = t >> 1;
    }
    return ret;
}


int main(void) {
    int i,j;
    int n,m,a,b,c,t;

    while(cin >> n >> m >> a >> b >> c >> t, n){
        vvi s(n,vi(1));
        rep(i,n) cin >> s[i][0];

        vvi A(n, vi(n,0));
        rep(i,n)rep(j,n){
            if(i == j+1) A[i][j] = a;
            if(i == j) A[i][j] = b;
            if(i+1 == j) A[i][j] = c;
        }
        //printMatrix(A);
        A = powMatrix(A,t,m);
        vvi ans = product(A, s, m);

        rep(i,n){
            cout << ans[i][0];
            if(i<n-1)cout << " " ;
            else cout << endl;
        }

    }
}



Measured memory_bytes: 3112
#include<iostream>
#include<vector>
#include<string>
#include<iomanip>
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

int main()
{
    int n;
    double ans;
    double sum=0;
    cin>>n;
    rep(i,n)
    {
        double a;
        cin>>a;
        double b=1/a;
        sum+=b;
    }
    ans=1/sum;
    cout<<fixed;
    cout<<setprecision(5)<<ans<<endl;

    return 0;
}


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

int main() {
  int n;
  cin >> n;
  int money, highest;
  highest = 0;
  money = 0;
  for(int i = 0; i < n; i++){
    int p;
    cin >> p;
    money = money + p;
    if (highest < p) highest = p;
  }
  money = money - (highest/2);
  cout << money << endl;
}


Measured memory_bytes: 3624
#import <Foundation/Foundation.h>
#include <stdio.h>

NSString* input(void){
    NSData *stdinData = [[NSFileHandle fileHandleWithStandardInput] availableData];
    return [[NSString alloc] initWithData:stdinData encoding:NSUTF8StringEncoding];
}
void output(NSString *s,NSString *sep){
    NSFileHandle *fileHandle = [NSFileHandle fileHandleWithStandardOutput];
    [fileHandle writeData:[s dataUsingEncoding:NSUTF8StringEncoding]];
    [fileHandle writeData:[sep dataUsingEncoding:NSUTF8StringEncoding]];
    [fileHandle closeFile];
}

NSMutableArray* to_numarray(NSString *s){
    NSMutableArray *l = [NSMutableArray arrayWithArray:[s componentsSeparatedByString:@" "]];
    NSInteger buf = 0;
    for(int i=0;i<[l count];i++){
        buf = [[l objectAtIndex:i] integerValue];
        [l replaceObjectAtIndex:i withObject:[NSNumber numberWithInteger:buf]];
    }
    return l;
}

int main(int argc, const char * argv[]) {
    int n,a;
    scanf("%d %d",&n,&a);
    NSInteger N = n;
    NSInteger A = a;
    NSString *result = @"No";
    N-=500*(N/500);
    if(N<=A){result=@"Yes";}
    output(result,@"\n");
    return 0;
}


Measured memory_bytes: 10468
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define rep(i, N) for(ll i = 0; i < (ll)N; i++)
typedef long long ll;
#define MOD 1000000007
#define min(l,r) ((l)<(r)?l:r)

int main() {
    int n, m, ans = MOD, flag = 0;
    char s[1010],t[1010];
    scanf("%s%s", s,t);
    int r = strlen(s) - (int)strlen(t) +1;
    rep(i,r){
        int tmp = 0;
        rep(j,(int)strlen(t)){
            if(s[i+j] != t[j]) tmp++;
        }
        ans = min(ans, tmp);
    }

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


Measured memory_bytes: 1708
#include <iostream>
#include<string>
#include<math.h>
#include<vector>
#include<algorithm>
#include<array>
#include<functional>
#include<iomanip>
#include<ios>
using namespace std;
#define FOR(i,n) for(int (i)=0;(i)<(n);(i)++)

typedef int value_type; /* ソートするキーの型 */

value_type med3(value_type x, value_type y, value_type z)
/* x, y, z の中間値を返す */
{
    if (x < y)
        if (y < z) return y; else if (z < x) return x; else return z; else
        if (z < y) return y; else if (x < z) return x; else return z;
}

void quicksort(value_type a[], int left, int right,value_type index[])
/* クイックソート
 * a     : ソートする配列 
 * left  : ソートするデータの開始位置
 * right : ソートするデータの終了位置
 * index: index配列
 */
{
    if (left < right) {
        int i = left, j = right;
        value_type tmp, pivot = med3(a[i], a[i + (j - i) / 2], a[j]); /* (i+j)/2ではオーバーフローしてしまう */
        while (1) { /* a[] を pivot 以上と以下の集まりに分割する */
            while (a[i] < pivot) i++; /* a[i] >= pivot となる位置を検索 */
            while (pivot < a[j]) j--; /* a[j] <= pivot となる位置を検索 */
            if (i >= j) break;
            tmp = a[i]; a[i] = a[j]; a[j] = tmp; /* a[i],a[j] を交換 */
            tmp = index[i]; index[i] = index[j]; index[j] = tmp;
            i++; j--;
        }
        quicksort(a, left, i - 1,index);  /* 分割した左を再帰的にソート */
        quicksort(a, j + 1, right,index); /* 分割した右を再帰的にソート */
    }
}


int dfs(int n,int N){
    if (n>N){
        return 0;
    }
    

    int ret;
    
    return ret;
}


int main(){
    string S;
    cin >> S;
    string ans="";
    int maxsize=0;
    string tmp="";
    FOR(i,S.size()){
        if(S[i]=='A' || S[i]=='T'||S[i]=='G'||S[i]=='C'){
            tmp+=S[i];
        }else{
            if(ans.size()<tmp.size()){
                ans=tmp;
                
            }
            tmp="";
        }
    }
    if(ans.size()<tmp.size()){
                ans=tmp;
                
            }

    std::cout << ans.size() << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main {
    public static void main(String args[]) {
        Scanner inp = new Scanner(System.in);
        do_(inp);
        inp.close();
    }
    public static void do_(Scanner inp) {
        int s = inp.nextInt();
        int w = inp.nextInt();
        System.out.println(w >= s ? "unsafe" : "safe");
    }
}


Measured memory_bytes: 35824
#include<bits/stdc++.h>
#define ll long long int

using namespace std;

const ll mod=1000000007;
const ll inf=1e18;

int main(){

  ll n,l;
  cin >> n >> l;

  ll s=0;
  for(int i=1;i<n+1;i++)s+=l+i-1;

  if(l+n-1<0)cout << s-(l+n-1) << endl;
  else if(l>0)cout << s-l << endl;
  else cout << s << endl;

}

Measured memory_bytes: 3612
#include<cstdio>
int n, k, ans = 1;
int main()
{
    scanf("%d%d",&n, &k);
    for(int i = 1;i <= n;i++){
        if(ans > k) ans+=k;
        else ans *= 2;
    }
    printf("%d",ans);
    return 0;
}

Measured memory_bytes: 128
from collections import *
MAX = 3*pow(10,5) + 2
n = int(input())
a = list(map(int,input().split()))
b = [0 for i in range(MAX)]
c = [0 for i in range(MAX)]
for i in a:
    b[i] += 1
for i in b:
    c[i] += 1
s = n
last = n
print(last)
for k in range(2,n+1):
    while(s//k < last):
        best = min(last,s//k)
        for i in range(last,best,-1):
            s -= c[i]
            c[i-1] += c[i]
            c[i] = 0
        last = best
    print(last)

Measured memory_bytes: 120420
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
//cout << setprecision(20) << 

int D = 365;
vector<int> c(27);
vector<vector<int>> s(D + 1);

ll calc_score(vector<int> &t) {
    ll satisfy = 0;
    vector<int> last(27, 0);
    for (int i = 1; i <= D; ++i) {
        int con = t[i];
        // add satisfy
        satisfy += s[i][con];
        // update last
        last[con] = i;
        // sub satisfy
        for (int j = 1; j <= 26; ++j) {
            satisfy -= c[j] * (i - last[j]);
        }
    }
    return satisfy;
}

int main() {
    clock_t start = clock();

    cin >> D;
    for (int i = 1; i <= 26; ++i) cin >> c[i];
    for (int i = 1; i <= D; ++i) {
        vector<int> v(27);
        for (int j = 1; j <= 26; ++j) cin >> v[j];
        s[i] = v;
    }

    // output
    vector<int> ans(D + 1);
    vector<int> last(27, 0);
    ll satisfy = 0;
    for (int i = 1; i <= D; ++i) {
        ll max_pen = 0;
        ll choose_con = 0;
        for (int j = 1; j <= 26; ++j) {
            ll penalty = c[j] * (i - last[j]);
            if (penalty > max_pen) {
                choose_con = j;
                max_pen = penalty;
            }
        }
        // actual update
        int con = choose_con;
        last[con] = i;
        ans[i] = con;
    }

    // random
    // cout << "random" << endl;
    // clock_t end = clock();
    // double time = static_cast<double>(end-start) / CLOCKS_PER_SEC * 1000.0;
    ll best_score = calc_score(ans);
    random_device rd{};
    for (int i = 0; i < 10000; ++i) {
        // random
        ll times = rd() % 100;
        vector<int> c_ans = ans;
        for (int j = 0; j < times; ++j) {
            ll day = rd() % 360 + 1;
            ll con = rd() % 25 + 1;
            c_ans[day] = con;
        }
        ll score = calc_score(c_ans);
        if (score > best_score) ans = c_ans;
        // end = clock();
        // time = static_cast<double>(end-start) / CLOCKS_PER_SEC * 1000.0;
    }

    // output
    for (int i = 1; i <= D; ++i) {
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 3688
#define _GLIBCXX_DEBUG

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>

#include <cmath>

#define int long long

using namespace std;

signed main() {
  int n;
  cin >> n;

  int ans = n * (n - 1) / 2;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256