akhauriyash/Code-Regression huggingface dataset:
n, candy = list(map(int, input().split()))
nums = list(map(int, input().split()))

nums.sort()

ans = 0
for i in range(n):
    if candy >= nums[i]:
        candy -= nums[i]
        ans += 1
    else:
        break

# 配りきってまだ余っている場合
if candy > 0 and ans == n:
    ans -= 1
print(ans)


Measured memory_bytes: 3060
import java.util.*;

public class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] factor = new int[N+1];
        
        for(int num = 2; num <= N; num++) {
            int n = num;
            for(int i = 2; i * i <= n; i++) { //寻找质因子
                while(n % i == 0) {
                    factor[i]++;
                    n /= i;
                }
            }
            if(n != 1)
                factor[n]++;
        }
        
        long ans = 1;
        for(int a : factor) {
            ans = ans * (a + 1) % 1000000007;
        }

        System.out.println(ans);
    }

}   

Measured memory_bytes: 21204
#include<iostream>
#include<algorithm>
using namespace std;
struct ab{
	int c,v;
};
int main(){
	int n,i,sum=0;
	cin>>n;
	ab a[n];
	for(i=0;i<n;i++){
		cin>>a[i].c;
	}
	for(i=0;i<n;i++){
		cin>>a[i].v;
	}	
	for(i=0;i<n;i++){
		if(a[i].c-a[i].v>=0) {
			sum+=a[i].c-a[i].v;
		}
	}
	cout<<sum;
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;

#define ff 					first
#define ss 					second
#define sz(x) 				(int)(x).size()
#define all(x) 				begin(x), end(x)
#define rall(x) 			(x).rbegin(), (x).rend() 
#define rsz 				resize
#define ins 				insert 
#define ft 					front() 
#define bk 					back()
#define pf 					push_front 
#define pb 					push_back
#define eb 					emplace_back 
#define lb 					lower_bound 
#define ub 					upper_bound 
#define pqmax				priority_queue<int>
#define pqmin				priority_queue<int,vector<int>,greater<int>>
#define transup(x)			transform(x.begin(),x.end(),x.begin(),::toupper)
#define translow(x)			transform(x.begin(),x.end(),x.begin(),::tolower)
#define rep(i,a,b) 			for (int i = (a); i < (b); ++i)
#define per(i,a,b) 			for (int i = (b)-1; i >= (a); --i)
#define trav(a,x) 			for (auto a: x)

#define setbits(x)  		__builtin_popcountll(x)
#define zerobits(x)			__builtin_ctzll(x)

const ll mod = 1e9+7; // 998244353;
const ll inf = 1e18; 
const ld pie = acos((ld)-1);

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


int main(){

	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
    auto start = std::chrono::high_resolution_clock::now();
    /*start from here*/
    	
    int n;
    cin>>n;
    string s;
    cin>>s;
    int cntw=0;
    rep(i,0,sz(s)){
    	if(s[i]=='W'){
    		cntw++;
    	}
    }

	if(cntw==0){
		cout<<0<<'\n';
	}else{

		int cnt=0;
		vector<int> posw;
		vector<int> posr;
		rep(i,0,sz(s)){

			if(s[i]=='W'){
				posw.pb(i);
			}else{
				posr.pb(i);
			}
		}

		int k=0,l=posr.size()-1;
		while(k<sz(posw)&&l>=0){

			if(posw[k]<posr[l]){
				cnt++;
				swap(posr[l],posw[k]);
				swap(s[posr[l]],s[posw[k]]);
				l--;
			}
			k++;
		}

		cout<<cnt<<'\n';
	}

	auto stop = std::chrono::high_resolution_clock::now(); 
    auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>(stop - start); 
    
    // cerr << "Time taken : " << ((long double)duration.count())/((long double) 1e9) <<"s "<< endl;     

    return 0;

    /*STUFF TO LOOK:	
	1. Special cases/corner cases(n==0||n==1)
	2. Variables in loops
	3. Input ranges
	*/
}


Measured memory_bytes: 4848
import java.math.*

fun main(args: Array<String>) {
    val N = readInputLine().toInt()
    val B = readInputLine().split(" ").map { it.toInt() }.toIntArray()
    
    // A_1はB_1に等しい
    var ans = B[0]
    
    // A_2...A_N-1は各A_iについてmin(B_i, B_i-1)に等しい
    
    for (i in 0 until N - 2) {
        ans += Math.min(B[i], B[i + 1])
    }
    
    // A_NはB_N-1に等しい
    
    ans += B[N - 2]

    println(ans)
}

fun readInputLine(): String {
    return readLine()!!
}


Measured memory_bytes: 37644
def solve(N,Y):
    Y //= 1000
    for i in range(Y//10+1):
#        print(Y-N-9*i)
        if (Y - N -9*i)%4==0:
            b = (Y-N-9*i)//4
            if N-i-b >= 0 and b >=0:
                return [i,b,N-i-b]
    
    return [-1,-1,-1]


N,Y=[int(i) for i in input().split()]

lis = solve(N,Y)

print(lis[0],lis[1],lis[2])



Measured memory_bytes: 3060
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var lines = input.split('\n');



if(lines.length > 200) {
	console.log("Invalid dataset size. Dataset size is "+lines.length+" but must be <= 200");
} else {
	for (var i = 0; i < lines.length; i++) {
		var line = lines[i].trim();
	    if (line == '') break;
	    var vals = line.split(' ').map(function(i){return +i;});
	    if(vals.length != 2 || isNaN(vals[0])|| isNaN(vals[1]) || vals[0] < 0 || vals[0] > 1000000 || vals[1] < 0 || vals[1] > 1000000) {
	    	console.log("invalid dataset: "+line+ ". Use 0 <= a, b <= 1,000,000");
	    } else {
	    	var a = vals[0] + vals[1];
	    	var str = a + '';
	    	console.log(str.length);
		}
	}
}

Measured memory_bytes: 16000
#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <math.h>
#include <iomanip>
#include <algorithm>

using namespace std;

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

    long long int tot = 0;
    for (long long int i = 1; i <= n; i++) {
        if (i%5 && i%3) {
            tot += i;
        }
    }

    cout << tot << endl;


}


Measured memory_bytes: 3608
def num2alpha(num):
    if num<=26:
        return chr(64+num)
    elif num%26==0:
        return num2alpha(num//26-1)+chr(90)
    else:
        return num2alpha(num//26)+chr(64+num%26)

N = int(input())

S = num2alpha(N)
print(S.lower())

Measured memory_bytes: 9172
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define UN unsigned int
#define mod 1000000007
#define F first
#define S second
#define mk make_pair
#define B(v) v.begin(), v.end()
#define BS binary_search

int main()
{
	int a;string s;
	cin>>a>>s;
	if(a>=3200) cout<<s<<endl;
	else cout<<"red"<<endl;
}

Measured memory_bytes: 256
#D問題
import math
S = list(str(input()))
N = len(S)
ans = [0 for i in range(N)]

nowr = 0
nowl = 0
flag = 0
for i in range(N):
    if flag == 0:
        if S[i] == "R":
            nowr+=1
        else:
            flag = 1
            nowl = 1
    elif flag == 1:
        if S[i] == "R":
            ans[i-nowl-1] = math.ceil(nowr/2) + nowl//2
            ans[i-nowl] = math.ceil(nowl/2) + nowr//2
            nowr = 1
            nowl = 0
            flag = 0
        else:
            nowl += 1

ans[N-1-nowl] = math.ceil(nowr/2) + nowl//2
ans[N-nowl] = math.ceil(nowl/2) + nowr//2
for i in range(N):
    print(ans[i],end=" ")

Measured memory_bytes: 5552
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll GCD(ll x,ll y){
    if(y == 0) return x;
    else return GCD(y,x%y);
}

int main() {
    ll K;
    cin >> K;
    ll ans = 0;
    for(int i = 1;i <= K;++i){
        for(int j = 1;j <= K;++j){
            for(int k = 1;k <= K;++k){
                ans += GCD(GCD(i,j),k);
            }
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3600
Imports System.Collections.Generic
Module Module1
 
    Sub Main()
        Dim StationInputData As String = Console.ReadLine()
        Dim StationList As New List(Of String)
        For i As Integer = 0 To StationInputData.Length - 1
            StationList.Add(StationInputData.Substring(i, 1))
        Next
 
        Dim otherCompany As Boolean = False
 
        Dim preStation As String = String.Empty
        For Each station As String In StationList
            If preStation <> String.Empty AndAlso preStation <> station Then
                otherCompany = True
                Exit For
            End If
            preStation = station
        Next
 
        If otherCompany Then
            Console.WriteLine("Yes")
        Else
            Console.WriteLine("No")
        End If
        Stop
    End Sub
 
End Module

Measured memory_bytes: 21840
# ABC 093: B – Small and Large Integers
a, b, k = [int(s) for s in input().split()]
nums = []

if k >= b - a + 1:
    nums = list(range(a, b + 1))
else:
    nums = list(set(list(range(a, a + k)) + list(range(b - k + 1, b + 1))))
    nums.sort()

for num in nums:
    print(num)

Measured memory_bytes: 3060
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 1e6 + 10;
struct edge
{
    int to, nxt;
} map[maxn];

int n, m, stk[maxn], top, val, ans[maxn], tp, nxt[maxn];
int head[maxn], cnt;
bool vis[maxn], flag, tag[maxn];

inline void add(int x, int y)
{
    map[++cnt] = (edge){y, head[x]};
    head[x] = cnt;
    return;
}

void dfs(int x)
{
    stk[++top] = x;
    vis[x] = tag[x] = true;
    for (int i = head[x]; i; i = map[i].nxt)
    {
        int y = map[i].to;
        if (!vis[y])
        {
            dfs(y);
        }
        else if (tag[y])
        {
            val = y;
            flag = true;
        }
        if (flag)
        {
            return;
        }
    }
    top--;
    vis[x] = false;
    return;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!tag[i])
        {
            dfs(i);
            if (flag)
            {
                break;
            }
        }
    }
    if (!flag)
    {
        printf("-1");
        return 0;
    }
    int pos;
    for (int i = 1; i <= top; i++)
    {
        if (stk[i] == val)
        {
            pos = i;
        }
    }
    nxt[stk[top]] = val;
    for (int i = pos; i < top; i++)
    {
        nxt[stk[i]] = stk[i + 1];
    }
    for (int i = 1; i <= n; i++)
    {
        if (!nxt[i])
        {
            continue;
        }
        for (int j = head[i]; j; j = map[j].nxt)
        {
            int y = map[j].to;
            if (!nxt[y])
            {
                continue;
            }
            int p = i, q = nxt[i];
            while (q != y)
            {
                int r = nxt[q];
                nxt[p] = r;
                nxt[q] = 0;
                q = r;
            }
        }
    }
    int x;
    for (int i = 1; i <= n; i++)
    {
        if (nxt[i])
        {
            x = i;
        }
    }
    int p = x;
    ans[++tp] = p;
    p = nxt[p];
    while (p != x)
    {
        ans[++tp] = p;
        p = nxt[p];
    }
    cout << tp << endl;
    for (int i = 1; i <= tp; i++)
    {
        cout << ans[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 8448
// #include<bits/stdc++.h>
// using namespace std;
// #define F first
// #define S second
// #define PB push_back
// #define MP make_pair
// #define REP(i,a,b) for (int i = a; i <= b; i++)

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

// int main() {
//   ios::sync_with_stdio(0);
//   cin.tie(0);
//   freopen("input.txt", "r", stdin);
//   freopen("output.txt", "w", stdout);
//   //(a + b) mod m = (a mod m + b mod m) mod m;
//   //(a - b) mod m = (a mod m - b mod m) mod m;
//   //(a * b) mod m = (a mod m * b mod m) mod m;
//   // x = x % m;
//   // if (x < 0) x += m;
// }

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1000000007;
const char nl = '\n';
const int MX = 100001; //check the limits, dummy

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	//freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);

  int n,k;
  cin >> n>>k;
  vi nums(n,0);
  FOR(i, 0, n)
  {
    cin >> nums[i];
  }
  sort(all(nums));
  int count = 0;
  FOR(i, 0, k)
    count += nums[i];
  cout << count;
  return 0;
}

// read the question correctly (ll vs int)
// template by bqi343




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




int main()
{
    ll n;
    cin>>n;
    map<ll,ll>m;
    ll ans = 0;


     while (n % 2 == 0)
    {
        if(!m.count(2))m[2]=1;
        else m[2]++;
        n = n/2;
    }

    // n must be odd at this point. So we can skip
    // one element (Note i = i +2)
    for (ll i = 3; i <= sqrt(n); i = i + 2)
    {
        // While i divides n, print i and divide n
        while (n % i == 0)
        {
          if(!m.count(i))m[i]=1;
        else m[i]++;
            n = n/i;
        }
    }

    // This condition is to handle the case when n
    // is a prime number greater than 2
    if (n > 2)
        if(!m.count(n))m[n]=1;
        else m[n]++;
    for(auto c: m){

        ll k  =c.second;
        k = 8*k;
        k = k+1;
        ll p = sqrt(k)-1;
        p = p/2;

        ans+=p;

    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 3680
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int a;
		cin>>a;
		if(a%2==0){
			if(a%3!=0&&a%5!=0){
				cout<<"DENIED"<<endl;
				return 0;
			}
		}
	}
	cout<<"APPROVED"<<endl;
	return 0;
}


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

int main(){
    int n, q;
    std::cin >> n >> q;

    std::vector<std::string> names(n);
    std::vector<int> times(n);
    int val, buf, totalTime = 0;
    for(int i = 0; i < n; ++i){
        std::cin >> names.at(i) >> val;
        buf = std::min(q, val);
        totalTime += buf;
        times.at(i) = val - buf;        
        if(0 == times.at(i)){
            std::cout << names.at(i) << " " << totalTime << std::endl;
        }
    }

//    std::cout << "------" << std::endl;

    while(1){
        std::vector<int>::iterator itr = std::find_if(times.begin(), times.end(), [] (int elem) {return 0 != elem;});

        if(times.end() == itr){
            break;
        }else{

//            std::cout << "flag" << std::endl;

            while(times.end() != itr){
//                for(int i = 0; i < n; ++i){
//                    std::cout << names.at(i) << " " << times.at(i) << " / ";
//                }
//                std::cout << std::endl;

                buf = std::min(q, *itr);
                *itr -= buf;
                totalTime += buf;
                if(0 == *itr){
                    int i = std::distance(times.begin(), itr);
                    std::cout << names.at(i) << " " << totalTime << std::endl;
                }
                ++itr;
                itr = std::find_if(itr, times.end(), [] (int elem) {return 0 != elem;});
            }
        }
    }

    return 0;
}


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

using namespace std;

typedef long long LL;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<LL> vl;
typedef vector<vector<LL>> vvl;
typedef vector<vector<vector<LL>>> vvvl;


const int inf = 1e9+7;
const LL INF = 1e18+5;
const int mod = 1e9+7;
const int mxN = 1e5+5;
const int mxM = 1e5+5;
int p[1000005];

void count(){
    for(int i=2;i*i<=1000000;i++){
        if(p[i]==0){
            for(int j=i*i;j<=1000000;j+=i){
                if(p[j]==0) p[j] = i;
            }
        }
    }
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("E:\\Coding\\Programming\\input.txt", "r", stdin);
    freopen("E:\\Coding\\Programming\\output.txt", "w", stdout);
    #endif
    int n;
    cin>>n;
    LL ans = 0;
    memset(p,0,sizeof p);
    count();
    //cout<<"done"<<endl;
    //for(int i=1;i<=100;i++) cout<<p[i]<<" ";cout<<endl;
    for(int i=1;i<n;i++){
        int x = n-i;
        unordered_map<int,int> mp;
        while(x>1){
            if(p[x]==0){
                mp[x]++;
                break;
            }else{
                mp[p[x]]++;
                x = x/p[x];
            }
        }
        LL xx = 1;
        for(std::unordered_map<int,int>::iterator iter = mp.begin(); iter != mp.end(); ++iter){
            xx = xx*((iter->second)+1);
        }
        ans += xx;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 7536
#include <iostream>

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

int h[100000];

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

	cin >> N >> K;
	rep(i, N) {
		cin >> h[i];
		if (h[i] >= K) ans++;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 640
N, X = map(int,input().split())
x = list(map(int,input().split())) + [X]
ans = abs(X-x[0])

def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)

for i in range(N):
    ans = gcd(ans,abs(x[i]-X))
print(ans)

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

int main(){
    int a,b;
    double ans=0;
    cin>>a>>b;
    if(a>=13){
        ans=b;}
    else if(a>=6){
        ans=b/2;}
    
    cout<<ans<<endl;
    return 0;
    }


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace::std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define endl "\n"
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/numeric/interval.hpp>
#include <boost/numeric/interval/io.hpp>
#include <boost/any.hpp>
using namespace::std;
namespace mp = boost::multiprecision;
typedef mp::number<mp::cpp_dec_float<32,int64_t>> cfloat;
typedef mp::cpp_int cint;
typedef long long lint;
typedef long long ll;
typedef long double ldouble;
typedef vector<lint> vec;
typedef vector<vector<lint>> mat;
typedef vector<vector<vector<lint>>> mat3;
typedef vector<double> dvec;
typedef vector<vector<double>> dmat;
typedef vector<vector<vector<double>>> dmat3;
typedef vector<string> svec;
typedef vector<vector<string>> smat;
typedef vector<vector<vector<string>>> smat3;
typedef vector<pair<lint,lint>> pvec;
typedef vector<vector<pair<lint,lint>>> pmat;
typedef vector<vector<vector<pair<lint,lint>>>> pmat3;
#define rep(i, n) for(lint i = 0; i < (lint)(n); i++)
#define irep(i) for(lint i = 0;; i++)
#define irep1(i) for(lint i = 1;; i++)
#define irep2(i) for(lint i = 2;; i++)
#define rrep(i, n) for(lint i = (lint)(n-1); i >-1; i--)
#define rrepi(i,a,b) for(lint i = (lint)(b-1); i >a-1; i--)
#define repi(i,a,b) for(lint i=lint(a);i<lint(b);i++)
#define rep2(i,a,b,c) for(lint i=lint(a);i>lint(b);i+=c)
#define all(x) (x).begin(),(x).end()
#define PI 3.141592653589793
#define dist(x1,y1,x2,y2) (pow(pow(x2-x1,2)+pow(y2-y1,2),0.5))
#define output(v) do{bool f=0;for(auto i:v){cout<<(f?" ":"");if(i>INF/2)cout<<"INF";else cout<<i;f=1;}cout<<"\n";}while(0)
#define output2(v) for(auto j:v)output(j);
#define input(a,n) lint n;cin>>n;vector<lint>a(n);rep(i,n)cin>>a[i];
#define SUM(v) accumulate(all(v),0LL)
#define INF (1LL<<60)
#define IINF (1<<30)
#define LINF 9223372036854775807
#define MOD 1000000007
inline lint gcd(lint a,lint b){return b?gcd(b,a%b):a;}
inline lint lcm(lint a,lint b){return a*b/gcd(a,b);}
inline bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;}
inline bool chmax(auto& s,const auto& t){bool res=s<t;s=max(s,t);return res;}
inline lint mex(vector<lint> s){
    lint res=0;
    sort(all(s));
    while(binary_search(all(s),res))res++;
    return res;
}
vector<lint> dx={-1,1,0,0,1,1,-1,-1};
vector<lint> dy={0,0,-1,1,1,-1,1,-1};

lint binary_search(lint max,function<bool(lint)> func) {
    lint left = -1;
    lint right =max;
    while (right - left > 1) {
        lint mid = left + (right - left) / 2;
        if (func(mid)) right = mid;
        else left = mid;
    }
    return right;
}

int main(){
    string s;
    cin>>s;
    if((s[0]!=s[s.size()-1])^s.size()%2)cout<<"Second";
    else cout<<"First";
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N=22,M=1000010,P=1e9+7;
const int inf=0x3f3f3f3f;
const int INF=0xcfcfcfcf;
const double eps=1e-9,pi=asin(1)*2;
inline ll read();
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
inline int ADD(int a,int b) { return a+b>=P?a+b-P:a+b; }
inline int MINUS(int a,int b) { return a-b<0?a-b+P:a-b; }
#define plus(a,b) a=ADD(a,b)
#define minus(a,b) a=MINUS(a,b)
#define mul(a,b) a=(1ll*a*(b))%P
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define mp(x,y) make_pair(x,y)

int n,K;
int dp[(1<<N)|10][N];
char s[(1<<N)|10];

#ifdef FILE
const int RS=1<<20;
char buf[RS],*p1=buf,*p2=buf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,RS,stdin),p1==p2)?EOF:*p1++
#endif
inline ll read()
{
	ll s=0;
	bool flag=false;
	char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') flag=true;
	for(;'0'<=ch&&ch<='9';ch=getchar()) s=(s<<3)+(s<<1)+(ch^'0');
	if(flag) return -s;
	return s;
}

int main()
{
#ifdef FILE
	freopen(FILE ".in","r",stdin);
	freopen(FILE ".out","w",stdout);
#endif
	n=read(),K=read();
	for(int i=0;i<=n;i++)
	{
		scanf("%s",s);
		for(int j=0;j<(1<<i);j++) dp[(1<<i)|j][i]=(s[j]=='1');
	}
	for(int i=n;i>=0;i--)
	{
		for(int j=0;j<(1<<i);j++)
		{
			for(int k=i;k>=0;k--)
			{
				int res=dp[(1<<i)|j][k],S=j>>k,T=j&((1<<k)-1);
				if(!res) continue;
				if(k) dp[(1<<i-k)|S][0]+=res;
				// Æ¥Åä³É¹¦, Ìõ¼þÊÇ k>0, ·ñÔò»áÓÐ (S,\empty)->(S,\empty)
				if(T!=((1<<k)-1)) // Æ¥Åä 0, Ìõ¼þÊÇ T ÖÐ±ØÐë´æÔÚ 0 
				{
					int p=k-1;
					while(T&(1<<p)) p--;
					dp[(1<<i-k+1+p)|(S<<p+1)|(T&(1<<p)-1)][p]+=res;
				}
				if(T) // Æ¥Åä 1, Ìõ¼þÊÇ T ÖÐ±ØÐë´æÔÚ 1 
				{
					int p=k-1;
					while(!(T&(1<<p))) p--;
					dp[(1<<i-k+1+p)|(S+S+1<<p)|(T&(1<<p)-1)][p]+=res;
				} 
			}
		}
	}
	for(int i=n;i>=0;i--)
	{
		for(int j=0;j<(1<<i);j++)
		{
/*
			for(int k=n;k>=0;k--)
				cerr<<"("<<i<<","<<j<<","<<k<<"): "<<dp[(1<<i)|j][k]<<"\n";
//*/
			if(dp[(1<<i)|j][0]>=K)
			{
				for(int l=i-1;l>=0;l--) putchar(((j>>l)&1)|'0');
				putchar('\n');
				return 0;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 183552
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>P;
const ll INF=1e18,MOD=1e9+7;
int main(){
    double w,h,x,y;
    cin>>w>>h>>x>>y;
    bool flag=false;
    if(w==x*2&&h==y*2)flag=true;
    double ans=w*h/2;
    if(flag)cout<<ans<<" "<<1<<endl;
    else cout<<ans<<" "<<0<<endl;
}   


Measured memory_bytes: 256
/*{{{*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(LL &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const LL &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1e6+10;
int main(){
    int A,B,T;
    R(A,B,T);
    int an=0;
    FOR(i,1,T){
        if(i%A==0)an+=B;
    }
    W(an);
    return 0;
}


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

int main() {
  int a,b,x;
  cin>>a>>b>>x;
  double ans;
  cout << fixed << setprecision(7);
  if(2*x>=a*a*b)ans=atan(2.0*(a*a*b-x)/(a*a*a))*180.0/3.14159265;
  else ans=atan((a*b*b/2.0)/x)*180.0/3.14159265;
  cout<<ans<<endl;
}


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

int main()
{
	int d;
	while (cin >> d) {
		int res = 0;
		for (int i = d; i < 600; i += d) {
			res += i * i * d;
		}
		cout << res << endl;
	}
	return 0;
}

Measured memory_bytes: 2976
tap_list = list(input())
cnt = 0
for tap in tap_list:
    if cnt == 0:
        if tap == "L":
            cnt = 2
            break
        else:
            cnt = 1
    elif cnt == 1:
        if tap == "R":
            cnt = 2
            break
        else:
            cnt = 0

if cnt == 2:
    print("No")
else:
    print("Yes")

Measured memory_bytes: 3060
//بسم الله الرحمن الرحيم
//* In The Name 0f ALLAH *//* The Most Beneficent *//* The Most Merciful *//*
#include<bits/stdc++.h>
using namespace std;
#define el << endl
typedef long int li;
typedef long long ll;
#define inf 1e9+123
#define tc int T; cin>>T; while(T--)
#define GOOD_BYE return 0;
#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define file() freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout)
const int mx = 1e5+123;
const ll MAX = 1e9+5;
//......TEMPLATE TERMINATES HERE......*//*......LET'S BEGIN (-_^)......//
int n,a[mx][4];
int dp[mx][4];


int man(int i, int f){

    if(i>n) return 0;
    if(dp[i][f]!=-1) return dp[i][f];

    int r=0;
    for(int j=1;j<=3;j++){
        if(j!=f)
            r=max(r,a[i][j]+man(i+1,j));
    }
    return dp[i][f]=r;
}

void fn(){

    memset(dp,-1,sizeof(dp));
    cin >> n;
    for(int i=1;i<=n;++i)
        cin >> a[i][1] >> a[i][2] >> a[i][3];
    cout << man(1,0) el;
}

int main(){

    //file();
    optimize();
    //tc
        fn();

    GOOD_BYE
}

///////////*  N A Y E M  *///////////

Measured memory_bytes: 14516
fun main(args: Array<String>) {

    val (n, m) = readLine()!!.split(" ").map { it.toInt() }

    var lMax = 0
    var RMin = Int.MAX_VALUE

    for (i in 0 until m) {
        val (l, r) = readLine()!!.split(" ").map { it.toInt() }

        if (l > lMax) {
            lMax = l
        }

        if (r < RMin) {
            RMin = r
        }
    }

    if (RMin - lMax < 0) println(0) else println(RMin - lMax + 1)

}

Measured memory_bytes: 55808
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <math.h>
//main definations
#define UI unsigned int
#define LLI long long int
#define ULLI unsigned long long int
void read_array(int *a, int n);
void write_array(int *a, int n);
void sort_array(int *a, int n);
//codechef only
#define TC for(UI defined_i=1;defined_i<=t;defined_i++)
using namespace std;

int main(){
	int x, t;
	cin>>x>>t;
	if(x<=t)
		cout<<"0"<<endl;
	else{
		x=x-t;
		cout<<x<<endl;
	}
	return 0;
}

void read_array(int *a, int n){
	for(int i=0;i<n;i++){
		cin>>*(a+i);
	}
}
void write_array(int *a, int n){
	for(int i=0;i<n;i++){
		cout<<*(a+i)<<" ";
	}
}
void sort_array(int *a, int n){
	sort(a,a+n);
}

Measured memory_bytes: 256
#include <cstdio>
#include <functional>
#include <algorithm>
#include <vector>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iostream>
#include <queue>
#include <math.h>
#include <bits/stdc++.h>
#include <queue>
#include <map>

using namespace std;

#define INF (1ll<<60)
#define INFint (1<<30)
#define MOD 1000000007
#define BOUND 27182818284

typedef long long ll;
typedef long long int lli;
typedef pair<ll,ll> P;

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

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

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

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

// gcd array
int findGCD(int arr[], int n){
    int result = arr[0];
    for (int i=1; i < n; i++)
        result = gcd(arr[i], result);
    return result;
}

template<typename T>
T lcm( T m, T n ){
    // 引数に0がある場合は0を返す
    if ( ( 0 == m ) || ( 0 == n ) )
        return 0;
    return ((m/gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    fill( (T*)array, (T*)(array+N), val );
}


int dx[5]={1,0,-1,0};
int dy[5]={0,1,0,-1};
// v.front() = -BOUND;
// v.back() = BOUND;

//struct edge{
//    int cost, to;
//
//    edge(int in_cost, int in_to){
//        cost=in_cost;
//        to=in_to;
//    }
//    bool operator<(const edge &a) const
//    {
//        return cost > a.cost;
//    }
//};

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

    int ans=0;
    for(int i=A; i<=T; i+=A){
        ans+=B;
    }

    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
input_str = gets
x, k, d = input_str.split.collect{|l| l.to_i.abs }

#puts "x=#{x}, k=#{k}, d=#{d}"
n = x / d
m = x % d
#puts "n=#{n}, m=#{m}"

if k < n then
  v = x - (k * d)
else
  v = x - (n * d)
  if (k - n).odd? then
    v = (v - d).abs
  end
end

puts v



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

template <typename T> T gcd(T x, T y) {
  if (y == 0)
    return x;
  return gcd(y, x % y);
}

template <typename T> T lcm(T x, T y) {
  if (x == 0 || y == 0)
    return 0;
  return x / gcd(x, y) * y;
}

int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}

vector<int> p;
vector<int> r;

void init(int n) {
  p.reserve(n);
  r.reserve(n);
  for (int i = 0; i < n; i++) {
    p[i] = i;
    r[i] = 0;
  }
}

int root(int x) { return p[x] == x ? x : p[x] = root(p[x]); }

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

void unite(int x, int y) {
  x = root(x);
  y = root(y);
  if (x == y)
    return;

  if (r[x] < r[y])
    p[x] = y;
  else {
    p[y] = x;
    if (r[x] == r[y])
      r[x]++;
  }
}

int main() {
  string S;
  cin >> S;
  int w;
  cin >> w;
  for (int i = 0; i < S.size(); i += w) {
    cout << S[i];
  }
  cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <cstdlib>  // abs() for integer 絶対値求めやつ
#include <cmath>    // abs() for float, and fabs()
#include <algorithm>
#include <vector>
#include <string>
#define rep(i,n) for(int i = 0; i< (n);i++)
#define SORT(a) sort((a).begin(),(a).end());
#define che(a,string) cout<<string<<":"<<(a)<<endl;
#define ch(a,string) cout<<string<<":"<<(a)<<" ";
using namespace std;
typedef pair<int,int> p;

int func(string s, string t){
	int ans = 0 ;
	for(char c='a';c<='z';c++){
		bool founds = false, foundt =false;
		for(int i = 0 ; i <s.length();i++){
			if(s[i]==c){
				founds=true;
			}
		}
		for(int i = 0 ; i < t.length();i++){
			if(t[i]==c){
				foundt=true;
			}
		}
		if(founds&&foundt){
			ans ++;
		}
		}
		return ans;
}	
	int main(){
	int n;
	cin>>n;
	string s;
	cin >> s;
	int ans = 0;
	for(int i = 0; i<=n; i++){
		int tmp =func(s.substr(0,i),s.substr(i));
		ans =max(ans,tmp); 
	}
	cout<<ans<<endl;
}




Measured memory_bytes: 256
get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: map(int, raw_input().strip().split())
getss = lambda n: [gets() for _ in xrange(n)]

# N = 10
# N = 50
# N = 10000000019

N = get()
x = int(N ** 0.5)
for i in xrange(x, 0, -1):
    if N / i * i == N:
        print i + N / i - 2
        exit()


Measured memory_bytes: 2692
# include <iostream>
# include <algorithm>
# include <cmath>

int n;
int edge[3];

int main() {
	std::cin >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < 3; ++j)
			std::cin >> edge[j];
		std::sort(edge, edge + 3);
		if (pow(edge[2],2)==pow(edge[1],2)+pow(edge[0],2))
			std::cout << "YES" << std::endl;
		else
			std::cout << "NO" << std::endl;
	}
		return 0;
}

Measured memory_bytes: 1168
function Main(s){
  const n = s.length;
  var ans = 0;
  var a = s[0];
  for(var i = 1; i < n; i++){
    if(s[i] !== a){
      ans++;
      a = s[i];
    }
  }
  console.log(ans);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8").trim());

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


int main(void){
    int a, b, c;
    vector<int> v={};
    cin >> a >> b >> c;
    v.push_back(a);
    v.push_back(b);
    v.push_back(c);
    
    sort(v.begin(),v.end());
    
    cout << v.at(0);
    for(int i = 1; i < v.size(); ++i) {
        cout << " " << v.at(i);
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 3136
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
#define F first
#define S second
typedef vector<pli> vpli;
#define MOD 1000000007
#define mp make_pair
#define pb push_back
#define all(v) v.begin(),v.end() 
#define tests int t; cin>>t; while(t--)
#define take(a,b,c) for(b=0;b<c;b++) cin>>a[b];
#define INF 1e18
// https://codeforces.com/problemset/page/3?tags=1500-1800
map <int,stack<int> > m;
int main()
{	
  ll x;
  cin>>x;
  ll y=100;
  ll j=1;
  while(1){
    y+=y/100;
    if(y>=x){
      cout<<j;
      break;
    }
    else j++;
  }
}


Measured memory_bytes: 3624
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <cstdio>
#include <utility>
#include <algorithm>

using namespace std;

int main() {
  long long n, c, k;
  cin >> n >> c >> k;
  vector<long long> a(n);
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }

  sort(a.begin(), a.end());

  int cnt = 0;
  for(int i = 0; i < n; i++) {
    if(a[i] == -1) continue;
    for(int j = i+1; j < i+c; j++) {
      if(j > n-1) { break;}
      if(a[i] + k >= a[j]) {
        a[j] = -1;
      }
    }
    cnt++;
  }

  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
void main_sub(void);
int main(int argc, char* argv[]) {
    main_sub();
    return 0;
}
// int を int64_t にする
// g++ に -DUSE_STRICT_INT をつけるか、
// 下のコメントアウトを外すと無効化
// #define USE_STRICT_INT
using i64 = int64_t;
#ifndef USE_STRICT_INT
#define int i64
#endif
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
constexpr int INF = (1 << 30);
constexpr i64 INFL = (1LL << 62);
constexpr i64 MOD = 1000000007;

void main_sub(void) {
    int n, p;
    cin >> n >> p;
    string s;
    cin >> s;
    if (10 % p == 0) {
        int ans = 0;
        rep(i, n) {
            if ((s[i] - '0') % p == 0) {
                ans += i + 1;
            }
        }
        cout << ans << endl;
        return;
    }
    vector<int> d(n + 1, 0);
    int ten = 1;
    for (int i = n - 1; i >= 0; --i) {
        int a = (s[i] - '0') * ten % p;
        d[i] = (d[i + 1] + a) % p;
        ten *= 10;
        ten %= p;
    }
    vector<int> cnt(p);
    int ans = 0;
    for (int i = n; i >= 0; --i) {
        ans += cnt[d[i]];
        cnt[d[i]]++;
    }
    cout << ans << endl;
    return;
}

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

int main() {
	vector<int> v; int n, q, c, x, y; cin >> n >> q;
	v.resize(n); fill(v.begin(), v.end(), INT_MAX);
	for (int i = 0; i < q; i++) {
		cin >> c >> x >> y;
		switch (c) {
		case 0:
			v[x] = y; break;
		case 1:
			auto itr = min_element(v.begin() + x, v.begin() + y + 1);
			cout << *itr << endl; break;
		}
	}
	return 0;
}


Measured memory_bytes: 3140
class stack:
    def __init__(self,arg_size):
        self.size = arg_size
        self.stack = [None] * self.size
        self.head = 0
        self.tail = 0

    def isEmpty(self):
        return self.tail == self.head
    
    def isFull(self):
        return len(self.stack) == self.tail

    def push(self, arg_object):
        self.stack[self.tail] = arg_object
        self.tail += 1

    def pop(self):
        self.tail -= 1
        return self.stack[self.tail]

    def top(self):
        return self.stack[self.head]

num = 101
s = stack(num)

po = list(input().split(' '))

for i in po:
    if i not in '+-*':
        s.push(int(i))
    
    else:
        a = s.pop()
        b = s.pop()
        if i == '+':
            s.push(b+a)
        elif i == '*':
            s.push(b*a)
        else:
            s.push(b-a)

print(s.top())


Measured memory_bytes: 5600
// This file is a "Hello, world!" in Java language by OpenJDK for wandbox.

import java.util.*;
import java.io.*;

class Main
{
	public static void main(String[] args){
		new Main().run();
	}
	
	void run(){
		Scanner sc=new Scanner(System.in);
		int H=sc.nextInt();
		int N=sc.nextInt();
		int[] A=new int[N];
		int[] B=new int[N];
		for(int i=0;i<N;++i){
			A[i]=sc.nextInt();
			B[i]=sc.nextInt();
		}
		long[] dp=new long[H+1];
		Arrays.fill(dp,Long.MAX_VALUE/3);
		dp[0]=0;
		for(int i=0;i<N;++i){
			for(int h=0;h<=H;++h){
				dp[Math.min(H,h+A[i])]=Math.min(dp[Math.min(H,h+A[i])],dp[h]+B[i]);
			}
		}
		System.out.println(dp[H]);
	}
}

// OpenJDK reference:
//   http://openjdk.java.net/

// Java language references:
//   http://docs.oracle.com/javase


Measured memory_bytes: 26324
#include<iostream>
#include<cstdlib>
#include<string>
#include<vector>
#include<map>
#include<unordered_map>
#include<queue>
#include<algorithm>
#include<iomanip>
using namespace std;
using ll = long long int;
const int mod = 1e9 + 7;
#define rep(i, a, b) for(ll i = a;i < b; i++)

int main() {

	int a, b, c, d;
	cin >> a >> b >> c >> d;

	while (1) {
		c -= b;
		a -= d;
		if (c <= 0) {
			cout << "Yes" << endl;
			break;
		}else if (a <= 0) {
			cout << "No" << endl;
			break;
		}
	}

	return 0;
}


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

typedef long long ll;

#define MAX_V 1002
#define MOD 1000000007LL

int V, E, n;
vector<int> G[MAX_V], rG[MAX_V], vs;
vector<int> t[MAX_V], rt[MAX_V];
bool used[MAX_V];
int cmp[MAX_V];

ll dp[MAX_V];

void init(){
  for(int i = 0; i < MAX_V; i++){
    G[i].clear();
    rG[i].clear();
    t[i].clear();
    rt[i].clear();
  }
}

void add_edge(int from, int to){
  G[from].push_back(to);
  rG[to].push_back(from);
}

void dfs(int v){
  used[v] = true;
  for(int i = 0; i < G[v].size(); i++){
    int to = G[v][i];
    if(!used[to]) dfs(to);
  }
  vs.push_back(v);
}

void rdfs(int v, int k){
  used[v] = true;
  cmp[v] = k;
  for(int i = 0; i < rG[v].size(); i++){
    int to = rG[v][i];
    if(!used[to]) rdfs(to,k);
  }
}

int scc(){
  memset(used, 0, sizeof(used));
  vs.clear();
  for(int i = 0; i < V; i++) if(!used[i]) dfs(i);

  memset(used, 0, sizeof(used));

  int k = 0;
  for(int i = 0; i < vs.size(); i++){
    int to = vs[vs.size() - i - 1];
    if(!used[to]) rdfs(to,k++);
  }
  return k;
}

void makeGraph(){
  for(int i = 0; i < V; i++){
    int from = cmp[i];

    for(int j = 0; j < G[i].size(); j++){
      int to = cmp[G[i][j]];
      if(from == to) continue;

      if(find(t[from].begin(), t[from].end(), to) == t[from].end()){
        t[from].push_back(to);
      }
      if(find(rt[to].begin(), rt[to].end(), from) == rt[to].end()){
        rt[to].push_back(from);
      }
    }
  }
}

int main(){
  while(cin >> V >> E){
    init();

    for(int i = 0; i < E; i++){
      int from, to;
      cin >> from >> to;
      from--;
      to--;
      add_edge(from, to);
    }

    n = scc();
    makeGraph();

    ll ans = 1;

    for(int i = 0; i < n; i++){
      if(rt[i].empty()){
        dp[i] = 2;
      }
      else{
        dp[i] = 1;

        for(int j = 0; j < rt[i].size(); j++){
          dp[i] *= dp[rt[i][j]];
          dp[i] %= MOD;
        }

        dp[i]++;
        dp[i] %= MOD;
      }

      if(t[i].empty()){
        ans *= dp[i];
        ans %= MOD;
      }
    }

    cout << ans << endl;
  }
}

Measured memory_bytes: 0
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
using namespace std;

int main(void) {
  int X;
  cin >> X;
  for (int i = 0; i < 8; i++) {
    if (pow(2, i) > X) {
      cout << pow(2, i - 1);
      return 0;
    }
  }
  return 0;
}


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

struct Str
{
	int cnt[26]{0};
	Str(string& s)
	{
		for (int i = 0; i < s.length(); ++i)
			cnt[s[i] - 'a']++;
	}
	bool operator<(Str& s2)
	{
		for (int i = 0; i < 26; ++i)
		{
			if (cnt[i] < s2.cnt[i]) return 1;
			if (cnt[i] > s2.cnt[i]) return 0;
		}
		return 0;
	}
	bool operator==(Str& s)
	{
		bool ret = 1;
		for (int i = 0; i < 26; ++i)
			if (cnt[i] != s.cnt[i]) return 0;
		return 1;
	}
};

int N;
lli ans;
string s;
vector<Str> v;
vector<lli> num;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	v.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> s;
		v.emplace_back(Str(s));
	}
	sort(v.begin(), v.end());
	lli tmp=1;
	for(int i=0;i<v.size()-1;++i)
	{
		if (v[i] == v[i + 1]) tmp++;
		else
		{
			num.emplace_back(tmp);
			tmp = 1;
		}
	}
	num.emplace_back(tmp);
	for(auto& i : num)
	{
		ans += (i * (i - 1)) / 2;
	}
	cout << ans;
}


Measured memory_bytes: 11640
#標準入力の受付
N = 0
while((1 > N) | (N > 10000) | (type(N) is not int)):
	N = int(input())
#入力を超える1000円単位の金額の算出
tmp = N / 1000
i = 0
while(True):
    if(i >= tmp):
    	break
    i += 1

charge = i * 1000 - N
print(charge)

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

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

using ll = long long;

int main() {
	ll a, b;
	cin >> a >> b;
	string ans;
	if (a > 0 && b > 0) ans = "Positive";
	if (a * b <= 0) ans = "Zero";
	if (a < 0 && b < 0) {
		if ((a - b) % 2 == 0) ans = "Negative";
		else ans = "Positive";
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
typedef vector<vector<P>> vvP;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

int main() {
    string s;
    cin >> s;
    ll n = s.size();
    cout << s[0] << n-2 << s[n-1] << endl;
    re0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int x[5], i;

  for(i=0; i<5; i++)
    scanf("%d", &x[i]);

  for(i=0; i<5; i++){
    if(x[i]==0){
      printf("%d\n", i+1);
      break;
    }
  }

  return 0;
}


Measured memory_bytes: 1728
#include <iostream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define mod 1000000007
using namespace std;
typedef pair<llint, llint> P;
typedef pair<llint, P> E;

llint n;
llint a[200005];
llint dp[200005];
vector<llint> vec[200005];

int main(void)
{
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) vec[a[i]].push_back(i);
	
	dp[0] = 1;
	for(int i = 1; i <= n; i++){
		llint p = lower_bound(vec[a[i]].begin(), vec[a[i]].end(), i) - vec[a[i]].begin();
		if(p > 0){
			llint pre = vec[a[i]][p-1];
			if(pre != i-1) dp[i] += dp[pre], dp[i] %= mod;
		}
		dp[i] += dp[i-1], dp[i] %= mod;
	}
	cout << dp[n] << endl;
	
	return 0;
}


Measured memory_bytes: 14336
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>
#include <functional>

using namespace std;

#define LOG(...) printf(__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define CLR(a) memset((a), 0 ,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

struct UnionFind {
	vector<int> v;
	UnionFind(int n) : v(n)  { for (int i = 0; i < n; i++) v[i] = i; }
	int  find(int x)         { return v[x] == x ? x : v[x] = find(v[x]); }
	void unite(int x, int y) { v[find(x)] = find(y); }
};

int main() {
	int r;
	int n;
	while (cin >> r >> n, r){
		double hight[40] = {0};
		double suny[41];
		REP(i, 41)
			suny[i] = -1e9;
		REP(i, 41){
			if (-r<=i - 20&&i-20<=r )
				suny[i] = -(double)r + sqrt((double)r*(double)r - (double)(i - 20)*(double)(i - 20));
		}
		REP(i, n){
			int x, x2, h;
			cin >> x >> x2 >> h;
			REP(i,x2-x){
				hight[x + 20+i] = max(hight[x + 20+i], (double)h);
			}
		}
		double mi = 100.0;
		REP(i, 41){
			if (abs(i - 20) <= r){
				if (i - 20==-r)
					mi = min(mi, hight[i] -suny[i]);
				else if (i - 20==r)
					mi = min(mi, hight[i-1] - suny[i]);
				else
					mi = min(mi, min(hight[i],hight[i-1]) - suny[i]);
			}
		}
		printf("%.4lf\n", mi);
	}
}

Measured memory_bytes: 3068