akhauriyash/Code-Regression huggingface dataset:
#if !defined(__clang__) && defined(__GNUC__)
#include <bits/stdc++.h>
#else
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <complex>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#endif //  !defined(__clang__) && defined(__GNUG__)
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>

using namespace std;


template<typename T>
class UnionFind {
public:
    UnionFind(size_t  size) : data_(size, -1) {}

    bool unite(T x, T y) {
        x = root(x);
        y = root(y);

        if (x != y) {
            if (data_[y] < data_[x]) {
                std::swap(x, y);
            }
            data_[x] += data_[y];
            data_[y] = x;
        }
        return x != y;
    }

    bool isSameGroup(T x, T y) {
        return root(x) == root(y);
    }

    T root(T x) {
        return data_[x] < 0 ? x : data_[x] = root(data_[x]);
    }

    // --
    size_t size(T x) {
        return -data_[root(x)];
    }

private:
    std::vector<T> data_;
};


int main()
{
    int64_t N, M;
    std::cin >> N >> M;

    std::vector<int64_t> P;

    for (size_t i = 0; i < N; ++i) {
        int t;
        std::cin >> t;
        t--;
        P.push_back(t);
    }

    UnionFind<int64_t> uf(N);

    for (size_t i = 0; i < M; ++i) {
        int64_t from, to;
        std::cin >> from >> to;
        from--;
        to--;
        uf.unite(from, to);
    }

    int64_t count = 0;

    for (int64_t i = 0; i < N; ++i) {
        if (uf.isSameGroup(i, P[i])) {
            count++;
        }
    }

    std::cout << count << std::endl;

    return 0;
}


Measured memory_bytes: 1908
#include <iostream>
#include <stdio.h>
using namespace std;
int main(void){
   int a,b,d,r;
       float f;
   cin>>a>>b;
   d=a/b;
   r=a%b;
   cout<<d<<" "<<r<<" ";
   printf("%.5lf\n",(double)a/b);
}


Measured memory_bytes: 3236
#include <bits/stdc++.h>
using namespace std;
string a,b;
int q,v,p,t;
unsigned long long dp[10000][10000];
int main(){
cin.tie(NULL);
cout.tie(NULL);
ios_base::sync_with_stdio(false);
getline(cin,a); getline(cin,b);
///cout<<f(a.size()-1,b.size()-1)<<'\n';
q=a.size(); v=b.size();
for(int n=1;n<=q;n++){
    for(int m=1;m<=v;m++){
        if(a[n-1]==b[m-1]) dp[n][m]=1+dp[n-1][m-1];
        else dp[n][m]=max(dp[n-1][m],dp[n][m-1]);
    }
}
p=q;
t=v;
string t="";
while(q>0&&v>0){
    if(a[q-1]==b[v-1]) {
        t=a[q-1]+t;
        q--;
        v--;
        continue;
    }
    if(dp[q-1][v]>=dp[q][v-1]){
        q--;
        continue;
    }
    v--;
}
cout<<t<<'\n';
///cout<<dp[p][t]<<'\n';
return 0;
}


Measured memory_bytes: 86188
#include <bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define dF(i,a,b) for(int i=a;i>=(b);--i)
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int mods = 998244353;
const int maxn = 1e6+10 ;
ll n,a,b;

int main(){
    cin>>n>>a>>b;
    if(a>b) swap(a,b);
    ll del = b-a;
    ll ans = 0;
    if(del==0){
        cout<<ans<<endl;
        return 0;
    }
    if(del%2==0){
        ans = del/2;
        cout<<ans<<endl;
        return 0;
    }
    ans = (del-1)/2 + min(abs(n-b),abs(a-1))+1;
    cout<<ans<<endl;
}


Measured memory_bytes: 256
<?php
	fscanf(STDIN,'%d',$n);
	
    
    for($i = 0; $i < $n; $i++){
		fscanf(STDIN,'%d %d %d',$r[0],$r[1],$r[2]);
		sort($r);
		
		if(pow($r[0],2) + pow($r[1],2) === pow($r[2],2)){
			echo "YES\n";
		}
		else{
			echo "NO\n";
		}
		
	}

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

using namespace std;

int a, b;

inline int read();

int main() {
	scanf("%d%d", &a, &b);
	int c = a + b;
	int d = a - b;
	int e = a * b;
	int ans = max(c, max(d, e));
	printf("%d\n", ans);
	return 0;
}

inline int read() {
	int x = 0, t = 1; char ch = getchar();
	while(ch < '0' || ch > '9') (ch == '-') && (t = -1), ch = getchar();
	while(ch >= '0' && ch <= '9') x = x * 10 + (ch ^ 48), ch = getchar();
	return x * t;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
mt19937 mrand(random_device{}()); 
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int M=1000000,N=1010000;

int n,cnt[N],x;
ll f[N],ans;
int main() {
	scanf("%d",&n);
	rep(i,0,n) scanf("%d",&x),cnt[x]++;
	rep(i,1,M+1) f[i]=powmod(i,mod-2);
	rep(i,1,M+1) {
		f[i]%=mod; if (f[i]<0) f[i]+=mod;
		for (int j=i+i;j<=M;j+=i) {
			f[j]=f[j]-f[i];
		}
	}
	for (int i=1;i<=M;i++) {
		ll pc=0;
		for (int j=i;j<=M;j+=i) pc=(pc+(ll)cnt[j]*j)%mod;
		ans=(ans+pc*pc%mod*f[i])%mod;
	}
	rep(i,1,M+1) ans=(ans-(ll)cnt[i]*i)%mod;
	ans=ans*(mod+1)/2%mod;
	if (ans<0) ans+=mod;
	printf("%lld\n",ans);
}


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

int main(){
    
    long long K,A,B;
    cin >> K >> A >> B;
    if(K < A)cout << K << endl;
    else if(B-A<=2)cout<< K + 1 <<endl;
    else cout << A +  ((K-A+1)/2)*(B-A)+(K-A+1)%2 <<endl;
    
}

    
    



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
int main()
{
  int x,y,z;
  cin >> x >> y >> z;

  cout << max({x,y,z}) - min({x,y,z}) << endl;
  return 0;
}


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

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int n, l; cin >> n >> l;
  vector<string> s(n);
  for(int i=0;i<n;++i) {
    cin >> s[i];
  }
  sort(s.begin(), s.end());
  for(int i=0;i<n;++i) {
    cout << s[i];
  }
  cout << endl;
}


