akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define inf 1010000000
#define infll 1010000000000000000ll
#define vi vector<int>
#define vll vector<ll>
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define mpr make_pair
#define fi first
#define se second
#define pq priority_queue<int>
#define pqll priority_queue<ll>
#define up(x,y) (x<(y)?x=(y):0)
#define dn(x,y) (x>(y)?x=(y):0)
#define ad(x,y) (x=(x+(y))%mod)
#define cbn(x,y) ((ll)fac[x]*inv[y]%mod*inv[(x)-(y)]%mod)
#define P 200003
#define N 600009
#define pi acos(-1.)
using namespace std;

int read(); ll readll();

int n,m,a[N],pos[N],id[N];
struct cpx{ double r,i; }b[N];
cpx operator +(cpx x,cpx y){ x.r+=y.r; x.i+=y.i; return x; }
cpx operator -(cpx x,cpx y){ x.r-=y.r; x.i-=y.i; return x; }
cpx operator *(cpx x,cpx y){
	cpx t; t.r=x.r*y.r-x.i*y.i; t.i=x.r*y.i+x.i*y.r; return t;
}
void dft(cpx *a,int flag){
	int i,j,k; cpx w,wn,u,v;
	for (i=0; i<m; i++) if (i<pos[i]) swap(a[i],a[pos[i]]);
	for (k=1; k<m; k<<=1){
		wn.r=cos(pi*flag/k); wn.i=sin(pi*flag/k);
		for (i=0; i<m; i+=(k<<1)){
			w.r=1; w.i=0;
			for (j=i; j<i+k; j++){
				u=a[j]; v=a[j+k]*w;
				a[j]=u+v; a[j+k]=u-v; w=w*wn;
			}
		}
	}
	if (flag<0) for (i=0; i<m; i++) a[i].r/=m;
}
int ksm(int x,int y){
	int z=1;
	for (; y; y>>=1,x=(ll)x*x%P) if (y&1) z=(ll)z*x%P;
	return z;
}
bool check(int x){
	int i;
	for (i=2; i*i<P; i++) if ((P-1)%i==0){
		if (ksm(x,i)==1) return 0;
		if (ksm(x,(P-1)/i)==1) return 0;
	}
	return 1;
}
int main(){
	scanf("%d",&n);
	int i,j;
	for (i=3; ; i++) if (check(i)) break;
	int g=i;
//	cerr<<g<<'\n';
	for (i=0,j=1; i<P-1; i++,j=(ll)j*g%P){
	//	assert(id[j]==0);
		id[j]=i;
	}
	id[0]=P-1;
	for (i=1; i<=n; i++) a[id[read()]]++;
	a[P-1]=0;
	m=1<<19;
//	cerr<<m<<'\n';
	for (i=0; i<m; i++) pos[i]=pos[i>>1]>>1|((i&1)?(m>>1):0);
//	for (i=0; i<m; i++) cerr<<a[i]<<' ';cerr<<'\n';
	for (i=0; i<m; i++) b[i].r=a[i];
	dft(b,1);
	for (i=0; i<m; i++) b[i]=b[i]*b[i];
	dft(b,-1);
//	for (i=0; i<m; i++) cerr<<b[i].r<<' '<<b[i].i<<"	"<<'\n';
	ll ans=0;
	for (i=0; i<m; i++)	if (b[i].r>1e-7){
	//	cerr<<"??"<<ksm(g,i)<<' '<<b[i].r<<'\n';
		ans+=ksm(g,i)*((ll)round(b[i].r));
	}
//	cerr<<"----"<<'\n';
	for (i=0; i<P-1; i++) if (a[i]){
		int x=ksm(g,i);
	//	cerr<<i<<' '<<x<<'\n';
		ans-=(ll)x*x%P*a[i];
	}
	//assert(ans%2==0);
	printf("%lld\n",ans/2);
	return 0;
}

int read(){
	int x=0; char ch=getchar(); bool flag=0;
	while (ch<'0' || ch>'9'){ if (ch=='-') flag=1; ch=getchar(); }
	while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
	return flag?-x:x;
}
ll readll(){
	ll x=0; char ch=getchar(); bool flag=0;
	while (ch<'0' || ch>'9'){ if (ch=='-') flag=1; ch=getchar(); }
	while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
	return flag?-x:x;
}


Measured memory_bytes: 15836
def sortByBubble(a, n)
  n.times do |i|
    (n-1).downto(i+1) do |j|
      a[j], a[j-1] = a[j-1], a[j] if a[j][1] < a[j-1][1]
    end
  end
  puts a.join(' ')
end

def sortBySelection(a, n)
  n.times do |i|
    minj = i
    i.upto(n-1) do |j|
      minj = j if a[j][1] < a[minj][1]
    end
    a[i], a[minj] = a[minj], a[i]
  end
  puts a.join(' ')
end

def checkStable(n, origin, sorted)
  originOrder = {1 => '', 2 => '', 3 => '', 4 => '', 5 => '', 6 => '', 7 => '', 8 => '', 9 => ''}
  sortedOrder = {1 => '', 2 => '', 3 => '', 4 => '', 5 => '', 6 => '', 7 => '', 8 => '', 9 => ''}
  n.times do |i|
    originOrder[origin[i][1].to_i] << origin[i][0]
    sortedOrder[sorted[i][1].to_i] << sorted[i][0]
  end
  puts originOrder == sortedOrder ? 'Stable' : 'Not stable'
end

n = gets.to_i
origin = gets.chomp.split(' ').map(&:to_s)
bubble = Marshal.load(Marshal.dump(origin))
selection = Marshal.load(Marshal.dump(origin))
sortByBubble(bubble, n)
checkStable(n, origin, bubble)
sortBySelection(selection, n)
checkStable(n, origin, selection)

Measured memory_bytes: 8844
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;


int main()
{
    ll H, W;
    ll h, w;
    cin >> H >> W;
    cin >> h >> w;
    cout << (H - h) * (W - w) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    unsigned long long i,n,count=1,X,j,temp;
    scanf("%llu",&n);
    unsigned long long x[n];
    for(i=0;i<n;i++)scanf("%llu",&x[i]);
    for(i=0;i<n-1;i++){
        for(j=0;j<n-1;j++){
            if(x[j]>x[j+1])
            {
                temp=x[j];
                x[j]=x[j+1];
                x[j+1]=temp;
            }
        }
    }
    X=x[0];
    for(i=0;i<n;i++){
        if(x[i]!=X){
                X=x[i];
                count++;
        }
    }
    printf("%llu\n",count);
    return 0;
}




