akhauriyash/Code-Regression huggingface dataset:
S = input()
N = len(S)
for i in range(N-1):
    c2 = S[i:i+2]
    c3 = S[i:i+3]
    if len(set(c2)) == 1:
        print(i+1, i+2)
        exit()
    if  i != N-2 and len(set(c3)) == 2:
        print(i+1, i+3)
        exit()

print(-1, -1)

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

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;
const ll INF = 1LL<<60;
//int INF = numeric_limits<int>::max();

int main(int, char**) {
	int d; cin >> d;
	vector<int> C(26);
	vector<int> D(26, 0);
	vector<vector<int>> S(d, vector<int>(26));
	for (int i=0; i<26; i++) cin >> C[i];
	for (int i=0; i<d; i++) for (int j=0; j<26; j++) cin >> S[i][j];
	vector<int> T(d);
	for (int i=0; i<d; i++) cin >> T[i];
	int m = 0;
	int mind = 0;
	for (int i=0; i<d; i++) {
		for (int j=0; j<26; j++) {
			if (S[i][j] > m) {
				m = S[i][j];
				mind = j+1;
			}
		}
		cout << mind << endl;
	}
	return 0;
}


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

int main(int argc, char const *argv[])
{
	char c;
	cin >> c;
	if(c >= 'a' && c <='z')
		cout << 'a';
	else
		cout << 'A';
	return 0;
}

Measured memory_bytes: 3588
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 340
#define mid (l+r)/2
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef short int si;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll inf=1e18;
const ld pai=acos(-1);
ll n,mod;
vll v[100009];
ll dpdn[100009],dpup[100009];
void dfs1(ll node,ll p){
	dpdn[node]=dpup[node]=1;
	for(auto u:v[node]){
		if(u==p)C;
		dfs1(u,node);
		dpdn[node]*=(dpdn[u]+1);
		dpdn[node]%=mod;
	}
}
void dfs2(ll node,ll P){
	vll p,s;
	ll crnt=1;
	for(auto u:v[node]){
		if(u==P)C;
		crnt*=(dpdn[u]+1);
		crnt%=mod;
		p.pb(crnt);
	}crnt=1;
	for(ll i=v[node].size()-1;i>=0;i--){
		ll u=v[node][i];
		if(u==P)C;
		crnt*=(dpdn[u]+1);
		crnt%=mod;
		s.pb(crnt);
	}reverse(s.begin(),s.end());
	ll z=-1;
	for(int i=0;i<v[node].size();i++){
		int u=v[node][i];
		if(u==P)C;
		z++;
		ll bef=1;
		ll aft=1;
		if(z)bef=p[z-1];
		if(z!=s.size()-1)aft=s[z+1];
		dpup[u]=((1)+((((dpup[node]%mod)*(bef%mod))%mod)*(aft%mod))%mod)%mod;
		dfs2(u,node);
	}
}
int main(){
	cin>>n>>mod;
	for(ll i=0;i<n-1;i++){
		ll a,b;cin>>a>>b;
		a--,b--;
		v[a].pb(b);
		v[b].pb(a);
	}
	dfs1(0,0);
	dfs2(0,0);
	for(ll i=0;i<n;i++)cout<<(dpup[i]*dpdn[i])%mod<<endl;
}


Measured memory_bytes: 23040
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define mrep(i,j,n) for(int i = j; i < n; i++)
#define reps(i,n) for(int i = 1; i <= n; i++)
#define rrep(i,n) for(int i = n-1; i >= 0; i--)
#define mreps(i,j,n) for(int i = j; i <= n; i++)
#define rreps(i,n) for(int i = n; i >= 1; i--)
#define co(x) cout << x <<endl
#define cs(x) cout << x <<" "
#define el cout << endl
#define sp(x) cout << setprecision(x);
#define cer(x) cerr << x <<endl
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ERASE(x,val) x.erase(remove(ALL(x), val), x.end())
#define vi vector<int> 
#define vvi vector<vector<int>> 
#define pii pair<int,int>
#define vpii vector<pair<int,int>> 
#define vl vector<ll> 
#define vvl vector<vector<ll>> 
#define vd vector<double> 
#define vvd vector<vector<double>> 
#define vb vector<bool> 
#define vvb vector<vector<bool>>
#define vs vector<string>
typedef long long ll;
using namespace std;
ll mod = 1e9 + 7;
int inf_i = 1001001000;
ll inf_l = 1001001001001000;
template<class T>inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; }return false; }
template<class T>inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; }return false; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { ll g = gcd(a, b); return a * b / g; }
bool is_prime(ll x) { for (ll i = 2; i * i <= x; i++) { if (x % i == 0)return false; } return true; }

void solve()
{
	string s, t, u;
	cin >> s >> t;
	int a, b;
	cin >> a >> b;
	cin >> u;
	map<string, int> m;
	m[s] = a;
	m[t] = b;
	m[u]--;
	co(m[s] << " " << m[t]);
	return;
}

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


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <numeric>
#include <cmath>
#include <iomanip> //cout << fixed << setprecision(15) << << endl;
#include <cassert>
//#include "atcoder/all"

using namespace std;
//using namespace atcoder;

typedef long long ll;

#define pb push_back
#define rep(i, n) for(int i=0;i<(n);i++)
#define REP(i, n) for(int i=1;i<=(n);i++)
#define P pair<int,int>

int mx8[] = {0, 0, 1, -1, -1, 1, -1, 1};
int my8[] = {-1, 1, 0, 0, -1, -1, 1, 1};
int mx4[] = {1, -1, 0, 0};
int my4[] = {0, 0, -1, 1};

const int MOD = 1000000007;

int main() {
    ios::sync_with_stdio(false);

    ll a; double b; cin >> a >> b;
    ll b1 = b*100 + 0.5;
    ll ans = a * b1 / 100;
    cout << ans << endl;
}

Measured memory_bytes: 3708
N, M = map(int, input().split())
trans = {}
for i in range(1, N+1):
    trans[i] = set()
