akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

using int64 = long long;
const int mod = 1e9 + 7;

const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;

struct IoSetup {
  IoSetup() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    cerr << fixed << setprecision(10);
  }
} iosetup;


template< typename T1, typename T2 >
ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {
  os << p.first << " " << p.second;
  return os;
}

template< typename T1, typename T2 >
istream &operator>>(istream &is, pair< T1, T2 > &p) {
  is >> p.first >> p.second;
  return is;
}

template< typename T >
ostream &operator<<(ostream &os, const vector< T > &v) {
  for(int i = 0; i < (int) v.size(); i++) {
    os << v[i] << (i + 1 != v.size() ? " " : "");
  }
  return os;
}

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

template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

template< typename T = int64 >
vector< T > make_v(size_t a) {
  return vector< T >(a);
}

template< typename T, typename... Ts >
auto make_v(size_t a, Ts... ts) {
  return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));
}

template< typename T, typename V >
typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {
  t = v;
}

template< typename T, typename V >
typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {
  for(auto &e : t) fill_v(e, v);
}

template< typename F >
struct FixPoint : F {
  FixPoint(F &&f) : F(forward< F >(f)) {}

  template< typename... Args >
  decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, forward< Args >(args)...);
  }
};

template< typename F >
inline decltype(auto) MFP(F &&f) {
  return FixPoint< F >{forward< F >(f)};
}