Measured memory_bytes: 256
#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 vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#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 pb push_back
#define pp 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;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
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; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
  
  	string s;
  	cin >> s;
  	int l = s.size();
  	rep(i,l) cout <<"x";
  	cout <<endl;

  	return 0;
}

Measured memory_bytes: 256
DEBUG = False
K, N = map(int, input().split())
A = list(map(int, input().split()))
distance = [A[i+1]-A[i] for i in range(len(A)-1)]+[K-A[-1]+A[0]]

if DEBUG:
    print("K = %d  N = %d"%(K,N))
    print("A = \n"+str(A))
    print("Distance = \n"+str(distance))
print(sum(distance)-distance[distance.index(max(distance))])

Measured memory_bytes: 26444
#include <bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c;
	cin>>a>>b;
	c=a+b;
	if(a%3==0||b%3==0||c%3==0)
	cout<<"Possible"<<endl;
	else cout<<"Impossible"<<endl;
	return 0;
}

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

int main(){
    int n;
    cin>>n;
    int M[3]={};
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        M[a%3]++;
    }

    int ans=min(M[1],M[2])*2;
    int diff=max(M[1],M[2])-min(M[1],M[2]);
    if(diff>3) ans+=3;
    else ans+=diff;
    if(ans){
        ans+=M[0];
    }else{
        if(M[0]) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3096
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
const int maxn=1e5+5;
vector<int> nei[maxn];
int deg[maxn],que[maxn],maxx[maxn];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        nei[u].push_back(v);
        deg[v]++;
    }
    int head=1,tail=1;
    for(int i=1;i<=n;i++)
        if(deg[i]==0)
            que[tail++]=i;
    while(head<tail)
    {
        int cur=que[head++];
        for(int i=0;i<(int)nei[cur].size();i++)
        {
            int next=nei[cur][i];
            deg[next]--;
            if(deg[next]==0)
                que[tail++]=next;
        }
    }
    for(int i=1;i<=n;i++)
    {
        int cur=que[i];
        for(int i=0;i<(int)nei[cur].size();i++)
        {
            int next=nei[cur][i];
            maxx[next]=max(maxx[next],maxx[cur]+1);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,maxx[i]);
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 10364
public class Main{
  public void run(java.io.InputStream in, java.io.PrintStream out){
    java.util.Scanner sc = new java.util.Scanner(in);
    int n, i, j, xk, yk, xs, ys;
    int[] x, y;

    n = sc.nextInt();
    x = new int[4]; y = new int[4];
    for(i = 0;i < n;i++){
      for(j = 0;j < 3;j++){
        x[j] = sc.nextInt(); y[j] = sc.nextInt();
      }
      x[3] = x[0]; y[3] = y[0];
      xk = sc.nextInt(); yk = sc.nextInt();
      xs = sc.nextInt(); ys = sc.nextInt();
      if(solve(x, y, xk, yk) + solve(x, y, xs, ys) == 2)out.println("OK");
      else out.println("NG");
    }

    sc.close();
  }
  public static void main(String[] args){
    (new Main()).run(System.in, System.out);
  }

  private static int solve(int[] x, int[] y, int x0, int y0){
    int i, j, countr, n;
    int ax, ay, bx, by, tmp;

    countr = 0; n = 3;

    for(j = 0;j < n;j++){
      if((x[j] - x0) * (y[j + 1] - y0) - (y[j] - y0) * (x[j + 1] - x0) == 0){
        if((x[j] - x0) * (x[j + 1] - x0) <= 0
        && (y[j] - y0) * (y[j + 1] - y0) <= 0)break;
        else if(x0 < x[j + 1] && x0 < x[j] && y0 == y[j] && y0 == y[j + 1])
          if((y[(j - 1 + n) % n] - y0) * (y[(j + 2) % n] - y0) > 0)countr++;
      }

      if((y[j] - y0) * (y[j + 1] - y0) <= 0 && y0 != y[j + 1]){
        ax = x[j]; ay = y[j];
        bx = x[j + 1]; by = y[j + 1];

        if(ay > by){
          tmp = ay; ay = by; by = tmp;
          tmp = ax; ax = bx; bx = tmp;
        }
        if((ax - x0) * (by - y0) - (bx - x0) * (ay - y0) > 0){
          countr++;
          if((y[(j - 1 + n) % n] - y0) * (y[j + 1] - y0) > 0 && y[j] == y0){
            countr++;
          }
        }
      }
    }

    if(j < n)return 1;
    else{
      if(countr % 2 == 1)return 2;
      else return 0;
    }
  }
}

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

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

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

    if (n % sum(n) == 0)
    {
        cout << "Yes\n";
    }
    else
    {
        cout << "No\n";
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<map>
#include<cstdio>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define P pair<int,int>
#define ll __int64
int n,m;
int l[210000],r[210000],d[210000];
vector<P>G[210000];//to,cost
int dist[210000];
bool used[210000];
void nuri(int now){//頂点番号nowを座標0として、距離を確定させていく
	dist[now]=0;
	used[now]=1;
	queue<int>bfs;
	while(!bfs.empty())bfs.pop();
	bfs.push(now);
	
	while(!bfs.empty()){
		int z=bfs.front();
		bfs.pop();
		//cout<<z<<endl;
		for(int i=0;i<G[z].size();i++){
			int next=G[z][i].first;
			if(!used[next]){
			used[next]=1;
			dist[next]=dist[z]+G[z][i].second;
			bfs.push(next);
			}
		}
	}

}
int main(){
cin>>n>>m;
rep(i,m){

cin>>l[i]>>r[i]>>d[i];
l[i]--;
r[i]--;
G[l[i]].push_back(mp(r[i],d[i]));
G[r[i]].push_back(mp(l[i],-d[i]));
}



rep(i,n){
	if(!used[i])nuri(i);
}

/*rep(i,n){
	cout<<i<":";
	rep(j,G[j].size())cout<<G[i][j].first<<","<<G[i][j].second<<" ";
	cout<<endl;
}*/


//rep(i,n)cout<<dist[i]<<" ";cout<<endl;

bool ok=1;
rep(i,m){
	if(dist[r[i]]-dist[l[i]]!=d[i])ok=0;
}
if(ok)cout<<"Yes"<<endl;
else cout<<"No"<<endl;


	return 0;
}

Measured memory_bytes: 14464
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << endl
#define debugArray(x, n)                           \
  for (long long hoge = 0; (hoge) < (n); ++(hoge)) \
  cerr << #x << "[" << hoge << "]: " << x[hoge] << endl
using namespace std;

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int L, R, d;
  cin >> L >> R >> d;
  cout << R / d - (L - 1) / d << endl;
  return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using ll=long long;

#define fi first
#define se second
#define pb push_back
#define rep(i,n) for(int i=0; i<(int)(n); i++)

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 (b<a) { a=b; return 1; } return 0; }

// int vvi[200010][200010];
//int n;
bool visited[200010];

void dfs(vector<vector<int>>& vvi, vector<ll>& vi, ll p, int i) {
	//cout << "p: " << p <<  " i: " << i << endl;
	vi[i] += p;
	visited[i] = true;
	/*for(auto k : vvi[i]) {
		cout << k << " ";
	}
	cout << endl;*/
	for(auto j : vvi[i]) {
		if(!visited[j]) dfs(vvi, vi, vi[i], j);
	}
}

int main() {
	int n,q;
	cin >> n >> q;
	vector<vector<int>> vvi(n, vector<int>());
	int a,b;
	rep(i,n-1) {
		cin >> a >> b;
		a--;b--;
		vvi[a].pb(b);
		vvi[b].pb(a);
	}
	rep(i,n) visited[i] = false;
	vector<ll> vi(n, 0);
	int p,x;
	rep(i,q) {
		cin >> p >> x;
		vi[p-1] += x;
	}
	//cout << "debug" << endl;
	rep(i,n) {
		//cout << vi[i] << endl;
	}
	//cout << "debug" << endl;
	dfs(vvi, vi, 0, 0);
	rep(i,n) {
		cout << vi[i];
		if(i == n-1) cout << endl;
		else cout << " ";
	}

	return 0;
}


Measured memory_bytes: 24448
#include <iostream>

using namespace std;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, x;
	cin >> n >> x;
	
	int Di = 0;
	int tot = 1;
	for(int i=0;i<n;i++)
	{
		int Li;
		cin >> Li;
		Di = Di + Li;
		if(Di <= x)
			tot++;
	}
	
	cout << tot << endl;
	
	return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int x = sc.nextInt();
		int[] nums = new int[n];
		int min = Integer.MAX_VALUE;
		for(int i=0; i<n; i++) {
			nums[i] = sc.nextInt();
			min = Math.min(min, Math.abs(x-nums[i]));
			
		}
		Arrays.sort(nums);
		
		for(int i=0; i<n; i++) {
			if(Math.abs(x-nums[i])%min == 0) {
				continue;
			}else {
				min--;
				i = 0;
			}
		}
		System.out.println(min);
	}
}


