akhauriyash/Code-Regression huggingface dataset:
from collections import defaultdict

n = int(input())
A = [int(input()) for _ in range(n)]

dic = defaultdict()

for i in range(n):
    dic[i+1] = A[i]

cnt, idx = 1, 0
val = dic[1]

while idx <= n:
    if val == 2:
        print(cnt)
        exit()
    val = dic[val]
    cnt += 1
    idx += 1
print(-1)


Measured memory_bytes: 23692
n, m = map(int, input().split())
a = []
b = []
c = []
d = []
for i in range(n):
    temp = list(map(int, input().split()))
    a.append(temp[0])
    b.append(temp[1])


for i in range(m):
    temp = list(map(int, input().split()))
    c.append(temp[0])
    d.append(temp[1])

ans = []

for i in range(n):
    min_dis = 10 ** 9
    for j in range(m):

        distance = abs(c[j] - a[i]) + abs(d[j] - b[i])

        #print("学生{}, {} チェックポイント{}, {}".format(a[i], b[i], c[j], d[j]))
        #print("距離番号{} = {}".format(j, distance))
        
        if min_dis > distance:
            min_dis = distance
            min_num = j
            #print("更新")
        
    ans.append(min_num)
    
for i in range(n):
    print(ans[i] + 1)


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

int main() {
  int N,K,I=1;
  int64_t Z=100000000000000;
  cin>>N>>K;
  vector<int> p(N);
  vector<int> m(N);
  for(int i=0;i<N;i++){
    cin>>p.at(i);
    if(i==0){
      m.at(i)=p.at(i);
    }
    else{
      m.at(i)=max(m.at(i-1),p.at(i));
    }
  }
  vector<int> v(N-1);
  for(int i=0;i<N-1;i++){
    if(i<N-K){
      v.at(i)=0;
      I*=N-1-i;
      I/=i+1;
    }
    else{
      v.at(i)=1;
    }
  }
  for(int i=0;i<I;i++){
    vector<int> q;
    vector<int> atai;
    for(int j=0;j<N-1;j++){
      if(v.at(j)==1){
        q.push_back(p.at(j+1));
        atai.push_back(j);
      }
    }
    int64_t A=0;
    int C=p.at(0);
    for(int j=0;j<K-1;j++){
      C=max(C+1,m.at(atai.at(j))+1);
      A+=max(0,C-q.at(j));
    }
    Z=min(A,Z);
    next_permutation(begin(v),end(v));
  }
  cout<<Z<<endl;
    
}



Measured memory_bytes: 256
function main(input) {
  const tmp = input.trim().split('\n').map((n) => parseInt(n, 10))
  if (tmp[4] - tmp[0] <= tmp[5]) {
    console.log('Yay!')
  } else {
    console.log(':(')
  }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'))

Measured memory_bytes: 29516
n,k = map(int,input().split())
a = list(map(int,input().split()))
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
if max(a)<k:
    print('IMPOSSIBLE')
else:
    g = a[0]
    for i in range(n):
        g = gcd(max(g,a[i]),min(g,a[i]))
    if k%g==0:
        print('POSSIBLE')
    else:
        print('IMPOSSIBLE')

Measured memory_bytes: 14224
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long int
#define ff first
#define ss second
#define pi pair<ll,ll>
#define maxn 1000002
#define mod 1000000007

//vector<ll>adj[maxn];
//ll vis[maxn];
//ll cc[maxn];

//ll curr_cc;



int main(){
	ll n;
	cin>>n;
	
	ll arr[n+1],ans=0;
	
	for(int i=1;i<=n;i++)cin>>arr[i];
	
	for(int i=1;i<=n;i+=2)if(arr[i]&1)ans++;
	
	cout<<ans;
}
	
	
	
	



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

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    int length = S.size();
    int answerBFirst = 0;
    for (int i = 0; i < length; i++)
    {
        if (i % 2 == 0 && S.at(i) == '1')
        {
            answerBFirst++;
        }
        else if (i % 2 == 1 && S.at(i) == '0')
        {
            answerBFirst++;
        }
    }
    int answerWFirst = 0;
    for (int i = 0; i < length; i++)
    {
        if (i % 2 == 0 && S.at(i) == '0')
        {
            answerWFirst++;
        }
        else if (i % 2 == 1 && S.at(i) == '1')
        {
            answerWFirst++;
        }
    }
    cout << min(answerBFirst, answerWFirst) << endl;
    return 0;
}


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

int main(){
  string a,b,c;
  ll n,i;
  cin >> n >> a >> b;
  c="";
  for(i=0;i<n;i++){
    c+=a.substr(i,1);
    c+=b.substr(i,1);
  }
  cout << c;
}

Measured memory_bytes: 256
a, b, c, x, y = map(int, input().split())
ans = 0
if c * 2 < a + b:
    m = min(x, y)
    ans += m * c * 2
    x -= m
    y -= m
if c * 2 < a:
    ans += x * c * 2
else:
    ans += x * a
if c * 2 < b:
    ans += y * c * 2
else:
    ans += y * b
print(ans)

Measured memory_bytes: 3064
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n,k=map(int,input().split())
a=list(map(int,input().split()))
m=0
if k==0:
    m=int(math.log2(1)+1)
else:
    m=int(math.log2(k)+1)
lst=[0]*m
for i in range(n):
    for j in range(m):
        if a[i]&(1<<j):
            lst[j]+=1
# print(lst)

ans=0
ans2=0
for i in range(m):
    if lst[m-i-1]<=n/2 and ans+pow(2,m-i-1)<=k:
        ans+=pow(2,m-i-1)
# print(ans)
# print(ans2)
for i in range(n):
    ans2+=ans^a[i]

print(ans2)

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

typedef long long int ll;
#define rep(i,n) for (int i = 0; i < (n); i++)
#define sz(x) int(x.size())
const ll mod = 1000000007;
int INF = 1001001001;