int main() {
  string S;
  cin >> S;
  if(S == "Sunny") cout << "Cloudy" << endl;
  else if(S == "Cloudy") cout << "Rainy" << endl;
  else cout << "Sunny" << endl;

}




Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <iomanip>
using namespace std;
int main(){
  int n,res;
  int m=100000;
  cin>>n;
  if(!n){cout<<m<<endl;return 0;}
  for(;n;n--){
    m*=1.05;
    if(m%1000){
      m+=1000-(m%1000);
    }
  }
  cout<<m<<endl;
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
 
typedef unsigned long long int ull;
typedef long double ldb;
typedef long long int ll;
 
#define for01(k,n)  for (ll i=k; i<n; i++)
#define for02(k,n)  for (ll j=k; j<n; j++)
#define for03(k,n)  for (ll k=k; k<n; k++)
#define for11(k,n)  for (ll i=k; i<=n; i++)
#define for12(k,n)  for (ll j=k; j<=n; j++)
#define for13(k,n)  for (ll k=k; k<=n; k++)

#define pb push_back
#define mp make_pair
#define vll vector<ll>
#define F first
#define S second
#define pp pair <ll, ll>
#define lb lower_bound
#define ub upper_bound
#define emp empty()
#define beg begin()
#define en end()
#define si size()
#define bk back()
#define deci(n)  fixed<<setprecision(n)

#define p0(a) cout << a << " "
#define p1(a) cout << a << "\n"


#define MAX LLONG_MAX

#define MIN LLONG_MIN

using namespace std;


int main()
{
  string a,b,c;
  cin >> a >> b >> c;
  
  queue<char> sa,sb,sc;
  
  for01(0,a.length())
    sa.push(a[i]);
  
  for01(0,b.length())
    sb.push(b[i]);
  
  for01(0,c.length())
    sc.push(c[i]);
  
  char c1 = sa.front();
  sa.pop();
  
  while(1)
  {
    
    if(c1 == 'a')
    {
      if(sa.empty())
      {
       p1('A');
       return 0;
      }
      c1 = sa.front();
      sa.pop();
    }
    else if(c1 == 'b')
    {
      if(sb.empty())
      {
       p1('B');
       return 0;
      }
      c1 = sb.front();
      sb.pop();
    }
    else
    {
      if(sc.empty())
      {
       p1('C');
       return 0;
      }
      c1 = sc.front();
      sc.pop();
    }
  }
  return 0;
}

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

int main() {
    int n, card[13 * 4 + 1] = {};

    cin >> n;
    for (int i = 0; i < n; i++) {
        char s;
        int r;
        cin >> s >> r;
        switch (s) {
            case 'S': card[13 * 0 + r] = 1; break;
            case 'H': card[13 * 1 + r] = 1; break;
            case 'C': card[13 * 2 + r] = 1; break;
            case 'D': card[13 * 3 + r] = 1; break;
        }
    }

    for (int i = 1; i <= 13 * 4; i++) {
        if (card[i] == 0) {
            if (i <= 13 * 1) {
                cout << "S";
            } else if (i <= 13 * 2) {
                cout << "H";
            } else if (i <= 13 * 3) {
                cout << "C";
            } else {
                cout << "D";
            }
            cout << " " << (i - 1) % 13 + 1 << endl;  // i % 13 とすると、0 ~ 12
        }
    }

    return 0;
}


Measured memory_bytes: 3104
#!/usr/bin/env python3
#input
import math
# math.degrees(theta) = theta radian to kodo
# math.atan(math.tan(theta)) = theta
a,b,x = map(int,input().split())
if x <= a*a*b/2:
    tan = (a*b*b)/(2*x)
else:
    tan = 2*(a*a*b-x)/(a**3)
print(math.degrees(math.atan(tan)))


Measured memory_bytes: 2940
#include<iostream>
using namespace std;
int main(void){
  int N,T,A;
  cin>>N>>T>>A;
  int H[N];
  double C[N],Abs[N];
  for(int i(0);i<N;i++){
    cin>>H[i];
    C[i]=T-H[i]*0.006;
    if(C[i]>A)Abs[i]=C[i]-A;
    else Abs[i]=A-C[i];
  }
  double min(Abs[0]);
  int t(0);
  for(int i(1);i<N;i++){
    if(min>Abs[i]){
      min=Abs[i];
      t=i;
    }
  }
  cout<<t+1<<endl;
  return 0;
}

Measured memory_bytes: 256
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    S = readline().strip()
    T = readline().strip()
    N, M = len(S), len(T)

    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            elif dp[i + 1][j] > dp[i][j + 1]:
                dp[i + 1][j + 1] = dp[i + 1][j]
            else:
                dp[i + 1][j + 1] = dp[i][j + 1]

    ans = []
    i, j = N, M
    while i and j:
        if S[i - 1] == T[j - 1]:
            ans.append(S[i - 1])
            i -= 1
            j -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            i -= 1

    print(''.join(reversed(ans)))
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 111580
#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;


int main(){
    string t;
    cin >> t;
    int n = t.size();
    rep(i, n){
        if (t[i] == '?') t[i] = 'D';
    }
    cout << t << endl;
    return 0;
}


Measured memory_bytes: 3756
#include <algorithm>
#include <bits/stdc++.h>
#include <bitset>
#include <cassert>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <cmath>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
#define REP(i, n) for (int64_t i = 0; i < (int64_t)n; i++)
#define REP_FOR(i, a, b) for (int64_t i = (int64_t)a; i < (int64_t)b; i++)
#define REP_REV(i, a, b) for (int64_t i = (int64_t)a; i > (int64_t)b; i--)
#define FORALL(v) (v).begin(), (v).end()
#define mp(a, b) make_pair(a, b)
#define eb(x) emplace_back(x)
#define F first
#define S second
typedef long long ll;
typedef long double ld;
typedef pair<int64_t, int64_t> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int64_t> vii;
typedef vector<vii> vvii;
const ll mod = 1e9 + 7;
const int64_t infi = 1147483600;
const ll infl = 4e18 + 5;
const char EOL = '\n';
const ll MOD = 998244353;

template <typename T>
bool carry4(vector<T> & L) {
    bool carry = true;
    for (auto & l: L) {
        if (carry) {
            carry = false;
            ++l;
            if (l >= 4) {
                carry = true;
                l = 0;
            }
        }
    }
    return carry;
}

int main() {
    ll n;
    vector<ll> E(3);
    cin >> n >> E[0] >> E[1] >> E[2];
    ll combine = (n - 3) * 10;
    vector<ll> L(n);
    for (auto & l : L) {
        cin >> l;
    }

    vector<int> Ord(n, 0);

    ll res = 4e18 + 5;
    while (!carry4(Ord)) {
        ll cur = 0;
        vector<ll> T(3, 0);
        vector<ll> counts(3, 0);
        vector<ll> mins(3, 1e9);
        for (ll i = 0; i < n; ++i) {
            if (Ord[i] >= 3) continue;
            T[Ord[i]] += L[i];
            ++counts[Ord[i]];
        }
        if (T[0] == 0 || T[1] == 0 || T[2] == 0) continue;
        for (ll i = 0; i < 3; ++i) {
            cur += abs(E[i] - T[i]) + 10 * (counts[i] - 1);
        }
        res = min(res, cur);
    }

    cout << res << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
const int  maxn=5e5+10;
int a[maxn],n,num[maxn],m,ans,block,vis[maxn];

inline int read() {
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*f;
}

struct node {
    int l, r, id;
    bool operator<(const node &b) const {
        if (l / block == b.l / block) return r < b.r;
        return l / block < b.l / block;
    }
}q[maxn];
 
void add(int x){
    vis[a[x]]++;
    if (vis[a[x]]==1)ans++;
}
void del(int x){
    vis[a[x]]--;
    if (vis[a[x]]==0)ans--;
}
int main() {
	n=read(),m=read();
    block=sqrt(n);
    for (int i = 1; i <= n; i++) a[i]=read();
    for (int i = 1; i <= m; i++) {
    	q[i].l=read(), q[i].r=read();
        q[i].id = i;
    }
    sort(q + 1, q + 1 + m);
    int l = 1,r=0;
    for (int i = 1; i <= m; i++) {
        while (l<q[i].l) {
            del(l);
            l++;
        }
        while (l>q[i].l){
            l--;
            add(l);
        }
        while (r<q[i].r){
            r++;
            add(r);
        }
        while (r>q[i].r){
            del(r);
            r--;
        }
        num[q[i].id] =ans;
    }
    for (int i = 1; i <= m; i++) {
        printf("%d\n", num[i]);
    }
}

Measured memory_bytes: 15408
k, t = map(int, input().split())
a_list = [[int(value), index] for index, value in enumerate(input().split())]
ans = 0
prev = -1
for i in range(k):
    a_list.sort(reverse=True)
    index = 0
    if prev == a_list[index][1]:
        if len(a_list) > 1:
            index += 1
        else:
            ans += 1
    prev = a_list[index][1]
    if a_list[index][0] == 1:
        a_list.pop(index)
    else:
        a_list[index][0] -= 1
print(ans)

Measured memory_bytes: 9084
n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7

ans = 0
for k in range(60):
    cnt_z = 0
    cnt_o = 0
    for i in range(len(a)):
        if (a[i] >> k) & 1 == 1:
            cnt_o += 1
        else:
            cnt_z += 1
    ans += ((cnt_o * cnt_z) * 2 ** k)
    ans %= MOD

print(ans)




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

const ll INF = 1LL << 60;

int main(){
    int n;
    cin >> n;
    vector<string> sv(n);
    string s="MARCH";
    set<char> st;
    int ans[5]={};
    rep(i,n){
        cin >> sv[i];
        int tmp=s.find(sv[i][0]);
        if(tmp!=-1){
            st.insert(s[tmp]);
            ans[tmp]++;
        }
    }
    ll a=0;
    rep(i,3){
        ll tmp=ans[i];
        for(int j=i+1;j!=4;j++){
            ll tmp2=tmp*ans[j];
            for(int k=j+1;k!=5;k++){
                ll tmp3=tmp2*ans[k];
                a+=tmp3;
            }
        }
    }
    cout << a << endl;
}


Measured memory_bytes: 6144
#include <iostream>

using namespace std;

int main() 
{
	int nX, nY;
	cin >> nX;
	cin >> nY;

	bool isFlg = false;

	for (int i = 1; i < nX + 1; i++)
	{
		if (nY == (2 * i + 4 * (nX - i)))
		{
			isFlg = true; 
		}

		if (nY == (4 * i + 2 * (nX - i)))
		{
			isFlg = true;
		}
	}

	if (isFlg)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
}

Measured memory_bytes: 3624
#include <stdio.h>

int bubbleSort();

int main() {
  int num;
  int i,j,count;
  int A[100];

    scanf("%d",&num);
    for(i = 0; i<num; i++)
      scanf("%d",&A[i]);
    
    count = bubbleSort(A, num);

    for(i = 0; i<num; i++){
      printf("%d",A[i]);
      if(i != num -1) printf(" ");
    }
    printf("\n%d\n",count);

    return 0;
    
}

int bubbleSort(int A[],int num){
  
  int flag = 1;
  int  i = 0;
  int j;
  int count = 0;
  int temp;
  
    while (flag){
      flag = 0;
      for (j =num-1; j >= i+1; j--){
	
	if (A[j] < A[j-1]){
	     
	  temp = A[j];
	  A[j] = A[j-1];
	  A[j-1] = temp;
	
	  flag = 1;
	  count++;

	}
      }
	  i++;
      
    }
    return count;
}

Measured memory_bytes: 604
import java.util.*;
class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int[] A=new int[N+1];
		A[0]=0;
		for(int i=1;i<=N;i++){
			A[i]=sc.nextInt();
		}
		int[] dp=new int[N+1];
		
		if(A[N]==0){
			dp[N]=0;
		}else{
			dp[N]=1;
		}
		
		for(int i=N-1;i>=1;i--){
			int sum=0;
			for(int j=i;j<=N;j+=i){
				sum+=dp[j];
			}
			if(sum%2==A[i]){
				dp[i]=0;
			}else{
				dp[i]=1;
			}
		}
		int count=0;
		for(int i=1;i<=N;i++){
			if(dp[i]==1)
				count++;
		}
		
		System.out.println(count);
		for(int i=1;i<=N;i++){
			if(dp[i]==1){
				System.out.println(i);
				
			}
		}

	}
}		