Measured memory_bytes: 47660
#include <iostream>
#include <set>
#include <cctype>
#include <vector>
#include <cstring>

using namespace std;

string S;

bool is_op(char c)
{
    return (c == '+' || c == '-' || c == '*' || c == '/');
}

bool is_num(int L, int R)
{
    for (int i = L; i <= R; i++) {
        if (!isdigit(S[i])) return 0;
    }
    return 1;
}

int num(int L, int R)
{
    int res = 0;
    for (int i = L; i <= R; i++) {
        res *= 10;
        res += (S[i] - '0');
    }
    return res;
}

int near(int L, int R)
{
    int p = 0;
    for (int i = L; i <= R; i++) {
        if (S[i] == '(') p++;
        if (S[i] == ')') p--;
        if (p == 0) return i;
    }
    return -1;
}

set<int> expr(int L, int R)
{
    set<int> res;
    
    if (is_num(L, R)) return {num(L, R)};
    
    int nR = near(L, R);
    if (nR == R && S[L] == '(' && S[R] == ')') {
        return expr(L + 1, R - 1);
    }
    
    for (int i = L; i <= R - 1; i++) {
        char c = S[i];
        
        if (!is_op(c)) continue;        
        
        auto l = expr(L, i - 1);
        auto r = expr(i + 1, R);
        
        for (int lv : l) {
            for (int rv : r) {
                switch (c) {
                    case '+':
                        res.insert(lv + rv);
                        break;
                    case '-':
                        res.insert(lv - rv);
                        break;
                    case '*':
                        res.insert(lv * rv);
                        break;
                    case '/':
                        if (rv != 0) {
                            res.insert(lv / rv);                            
                        }                            
                        break;
                }
            }
        }
    } 
    return res;
}

void solve()
{
    int N = S.size();
    cout << expr(0, N - 1).size() << endl;
}