int main() {
    int n,m; cin >> n >> m;
    int n2 = (1<<n);
    int dp[m+1][n2]; rep(i,m+1) rep(j,n2) dp[i][j] = INF;
    dp[0][0] = 0;
    int a,b,c;
    rep(i,m) {
        cin >> a >> b;
        int score = 0;
        rep(j,b) {
            cin >> c;
            c--;
            c = 1<<c;
            score += c;
        }
        rep(j,n2) dp[i+1][j] = dp[i][j];
        rep(j,n2) {
            int jj = j | score;
            dp[i+1][jj] = min(dp[i][j]+a, dp[i+1][jj]);
        }
    }
    //rep(i,m+1) {rep(j,n2) printf("%d ", dp[i][j]);printf("\n");}
    if (dp[m][n2-1] == INF) cout << -1 << endl;
    else cout << dp[m][n2-1] << endl;
    return 0;
}


Measured memory_bytes: 19592
n, k, q = map(int, input().split(' '))
a = [0 for i in range(n)]
for i in range(q):
    a_i = int(input())
    a[a_i-1] += 1
for j in a:
    if k - q + j > 0:
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 51104
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define lli long long int
#define ulli unsigned long long int
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define pf pop_front()
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define loopl(i,a,b) for(lli i=a;i<b;i++) 
#define loop(i,a,b) for(int i=a;i<b;i++)
#define mod 1000000007
#define inf 100000000000000000
#define lld long double
#define pll pair<long long int,long long int>
#define vll vector<lli>
#define eps 0.000001
#define endl '\n'
#define mo 998244353
 
using namespace std ;
 
#define MAXN 100000 + 5 
 
typedef tree<lli,null_type,less<lli>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
 
vll v[MAXN] ;
bool vis[MAXN];
lli dp[MAXN][2];
 
void dfs(lli q)
{
    vis[q] = 1;
 
    lli ans1=1,ans2=1;
 
    for(auto x:v[q])
    {
        if(!vis[x])
        {
            dfs(x);
            ans1  = (ans1*((dp[x][0] + dp[x][1])%mod))%mod;
            ans2  = (ans2*dp[x][0])%mod ;
        }
    }

        dp[q][0] = ans1;
        dp[q][1] = ans2; 
    
 
}
 
 
int main()
{
///////////////////////////////////////////
    fastio;
///////////////////////////////////////////
 
    lli n;
    cin>>n;
 
    memset(dp,1,sizeof(dp));
    loopl(i,0,n-1) 
    {
        lli x,y;
        cin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }    
 
    dfs(1);
 
    cout<<(dp[1][0] + dp[1][1])%mod<<endl;
 
}

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

using namespace std;

typedef long long ll;

const ll INF = 1e15;
const ll MOD = 1e9 + 7;  