for _ in range(M):
    a, b = map(int, input().split())
    trans[a].add(b)
    trans[b].add(a)

for i in trans[1]:
    if N in trans[i]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")


Measured memory_bytes: 89188
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b!=0?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}

int main(){
    ll a,b;
    cin>>a>>b;
    ll g=gcd(a,b),ng=g,cnt=1;
    for(ll i=2;i*i<=g&&ng!=1;i++){
        if(ng%i==0){
            cnt++;
            while(ng%i==0) ng/=i;
        }
    }
    cout<<(ng==1?cnt:cnt+1)<<endl;
    return 0;
}

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

using namespace std;
int main(void)
{
   int n;
   cin>>n;
   double x;
   double sum;
   string c;
   for(int i=0;i<n;i++)
   {
      cin>>x>>c;
      if(c == "JPY")
         sum+=x;
      else if(c == "BTC")
         sum+=x*380000;
   }
   cout<<sum<<endl;
   return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		for (int d = a; d <= b; ++d) {
			if (d % k == 0) {
				System.out.println("OK");
				return;
			}
		}

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

}


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

using namespace std;

#define all(x) begin(x), end(x)

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;

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

    int n;
    cin >> n;
    vi a(n);
    for (auto& x : a) {
        cin >> x;
    }

    sort(all(a));

    int gap = a[n / 2] - a[(n - 1) / 2];
    cout << gap << '\n';
    
    return 0;
}


Measured memory_bytes: 640
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    token.parse().ok().unwrap()
}

fn main() {
    let n = input::<usize>();
    let p = {
        let mut temp = (0..n).map(|_| input()).collect::<Vec<i64>>();
        temp.sort();
        temp
    };

    let ans = p.iter().sum::<i64>() - p[n - 1] / 2;
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,c=0,d=0;
  cin>>n;
  int a[n],b[n],i;
  for(i=0;i<n;i++)
    cin>>a[i]>>b[i];
  for(i=0;i<n;i++)
  {
    if(a[i]==b[i])
      c++;
    else
      c=0;
    if(c==3)
    {
      d++;
      break;
    }
  }
  if(d)
    cout<<"Yes";
  else
    cout<<"No";
}

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

YES = "Yes"  # type: str
NO = "No"  # type: str

def is_all_num(test):
    for c in test:
        if c not in "0123456789":
            return False
    return True

def solve(A: int, B: int, S: str):
    if S[A] == "-" and is_all_num(S[0:A]) and is_all_num(S[A+1:]):
        print(YES)
    else:
        print(NO)

# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(A, B, S)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

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

using namespace std;
using namespace __gnu_pbds;

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;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#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 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()

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

const int MOD = 998244353;
const ll INF = 1e18;
const int N = 2e5 + 12; //check the limits, dummy

ld fn (pl a, pl b) {
    ld ans = (a.f - b.f) * (a.f - b.f);
    ans = ans + 0.0 + (a.s - b.s) * (a.s - b.s);
    ans = (ld) sqrt ( (ld) ans);
    return ans;
}

int main() {

    ios_base::sync_with_stdio (0);
    cin.tie (0);

    ll n;
    cin >> n;
    vpl a (n);
    FOR (i, 0, n) cin >> a[i].f >> a[i].s;
    sort (all (a) );

    ld ans = 0;
    ll tot = 0;
    do {
        tot++;
        FOR (i, 1, n) {
            ans = ans + fn (a[i], a[i - 1]);
        }
    } while (next_permutation (all (a) ) );
    ans = ans / tot;
    cout << setprecision (10) << fixed << ans << '\n';

    return 0;
}


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

int main(){
  int s;
  cin >> s;
  set<int> st;
  st.insert(s);
  int ans = 1;
  while(true){
    ans++;
    if (s%2==0) s /= 2;
    else s = 3*s + 1;
    if (st.find(s)!=st.end()){
      cout << ans << endl;
      return 0;
    }
    st.insert(s);
  }
}


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

class ModularExponentiation
{
    long long ans;                    // Answer
public:
    long long compME(long long, long long, long long);  // Compute Modular Exponentiation
};

long long ModularExponentiation::compME(long long b, long long e, long long m)
{
    ans = 1;

    while (e > 0) {
       if ((e & 1) == 1) ans = (ans * b) % m;
       e >>= 1;
       b = (b * b) % m;
    }

    return ans;
}

int main(){
    long long N, ans=1, Mod=998244353, count=0, tmp=0, tmp2=1;;
    cin >>  N;
    vector<long long> a(N);
    for(long long i=0; i<N; i++){
	cin >> a[i];
    }
    if(a[0]!=0){
	cout << 0 << endl;
	return 0;
    }
	
    sort(a.begin(), a.end());
    ModularExponentiation objMain;
    for(long long i=0; i<N; i++){
	if(count==a[i]){
	    tmp++;
	}else{
	    count++;
	    ans *= objMain.compME(tmp2, tmp, Mod);
	    ans %= Mod;

	    tmp2=tmp;
	    if(count==a[i]){
		tmp=1;
	    }else{
		cout << 0 << endl;
		return 0;
	    }
	}

    }
    ans *= objMain.compME(tmp2, tmp, Mod);
    ans %= Mod;

    if(a[1]==0)
	ans=0;
    cout << ans << endl;
}



Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef pair<string , int> s_i;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> ve_vel;
typedef vector<vector<int>> ve_vei;
typedef vector<vector<char>> ve_vec;
typedef vector<vector<bool>> ve_veb;
typedef vector<vector<string>> ve_ves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pub push_back
#define puf push_front
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
//#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
const int64 INF = 1LL << 58;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
template<typename T> void remove(T & vector, unsigned int index){vector.erase(vector.begin() + index);}

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

    ll N, H; cin >> N >> H;
    vel a(N), b(N); rep(i,N) cin >> a[i] >> b[i];

    sort(rall(a)); sort(rall(b));

    int cnt = 0;
    rep(i,N) {
        if(b[i] > a[0]) { H -= b[i]; cnt++; }
        if(H <= 0) break;
    }
    if(H <= 0) {cout << cnt << endl; return 0;}
    do {
        H -= a[0];
        cnt++;
    } while(H > 0);
    cout << cnt << endl;
    return 0;
    
}