int main()
{
    while (cin >> S, S != "#") {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3184
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll h;
	cin >> h;
	ll n = log(h) / log(2) + 1;
	ll ans = (1LL << n) - 1;
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>
#include <random>
#include <iomanip>

using namespace std;
typedef long long unsigned int ll;
typedef pair<int, int> P;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

#define fillInt(xs, x)        \
  for (int i = 0; i < (x); i++) \
    scanf("%d", &xs[i]);
#define fillLong(xs, x)       \
  for (int i = 0; i < (x); i++) \
    scanf("%ld", &xs[i]);
#define fillString(xs, x)       \
  for (int i = 0; i < (x); i++) \
    cin >> xs[i];
#define sortv(xs) sort(xs.begin(), xs.end())
#define sortvdi(xs) sort(xs.begin(), xs.end(), std::greater<long>())
#define lbv(xs, x) lower_bound(xs.begin(), xs.end(), x) - xs.begin()
#define ubv(xs, x) upper_bound(xs.begin(), xs.end(), x) - xs.begin()
#define bs(xs, x) binary_search(xs.begin(), xs.end(), x)

#define rep(i,n) for(auto i=0; i<(n); i++)
#define isValidPoint(x, y, mx, my) x >= 0 && x  < mx && y >= 0 && y < my

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

const int MOD = 1000000007;

struct Pony
{
    long a, b;
 
    Pony(long a_, long b_)
    {
        a = a_;
        b = b_;
    }
 
    bool operator<(const Pony &another) const
    {
        return b < another.b;
    };
};

int fac(int k){
    int sum = 0;
    for (int i = 1; i <= k; ++i)
    {
        sum += i;
    }
    return sum;
}

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

  long n, k;

  cin >> n >> k;

  long sm = 0;
  vector<long> v(n);
  fillLong(v, n);

  rep(i, n) {
    sm += v[i];
  }

  long res = 1;

  vector<long> yakusu;

  for(long i = 1; i <= sqrt(sm); i++) {
    if(!(sm % i)) {
      yakusu.push_back(i);
      yakusu.push_back(sm/i);
    }
  }

  sortv(yakusu);

  rep(i, yakusu.size()) {
    long y = yakusu[i];
    long cnt = 0;
    vector<long> v2(n);
    rep(j, n) {
      v2[j] = (v[j] + y) % y;
    }
    sortv(v2);
    long left = 0;
    long right = n-1;
    while(left < right) {
      long dff = v2[left];
      cnt += dff;
      left++;
      while(dff) {
        long tmp = y-v2[right];
        v2[right] = min(y, v2[right] + dff);
        dff -= min(dff, tmp);
        if (v2[right] == y) right--;
      }
    }
    if (cnt <= k) res = y;
  }
  
  cout << res << endl;
}


Measured memory_bytes: 256
using System;
using System.Text.RegularExpressions;
using System.Text;
using System.Linq;


namespace aizu
{
	public class EntryPoint
	{
		public static int[] Split(string line)
		{
			return Regex.Split(line, " ").Select(x => int.Parse(x)).ToArray();
		}
		public static void Main()
		{
			var line = Console.ReadLine();
			
			var v = Split(line);
			
			if (v[0] < v[1] && v[1] < v[2])
			{
				Console.WriteLine("Yes");
			}
			else
			{
				Console.WriteLine("No");
			}
			
			
		}
	}


}

Measured memory_bytes: 7132
N = int(input())
A = list(map(int, input().split()))

dic = dict()
for a in A:
    if a in dic:
        dic[a] += 1
    else:
        dic[a] = 1

base = 0

for v in dic.values():
    base += v * (v - 1) // 2

for i in range(N):
    ord = dic[A[i]]
    print(base - (ord * (ord - 1) // 2) + ((ord - 1) * (ord - 2) // 2))

Measured memory_bytes: 86348
#include <bits/stdc++.h>
#define INF 1e10;
using namespace std;

typedef long long ll;

int main(void){
    int N,W;
    cin>>N>>W;
    
    ll w[N+1],v[N+1];
    ll sum=0;
    for(int i=0;i<N;i++){
        cin>>w[i+1]>>v[i+1];
        sum+=v[i+1];
    }
    
    ll dp[N+10][sum+100];
    for(int i=0;i<=N;i++){
        for(int j=0;j<=sum;j++){
            dp[i][j]=INF;
        }
    }
    
    dp[0][0]=0;
    for(int i=1;i<=N;i++){
        for(int j=0;j<=sum;j++){
            if(j<v[i])dp[i][j]=dp[i-1][j];
            dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
        }
    }
    
    ll res;
    for(int j=0;j<=sum;j++){
        if(dp[N][j]<=W)res=j;
    }
    
    cout<<res<<endl;

}


Measured memory_bytes: 79744
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define mod 1000000007
#define endl "\n"
#define pb push_back
#define mp make_pair
int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,l,max,min;
	cin>>n>>l;
	max=l+n-1;
	min=l;
	if(min>=0)
	{
		ll ans=0;
		for(ll i=1;i<n;i++)
		{
			ans+=min+i;
		}
		cout<<ans;
	}
	else if(max<=0)
	{
		ll ans=0;
		for(ll i=0;i<n-1;i++)
		{
			ans+=min+i;
		}
		cout<<ans;
	}
	else
	{
		ll ans=0;
		for(ll i=0;i<n;i++)
		{
			ans+=min+i;
		}
		cout<<ans;
	}
	return 0;
}

Measured memory_bytes: 256
import fractions
from functools import reduce

def lcm_2val(x, y):
  return (x * y) // fractions.gcd(x, y)

def lcm(numbers):
  return reduce(lcm_2val, numbers, 1)

N = int(input())
T = [int(input()) for _ in range(N)]

print(lcm(T))

Measured memory_bytes: 5688
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ii pair<int, int>
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define vvi vector<vector<int>>
#define vvii vector<vector<ii>>
#define vvll vector<vector<ll>>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define uni(v) v.erase(unique(v.begin(), v.end()), v.end())
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) (ll) a / __gcd(a, b) * b
#define what_is(x) cerr << #x << " is " << x << endl;

using namespace std;

void write();
template <typename T, typename... Args>
void write(T x, Args... args);

void solve() {
    int n, k;
    cin >> k >> n;
    vi a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    int res = k;
    for (int i = 0; i < n; ++i) {
        res = min(res, k - (a[(i + 1) % n] - a[i] + k) % k);
    }
    write(res);
}
int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    // freopen("in", "r", stdin);

    int t = 1;
    // cin >> t;
    while (t--) solve();

    return 0;
}
template <typename T, typename... Args>
void write(T x, Args... args) {
    cout << x;
    if (sizeof...(args)) {
        cout << ' ';
        write(args...);
    } else
        cout << '\n';
}