int main(){
    map<string,int> m;
    int N;
    cin >> N;
    m["AC"] = 0;
    m["WA"] = 0;
    m["TLE"] = 0;
    m["RE"] = 0;
    for(int i = 0; i < N; i++){
        string str;
        cin >> str;
        m[str]++;
    }
    int ans[4];
    auto ite = m.begin();
    for(; ite != m.end(); ite++){
        if(ite->first == "AC") ans[0] = ite->second;
        if(ite->first == "WA") ans[1] = ite->second;
        if(ite->first == "TLE") ans[2] = ite->second;
        if(ite->first == "RE") ans[3] = ite->second;
    }
    for(int i = 0; i < 4; i++){
        if(i == 0) cout << "AC x " << ans[i] << endl;
        if(i == 1) cout << "WA x " << ans[i] << endl;
        if(i == 2) cout << "TLE x " << ans[i] << endl;
        if(i == 3) cout << "RE x " << ans[i] << endl;

    }
    return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <functional>
#include <bitset>
#include <iomanip>
#include <cassert>
#include <float.h>
#include <random>

#define repeat(i,n) for (int i = 0; (i) < (n); ++ (i))
#define debug(x) cerr << #x << ": " << x << '\n'
#define debugArray(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge] << '\n'
#define debugArrayP(x,n) for(long long hoge = 0; (hoge) < (n); ++ (hoge)) cerr << #x << "[" << hoge << "]: " << x[hoge].first<< " " << x[hoge].second << '\n'

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef vector<int> vint;
typedef vector<ll> vll;
const int INF = INT_MAX;
const ll MOD = 998244353;

bool is_noprime[10010];
vint prime;

void init(){
  is_noprime[0]=is_noprime[1]=true;
  for(int i=2;i<=10010;i++)if(!is_noprime[i]){
    prime.push_back(i);
    for(int j=2*i;j<=10010;j+=i){
      is_noprime[j]=true;
    }
  }
}

ll gcd(ll x,ll y){
  return y? gcd(y,x%y):x;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  init();
  int N;cin>>N;
  vll a(N+1);
  repeat(i,N+1){
    cin>>a[i];
  }
  reverse(a.begin(),a.end());
  ll g=abs(a[N]);
  repeat(i,N){
    g = gcd(g,abs(a[i]));
  }
  repeat(i,N+1){
    a[i]/=g;
  }
  //cerr<<"!!!"<<endl;
  vll ans;
  for(int i=2;i*i<=g;i++){
    if(g%i==0){
      while(g%i==0){
        g/=i;
      }
      ans.push_back(i);
    }
  }
  if(g>1)ans.push_back(g);
  ll a0=abs(a[0]);
  repeat(i,prime.size()){
    int p=prime[i];
    if(a0%p==0){
      bool isok=true;
      repeat(j,p-1){
        ll c=0;
        for(int k=j;k<=N;k+=p-1){
          if(a[k]<0)c=(c-((-a[k])%p)+p)%p;
          else c=(c+a[k])%p;
        }
        isok &=!c;
      }
      if(isok){
        ans.push_back(p);
      }
    }
  }
  sort(ans.begin(),ans.end());
  ans.erase(unique(ans.begin(),ans.end()),ans.end());
  repeat(i,ans.size()){
    cout<<ans[i]<<endl;
  }
  return 0;
}


Measured memory_bytes: 512
c[60000],n;main(i,j){for(i=2;i*i<5e4;i++)for(j=i;!c[i]&&j<5e4;c[j+=i]=1);for(;scanf("%d",&j),*c=j;n=!printf("%d\n",n))for(i=2;i<=j/2;n+=!(c[i]+c[j-i++]));}

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

int main()
{
  int h, w;
  cin >> h >> w;
  
  char a[h+2][w+2];
  for(int i = 1; i < h+1; ++i){
    for(int j = 1; j < w+1; ++j){
      cin >> a[i][j];
    }
  }
  
  for(int i = 0; i < h+2; ++i){
    for(int j = 0; j < w+2; ++j){
      if(i == 0 || j == 0 || i == h+1 || j == w+1) cout << '#';
      else cout << a[i][j];
    }
    cout << endl;
  }
}

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

int main() {
    int N;
    cin >> N;
    long long sum = 0;

    for(int i = 1; i <= N; i++) {
        if(i % 3 != 0 && i % 5 != 0) {
            sum += i;
        }
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 3636
N, K = map(int, input().split())

if K == 0:
    print(N**2)
    exit()

c = 0 
for b in range(1, N+1):
    c += max(0, b-K)*(N//b) + max(0, (N%b)-K+1)
    # print(b, c)

print(c)

Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define FOR(i, k, n) for(int i = (k); i < (n); i++)
#define FORe(i, k, n) for(int i = (k); i <= (n); i++)
#define FORr(i, k, n) for(int i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(int i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;
using ll = long long;

const int INF = 1001001001;

int main(void){
  int n;
  cin >> n;
  vector<int> p(n);
  REP(i, n) cin >> p[i];
  sort(ALLr(p));
  p[0] /= 2;
  int ans = 0;
  REP(i, n) ans += p[i];
  cout << ans << endl;
  return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;

int main(){
    double x1,y1,x2,y2;
    cin >> x1 >> y1 >> x2 >> y2;

    printf("%.12lf\n",sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)));
    
    return 0;
}


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

// def
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
#define repeat(i, a, b) for (int i = (a); i < (b); i++)
#define revrepeat(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define revrep(i, n) for (int i = (n)-1; i >= 0; i--)
typedef long long ll;
typedef pair<ll, ll> P;
const int M = 1e9 + 7;
const int INF = 1e9;
const int MAX_V = 100 + 5;
const int MAX_N = 1e5 * 2 + 5;

using Graph = vector<vector<int>>;
vector<bool> seen;
vector<int> ans;

void dfs(const Graph &G, int v) {
    seen[v] = true; // v を訪問済にする
    // v から行ける各頂点 next_v について
    for (auto next_v : G[v]) {
        if (seen[next_v])
            continue; // next_v が探索済だったらスルー
        ans[next_v] += ans[v];
        dfs(G, next_v); // 再帰的に探索
    }
}

int main() {
    int n, q;
    cin >> n >> q;
    Graph G(n);
    seen.assign(n, false);
    ans.assign(n, 0);
    rep(i, n - 1) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        G[a].push_back(b);
    }
    rep(i, q) {
        int a, b;
        cin >> a >> b;
        a--;
        ans[a] += b;
    }
    dfs(G, 0);
    rep(i, n) {
        cout << ans[i] << " ";
    }
    cout << endl;
}


Measured memory_bytes: 23552
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int a, b;
    cin >> a >> b;
    string sa = to_string(a);
    string sb = to_string(b);
    string t = sa + sb;
    int n = stoi(t);
    for(int i = 1; i <= 1000; i++){
        if(i * i == n){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl
#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 100005;

struct edge
{
    int to,cost;
};

vector<edge> G[MAX_N];
bool flag[MAX_N];
int d[MAX_N];

bool dfs(int u,int dist){
    d[u] = dist;
    flag[u] = true;
    for(auto v : G[u]){
        if(!flag[v.to]){
            if(dfs(v.to,dist+v.cost)){
                return true;
            }
        }else{
            if(d[v.to] != dist+v.cost){
                return true;
            }
        }
    }
    return false;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    rep(i,m){
        int a,b,c;
        cin >> a >> b >> c;
        G[a-1].pb((edge){b-1,c});
        G[b-1].pb((edge){a-1,-c});
    }
    rep(i,n){
        if(!flag[i]){
            if(dfs(i,0)){
                cout << "No\n";
                return 0;
            }
        }
    }
    cout << "Yes\n";
    return 0;
}


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

int main(){
    string n;
    cin >> n;
    if(n[n.size()-1] == '3'){
        printf("bon\n");
    }
    else if(n[n.size()-1] == '0' ||n[n.size()-1] == '1' || n[n.size()-1] == '6'||n[n.size()-1] == '8'){
        printf("pon\n");
    }
    else{
        printf("hon\n");
    }
    return 0;

}

Measured memory_bytes: 3624
package main

import (
	"fmt"
)

func main(){
	var r, c, sum, num int
	fmt.Scan(&r, &c)
	line := make([][]int, r)
	for i:=0; i<r; i++{
		line[i] = make([]int, c+1)
	}
	for i:=0; i<r; i++{
		sum = 0
		for j:=0; j<c; j++{
			fmt.Scan(&num)
			line[i][j] = num
			fmt.Printf("%d ", num)
			sum += num
		}
		line[i][c] = sum
			fmt.Printf("%d\n", sum)
	}
	for i:=0; i<c+1; i++{
		sum = 0
		for j:=0; j<r; j++{
			sum += line[j][i]
		}
		fmt.Print(sum)
		if i != c {
			fmt.Print(" ")
		} else {
			fmt.Print("\n")
		}
	}
}


Measured memory_bytes: 1956
#include<stdio.h>
int a[1111],b[1111],c[1111],d[1111],p[1111],i,j,x,y,z;
main(){
  for(;scanf("%d%d%d",a,b,c)&&(*a+=*b+*c);i=0){
    for(scanf("%d",p);i++<*p;scanf("%d%d%d%d",a+i,b+i,c+i,d+i),p[i]=2);
    for(;--i;)
      for(j=0;j++<*p;d[j]?p[a[j]]=p[b[j]]=p[c[j]]=1:(x=p[a[j]]&1)&(y=p[b[j]]&1)?p[c[j]]=0:x&(z=p[c[j]])?p[b[j]]=0:y&z?p[a[j]]=0:0);
    for(;i<*a;printf("%d\n",p[++i]));
  }return 0;
}

Measured memory_bytes: 620
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,top,st[101010];
int id[101010],bok[101010];
long long k,ans[101010],a[101010];
void change(int x)
{
	top=0;
	st[++top]=x;bok[x]=1;
	while(!bok[id[x]]) bok[id[x]]=1,st[++top]=x=id[x];
	int k1=k%top;
	for(int i=1;i<=top-k1;i++)
		ans[st[i]]=a[st[i+k1]]-a[st[i+k1]-1];
	for(int i=top-k1+1;i<=top;i++)
		ans[st[i]]=a[st[i-top+k1]]-a[st[i-top+k1]-1];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]),id[i]=i;
	scanf("%d%lld",&m,&k);
	for(int i=1,x;i<=m;i++)
	{
		scanf("%d",&x);
		swap(id[x+1],id[x]);
	}
	for(int i=1;i<=n;i++)
	if(!bok[i]) change(i);
	printf("%lld.0\n",a[1]);
	for(int i=2;i<=n;i++)
		printf("%lld.0\n",a[i]=a[i-1]+ans[i]);
	return 0;
}

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

using ll = long long;
using ull = unsigned long long;
using st = string;
using ch = char;
using db = double;
using bl = bool;
using vll = vector<long long>;
using vdb = vector<db>;
using vst = vector<st>;
using vch = vector<char>;
using vbl = vector<bl>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
#define rep(i, m, n) for (ll i = (ll)(m); i < (ll)(n); i++)
#define vrep(i, vec) for(auto& i : vec)
#define vin(vec) for(auto& i : vec) cin >> i
#define all(v) v.begin(), v.end()
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;}
const ll mod = 1000000007;
const ll inf = 1LL << 60;
const db pi = acos(-1.0L);

vbl seen, finished;
ll pos = -1;
stack<ll> hist;

void dfs(vvll &graph, ll v, ll p){
	seen.at(v) = true;
	hist.push(v);
	vrep(nv, graph.at(v)){
		if(nv == p) continue;
		if(finished.at(nv)) continue;
		if(seen.at(nv) && !finished.at(nv)){
			pos = nv;
			return;
		}
		dfs(graph, nv, v);
		if(pos != -1) return;
	}
	hist.pop();
	finished.at(v) = true;
}

int main(){
  ll n;
	cin >> n;
	vvll graph(n);
	rep(i, 0, n){
		ll u, v;
		cin >> u >> v;
		u--; v--;
		graph.at(u).push_back(v);
		graph.at(v).push_back(u);
	}
	ll q;
	cin >> q;
	vll a, b;
	rep(i, 0, q){
		ll aa, bb;
		cin >> aa >> bb;
		aa--; bb--;
		a.push_back(aa); b.push_back(bb);
	}

	seen.assign(n, false); finished.assign(n, false);
	dfs(graph, 0, -1);
	set<ll> cycle;
	while(hist.size()){
		cycle.insert(hist.top());
		if(hist.top() == pos) break;
		hist.pop();
	}

	rep(i, 0, q) {
		if(cycle.count(a.at(i)) && cycle.count(b.at(i))) cout << 2 << endl;
		else cout << 1 << endl;
	}
}


Measured memory_bytes: 20544
#include<bits/stdc++.h>
#define ll long long
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
 
int main(){

    int n, m, sum = 0;
    cin >> n >> m;

    int inp[m];
    
    for (int i = 0; i < m; i++)
    {
        cin >> inp[i];
        sum = sum + inp[i];
    }

    if(sum > n)
    {
        cout << -1;
    }

    if(sum <= n)
    {
        cout << n-sum;
    }

	return 0;
}

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

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

using namespace std;

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

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

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

/* Macros reg. ends here */

const ll INF = 1LL << 50;

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

  ll n;
  cin >> n;

  vll memo(n + 1, 0);
  repLRE(i, 1, n) {
    for (ll j = i; j <= n; j += i) {
      memo[j]++;
    }
  }

  ll ans = 0;
  repLRE(i, 1, n) ans += i * memo[i];

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 81396
#include <iostream>
#include <cmath>
 
int main(){
    int num;
    std::cin >> num;
     
    for(int i = 0; i < num; ++i){
        double xa, xb, ya, yb, ra, rb;
        std::cin >> xa >> ya >> ra >> xb >> yb >> rb;
        double d = hypot(xa - xb, ya - yb);
         
        int answer = 1;
        if(ra + rb < d){
            answer = 0;
        }
        else if(ra - rb > d){
            answer = 2;
        }
        else if(rb - ra > d){
            answer = -2;
        }
        std::cout << answer << std::endl;
    }
    return 0;
}

Measured memory_bytes: 1244
N,K = list(map(int,input().split()))
S = input()
n = []
p = S[0]
c = 1
for s in S[1:]:
    if s != p:
        n.append(c)
        p = s
        c = 0
    c+=1
n.append(c)
ans = max(n)
sum_n = [0]
for i in n:
    sum_n.append(i+sum_n[-1])
if S[0]=="0":
    for i in range(1,len(n)-2*K+1,2):
        ans = max(ans,sum_n[min(i+2*K+1,len(sum_n)-1)]-sum_n[i])
    sum_n.pop(1)
    n.pop(0)
    K -=1
for i in range(0,len(n)-2*K+1,2):
    ans = max(ans,sum_n[min(i+2*K+1,len(sum_n)-1)]-sum_n[i])
if (len(n)-2*K+1)<=0:
    ans = max(ans,sum_n[-1])
print(ans)

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

ll N, M;
vector< vector<ll> > E;
vector<bool> visited;

ll dfs(ll v) {
  if(visited[v]) return 0;
  visited[v] = true;

  ll ret = 1;
  for(ll u : E[v]) ret += dfs(u);

  return ret;
}

int main(void) {
  cin >> N >> M;
  E.resize(N);
  REP(i, 0, M) {
    ll A, B;
    cin >> A >> B; A--; B--;
    E[A].push_back(B);
    E[B].push_back(A);
  }

  visited.assign(N, false);

  ll s0 = dfs(0);
  ll s1 = dfs(1);
  ll s2 = N - s0 - s1;

  ll l = max(s0, s1) + s2;
  ll s = min(s0, s1);

  cout << l * (l - 1) / 2 + s * (s - 1) / 2 - M << endl;
}


Measured memory_bytes: 8832
#include<bits/stdc++.h>
#define maxn 500010
#define INF 1000000100
using namespace std;
int flag,n;
int a[maxn];

void Merge(int l,int m,int r)
{
    int n1=m-l;
    int n2=r-m;
    int b[n1+1],c[n2+1];
    for(int i=0;i<n1;i++)
        b[i]=a[l+i];
    for(int i=0;i<n2;i++)
        c[i]=a[m+i];
    int i=0,j=0;
    b[n1]=INF;
    c[n2]=INF;
    for(int k=l;k<r;k++)
    {
        flag++;
        if(b[i]<=c[j])
            a[k]=b[i++];
        else
            a[k]=c[j++];
    }
}
void MergeSort(int l,int r)
{
  if(l+1<r)
  {
      int m=(l+r)/2;
      MergeSort(l,m);
      MergeSort(m,r);
      Merge(l,m,r);
  }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    int l,r,m;
    l=0;
    r=n;
    flag=0;
    MergeSort(l,r);
    for(int i=0;i<n;i++)
        printf("%d%c",a[i],i==n-1?'\n':' ');
    printf("%d\n",flag);
    return 0;
}

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

int main()
{
  int N, i, j, k;
  cin >> N;
  vector<int> vec(N + 1, 0);
  
  i = 1;
  while (i <= N)
  {
    int	a;
    cin >> a;
    
    vec.at(i) = a;
    //cout << vec.at(i) << endl;
    i++;
  }
  //cout << vec.at(vec.at(1)) << endl;
  k = 1;
  j = vec.at(1);
  while (k < N && j != 2)
  {
    j = vec.at(j);
    k++;
  }
  if (j == 2)
    cout << k << endl;
  else
    cout << -1 << endl;
  return (0);
}


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

using namespace std;

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

int main(){
 int h,w;
  cin >> h >> w;
  
  int c[10][10];
  rep(i,10){
   rep(j,10) cin >> c[i][j];
  }
  
  rep(k,10){
  rep(i,10){
   rep(j,10) c[i][j]=min(c[i][j],c[i][k]+c[k][j]);
  }
  }
  
  int res=0;
  rep(i,h){
   rep(j,w){
   int a;
     cin >> a;
    res+=max(0,c[a][1]);
   }
  }
 cout << res << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

int manhattan(int x1, int y1, int x2, int y2) {  // (x1, y1) と (x2, y2) のマンハッタン距離
    return abs(x1 - x2) + abs(y1 - y2);
}

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

    vector<int> x(n), y(n), h(n);
    rep(i, n) {
        cin >> x[i] >> y[i] >> h[i];
    }

    rep(cx, 101) {
        rep(cy, 101) {

            int H;
            rep(i, n) {
                if(h[i] > 0) {
                    H = h[i] + manhattan(x[i], y[i], cx, cy);
                    break;
                }
            }

            int flag = 0;
            rep(i, n) {
                if(h[i] > 0) {
                    if( H != h[i] + manhattan(x[i], y[i], cx, cy) ) {
                        flag = 1;
                        break;
                    }
                }
                else if(h[i] == 0) {
                    if( H > manhattan(x[i], y[i], cx, cy) ) {
                        flag = 1;
                        break;
                    }
                }
            }

            if(!flag) {
                cout << cx << " " << cy << " " << H << endl;
                return 0;
            }

        }
    }

    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 = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;

const int MOD = 1000000007;

int main() {
    int D, G;
    cin >> D >> G;
    vector<int> p(D);
    vector<int> c(D);
    rep(i, D) cin >> p[i] >> c[i];

    int ans = 100100100;
    rep(i, 1 << D) {
        int score = 0;
        int count = 0;

        for (int j = 0; j < D; j++) {
            if (i >> j & 1) {
                score += p[j] * 100 * (j + 1) + c[j];
                count += p[j];
            }
        }

        for (int j = D - 1; j >= 0; j--) {
            if (score >= G) break;
            if (i >> j & 1) continue;

            float point = 100 * (j + 1);
            int needCount = ceil((G - score) / point);
            if (needCount > p[j] - 1) {
                needCount = p[j] - 1;
            }

            score += needCount * 100 * (j + 1);
            count += needCount;
        }


//        cout << bitset<8>(i) << endl;
//        cout << score << " " << count << endl;
        if (score >= G) {
            chmin(ans, count);
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace A
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var N = Console.ReadLine();
            Console.WriteLine(N.Contains('9') ? "Yes" : "No");
        }
    }
}


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


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

    std::vector<int> union_find(N);
    for (int i = 0; i < N; i++) {
        union_find[i] = i;
    }

    auto find_root = [&union_find](int idx) {
        std::vector<int> inter;
        while (union_find[idx] != idx) {
            inter.emplace_back(idx);
            idx = union_find[idx];
        }
        for (auto i : inter) {
            union_find[i] = idx;
        }
        return idx;
    };

    int a, b;
    for (int i = 0; i < M; i++) {
        std::cin >> a >> b;
        a--; b--;
        int root_a = find_root(a);
        int root_b = find_root(b);
        if (root_a != root_b) {
            union_find[root_a] = root_b;
        }
    }
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        int root = find_root(i);
        if (root == i) {
            cnt++;
        }
    }
    std::cout << cnt - 1 << std::endl;
}