Measured memory_bytes: 1792
#include <iostream>
#include <sstream>
#include <stack>
#include <iomanip>
#include <numeric>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <queue>
#include <cmath>

#define BEGIN(x) x.begin()
#define END(x) x.end()
#define ALL(x) BEGIN(x), END(x)
#define PAIR make_pair
#define VEC(type) vector<type >
#define endl '\n'

#define FOR(i, A, B) for(auto i = (A);i != (B); i++)
#define FORD(i, A, B) for(auto i = (A);i != (B); i--)

#define READRANGE(begin, end) FOR(it, begin, end) cin >> *it
#define READVEC(V) READRANGE(BEGIN(V), END(V))

using namespace std;

typedef long long lint;
typedef pair<int, int> Pii;
typedef pair<int, lint> Pil;
typedef pair<lint, lint> Pll;
typedef pair<lint, int> Pli;

// ---- BEGIN LIBRARY CODE ----
// ---- END LIBRARY CODE ----
void io_init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
};

bool isSortedArray(VEC(int)& array)
{
    FOR(i, 1, array.size())
        if (array[i] <= array[i - 1])
            return false;
    return true;
}

int main(int argc, char **argv)
{
    io_init();

    // Actual program code starts here.
    int N;
    cin >> N;
    VEC(int) Perm(N);
    READVEC(Perm);
    if (isSortedArray(Perm)) {
        cout << "YES" << endl;
        return 0;
    }

    FOR(i, 0, N)
        FOR(j, 0, i) {
            swap(Perm[i], Perm[j]);
            if (isSortedArray(Perm)) {
                cout << "YES" << endl;
                return 0;
            }
            swap(Perm[i], Perm[j]);
        }
    
    cout << "NO" << endl;
    return 0;
};


Measured memory_bytes: 256
def main():
    n, m, x = map(int, input().split())
    ca = [list(map(int, input().split())) for _ in [0]*n]
    ans = 10**20
    for i in range(2**n):
        temp = [0]*m
        cost = 0
        for j in range(n):
            if i & 2**j:
                cost += ca[j][0]
                for k in range(m):
                    temp[k] += ca[j][k+1]
        for j in range(m):
            if temp[j] < x:
                break
        else:
            ans = min(ans, cost)
    if ans == 10**20:
        print(-1)
    else:
        print(ans)


main()

Measured memory_bytes: 68644
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <algorithm>
#include <functional>
#include <limits.h>
#include <bitset>

#include <tuple>
#include <unordered_map>

#define mp       make_pair
#define mt       make_tuple
#define pb       push_back
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const double EPS=1e-9;

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

