akhauriyash/Code-Regression huggingface dataset:
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define SORTD(a) sort(a.rbegin(), a.rend());
#define UNIQUE(a) unique(a.begin(), a.end())
#define ll long long
#define INF 1000000000000000000
#define INT_MAX 2147483647

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <cctype>
#include <numeric>
#include <algorithm>
#include <queue>
#include <set>
#include <utility>
#include <ios>
#include <iomanip>
#include <sstream>
#include <map>

using namespace std;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;

const ll mod = 1e9+7;

int arr[100001];
const int N = 100001;

void eratosthenes() {
	for (int i = 0; i < N; i++) {
		arr[i] = 1;
	}
	for (int i = 2; i < sqrt(N); i++) {
		if (arr[i]) {
			for (int j = 0; i * (j + 2) < N; j++) {
				arr[i *(j + 2)] = 0;
			}
		}
	}
}

int main() {
	int q;
	cin >> q;

	eratosthenes();
	
	int cum[100001] = { 0 };
	
	for (int i = 3; i < N; i = i + 2) {
		if (arr[i] == 1 && arr[(i + 1) / 2] == 1) {
			cum[i] = 1;
		}
	}

	for (int i = 3; i < N; i++) {
		cum[i] += cum[i - 1];
	}

	int l, r;
	REP(i, q) {
		cin >> l >> r;
		cout << cum[r] - cum[l - 1] << endl;
	}
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0;}

int dp[101][4][4][4];
int mod = 1000000007;
int main() {
    int n;
    cin >> n;
    //T:0A:1G:2C:3
    dp[0][0][0][0] = 1;
    rep(i,n) rep(a,4) rep(b,4) rep(c,4) rep(d,4) {
        //ダメなパターン　AGC,GAC,ACG,AXGC,AGXC
        if(b==1 && c==2 && d==3) continue; // AGC
        if(b==2 && c==1 && d==3) continue; // GAC
        if(b==1 && c==3 && d==2)continue; // ACG
        if(a==1 && c==2 && d==3) continue; // AXGC
        if(a==1 && b==2 && d==3) continue; // AGXC
        dp[i+1][b][c][d] =  (dp[i+1][b][c][d] + dp[i][a][b][c] )%mod;
    }
    int ans = 0;
    rep(a,4)rep(b,4)rep(c,4) {
        ans += dp[n][a][b][c];
        ans %= mod;
    }
    cout << ans << endl;
    
}

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

int main() {
    int n, x = 0;
  	string s;
  	cin >> n >> s;
  	int max_x = x;
  	rep(i, s.length()) {
    	if(s[i] == 'I'){
        	x++;
        }else if(s[i] == 'D'){
        	x--;
        }
      	max_x = max(max_x, x);
    }
  	cout << max_x << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <set>
#define MAX(a,b) ((a>b)?(a):(b))
using namespace std;

int main(void){
	int n,m;
	int a;
	while(cin>>n>>m,n||m){
		std::multiset<int> ms;
		for(int i=0;i<n+m;i++)cin>>a,ms.insert(a);
		int m=*(ms.begin());
		for(__typeof(ms.begin()) it=++ms.begin(),b=ms.begin();it!=ms.end();it++,b++){
			m=MAX(m,*it-*b);
		}
		cout<<m<<endl;
	}
	return 0;
}

Measured memory_bytes: 3928
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main(void){
    int a,b,c;
    cin>>a>>b>>c;
    double PI=acos(-1);
    double rad=c*PI/180;
    cout<<fixed<<setprecision(5);
    cout<<a*b*sin(rad)/2<<endl<<a+b+sqrt(a*a+b*b-2*a*b*cos(rad))<<endl<<b*sin(rad)<<endl;
}


Measured memory_bytes: 3480
#-- 未訪問のxの隣接ノード番号を返す。見つからないとnilを返す。
#--------------------------------------------------------------
def next_neighbor nodes, x
  nodes[x][:neighbors].each do |neighbor|
    if nodes[neighbor][:visit] == nil
        return neighbor
    end
  end
  nil
end

#-- スタックが空になるまで探索
#--------------------------------------------------------------
def dfs stack, nodes, stamp
  if stack == []
    return [stack, nodes, stamp]
  end

  x = stack.last
  y = next_neighbor nodes, x
  stamp += 1

  if y == nil
  #-- y == nil -> 未訪問の隣接ノードがなくなった -> xをスタックから削除 して完了印
    stack.pop
    nodes[x][:fix] = stamp
  else
  #-- y == not nil -> 未訪問の隣接ノードが見つかった -> スタックへpushして訪問印
    stack.push y
    nodes[y][:visit] = stamp
  end

  dfs stack, nodes, stamp
end

#-- メイン処理
#-------------------
nodes = [] #-- 訪問時刻、完了時刻、隣接リストを持ったノードの配列
stack = [] #-- 訪問中のノードを格納するスタック
stamp = 0  #-- 訪問時刻

#-- 入力を受け取って自分の隣接リストを持つnodeのリスト(nodes)を作成
n = gets.to_i
n.times do
 no, na, *ns = gets.split.map(&:to_i)
 nodes[no] = { neighbors: ns }
end

#-- nodesを小さい方から調べて訪問してないならそれを支点としてDFSする
[*1...nodes.length].each do |i|
  if nodes[i][:visit] == nil
    stack.push i; stamp += 1; nodes[i][:visit] = stamp
    stack, nodes, stamp = dfs stack, nodes, stamp
  end
end

#-- 表示
[*1...nodes.length].each_with_index do |i|
  puts "#{i} #{nodes[i][:visit]} #{nodes[i][:fix]}"
end


Measured memory_bytes: 6884
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))


class UnionFind:
  def __init__(self, size):
    self.size = size
    self.parent = [i for i in range(size)]
    self.size = [1 for _ in range(size)]
    self.height = [1 for _ in range(size)]

  def root(self, i):
    if i != self.parent[i]:
      self.parent[i] = self.root(self.parent[i])
    return self.parent[i]

  def union(self, i, j):
    pi, pj = self.root(i), self.root(j)
    if pi == pj:
      return
    if self.height[pi] < self.height[pj]:
      self.parent[pi] = pj
      self.size[pj] += self.size[pi]
    else:
      self.parent[pj] = pi
      self.size[pi] += self.size[pj]
      if self.height[pi] == self.height[pj]:
        self.height[pi] += 1

  def is_same(self, i, j):
    return self.root(i) == self.root(j)