Measured memory_bytes: 3760
#include <cstdio>
#include <algorithm>

using namespace std;


const int MAX_N = 105;
const int MAX_V = 100005;
const long long INF = 1000000000000;

typedef long long ll;

int n,W;
ll dp[MAX_N][MAX_V];

ll mmin(ll a, ll b)
{
	if (a<0&&b<0)
		return -INF;
	if (a<0)
		return b;
	if (b<0)
		return a;
	return min(a,b);
}

int main()
{
	scanf("%d %d",&n,&W);
	for (int j=1; j<MAX_V; j++)
		dp[0][j]=-INF;
	for (int i=1; i<=n; i++)
	{
		int w,v;
		scanf("%d %d",&w,&v);
		for (int j=0; j<MAX_V; j++)
			if (j-v>=0)
				dp[i][j]=mmin(dp[i-1][j],w+dp[i-1][j-v]);
			else
				dp[i][j]=dp[i-1][j];
	}
	for (int v=MAX_V-1; v>=0; v--)
		if (dp[n][v]>=0&&dp[n][v]<=W)
		{
			printf("%d\n",v);
			break;
		}
	return 0;
}


Measured memory_bytes: 80000
#include"bits/stdc++.h"
using namespace std;
int main(){
	long long n,ans=0,temp;
	vector<long long> x;
	cin>>n;
	for(int i=0;i!=n;++i){
		cin>>temp;
		x.push_back(temp);
	}
	for(int i=0;i!=n-1;++i){
		ans+=x[i]/2;
		x[i]%=2;
		if(x[i] && x[i+1]){
			++ans;
			--x[i+1];
		}
	}
	ans+=x.back()/2;
	cout<<ans;
}

