akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef unsigned long ul;
typedef pair<ul, ul> P;
map<int, int> dp;
#define REP(i, n) for (int i = 0; i < n; i++)

ul N, M, T;
std::string S;
ul gcd(ul m, ul n) {
  if ((0 == m) || (0 == n)) return 0;
  while (m != n) {
    if (m > n)
      m = m - n;
    else
      n = n - m;
  }
  return m;
}  // gcd

ul lcm(ul m, ul n) {
  if ((0 == m) || (0 == n)) return 0;

  return ((m / gcd(m, n)) * n);  // lcm = m * n / gcd(m,n)
}  // lcm

ul A, B, K;
ul eat(ul& num) {
  auto ans = 0;
  if (num % 2 != 0) {
    ans = (num - 1) / 2;
    num -= 1 + ans;
  } else {
    ans = num / 2;
    num -= ans;
  }
  return ans;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> A >> B >> K;
  bool flag = true;
  ul cnt = 0;
  while (cnt != K) {
    if (flag) {
      B += eat(A);
    } else {
      A += eat(B);
    }
    ++cnt;
    flag = !flag;
  }
  cout << A << " " << B << endl;
}

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


int main(){
  string s;
  ll k;
  cin >> s >> k;
  ll n = sz(s);
  vector<ll> seq(0);

  ll cnt = 1;
  rep(i,n){
    if(i == n-1) {
      seq.push_back(cnt);
      continue;
    }
    if(s[i] == s[i+1]) cnt++;
    else{
      seq.push_back(cnt);
      cnt = 1;
    }

  }

  ll ns = seq.size();

  ll ans = 0;
  if(s[0] != s[n-1]){
    for(auto s : seq){
      ans += s/2;
    }
    ans *= k;
  }

  else if(ns == 1){
    ans = seq[0]*k;
    ans /= 2;
  }

  else {
    for(int i = 0; i < ns; i++){
      if(i == 0 || i == ns-1) continue;
      ans += seq[i]/2;
    }
    ans *= k;
    ans += seq[0]/2 + seq.back()/2;
    int add = (seq[0]+seq.back())/2;
    ans += add*(k-1);
  }

  cout << ans << endl;
  
}


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

int main() {
    int a, b, c, d;
    int sum = 0;

    cin >> a >> b >> c >> d;

    if(a > b) {
        sum += b;
    }
    else {
        sum += a;
    }

    if(c > d) {
        sum += d;
    }

    else {
        sum += c;
    }

    cout << sum << endl;
}

Measured memory_bytes: 256
#include<iostream>
#define ll long long int
using namespace std;
int main()
{
  ll n, W;
  cin >> n >> W;
  
  ll i, j;
 ll v[200];ll w[200];
  ll dp[100005]={0};
  
  for ( i=0; i < n; i++)
  {
   cin >> w[i];cin>>v[i]; 
  }
  
  for ( i=0; i < n; i++)
  {
    for ( j=W; j >=w[i];j--)
      dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
  }
  cout << dp[W];
}

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