def main():
  n, q = map(int, input().split())
  uf = UnionFind(n)
  for _ in range(q):
    c, x, y = map(int, input().split())
    if c == 1:
      if uf.is_same(x, y):
        print(1)
      else:
        print(0)
    else:
      uf.union(x, y)


if __name__ == '__main__':
  main()



Measured memory_bytes: 6848
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define repLRE(i, l, r) for (ll i = (l); i <= (r); ++i)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

ll dx[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
ll dy[9] = {0, 0, -1, 1, -1, 1, -1, 1, 0};

/* Macros reg. ends here */

const ll INF = 1LL << 50;

static const long long mod = 1000000007;

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);

  string s;
  cin >> s;
  printf("%c%u%c\n", s[0], (int)s.size() - 2, s[s.size() - 1]);

  return 0;
}


Measured memory_bytes: 256
/// Containers Start
#include <algorithm>
#include <bitset>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
/// C Header Files
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <math.h>
#include <stdio.h>
/// Containers End

using namespace std;

/// Math Start
#define PI acos(-1.0)
#define Pi 3.141592653589793
#define EPS (1e-7)
#define INF (0x3f3f3f3f)
/// Math End

/// Extra Start
#define nn '\n'
#define pb push_back
#define ull unsigned long long
#define ll long long
#define MOD 1000000007
#define sz(a) int((a).size())
#define space " "
#define All(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
/// Extra End

#define rep(i, n) for (int i = 0; i < n; i++)
#define Cini(a)                                                                \
    int a;                                                                     \
    cin >> a;
#define Cinii(a, b)                                                            \
    int a, b;                                                                  \
    cin >> a >> b;
#define Ciniii(a, b, c)                                                        \
    int a, b, c;                                                               \
    cin >> a >> b >> c;
#define Cins(s)                                                                \
    string s;                                                                  \
    cin >> s;
#define Cinss(s1, s2)                                                          \
    string s1, s2;                                                             \
    cin >> s1 >> s2;
#define Cinc(c)                                                                \
    char c;                                                                    \
    cin >> c;
/// Functions End

/// Debug Start
#define deb(x) cout << #x << ": " << x << endl
#define deb2(x, y) cout << #x << ": " << x << '\t' << #y << ": " << y << endl;
#define deb3(x, y, z)                                                          \
    cout << #x << ": " << x << '\t' << #y << ": " << y << '\t' << #z << ": "   \
         << z << endl;
/// Debug End

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

/**>>>>>>>>>>>>>>>>>>> END <<<<<<<<<<<<<<<<<<**/

/// template

signed main(void) {
    cin.sync_with_stdio(false);
    cin.tie(0);
    Ciniii(a,b,c);
    cout << max(0,c-a+b) << nn;
    return 0;
}

Measured memory_bytes: 256
import heapq
import sys
input=sys.stdin.readline

def sol():
    n,m=map(int,input().split())
    d=[]
    for i in range(n):
        a,b=map(int,input().split())
        #if a<=m: d.append((a,b))
        if a<=m: heapq.heappush(d,(a,b))
    #d.sort(reverse=True)
    q=[]
    ans=0
    for i in range(1,m+1):
        #while d and d[-1][0]<=i:
        while d and d[0][0]<=i:
            #a,b=d.pop()
            a,b=heapq.heappop(d)
            heapq.heappush(q,-b)
        if q:
            ans += -heapq.heappop(q)
    print(ans)

if __name__=="__main__":
    sol()

Measured memory_bytes: 93020
import java.util.*;
import java.math.*;
import java.io.*;
import java.lang.*;

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

        System.out.println(Math.min(b,n*a));
    }
}

class io{
    public static void YesNo(boolean f) {
        System.out.println(f?"Yes":"No");
    }
    public static void YESNO(boolean f) {
        System.out.println(f?"YES":"NO");
    }
}

class Algo{
    public static boolean isOdd(int n){
        return n % 2 == 1;
    }
    public static boolean isEven(int n){
        return n % 2 == 0;
    }


}



Measured memory_bytes: 22740
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author rahdirigs
 */

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

template <typename T> void s_min(T& a, T b) {
	if (a > b) {
		a = b;
	}
}

class TaskN {
	int N;
	vector<int> a;
	vector<ll> pref;
	vector<vector<ll>> dp;

public:
	void solve(std::istream& in, std::ostream& out) {
		in >> N;
		a.resize(N + 1);
		pref.resize(N + 1, 0);
		for (int i = 1; i <= N; i++) {
			in >> a[i];
			pref[i] = pref[i - 1] + a[i];
		}
		dp.resize(N + 1, vector<ll> (N + 1, -1));
		ll ans = rec(1, N);
		out << ans;
	}