const int MAX_N = 101000;//MAX???????????°
struct edge{
	int tar;//????????°
	int ecost;//???????????????
	edge(){}
	edge(int _tar, int _ecost){
		tar = _tar;
		ecost = _ecost;
	}
};
struct State{
	int pos;//?????¨??°
	int cost;//??????????????????pos?????§????????????
	State(){}
	State(int _pos, int _cost){
		pos = _pos;
		cost = _cost;
	}
	//cost?????§????????????????°?????????¨??????priority_queue???default???????????????
	bool operator < (const State &st) const {
		return cost > st.cost;
	}
};
vector<edge> edges[MAX_N];//??£??\?????????
int dist[MAX_N];//?§????s????????????dist[v]?????§??????????????????
void dijkstra(int s){
	priority_queue<State> que;
	fill(dist, dist + MAX_N, INF);
	dist[s] = 0;
	que.push(State(s, 0));
	while (!que.empty()){
		State p = que.top();
		que.pop();
		if (dist[p.pos] < p.cost)continue;
		for (int i = 0; i < edges[p.pos].size(); i++){
			edge e = edges[p.pos][i];
			if (dist[e.tar] > dist[p.pos] + e.ecost){
				dist[e.tar] = dist[p.pos] + e.ecost;
				que.push(State(e.tar, dist[e.tar]));
			}
		}
	}
	return ;
}
int N;
int main(){
	cin >> N;
	for (int i = 0; i < N; i++){
		int u,k;
		cin >> u >> k;
		for (int j = 0; j < k; j++){
			int v,c;
			cin >> v >> c;
			edges[u].push_back(edge(v, c));
			// edges[v].push_back(edge(u, c));
		}
	}
	dijkstra(0);
	for (int i = 0; i < N; i++){
		cout << i << " " << dist[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 8808
from queue import Queue
N = int(input())
q = Queue()
L = [3,5,7]
cnt = 0
for i in L:
    q.put(i)
while True:
    num = q.get()
    if num > N:
        break
    for i in L:
        q.put(num * 10 + i)
    num = str(num)
    if '3' in num and '5' in num and '7' in num:
        cnt += 1
print(cnt)

Measured memory_bytes: 6640
/*
Author: Arham_doshi
@quote "Code like there's no tommorow!"
 ***************************************   UNAUTHORISED COPYING OF CODE PROHIBITED   **********************************
*/
#include <bits/stdc++.h>

#define int         long long
#define double      long double
#define pb          push_back
#define pf          push_front
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define rall(a)     (a).rbegin(),(a).rend()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        998244353 
#define PI          3.141592653589
#define bs(v,n)     binary_search(all((v)),(n))
#define lb(v,n)     lower_bound(all((v)),(n))
#define ub(v,n)     upper_bound(all((v)),(n))
#define fo(i,l,u)   for(i=l;i<u;i++)
#define rfo(i,l,u)  for(i=l;i>=u;i--)
#define allfo(s)    for(auto it=(s).begin();it!=(s).end();it++)
#define _init(b)     memset(b,-1,sizeof(b))
#define _init0(b)     memset(b,0,sizeof(b))
#define MOD         1000000007



using namespace std;

int gcd(int a, int b) {  if (a == 0)  return b; return gcd(b % a, a); }  
bool mod(double a,double b) {return a/b - floor(a/b);}

int occurs(vi v,int n){
auto it=lb(v,n);auto it1=ub(v,n);int x=it1-it;return x;}

int logb(int base, int x) {
    return (log(x) / log(base));
}



signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int i,j,x,l,t,n,k;
    cin>>n>>k;
    vi v;
    fo(i,0,n){
        cin>>x;
        v.pb(x);
        //cout<<x<<" ";
    }
    
    //cout<<endl;
    sort(all(v));
    int dp[100005];
    
    fo(i,0,v[0]){
        dp[i]=0;
        
    }
    fo(i,v[0],k+1){
        dp[i]=0;
        //cout<<i<<endl;
        //bool p=false;
        fo(j,0,n){
            if(i-v[j]>=0){
                if(dp[i-v[j]]==0){
                    //if(i==5)
                   // cout<<i<<" "<<v[j]<<" "<<dp[i-v[j]]<<endl;
                    dp[i]=1;
                    break;
                }
            }
            else break;
        }
        
        // fo(j,0,k+1)cout<<dp[j]<<" ";
         //cout<<endl;
        
    }
    //fo(i,0,k+1)cout<<dp[i]<<" ";
    if(dp[k]==1)cout<<"First";
    else cout<<"Second";
    
    
    
    return 0;
}

Measured memory_bytes: 1024
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

#[allow(dead_code)]
struct Eratosthnes {
    n: usize,  // incluesive
    bprime: Vec<bool>,  // self.bprime[5] = true
    primes: Vec<usize>, // self.primes[2] = 5
}
#[allow(dead_code)]
impl Eratosthnes {
    fn new(n: usize) -> Eratosthnes {
        let mut bprime = vec![true; n + 1];
        let mut primes = vec![];
        primes.reserve(n / 10 + 1000);
        bprime[0] = false;
        bprime[1] = false;
        for i in 2..n+1 {
            if !bprime[i] { continue; }
            primes.push(i);
            if i * i > n { continue; }
            let mut j = i * i;
            while j <= n {
                bprime[j] = false;
                j += i;
            }
        }
        Eratosthnes {
            n: n,
            bprime: bprime,
            primes: primes,
        }
    }
}

fn main() {
    let n = 1e+5 as usize + 10;
    let era = Eratosthnes::new(n as usize);
    let mut sums = vec![0; n];
    for i in 1..n {
        if era.bprime[i] && era.bprime[(i + 1) / 2] { sums[i] += 1; }
        sums[i] += sums[i - 1];
    }
    let q: usize = read();
    for _ in 0..q {
        let l: usize = read();
        let r: usize = read();
        println!("{}", sums[r] - sums[l - 1]);
    }
}

Measured memory_bytes: 4732
import java.util.Scanner;

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

        int ans = Integer.compare(a, b);
        String out = ans == 1 ? "a > b" : "a < b";
        String aa = a == b ? "a == b" : out;
        System.out.println(aa);
    }
}

Measured memory_bytes: 26272
#include<iostream>
#include<vector>
#include<algorithm>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,s,e) for(int i=s;i<e;i++)

using namespace std;

int main(void) {
	int N, MINR = 1001, MINL = 1001;
	cin >> N;
	vector<int> a(N);
	vector<int> w(N);
	REP(i, N)cin >> a[i];
	REP(i, N)cin >> w[i];
	REP(i, N) {
		if (a[i] == 0 && w[i] < MINR)MINR = w[i];
		else if (a[i] == 1 && w[i] < MINL)MINL = w[i];
	}
	if (MINL == 1001 || MINR == 1001)cout << 0 << endl;
	else cout << MINL + MINR << endl;
	return 0;
}


Measured memory_bytes: 3104
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>

struct graph{
  int to;
  long long cost;
};

using P=std::pair<long long,int>;
constexpr long long inf=999999999999999;

int n,q,k;
std::vector<graph> data[100005];
long long d[100005];
int main(){
  std::cin>>n;
  for(int i=0;i<n-1;++i){
    int a,b;
    long long c;
    std::cin>>a>>b>>c;
    graph g;
    g.to=b-1;
    g.cost=c;
    data[a-1].push_back(g);
    g.to=a-1;
    data[b-1].push_back(g);
  }
  std::cin>>q>>k;
  --k;
  
  std::priority_queue<P,std::vector<P>,std::greater<P>> que;
  std::fill(d,d+n,inf);
  d[k]=0;
  que.emplace(0,k);
  
  while(!que.empty()){
    auto p=que.top();
    que.pop();
    auto v=p.second;
    if(d[v]<p.first)
      continue;
    for(size_t i=0,end=data[v].size();i<end;++i){
      auto e=data[v][i];
      if(d[e.to]>d[v]+e.cost){
        d[e.to]=d[v]+e.cost;
        que.emplace(d[e.to],e.to);
      }
    }
  }
  
  for(int i=0;i<q;++i){
    int x,y;
    std::cin>>x>>y;
    std::cout<<d[x-1]+d[y-1]<<std::endl;
  }
  
  return 0;
}


Measured memory_bytes: 11120
let solve w h xya_lst =
    let rec solve' xya_lst sx sy ex ey =
        match xya_lst with
        | [] -> (sx, sy, ex, ey)
        | x::xs ->
            let x, y, a = x
            let nsx, nsy, nex, ney =
                match a with
                | 1 -> max sx x, sy, ex, ey
                | 2 -> sx, sy, min ex x, ey
                | 3 -> sx, max sy y, ex, ey
                | _ -> sx, sy, ex, min ey y
            solve' xs nsx nsy nex ney
    let sx, sy, ex, ey = solve' xya_lst 0 0 w h
    let bw = if sx < ex then ex - sx else 0
    let bh = if sy < ey then ey - sy else 0
    bw * bh