Measured memory_bytes: 1400
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect

def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


def LIR(n):
    return [LI() for i in range(n)]


def SR(n):
    return [S() for i in range(n)]


def LSR(n):
    return [LS() for i in range(n)]


sys.setrecursionlimit(1000000)
mod = 1000000007


def solve():
    n, m = LI()
    h = LI()
    li = LIR(m)
    flag_list = [False] * n
    for i in range(m):
        if h[li[i][0]-1] > h[li[i][1]-1]:
            flag_list[li[i][1]-1] = True
        elif h[li[i][0]-1] < h[li[i][1]-1]:
            flag_list[li[i][0]-1] = True
        else:
            flag_list[li[i][0]-1] = True 
            flag_list[li[i][1]-1] = True
    print(flag_list.count(False))

    return


if __name__ == "__main__":
    solve()


Measured memory_bytes: 90412
#include <cstdio>
#include <algorithm>

using namespace std;

int a[100000];
int b[100000];

int main() {
    int A, B, m, ans = 1e9, ma = 1e9, mb = 1e9, i;
    
    scanf("%d %d %d", &A, &B, &m);
    
    for (i = 0; i < A; i++) {
        scanf("%d", &a[i]);
        
        ma = min(ma, a[i]);
    }
    
    for (i = 0; i < B; i++) {
        scanf("%d", &b[i]);
        
        mb = min(mb, b[i]);
    }
    
    ans = min(ans, ma + mb);
    
    for (i = 0; i < m; i++) {
        int x, y, c;
        
        scanf("%d %d %d", &x, &y, &c);
        
        ans = min(ans, a[x - 1] + b[y - 1] - c);
    }
    
    printf("%d\n", ans);
    
    return 0;
}