Measured memory_bytes: 1728
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <stack>
#include <list>

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,b,n) for(int i=b;i<n;i++)
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

const float PI = 3.1415926;
static const int INFTY = (1<<30);

using namespace std;

typedef long long ll;
typedef long double ld;

ll res = 0;
int N,K;

int main() {
  cin >> N >> K;

  res = K;
  rep(i, N-1)
    res *= K-1;

  cout << res << endl;
  return 0;
}


Measured memory_bytes: 256
n=int(input())
k=int(input())
ans=float('inf')
for i in range(2**n):
  c=1
  tmp=format(i, '0'+str(n)+'b')
  for j in tmp:
    if j=='0':
      c*=2
    else:
      c+=k
      
  ans=min(c, ans)
  
print(ans)

Measured memory_bytes: 8968
#include <iostream>

int main(void){
    std::cout.tie(nullptr); std::cout.sync_with_stdio(false);
    int n, m; std::cin >> n >> m;
    int x = 1, y = n - 1;
    if(n & 1){ while(m--){ std::cout << x << ' ' << y << '\n'; ++x; --y; } }
    else{
       const int k = n >> 1;
       const int pos = (k & 1) ?  (k >> 1) + 1 : (k >> 1);
        while(m--){ if(x == pos) --y; std::cout << x << ' ' << y << '\n'; ++x; --y;}
    }
    return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define REP(i, n) for(int i = 0;i < (n);++i)
#define RREP(i, n) for(int i = (n)-1; i >= 0; --i)

#define ln '\n'
#define pb push_back
#define eb emplace_back
#define prique priority_queue
#define umap unordered_map
#define BIG 2000000000
#define VERYBIG 1000000000000000ll
#define PI 3.1415926
#define coutdb cout<<fixed<<setprecision(15)

const int dx[]={1,0,-1,0,1,1,-1,-1}, dy[]={0,-1,0,1,1,-1,1,-1};
const long long MOD = 1e9+7;

// typedef int_fast64_t ll;
#define int int_fast64_t
using Graph = vector<vector<int> >;
typedef pair<int, int> P;

template<typename T> inline T GCD(T a,T b){T c;while(b!=0){c=a%b;a=b;b=c;}return a;}
template<typename T> inline T LCM(T a,T b){T c=GCD(a,b);a/=c;return a*b;}
template<typename T> inline T nCr(T a,T b){T i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
template<typename T> inline T nHr(T a,T b){return nCr(a+b-1,b);}

int N, K, A[500];

bool notgreater(int num){
  // cerr << "***" << num << ln;
  vector<int> B(N), C(N);
  REP(i, N){
    B[i] = A[i] % num;
    C[i] = num-B[i];
  }
  sort(ALL(B)); sort(RALL(C));
  int idx = 0;
  /*
  for(int a : B)
    cerr << a << ln;
  cerr << ln;
  for(int a : C)
    cerr << a << ln;
  cerr << ln;*/
  REP(i, N){
    if(B[i]!=0) break;
    idx++;
  }
  B.erase(B.begin(), B.begin()+idx);
  C.erase(C.begin(), C.begin()+idx);
  vector<int> Bsum(N+1), Csum(N+1);
  int siz = B.size();
  REP(i, siz){
    Bsum[i+1] = Bsum[i]+B[i];
    Csum[siz-1-i] = Csum[siz-i]+C[siz-1-i];
  }
  REP(i, siz+1){
    if(Bsum[i] == Csum[i] and Bsum[i] <= K) return 1;
  }
  return 0;
}

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

  cin >> N >> K;
  int sum = 0, ans = 0;
  REP(i, N){
    cin >> A[i]; sum += A[i];
  }
  for(int num = 1; num*num <= sum; num++){
    if(sum % num != 0) continue;
    int d = num, e = sum/num;
    if(notgreater(d)) ans = max(ans, d);
    if(notgreater(e)) ans = max(ans, e);
  }
  cout << ans << ln;
}


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

int main() {
  int N;
  cin >> N;
  int a;
  a = N % 10;
  if(a == 2 || a == 4 || a == 5 || a == 7 || a == 9) cout << "hon" << endl;
  else if(a == 0 || a == 1 || a == 6 || a == 8) cout << "pon" << endl;
  else cout << "bon" << endl;
}


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


int main() {
    int n,a,b;
    cin >> n >> a >> b;
    cout << min(n*a,b) << endl;
    return 0;
}

/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

Measured memory_bytes: 256
#include<stdio.h>
#define MAX 100000

int main(){
  int i, n;
  int tree[MAX+1];

  scanf("%d", &n);
  for(i=1; i<=n; i++){
    scanf("%d", &tree[i]);
  }

  for(i=1; i<=n; i++){
    printf("node %d: key = %d, ", i, tree[i]);
    if(i/2 >= 1) printf("parent key = %d, ", tree[i/2]);
    if(i*2 <= n) printf("left key = %d, ", tree[i*2]);
    if(i*2+1 <= n) printf("right key = %d, ", tree[i*2+1]);
    printf("\n");
  }

  return 0;
}



Measured memory_bytes: 2052
#include <stdio.h>
#define MAX 500000
#define INFTY 1000000001

int L[MAX], R[MAX], count = 0;

void merge(int *A, int left, int mid, int right) {
  int i, j, k;
  int n1 = mid - left;
  int n2 = right - mid;
  //L[0...n1], R[0...n2] を生成
  for (i = 0; i < n1; i++)
    L[i] = A[left + i];
  for (i = 0; i < n2; i++)
    R[i] = A[mid + i];
  L[n1] = INFTY;
  R[n2] = INFTY;
  i = 0;
  j = 0;
  for (k = left; k < right; k++) {
    count++;
    if (L[i] <= R[j]) {
      A[k] = L[i];
      i++;
    } else {
      A[k] = R[j];
      j++;
    }
  }
}

void mergeSort(int *A, int left, int right) {
  if (left+1 < right) {
    int mid = (left + right)/2;
    mergeSort(A, left, mid);
    mergeSort(A, mid, right);
    merge(A, left, mid, right);
  }
}

void print_array(int *A, int N) {
  int i;
  for(i = 0; i < N - 1; i++) {
    printf("%d ", A[i]);
  }
  printf("%d\n", A[i]);
}


int main() {
  int A[MAX], n, i;
  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%d", &A[i]);
  }
  mergeSort(A, 0, n);
  print_array(A, n);
  printf("%d\n", count);
  return 0;
}



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