let () =
    let w, h, n = stdin.ReadLine () |>
                  (fun str -> str.Split()) |>
                  Array.map int |>
                  fun arr -> (arr.[0], arr.[1], arr.[2])
    let xya_lst = seq {
        for i in 1..n do
            let x, y, a = stdin.ReadLine () |>
                          (fun str -> str.Split()) |>
                          Array.map int |>
                          fun arr -> (arr.[0], arr.[1], arr.[2])
            yield (x, y, a) } |> List.ofSeq

    solve w h xya_lst |> printfn "%d"


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

int main() {

	int n;
	cin >> n;

	int vec[n];
	for(int i=0; i<n; i++){
		cin >> vec[i];
	}

	sort(vec, vec+n);

	int ans=0;
	int tmp=-1;
	for(int i=0; i<n; i++){
		if(vec[n-1-i] != tmp){
			ans++;
			tmp = vec[n-1-i];
		}else{
			continue;
		}
	}
	cout << ans;

	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<tuple>
#include<queue>
#include<set>
#include<algorithm>
#include<string>
#include<math.h>

using namespace std;

int main(int argc, char* argv[]){
  long long int t,x;
  float ans = 0;
  cin >> t >> x;
  ans = (float)t / (float)(x);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
  int a,b,c;
  cin >> a >> b >> c;
  if(a!=b&&b!=c&&c!=a){
    cout << "No" << endl;
  }
  else if(a==b&&b==c&&c==a){
    cout << "No" << endl;
  }
  else{
    cout << "Yes" << endl;
  }
}


Measured memory_bytes: 256
l = [int(input()) for i in range(3)]
x = int(input())
count = 0
for i in range(l[0]+1):
  for j in range(l[1]+1):
    for k in range(l[2]+1):
      if 500*i+100*j+50*k == x:
        count += 1
print(count)
      


Measured memory_bytes: 3064
#include <stdio.h>
#include <math.h>
double sqr(double a)
{
    return a * a;
}
int main(void) 
{
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    double da = a;
    double db = b;
    double dc = c;
    double PI = acos(-1);

    double S, L, h;

    if (c <= 90)
    {
        h = cos((90 - dc) * PI / 180) * db;
        S = da * h / 2;

        double t1, t2; //a = t1 + t2 とする
        t1 = sqrt(sqr(db) - sqr(h));
        t2 = da - t1;
        L = da + db + sqrt(sqr(t2) + sqr(h));
    }
    else if (c > 90)
    {
        h = cos((90 - (180 - c)) * PI / 180) * db;
        S = da * h / 2;

        double t = sqrt(sqr(db) - sqr(h));
        L = da + db + sqrt(sqr(a + t) + sqr(h));
    }

    printf("%lf  %lf %lf\n", S, L, h);

    return 0;
}


Measured memory_bytes: 2800
import std.stdio;
import std.string;
import std.conv;
import std.typecons;
import std.algorithm;
import std.functional;
import std.bigint;
import std.numeric;
import std.array;
import std.math;
import std.range;
import std.container;

void main() {
    int maxN = 10^^6;
    int[] f, f_odd;
    for(int n=1; ;n++) {
        f ~= func(n);
        if (f.back > maxN) break;
        if (f.back%2!=0) f_odd~= f.back;
    }
    int INF = 1<<30;

    int[] ary = new int[maxN+1];
    ary[] = INF;
    ary[0] = 0;
    while(true) {
        foreach(int i; 0..maxN) {
            if (ary[i]<INF) {
                for(int n=0; n<f.length; n++) {
                    if (i+f[n]<=maxN) {
                        ary[i+f[n]] = min(ary[i+f[n]], ary[i]+1);
                    } else {
                        break;
                    }
                }
            }
        }
        if (ary[maxN] < INF) break;
    }
    int[] _ary = new int[maxN+1];
    _ary[] = INF;
    _ary[0] = 0;
    while(true) {
        foreach(int i; 0..maxN) {
            if (_ary[i]<INF) {
                for(int n=0; n<f_odd.length; n++) {
                    if (i+f_odd[n]<=maxN) {
                        _ary[i+f_odd[n]] = min(_ary[i+f_odd[n]], _ary[i]+1);
                    } else {
                        break;
                    }
                }
            }
        }
        if (_ary[maxN] < INF) break;
    }

    while(true) {
        int N = readln.chomp.to!int;
        if (N==0) break;
        writeln(ary[N], " ", _ary[N]);
    }
}
int func(int n) {
    return n*(n+1)*(n+2)/6;
}

Measured memory_bytes: 9960
n,k=map(int,input().split())
s=input()
ls=[c for c in s]
for i in range(n):
    if i==k-1 and s[i]=='A':
        ls[i]='a'
    elif i==k-1 and s[i]=='B':
        ls[i]='b'
    elif i==k-1 and s[i]=='C':
        ls[i]='c'
ss = ''.join(ls)
print(ss)

Measured memory_bytes: 3064
n,a,b = map(int,input().split())
mod = 10**9+7
def pow(n, p,mod=10**9+7): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def large_conbination(n,k,mod=10**9+7): #needs pow method. return nCk.
    res1 = 1
    for i in range(n,n-k,-1):
        res1*=i
        res1%=mod
    res2 = 1
    for i in range(1,k+1):
        res2*= pow(i,mod-2) #フェルマーの小定理を用いて分母を計算
        res2%=mod
    return res1*res2%mod

ans = pow(2,n) -1 

ans -= large_conbination(n,a)
ans -= large_conbination(n,b)

while ans<0:
    ans += mod
print(ans%mod)

Measured memory_bytes: 41964
#include <iostream>

using namespace std;

int main() {
	int A, B, C, D;
	
	cin >> A >> B >> C >> D;
	
	for (int turns = 0; ; turns++){
		
		//Mr.Takahashi's Attack
		C -= B;
		
		if (C <= 0) {
			cout << "Yes" << endl;
			break;
		}
		
		
		//Mr.Aoki's Attack
		A -= D;
		
		if (A <= 0) {
			cout << "No" << endl;
			break;
		}
	}
	
	return 0;
}

Measured memory_bytes: 3564
#include<stdio.h>

int main()
{
    int n,m,c,count=0;

    scanf("%d %d %d",&n,&m,&c);
    int a[n][m],b[m];

    for(int i=0;i<m;i++)
    {
        scanf("%d",&b[i]);
    }
    for(int i=0;i<n;i++)
    {

        for(int j=0;j<m;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }

    for(int i=0;i<n;i++)
    {
         int sum=0;
        for(int j=0;j<m;j++)
        {
            sum=sum+(a[i][j]*b[j]);
        }
        if(sum+c>0)
        {
            count++;
        }
    }
    printf("%d\n",count);
    return 0;
}


Measured memory_bytes: 1728
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define F first
#define S second
#define int long long
#define lint long long
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

using namespace std;
using namespace __gnu_pbds;
template <typename T> 
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N=2e5+5, MOD=1e9+7;
const lint INF=1e18;
lint _add(lint x, lint y) {
    lint ret=x+y;
    while(ret<0LL) ret+=MOD;
    return ret;
}
lint _mult(lint x, lint y) {
    x%=MOD; y%=MOD;
    lint ret=x*y;
    ret%=MOD;
    while(ret<0LL) ret+=MOD;
    return ret;
}
inline int modpow(lint base, int exp, int modulo) {
  base %= modulo;  lint result = 1;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % modulo;
    base = (base * base) % modulo; exp >>= 1;
  }
  return result;
}
int n, k, c, suff[N];
string s;
vi ans;
signed main()
{
    cin >> n >> k >> c;
    cin >> s;
    for(int i = n-1; i >= max(0LL, n-1-c); i--)
    {
        int curr;
        if(s[i]=='o') curr=1;
        suff[i] = max(curr, suff[i+1]);
    }
    for(int i = n-c-2; i >= 0; i--)
    {
        int curr = 1 + suff[i+c+1];
        if(s[i]=='x') curr = 0;
        suff[i] = max(suff[i+1], curr);
    }
    if(suff[0]>k)
    {
        return 0;
    }
    int curr = 0, jmps=0;
    while(jmps<k)
    {
        while(s[curr]=='x')
        {
            curr++;
        }
        if(curr==n-1)
        {
            ans.pb(curr+1);
        }
        else if(suff[curr+1]<suff[curr])
        {
            ans.pb(curr+1);
        }
        curr+=c+1;
        jmps++;
    }
    for(auto v: ans)
    {
        cout << v << endl;
    }
}

Measured memory_bytes: 4980
# AGC019B - Reverse and Compare
def main():
    S = input().rstrip()
    N = len(S)
    ans = N * (N - 1) // 2 + 1  # all possible patterns
    abc = "abcdefghijklmnopqrstuvwxyz"
    for a in abc:
        x = S.count(a)
        ans -= x * (x - 1) // 2  # exclude duplicates
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 3500
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define rep(i,n)for(ll i=0;i<n;i++)
#define ll long long
#define double long double
using namespace std;
ll n, h; ll a[114514], b[114514];
signed main() {
	cin >> n >> h;
	rep(i, n)cin >> a[i] >> b[i];
	sort(a, a + n);
	sort(b, b + n);
	reverse(b, b + n);
	ll cnt = 0, memo = 0;
	rep(i, n) {
		if (b[i] < a[n - 1])continue;
		cnt += b[i];
		memo++;
		if (cnt >= h) {
			cout << memo << endl;
			return 0;
		}
	}
	cout << ((h - cnt) - 1) / a[n - 1] + 1 + memo << endl;
	getchar(); getchar(); return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<vector>
#include<cmath>
#include<string>
#include<map>
#include<list>
#include<cctype>
using namespace std;

vector<int> split(string s,char c){
	vector<int> v;string tmp;
	for(int i=0;i<s.size();i++){
		if(s[i]==c){
			v.push_back(stoi(tmp));
			tmp ="";
		}
		else tmp += s[i];
	}
	if(tmp!="")v.push_back(stoi(tmp));
	return v;
}

int total[26];
int main(void){
	string s;
	while(cin >> s){
	for(int i=0;i<s.size();i++){
		if(isalpha(s[i]))
			total[tolower(s[i]) - 'a']++;
	}
	}
	for(int i=0;i<26;i++){
		printf("%c : %d\n",'a'+i,total[i]);
	}
	return 0;
}

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

using namespace std;

typedef long long ll;

const int Inf = 2e9;

int main()
{
    int X, Y, A, B, C;  cin >> X >> Y >> A >> B >> C;

    priority_queue <int, vector <int>, greater <int>> a;
    priority_queue <int, vector <int>, greater <int>> b;
    priority_queue <int> c;

    for(int i = 0; i < A; i++)
    {
        int x;
        scanf("%d", &x);
        a.push(x);
    }

    for(int i = 0; i < B; i++)
    {
        int x;
        scanf("%d", &x);
        b.push(x);
    }

    for(int i = 0; i < C; i++)
    {
        int x;
        scanf("%d", &x);
        c.push(x);
    }

    while(a.size() > X) a.pop();
    while(b.size() > Y) b.pop();

    while(!c.empty())
    {
        int Min1 = (a.empty() ? Inf : a.top());
        int Min2 = (b.empty() ? Inf : b.top());

        int Min = min(Min1, Min2);
        int Max = c.top();

        if(Min >= Max)  break;

        if(Min1 == Min)
        {
            a.pop();
            a.push(Max);
            c.pop();
        }

        else
        {
            b.pop();
            b.push(Max);
            c.pop();
        }
    }

    ll Ans = 0;

    while(!a.empty())   Ans += (ll) a.top(), a.pop();
    while(!b.empty())   Ans += (ll) b.top(), b.pop();

    cout << Ans << endl;
}


Measured memory_bytes: 1784
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

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

#define pb push_back
#define F first
#define S second
#define f(i,a,b)  for(int i = a; i < b; i++)
#define endl '\n'

using ll = long long;
using db = long double;
using ii = pair<int, int>;

const int N = 1e6 + 5, LG = 19, MOD = 1e9 + 7;
const int SQ =225;
const long double EPS = 1e-7;
int n, a[200005];
bool check(int c){
  map<int, int> mp;

  f(i,1,n){
    if(a[i] <= a[i - 1]){
      while(mp.size() && mp.rbegin()->first > a[i])
        mp.erase(--mp.end());
      if(c==1)return false;
      int idx = a[i];
      while(mp[idx] == c-1){
        mp.erase(idx);
        --idx;
      }
      if(!idx)
        return false;
      mp[idx]++;
    }
  }
  return true;
}
int32_t main(){
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif

  cin >> n;

  f(i,0,n)
    cin >> a[i];

  int lo = 1, hi = n;

  while(lo < hi){
    int md = lo + (hi-lo)/2;
    if(check(md))
      hi = md;
    else
      lo = md + 1;
  }

  cout << lo << endl;

  return 0;
}


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

L = []
R = []

for i in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
    
tmp = min(R) - max(L) + 1
if tmp >= 0:
    print(tmp)
else:
    print(0)

Measured memory_bytes: 11020
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
 
#define ll 				long long
#define int             long long int
#define setbits(x)      __builtin_popcountll(x)
#define mod             1000000007
#define modp            998244353
#define inf             (ll)1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define w(x)            int x; cin>>x; while(x--)
#define FIO           	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl 			'\n'
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;


void solve()
{
	int k; cin >> k;
	int x = 7, moves = 10000000, g = 0, cnt = 1;
	while(moves--)
	{
		x = x%k;
		if(x%k == 0)
		{
			// cout << k << endl;
			cout << cnt << endl;
			g = 1;
			break;
		}
		x = x*10+7;
		cnt++;
	}
	if(g == 0)
		cout << -1 << endl;
}
 
int32_t main()
{
	FIO
    // w(t)
    {
    	solve();
    }
    return 0;
}
	

	

Measured memory_bytes: 3644
def resolve():
    N, M, K = list(map(int, input().split()))
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    ans = 10 ** 10
    t = 0

    for i in range(M):
        t += B[i]
    j = M
    ans = 0
    for i in range(N+1):
        while j > 0 and t > K:
            j -= 1
            t -= B[j]
        
        if t > K:
            break
        
        ans = max(ans, i+j)
        
        if i == N:
            break
        t += A[i]
    
    print(ans)

resolve()

Measured memory_bytes: 40404
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); i++)
#define all(vec) vec.begin(), vec.end()
#define MOD 1000000007
#define int long long