Measured memory_bytes: 73680
#include <bits/stdc++.h>
#include <iostream>
#include <utility> // pair
#include <string>
#include <vector>
#define MAX_N 100001
#define rep(i, a, b) for(ll i=a; i<b; i++)
#define rer(i, a, b) for(ll i=a-1; i>=b; i--)
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll n;
string a, b, c;

signed main(){
    cin >> n >> a >> b >> c;
    ll ret = 0;
    rep(i, 0, n){
        if(a[i]==b[i] && a[i]==c[i]) continue;
        else if(a[i]==b[i] || b[i]==c[i] || c[i]==a[i]) ret += 1;
        else ret += 2;
    }
    cout << ret << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define maxn 100
#define maxk 100001
using namespace std;
typedef long long LL;

LL ans;
int n,k;
int w[maxn];
int v[maxn];
LL dp[maxk];

int main() {
	cin >> n >> k;
	for( int i = 0 ; i < n ; i++ )
		cin >> w[i] >> v[i];
	memset( dp , -1 , sizeof(dp) );
	dp[0] = 0;
	for( int i = 0 ; i < n ; i++ )
		for( int j = k - w[i] ; j >= 0 ; j-- )
			if( dp[j] != -1 )
				if( dp[j+w[i]] == -1 || dp[j]+v[i] > dp[j+w[i]] )
					dp[j+w[i]] = dp[j]+v[i];
	for( int i = 0 ; i <= k ; i++ )
		ans = max( ans , dp[i] );
	cout << ans << endl;
}


Measured memory_bytes: 1024
#include<stdio.h>
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;

int main(){
    int x[5];
    int k;

    for(int i = 0;i < 5;i++)cin >> x[i];
    cin >> k;

    if(x[4] - x[0] <= k)cout << "Yay!" << endl;
    else cout << ":(" << endl;
    
    return 0;
}

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

int main() {
  ll n, d;
  cin >> n >> d;
  ll cnt = 0;
  rep(i,n) {
    ll x, y;
    cin >> x >> y;
    ll tmp = x*x + y*y;
    if (tmp <= d*d) cnt++;
  }
  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 3668
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int l = sc.nextInt();
    int Sum = l;
    
    if(l>=0){
      Sum = 0;
      for(int i=1;i<n;i++){
        Sum += l+i;
      }
    }else{
      if(n+l > 0){
        for(int i=1;i<n;i++){
          Sum += l+i;
        }
      }else{
        for(int i=1;i<n-1;i++){
        	Sum += l+i;
      	}
      }
    }
    System.out.println(Sum);
  }
}

Measured memory_bytes: 22228
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i < (b); ++i)
#define rrep(i,a,b) for(int i = b; i --> (a);)
#define all(v) v.begin(),v.end()
#define trav(x,v) for(auto &x : v)
#define sz(v) (int)(v).size()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;

const int mx = 100;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll a, b;
	cin >> a >> b;
	cout << (abs(a-b) >= 2 ? "Alice" : "Brown") << endl;

}

Measured memory_bytes: 256
N,Y = [int(x) for x in input().split()]

def func(N,Y):
    for m in range(N,-1,-1):
        for i in range(0,N-m+1):
            if 10000*m+5000*i+1000*(N-m-i)==Y:
                return m,i,N-m-i
                
    return -1,-1,-1
    
a,b,c=func(N,Y)
print(a,b,c)

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

bool solve(int , int, int);


int main()
{
    int K, A, B;
    cin>>K;
    cin>>A>>B;
    if(solve(K, A, B))
        cout<<"OK\n";
    else
        cout<<"NG\n";
    return 0;
}

bool solve(int K, int A, int B)
{
    for(int i=A; i<=B; i++)
    {
        if(i%K == 0)
            return true;
    }
    return false;
}