Measured memory_bytes: 1024
# -*- coding:utf-8 -*-
from itertools import product

def solve():
    N, M = list(map(int, input().split()))
    K, S = [], []
    for _ in range(M):
        _in = list(map(int, input().split()))
        K.append(_in[0])
        S.append(_in[1:])
    P = list(map(int, input().split()))

    all_stats = product((0,1), repeat=N)
    ans = 0
    for stat in all_stats:
        is_ok = True
        for switch_i, switch in enumerate(S):
            on_num = 0
            for i in range(len(switch)):
                if stat[switch[i]-1] == 1:
                    on_num += 1
            if on_num%2 != P[switch_i]:
                is_ok = False
                break
        if is_ok:
            ans += 1
    print(ans)

if __name__ == "__main__":
    solve()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 200000 + 10;

int n;
int a[MAXN];
int32_t main() {
    ios_base::sync_with_stdio(0);
    int q, h, s, d;
    cin >> q >> h >> s >> d;
    int n;
    cin >> n;

    int dd = min(d, min(2*s, min(4*h, 8*q)));
    int ss = min(s, min(2*h, 4*q));
    int hh = min(h, 2*q);
    int qq = q;

    int p = (n/2) * 2;

    int res = dd * (p/2);
    if (n%2 == 1) res += ss;

    cout << res << "\n";

    return 0;
}


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

template<typename T>
istream &operator >> (istream &istr, vector<T> &v){
    for(T &x: v) istr >> x;
    return istr;
}

template<typename T, typename U>
istream &operator >> (istream &istr, pair<T,U> &p){
    istr >> p.first >> p.second;
    return istr;
}

template<typename T>
ostream &operator << (ostream &ostr, vector<T> &v){
    if(!v.empty()){
        ostr << v.front();
        for(auto itr = ++v.begin(); itr != v.end(); itr++)
            // ostr << *itr;
            ostr << " " << *itr;
    }
    return ostr;
}

template<typename T, typename U>
ostream &operator << (ostream &ostr, pair<T,U> &p){
    // ostr << p.first << p.second;
    // ostr << p.first << ", " << p.second;
    ostr << "(" << p.first << ", " << p.second << ")";
    return ostr;
}

template<typename T>
ostream &operator << (ostream &ostr, vector<vector<T>> &vv){
    if(!vv.empty()){
        ostr << vv.front();
        for(auto itr = ++vv.begin(); itr != vv.end(); itr++)
            ostr << endl << *itr;
    }
    return ostr;
}

template<typename T, typename U>
ostream &operator << (ostream &ostr, vector<pair<T,U>> &vp){
    if(!vp.empty()){
        ostr << vp.front();
        for(auto itr = ++vp.begin(); itr != vp.end(); itr++)
            ostr << endl << *itr;
    }
    return ostr;
}

typedef long long ll;
typedef vector<ll> vll;
typedef vector<char> vc;
typedef vector<double> vd;
// vll v(n); v[i]=x;
typedef vector<vll> vvll;
typedef vector<vc> vvc;
typedef vector<vd> vvd;
// vvll v(m,vll(n)); v[i][j]=x;
typedef pair<ll,ll> pll;
typedef pair<double,double> pd;
typedef vector<pll> vpll;
typedef vector<pd> vpd;
// vpll v(n); v[i]=make_pair(x,y); v[i].first/second;
// v.front() : v[0]
// v.back()  : v[v.size()-1]

#define PI 3.1415926535897932
#define EPS 1e-12
#define INF ((ll)1e+12)
#define REP(i,n) for(ll i=0; i<(n); i++)
#define RREP(i,n) for(ll i=(n)-1; i>=0; i--)
#define FOR(i,a,b) for(ll i=(a); i<=(b); i++)
#define FORR(i,a,b) for(ll i=(b); i>=(a); i--)
#define fix(x) cout << fixed << setprecision(x)
#define dump(x) cout << #x << " = " << (x) << endl
#define all(x) (x).begin(),(x).end()

template<typename T> T sum(vector<T> &v){return accumulate(all(v), (T)0);}
template<typename T> inline void sort(vector<T> &v){sort(all(v));}
template<typename T> inline void rsort(vector<T> &v){sort(all(v), greater<T>());}
template<typename T> inline void chmin(T &a, T b){if(a>b) a=b;}
template<typename T> inline void chmax(T &a, T b){if(a<b) a=b;}

// 距離
template<typename T, typename U>
double dist_2d(pair<T,T> p1, pair<U,U> p2){
    double xd = (double)p1.first  - (double)p2.first;
    double yd = (double)p1.second - (double)p2.second;
    return sqrt(xd*xd+yd*yd);
}

int main(){
    fix(10);
    ll a, b, h, m;
    cin >> a >> b >> h >> m;
    double ah = (h+m/60.0)*30.0*PI/180;
    double mh = m*6.0*PI/180;

    pd ph = {a*cos(ah), a*sin(ah)};
    pd pm = {b*cos(mh), b*sin(mh)};
    cout << dist_2d(ph, pm) << endl;
    return 0;
}


Measured memory_bytes: 4104
h, w = map(int, input().split())
ls = [input().rstrip() for _ in range(h)]
ds = [[float('inf') for _ in range(w)] for _ in range(h)]
ds[0][0] = 1

dxdy = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def bfs(q):
    while q:
        x, y = q.pop()
        for i in range(4):
            dx, dy = dxdy[i]
            nx = x + dx
            ny = y + dy
            if 0 <= nx < w and 0 <= ny < h and ls[ny][nx] == '.':
                if ds[ny][nx] > ds[y][x] + 1:
                    ds[ny][nx] = ds[y][x] + 1
                    q.append([nx, ny])


q = [[0, 0]]
bfs(q)
d = ds[h - 1][w - 1]
if d < float('inf'):
    s = sum([l.count('.') for l in ls])
    print(s - d)
else:
    print(-1)