signed main(){
    int n,m,x,y;cin>>n>>m>>x>>y;
    int xx=-MOD;
    rep(i,n){
        int c;cin>>c;
        xx=max(xx,c);
    }
    int yy=MOD;
    rep(i,m){
        int c;cin>>c;
        yy=min(yy,c);
    }
    if(max(x,xx)<min(y,yy))cout<<"No War"<<endl;
    else cout<<"War"<<endl;
}

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

int main(){
 int n; cin >>n;
double  ans;
 vector<double> v(n);
  rep(i,n)cin >>v[i];
  sort(v.begin(),v.end());
  if(n==2){
    ans=(v[0]+v[1])/2;
  }
  else{
    double sum=v[0]+v[1];
    for(int i=2;i<n;i++){
      sum+=v[i]*pow(2,i-1);
    }
    ans=sum/pow(2,n-1);
  }
   cout << ans << endl;
}


Measured memory_bytes: 384
// https://atcoder.jp/contests/dp/tasks/
#include <bits/stdc++.h>

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

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

int n;
int x = 0, y = 0, z = 0;
double dp[301][301][301];

double solve(int x, int y, int z) {
    double r = 0.0;
    double sum = 0.0;
    if (dp[x][y][z] >= 0) {
        // printf("* dp hit ");
        r = dp[x][y][z];
    } else {
        if (x >= 1) {
            sum += x * solve(x - 1, y, z);
        }
        if (y >= 1) {
            sum += y * solve(x + 1, y - 1, z);
        }
        if (z >= 1) {
            sum += z * solve(x, y + 1, z - 1);
        }
        r = (sum + n) / (x + y + z);
        dp[x][y][z] = r;
    }

    // printf("x:%d,y:%d,z:%d,r:%lf\n", x, y, z, r);
    return r;
}