Measured memory_bytes: 3636
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
#define LL long long
const int maxn = 1e6+33;
const int mod = 1e9+7;
int main()
{
   int n;
   scanf("%d",&n);
   int ans=0;
   for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        ans+=x-1;
   }
   printf("%d\n",ans);
    return 0;

}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> l_l;
typedef pair<int,int> i_i;
const ll MOD=1e9+7;
const int INF=1<<30;

int dp[100100];

int main(){
  int N; cin >> N;
  vector<int> h(N);
  rep(i,N) cin >> h[i];
  rep(i,100100){
    dp[i]=INF;
  }
  dp[0]=0;
  rep(i,N){
    if(i+2<N) chmin(dp[i+2],dp[i]+abs(h[i+2]-h[i]));
    if(i+1<N) chmin(dp[i+1],dp[i]+abs(h[i+1]-h[i]));
  }
  cout << dp[N-1] << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

#define CH(N,A,B) (A<=N&&N<B)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define RREP(i,a,b) for(int i=(b-1);a<=i;i--)

using namespace std;

int main() {

    int n, d, x, p[10][10];
    cin>>n>>d>>x;
    REP(i,0,d)REP(j,0,n) cin>>p[i][j];

    int dp[100005];
    int maxMoney = x;

    REP(day,0,d-1){
      REP(i,0,maxMoney+1) dp[i] = i;

      REP(j,0,n){ //select stock
        REP(i,0,maxMoney+1){  //select amount of money
          if(i - p[day][j] >= 0){
            dp[i] = max(dp[i], dp[i - p[day][j]] + p[day+1][j]);
          }
        }
      }

      maxMoney = *max_element(dp, dp+(maxMoney+1));
    }

    cout<<maxMoney<<endl;

  return 0;
}

Measured memory_bytes: 3052
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back 
#define pf push_front 
#define mp make_pair
#define fr first
#define sc second
#define Rep(i,n) for(int i=0;i<(n);i++)
#define All(v) v.begin(),v.end()
typedef pair<int, int> Pii; typedef pair<int, Pii> Pip;
const int INF = 1107110711071107;

main()
{
  int isprime[1000001];
  
  fill_n(isprime, 1000001, 1);
  isprime[0] = isprime[1] = 0;
  
  for(int i=2; i<1000001; i++) {
    for(int j=2; i*j<1000001; j++) {
      isprime[i*j] = 0;
    }
  }
  
  
  int a, d, n;
  while( cin >> a >> d >> n, !(a == 0 && d == 0 && n == 0) ) {
    int cnt = 0;
    for(int i=0; ; i++) {
      if( isprime[a+i*d] ) cnt++;
      if( cnt == n ) {
	cout << a+i*d << endl;
	break;
      }
    }
  }
  
}

Measured memory_bytes: 10808
from math import *
f=lambda:[*map(int,input().split())]
n,k=f()
a=f()
def ok(x):
  c=0
  for i in a:
    c+=ceil(i/x)
  return c<=n+k
l,r=0,10**9+1
while r-l>0.1:
  m=(l+r)/2
  if ok(m): r=m
  else: l=m
t=ceil(r)
print(t-ok(t-1) if t>1 else t)

Measured memory_bytes: 31240
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  map<string,int>m;
  string s,t;
  cin>>s>>t;
  int a,b;
  cin>>a>>b;
  m[s]=a;
  m[t]=b;
  string u;
  cin>>u;
  m[u]--;
  cout<<m[s]<<' '<<m[t];
  return 0;
}

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

#define pow(n) (n)*(n)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

using namespace std;

/* function */
int Dig_Max   (int64_t, int64_t);
int Dig_Count (int64_t);


/* code */
int main (void) 
{

  /* Variable_Proclamation */
  int64_t N;    // input

  int i;    // subscript

  int64_t root_n;
  int64_t A, B;
  int digits;
  int prov_min;


  /* Input, Array_Proclamation */
  cin >> N;


  /* Initialize */
  prov_min = INT_MAX;



  /* Calculation */
  root_n = sqrt(N);

  for(i=1; i <= root_n; i++)
  {

    if( N%i == 0 )
    {
      A = i;
      B = N /i;
    }
    else
    {
      continue;
    }
    

    digits   = Dig_Max(A, B);
    prov_min = min(digits, prov_min);

  }
  

  /* Output */
  cout << prov_min << endl;


  return 0;

}


/* entity */
int Dig_Count (int64_t data)
{

  int digits;

  digits = 0;
  while(data > 0)
  {
    data /= 10;
    digits++;
  }

  return digits;

}

int Dig_Max(int64_t data1, int64_t data2)
{

  int ret1, ret2;
  int ans;

  ret1 = Dig_Count(data1);
  ret2 = Dig_Count(data2);
  ans  = max(ret1, ret2);

  return ans;

}



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

int even(int n){
    return n/2;
}

int odd(int n){
    return 3 * n + 1;
}

int main(){
    int n;
    cin >> n;
    set<int> exist;
    int cnt = 0;
    while (true){
        if (exist.count(n) == 1) break;
        exist.insert(n);
        if (n%2 == 0) n = even(n);
        else n = odd(n);
        // printf("n: %d\n", n);
        cnt ++;
    }
    cout << cnt+1 << endl;
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i, n) for(int i=0; i<(n); ++i)
#define chmax(x, y) (x > (y) ? x : x = (y))
#define chmin(x, y) (x < (y) ? x : x = (y))
#define write(x) cout << (x) << endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = INT32_MAX / 2;
const int MAX = 1e5 + 10;

int N;
ll A[MAX], B[MAX];
multimap<ll, ll> mm;

int main()
{
    cin >> N;
    rep(i, N) cin >> A[i] >> B[i];

    rep(i, N) mm.insert(pair<ll, ll>(A[i] + B[i], A[i]));

    int j = 0;
    ll dif = 0;
    for (auto it = mm.crbegin(); it != mm.crend(); it++) {
        if (j % 2) {
            dif -= it->first - it->second;
        }
        else {
            dif += it->second;
        }
        j++;
    }
    write(dif);
}

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