Measured memory_bytes: 3188
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;

int main(){
    int N,K;cin>>N>>K;
    int ans=K;
    REP(i,N-1) ans*=K-1;
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
const int MAXN=17;
int n,a[MAXN][MAXN];
long long f[1<<MAXN],g[1<<MAXN];

inline long long max(long long x,long long y){
	return x>y?x:y;
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			scanf("%d",&a[i][j]);
	for(int msk=0;msk<(1<<n);msk++){
		for(int i=0;i<n;i++)
			if((msk>>i)&1)
				for(int j=i;j<n;j++)
					if((msk>>j)&1)
						f[msk]+=a[i][j];
		g[msk]=f[msk];
	}
	for(int msk=0;msk<(1<<n);msk++)
		for(int p=(msk-1)&msk;p;p=(p-1)&msk)
			g[msk]=max(g[msk],g[msk^p]+f[p]);
	printf("%lld\n",g[(1<<n)-1]);
	return 0;
}

Measured memory_bytes: 1280
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<string>
#include<cassert>
using namespace std;
#define N 4
#define N2 16
#define LIMIT 100
 
static const int dx[4] = {0, -1, 0, 1};
static const int dy[4] = {1, 0, -1, 0};
static const char dir[4] = {'r', 'u', 'l', 'd'};
int MDT[N2][N2];
 
struct Puzzle {int f[N2], space, MD;};
 
Puzzle state;
int limit;
int path[LIMIT];
 
int getAllMD(Puzzle pz){
    int sum = 0;
    for(int i=0;i<N2;i++){
        if(pz.f[i] == N2) continue;
        sum += MDT[i][pz.f[i]-1];
    }
    return sum;
}
 
bool isSolved(){
    for(int i=0;i<N2;i++) if(state.f[i] != i+1) return false;
    return true;
}
 
bool dfs(int depth, int prev){
    if(state.MD == 0) return true;
    if(depth + state.MD > limit) return false;
 
    int sx = state.space / N;
    int sy = state.space % N;
    Puzzle tmp;
 
    for(int r=0;r<4;r++){
        int tx = sx + dx[r];
        int ty = sy + dy[r];
        if(tx < 0 || ty < 0 || tx >= N || ty >= N) continue;
        if(max(prev,r) - min(prev,r) == 2) continue;
        tmp = state;
        state.MD -= MDT[tx * N + ty][state.f[tx * N + ty] - 1];
        state.MD += MDT[sx * N + sy][state.f[tx * N + ty] - 1];
        swap(state.f[tx * N + ty], state.f[sx * N + sy]);
        state.space = tx * N + ty;
        if(dfs(depth + 1, r)) {path[depth] = r; return true;}
        state = tmp;
    }
 
    return false;
}
 
string iterative_deepening(Puzzle in){
     in.MD = getAllMD(in);
 
     for( limit = in.MD; limit <= LIMIT; limit++){
         state = in;
         if(dfs(0,-100)){
             string ans = "";
             for(int i=0;i<limit;i++) ans += dir[path[i]];
             return ans;
         }
     }
 
     return "unsolved";
}
 
int main(){
    for(int i=0;i<N2;i++)
        for(int j=0;j<N2;j++)
            MDT[i][j] = abs(i / N - j / N) + abs(i % N - j % N);
    Puzzle in;
 
    for(int i=0;i<N2;i++){
        cin >> in.f[i];
        if(in.f[i] == 0){
            in.f[i] = N2;
            in.space = i;
        }
    }
    string ans = iterative_deepening(in);
    cout << ans.size() << endl;
 
    return 0;
}


Measured memory_bytes: 3220
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int a[4][11]={0},b[4][11]={0},c[4][11]={0},d[4][11]={0};
  int n,l,f,r,v;
  cin>>n;
  while(n--)
  {
    cin>>l>>f>>r>>v;
    if(l==1)
    {
      a[f][r]+=v;
    }
    else if(l==2)
    {
      b[f][r]+=v;
    }
    else if(l==3)
    {
      c[f][r]+=v;
    }
    else if(l==4)
    {
      d[f][r]+=v;
    }
  }
  for(int i=1;i<=3;i++)
  {
    for(int j=1;j<=10;j++)
    {
      cout<<" "<<a[i][j];
    }
    cout<<endl;
  }
  cout<<"####################"<<endl;
  for(int i=1;i<=3;i++)
  {
    for(int j=1;j<=10;j++)
    {
      cout<<" "<<b[i][j];
    }
    cout<<endl;
  }
  cout<<"####################"<<endl;
  for(int i=1;i<=3;i++)
  {
    for(int j=1;j<=10;j++)
    {
      cout<<" "<<c[i][j];
    }
    cout<<endl;
  }
  cout<<"####################"<<endl;
  for(int i=1;i<=3;i++)
  {
    for(int j=1;j<=10;j++)
    {
      cout<<" "<<d[i][j];
    }
    cout<<endl;
  }
}



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

using namespace std;

int main() {
    string s;
    cin >> s;

    while (s.size() > 1) {
        s.erase(s.size()-1);
        int ssize = s.size();
        if (ssize % 2 == 0) {
            int shalf = ssize / 2;
            if (s.substr(0, shalf) == s.substr(shalf, shalf)) {
                cout << ssize << endl;
                return 0;
            }
        }
    }
}

Measured memory_bytes: 256
import Data.List
import Control.Monad

my_comp::((String,Int),Int)->((String,Int),Int)->Ordering
my_comp ((st1,i1),_) ((st2,i2),_) = case compare st1 st2 of
                            EQ -> compare i2 i1
                            o  -> o

solver::[((String,Int),Int)]->[Int]
solver = map snd . sortBy my_comp

main::IO()
main=do
  n<-return. read =<< getLine
  dat <- forM [1..n] (\_->return. (\ (s:p:_) -> (s,read p) ) .words =<< getLine)
  forM_ (solver (zip dat [1..])) print


Measured memory_bytes: 1020
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>
#include <climits>
#include <cmath>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define reps(i,s,n) for(int i=s, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;
const char sp = ' ';