main()
{
  string n;
  int maxv[20];
  int sum = 0;
  
  for ( int i = 0; i < 19; i++) {
    maxv[i] = 9 * i;
  }
  
  cin >> n;

  for ( int i = 0; i < n.size(); i++) {
    sum += n[i] - '0';
  }
  
  if ( maxv[n.size() - 1] + (n[0] - '0' - 1) < sum) {
    cout << sum << endl;
  } else {
    cout << maxv[n.size() - 1] + (n[0] - '0' - 1) << endl;
  }

  return (0);
}

Measured memory_bytes: 256
N, M = map(int, input().split())
mi = 0
ma = 1000001
for i in range(M):
    right, left = map(int, input().split())
    if right > mi:
        mi = right
    if left < ma:
        ma = left
if mi > ma:
    print(0)
else:
    print(ma - mi + 1)

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


using namespace std;

#define fastio() ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
#define mk make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define sz(x) (int) (x).size()
#define print_vec(vec) for(int i=0;i<sz(vec);i++) cout << vec[i] << " ";
#define FORin(vec) for(int& x : vec) cin>>x;

void go(){
	int n,k;cin>>n>>k;
	int INF=1e9;
	vector<int> h(n); FORin(h);
	vector<int> dp(n,INF);
	dp[0]=0;
	for(int i=0;i<n;i++) {
		for(int j=i+1;j<=i+k;j++) {
			if(j<n) {
				dp[j]=min(dp[j],dp[i] + abs(h[i]-h[j]));
			}
		}
	}
	
	cout << dp[n-1];
			
}
int main(){
   
   fastio();
   cin.tie(0);
   cout.tie(0);

   go();

   return 0;
}




Measured memory_bytes: 3976
//============================================================================
// Name        : AOJ.cpp
// Author      :
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cctype>
using namespace std;

int main() {
	int N,k,p;
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>k>>p;
 	int j = 1;
	while (--k) {
		++j;
		if (j == p+1) j = 1;
	}
	cout<<j<<endl;
	}

	return 0;
}

Measured memory_bytes: 3076
import sys
input = sys.stdin.buffer.readline
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
def hypot(x1, y1, x2, y2):
  return ((x1-x2)**2 + (y1-y2)**2) ** 0.5
INF = 2**31 - 1
sx, sy, ex, ey = map(int, input().split())
n = int(input())
XYR = [list(map(int, input().split())) for _ in range(n)]
G = [[INF]*(n+2) for _ in range(n+2)]
for i in range(n-1):
  for j in range(i+1, n):
    x1, y1, r1 = XYR[i]
    x2, y2, r2 = XYR[j]
    d = hypot(x1, y1, x2, y2)
    k = max(d-r1-r2, 0)
    G[i][j] = k
for i, xyr in enumerate(XYR):
  x, y, r = xyr
  ds = hypot(sx, sy, x, y)
  de = hypot(ex, ey, x, y)
  ks = max(ds-r, 0)
  ke = max(de-r, 0)
  G[i][n] = ks
  G[i][n+1] = ke
G[n][n+1] = hypot(sx, sy, ex, ey)
C = csgraph_from_dense(G, null_value=INF)
D = dijkstra(C, indices=n, directed=False)
ans = D[n+1]
print(ans)

Measured memory_bytes: 58804
S = input()

M1_ = True if int(S[:2]) in range(1, 13, 1) else False
M2_ = True if int(S[2:]) in range(1, 13, 1) else False

if M1_:
  if M2_:
    print('AMBIGUOUS')
  else:
    print('MMYY')
elif not M1_:
  if M2_:
    print('YYMM')
  else:
    print('NA')

Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 
  string w;
  cin >> w;
  int index;
  
  for(int i=0;i<w.size();i++){
    index=0;
    for(int j=0;j<w.size();j++){
      if(w.at(j)==w.at(i)){
        index++;
      }
    }
    if(index%2==1){
      break;
    }
  }
  
  if(index%2==1){
    cout << "No" << endl;
  }else{
    cout << "Yes" << endl;
  }
  
}

Measured memory_bytes: 256
import string
n = int(input())
s = input()

st = string.ascii_uppercase

s1 = list(s)
s2 = list()
for i in range(len(s)):
    k = st.find(s1[i])
    if k>=26-n:
        k=k-26
    s2.append(st[k+n])
s2 = "".join(s2)
print(s2)

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

int main(){
  int N;
  cin >> N;
  vector<int> a(N);
  int sum = 0;
  rep(i,N){
    cin >> a.at(i);
    sum += a.at(i);
  }
  int cost = 1e9+7;
  for(int j=-100;j<=100;++j){
    int t = 0;
    rep(i,N){
      if(a.at(i)==j){
        continue;
      }else{
        t += pow((a.at(i)-j),2);
      }
    }
    cost = min(cost,t);
  }

  cout << cost << endl;
}


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

int main() { 
  int n,k;
  cin>>n>>k;
  vector <int> a(n);
 
  rep(i,n){
    cin>>a[i];
  }
  
  sort(a.begin(),a.end());
  int ans=0;
  rep(i,k){
    ans+=a[i];
  }
  
  cout<<ans<<endl;
}