int main() {
    // speedup cin
    ios::sync_with_stdio(false);

    cin >> n;
    int tmp;

    rep(i, 301) rep(j, 301) rep(k, 301) dp[i][j][k] = -1.0;
    dp[0][0][0] = 0.0;

    rep(i, n) {
        cin >> tmp;
        if (tmp == 1)
            x++;
        else if (tmp == 2)
            y++;
        else if (tmp == 3)
            z++;
    }
    // printf("initial x:%d, y:%d, z:%d\n", x, y, z);

    printf("%0.10f\n", solve(x, y, z));
    return 0;
}


Measured memory_bytes: 213376
parseInt(x::String) = parse(Int, x)
parseInt(x::SubString{String}) = parse(Int, x)
parseInt(x::Char) = parse(Int, x)
parseInt(x::Float64) = trunc(Int, x)
parseFloat(x::String) = parse(Float64, x)
parseFloat(x::Int) = trunc(Float64, x)
parseFloat(x::SubString{String}) = parse(Float64, x)
parseFloat(x::Char) = parse(Float64, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    println(length(collect(collect(Set(parseMap(split(readline())))))))
end
main()

Measured memory_bytes: 166992
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;

ll a[200010];

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

    ll b = a[0];
    rep(i, n-1){
        b ^= a[i+1];
    }
    rep(i, n) cout << (b^a[i]) << " ";
    cout << endl;

    return 0;
}