using namespace std;

ll p[10][10];

ll topping(ll index){
    while(true){
        if(index<10) break;
        index/=10;
    }
    return index;
}

int main(void){
    MEMSET(p, 0);
    ll N;
    cin>>N;
    rep1(i, N){
        p[topping(i)][i%10]++;
        //cout<<topping(i)<<sp<<i%10<<endl;
    }
    ll count=0;
    rep1(i, 9){
        rep1(j, i){
            if(i==j) count+=p[i][j]*p[i][j];
            else count+=p[i][j]*p[j][i]*2;
        }
    }
    cout<<count<<endl;
    return 0;
}


Measured memory_bytes: 3652
#include<stdio.h>
#define MAX 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

int main(){
  int i,j,a,r,n;
  int b,c,min,X[MAX],Y[MAX],color[MAX],G[MAX][MAX];
  int sum=0;

  scanf("%d", &n);

  for ( i = 0; i< n; i++ ){
    for ( j = 0; j < n; j++ ){
      scanf("%d",&a);
      G[i][j]=(a==-1)?1000000:a;
    }
  }

  for ( i = 0; i < n; i++ ) {
    X[i]=1000000;
    Y[i]=-1;
    color[i]=WHITE;
  }

  X[0]=0;

  while(1){
    min=1000000;
    b=-1;
    for (i=0;i<n;i++){
      if (min>X[i]&&BLACK!=color[i]){
	b=i;
	min=X[i];
      }
    }
    if (b==-1) break;
    color[b]=BLACK;
    
    for (c=0;c<n;c++){
      if (BLACK!=color[c]&&G[b][c]!=1000000){
	if (X[c]>G[b][c]){
	  X[c]=G[b][c];
	  Y[c]=b;
	  color[c]=GRAY;
	}
      }
    }
  }

  for (i=0;i<n;i++){
    if (Y[i]!=-1){
      sum+=G[i][Y[i]];
  }
  }
 

  printf("%d\n",sum);

  return 0;
}




Measured memory_bytes: 2108
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
// #define main int main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vb> vvb;
typedef vector<vpii> vvpii;
const int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
const int MOD = 1000000007;
const double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
bool odd(const int &n) { return n & 1; }
bool even(const int &n) { return !odd(n); }
template<typename V> typename V::value_type sum(const V &v) { return accumulate(all(v), 0); }
void solve();
main { solve(); return 0; }
// clang-format on

bool f(int a, int b, int c) {
  return a * a + b * b == c * c;
}

void solve() {
  int n;
  cin >> n;
  rep(_, n) {
    int a, b, c;
    cin >> a >> b >> c;
    cout << (f(a, b, c) || f(b, c, a) || f(c, a, b) ? "YES" : "NO") << endl;
  }
}

Measured memory_bytes: 2936
a, b = map(int,input().split())

cnt = 0