int main(){
	LL s,c;
	cin>>s>>c;
	LL ans;
	if(2*s<c){
		ans=(s+((c-(2*s))/4LL));
	}else{
		ans=c/2LL;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
//
//  main.cpp
//  dodecagon
//
//  Created by SZhang on 7/20/19.
//  Copyright © 2019 SZhang. All rights reserved.
//

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    // insert code here...
    int n,i,k=0,a[200000], b[200000];
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b,b+n);
    
    for(i=0;i<n;i++){
        if(a[i]!=b[n-1]){
            cout<<b[n-1]<<endl;
        }
        else{
            cout<<b[n-2]<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3200
#include<iostream>
using namespace std;
int main(){
  long long A,B,K;
  cin>>A>>B>>K;
  long long t=A-K;
  long long u=0;
  if (t>=0) u=B; 
    else{ u=B+t; 
         t=0;}
  if(u<=0) u=0;
  cout<<t<<" "<<u<<endl;
}

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

int main()
{
  int x,h;
  for(;cin>>x>>h,x;)
      cout<< fixed << setprecision(6)<<(double)x*sqrt(4*h*h+x*x)+x*x<<endl;
}

Measured memory_bytes: 1232
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
 
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;
using vs = vector<string>;
using vb = vector<bool>;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REV(c) reverse(ALL(c))
#define sz(v) (int)v.size()
#define endl '\n'
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;}
template<class T> inline void prn(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << ' ';}
template<class T> inline void printv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << (i == n - 1 ? endl : ' ');}
template<class T> inline void printvv(vector<vector<T>>& v) {for (auto u : v) printv(u);}
template<class T> inline void printlnv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << endl;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}
 
int op(int a, int b) {return max(a, b);}
 
int e() {return -1;}
 
int x;
bool f(int b) {return b < x;};

void solve() {
    int n, q;
    cin >> n >> q;
    vi a(n);
    REP(i, n) cin >> a[i];
    segtree<int, op, e> st(a);
    int t, u, v;
    REP(i, q) {
        cin >> t >> u >> v;
        if (t == 1) st.set(u - 1, v);
        else if (t == 2) cout << st.prod(u - 1, v) << endl;
        else {
            x = v;
            cout << st.max_right<f>(u - 1) + 1 << endl;
        }
    }
}

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

using namespace std;

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;
using vld = vector<ld>;
using vvld = vector<vld>;

typedef pair<ll, ll> P;

#define bit(n) (1LL << (n))

//#define int long long

#define all(v) v.begin(), v.end()

#define rep(i, n) for (ll i = 0; i < n; i++)
#define REP(i, n) for (ll i = 1; i < n; i++)

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORm(i, m) for (auto i = m.begin(); i != m.end(); i++)

template <class T>
inline void chmax(T& a, T b) {
  a = std::max(a, b);
}
template <class T>
inline void chmin(T& a, T b) {
  a = std::min(a, b);
}

#define mod (ll)(1e9 + 7)
// #define mod (998244353ll)

const long long INF = 1LL << 60;

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);

  string s, t;
  cin >> s >> t;

  ll n = s.size();
  ll m = t.size();

  vvll dp(n + 1, vll(m));
  rep(i, n) {
    rep(j, m) {
      chmax(dp[i + 1][j], dp[i][j]);
      if (s[i] == t[j]) {
        if (j - 1 >= 0) {
          chmax(dp[i + 1][j], dp[i][j - 1] + 1);
        } else {
          dp[i + 1][j] = 1;
        }
      }

      if (j - 1 >= 0) {
        chmax(dp[i + 1][j], dp[i + 1][j - 1]);
      }
    }
  }

  string ans;
  int i = n;
  int j = m;

  while (i > 0) {
    int mi = distance(dp[i].begin(), max_element(dp[i].begin(), dp[i].begin() + j));

    if (dp[i][mi] == 0) {
      break;
    }
    ans.push_back(t[mi]);
    i--;
    while (dp[i + 1][mi] == dp[i][mi]) {
      i--;
      if (i == -1) {
        break;
      }
    }
    if (i == -1) {
      break;
    }
    j = mi;
  }

  reverse(all(ans));

  std::cout << ans << endl;

  return 0;
}


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

def solve(N: int, M: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    counter = collections.Counter(A)
    A = [[c, b] for c, b in counter.items()]
    for b, c in zip(B, C):
        A.append([c, b])

    A = sorted(A, reverse=True, key = lambda x:x[0])
    
    header = 0
    result = 0
    current_max = A[header]

    
    for i in range(N):
        if current_max[1] > 0:
            result += current_max[0]
            current_max[1] -= 1
        else:
            header += 1
            current_max = A[header]

            result += current_max[0]
            current_max[1] -= 1
    print(result)
    return


# 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()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    A = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    B = [int()] * (M)  # type: "List[int]" 
    C = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, M, A, B, C)

if __name__ == '__main__':
    main()


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

int main(){
	int h, w;
	int minh, minw;
	long long int minr;
	while(cin >> h >> w, h || w){
		minh = 150;
		minr = 1000000;
		for(int i=1; i < 150; i++){
			for(int j=1; j < i; j++){
				if(h*h+w*w == i*i+j*j && h < j){
					if(i == w && j == h) continue;
					if(j < minh){
						minh = j;
						minw = i;
						minr = i*i+j*j;
					}
				}
				else if(h*h+w*w < i*i+j*j){
					if(j < minh && i*i+j*j <= minr){
						minh = j;
						minw = i;
						minr = i*i+j*j;
					}
				}
			}
		}
		cout << minh << " " << minw << endl;
	}
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define COUT(x) cout<<(x)<<"\n"
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define REP(i, n) for(int i=0;i<n;i++)
#define YES(x) cout<<(x?"YES":"NO")<<"\n"
#define Yes(x) cout<<(x?"Yes":"No")<<"\n"
#define dump(x) cout<<#x<<" = "<<(x)<<"\n"
#define endl "\n"
using G = vector<vector<int>>;
using M = map<int,int>;
using P = pair<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int,vector<int>,greater<int>>;
using V = vector<int>;
using ll = long long;
using edge = struct { int to; int cost; };
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; }
const int INF = 1e9;
const ll LINF = 1e18;
const int mod = 1e9+7;