Measured memory_bytes: 5124
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int nest = scan.nextInt();
		int step = 0;
		int count = 0;
		for(int ind = 1;ind<=nest;ind++) {
			if(count == step) {
				step++;
				count = 0;
			}
			count++;
		}
		System.out.println(step);
	}
}


Measured memory_bytes: 23892
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

int minn(int a, int b){
	if(a < b)
		return a;
	return b;
}

int maxx(int a, int b){
	if(a > b)
		return a;
	return b;
}

int main(){
	int a, b, c, x, y;
	long long ans = 0;
	scanf("%d %d %d %d %d",&a, &b, &c, &x, &y);
	int maxy = maxx(x, y);
	int miny = minn(x, y);
	int chaxy = maxy - miny;
	if(2 * c < a + b){
		ans += miny * 2 * c;
		if(miny == x)
			ans += chaxy * b;
		else 
			ans += chaxy * a;
	}
	else{
		ans = x * a + y * b;
	}
	long long sum = 2 * c * maxy;
	if(sum < ans)
		printf("%lld\n",sum);
	else
		printf("%lld\n",ans);
return 0;
}

Measured memory_bytes: 256
from sys import stdin, setrecursionlimit


def main():
    input = stdin.readline
    n = int(input())
    a = list(input()[:-1])
    b = list(input()[:-1])
    c = list(input()[:-1])

    ans = 0
    for ai, bi, ci in zip(a, b, c):
        ans += len(list(set([ai, bi, ci]))) - 1

    print(ans)


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()


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

using namespace std;

constexpr size_t N {155555};

int n, m;
int color[N];

vector<int> g[N];

int h = 0;
long long f[N][2];
long long ed[N];

void dfs(int v, int prev = -1) {
//    f[v][0] = 1;
    for (int to : g[v]) {
        if (to == prev) continue;
        if (color[to]) continue;
        color[to] = (color[v] == 1 ? 2 : 1);
        dfs(to, v);
        ed[v] += f[v][0] * f[to][0];
        ed[v] += f[v][1] * f[to][1];
        ed[v] += max(f[to][0] - 1, 0ll);

        f[v][0] += f[to][1];
        f[v][1] += f[to][0];

        ed[v] += ed[to];
    }
    f[v][0]++;
}

int main() {

#ifdef Alex_PKZDL
    freopen(input_file, "r", stdin);
    freopen(output_file, "w", stdout);
#endif
    ios_base::sync_with_stdio(false);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y; cin >> x >> y; --x; --y;
        g[x].push_back(y);
        g[y].push_back(x);
    }

    color[0] = 1;
    dfs(0);

    for (int v = 0; v < n; ++v) {
        for (int u : g[v]) {
            if (color[v] == color[u]) {
                cout << 1LL * n * (n - 1) / 2LL - m << endl;
                return 0;
            }
        }
    }

    cout << ed[0] - (m - (n - 1)) << endl;
    return 0;
}


Measured memory_bytes: 12160
#include<iostream>
#include<algorithm>
using namespace std;
long long int cara(long long int x);
long long int a[200000];
int main() {

	//C
	int n, k;
	int i;
	cin >> n >> k;

	for (i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	long long int sum = 0;
	if (k >= n) {
		cout << 0 << endl;
		return 0;
	}
	for (i = 0; i <= n - k - 1; i++) {
		sum = sum + a[i];
	}
	cout << sum << endl;
	return 0;


	//E
	/*int h, n;
	int a[1000], b[1000];
	int i, j, k;
	cin >> h >> n;
	for (i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}

	//体力hに対して使用する最小の魔力を求めるDP
	int DP[10001];
	DP[0] = 0;
	int min;
	for (i = 1; i <= h; i++) {
		min = 100000000;
		for (j = 0; j < n; j++) {
			if (a[j] >= i) {
				if (min > b[j]) {
					min = b[j];
				}
			}
			else {
				if (DP[i - a[j]] + b[j] < min) {
					min = DP[i - a[j]] + b[j];
				}
			}
		}
		DP[i] = min;
	}
	cout << DP[h] << endl;
	return 0;
	*/

	//D


	/*long long int n;
	cin >> n;
	cout << cara(n) << endl;
	return 0;*/

}
long long int cara(long long int x) {

	int i = 0;
	if (x == 1) {
		return 1;
	}
	else {
		return 1  + 2 * cara((long long int)(x / 2));
	}

}

Measured memory_bytes: 5096
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <bitset>
#include <stack>
#include <deque>
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;

int main() {
    int K, A, B;
    scanf("%d %d %d", &K, &A, &B);
    if (B <= A + 2) return !printf("%d\n", K + 1);
    LL add = (B - A);
    K -= (A - 1);
    LL ans = A;
    ans += (K / 2) * add;
    ans += (K % 2);
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 256
n, m = map(int, input().split())
holl = set([int(input()) for _ in range(m)])
dp = [0]*(n+1)
dp[0] = 1
if 1 in holl:
  dp[1] = 0
else:
  dp[1] = 1
for i in range(2, n+1):
  if i in holl:
    dp[i] = 0
  else:
    dp[i] = dp[i-1] + dp[i-2]
    dp[i] %= 1000000007
print(dp[n])
 

Measured memory_bytes: 13192
#include "bits/stdc++.h"
using namespace std;
int main()
{
    long long n, k, total = 0;
    scanf("%lld %lld", &n, &k);
    for (long long i = k + 1; i <= n; ++i)
    {
        if (k)
        {
            total += n / i * (i - k) + max(0ll, n % i - k + 1);
        }
        else
        {
            total += n / i * (i - k) + max(0ll, n % i - k);
        }
    }
    printf("%lld\n", total);
}



Measured memory_bytes: 256