for i in range(1,1010):
    A = int(i * 8 //100)
    B = int(i * 10 //100)
    if (A == a) and (B == b):
        print(i)
        cnt += 1
        break

if cnt == 0:
    print(-1)

Measured memory_bytes: 9060
def get_i() #空白区切の入力を数値(整数)の配列で返す
  return gets.chomp.split(" ").map(&:to_i)
end
def get_f() #空白区切の入力を数値(実数)の配列で返す
  return gets.chomp.split(" ").map(&:to_f)
end
def get() #空白区切の入力を文字列の配列で返す
  return gets.chomp.split(" ")
end
def get_nsp() #入力されたものを一文字ずつに区切った文字列の配列で返す
  return gets.chomp.split("")
end
def yn_judge(bool,y="Yes",n="No") #boolに真偽を投げることで、trueならy、falseならnの値を出力する
  return bool ? y : n 
end
def array(size1,init=nil,size2=1) #size2に二次元配列時の最初の要素数、size1に次の配列の大きさ、initに初期値を投げることでその配列を返す
  if size2==1
    return Array.new(size1){init}
  else
    return Array.new(size2){Array.new(size1){init}}
  end
end

dp=array(30,0)
dp[0]=1
dp[1]=2
dp[2]=4
3.upto(29) do|i|
    dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
end
loop do
    n=gets.to_i
    break if n.zero?
    puts dp[n-1]/(10*365)+1
end


Measured memory_bytes: 6880
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;
ll MOD = 1e9+7;
//LLONG_MIN

int main(void){
	int ans=0;
	string s;//gpgp...が最適だとすると
	cin>>s;
	rep(i,s.size()){
		if(s[i]=='p' && i%2==0){
			ans--;
		}else if(s[i]=='g' && i%2==1){
			ans++;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
map<int,bool> ok;

int main(){
int n,cont3=0;
cin>>n;
int v[n],val[2];
val[0]=val[1]=0;
for(int i=0;i<n;i++){
	cin>>v[i];
	if(ok[v[i]]==false){
		ok[v[i]]=true;
		val[cont3]=v[i];
		cont3++;
		if(cont3==3){
			cout<<"No"<<endl;
			return 0;
		}
	}
}

if(cont3==1){
	if(n==val[0]+1||n>=val[0]*2)
	cout<<"Yes"<<endl;
	else
	cout<<"No"<<endl;
}
else{
	
	int cont=0,cont1=0;
	if(val[0]>val[1])
	swap(val[0],val[1]);
	
	for(int i=0;i<n;i++){
		if(v[i]==val[0])
		cont++;
		else
		cont1++;
	}
	if(val[0]==val[1]-1&&cont1!=1&&val[1]>cont&&val[1]<=cont+(cont1/2))
	cout<<"Yes"<<endl;
	else
	cout<<"No"<<endl;
	
}

return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<climits>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define scan(arg) cin>>arg
#define prin(arg) cout<<arg<<"\n"
#define prin2(arg1,arg2) cout<<arg1<<" "<<arg2<<"\n"
using namespace std;
typedef long long ll;
const int NMAX=1<<17;
int n;
int l[1010],r[1010];
int main(){
  scan(n);
  rep(i,n){
    scan(l[i]);scan(r[i]);
  }
  int res=0;
  rep(i,n){
    res+=r[i]-l[i]+1;
  }
  prin(res);
  
  return 0;
}


Measured memory_bytes: 256
class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

N, M = map(int, input().split())
MOD = 10**9 + 7

def primeCount(N):
    R = int(N**(0.5)) + 1  # 素数の範囲
    primes = {}  # 素数のリスト
    n = N
    for num in range(2, R):
        primes[num] = 0
        while n % num == 0:
            n //= num
            primes[num] += 1
    if n > 1 :
        primes[n] = 1
    return { key : val for key, val in primes.items() if val > 0}  # フィルターをかける

primeM = primeCount(M)
ans = 1
comb = Combination(sum(primeM.values()) + N + 100)

for cnt in primeM.values():
    ans *= comb.ncr(cnt + N - 1, cnt)
    ans %= MOD

print(ans)


Measured memory_bytes: 15788
fn main() {
	let mut s = String::new();
	use std::io::Read;
	std::io::stdin().read_to_string(&mut s).unwrap();
	let mut s = s.split_whitespace();
	let op = s.next().unwrap().split("T").map(|a| a.len()).collect::<Vec<_>>();
	let x: i32 = s.next().unwrap().parse().unwrap();
	let y: i32 = s.next().unwrap().parse().unwrap();
	let mut xs = std::collections::BTreeSet::new();
	let mut ys = std::collections::BTreeSet::new();
	xs.insert(op[0] as i32);
	ys.insert(0);
	if op.len() > 1 {
		for (i, f) in op[1..].iter().enumerate() {
			let f = *f as i32;
			if f == 0 { continue; }
			if i & 1 == 0 {
				ys = ys.into_iter().flat_map(|a| vec![a + f, a - f]).collect::<std::collections::BTreeSet<_>>();
			} else {
				xs = xs.into_iter().flat_map(|a| vec![a + f, a - f]).collect::<std::collections::BTreeSet<_>>();
			}
		}
	}
	if xs.contains(&x) && ys.contains(&y) {
		println!("Yes");
	} else {
		println!("No");
	}
}

Measured memory_bytes: 4476
#include<iostream>
using namespace std;
int main(){
	int n, r, b;
	char cap[102];
	cin >> n >> cap;
	r = b = 0;
	for(int i = 0;i < n;i ++){
		if(cap[i] == 'R') r++;
		else b++;
	}
	if(r > b) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;

}

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

string s[214514];

int main(){
	ll n;
	cin>>n;
	map<string,ll>mp;
	for(int i=0;i<n;i++){
		cin>>s[i];
		sort(s[i].begin(),s[i].end());
		mp[s[i]]++;
	}
	sort(s,s+n);
	vector<string>v;
	for(int i=1;i<n;i++){
		if(s[i-1]!=s[i]&&mp[s[i-1]]>=2)v.push_back(s[i-1]);
	}
	if(mp[s[n-1]]>=2)v.push_back(s[n-1]);
	ll ans=0;
	for(int i=0;i<v.size();i++){
		ans+=mp[v[i]]*(mp[v[i]]-1)/2;
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 19072
# include <bits/stdc++.h>
# define fi first
# define se second

using namespace std ;

long long K, A, B ;
long long bis=1, m ;

int main() {
    cin >> K >> A >> B ;
    if( A >= B-2 ) {
        cout << K + 1 << endl;
        return 0 ;
    }
    while( true ) {
        if( K == 0) break ;
        if( bis >= A && K > 1 ) {
            K -= 2 ;
            bis += B - A ;
        }
        else {
            bis ++ ;
            K -- ;
        }
    }
    cout << bis << endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> l_l;
const int INF=1001001000;
const int mINF=-1001001000;
const ll LINF=1010010010010010000;
template<class T> inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<class T> inline bool chmax(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
bool dpx[16005][8005];
bool dpy[16005][8005];
int main(){
    string s;cin >> s;
    int x,y;cin >> x >> y;
    vector<int> cnt;
    int cc=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='F') cc++;
        else{
            cnt.push_back(cc);
            cc=0;
        }
    }
    if(cc!=0) cnt.push_back(cc);
    int n=cnt.size();
    //for(int i=0;i<n;i++) cout << cnt[i] << endl;
    for(int i=0;i<16005;i++){
        for(int j=0;j<8005;j++){
            dpx[i][j]=false;
            dpy[i][j]=false;
        }
    }
    dpx[8000][0]=true;
    dpy[8000][0]=true;
    dpx[8000+cnt[0]][1]=true;
    for(int i=0;i<n;i++){
        if(i%2==0){
            if(i!=0){
                for(int j=0;j<=16000;j++){
                    if(j+cnt[i]<=16000){
                        if(!dpx[j+cnt[i]][i+1]) dpx[j+cnt[i]][i+1]=dpx[j][i];
                    }
                    if(j-cnt[i]>=0){
                        if(!dpx[j-cnt[i]][i+1]) dpx[j-cnt[i]][i+1]=dpx[j][i];
                    }
                }
            }
            for(int j=0;j<=16000;j++){
                dpy[j][i+1]=dpy[j][i];
            }
        }
        else if(i%2==1){
            for(int j=0;j<=16000;j++){
                if(j+cnt[i]<=16000){
                    if(!dpy[j+cnt[i]][i+1]) dpy[j+cnt[i]][i+1]=dpy[j][i];
                }
                if(j-cnt[i]>=0){
                    if(!dpy[j-cnt[i]][i+1]) dpy[j-cnt[i]][i+1]=dpy[j][i];
                }
            }
            for(int j=0;j<=16000;j++){
                dpx[j][i+1]=dpx[j][i];
            }
        }
    }
    if(dpx[x+8000][n]&&dpy[y+8000][n]) cout << "Yes" << endl;
    else cout << "No" << endl;
    //cout << dpy[8000][1] << endl;
    return 0;
}

Measured memory_bytes: 250496