int dp[2000];

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

  dp[0] = 1;
  for (int i = 3; i <= s; i++) {
    for (int j = 3; j <= s; j++) {
      int v = i - j;
      if (v < 0) break;

      dp[i] = dp[i] + dp[v];
      dp[i] %= mod;
    }
  }

  COUT(dp[s]);
  return 0;
}

Measured memory_bytes: 3592
#pragma region kyomukyomupurin

/**
 *    author  : 𝒌𝒚𝒐𝒎𝒖𝒌𝒚𝒐𝒎𝒖𝒑𝒖𝒓𝒊𝒏
 *    created : 2020-05-11 08:58:48
 **/

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#include <cmath>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

using int64 = long long;

template <class T>
using binary_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) {
  return os << '(' << p.first << ", " << p.second << ')';
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
  int flag = 0;
  for (auto e : vec) os << (flag++ ? ", " : "{") << e;
  return os << (vec.empty() ? "{}" : "}");
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& st) {
  int flag = 0;
  for (auto e : st) os << (flag++ ? ", " : "{") << e;
  return os << (st.empty() ? "{}" : "}");
}

template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::map<T, U>& mp) {
  int flag = 0;
  for (auto e : mp) os << (flag++ ? ", " : "{") << e;
  return os << (mp.empty() ? "{}" : "}");
}

template <class T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
  for (T& e : vec) is >> e;
  return is;
}

#define all(_) begin(_), end(_)
#define rall(_) rbegin(_), rend(_)

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

void debug_out() { std::cerr << '\n'; }

template <class Head, class... Tail>
void debug_out(Head&& head, Tail&&... tail) {
  std::cerr << head;
  if (sizeof...(Tail) != 0) std::cerr << ", ";
  debug_out(std::forward<Tail>(tail)...);
}

#pragma endregion kyomukyomupurin

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

  int n; cin >> n;
  int64 k; cin >> k;
  vector<int> a(n); cin >> a;
  vector<int> cnt(202020, 0);

  for_each(all(a), [](int& e){ --e; });

  vector<int> route;
  int p = 0;
  int d = -1;

  cnt[p] = 1;

  while (1) {
    route.emplace_back(p);
    p = a[p];
    ++cnt[p];
    if (cnt[p] == 2) {
      d = p; break;
    }
  }

  debug(route, d);

  int res = -1;

  while (route[res + 1] != d) ++res;

  debug(res);

  vector<int> cycle;

  for (int i = res + 1; i < (int)route.size(); ++i) cycle.emplace_back(route[i]);
  debug(cycle);

  if (k <= res) {
    cout << route[k] + 1 << endl;
  } else {
    k -= res;
    int rep = cycle.size();
    cout << cycle[((k % rep + rep) - 1) % rep] + 1 << endl;
  }

  return 0;
}

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

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

const int N = 1e5 + 5;

int n,ans;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n;
  for (int i = 1 ; i <= n ; i++) {
    int x = i,cnt = 0;
    while(x) {
      cnt++;
      x /= 10;
    }
    if (cnt & 1)
      ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int average(int a[])
{
  int i,sum=0;
  for(i=0;i<5;i++){
    if(a[i]<40){
      a[i]=40;
    }
    sum=sum+a[i];
  }
  return(sum/5);
}

int main(void)
{
  int a[5];
  int s;
  int i;
  for(i=0;i<5;i++){
    scanf("%d",&a[i]);
  }

  s=average(a);
  printf("%d\n",s);
  return(0);
}

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

int main() {
    string str;
    cin >> str;
    int num = 700;

    for (int i = 0; i < 3; i++) {
        if (str[i] == 'o') {
            num += 100;
        }
    }

    printf("%d", num);
}

Measured memory_bytes: 256
#include<stdio.h>

#define MAX(x,y) (((x)>(y))?(x):(y))
#define MIN(x,y) (((x)<(y))?(x):(y))

int main(void){
  long long N,X,sums;
  long long low,high;

  scanf("%lld%lld",&N,&X);
  sums=N;
  low=MIN(X,N-X);
  high=MAX(X,N-X);

  do{
    sums+=low*((high/low)*2);
    high%=low;

    high^=low;
    low^=high;
    high^=low;
  }while(low!=0);
  sums-=high;
  printf("%lld\n",sums);
  return 0;

}
  


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(ll i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

ll n, m;
string s;

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	cin >> s;
	n = s.size()+1;
	ll a[n+1];
	memset(a, 0, sizeof(a));
	
	bool flag = false;
	rep(i, 0, n-1){
		if(!flag){
			if(s[i] == '<'){
				a[i] = 0;
				a[i+1] = 1;
				flag = true;
			}
		}
		else{
			if(s[i] == '<'){
				a[i+1] = a[i]+1;
			}
			else{
				flag = false;
			}
		}
	}
	
	if(s[n-2] == '>'){
		a[n-1] = 0;
	}
	rrep(i, n-2, 0){
		if(s[i] == '>'){
			a[i] = max(a[i+1] + 1, a[i]);
		}
	}
	
	ll ans = 0;
	rep(i, 0, n){
		ans += a[i];
		//print(a[i])
	}
	print(ans)
	return 0;
}

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

using namespace std;

string s;

#define pii pair < int, int >

int main() {
    cin >> s;
    int n = s.size();

    if (s[0] == '0' || s[n-1] == '1') {
        printf("-1\n");
        return 0;
    }

    vector < pii > ans;
    bool val = true;
    int node = 1;
    for (int i = n; i >= 1; i--) {
        if (s[i-1] == '1') {
            if (s[n-i-1] == '0') val = false;
            else {
                for (int j = node+1; j <= n-i; j++)
                    ans.push_back(pii(node, j));
                ans.push_back(pii(node, n-i+1));
                node = n-i+1;
            }
        }
    }

    if (!val) printf("-1\n");
    else {
        for (int i = 0; i < n-1; i++)
            printf("%d %d\n", ans[i].first, ans[i].second);
    }

    return 0;
}


Measured memory_bytes: 2420
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(obj) (obj).begin(),(obj).end()
typedef long long llong;
llong mod=1e9+7;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,m,k,j=0;
  cin>>n;
  k=n+1;
  vector<int> a;
  a.push_back(100);
  for(int i=1;i<=n;i++){
    cin>>m;
    if(a.size()==m){
      a.push_back(m);
    }
    else{
      j++;
    }

  }

if(j==n)cout<<-1<<endl;
else{
  cout<<j<<endl;
}
  return 0;
  }