int main() {
    int k, s; cin >> k >> s;
    long long ans = 0;
    for (int i=0; i<=k; ++i) {
        for (int j=0; j<=k; ++j) {
            int n = s-i-j;
            if (0<=n && n<=k) ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include<iostream>
#include<iomanip>
#include<numeric>
#include<cstdio>
#include<cmath>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<ctype.h>
#include <fstream>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
using namespace std;
typedef long long ll;//int64
typedef unsigned long long ull;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int dy[4]={0,1,0,-1};
//----------program from here----------

int main(){
  char c='\0';
  cin >> c;
  cout << (c=='a'||c=='e'||c=='i'||c=='o'||c=='u'?"vowel":"consonant") << endl;

  return 0;
}

Measured memory_bytes: 256
array=5.times.map { gets.to_i }
sum=[]
array.each do |a|
  ans=0
  array.each do |b|
    ans+=b
    ans+=10-b%10 if b%10!=0
  end
  ans = ans-(10-a%10) if a%10!=0
  sum.push(ans)
end

p sum.min


Measured memory_bytes: 1788
/* ***********************************************
Author        :guanjun
Created Time  :2016/8/21 20:16:08
File Name     :at003b.cpp
************************************************ */
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <iomanip>
#include <list>
#include <deque>
#include <stack>
#define ull unsigned long long
#define ll long long
#define mod 90001
#define INF 0x3f3f3f3f
#define maxn 100010
#define cle(a) memset(a,0,sizeof(a))
const ull inf = 1LL << 61;
const double eps=1e-5;
using namespace std;
priority_queue<int,vector<int>,greater<int> >pq;
struct Node{
	int x,y;
};
struct cmp{
    bool operator()(Node a,Node b){
        if(a.x==b.x) return a.y> b.y;
        return a.x>b.x;
	}
};

bool cmp(int a,int b){
    return a>b;
}
int a[maxn];
int main()
{
    #ifndef ONLINE_JUDGE
    //freopen("in.txt","r",stdin);
    #endif
    //freopen("out.txt","w",stdout);
    int n;
	ll x;
	cin>>n;
	int mark=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	ll ans=0;
	for(int i=1;i<=n;i++){
		if(a[i]>0){
			ans+=a[i]/2;
			if(a[i+1]>0)a[i+1]+=(a[i]%2);
		}
	}
	cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] a = new int[n];
		
		for(int i = 0; i < n; i++ ) {
			a[i] = scan.nextInt();
		}
		int ans = 0;
		for(int i = 1; i < n+1; i++) {
			if(i % 2 == 1 && a[i-1] % 2 == 1) {
				ans++;
			}
		}
		System.out.print(ans);
	}

}


Measured memory_bytes: 35768
s = input()

sg = 0
sp = 0
ans = 0

for i in range(len(s)):
    if sp+1 <= sg and s[i] == 'g':
        sp += 1
        ans += 1
    elif sp+1 > sg and s[i] == 'p':
        sg += 1
        ans -= 1
    elif sp+1 <= sg and s[i] == 'p':
        sp += 1
    else:
        sg += 1
print(ans)


Measured memory_bytes: 3316
#include <iostream>
using namespace std;
int main() {
    int a,b,c,d;
    
    cin >> a;
        
    c = a / 3600 ;//秒を時間に
    b = a % 60 ;
    d = a / 60 % 60;
    
    cout << c << ":" <<  d << ":" << b << endl;
    
    return 0;
       
}

Measured memory_bytes: 1168
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#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 IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;

class UnionFind {
public:
    vector <int> par;
    vector <int> siz;

    UnionFind(int sz_): par(sz_), siz(sz_, 1LL) {
        for (int i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(int sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (int i = 0; i < sz_; ++i) par[i] = i;
    }

    int root(int x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }

    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

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

    int size(int x) {
        return siz[root(x)];
    }
};

signed main() {
  int N, M;
  cin >> N >> M;

  UnionFind uf(M);

  vector<vector<int>> vec(N);
  REP(i, N){
    int K;
    cin >> K;
    REP(j, K){
      int L;
      cin >> L; L--;
      vec[i].emplace_back(L);
    }
    REP(j, K){
      uf.unite(vec[i][0], vec[i][j]);
    }
  }

  bool ans = true;
  int p = uf.root(vec[0][0]);
  REP(i, N){
    if(p != uf.root(vec[i][0])) ans = false;
  }

  ans? YES: NO;

  return 0;
}

Measured memory_bytes: 7296
n = int(input())
a = [int(s) for s in input().split()]
b = []
val = 0
sum_val= 0
for i in range(0, n):
    b.append(a[i] * sum_val) 
    sum_val+= a[i] 
val = sum(b)
print(val % (10 ** 9 + 7))

Measured memory_bytes: 31660
import fractions
A,B,C,D=map(int,input().split())
L=C*D//fractions.gcd(C,D)

if A%C!=0 and A%D!=0:
    print((B-A+1)-((B-(A//C+1)*C)//C+1+(B-(A//D+1)*D)//D+1-(((B-(A//L+1)*L)//L)+1)))
elif A%C==0 and A%D!=0:
    print((B-A+1)-(((B-(A//C)*C)//C+1)+((B-(A//D+1)*D)//D+1)-((B-(A//L+1)*L)//L+1)))
elif A%C!=0 and A%D==0:
    print((B-A+1)-((B-(A//C+1)*C)//C+1+(B-(A//D)*D)//D+1-(B-(A//L+1)*L)//L-1))
elif A%C==0 and A%D==0 and A%L==0:
    print((B-A+1)-((B-(A//C)*C)//C+1+(B-(A//D)*D)//D+1-(B-(A//L)*L)//L-1))
elif A%C==0 and A%D==0 and A%L!=0:
    print((B-A+1)-((B-(A//C)*C)//C+1+(B-(A//D)*D)//D+1-(B-(A//L+1)*L)//L-1))

Measured memory_bytes: 64748
import numpy as np
n = int(input())
a = [int(input()) for _ in range(n)]
t1 = max(a)
t1_idx = [i for i, v in enumerate(a) if v == t1]
a.sort()

if len(t1_idx) < 2:
    try:
        t2 = a[-1*len(t1_idx)-1]
    except:
        for i in range(n):
            print(t1)

    for i in range(n):
        if i in t1_idx:
            print(t2)
        else:
            print(t1)
else:
    for i in range(n):
        print(t1)


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

int main(){
 string s,t;
 cin>>s>>t;
 int l=s.length();
 int sum=0;
 for(int i=0;i<l;i++){
   if(s[i]!=t[i]){
     sum++;
   }
 }
 cout<<sum<<endl;
}

Measured memory_bytes: 3900
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e5 +7;

#include <math.h>
#define PI 3.14159265358979323846264338327950L



int main() {
    int n;
    cin >> n;
    int mn = 30000000;
    int cnt = 0;

    while (n--) {
        int x;
        cin >> x;
        if (x <= mn) cnt++;
        mn = min(mn, x);
    }
    cout << cnt;
    return 0;
}

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

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

    int k, X;
    cin >> k >> X;

    string res;

    if(500 * k >= X){
        res = "Yes";
    }else{
        res = "No";
    }
    cout << res << endl;
}

Measured memory_bytes: 256
x,y,a,b,c= map(int, input().split())
p= list(map(int, input().split()))
q= list(map(int, input().split()))
r= list(map(int, input().split()))

p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)

ans=0
v=[]
for i in range(x):
    v.append(p[i])
for i in range(y):
    v.append(q[i])

v.sort()

w=0
for i in range(min(x+y,c)):
    if v[i]<r[w]:
        v[i]=r[w]
        w+=1

print(sum(v))

Measured memory_bytes: 109676
while True:
    n, m = [int(num) for num in input().split()]
    if n == m == 0:
        break
    items = sorted([int(num) for num in input().split()])
    answer = 0
    j = n - 1
    for i in range(n):
        while j > i and items[i] + items[j] > m:
            j -= 1
        if j <= i:
            break
        answer = max(answer, items[i] + items[j])
    print(answer if answer > 0 else "NONE")



Measured memory_bytes: 5640
N = gets.to_i
s = []
N.times{ s << gets.to_i }
s.sort!
 
sum = s.inject(:+)
 
if sum % 10 != 0
  
  puts sum
  
else
  
  t = []
  s.each{ |x| t << x if x % 10 != 0 }
  
  if t.empty?
    puts 0
  else
    puts sum - t[0]
  end
end

Measured memory_bytes: 1788
N,M,Q = map(int,input().split())
ABCD = [list(map(int,input().split())) for _ in range (Q)]
import sys
sys.setrecursionlimit(10**9)
Alist = []
def dfs(v):
    if len(v)==N:
        Alist.append(v)
        return 
    for t in range(v[-1],M+1):
        dfs(v+[t])
dfs([1])

ans = 0
for A in Alist:
    res = 0
    for a,b,c,d in ABCD:
        if A[b-1]-A[a-1]==c:
            res += d
    ans = max(ans,res)
print(ans)

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

using namespace std;

int main()
{
    string s;
    cin >> s;
    for(int i=0;i<s.size();i++){
        if(s[i] == 'B'){
            if(i == 0){
                s.erase(s.begin());
                i--;
            }else{
                s.erase(s.begin()+i-1,s.begin()+i+1);
                i -= 2;
            }
        }
    }
    cout << s << endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
	int A, B, M;
	scanf("%d %d %d", &A, &B, &M);
	int a[A], b[B], x[M], y[M], c[M];
	for (int i = 0; i < A; ++i) scanf("%d", &a[i]);
	for (int i = 0; i < B; ++i) scanf("%d", &b[i]);
	for (int i = 0; i < M; ++i) scanf("%d %d %d", &x[i], &y[i], &c[i]);
	int ans = 1000000;
	for (int i = 0; i < M; ++i) ans = min(ans, a[x[i] - 1] + b[y[i] - 1] - c[i]);
	sort(a, a + A);
	sort(b, b + B);
	ans = min(ans, a[0] + b[0]);
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 2176
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#define nmax_def 110000
#define Cmax_def 2200
#define mod 1000000007
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

int main() {
	int N, M;
	cin >> N >> M;
	vector<bool> A(N, true);
	rep(i, M) {
		int a;
		cin >> a;
		A[a-1] = false;
	}
	vl ans(N + 2, 0);
	ans[1] = 1;
	rep(i, N) {
		if (A[i])
			ans[i + 2] = (ans[i + 1] + ans[i]) % mod;
	}
	cout << ans[N + 1] << endl;
	return 0;
}

Measured memory_bytes: 1024
//#include <iostream>
//#include <vector>
//#include <algorithm>
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)

using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int INF = 100000000;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int main(){
  string S;
  cin >> S;
  int n=S.length();
  bool X = true;
  //cout << n << endl;
  rep(i,n){
    if(i%2==0){
      if(S[i]=='L'){
        X = false;
        //cout << i << endl;
      }
    }else{
      if(S[i]=='R'){
        X = false;
      }
    }
  }
    
  if(X) cout<< "Yes" << endl;
  else cout << "No" << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    string s,t;
    cin>>s>>t;
    for(int i=0;i<s.size();i++)
    if(t[i]!=s[i]){
    cout<<"No";
    return 0;
    }
    cout<<"Yes";
    return 0;
}

Measured memory_bytes: 3604
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Main main = new Main();
		main.run();
	}

	public void run() {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		int h=sc.nextInt();
		ArrayList<Integer> a = new ArrayList<>();
		ArrayList<Integer> b = new ArrayList<>();

		int maxa = 0;
		int maxi = 0;
		for(int i=0; i<n; i++) {
			a.add(sc.nextInt());
			b.add(sc.nextInt());
			if(maxa < a.get(i)) {
				maxa = a.get(i);
				maxi = i;
			}

		}

		Collections.sort(b, Collections.reverseOrder());
		long cnt = 0;

		for(int i=0; i<n; i++) {

			if(b.get(i)>maxa) {
				cnt++;
				h -= b.get(i);
				if(h<=0) {
					System.out.println(cnt);
					sc.close();
					return;
				}
			}
		}



		if(h>0) {
			cnt += (h + (maxa -1))/maxa;
		}

		System.out.println(cnt);
		sc.close();
	}
}


Measured memory_bytes: 63716
import java.util.*;

public class Main {


	public static void main(String[] args) {
		Main main = new Main();
		main.run();
	}
	int dist[][];
	int a[];
	int b[];
	int cost[];
	int n;
	int INF = 1000*1000+5;
	public void run() {
		Scanner sc = new Scanner(System.in);
		n=sc.nextInt();
		int m=sc.nextInt();
		dist = new int[n][n];
		a = new int[m];
		b = new int[m];
		cost = new int[m];
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				dist[i][j]=INF;
				if(i==j) {
					dist[i][j]=0;
				}
			}
		}
		for(int i=0; i<m; i++) {
			int s = sc.nextInt();
			int t = sc.nextInt();
			s--;
			t--;
			int c = sc.nextInt();
			dist[s][t]=c;
			dist[t][s]=c;
			a[i]=s;
			b[i]=t;
			cost[i]=c;
		}
		f();

		int ans = m;
		for(int k=0; k<m; k++) {
			boolean shortest=false;
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					if(dist[i][j] == dist[i][a[k]] + cost[k] + dist[b[k]][j]) {
						shortest=true;
					}
				}
			}
			if(shortest) {
				ans--;
			}
		}
		System.out.println(ans);
		sc.close();
	}

	private void f() {
		for(int k=0; k<n; k++) {
			for(int i=0; i<n; i++) {
				if(dist[i][k] == INF) continue;
				for(int j=0; j<n; j++) {
					if(dist[k][j] == INF) continue;
					dist[i][j] = Math.min(dist[i][j], dist[i][k]+dist[k][j]);
				}
			}
		}
	}
}


Measured memory_bytes: 40984
n = int(input())
a = [int(i) for i in input().split()]
d = []
cnt = 0
ans = 0
for i in range(n-1,0,-1):
	cnt+=a[i]
	d.append(cnt)
d = d[::-1]
for i in range(n-1):
	ans+=d[i]*a[i]
print(ans%(10**9+7))

Measured memory_bytes: 107872
#include <algorithm>
#include <cstdint>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using namespace std;

using lint=int64_t;
using uint=uint32_t;
using ulint=uint64_t;

template<class T>
using vector2d=vector<vector<T>>;

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

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

template <class T>
void OutVec(const vector<T>& vec){
  for(int i = 0; i < vec.size() - 1; ++i){
    cout<<vec[i]<<" ";
  }
  cout<<vec.back()<<endl;
}

template <class T>
void OutVec2d(const vector2d<T>& vec){
  for(auto v:vec){
    OutVec(v);
  }
}

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  string s;
  cin>>s;
  int q;
  cin>>q;
  bool flipped=false;
  string left,right;

  for(int i=0;i<q;i++){
    int t;
    cin>>t;
    if(t==1){
      flipped=!flipped;
    }else{
      int f;
      char c;
      cin>>f>>c;
      if(f==1){
        if(flipped){
          right+=c;
        }else{
          left+=c;
        }
      }else{
        if(flipped){
          left+=c;
        }else{
          right+=c;
        }
      }
    }
  }

  std::reverse(left.begin(),left.end());
  string result=left+s+right;
  if(flipped){
    reverse(result.begin(),result.end());
  }
  cout<<result<<endl;

  return 0;
}




Measured memory_bytes: 1300
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<time.h>
#include<vector>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;

ll po(ll a,ll b)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1)
        {
            ans = ans * a % mod;

        }
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}
int main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    ll n;
    cin>>n;


    ll ans = (po(10,n)-po(9,n)-po(9,n)+po(8,n))%mod;
    ans = (ans + mod)%mod;
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 3564
#include <iostream>
#include <unordered_set>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

int main(void) {
  int N;
  cin >> N;
  char last_char;
  unordered_set<string> history;
  bool ok = true;
  rep(i, N) {
    string S;
    cin >> S;
    if (history.count(S)) ok = false;
    if (i != 0 && last_char != S[0]) ok = false;
    history.emplace(S);
    last_char = S.back();
  }
  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> int_pair;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
int c[4][4];

bool tate12(){
	return (c[1][1]-c[2][1])==(c[1][2]-c[2][2])&&(c[1][1]-c[2][1])==(c[1][3]-c[2][3]);
}
bool tate23(){
	return (c[2][1]-c[3][1])==(c[2][2]-c[3][2])&&(c[2][1]-c[3][1])==(c[2][3]-c[3][3]);
}
bool tate13(){
	return (c[1][1]-c[3][1])==(c[1][2]-c[3][2])&&(c[1][1]-c[3][1])==(c[1][3]-c[3][3]);
}
bool yoko12(){
	return (c[1][1]-c[1][2])==(c[2][1]-c[2][2])&&(c[1][1]-c[1][2])==(c[3][1]-c[3][2]);
}
bool yoko23(){
	return (c[1][2]-c[1][3])==(c[2][2]-c[2][3])&&(c[1][2]-c[1][3])==(c[3][2]-c[3][3]);
}
bool yoko13(){
	return (c[3][1]-c[3][3])==(c[2][1]-c[2][3])&&(c[3][1]-c[3][3])==(c[1][1]-c[1][3]);
}




int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	FOR(i,1,4){
		FOR(j,1,4){
			cin>>c[i][j];
		}
	}
	if(tate12()&&tate13()&&tate23()&&yoko13()&&yoko23()&&yoko12()){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}

	
	return 0;
}

Measured memory_bytes: 256
from itertools import combinations
n, k = map(int, input().split())


MAX_PAIR = (n-1)*(n-2)//2
if MAX_PAIR < k:
    print(-1)
else:
    m = n-1+MAX_PAIR-k
    print(m)
    for v2 in range(2, n+1):
        print(1, v2)

    cnt = MAX_PAIR-k
    for v, v2 in combinations(range(2, n+1), 2):
        if cnt == 0:
            break
        cnt -= 1
        print(v, v2)

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

using namespace std;

#define int long long
#define endl '\n'
#define maxn 100010
const int MOD = 1000000007;

void solve() {
    int n;
    cin >> n;

    vector<int> v(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> v[i];
    }
    int ans = 0;
    map<int, int> mp;
    for (int i = 1; i <= n; i++) {
        ans += mp[-1 * (v[i] - i)];
        mp[v[i] + i]++;
    }
    cout << ans << endl;
}

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

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}

Measured memory_bytes: 27452
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
// using namespace __gnu_pbds;
using namespace std;
 
// template <typename T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;
typedef pair <long long,long long> ii;
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n;
    cin >> n;
    cout << (n)*(n-1)/2 << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int x = (int) (n / 1.08);
        if (n == x * 1.08) {
            System.out.println(x);
        } else {
            x++;
            System.out.println(n == (int) (x * 1.08) ? x : ":(");
        }
    }
}


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

long long dp[110][100010];//dp[i][j]はi番目までの品物を重さjまでに入れたときの最大値

int main()
{
 int N;
 int W;
 int v[110],w[110];
 cin >> N >> W;
 for(int i = 0; i < N; i++) cin >> w[i] >> v[i];
 
 //dp初期条件
 for(int j = 0; j <= W; j++) dp[0][j] = 0;

 for(int i = 0; i < N; i++){
  for(int j = 0; j <= W; j++){
   if(j >= w[i]) dp[i + 1][j] = max(dp[i][j - w[i]] + v[i],dp[i][j]);
   else dp[i + 1][j] = dp[i][j];
  }
 }
 
 cout << dp[N][W];
    
 return 0;
}


Measured memory_bytes: 80128
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1145141919810893364
//#define INF 810114514
//#define PI 3.141592653589
typedef pair<int,int> PP;
typedef long long ll;
#define int ll
#define setdouble setprecision
#define REP(i,n) for(int i=0;i<(n);++i)
#define OREP(i,n) for(int i=1;i<=(n);++i)
#define RREP(i,n) for(int i=(n)-1;i>=0;--i)
#define GOODBYE do { cout << "0" << endl; return 0; } while (false)
#define MM <<" "<<
#define Endl endl

signed main(void){
    int L;
    cin >> L;
    double Ans = 0.0;
    
    double l = (L+0.0)/3;
    Ans = l*l*l;
    printf("%.8f\n",Ans);
    
    return 0;
}



Measured memory_bytes: 256
import java.util.*;
 
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int A = sc.nextInt();
    int B = sc.nextInt();
    int C = sc.nextInt();
    int D = sc.nextInt();
    while(A>0){
      C -=B;
        if(C<=0){
          System.out.println("Yes");
          break;
        }
      A -= D;
        if(A<=0){
          System.out.println("No");
          break;
      }
    }
  }
}

Measured memory_bytes: 35776
t = int(input())

def calc(x):
    if x not in dp:
        divs = [5, 3, 2]
        costs = [c, b, a]
        values = lambda div, cost: [calc(x // div) + cost + x % div * d, calc((x + div - 1) // div) + cost + (-x) % div * d]
        dp[x] = min(x * d, *[value for div, cost in zip(divs, costs) for value in values(div, cost)])
    return dp[x]

for _ in range(t):
    n, a, b, c, d = map(int, input().split())
    dp = {0: 0, 1: d}
    print(calc(n))


Measured memory_bytes: 85780
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=210003;
const ll INF=1LL<<60;

ll dp[MAX][3];

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int N;cin>>N;
    vector<ll> A(13+N);
    for(int i=0;i<N;i++) cin>>A[11+i];
    
    if(N%2==0){
        for(int i=11;i<=10+N;i++){
            dp[i][0]=dp[i][1]=-INF;
        }
        
        for(int i=11;i<=10+N;i++){
            if(i%2){
                dp[i][0]=max(dp[i][0],dp[i-2][0]+A[i]);
            }else{
                dp[i][1]=max(dp[i][1],dp[i-3][0]+A[i]);
                dp[i][1]=max(dp[i][1],dp[i-2][1]+A[i]);
            }
        }
        
        cout<<max(dp[10+N-1][0],dp[10+N][1])<<endl;
    }else{
        for(int i=0;i<=10+N;i++){
            dp[i][0]=dp[i][1]=dp[i][2]=-INF;
        }
        dp[9][0]=0;
        
        for(int i=11;i<=10+N;i++){
            dp[i][0]=max(dp[i][0],dp[i-2][0]+A[i]);
            
            dp[i][1]=max(dp[i][1],dp[i-2][1]+A[i]);
            dp[i][1]=max(dp[i][1],dp[i-3][0]+A[i]);
            
            dp[i][2]=max(dp[i][2],dp[i-2][2]+A[i]);
            dp[i][2]=max(dp[i][2],dp[i-3][1]+A[i]);
            dp[i][2]=max(dp[i][2],dp[i-4][0]+A[i]);
        }
        
        cout<<max({dp[10+N-2][0],dp[10+N-1][1],dp[10+N][2]})<<endl;
    }
}


Measured memory_bytes: 9504
#include<bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef complex < double > P;
typedef pair < P, P >      L;
typedef pair < P, P >      Ls;
const double EPS = 1e-10;
const double INF = 1e8;
double cross( P a,  P b){ //OK
  return imag( conj(a) * b);
}
double dot( P a, P b){ //OK
  return real( conj(a) * b);
}
int ccw( P a, P b, P c){  //OK
  b -= a, c -= a;
  if(cross(b,c) > 0)    return +1;  // a → b で 反時計方向におれて c
  if(cross(b,c) < 0)    return -1; // a → b で 時計方向におれて c
  if(dot(b,c) < 0)      return +2;  // c -- a -- b
  if(norm(b) < norm(c)) return -2; // a -- b -- c
                        return 0;  // a -- c -- b
}
P projection( L l, P p) { //OK
  double t = dot( p - l.fr, l.fr - l.sc) / norm( l.fr - l.sc);
  return l.fr + t * ( l.fr - l.sc);
}
bool intersect( L a, P p){ //OK
   return abs( a.fr - p) + abs( a.sc - p) - abs( a.fr - a.sc) < EPS;
}
bool intersect( L a, L b){ //OK
  return ccw( a.fr, a.sc, b.fr) * ccw( a.fr, a.sc, b.sc) <= 0 &&
    ccw( b.fr, b.sc, a.fr) * ccw( b.fr, b.sc, a.sc) <= 0;
}
double distance( L s, P p){ //OK
  P r = projection(s, p);
  if ( intersect( s, r)) return abs( r - p);
  return min( abs( s.fr - p), abs( s.sc - p));
}
double distancion( L a, L b){ //OK
  if(intersect( a, b)) return 0;
  return min( min( distance( a, b.fr), distance( a, b.sc)),
              min( distance( b, a.fr), distance( b, a.sc)));
}
double Degree_to_Radian(double n){
  return n * M_PI / 180.0;
}
double Radian_to_Degree(double n){
  return n * 180.0 / M_PI;
}
/* ここまでテンプレート */
double info[100][100];
int n, m, l;
L stars[100][5];
int table[][5] = {{0,0,1,1,2},{2,3,3,4,4}};
P hosi[5];
void add( double x, double y, double a, double r, int z){
  for(int i = 0 ; i < 5 ; i++ ){
    double theta = Degree_to_Radian(a + 72 * i);
    double nx = r * sin( theta ), ny = r * cos( theta );
    hosi[i] = P( x - nx, y + ny);
  }
  for(int i = 0 ; i < 5 ; i++ ){
    stars[z][i] = L( hosi[table[0][i]], hosi[table[1][i]]);
  }
}
int main(){ //vectorが重いかも
  while(scanf("%d%d%d", &n, &m, &l), n|m|l){
    m--, l--;
    for(int i = 0 ; i < n ; i++ ){
      double x, y, a, r;
      scanf("%lf%lf%lf%lf", &x, &y, &a, &r);
      add( x, y, a, r, i);
    }
    for(int i = 0 ; i < n ; i++ ){
      for(int j = i + 1 ; j < n ; j++ ){
        double dist = INF;
        for(int a = 0 ; a < 5 ; a++ ){
          for(int b = 0 ; b < 5 ; b++ ){
            dist = min( dist, distancion( stars[i][a], stars[j][b]));
          }
        }
        info[i][j] = info[j][i] = dist;
      }
    }
    for(int k = 0; k < n; k++ ){
      for(int i = 0; i < n; i++ ){
        for(int j = 0; j < n; j++ ){
          info[i][j] = min( info[i][j], info[i][k] + info[k][j]);
        }
      }
    }
    printf("%.10f\n", info[m][l]);
  }
}

Measured memory_bytes: 1360
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#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 SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)

ll mod = 1e09;

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

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

  ll cnt = 1;
  for(ll i = 0; i < 1e08; i++){
    if(a * i % b == c){
      cout << "YES";
      return 0;
    }
  }
  cout << "NO";
}


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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int r;
    
    cin >> r;
    
    if(r  <  1200){
        cout<<"ABC"<<"\n";
    }
    else if(r >= 1200 && r < 2800){
        cout << "ARC"<< "\n";
    }
    else{
        cout<<"AGC" <<"\n";
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <climits>
#include <stack>
#include <queue>
#include <string>
#include <random>
#include <utility>
#include <cmath>
#include <set>
#include <map>
#include <string.h>
#include <iomanip>
#include <stdlib.h>
#include <algorithm>
#include <vector>
 
using namespace std;
typedef long long ll;
 
 
typedef pair<ll,ll> P;
long long int INF = 1e20;
double Pi = 3.141592653589;
const int mod = 1000000007;
// memset(a,0,sizeof(a)); →全部０にする
 
vector<int> G[100005];
 
int dx[8]={1,0,-1,0,1,1,-1,-1};
int dy[8]={0,1,0,-1,1,-1,-1,1};
 
std::vector<P> tree[100010];
struct edge{int to,cost;};
 
ll i,j,k;
ll x[53],y[53],xx[53],yy[53];
ll xs,xe,ys,ye;
ll n,ans=INF,kazu=0;

 
int main(){
	cin>>n>>k;
	for(i=0;i<n;i++){
		cin>>x[i]>>y[i];
		xx[i]=x[i];
		yy[i]=y[i];
	}
	sort(x,x+n);
	sort(y,y+n);
	for(xs=0;xs<n;xs++){
		for(xe=xs+1;xe<n;xe++){
			for(ys=0;ys<n;ys++){
				for(ye=ys+1;ye<n;ye++){
					for(i=0;i<n;i++){
						if(xx[i]>=x[xs] && xx[i] <= x[xe] && yy[i]>=y[ys] && yy[i] <= y[ye]){
							kazu++;
						}
					}
					if(kazu>=k){
						ans = min(ans,(x[xe]-x[xs])*(y[ye]-y[ys]));
					}
					kazu=0;
				}
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
int a[100005];
map<int,int>ma;
int main(){
	int n,sum=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ma[a[i]]++;
	} 
	for(int i=1;i<=n;i++)
	{
	if(ma[a[i]]>a[i])
	{
	sum+=ma[a[i]]-a[i];
	ma[a[i]]=a[i];
	}if(ma[a[i]]<a[i])
	sum+=ma[a[i]];
	ma[a[i]]=a[i];
	}
	cout<<sum;
}

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

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define MX              200005
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define pw(b,p)         pow(b,p) + 0.1

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    // cin>>t;
    // while(t--){
        
    //     cout<<'\n';
    // }
    int n,x,y;
    cin>>n>>x>>y;
    if(x>y)swap(x,y);
    if((x==1&&y==n)||(x==n&&y==1)){
        int a[n]={0};
        for(int i=1;i<n;i++){
            for(int j=i+1;j<=n;j++){
                int k=j-i,l=i+(n-j);
                int mn=min(k,l);
                a[mn]++;
            }
        }
        for(int i=1;i<n;i++)cout<<a[i]<<endl;
    }else{
        int a[n]={0};
        for(int i=1;i<n;i++){
            for(int j=i+1;j<=n;j++){
                int d=j-i;int t=abs(y-j)+1+abs(x-i);
                d=min(d,t);
                a[d]++;
            }
        }
        for(int i=1;i<n;i++)cout<<a[i]<<endl;
    }
    return 0;
}




Measured memory_bytes: 256
#include<iostream>
using namespace std;
#include<vector>
#include<set>
#include<algorithm>
#define int long long int
#define inf 10000000000000
int function2(int x,int val1,int val2)
{
	int here1=abs(x-val1)+abs(val1-val2);
	int here2=abs(x-val2)+abs(val1-val2);
	return min(here1,here2);
}
int32_t main()
{
	int a,b,q;
	cin>>a>>b>>q;
	set<int> st1,st2;
	int j;
	for(j=0;j<a;j++)
	{
		int x;
		cin>>x;
		st1.insert(x);
	}
	for(j=0;j<b;j++)
	{
		int x;
		cin>>x;
		st2.insert(x);
	}
	while(q--)
	{
		int x;
		cin>>x;
		int val1=inf,val2=inf,val3=inf,val4=inf;
		auto it=st1.lower_bound(x);
		if(it!=st1.end())
		{
			val1=*it;
		}
		if(*st1.begin()<x)
		{
			auto it2=st1.lower_bound(x);
			it2--;
			val2=*it2;
		}
		it=st2.lower_bound(x);
		if(it!=st2.end())
		{
			val3=*it;
		}
		if(*st2.begin()<x)
		{
			auto it2=st2.lower_bound(x);
			it2--;
			val4=*it2;
		}
		int here1=function2(x,val1,val3);
		int here2=function2(x,val1,val4);
		int here3=function2(x,val2,val3);
		int here4=function2(x,val2,val4);
		int answer=inf;
		int here=min(min(here1,here2),min(here3,here4));
		answer=min(answer,here);
		cout<<answer<<endl;
	}
}


Measured memory_bytes: 12992
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep2(i, m, n) for(int i=int(m); i<int(n); i++)
#define rep(i, n) rep2(i, 0, n)
#define ALL(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
const int INF = int(1e9)+10;
const ll INFll = ll(1e18)+10;
const ld EPS = 1e-10;
const int MOD = int(1e9)+7;

int main() {
	int L; cin >> L;
	
	int N = 0;
	int x = L;
	while (x > 0) {
		N++;
		x /= 2;
	}

	int M = 2*(N-1) + __builtin_popcount(L) - 1;
	cout << N << " " << M << endl;

	rep(i, N-1) {
		cout << (i+1) << " " << (i+2) << " " << 0 << endl;
		cout << (i+1) << " " << (i+2) << " " << (1<<(N-2-i)) << endl;
	}

	int w = 1<<(N-1);
	rep(i, N-1) {
		if (L % 2) {
			cout << 1 << " " << (N-i) << " " << w << endl;
			w += 1<<i;
		}
		L /= 2;
	}
	
	return 0;
}


Measured memory_bytes: 256
H, W = map(int,input().split())
maze = [list(input()) for i in range(H)]

def calc_distance(maze):
    global maxd
    global sx, sy
    global nextx, nexty
    INF = 100000000

    field_x_length = len(maze[0])
    field_y_length = len(maze)

    distance = []
    for i in range(field_y_length):
        distance.append([])
        for j in range(field_x_length):
            distance[i].append(INF)

    queue = []

    queue.insert(0, (sy, sx))

    distance[sy][sx] = 0

    while True:
        y, x = queue.pop()

        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]


            if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[ny][nx] != '#' and distance[ny][nx] == INF):
                queue.insert(0, (ny, nx))
                distance[ny][nx] = distance[y][x] + 1
                if maxd < distance[y][x] + 1:
                    maxd = distance[y][x] + 1
                    nexty = ny
                    nextx = nx
        if len(queue) == 0: break

maxd = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            sx, sy = j, i
        else: continue
        distance = calc_distance(maze)
print(maxd)


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

// 最大公約数を求める
// 計算量O(logn)
template<class T>
T gcd(T a, T b){
    if(b == 0) return a;
    return gcd(b, a%b);
}

// 最小公倍数を求める
// 計算量O(logn)
template<class T>
T lcm(T a, T b){
    return a/gcd(a,b)*b;
}

// 素数判定
// 計算量O(√n)
template<class T>
bool isPrime(T n){
    if(n < 2) return false;
    for(long long i = 2; i*i <= n; ++i) if(n % i == 0) return false;
    return true;
}

// 素数列挙
// nまでの素数をEratosthenesの篩で列挙する
// 計算量O(nloglogn)
template<class T>
vector<T> prime_list(T n){
    vector<T> ret;
    vector<T> isPrime(n+1,1);
    isPrime[0] = isPrime[1] = 0;
    for(long long i = 2; i <= n; ++i){
        if(isPrime[i] == 0) continue;
        ret.push_back(i);
        for(long long j = i*i; j <= n; j += i) isPrime[j] = 0;
    }
    return ret;
    // return isPrime;  // 状況によってはこっちを返す
}

// 素因数分解
// nを素因数分解してmapに記録
// 計算量O(√nlogn),必要ならmapではなくvectorにすると計算量を落とせる
template<class T>
map<T,int> prime_factor(T n){
    map<T,int> ret;
    if(n <= 0){
        cout << "Prime_factor Error" << "\n";
        return ret;
    }
    for(long long i = 2; i*i <= n; ++i){
        while(n%i== 0){
            ++ret[i];
            n /= i;
        }
    }
    if(n != 1) ret[n]++;
    return ret;
}


// 関数名：pow
// 概要：modつき指数関数
// 第一引数a：指数の底
// 第二引数b：指数
// 第三引数mod：法となる値
// 戻り値：a^b(m mod)
// 計算量O(log b)
template<class T>
T pow(T a, int b){
    if(b == 0) return 1;
    if(b%2){
        T ret = pow(a,(b-1)/2); 
        return ret*ret*a;
    }else{
        T ret = pow(a,b/2);
        return ret*ret;
    }
}

template<class T>
T pow(long long a, long long b, T mod){
    if(b == 0) return 1;
    if(b % 2 == 0){
        T d = pow(a,b/2,mod);
        return (d*d)%mod;
    }else return a%mod*pow(a,b-1,mod)%mod;
}

//関数名：comb
//概要：二項係数
//第一引数n：組み合わせの全体
//第二引数r：何個取り出すか
//第三引数mod：法となる値
//戻り値：nCr(m mod)
// 計算量O(r), 第三引数まで指定するとO(rlogmod)
template<class T>
T comb(T n, T r){
    if(r > n) return 0;
    if(n == r || r == 0) return 1;
    T ret = 1;
    for(T i = 1; i <= r; ++i){
        ret *= n--;
        ret /= i;
    }
    return ret;
}

template<class T>
T comb(long long n,long long r,T mod){
    if(r > n) return 0;
    if(n == r || r == 0) return 1;
    long long fact1 = 1,fact2 = 1;
    for(long long i = n; i >= n-r+1; --i) fact1 = fact1*i%mod;
    for(long long i = r; i >= 1; --i) fact2 = fact2*i%mod;
    return fact1*pow(fact2,mod-2,mod)%mod;
}

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

    int n; cin >> n;
    ll k = 5;
    vector<ll> ans;
    ans.push_back(2);
    rep(i,n-1){
        while(!isPrime(2*k+1)) k += 5;
        ans.push_back(2*k+1);
        k += 5;
    }
    rep(i,n){
        cout << ans[i];
        if(i != n-1) cout << " ";
    }
    cout << "\n";
}

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

int main() {
  int N;
  cin >> N;
  int n = N, m = 0;
  while (N > 0){
    m+= N % 10;
    N/=10;
  }
  cout << (n % m == 0 ? "Yes" : "No") <<endl;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  long long int h,n,a;
  cin>>h>>n;
  for(int i=0;i<n;i++){
    cin>>a;
    h -= a;
  }
  if(h>0) cout<<"No"<<endl;
  else cout<<"Yes"<<endl;
}
    

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    int p[N];
    for (int i = 0; i < N; i++) {
        cin >> p[i];
    }
    int ans = 0;
    for (int i = 0; i <= N; i++) {
        int t = 0;
        for (int j = 0; j < N; j++) {
            if (p[j] >= i)t++;
        }
        if (t >= i) ans = max(ans, i);
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 3112
n,m = map(int,input().split())
py = [list(map(int,input().split())) for i in range(m)]
for i in range(m):
  py[i] = tuple([py[i][0],py[i][1],i])

py.sort()
ans = {}
cnt = 1
for i in range(len(py)):
  if i == 0:
    cnt = 1
  elif py[i][0] == py[i-1][0]:
    cnt += 1
  else:
    cnt = 1
  l = str(py[i][0])
  temp = '0' * (6-len(l))+l
  sc = str(cnt)
  sc = '0' * (6-len(sc)) + sc
  ans[py[i][2]] =temp+sc
  
for i in range(m):
  print(ans[i])

Measured memory_bytes: 45148
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e18;
int mod = 1e9+7;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
signed main() {
    int N;
    string S;
    cin >> N >> S;
    int ans = 0;
    for(int i = 0; i <= 999; i++) {
        string T = to_string(i);
        int N = T.size();
        for(int j = 0; j < 3-N; j++) {
            T = '0'+T;
        }
        int now = 0;
        for(int i = 0; i < S.size(); i++) {
            if(S[i] == T[now]) {
                now++;
            }
            if(now == 3) {
                break;
            }
        }
        if(now == 3) {
            ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3724
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // TODO 自動生成されたメソッド・スタブ
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String S = sc.next();
        String[] s = new String[N];
        int initData = 0;
        for (int i = 0 ; i < N ; i++) {
                s[i] = String.valueOf(S.charAt(i));

        }

        for (int i = 1; i < N ; i++) {
            if (String.valueOf(S.charAt(i)).equals("E")) {
                initData++;
            }
        }
        int min = initData;
        int calc = initData;
        for (int i = 1; i < N ; i++) {

            if (s[i -1].equals("W")) {
                calc++;
            }
            if (s[i].equals("E")) {
                calc--;
            }

            min = Math.min(calc, min);

        }
        System.out.println(min);

    }
}


Measured memory_bytes: 53656
#include <bits/stdc++.h> 
using namespace std; 
  
unsigned long long power(unsigned long long x, 
                         int y, int p) 
{ 
    unsigned long long res = 1; 
  
    x = x % p; 
  
    while (y > 0) { 
        if (y & 1) 
            res = (res * x) % p; 
  
        y = y >> 1; 
        x = (x * x) % p; 
    } 
    return res; 
} 
  
unsigned long long modInverse(unsigned long long n, int p) 
{ 
    return power(n, p - 2, p); 
} 
 
unsigned long long nCrModPFermat(unsigned long long n, 
                                 int r, int p) 
{ 
    if (r == 0) 
        return 1; 
  
    unsigned long long fac[n + 1]; 
    fac[0] = 1; 
    for (int i = 1; i <= n; i++) 
        fac[i] = (fac[i - 1] * i) % p; 
  
    return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p; 
} 
  
int main() 
{   int s,sum=0,r;
   scanf("%d",&s);
    int n = s,  p = 1000000007; 
    for(r=1;r<=s/3;r++)
       sum=(sum+nCrModPFermat(n-2*r-1, r-1, p))%1000000007; 
       if(s<3)
       sum=0;
       printf("%d",sum);
    return 0; 
} 

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

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

const long long MOD = 1000000007;

int main(){
  int k,a;
  string s;
  cin >> k >> s;
  a=s.size();
  int n=min(k,a);
  rep(i,n) cout << s.at(i);
  if(k<a) cout << "...";
  cout<<endl;
}


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

void solve(std::string s) {
    string ans = "";
    rep(i, s.length()) {
        if (s[i] == '0') {
            ans.push_back('0');
        } else if (s[i] == '1') {
            ans.push_back('1');
        } else {
            if (ans.length() != 0) {
                ans.pop_back();
            }
        }
    }
    cout << ans << endl;
}

int main() {
    std::string s;
    std::cin >> s;
    solve(s);
    return 0;
}


Measured memory_bytes: 3620
#include"bits/stdc++.h"
using namespace std;

int main() {
	int n;
	cin >> n;
	long long x = 1000000000000000000, ans = 1;
	long long a[1000000];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (a[i] == 0) { 
			cout << "0";
			return 0; 
		}
	}
	for (int i = 0; i < n; i++) {
		if (x < a[i]) {
			cout << "-1";
			return 0; 
		}
		else {
			ans *= a[i];
			x /= a[i];
		}
	}
	cout << ans;
}

Measured memory_bytes: 4352
h, w = map(int, input().split())
S = [list(input()) for i in range(h)]

ans = 'Yes'
for i in range(1, h - 1):
    for j in range(1, w - 1):
        if S[i][j] == '#' and S[i - 1][j] == '.' and S[i + 1][j] == '.' and S[i][j -1] == '.' and S[i][j + 1] == '.':
            ans = 'No'
            
print(ans)

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int A[13]={0,1,3,1,2,1,2,1,1,2,1,2,1};

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>x>>y;
	if(A[x]==A[y]) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


Measured memory_bytes: 256
n, k = list(map(int, input().rstrip().split()))
d = list(map(int, input().rstrip().split()))
ans = n
while (True):
    x = ans
    flag = 1
    while x > 0:
        r = x % 10
        x = x // 10
        if r in d:
            ans += 1
            flag = 0
            break
    if flag == 1:
        break
print(ans)


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


int main(){
    long long n;
  	cin >> n;
    string s; 
  	cin >> s;
    long long count = 0;
    for(int i = 0; i < 1000; i++){
        char a, b, c; 
      	string t;
        if(i <10){
            a = '0';
            b = '0';
            t = to_string(i);
            c = t[0];
        }
        else if(i < 100){
            a = '0';
            t = to_string(i);
            b = t[0];
            c = t[1];
        }
        else{
            t = to_string(i);
            a = t[0];
            b = t[1];
            c = t[2];
        }
        long long y = 0;
        for(int j = 0; j < n; j++){
            if(y == 0){
                if(s[j] == a){ y++; }
            }
            else if(y == 1){
                if(s[j] == b){ y++; }
            }
            else if(y == 2){
                if(s[j] == c){ y++; }
            }
            else{ continue; }
        }
        if(y == 3){ count++; }
    }
    cout << count << endl;
}

Measured memory_bytes: 384
# coding: utf-8
# Your code here!
n=int(input())
s=list(map(int,input().split()))
s.sort()
ans=0
for i in range(n):
  for j in range(n):
    if s[i]<s[j]:
      for k in range(n):
        if s[j]<s[k] and s[i]+s[j]>s[k]:
          ans+=1
print(ans)



Measured memory_bytes: 70644