	ll rec(int l, int r) {
		if (l >= r) return 0;
		if (dp[l][r] != -1) return dp[l][r];
		dp[l][r] = 1e18;
		for (int i = l; i < r; i++) {
			s_min(dp[l][r], rec(l, i) + rec(i + 1, r));
		}
		dp[l][r] = dp[l][r] + pref[r] - pref[l - 1];
		return dp[l][r];
	}
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	TaskN solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 4484
#include <iostream>
using namespace std;
struct edge { int src, dst, score; };
int main() {
    int n, m; cin >> n >> m;
    edge es[m];
    for (int i = 0; i < m; i++) {
        cin >> es[i].src >> es[i].dst >> es[i].score;
        es[i].src--; es[i].dst--;
    }
    long long d[n];
    fill(d, d+n, -1LL<<60);
    d[0] = 0;
    long long a1;
    for (int k = 0; k < 2*n; k++) {
        for (int i = 0; i < m; i++) {
            if (d[es[i].src] + es[i].score > d[es[i].dst])
                d[es[i].dst] = d[es[i].src] + es[i].score;
        }
        if (k == n) a1 = d[n-1];
    }
    if (a1 == d[n-1]) cout << a1 << endl;
    else cout << "inf\n";
}


Measured memory_bytes: 256
n = gets.to_i
a = gets.chomp.split.map(&:to_i)
ans_odds = 0
ans_even = 0
sum = 0
for i in 0..n-1
  sum += a[i]
  if i%2 == 0 && sum >= 0
    ans_odds += sum + 1
    sum = -1
  elsif i%2 != 0 && sum <= 0
    ans_odds += 1 - sum
    sum = 1
  end
end
sum = 0
for i in 0..n-1
  sum += a[i]
  if i%2 != 0 && sum >= 0
    ans_even += sum + 1
    sum = -1
  elsif i%2 == 0 && sum <= 0
    ans_even += 1 - sum
    sum = 1
  end
end
puts [ans_odds,ans_even].min 

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

const long N=300000;

int main(){
	long n, q;
	long c[N], lowlim[N+1];
	bool ce[N+1];
	
	for(long i=0; i<=N; ++i) ce[i]=false;
	
	
	scanf(" %ld %ld", &n, &q);
	for(long i=0; i<n; ++i){
		scanf(" %ld", &c[i]);
		ce[c[i]]=true;
	}
	sort(c, c+n);

	long now=0;
	for(long i=0; i<=c[n-1]; ++i){
		lowlim[i]=now;
		
		if(ce[i]) now=i;	
	}
	
	
	for(long t=0; t<q; ++t){		
		long a;
		scanf(" %ld", &a);	
		
		long ans=0, p;
		
		for(long i=c[n-1]; i>0; i=lowlim[i-p]){
			p=i%a;
			ans=max(ans,p);
			
			if(i-p<0) break;
		}
		
		printf("%ld\n", ans);
	}
}

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

int H,W,K,sum = 0;
char c[6][6];
int f[6][6];

int main(){
    cin >> H >> W >> K;
    for(int i = 0;i < H;i++){
        for(int j = 0;j < W;j++){
            cin >> c[i][j];
            if(c[i][j] == '.') f[i][j] = 0;
            else if(c[i][j] == '#'){
                f[i][j] = 1;
                sum++;
            }
        }
    }

    
    int count = 0;

    for (int bit = 0; bit < (1 << H); bit++) {
        vector<int> Sh;
        for (int i = 0; i < H; i++) {
            if (bit & (1 << i)) {
                Sh.push_back(i);
            }
        }

        for (int wbit = 0; wbit < (1 << W); wbit++) {
            vector<int> Sw;
            for (int i = 0; i < W; i++) {
                if (wbit & (1 << i)) {
                    Sw.push_back(i);
                }
            }
            /**/
            int ans = sum;

            for(int i = 0;i < Sh.size();i++){
                for(int j = 0;j < W;j++){
                    if(f[Sh[i]][j] == 1) ans--;
                }
            }

            for(int i = 0;i < H;i++){
                for(int j = 0;j < Sw.size();j++){
                    if(f[i][Sw[j]] == 1) ans--;
                }
            }

            for(int i = 0;i < Sh.size();i++){
                for(int j = 0;j < Sw.size();j++){
                    if(f[Sh[i]][Sw[j]] ==  1) ans++;
                }
            }

            if(ans == K) count++;
        }
        
    }

    cout << count << endl;
    
    

        

    return 0;
}

Measured memory_bytes: 3608
#include <iostream>
using namespace std;
int main() {
	int N, K;
	cin >> N >> K;
	double sum = 0.0;
	for (int i = 1; i <= N; ++i) {
		int cur = i; double prob = 1;
		while (cur < K) {
			cur *= 2;
			prob *= 0.5;
		}
		sum += prob;
	}
	cout.precision(15);
	cout << fixed << sum / N << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*

fun main(args: Array<String>) {
    val (n, m) = readLine()!!.split(' ').map { it.toInt() }

    val graph = Graph2(n)
    repeat(m) {
        val (x, y) = readLine()!!.split(' ').map { it.toInt() }
        graph.add(x - 1, y - 1)
    }

    println(graph.solve())
}

class Graph1 constructor(private val n: Int) {
    private val graph = Array(n) { mutableListOf<Int>() }
    private val dp = IntArray(100000) { -1 }

    fun add(x: Int, y: Int) {
        graph[x].add(y)
    }

    private fun rec(v: Int): Int {
        if (dp[v] != -1) return dp[v]

        var res = 0
        graph[v].forEach {
            res = Math.max(res, rec(it) + 1)
        }
        dp[v] = res
        return res
    }

    fun solve(): Int {
        var res = 0
        (0 until n).forEach {
            res = Math.max(res, rec(it))
        }
        return res
    }

}

class Graph2 constructor(private val n: Int) {
    private val graph = Array(n) { mutableListOf<Int>() }
    private val deg = IntArray(n) { 0 }
    private val dp = IntArray(100000) { 0 }

    fun add(x: Int, y: Int) {
        graph[x].add(y)
        deg[y]++
    }

    fun solve(): Int {

        val queue: Queue<Int> = ArrayDeque<Int>()
        deg.forEachIndexed { index, i ->
            if (i == 0) {
                queue.add(index)
            }
        }

        while (queue.isNotEmpty()) {
            val v = queue.remove()
            graph[v].forEach {
                deg[it]--
                if (deg[it] == 0) {
                    queue.add(it)
                    dp[it] = Math.max(dp[it], dp[v] + 1)
                }
            }
        }

        var res = 0
        (0 until n).forEach {
            res = Math.max(res, dp[it])
        }
        return res
    }

}

Measured memory_bytes: 70208
from operator import itemgetter

N = int(input())

T, A = [int(num) for num in input().split()]

high_list = [int(num) for num in input().split()]

TEMP = 0.006

d = {}
for h in high_list:
    average = T - (h * TEMP)
    absolute = abs(A - average)
    d[h] = absolute

sorted_dict = sorted(d.items(), key=itemgetter(1))
ans = sorted_dict[0][0]

print(high_list.index(ans) + 1)


Measured memory_bytes: 3188
s=input()

s1=s[0]+s[1]
s2=s[2]+s[3]

if (s1[0]=='0' and s1!='00') or s1=='11' or s1=='12':
  ans1='MM'
else:
  ans1='YY'

if (s2[0]=='0' and s2!='00') or s2=='11' or s2=='12':
  ans2='MM'
else:
  ans2='YY'

if ans1==ans2=='MM':
  print('AMBIGUOUS')
elif ans1==ans2=='YY':
  print('NA')
else:
  print(ans1+ans2)

Measured memory_bytes: 3064
S = gets.chomp

stack = []
ans = 0
S.chars.each do |s|
  if s == '0'
    if stack.last == '1'
      stack.pop
      ans += 2
    else
      stack << s
    end
  else
    if stack.last == '0'
      stack.pop
      ans += 2
    else
      stack << s
    end
  end
end

p ans


Measured memory_bytes: 10364
# import sys
# def input(): return sys.stdin.readline().rstrip()


from collections import deque
h, w = map(int, input().split())
a, b = map(int, input().split())
c, d = map(int, input().split())
a -= 1
b -= 1
c -= 1
d -= 1
s = [list(input()) for i in range(h)]
now = 0
dd = [(-1, 0), (1, 0), (0, 1), (0, -1)]

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            de = deque([(i, j)])
            s[i][j] = now
            while de:
                x, y = de.popleft()
                for p, q in dd:
                    if 0 <= x + p < h and 0 <= y + q < w and s[x + p][y + q] == ".":
                        s[x + p][y + q] = now
                        de.append((x + p, y + q))
            now += 1
st = s[a][b]
en = s[c][d]
es = [set() for i in range(now)]
for i in range(h):
    for j in range(w):
        if s[i][j] != "#":
            for p in range(-2, 3):
                for q in range(-2, 3):
                    if 0 <= i + p < h and 0 <= j + q < w and s[i + p][j + q] != "#":
                        es[s[i][j]].add(s[i + p][j + q])
                        es[s[i + p][j + q]].add(s[i][j])
from heapq import heappush, heapify, heappop


def dijkstra(s):
    INF = 1 << 32
    d = [INF] * now  # 頂点sからの最短距離
    v = -1
    que = [(0, s)]
    heapify(que)
    d[s] = 0
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for e in es[v]:
            if d[e] > d[v] + 1:
                d[e] = d[v] + 1
                heappush(que, (d[e], e))
    return d[en] if d[en] < INF else -1


print(dijkstra(st))


Measured memory_bytes: 187820
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;

int main(){
    string S;
    cin >> S;
    int N = S.size();

    int ans = 0;
    stack<char> st;
    for(int i=0; i<N; i++){
        if(st.empty() || st.top() == S[i])
            st.push(S[i]);
        else{
            ans+=2;
            st.pop();
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 512
package main

import (
	"fmt"
	"strconv"
	"strings"
)

var n int = 0
var chars = []string{"3", "5", "7"}

func main() {
	fmt.Scan(&n)
	ans := dfs("")
	fmt.Println(ans)
}

func dfs(s string) int {
	i, _ := strconv.Atoi(s)
	if len(s) > 0 && i > n {
		return 0
	}

	res := 0
	if strings.Contains(s, "3") &&
		strings.Contains(s, "5") &&
		strings.Contains(s, "7") {
		res = 1
	}

	for _, c := range chars {
		res += dfs(s + c)
	}

	return res
}


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

int main() {
  int N;
  cin >> N;
  
  vector<int> H(N);
  for (int i=0; i<N; i++) {
    cin >> H.at(i);
  }
  
  for (int i=0; i<N; i++) {
    if (i==0) continue;
    if (H.at(i-1) > H.at(i)) {
      cout << "No";
      return 0;
    }
    if (H.at(i-1) < H.at(i)) {
      H.at(i)--;
    }
  }
  
  cout << "Yes";
  return 0;
}

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


int main(int argc, const char * argv[]) {
    
    double a[1001];
    double ave=0, sum=0, x=0;
    int n,i;
    
    while(1){
        scanf("%d",&n);
        if(n==0)break;
        
        for(i=0; i<n; i++){
            scanf("%lf",&a[i]);
            sum += a[i];
        }
        ave = sum / n;
        
        for(i=0; i<n; i++){
            x += pow(ave - a[i], 2);
        }
        printf("%f\n",sqrt(x/n));
        sum=0;
        x=0;
    }
    return 0;
}



Measured memory_bytes: 2104
#include"bits/stdc++.h"
#define int long long
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define itr(i,x) for(auto i=(x).begin();i!=(x).end();++i)
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()
using namespace std;
using Graph=vector<vector<int>>;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
const int mod=1000000007;
int gcd(int x,int y){return y?gcd(y,x%y):x;}
int lcm(int x,int y){return x*y/gcd(x,y);}
int roundup(int a,int b){return	(a-1)/b+1;}
void YN(bool flg){cout<<(flg?"YES":"NO")<<endl;}
void Yn(bool flg){cout<<(flg?"Yes":"No")<<endl;}
void yn(bool flg){cout<<(flg?"yes":"no")<<endl;}


signed main(){
	int a,b;cin>>a>>b;
	if(a+b==15) cout<<'+'<<endl;
	else if(a*b==15) cout<<'*'<<endl;
	else cout<<'x'<<endl;
}


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

const long long Inf = 1LL << 60;

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

template <class T> bool chmin(T&a,T b);

int main()
{
    int N;cin >> N;
    long long dp[100000],list[100000];
    rep(i,N)
    {
        cin >> list[i];
        dp[i] = Inf;
    }
    dp[0] = 0;
    rep(i,N)
    {
        chmin(dp[i],dp[i - 1] + abs(list[i] - list[i - 1]));
        if(i > 1)
        {
            chmin(dp[i],dp[i - 2] + abs(list[i] - list[i - 2]));
        }
    }
    cout << dp[N - 1] << endl;
}

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

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
#define print(A,n) for(ll i=0;i<n;++i)cout<<A[i]<<' ';cout<<endl;
#define take(A,n) for(ll i=0;i<n;++i)cin>>A[i];
//    for(auto& it : m)
void fastio(){ios_base::sync_with_stdio(false);cin.tie(NULL);}
//  priority_queue<ll int> pq;
//  priority_queue <ll int, vector<ll int>, greater<ll int> > pq;
//  vector<ll int> v;
//  vector< pair<ll int,ll int> > v;
//  set<ll int>::iterator it=s.begin();
//  unordered_map<  pair<ll int,ll int>, ll int> mp;
 
 
 int lis( int arr[], int n )  
{  
    int lis[n]; 
   
    lis[0] = 1;    
  
    /* Compute optimized LIS values in bottom up manner */
    for (int i = 1; i < n; i++ )  
    { 
        lis[i] = 1; 
        for (int j = 0; j < i; j++ )   
            if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)  
                lis[i] = lis[j] + 1;  
    } 
  
    // Return maximum value in lis[] 
    return *max_element(lis, lis+n); 
}  
void computeLPSArray(char* pat, int M, int* lps) 
{ 
    // length of the previous longest prefix suffix 
    int len = 0; 
  
    lps[0] = 0; // lps[0] is always 0 
  
    // the loop calculates lps[i] for i = 1 to M-1 
    int i = 1; 
    while (i < M) { 
        if (pat[i] == pat[len]) { 
            len++; 
            lps[i] = len; 
            i++; 
        } 
        else // (pat[i] != pat[len]) 
        { 
            // This is tricky. Consider the example. 
            // AAACAAAA and i = 7. The idea is similar 
            // to search step. 
            if (len != 0) { 
                len = lps[len - 1]; 
  
                // Also, note that we do not increment 
                // i here 
            } 
            else // if (len == 0) 
            { 
                lps[i] = 0; 
                i++; 
            } 
        } 
    } 
} 
    
int main()
{
  fastio();
 
ll int T;
T=1;
ll int anscount=1;
while(T--)
{
   ll int n,i;
   cin>>n;ll int count[n+1]={0},a[n],ans=0;
   
   for(i=0;i<n;i++){cin>>a[i];count[a[i]]++;}
   for(i=0;i<=n;i++)
   {
       ans+=count[i]*(count[i]-1)/2;
   }
   for(i=0;i<n;i++)
   {
       ll int tans=ans;
       tans-=count[a[i]]*(count[a[i]]-1)/2;
       tans+=(count[a[i]]-1)*(count[a[i]]-2)/2;
       cout<<tans<<endl;
   }
   
   
}
    return 0;
}

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

int main() {
  int N,A;
  cin >> N;
  
  A = N % 10;
  
  if(N >= 90){
    cout << "Yes" << endl;
  }
  else if(A == 9){
    cout << "Yes" << endl;
  }
  else
    cout << "No" << endl;
}

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

int main() {
  int n;
  cin >> n;
  int cnt = 0;
  vector<vector<int>> data(n, vector<int>(2));
  for(int i = 0; i < n; i++) {
    cin >> data[i][1] >> data[i][2];
    if(data[i][1] == data[i][2]) cnt++;
    else cnt=0;
    
    if(cnt == 3) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3628
#[allow(unused_imports)]
use std::{cmp::Reverse, collections::*};

#[allow(unused_imports)]
use proconio::{
    fastout, input,
    marker::{Chars, Usize1},
};

#[allow(unused_imports)]
use itertools::Itertools;

#[allow(unused_imports)]
use num::Integer;

#[fastout]
pub fn main() {
    input! {
        mut n: isize,
        k: isize,
    }

    n %= k;

    loop {
        let nn = (n - k).abs();
        if nn >= n {
            println!("{}", n);
            return;
        }
        n = nn;
    }
}


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

const int mod = 1000000007;

int main()
{
	//freopen("in.in", "r", stdin);
	//freopen("out.out", "w", stdout);

	int res = 1, n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) res = 1ll * res * i % mod;
	for (int i = 1; i <= m; ++i) res = 1ll * res * i % mod;
	if (abs(n - m) > 1) puts("0");
	else 
	{
		if (n == m) res = 1ll * res * 2 % mod;
		printf("%d\n", res);
	}
	
	
	return 0;
}


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

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

int main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  
  ll a, b;
  cin >> a >> b;
  
  ll AB = a*b;
  ll ans = AB / gcd(a, b);
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3648
#import <Foundation/Foundation.h>

int main(void){

    @autoreleasepool {
    
        NSStringEncoding enc = NSUTF8StringEncoding;
        NSFileHandle *stdin = [NSFileHandle fileHandleWithStandardInput];
        NSFileHandle *stdout = [NSFileHandle fileHandleWithStandardOutput];
        
        NSData *indata = [stdin readDataToEndOfFile];
        NSMutableString *str = [NSMutableString alloc];
        [str initWithBytes:indata.bytes length:indata.length encoding:enc];
        
        NSScanner *scan = [NSScanner alloc];
        [scan initWithString:str];
        
        NSString *n_str = [NSString alloc];
        [scan scanUpToString:@"\n" intoString:&n_str];
        NSInteger n = [n_str integerValue];
        
        [stdout writeData:[(n < 1000?@"ABC":@"ABD") dataUsingEncoding:enc]];
    }
    
    return 0;
}

Measured memory_bytes: 10008
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);
	static boolean debug = false;

	static boolean f(int n, int m) {
		int p = n;
		for (int i=m; i>=1; i--) {
			if (p >= i) p -= i;
		}
		return p == 0;
	}

	static void f2(int n, int m) {
		int p = n;
		for (int i=m; i>=1; i--) {
			if (p >= i) {
				p -= i;
				System.out.println(i);
			}
		}
	}

	static void solve() {
		int n = in.nextInt();
		int l = -1, r = n;
		while (r - l > 1) {
			int m = (l+r)/2;
			if (f(n, m)) r = m;
			else l = m;
		}

		f2(n,r);
	}

	public static void main(String[] args) {
		debug = args.length > 0;
		long start = System.nanoTime();

		solve();
		out.flush();

		long end = System.nanoTime();
		dump((end - start) / 1000000 + " ms");
		in.close();
		out.close();
	}

	static void dump(Object... o) { if (debug) System.err.println(Arrays.deepToString(o)); }
}

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

vector<string> v(12);
bool used[12][12];
void dfs(int i, int j) {
    if(i < 0 || i > 11 || j < 0 || j > 11) return;
    if(!used[i][j] && v[i][j] == '1') {
        used[i][j] = true;
        dfs(i+1, j); dfs(i, j+1); dfs(i-1, j); dfs(i, j-1);
    }
    return;
}

int main() {
    while(cin >> v[0]) {
        for(int i=0;i<12;i++)
            for(int j=0;j<12;j++)
                used[i][j] = false;

        for(int i = 1;i<12;i++) {
            cin >> v[i];
        }
        int cnt = 0;
        for(int i = 0;i < 12; i++) {
            for(int j = 0; j < 12; j++) {
                if(!used[i][j] && v[i][j] == '1') {
                    cnt++;
                    dfs(i, j);
                }
            }
        }
        cout << cnt << endl;
    }
}

Measured memory_bytes: 3148
#include<iostream>
#include<map>
#include<string>

using namespace std;

int main(){
	long long a,b,c;
	cin>>a>>b>>c;

	long long hlfa=abs((a/2)*b*c-(a-a/2)*b*c);
	long long hlfb=abs((b/2)*a*c-(b-b/2)*a*c);
	long long hlfc=abs((c/2)*a*b-(c-c/2)*a*b);
	long long mn=min(hlfa,hlfb);	
	mn=min(mn,hlfc);	
	cout<<mn<<"\n";
	return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (long long i = 0; i < n; i++)
#define FOR(i, start, end) for (long long i = start; i < end; i++)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1'000'000'007
using ll = long long;
using namespace std;
const int INF32       = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7        = 1'000'000'007;
const int MOD9        = 1'000'000'009;
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;
}
void print() { std::cout << '\n'; }
template <class H, class... T> void print(H &&head, T &&... args) {
    std::cout << head;
    sizeof...(args) == 0 ? std::cout << "" : std::cout << ' ';
    print(std::forward<T>(args)...);
}
template <class T> void print(std::vector<T> &v) {
    for (int i = 0; i < v.size(); i++) {
        std::cout << v[i];
        i == v.size() - 1 ? std::cout << '\n' : std::cout << ' ';
    }
}
template <class T> void print(std::vector<std::vector<T>> &v) {
    for (int i = 0; i < v.size(); i++) {
        for (int j = 0; j < v[i].size(); j++) {
            std::cout << v[i][j];
            j == v[i].size() - 1 ? std::cout << '\n' : std::cout << ' ';
        }
    }
}

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

    int N;
    cin >> N;
    vector<int> H(N);
    for (auto &&i : H) {
        cin >> i;
    }
    int mx = H[N - 1];
    for (int i = N - 2; i >= 0; i--) {
        if (!chmin(mx, H[i])) {
            int less = H[i] - mx;
            if (1 < less) {
                print("No");
                return 0;
            }
        }
    }

    print("Yes");

    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<ll,ll,ll> T;
const long long INF = 1LL<<60;
const int MOD = 1000000000+7;
#define rev(s) (string((s).rbegin(), (s).rend()))
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };
// cout << fixed << setprecision(10) << ans << endl;
// *min_element(c + l, c + r) *max_element(c + l, c + r)
// int dx[8]={1,1,0,-1,-1,-1,0,1};
// int dy[8]={0,1,1,1,0,-1,-1,-1};
// int dx[4]={1,0,-1,0};
// int dy[4]={0,1,0,-1};
// struct Edge {
//   int to, id;
//   Edge(int to, int id): to(to), id(id) {}
// };

int main() {
  int N,K;cin>>N>>K;
  vector<int> a(N);
  rep(i,N) cin>>a[i];
  vector<int> s(N+1,0);
  map<int,vector<int>> dic;
  dic[0].push_back(0);
  rep(i,N) {
    s[i+1] = (s[i] + a[i]) % K;
    // cout<<s[i+1]<<endl;
  }
  rep(i,N) {
    dic[((s[i+1] - (i+1)) % K + K) % K].push_back(i+1);
  }
  ll ans = 0;
  for(auto it = dic.begin();it!=dic.end();++it) {
    if(it->second.size() < 2) continue;
    int cnt = 0;
    for(auto now : it->second) {
      int plc = lower_bound(it->second.begin(),it->second.end(),now+K) - it->second.begin();
      ans += plc - 1 - cnt;
      // cout<<it->first<<" "<<now<<" "<<plc<<" "<<cnt<<" "<<ans<<endl;
      cnt++;
    }
  }
  cout<<ans<<endl;
}


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

int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    vector<int> origin(n);
    for(int i = 0; i < n; ++i)
    {
        int t;
        cin >> t;
        v[i] = t;
        origin[i] = t;
    }
    sort(v.rbegin(), v.rend());
    for(int num : origin)
    {
        if(num == *v.begin())
        {
            cout << *(v.begin() + 1) << endl;
        }
        else
        {
            cout << *v.begin() << endl;
        }
    }
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void solve() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    rep(i, N) {
        cin >> A[i];
    }
    set<ll> used;
    ll idx = 0;
    ll ans = 0;
    rep(i, N) {
        ll a = A[idx];
        if (a == 2) {
            cout << ans + 1<< '\n';
            return;
        }else {
            if (used.count(a)) {
                cout << -1 << '\n';
                return;
            }else {
                used.insert(a);
                idx = a - 1;
                ans ++;
            }
        }
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}


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

using namespace std;


#define PI 3.14159265
#define int long long

const int mod = 1e9 + 7;


main(){


	int n, k;

	cin >> n >> k;


	long double sum = 0, base = 2;

	for(int i = 1; i <= n; i++){
		int t = i, step = 0;
		while(t < k){
			t *= 2;
			step++;
		}


		sum += 1 / pow(base, step);
	}


	cout << fixed << setprecision(15) << sum / n << endl;

	return 0;
}

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

int main(){
	long long int x, y;
	string str;
	cin >> x;

	
	y = x/11;
	x = fmod(x, 11);
	if(x==0) cout << 2*y << endl;
	else if((x-6)<=0) cout << 2*y+1 << endl;
	else cout << 2*y+2 << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<stdio.h>
#include<vector>
using namespace std;
#define int long long
#define rep(s,i,n) for(int i=s;i<n;i++)
#define c(n) cout<<n<<endl;
#define ic(n) int n;cin>>n;
#define sc(s) string s;cin>>s;
#define mod 1000000007
#define inf 1000000000000000007
#define f first
#define s second
#define mini(c,a,b) *min_element(c+a,c+b)
#define maxi(c,a,b) *max_element(c+a,c+b)
int keta(int x){
	rep(0,i,30){
		if(x<10){
			return i+1;
		}
		x=x/10;
	}
}
int gcd(int x,int y){
	int aa=x,bb=y;
	rep(0,i,1000){
		aa=aa%bb;
		if(aa==0){
			return bb;
		}	
		bb=bb%aa;
		if(bb==0){
			return aa;
		}
	}
}	
int lcm(int x,int y){
	int aa=x,bb=y;
	rep(0,i,1000){
		aa=aa%bb;
		if(aa==0){
			return x/bb*y;
		}	
		bb=bb%aa;
		if(bb==0){
			return x/aa*y;
		}
	}
}
bool p(int x){
	if(x==1)return false;
	rep(2,i,sqrt(x)+1){
		if(x%i==0&&x!=i){
			return false;
		}
	}	
	return true;
}	
char mem[214514];
char t[214514];
char c[214514];
string s[214514];
int l[214514],r[214514];
int a[214514];
int sa[214514];
signed main(){
	ic(n)
	rep(0,i,n){
		cin>>l[i];
		cin>>r[i];
	}	
	int sum=0;
	for(int j=3;j<114514;j+=2){
		if((j==3||j%4==1)&&p(j)&&p((j+1)/2)){
			sum++;
		}
		a[j]=sum;		
	}
	rep(0,i,n){
		if(l[i]>1)c(a[r[i]]-a[l[i]-2])
		else c(a[r[i]])
	}				
}			
			
			


Measured memory_bytes: 7296
import Control.Monad

main :: IO ()
main = do
    [h,w] <- map read . words <$> getLine
    s <- replicateM h getLine
    putStrLn $ replicate (w + 2) '#'
    forM_ s $ \t -> do
        putStrLn $ ['#'] ++ t ++ ['#']
    putStrLn $ replicate (w + 2) '#'

Measured memory_bytes: 1404
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Program
{
    static void Main()
    {
        Console.ReadLine();
        string[] arrStrOriginalTime = Console.ReadLine().Split(' ');
        int intDrinkCount = int.Parse(Console.ReadLine());
        List<string> lstStrProlemAndChangeTime = new List<string>();

        for(int i = 0; i < intDrinkCount; i++)
        {
            lstStrProlemAndChangeTime.Add(Console.ReadLine());
        }

        int intSumTime = 0;
        for(int i = 0; i < arrStrOriginalTime.Length; i++)
        {
            intSumTime += int.Parse(arrStrOriginalTime[i]);
        }

        for (int i = 0; i < intDrinkCount; i++)
        {

            int intProblemNumber = int.Parse(lstStrProlemAndChangeTime[i].Split(' ')[0]);
            int intChangeTime = int.Parse(lstStrProlemAndChangeTime[i].Split(' ')[1]);
            int intOutputTime = intSumTime - int.Parse(arrStrOriginalTime[intProblemNumber - 1]) + intChangeTime;
            Console.WriteLine(intOutputTime.ToString());
        }
    }
}

Measured memory_bytes: 2776
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

set<vector<int> > sv;
// vv[k] := 3個以上の合計が10になる饅頭の組合せ
vector<vector<int> > vv;
// v_sum[k] := vv[k]の合計
int v_sum[40] = {0};
// memo[k] := k 番目の組合せで饅頭が作れない
bool memo[40];
// すでに訪れた状態をメモ
set<vector<int> > mm;

// v := 饅頭の集合, sum := v[0] + v[1] + ... + v[v.size()-1] (合計)
void f(vector<int> v, int sum = 0){
	if( sum == 10 ){
		if( 3 <= v.size() ){ 
			sort(v.begin(), v.end());
			sv.insert(v);
		}
	}else if( sum < 10 ){
		for(int i = 9; i >= 1 ; i-- ){
			v.push_back(i);
			f(v, sum + i);
			v.pop_back();
		}
	}
}

// 3個以上で10になる饅頭の組合せを事前に列挙しておく
void init(){
	vector<int> v;
	f(v);
	for(set<vector<int> >::iterator it = sv.begin() ; it != sv.end() ; ++it ){
		vv.push_back(*it);
	}
	for(int i = 0 ; i < vv.size() ; i++ ){
		int sum = 0;
		for(int j = 0 ; j < vv[i].size() ; j++ ){
			sum += vv[i][j];
		}
		v_sum[i] = sum;
	}
}

// v[k](k番目の合計が10になる組合せ)が使えるかどうかを返す
bool check(int k, vector<int> s){
	for(int i = 0 ; i < vv[k].size() ; i++ ){
		int e = vv[k][i];
		if( s[e] == 0 ){
			return false;
		}else{
			s[e]--;
		}
	}
	return true;
}

// v[k](k番目の合計が10になる組合せ)を使う
void used(int k, vector<int> &s){
	for(int i = 0 ; i < vv[k].size() ; i++ ){
		int e = vv[k][i];
		if( s[e] ) s[e]--;
	}
}



// DFS
void dfs(int &res, int cnt, int sum, vector<int> &s){
	// 解の更新
	res = max(res, cnt);
	
	// すでに訪れたまんじゅうの状態なら探索打ち切り
	if( mm.count(s) ) return;
	mm.insert(s);
	
	if( sum < 10 ) return;
	// もう解が更新できない時点で探索打ち切る
	if( cnt + sum / 10 <= res ) return;
	
	for(int i = 0 ; i < vv.size() ; i++ ){
		if( memo[i] ) continue;
		
		if( check(i, s) ){
			vector<int> s_ = s;
			used(i, s_);
			dfs(res, cnt + 1, sum - v_sum[i], s_);
		}
	}
}

int solve(vector<int> &s){
	int sum = 0, res = 0;
	for(int i = 0 ; i < vv.size() ; i++ ){
		if( !check(i, s) ){
			memo[i] = true;
		}
	}
	
	mm.clear();
	for(int i = 1 ; i <= 9 ; i++ ) sum += i * s[i];
	dfs(res, 0, sum, s);
	return res;
}

int main(){
	// 3個以上で10になる饅頭の組合せを事前に列挙しておく
	init();
	
	int n;
	while( cin >> n, n ){
		
		// s[k] := 重さkの饅頭の個数
		vector<int> s(12, 0);
		fill(memo, memo + 40, false);
		
		for(int i=0 ; i < n ; i++ ){
			int e;
			cin >> e;
			s[e]++;
		}
		
		int ans = 0;
		// 2個で10になる組合せは貪欲に使う
		for(int i = 1 ; i <= 4 ; i++ ){
			int j = 10 - i;
			int k = min(s[i], s[j]);
			s[i] -= k;
			s[j] -= k;
			ans += k;
		}
		ans += s[5]/2;
		s[5] %= 2;
		// 3個以上で10になる組合せを探索する
		ans += solve(s);
		// 出力
		cout << ans << endl;
	}	
}

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

int main() {
    ll a; double b;
    cin >> a >> b;
    ll bb = b*100+0.5;
    ll ans = a*bb/100;
    cout << ans << endl;
}


Measured memory_bytes: 3724
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define vll vector<int>
#define pii pair<int,int>
#define pb push_back
#define sz(v) (int)(v).size()
#define inf 1e18
#define md 1000000007
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(int i=a;i<b;++i)
using namespace std;

#define M 100010

int ex(int a,int b){int ans=1;while(b){if(b&1)ans=(ans*a)%md;a=(a*a)%md,b/=2;}return ans;} 
inline int add(int a,int b){a=a%md+b%md;if(a>md)a%=md;return a;}
inline int sub(int a,int b){a=a%md-b%md;if(a<0)a+=md;return a;}
inline int mul(int a,int b){a%=md,b%=md;return (a*b)%md;}


int f[M],iv[M];
int C(int n,int r){
	if(n<r)return 0;
	return mul(f[n],mul(iv[r],iv[n-r]));
}

void prep_fac(){
	f[0]=1;
	rep(i,1,M)f[i]=mul(i,f[i-1]);
	iv[M-1]=ex(f[M-1],md-2);
	for(int i=M-2;i>=0;--i)iv[i]=mul(i+1,iv[i+1]);
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   	
   	prep_fac();
   	int S;cin>>S;
   	// a1+a2+...an=S  ai>=3 bi=ai-3
   	// b1+b2+...bn=S-3n  n+r-1Cr-1
   	int ans=0;
   	rep(i,1,S+1)(ans+=C(S-3*i+i-1,i-1))%=md;
   	cout<<ans;
   	
   	
    return 0;
}

Measured memory_bytes: 5200
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define rfor(i, a, b) for(int i = a; i < (int)b; i++)
#define all(ary) (ary).begin(), (ary).end()
#define debug(x) cerr << #x << ": " << x << '\n'
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
using namespace std;
using v = vector<int>;
using ll = long long;
template <class T = int> T in(){ T x; cin >> x; return (x);}
const int dy[4] = {-1, 0, 0, 1};
const int dx[4] = {0, -1, 1, 0};

string s;

int main(int argc, char *argv[]){
    cin >> s;
    string res;
    string s1 = s.substr(0, 2);
    string s2 = s.substr(2, 2);
    int a = stoi(s1);
    int b = stoi(s2);
    // if(b <= 0 or b >= 13) res = "NA";
    // else{
    //     if(stoi(s[0]) <= 0) res = "NA";
    //     else if()
    // }
    // cout << res << endl;
    // cout << a << endl;
    // cout << b << endl;

    /* YYMM */
    if(b >= 1 and b <= 12){
        if(a >= 0 and a <= 99){
            if(a >= 1 and a <= 12) cout << "AMBIGUOUS" << endl;
            else cout << "YYMM" << endl;
        }
    }//MMYY
    else if(a >= 1 and a <= 12){
        if(b >= 0 and b <= 99){
            if(b >= 1 and b <= 12) cout << "AMBIGUOUS" << endl;
            else cout << "MMYY" << endl;
        }
    }
    else cout << "NA" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

void dfs(vector<vector<int> >& Graph, vector<bool>& visited, int v, int k, bool root, ll& ans) {
  visited[v] = true;
  int n = root ? k-1 : k-2;
  for(int i=0; i<Graph[v].size(); i++) {
    int w = Graph[v][i];
    if(!visited[w]) {
      ans = (ans * n) % mod;
      n--;
      dfs(Graph, visited, w, k, false, ans);
    }
  }
}

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> A(N), B(N);
  vector<vector<int> > Graph(N);
  vector<bool> visited(N);

  rep(i, N-1) {
    cin >> A[i] >> B[i];
    A[i]--; B[i]--;
    Graph[A[i]].push_back(B[i]);
    Graph[B[i]].push_back(A[i]);
  }
  ll ans = K;
  dfs(Graph, visited, 0, K, true, ans);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 12416
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <limits>
#include <random>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef long long ll;
#define REP(i,n) for (int i = 0; i < n; i++)
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;

int N;
int h[100010];
int dp[100010];
const int INF = 2e9;

int main ()
{
    cin >> N;
    REP(i,N) cin >> h[i];
    fill (dp, dp + 100010, INF);

    dp[0] = 0;
    dp[1] = abs(h[0] - h[1]);
    for (int i = 2; i < N; i++) {
        dp[i] = min(dp[i - 2] + abs(h[i - 2] - h[i]), dp[i - 1] + abs(h[i - 1] - h[i]));
    }

    cout << dp[N - 1] << endl;

    return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>
int main()
{
	int A,B;
	scanf("%d%d",&A,&B);
	if(A!=1&&B!=1)
	{
		if(A>B)
			printf("Alice\n");
			else if(A==B)
				printf("Draw\n");
				else
					printf("Bob\n");
	}
	if(A==1&&B!=1)
	{
		printf("Alice\n");
	}
	if(A!=1&&B==1)
	{
		printf("Bob\n");
	}
	if(A==1&&B==1)
	{
		printf("Draw\n");
	}
}


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

int main() {
    ll h, n;
    cin >> h >> n;
    ll sum = 0;
    rep(i, n) {
        ll a;
        cin >> a;
        sum += a;
    }
    cout << (sum >= h ? "Yes\n" : "No\n");
}

Measured memory_bytes: 256