Measured memory_bytes: 1400
#include <stdio.h>

int main() {

   int x, n, a, i, j, k;

   while(1) {
      scanf("%d %d", &n, &x);
      
      if(n == 0 && x ==0) break;
      a = 0;
      for (i = 1; i <= n-2; ++i) {
          for (j = i + 1; j <= n-1; ++j){
              for (k = j + 1; k <= n; ++k){
                  if (i + j + k == x) a++;
              }
          }
      }
      printf("%d\n", a);
   }

   return 0;
}

Measured memory_bytes: 1748
A = int(input())
B = int(input())
C = int(input())
X = int(input())

counts = 0

for a in range(A+1):
    for b in range(B+1):
        for c in range(C+1):
            if (a*500 + b*100 + c*50)==X:
                counts += 1
                
print(counts)

Measured memory_bytes: 3064
#include <stdio.h>
#include <string.h>
int main(void){
	char a[202],b[101],c[101];
	int i;
	
	scanf("%s",a);
	scanf("%s",b);
	for(i=0;a[i] != '\0';i++)
		c[i] = a[i];
	strcat(a,c);
	if(strstr(a,b)!=NULL)
		printf("Yes\n");
	else
		printf("No\n");
	return 0;
}

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

int N;
string s;
int main()
{
    cin>>N>>s;
    if(N%2){
        cout<<"No"<<endl;
    }
    else
    {
        bool b=true;
        for(int i=0;i<N/2;i++)
            if(s[i]!=s[i+N/2]) b=false;
        if(b) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}



Measured memory_bytes: 256
#include<cstdio>
#include<string>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<utility>
#include<algorithm>

using namespace std;

typedef string::iterator State;

vector<int> G[200200];
int N;
int sz[200200];

string str;
stack<int> st,fin;
int c=0;

void parse(){
	for(int i=0;i<str.size();i++){
		if(str[i]=='('){
			st.push(c++);
		}else{
			if(str[i-1]=='('){
				int v=st.top();
				st.pop();
				fin.push(v);
				sz[v]=0;
			}else{
				int v=fin.top();
				fin.pop();
				int u=fin.top();
				fin.pop();
				int p=st.top();
				st.pop();
				fin.push(p);
				G[p].push_back(u);
				G[p].push_back(v);
				sz[p]=sz[u]+sz[v]+2;
			}
		}
	}
}

int cands[200200];

queue<int> que;
bool rec(int v,int a){
//	printf("(%d,%d)\n",v,a);
	if(G[a].size()>0&&G[v].size()==0) return false;
	if(G[v].size()>0&&G[a].size()==0){
		que.push(v);
	}
	bool flg=true;
	if(G[v].size()>0&&G[a].size()>0){
		int b=G[a][0],c=G[a][1];
		int u=G[v][0],w=G[v][1];
		flg&=rec(u,b);
		flg&=rec(w,c);
	}
	return flg;
}

bool check(int r){
//	printf("check %d\n",r);
	while(!que.empty()) que.pop();
	que.push(0);
	while(!que.empty()){
		int v=que.front();
		que.pop();
		bool flg=rec(v,r);
		if(flg==false) return false;
	}
	return true;
}

vector<int> vals;
vector<int> dis;

int main(){
	cin>>str;
	parse();
//	for(int i=0;i<c;i++){
//		printf("%d::",i);
//		for(int j=0;j<G[i].size();j++) printf("%d ",G[i][j]);
//		printf("\n");
//	}
	N=c;
	if(N==3){
		printf("0\n");
		return 0;
	}
	for(int i=0;i<200200;i++) cands[i]=-1;
	for(int i=1;i<N;i++){
		if(sz[i]==0) continue;
		if(cands[sz[i]]==-1&&sz[0]%sz[i]==0){
			cands[sz[i]]=i;
		}
	}
	for(int i=0;i<200200;i++){
		if(cands[i]!=-1){
			bool flg=check(cands[i]);
			if(flg){
				vals.push_back(i);
			}
		}
	}
	vals.push_back(N-1);
	for(int i=0;i<vals.size();i++){
		if(i==0){
			dis.push_back(0);
			continue;
		}
		int tmp=-1;
		for(int j=0;j<i;j++){
			if(vals[i]%vals[j]==0){
				int cur=dis[j]+(vals[i]/vals[j]-1);
				if(tmp==-1||tmp>cur) tmp=cur;
			}
		}
		dis.push_back(tmp);
	}
	printf("%d\n",dis.back());
	return 0;
}

Measured memory_bytes: 13888
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
using i64 = int64_t;
int main() {
  int ans = 10000000;
  int N,M,X;
  cin >> N >> M >> X;
  vector<int> C(N);
  vector<vector<int>> A(N,vector<int>(M));
  rep(i,N){
    cin >> C.at(i);
    rep(j,M){
      cin >> A.at(i).at(j);
    }
  }
  rep(s,1<<N){
    int cost = 0;
    vector<int> rikai(M,0);
    rep(i,N){
      if(s >> i & 1){
        cost += C.at(i);
        rep(j,M){
          rikai.at(j) += A.at(i).at(j);
        }
      }
    }
    int TF = 0;
    rep(j,M)if(rikai.at(j) < X){
      TF = 1;
    }
    if(TF == 0){
      ans = min(ans,cost);
    }
  }
  if(ans == 10000000){
    cout << -1 << endl;
  }
  else{
  cout << ans << endl;
  }
}

Measured memory_bytes: 3624
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define Repr(e, b, i) for(int i = e; i >= b; i--)
#define rep(n, i) Rep(0, n-1, i)
#define repr(n, i) Repr(n-1, 0, i)
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define uniq(x) (x).erase(unique(all(x)),(x).end())

typedef long long ll;
typedef pair<ll, ll> llP;
typedef pair<int, int> intP;
typedef std::priority_queue<int> IntPrioQueue; //Z->A
typedef std::priority_queue<int, std::vector<int>, std::greater<int> > IntReversePrioQueue; //A->Z

const int MAX = 1024;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const int MOD = 1000000007;

int step[MAX];

void solve(void){
    int N, m;
    cin >> N >> m;
    rep(m, i) {
        int a, b;
        scanf("%d %d\n", &a, &b);
        a--; b--;
        step[a]++;
        step[b]--;
    }
    rep(N, i) step[i+1] += step[i];
    int dis = 0, ans = 0;
    rep(N+1, n) {
        if (step[n] > 0) dis++;
        else {
            ans += dis;
            dis = 0;
        }
    }
    ans = ans*2+1+N;
    cout << ans << '\n';
}

int main(void){
  solve();
  return 0;
}



Measured memory_bytes: 3236
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[0 for _ in range(n+1)]
dp[2]=abs(h[1]-h[0])
for i in range(2,n):
    dp[i+1]=999999999
    for x in range(min(k,i)):
        if dp[i+1]>dp[i-x]+abs(h[i]-h[i-1-x]):
            dp[i+1]=dp[i-x]+abs(h[i]-h[i-1-x])
print(dp[n])


Measured memory_bytes: 56544
from fractions import gcd
def solve():
    A,B,C,D,E,F = map(int, input().split())
    ans = {"w":A*100, "s":0}
    def density(water, sugar):
        return 100*sugar/(water+sugar)

    G = gcd(C,D)
    for a in range(31):
        for b in range(31):
            water = (a*A+b*B)*100
            if water>F:
                continue
            max_sugar = min((a*A+b*B)*E, F-water)
            sugar = int(G*(max_sugar//G))
            if sugar<min(C,D): continue
            if water+sugar==0: 
                continue
            if density(water, sugar)>density(ans["w"], ans["s"]):
                ans["w"] = water
                ans["s"] = sugar
                #print(water, sugar)
    print(ans["w"]+ans["s"], ans["s"])
    
if __name__ == '__main__':
    solve()

Measured memory_bytes: 5048
#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;

int main() {
    int A, B;
    cin >> A >> B;
    bool flag = true;
    if (A % 2 == 0 || B % 2 == 0) flag = false;
    if (flag) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


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

const int MX=100005;

int main(){
  int n;
  cin>>n;
  vector<ll> cnt(MX);//{0,0,...,0}が初期値
  rep(i,n){
    int a;
    cin>>a;
    cnt[a]++;
  }
  ll tot=0;
  rep(i,MX) tot+=i*cnt[i];

  int q;
  cin>>q;
  rep(i,q){
    int b,c;
    cin>>b>>c;
    tot-=b*cnt[b];
    tot-=c*cnt[c];
    cnt[c]+=cnt[b];cnt[b]=0;//bからcへ移動したから個数は0になる
    tot+=b*cnt[b];
    tot+=c*cnt[c];
    cout<<tot<<endl;
  }
}

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

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)

lli d[200100];

void func(long long N, std::vector<long long> a){

    vector<lli> v;
    for(lli i=N;i>=1;i--){
        if(d[i]%2!=a[i]){
            for(lli j=1;j*j<=i;j++){
                if(i%j==0){
                    d[j]++;
                    if(i/j != j)d[i/j]++;
                }
            }
            v.push_back(i);
        }
    }
    sort(v.begin(),v.end());
    cout<<v.size()<<endl;
    REP(i,0,v.size())cout<<v[i]<<" ";
    cout<<endl;

}

int main(){
    // cout << fixed << setprecision(5);

    long long N;
    scanf("%lld",&N);
    std::vector<long long> a(N+1);
    for(int i = 1 ; i <= N ; i++){
        scanf("%lld",&a[i]);
    }
    func(N, std::move(a));
    return 0;
}


Measured memory_bytes: 4980
#最初に入れれば入れるほど価値は小さくなる。つまり小さい順のリストを作り、小さい順に合成する。

n=int(input())

S=input().split()
s=list(S)

for i in range(n):
  s[i]=float(s[i])

#小さい順に並べ替え
list=sorted(s)

def mazemaze(a,b):
  return (a+b)/2

ans=list[0]

for i in range(n-1):
  ans=mazemaze(ans,list[i+1])

print(ans)
  




Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pint;

int num[4];
int main(){
    string s;
    cin>>s;
    rep(i,4){
        num[i]=s[i]-'0';
    }
    int ai;
    rep(i,8){
        int ans=num[0];
        rep(j,3){
            if(i>>j&1) ans+=num[j+1];
            else ans-=num[j+1];
        }
        if(ans==7){
            ai=i;break;
        }
    }
    stringstream ss;
    ss<<num[0];
    rep(i,3){
        ss<<(ai>>i&1?"+":"-")<<num[i+1];
    }
    cout<<ss.str()<<"=7"<<endl;
    return 0;
}


Measured memory_bytes: 256