Measured memory_bytes: 3596
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007; // 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
/*-------------------------------------------------*/
int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n; cin >> n;
  string s; cin >> s;
  int cnt = 0;
  REP(i, n) {
    if (s[i] == '#') ++cnt;
  }
  int ans = cnt;
  int cnt2 = 0;
  for (int i = n - 1; i >= 0; --i) {
    if (s[i] == '.') ++cnt2;
    else --cnt;
    ans = min(ans, cnt + cnt2);
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 720
#include<stdio.h>
int main(){
    int W,H,x,y,r;
    scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);
    if(x-r>=0&&x+r<=W&&y-r>=0&&y+r<=H){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
    return 0;
}


Measured memory_bytes: 2096
N=int(input())
e_list = [[] for i in range(N)]
for i in range(N-1):
    a,b=list(map(int,input().split()))
    a,b=a-1,b-1
    e_list[a].append(b)
    e_list[b].append(a)

vi = 0 #時と場合によってここを変える
from collections import deque
Q = deque([vi])
checked_list = [False for i in range(N)]
checked_list[vi]=True
prev_list = [-1 for i in range(N)]
min_path_list = [10**27 for i in range(N)] #問題によりここを変える
min_path_list[vi] = 0
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.appendleft(v1)
            prev_list[v1]=v
            min_path_list[v1]=min(min_path_list[v1],min_path_list[v]+1) #問題によりここを変える

path = [N-1]
v=N-1
while prev_list[v]!=-1:
    path.append(prev_list[v])
    v=prev_list[v]

a=path[(min_path_list[N-1]-1)//2]
b=path[(min_path_list[N-1]-1)//2+1]
for i in range(len(e_list[a])):
    if e_list[a][i]==b:
        break
del e_list[a][i]

for i in range(len(e_list[b])):
    if e_list[b][i]==a:
        break
del e_list[b][i]

vi = 0 #時と場合によってここを変える

Q = deque([vi])
checked_list = [False for i in range(N)]
checked_list[vi]=True
count = 1
while len(Q)>0:
    v = Q.pop()
    for v1 in e_list[v]:
        if not checked_list[v1]:
            checked_list[v1]=True
            Q.appendleft(v1)
            count+=1

if count>N-count:
    print("Fennec")
else:
    print("Snuke")

Measured memory_bytes: 70048
#define N 1000010
c[N];main(n){for(int i=2;i^N;i++)if(!c[i])for(int j=i<<1;j<N;j+=i)c[j]=1;for(int i=2;i^N;i++)c[i]=c[i-1]+(!c[i]);while(~scanf("%d",&n))printf("%d\n",c[n]);}


Measured memory_bytes: 5616
#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;
#define int long long int
#define mod 1000000007
#define string_mod 2549536629329_base_255
#define pb push_back
#define F first
#define S second
#define endl "\n"
#define all(v) v.begin(), v.end()
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
int power(int x, unsigned int y, int p)
{
    int res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res % p;
}
void solve()
{
    char c;
    cin >> c;
    if(c>='a'&&c<='z'){
        cout << 'a' << endl;
        return;
    }
    else{
        cout << 'A' << endl;
    }
   
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int tc;
    tc = 1;
    //cin >> tc;
    while (tc--)
    {
        solve();
    }

    return 0;
}


Measured memory_bytes: 3648
/*   _/                _/                 _/_/_/   _/
  _/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
   _/     _/    _/   _/     _/    _/  _/_/_/     _/
  _/     _/    _/   _/     _/    _/  _/    _/   _/
   _/_/   _/_/       _/_/   _/_/      _/_/     _/ */
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
using ll=long long;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=2e9;
const ll INF=1e18;
using P=pair<int,int>;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  string s,ss,tt,uu,t,u,sss;
  cin >> s;
  ss=s;
  int f=1;
  reverse(s.begin(),s.end());
  if(s!=ss) {
    f=0;
  }
  t=ss.substr(0,(ss.size()-1)/2);
  tt=t;
  reverse(t.begin(),t.end());
  if(t!=tt) {
    f=0;
  }
  u=ss.substr((s.size()+3)/2-1,s.size()-(s.size()+3)/2+1);
  uu=u;
  reverse(u.begin(),u.end());
  if(u!=uu) {
    f=0;
  }
  cout << (f?"Yes":"No") << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
  string str;
  
  
  while(1){
    getline(cin,str);
    if(cin.eof())break;
    while(1){
      if(str.find("this")!=-1|| str.find("that")!=-1|| str.find("the")!=-1){cout<< str <<endl;break;}
      for(int i=0;i<(int)str.size();i++){
	
	if(str[i]=='a')str[i]='z';
	
	else if('b'<=str[i]&&str[i]<='z')str[i]-=1;
      } 
    }
  }
}

Measured memory_bytes: 1176
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cstring>
#include<string>
using namespace std;
int f[105][5][2],k;
char str[105];
int Calc(int now,int sumz,int flag){
	if(!now){
		if(sumz==k)return 1;
		return 0;
	}
	if(sumz>k)return 0;
	if(~f[now][sumz][flag])return f[now][sumz][flag];
	f[now][sumz][flag]=0;
	int &s=f[now][sumz][flag];
	int h=(flag?str[now]-'0':9);
	for(int i=0;i<=h;i++){
		s+=Calc(now-1,sumz+(i?1:0),flag&&i==h);
	}
	return s;
}
int main(){
	memset(f,-1,sizeof(f));
	scanf("%s%d",str+1,&k);
	int l=strlen(str+1);
	reverse(str+1,str+l+1);
	printf("%d\n",Calc(l,0,1));
}

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

# 1 "<stdin>"
# 1 "<built-in>"
# 1 "<command-line>"
# 31 "<command-line>"
# 1 "/usr/include/stdc-predef.h" 1 3 4
# 32 "<command-line>" 2
# 1 "<stdin>"

using namespace std;

# 1 "../Algo/NumberTheory/modulo.h" 1
class ModuloOps {
public:
    ModuloOps(long long mod): MOD(mod) {
    }

    long long binPow(long long a, long long b) {
        if (b == 0) {
            return 1;
        }
        auto prev = binPow(a, b/2);
        return mul(mul(prev, prev), b % 2 == 1 ? a : 1);
    }

    long long inv(long long a) {
        return binPow(a, MOD - 2);
    }

    inline long long add(long long a, long long b) {
        return (a + b) % MOD;
    }

    inline long long sub(long long a, long long b) {
        return (a - b + MOD) % MOD;
    }

    inline void inc(long long &a, long long b) {
        a = add(a, b);
    }

    inline long long mul(long long a, long long b) {
        return (a * b) % MOD;
    }

    inline long long div(long long a, long long b) {
        return mul(a, inv(b));
    }

private:
    long long MOD;
};
# 5 "<stdin>" 2

using BS = bitset<51>;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n;
    cin >> n;
    map<pair<int, int>, int> mp;
    vector<vector<int>> g(n);
    for (int i = 0; i < n-1; i++) {
        int u, v;
        cin >> u >> v;
        v--; u--;
        mp[{u, v}] = i;
        mp[{v, u}] = i;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int m;
    cin >> m;
    vector<BS> bs(m);
    for (int i = 0; i < m; i++) {
        int u0, v0;
        cin >> u0 >> v0;
        u0--; v0--;
        vector<int> path;
        function<void(int, int)> dfs;
        dfs = [&] (int v, int p) {
            if (v == u0) {
                for (int j: path) {
                    bs[i][j] = 1;
                }
            }
            for (int u: g[v]) {
                if (u != p) {
                    path.push_back(mp[{u, v}]);
                    dfs(u, v);
                    path.pop_back();
                }
            }
        };
        dfs(v0, -1);
    }
    long long ans = 1ll << (n-1);
    for (int mask = 1; mask < (1<<m); mask++) {
        BS cur;
        int tot = 0;
        for (int i = 0; i < m; i++) {
            if (((1<<i) & mask) > 0) {
                tot++;
                cur |= bs[i];
            }
        }
        int sz = cur.count();
        ans += (tot%2 == 1 ? -1 : 1)*(1ll<<(n-1-sz));
    }
    cout << ans << endl;
}


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

int main() {
  int N;
  int K;

  cin >> N;
  cin >> K;

  int x = 1;
  for (int i = 0; i < N; i++) {
    if ((x * 2) < (x + K)) {
      x *= 2;
    } else {
      x += K;
    }
  }

  cout << x << endl;
}


Measured memory_bytes: 256
N = int(input())


restaurants = []
names = []

for i in range(N):
    S,P = (input().split())
    P = int(P)
    newinput = [S,P]
    restaurants.append([S,P])
    if S not in names:
        names.append(S)

names.sort()
sortedrestaurants = sorted(restaurants, key=lambda x: x[1], reverse = True)

ans = []
for i in range(len(names)):
    for j in range(N):
        if sortedrestaurants[j][0] == names[i]:
            ans.append(sortedrestaurants[j])

for i in range(N):
    print(restaurants.index(ans[i])+1)

Measured memory_bytes: 3064
#include <bits/stdc++.h> 
#define pb push_back
#define fr first
#define sc second
#define MOD 1000000007
#define len(x) x.size()
#define min3(a, b, c) min(a, min(b, c))
#define max3(a, b, c) max(a, max(b, c))
#define all(v) v.begin(), v.end()
#define f(i,a,n) for(int i=a;i<n;i++)
using namespace std;
typedef vector<int> vi;
typedef map<int,int> mii;
typedef pair<int,int> pii; 
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vll> vvll;
typedef vector<string> vs;

int main() {

    /*#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin) ;
    freopen("output.txt", "w", stdout) ;
    #endif*/
    ios_base::sync_with_stdio(false);
    cin.tie(NULL) ; cout.tie(NULL) ;

    //int t; cin>>t; while(t--) 
	int x; cin>>x;
	int ans=(x/500)*1000;
	x=x-(x/500)*500;
	ans+=(x/5)*5;
	cout<<ans;
	
    return 0 ;  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = (int) 1e6 + 10;
const int MOD = (int) 1e9 + 7;

int n, m, a[MAXN];
int num[MAXN];

bool check(int x) {
	int sum = 0;
	for (int i=1; i<=n; i++) {
		int now = a[i];
		for (int j=0; j<=100; j++) {
			if (now / (1 << j) <= x) {
				sum += j;
				break;
			}
		}
	}
	return sum <= m;
}

bool cmp(int a, int b) {
	return a > b;
}

#undef int
int main(){
	#define int long long
	scanf("%lld%lld", &n, &m);
	for (int i=1; i<=n; i++)
	    scanf("%lld", &a[i]);
	int l = 0, r = 1e10;
	int best;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (check(mid)) {
			r = mid - 1;
			best = mid;
		} else l = mid + 1;
	}
	int ans = 0;
	for (int i=1; i<=n; i++) {
		for (int j=0; j<=100; j++) {
			if (a[i] / (1 << j) <= best) {
				a[i] /= (1 << j);
				m -= j;
				num[i] = j;
				break;
			}
		}
	}
	sort(a+1, a+n+1, cmp);
	for (int i=1; i<=m; i++) {
		a[i] *= (1 << num[i]);
		a[i] /= (1 << (num[i] + 1));
	}
	for (int i=1; i<=n; i++)
	    ans += a[i];
	printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 5120
n = int(input())
cities = list(map(int,input().split()))
braves = list(map(int,input().split()))
braves.append(0)
count = 0
for i in range(n+1):
  c = min(braves[i],cities[i])
  count += c
  if i != n and c != braves[i]:
    d = min(braves[i]-c, cities[i+1])
    count += d
    cities[i+1] -= d
print(count)

Measured memory_bytes: 18624
#include <stdio.h>

int main(){
	int r, g, b;
	scanf("%d%d%d", &r, &g, &b);
	
	if((r*100 + g*10 + b) % 4 == 0){
		printf("YES\n");
	}else{
		printf("NO\n");
	}
	
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define DEBUG
#ifdef DEBUG
#define DEBUG_PRINT(fm, ...) do{std::printf("%s:%d(%s)", __FILE__, __LINE__, __func__);std::cout << "DEBUG PRINT ";std::printf(fm, __VA_ARGS__);}while(0)
#define DEBUG_VAL(a, b) do{std::printf("%s:%d(%s)", __FILE__, __LINE__, __func__);std::cout <<"DEBUG VAL " << a << ":" << b << endl;}while(0)
#else
#define DEBUG_PRINT(...)do{}while(0);
#define DEBUG_VAL(a, b)do{}while(0);
#endif

using namespace std;
using ll = long long;
using v1 = vector<int>;
using vl = vector<long long>;
using v2 = vector<vector<int>>;
using v3 = vector<vector<char>>;

int main(){
    int n, m;
    cin >> n >> m;
    v1 H(n);
    rep(i, n){
        cin >> H[i];
    }
    vector<set<int>> AB(n);
    rep(i, m){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        AB[a].insert(b);
        AB[b].insert(a);
    }
    int ans = 0;
    v2 height(n, v1(0));
    rep(i, n){
        auto itr = AB[i].begin();
        rep(j, AB[i].size()){
            if(j != 0) itr++;
            height[i].push_back(H[*itr]);
        }
        sort(height[i].begin(), height[i].end());
        int s = height[i].size();
        if(s == 0) ans++;
        else{
            if(height[i][s-1] < H[i]) ans++;
        }
    }
    
    cout << ans << endl;
}

Measured memory_bytes: 22800
#include "bits/stdc++.h"

using namespace std;

#define ll long long
#define vi  vector<int>
#define vvi vector<vi>
#define pi  pair<int,int>
#define mp  make_pair
#define pb  push_back
#define MOD 1e9 + 7
#define PAI  3.1415
#define all(x) (x).begin(),(x).end()
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
#define pr(x) cout << x << endl
#define Endl endl
#define rep(i,n) for(int i = 0 ; i < n; i++)

const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
const int ddx[8] = {-1,0,1,-1,1,-1,0,1};
const int ddy[8] = {-1,-1,-1,0,0,1,1,1};
const int inf = 99999999;
const ll linf = 1LL << 62;

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

ll lcm(ll a,ll b){
  if(a < b)swap(a , b);
  return (a/gcd(a , b))*b;
}

int main(){

  int x;
  cin >> x;

  vector<bool> v(1010 , false);

  v[1] = true;

  for(int i = 2 ;i<sqrt(x); i++){
    int n = i*i;
    v[n] = true;
    rep(j,10){
      n*=i;
      if(n <= x)v[n] = true;
      else break;
    }
  }

  for(int i = x ;i >= 0 ;i--){
    if(v[i] == true){
      cout << i <<Endl;
      return 0;
    }
  }



  return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,k;
  cin >> n >> k;
  double sum = 0;
  for(int i=1 ; i<=n ; i++){
    int nn = 0;
    while(i * pow(2,nn)<k){
      nn++;
    }
    sum += pow(1.0/2.0, nn);
  }
  printf("%.9f", sum/n);
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>

int main(){
  char a;
  char b;
  char c;
  char d;
  std::cin >> a;
  std::cin >> b;
  std::cin >> c;
  std::cin >> d;
  
  if(a==b&&b==c&&c==d&&a==d){
    std::cout<<"No"<<std::endl;
  }
  else if(a==b&&c==d){
    std::cout<<"Yes"<<std::endl;
  }
  else if(a==c&&b==d){
    std::cout<<"Yes"<<std::endl;
  }
  else if(a==d&&b==c){
    std::cout<<"Yes"<<std::endl;
  }
  else{
    std::cout<<"No"<<std::endl;
  }
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <array>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>
#include <stack>
#include <utility>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <climits>
#include <bitset>
#include <complex>
#include <random>
#include <functional>
#include <sstream>
#include <iomanip>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)
#define FOR(i, m, n) for(int i=(m);i<(n);i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define REVE(x) reverse((x).begin(),(x).end())
#define mp make_pair
#define pb push_back
#define dump(x)  cout << #x << " = " << (x) << endl;
#define forauto(i, a) for(auto i:a)cout << i << " "; puts("");

typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef complex<double> CD;

int main() {
	while (true) {
		int n; cin >> n;
		if (n == 0)break;
		int y; cin >> y;
		VI b(n), r(n), t(n);
		rep(i, n)cin >> b[i] >> r[i] >> t[i];

		int ansi;
		double ansm = 0;
		rep(i, n) {
			double mon;
			if (t[i] == 1)mon = 1 + y * r[i] / 100.;
			else mon = pow(1 + r[i] / 100., y);

			//cout << b[i] << ":" << mon << endl;
			
			if (ansm < mon) { ansm = mon; ansi = b[i]; }
		}
		cout << ansi << endl;
	}
}


Measured memory_bytes: 3340
from collections import Counter

count = Counter([])

N = int(input())

for i in range(2,N+1):
    n = i
    tmp = []
    d = 2
    while d <= n:
        while n%d == 0:
            n //= d
            tmp.append(d)
        d += 1
    count += Counter(tmp)

ans = 0
#74個以上の次数をもつ素因数を探す
for v in count.values():
    if v >= 74:
        ans += 1

#24,2個以上の次数の組み合わせ
more24 = 0
more2 = 0
for v in count.values():
    if v >= 2:
        more2 += 1
    if v >= 24:
        more24 += 1

ans += more24*(more2-more24)
ans += more24*(more24-1)

#14,4個以上の次数の組み合わせ
more14 = 0
more4 = 0
for v in count.values():
    if v >= 4:
        more4 += 1
    if v >= 14:
        more14 += 1
ans += more14 * (more4-more14)
ans += more14*(more14-1)

#4,4,2個以上の次数の組み合わせ
ans += more4*(more4-1)//2 * (more2-more4)
ans += more4*(more4-1)//2*(more4-2)

print(ans)

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

int main(){
	int a,b,c,f=0;
	cin >> a >> b >> c;
	if(a+b==c)f=1;
	if(a+c==b)f=1;
	if(b+c==a)f=1;
	if(f==1){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <stack>
#include <iomanip>
#include <functional>
#include <array>
#include <memory>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#undef NDEBUG
#include <assert.h>

using namespace std;
typedef long long ll;

int gcd(int a, int b) {
	return b ? gcd(b, a%b) : a;
}

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

	
	int n, X;
	cin >> n >> X;
	int g = 0;
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		g = gcd(g, x - X);
	}
	cout << abs(g) << endl;
	return 0;
	// return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

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

    vector<int> a(N), b(N), c(M), d(M);
    for(int i=0; i<N; ++i) cin >> a[i] >> b[i];
    for(int i=0; i<M; ++i) cin >> c[i] >> d[i];

    for(int i=0; i<N; ++i){
        int tmp = INT_MAX;
        int ans;
        for(int j=0; j<M; ++j){
            if(abs(a[i]-c[j])+abs(b[i]-d[j]) < tmp){
                ans = j+1;
                tmp = abs(a[i]-c[j]) + abs(b[i]-d[j]);
            }
        }
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL ans,cnt[28];
string str;
int main(){
	cin>>str;
	for (LL i=0;str[i];i++) ans+=i-cnt[str[i]-'a']++;
	printf("%lld",ans+1);
	return 0;
}

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

bool my_compare(pair<string, int> a, pair<string, int> b) {
    if(a.second != b.second){
        return a.second > b.second;
    }
    if(a.first != b.first){
        return a.first < b.first;
    }else{
        return true;
    }
}


int main(){
  int N;
  cin >> N;
  vector<string> S(N);
  vector<pair<string, int>> pairs;
  for(int i=0;i<N;++i) cin >> S[i];
  map<string,int> m{};
  for(int i=0;i<N;++i){
    m[S[i]]++;
  }
  for( auto i = m.begin(); i != m.end() ; ++i ) {
    pairs.push_back(make_pair( i->first , i->second ));
  }
  sort(pairs.begin(), pairs.end(), my_compare);
  int max=pairs[0].second;
  for(int i=0; i<pairs.size(); i++){
    if(pairs[i].second==max) cout << pairs[i].first << endl;
    else break;
  }
}

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

#define d(x) cerr << #x ":" << x << endl;
#define dd(x, y) cerr << "(" #x "," #y "):(" << x << "," << y << ")" << endl
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define repp(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define all(v) v.begin(), v.end()
#define dump(v)                  \
    cerr << #v ":[ ";            \
    for (auto macro_vi : v) {    \
        cerr << macro_vi << " "; \
    }                            \
    cerr << "]" << endl;
#define ddump(v)                           \
    cerr << #v ":" << endl;                \
    for (auto macro_row : v) {             \
        cerr << "[";                       \
        for (auto macro__vi : macro_row) { \
            cerr << macro__vi << " ";      \
        }                                  \
        cerr << "]" << endl;               \
    }
using lint       = long long;
const int INF    = 1e9;
const lint LINF  = 1e18;
const lint MOD   = 1e9 + 7;
const double EPS = 1e-10;

int main() {
    long double A, B;
    long double H, M;
    cin >> A >> B >> H >> M;

    long double radA = 2 * M_PI * (H + M / 60) / 12.0;
    long double radB = 2 * M_PI * (60 * H + M) / 60.0;
    long double ax = A * cos(radA), ay = A * sin(radA);
    long double bx = B * cos(radB), by = B * sin(radB);
    dd(ax, ay);
    dd(bx, by);
    long double l = pow(ax - bx, 2);
    long double r = pow(ay - by, 2);

    cout << setprecision(18) << (sqrt(l + r)) << endl;
    return 0;
}


Measured memory_bytes: 4156
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
//const ll mod = 1000000007;
ll dp[20005];

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll H, N;
    cin >> H >> N;
    for(int i = 0; i <= 2e4; i++) dp[i] = 1e18;
    dp[0] = 0;
    for(int i = 0; i < N; i++) {
        ll a, b;
        cin >> a >> b;
        for(int j = 0; j <= H; j++) {
            chmin(dp[j+a], dp[j] + b);
        }
    }
    ll ans = 1e18;
    for(int i = H; i <= 2e4; i++) chmin(ans, dp[i]);
    cout << ans;
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <functional>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <deque>
#include <list>
#include <sys/timeb.h>
#include <fstream>
#include <set>

using namespace std;

#define repr(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repr(i,0,n)
#define reprrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) reprrev(i,0,n)
#define repi(itr,ds) for(auto itr=ds.begin();itr!=ds.end();itr++)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define mp make_pair
#define mt make_tuple
#define INF 1050000000
#define INFL 1100000000000000000LL
#define EPS (1e-10)
#define MOD 1000000007
#define PI 3.1415926536
#define RMAX 4294967295

typedef long long ll;
typedef pair<int, int> Pi;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<Pi> vPi;
typedef vector<vector<int> > vvi;
typedef vector<vector<bool> > vvb;
typedef vector<vector<ll> > vvll;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<double> > vvd;
typedef vector<vector<Pi> > vvPi;
typedef priority_queue<int, vector<int>, greater<int> > pqli;
typedef priority_queue<ll, vector<ll>, greater<ll> > pqlll;
typedef priority_queue<Pi, vector<Pi>, greater<Pi> > pqlP;
struct Edge {
	int from, to, cost;
	bool operator<(Edge e) {
		return cost < e.cost;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
template <class T>
using vec = vector<T>;
template<class T>
using pql = priority_queue<T, vector<T>, greater<T>>;
string debug_show(Pi a) {
	return "(" + to_string(a.first) + "," + to_string(a.second) + ")";
}

template<class T>
struct augEdge {
	T from, to;
	int cost;
	bool operator<(augEdge e) { return cost < e.cost; }
	bool operator>(augEdge e) { return cost > e.cost; }
};
template<class T>
using augGraph = vector<augEdge<T>>;


bool pairCompare(const Pi& firstElof, const Pi& secondElof)
{
	return firstElof.second > secondElof.second;
}

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

	int n, m, c;
	cin >> n >> m >> c;
	vi b(m);
	rep(i, m)cin >> b[i];

	int ans = 0;
	rep(i, n) {
		int t = 0;
		rep(j, m) {
			int a;
			cin >> a;
			t += a*b[j];
		}
		if (t+c > 0) {
			ans++;
		}
	}

	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pqueue priority_queue
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

struct SegmentTree {
  vector<pair<int, int> > Tree[20];

  void init() {
    for(int i=0;i<20;++i) Tree[i].resize((1<<i));
  }

  void eval(int pos1, int pos2) {
    if(Tree[pos1][pos2].se==0) return;
    if(pos1+1<20) {
      Tree[pos1+1][2*pos2].se = max(Tree[pos1+1][2*pos2].se, Tree[pos1][pos2].se);
      Tree[pos1+1][2*pos2+1].se = max(Tree[pos1+1][2*pos2+1].se, Tree[pos1][pos2].se);
    }
    Tree[pos1][pos2].fi = max(Tree[pos1][pos2].fi, Tree[pos1][pos2].se);
    Tree[pos1][pos2].se = 0;
  }

  void update(int ql, int qr, int x, int pos1=0, int pos2=0, int sl=0, int sr=(1<<19)) {
    eval(pos1, pos2);
    if(qr<=sl || sr<=ql) return;
    if(ql<=sl && sr<=qr) {
      Tree[pos1][pos2].se = x;
      eval(pos1, pos2);
      return;
    }
    update(ql, qr, x, pos1+1, 2*pos2, sl, (sl+sr)/2);
    update(ql, qr, x, pos1+1, 2*pos2+1, (sl+sr)/2, sr);
    Tree[pos1][pos2].fi = max(Tree[pos1+1][2*pos2].fi, Tree[pos1+1][2*pos2+1].fi);
    return;
  }

  int getans(int ql, int qr, int pos1=0, int pos2=0, int sl=0, int sr=(1<<19)) {
    eval(pos1, pos2);
    if(qr<=sl || sr<=ql) return 0;
    if(ql<=sl && sr<=qr) return Tree[pos1][pos2].fi;
    return max(getans(ql, qr, pos1+1, 2*pos2, sl, (sl+sr)/2), getans(ql, qr, pos1+1, 2*pos2+1, (sl+sr)/2, sr));
  }
};

int main() {
  int N, K;
  cin>>N>>K;
  int tmp;
  int tmp1;
  SegmentTree tree;
  tree.init();
  for(int i=0;i<N;++i) {
    cin>>tmp;
    tmp1 = tree.getans(tmp, tmp+1)+1;
    tree.update(max(0, tmp-K), min(tmp+K+1, (1<<19)), tmp1);
  }
  cout<<tree.getans(0, (1<<19))<<endl;
}



Measured memory_bytes: 11424
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, n) for(int i=0; i<int(n); i++)
#define RNG(i, f, t) for(int i=int(f); i<=int(t); i++)
#define REV(i, f, t) for(int i=int(f); i>=int(t); --i)
#define ALL(v) (v).begin(), (v).end()
#define EXIT(answer) { cerr<<"EXIT #"<<__LINE__<<endl; cout<<answer<<endl; exit(0); }
#define sz(v) int(v.size())
bool RELAXED = false;
template<int,typename T> struct MINMAX{ T val; MINMAX(T val) : val(val) {} };
template<typename T> MINMAX<1,T> MAX(T val) { return MINMAX<1,T>(val); };
template<typename T> MINMAX<2,T> MIN(T val) { return MINMAX<2,T>(val); };
template<typename T, typename U> inline T& operator|=(T &lhs, MINMAX<1,U> rhs) { return lhs = (rhs.val > lhs ? (RELAXED=true,rhs.val) : (RELAXED=false,lhs)); }
template<typename T, typename U> inline T& operator|=(T &lhs, MINMAX<2,U> rhs) { return lhs = (rhs.val < lhs ? (RELAXED=true,rhs.val) : (RELAXED=false,lhs)); }
template<typename T, typename U> istream& operator>>(istream& in, pair<T,U> &p) { in>>p.first>>p.second; return in; }
template<typename T> inline vector<T> READ(int n) { vector<T> vec(n); FOR(i,n) cin>>vec[i]; return vec; }
template<typename T> using min_heap = priority_queue<T, vector<T>, greater<T> >;
typedef signed long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

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

    int K; cin>>K;
    ll sum=0;

    RNG(a,1,K)
    RNG(b,1,K) {
        int x = __gcd(a, b);
        RNG(c,1,K) {
            sum += __gcd(c, x);
        }
    }


    cout<<sum<<endl;

}

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

int main() {
  string s;
  int k;
  cin >> s >> k;
  vector<int> vec[26];
  rep(i, s.length()) vec[s[i]-'a'].push_back(i);

  int n = s.length();
  set<string> sets;
  rep(i, 26) {
    for (int l : vec[i]) {
      for (int r = l+1; r <= min(n, l+k); ++r) {
        sets.insert(s.substr(l, r-l));
      }
    }
    if (sets.size() >= k) break;
  }
  auto itr = sets.begin();
  rep(i, k-1) ++itr;
  cout << *itr << endl;
  return 0;
}

Measured memory_bytes: 384
#include <iostream>
using namespace std;
int main(){

  int n,s[100],result1=0,result2,i,j,blank;

  cin>>n;

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

  result2=result1;
  for(i = 0; i < n-1; i++){
    for(j = 0; j < n-1; j++){
      if(s[j] > s[j+1]){

	blank=s[j];
	s[j]=s[j+1];
	s[j+1]=blank;

      }
    }
  }

  for(i = 0; i < n && result1%10 == 0; i++) result1 -= s[i];
  for(i = 0; i < n; i++) if((result2-s[i])%10 != 0 && result1 < result2-s[i]) result1=result2-s[i];

  cout<<result1<<endl;

  return 0;

}


Measured memory_bytes: 256
#abc073 c
n=int(input())
a=dict()
for i in range(n):
    x=int(input())
    if x not in a:
        a[x]=1
    else:
        a[x]+=1
ans=0
for i in a.values():
    if i%2==1:
        ans+=1
print(ans) 

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

int d, g;
vector<int> ps;
vector<int> cs;
vector<int> ss;

int solve(int, int, int, int, vector<bool> &);

int main() {
    cin >> d >> g;

    for (int i = 0; i < d; i++) {
        int p, c;
        cin >> p >> c;
        ps.push_back(p);
        cs.push_back(c);
        ss.push_back(c + 100 * (i + 1) * p);
    }

    vector<bool> solved(d);
    cout << solve(0, 0, 0, 10000, solved) << endl;
}

int solve(int i, int score, int n, int ans, vector<bool> &solved) {
    if (i > d) return ans;
    if (score >= g) {
        ans = n;
        return ans;
    }

    if (i == d) {
        for (int j = d - 1; j >= 0; j--) {
            if (!solved.at(j)) {
                for (int k = 0; k < ps.at(j); k++) {
                    n++;
                    score += 100 * (j + 1);
                    if (score >= g) break;
                }
            }
            if (score >= g) {
                if (ans > n) ans = n;
                break;
            }
        }
    } else {
        solved.at(i) = false;
        int ans2 = solve(i + 1, score, n, ans, solved);

        solved.at(i) = true;
        int ans1 = solve(i + 1, score + ss.at(i), n + ps.at(i), ans, solved);

        solved.at(i) = false;
        return min(ans1, ans2);
    }
    return ans;
}


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

#define Vsort(a) sort(a.begin(), a.end())
#define Vreverse(a) reverse(a.bigin(), a.end())
#define rep(i,n) for(int i = 0; i < (n); i++)
#define Srep(i,a,n) for(int i = (a); i < (n); i++)
#define vi vector<int>
#define vi64 vector<int64_t>
#define vvi vector<vector<int>>
#define vvi64 vector<vector<int64_t>>

using namespace std;

int main(){
    string s;
    int zero = 0, one = 0;
    cin >> s;
    int n = s.size();
    vector<char> ZERO(n), ONE(n);
    rep(i,n) ZERO[i] = s.at(i);
    rep(i,n) ONE[i] = s.at(i);
    if(ZERO[0] == '1'){
        zero++;
        ZERO[0] = '0';
    }
    if(ONE[0] == '0'){
        one++;
        ONE[0] = '1';
    }
    Srep(i,1,n){
        if(ZERO[i-1] == ZERO[i]) {
            ZERO[i-1] == '0' ? ZERO[i] = '1' : ZERO[i] = '0';
            zero++;
        }
        if(ONE[i-1] == ONE[i]) {
            ONE[i-1] == '0' ? ONE[i] = '1' : ONE[i] = '0';
            one++;
        }
    }
    zero < one ? cout << zero << endl : cout << one << endl;
}


Measured memory_bytes: 3812