Measured memory_bytes: 896
# -*- coding: utf-8 -*-


def main():
    n, a, b = map(int, input().split())

    if a > b or (n == 1 and a != b):
        print(0)
    else:
        print(max(0, b - a) * (n - 1) + (a - b) + 1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include<stdio.h>
int main(void){
int i,j,k,n,b,f,r,v,data[4][3][10]={0};
scanf("%d\n",&n);
for(i=0;i < n;i++){
scanf("%d %d %d %d\n",&b ,&f ,&r ,&v);
data[b-1][f-1][r-1] += v;
}
for(i=0;i < 4;i++){
for(j=0;j < 3;j++){
for(k=0;k < 10;k++){
printf(" %d",data[i][j][k]);
if (k == 9){
printf("\n");
}
}
if (j == 2 && i != 3){
printf("####################\n");
}
}
}
return 0;
}

Measured memory_bytes: 616
#include <bits/stdc++.h>
using namespace std;
//型に気を付けよう

#define rep(i,n) for(int i=0;i<n;i++)
long long SUM(vector<int> Vec){//配列の和
  int n=Vec.size();
  int sum= 0;
  for(int i=0;i<n;i++){
    sum+=Vec[i];
  }
  return sum;}
//桁数指定　cout << fixed << setprecision(2)
int main() {
        const double pi=3.1415926535;
  int n;
  cin>>n;
  int m;
  cin>>m;
  vector<int> v(m);
  rep(i,m)cin>>v[i];
  int ans=n-SUM(v);
  if(ans<0)ans=-1;
  cout<<ans;
}

Measured memory_bytes: 3676
#create date: 2020-05-02 21:18

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    a, b, n = na()
    x = min(n, b - 1)
    ans = a * x // b - a * ( x // b)
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 9192
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define Cout(s) cout << s << endl;
using ll = long long;
using P = pair<int, int>;

const ll INF = 1ll << 60;
ll MOD = 1e9 + 7;

int main()
{

    int a, b, t;
    cin >> a >> b >> t;

    Cout(t / a * b);
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#include<utility>
#include<climits>
#define MAX 1000000
#define pb push_back
#define f first
#define s second

using namespace std;

typedef pair<int, int> pii;
typedef map<int, int> mapint;

int32_t main(){
	int n;
	cin>>n;
	int maxh = 0;
	int ans = 0;
	for(int i=0; i<n; i++) {
		int temp;
		cin>>temp;
		if(temp>=maxh) ++ans;
		maxh = max(temp, maxh);
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int a,b,c,d;
  scanf("%d %d %d %d",&a,&b,&c,&d);
  for(int i=0;i<100;i++){
    c=c-b;
    if(c<=0){
      printf("Yes\n");
      break;
    }
    a=a-d;
    if(a<=0){
      printf("No\n");
      break;
    }
  }
}
  


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

int main()
{
    int N;cin >> N;
    string S;
    int ans=0;
    map<string,int> input;
    for (int i=0;i<N;i++)
    {
        cin >> S;
        if (input[S]==0)
        {
            ans++;
            input[S]=1;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 19228
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	long double f[55];
	cin>>n;
	for(int i=1;i<=n;i++) cin>>f[i];
	sort(f+1,f+n+1);
	long double ans=f[1];
	for(int i=2;i<=n;i++)
	ans=(ans+f[i])/2.0;
	printf("%.13Lf",ans);
}

Measured memory_bytes: 256
import scala.io.StdIn

case class Process(name: String, time: Int)

object Main extends App {
  val nq = StdIn.readLine().split(" ").toList.map(_.toInt)
  val n = nq.head
  val q = nq.last

  val queue = new scala.collection.mutable.Queue[Process]
  for (i <- 1 to n) {
    val tmp = StdIn.readLine().split(" ").toList
    queue += Process(tmp.head, tmp.last.toInt)
  }

  var sumOfTime = 0

  while (queue.nonEmpty) {
    val p = queue.dequeue()
    if (p.time > q) {
      sumOfTime += q
      queue += Process(p.name, p.time - q)
    } else {
      sumOfTime += p.time
      println(s"${p.name} $sumOfTime")
    }
  }
}

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

int main(){
  int num,ans;
  string s;
  cin>>num;
  ans=num;
  while(1){
    cin>>s;
    if(s=="=")break;
    cin>>num;
    if(s=="+")ans+=num;
    if(s=="-")ans-=num;
    if(s=="*")ans*=num;
    if(s=="/")ans/=num;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 1204
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)

	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt64(scanner)
	m := getNextInt64(scanner)

	fmt.Fprintln(writer, solve(n, m))

	writer.Flush()
}

func solve(n, m int64) int64 {
	if n == 1 && m == 1 {
		return 1
	}
	if n == 1 {
		return m - 2
	}
	if m == 1 {
		return n - 2
	}
	return (n - 2) * (m - 2)
}


Measured memory_bytes: 640
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
const int maxn = 4e5+5;
int n;
int en[maxn],nt[maxn],la[maxn],owo;
void adg(int x,int y) {
	en[++owo]=y; nt[owo]=la[x]; la[x]=owo;
}
int sta[maxn],tp;
int vis[maxn],tim;
int orz[maxn],oo,fr[maxn];
bool FUCK;
void dfs(int x) {
	if(vis[x]==tim) {
		int y;
		do{
			y = sta[tp--];
			orz[++oo] = y;
		}while(y!=x);
		FUCK = 1;
		return;
	}
	vis[x] = tim;
	sta[++tp] = x;
	for(int it=la[x];it;it=nt[it]) {
		int y = en[it];
		if(vis[y]==tim||(!vis[y]))dfs(y);
		if(FUCK) return;
	}
	--tp;
}
int val[maxn];
void dds(int x) {
	vector<int>ve; ve.push_back(0);
	for(int it=la[x];it;it=nt[it]) {
		int y = en[it];
		if(vis[y]) continue;
		dds(y);
		while(val[y]>=ve.size()) ve.push_back(0);
		ve[val[y]] = 1;
	}
	ve.push_back(0);
	int ss = ve.size();
	for(int i=0;i<ss;i++) if(!ve[i]) { val[x] = i; return; }
}
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		int x; scanf("%d",&x);
		adg(x,i);
	}
	for(int i=1;i<=n;i++) {
		if(!vis[i]) {
			++tim;
			dfs(i);
		}
		if(FUCK) break;
	}
	for(int i=1;i<=n;i++) vis[i] = 0;
	if( !(oo&1) ) 
	{ 
		puts("POSSIBLE"); 
		return 0; }
	for(int i=1;i<=oo;i++) vis[orz[i]] = 1;
	for(int i=1;i<=oo;i++) {
		dds(orz[i]);
	}
	bool flag = 1;
	for(int i=1;i<oo;i++) {
		if(val[orz[i]]!=val[orz[i+1]]) { flag = 0; break; }
	}
	if(flag) puts("IMPOSSIBLE"); 
	else puts("POSSIBLE");
}

Measured memory_bytes: 13056
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int day, num;
  cin >> day >> num;

  vector<int> weight(num);

  for(int i=0; i<num; i++) {
    cin >> weight.at(i);
  }

  int result = day;

  for(int i=0; i<num; i++) {
    result -= weight.at(i);
  }

  if(result<0) cout << -1 << endl;
  else cout << result << endl;

  return 0;
}


Measured memory_bytes: 3644
import itertools
import math
N=int(input())
P=tuple(map(int,input().split()))
Q=tuple(map(int,input().split()))

l=[ i+1 for i in range(N) ]
Per=itertools.permutations(l,N)
Per=list(Per)
num=[-1,-1]
for i in range(math.factorial(N)):
  if Per[i]==P:
    num[0]=i
  if Per[i]==Q:
    num[1]=i
print(abs(num[0]-num[1]))

Measured memory_bytes: 7972
#include<stdio.h>
int main(void){
  int N,M,L[100001],R[100001],min=100001,max=0,how;
  scanf("%d %d",&N,&M);
  for(int i=0;i<M;i++){
  scanf("%d %d",&L[i],&R[i]);
  if(min>R[i]){
  min=R[i];
  }
  if(max<L[i]){
  max=L[i];
  }
  }
  how=min-max+1;
  if(max<=min){
    printf("%d",how);
  
  }else{printf("0");}
  return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
int main(void){
    
    int n;
    long long a[200001]={};
    long long total=0;
    int ans=0;
    long long tt=0;
    int tmpi=0;
    
    cin >> n;
    
    for(int i=1; i<=n; i++){
        
        cin >> a[i];
        total += a[i];
        
    }
    
    
    
    for(int i=1; i<=n; i++){
        
        if(tt*2+a[i]*2==total){
            
            cout << "0" << endl;
            return 0;
            
        } else if(tt*2+a[i]*2>total){
            
            tmpi = i;
            break;
            
        }
        
        tt += a[i];
        
    }
    
    ans = total - tt - a[tmpi] - tt;
    ans = abs(ans);
    ans -= a[tmpi];
    ans = abs(ans);
    
    cout << ans << endl;

    return 0;
    
}

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

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int a,b,c,x,y;
  cin>>a>>b>>c>>x>>y;
  Int ans=a*x+b*y;
  for(Int i=0;i<=x;i++){
    Int j=(x-i)*2;
    Int k=max(0LL,y-(j/2));
    chmin(ans,a*i+c*j+b*k);
  }
  for(Int k=0;k<=y;k++){
    Int j=(y-k)*2;
    Int i=max(0LL,x-(j/2));
    chmin(ans,a*i+c*j+b*k);
  }
  cout<<ans<<endl;
  return 0;
}


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

using namespace std;

int main(){
  string a,b,c;
  cin>>a>>b>>c;
  cout<<a.at(0)<<b.at(0)<<c.at(0)<<endl;



  return 0;
  }


Measured memory_bytes: 256
/*
    2014.07.04 1250~1255
    C language Lecture week ∞
*/

#include <stdio.h>
#include <string.h>

int rtri_chk ( int a, int b, int c );

int main (void) {
    
    // 三角形の辺の長さ用
    int a;
    int b;
    int c;
    
    int max;
    
    scanf ( "%d", &max );
    
    for ( int cnt = 0; cnt < max; cnt ++ ) {
        scanf ( "%d", &a );
        scanf ( "%d", &b );
        scanf ( "%d", &c );
        if ( rtri_chk ( a, b, c ) ) {
            printf ( "YES\n" );
        } else {
            printf ( "NO\n" );
        }
    }
    
    return 0;
    
}

int rtri_chk ( int a, int b, int c ) {
    
    int a2 = a * a;
    int b2 = b * b;
    int c2 = c * c;
    if ( a2 == b2 + c2 || b2 == a2 + c2 || c2 == a2 + b2 ) {
        return 1;
    } else {
        return 0;
    }
    
}

Measured memory_bytes: 1008
#include <iostream>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <algorithm>

using namespace std;
int main() {
    int l,r;
    cin >> l >> r;

    int x, y;
    int z;
    int ans = 2019;
    if (r - l > 2020) {
        for (int i = 0; i <= 2019; i++) {
            for (int j = i + 1; j <= 2019; j++) {
                x = i % 2019;
                y = j % 2019;
                z = (x * y) % 2019;
                if (ans > z) {
                    ans = z;
                }
            }
        }
    }
    else
    {
        for (int i = l; i <= r; i++) {
            for (int j = i + 1; j <= r; j++) {
                x = i % 2019;
                y = j % 2019;
                z = (x * y) % 2019;
                if (ans > z) {
                    ans = z;
                }
            }
        }
    }
    
    
    cout << ans;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
const ll MOD = 1000000007;
const int nmax = 8;
bool graph[nmax][nmax];

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

ll lcm(ll a, ll b)
{
    ll g = gcd(a, b);
    return a / g * b;
}

ll mulMod(ll a, ll b)
{
    return (((a % MOD) * (b % MOD)) % MOD);
}
int dfs(int v, ll N, bool visited[nmax])
{
    bool all_visited = true;

    for (int i = 0; i < N; i++)
    {
        if (!visited[i])
        {
            all_visited = false;
        }
    }

    if (all_visited)
    {
        return 1;
    }
    int ret = 0;
    for (size_t i = 0; i < N; i++)
    {
        if (!graph[v][i])
        {
            continue;
        }
        if (visited[i])
        {
            continue;
        }

        visited[i] = true;
        ret += dfs(i, N, visited);
        visited[i] = false;
    }

    return ret;
}

void solve(long long x)
{
    if (x < 1200)
    {
        cout << "ABC" << endl;
    }
    else
    {
        cout << "ARC" << endl;
    }
}

int main()
{
    long long x;
    scanf("%lld", &x);
    solve(x);
    return 0;
}


Measured memory_bytes: 256
n = int(input())
cnt = [0]*(n+1)
for i in range(2,n+1):#2~n
    s = i
    while s != 1:
        for j in range(2,n+1):#2~n
            if s % j == 0:
                s //= j 
                cnt[j] += 1
                break

c = 1
for i in range(2,n+1):
    c *=(cnt[i]+1)
    c %=(10**9+7)

print(c)

Measured memory_bytes: 3060
#include <string.h>

int main(void) {

    // read inputs
    char s[101], p[101];
    scanf("%s\n%s\n", s, p);

    // search
    for (int i = 0; i < strlen(s); i++) {
        for (int j = 0;; j++) {

            // loop index
            int k = i + j;
            if (k > strlen(s) - 1) k -= strlen(s);

            // unmatched, continue from next character
            if (s[k] != p[j]) break;

            // found
            if (j == strlen(p) - 1) {
                puts("Yes");
                return 0;
            }
        }
    }
    // not found
    puts("No");
}


Measured memory_bytes: 2136
from itertools import combinations
from collections import Counter
N = int(input())
s = [input()[0] for i in range(N)]
cnt = {k:v for k,v in Counter(s).items()}
ans = 0
for x,y,z in [c for c in combinations('MARCH',3)]:
    try:
        ans += cnt[x]*cnt[y]*cnt[z]
    except:
        pass
print(ans)


Measured memory_bytes: 4260
#include <cstdio>
#include <cmath>
#include <cstdint>
#include <cinttypes>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

using namespace std;
static const long k10E7 = 1000000007;

uint64_t gcd(uint64_t a, uint64_t b)
{
    uint64_t big = max(a,b);
    uint64_t small = min(a,b);
    
    uint64_t r = big % small;
    while(r != 0){
        big = small;
        small = r;
        r = big % small;
    }
    return small;
}

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

    uint64_t multiple_c = b / c - (a - 1) / c;
    uint64_t multiple_d = b / d - (a - 1) / d;
    uint64_t lcm = c * d / gcd(c, d);
    uint64_t multiple_cd = b / lcm - (a - 1) / lcm;

    uint64_t ans = b - a + 1;
    ans -= multiple_c;
    ans -= multiple_d;
    ans += multiple_cd;

    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 256