akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    for(;;){
        int n, t;
        cin >> n >> t;
        if(n == 0)
            return 0;

        vector<vector<int> > time(n);
        for(int i=0; i<n; ++i){
            for(;;){
                int a;
                cin >> a;
                if(a == 0)
                    break;
                time[i].push_back(a);
            }
        }

        int ret = 0;
        vector<int> pos(n, 0);
        vector<int> pass(n, 0);
        queue<int> line;
        while(--t >= 0){
            bool end = false;
            for(int i=0; i<n; ++i){
                if(pos[i] % 2 == 0){
                    ++ pass[i];
                    if(pass[i] == time[i][pos[i]]){
                        pass[i] = -1;
                        ++ pos[i];
                    }
                }else{
                    if(pass[i] == -1){
                        pass[i] = 0;
                        line.push(i);
                    }
                    if(line.front() == i)
                        ++ pass[i];
                    else
                        ++ ret;

                    if(pass[i] == time[i][pos[i]]){
                        end = true;
                        pass[i] = 0;
                        ++ pos[i];
                        if(pos[i] == (int)time[i].size())
                            pos[i] = 0;
                    }
                }
            }
            if(end)
                line.pop();
        }

        cout << ret << endl;
    }
}

Measured memory_bytes: 924
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int X = sc.nextInt();
		int D = 0;
		int ans = 1;
		for(int i=0; i<N; i++) {
			D += sc.nextInt();
			if(D<=X)
				ans++;
		}
		System.out.println(ans);
		sc.close();
	}
}


Measured memory_bytes: 23764
def func(i,ls):
    if i == 10:
        return len(ls) == n and sum(ls) == s
    return func(i + 1,ls) + func(i + 1,ls + [i])
 
while True:
    n,s = map(int,input().split())
    if n == 0:
        break
    print(func(0,[]))


Measured memory_bytes: 5592
n=int(input())
dic={}
cnt=1
s=[input() for i in range(n)]
for i in s:
    if i in dic:
        dic[i]+=1
        cnt=max(cnt,dic[i])
    else:
        dic[i]=1
ans=[]
for i in s:
    if dic[i]==cnt:
        ans.append(i)
ans=list(set(ans))
ans.sort()
for i in ans:
    print(i)

Measured memory_bytes: 45456
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 M =sc.nextInt();
    int a[] =new int[A];
    int b[] =new int[B];
    int m[] =new int[3*M];
    int x=100000;int y=100000;
    for(int i=0;i<A+B;i++){
      if(i<A){a[i]=sc.nextInt();
             x=Math.min(a[i],x);}
      else{b[i-A]=sc.nextInt();
          y=Math.min(y,b[i-A]);}}
    int z=x+y;
    for(int j=0;j<M;j++){
      m[3*j]=sc.nextInt();
      m[3*j+1]=sc.nextInt();
      m[3*j+2]=sc.nextInt();
      z=Math.min(a[m[3*j]-1]+b[m[3*j+1]-1]-m[3*j+2],z);}
    System.out.println(z);
  }
}

Measured memory_bytes: 136664
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long mod = 1000000007;
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextLong();
        
        long[] sum = new long[n+1];
        for (int i = 0; i < n; i++) {
            sum[n-1-i] += sum[n-i] + a[n-1-i];
            sum[n-1-i] %= mod;
        }
        
        long result = 0;
        for (int i = 0; i < n; i++) {
            result += a[i] * sum[i+1];
            result %= mod;
        }
        System.out.println(result);
    }
}


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

int main() {
  int N, x = 0;
  cin >> N;
  
  for(int i = 0;i < N;i++){
   int l, r;
   cin >> l >> r;
   x = x + r - l + 1;
  }
  cout << x << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		@SuppressWarnings("resource")
		Scanner sc = new Scanner(System.in);

		int H = sc.nextInt();
		int W = sc.nextInt();

		String a[] = new String[H];
		for (int i = 0; i < H; i++) {
			a[i] = sc.next();
		}

		String ans = "#";
		for (int n = 0; n < W + 1; n++) {
			ans = ans + "#";
		}

		String b [] = new String [H];
		for (int n = 0; n < H; n++) {
			b[n] =  "#" + a[n] + "#";
		}

		System.out.println(ans);

		for (int n = 0; n < b.length; n++) {

			System.out.println(b[n]);
		}
		
		System.out.println(ans);

	}
}


Measured memory_bytes: 23764
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define mkp make_pair
#define fi first
#define se second
#define pr(num) cout << num << "\n"
#define max(a, b) ((a)>(b) ? (a):(b))
#define min(a, b) ((a)<(b) ? (a):(b))
#define chmax(a, b) (a<b ? a=b : 0)
#define chmin(a, b) (a>b ? a=b : 0)
#define INF 1000000000000000000
#define MOD 1000000007LL
#define MAX 101010
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef map<ll, ll> Map;

ll mfa[MAX];
ll mrfa[MAX];

ll mPow(ll x, ll n) {
    ll res=1;
    while(n>0) {
        if(n&1) res=res*x%MOD;
        x=x*x%MOD;
        n>>=1;
    }
    return res;
}

ll fa(ll x) {
    if(x==0) return 1;
    if(mfa[x]!=-1) return mfa[x];
    return mfa[x]=x*fa(x-1)%MOD;
}

ll rfa(ll x) {
    if(x==0) return 1;
    if(mrfa[x]!=-1) return mrfa[x];
    rfa(x-1);
    return mrfa[x]=mPow(fa(x), MOD-2)%MOD;
}

ll C(ll n, ll k) {
    if(n<k) return 0;
    return fa(n)*rfa(k)%MOD*rfa(n-k)%MOD;
}

int main(void) {
    ll N;
    ll a[MAX]={};
    ll cnt[MAX]={};
    ll id=-1;
    ll l=-1, r=-1;
    
    cin >> N;
    ll i;
    
    for(i=1; i<=N+1; i++) {
        cin >> a[i];
        cnt[a[i]]++;
        if(cnt[a[i]]==2) id=a[i];
    }
    
    for(i=1; i<=N+1; i++) {
        if(a[i]==id) {
            if(l==-1) l=i;
            else r=i;
        }
    }
    
    memset(mfa, -1, sizeof(mfa));
    memset(mrfa, -1, sizeof(mrfa));
    
    fa(100010);
    rfa(100010);
    
    for(i=1; i<=N+1; i++) {
        pr((C(N+1, i)-C(N+l-r, i-1)+MOD)%MOD);
    }
    
}


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

int X[3];
int main() {
  cin >> X[0] >> X[1] >> X[2];
  sort(X, X+3);
  if (X[0] == 5 && X[1] == 5 && X[2] == 7) cout << "YES\n";
  else cout << "NO\n";
  return 0;
}


Measured memory_bytes: 256
#require 'prime'
MOD=10**9+7;  cnt=0; sum=0; prev=nil; can=true; h=Hash.new(0)
def gs() gets.chomp end
def gi() gets.chomp.to_i end
def gsmi() gets.chomp.split.map(&:to_i) end

def ar2(s1,s2,de=nil) Array.new(s1){Array.new(s2,de)} end
def ar3(s1,s2,s3,de=nil) Array.new(s1){Array.new(s2){Array.new(s3,de)}} end

def desc(ar) ar.sort!{|x,y| y<=>x} end
def min(a,b) a<=b ? a : b end
def max(a,b) a>=b ? a : b end
def sum(ar) ar.inject(:+) end
def ceil(a,b) (a.to_f/b).ceil end

def C(a,b) b==0||a==b ? 1 : (b=a-b if a/2<b;(a-b+1..a).inject(:*)/(1..b).inject(:*)) end
def rui(ar) s=[0]; ar.size.times{|i| s<<s[-1]+ar[i]}; s end
def rev_rui(ar) s=[0]; ar.size.times.reverse_each{|i| s<<s[-1]+ar[i]}; s end

def puts_yesno(b) puts(b ? 'Yes' : 'No') end
def putsend(s) puts s; exit end
def pu(h) begin; require './../nemi_lib/debug.rb'; puts_val(h); rescue LoadError; end; end
########### ( ˘ω˘ )ｽﾔｧ… ###########
n=gi
ar=%w(a b c d e f g h i j)
ar=ar[0,n]

ans=[""]
prev_i=-1
1.upto n do |i|
  if i==1
    ans=["a"]
    next
  end
  current=[]
  ans.each do |a|
    idx=ar.index(a.chars.max)
    can_i=min(i-1,idx+1)
    0.upto can_i do |b|
      current<<a+ar[b]
    end
  end
  ans=current
end

puts ans.sort

Measured memory_bytes: 17328
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() { 
  ios::sync_with_stdio(false); cin.tie(0);
  double a, b, h, m;
  cin >> a >> b >> h >> m;
  h = h * 30 + m / 2;
  m *= 6;
  double ang = min(abs(h - m), 360 - abs(h - m));
  cout << setprecision(20) << fixed << sqrt(a * a + b * b - 2 * a * b * cos(ang / 180 * M_PI)) << endl;
  return 0;
}

Measured memory_bytes: 4268
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace atcoder
{
	class Program
	{
		static int In => int.Parse(Console.ReadLine());
		static int[] Ins => Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
		static void Out(bool b) => Console.WriteLine(b ? "Yes" : "No");

		static void Main(string[] args)
		{
			var N = In;
			var a = Ins;
			int sum = 0;
			Array.Sort(a);
			Array.Reverse(a);
			for (int i = 0;i < N;i += 2)
			{
				sum += a[i];
				if (i + 1 < N) sum -= a[i+1];
			}
			Console.WriteLine(sum);
		}	
	}
}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const int N = 5e5 + 10;
const int mod = 1e9 + 7;

ll fac[N];

ll binpow(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void init() {
    fac[0] = 1;
    for (int i = 1; i < N; i++) 
        fac[i] = fac[i - 1] * i % mod;
}

ll inv(ll a) {
    return binpow(a, mod - 2);
}

ll A(ll n, ll m) {
    return fac[n] * inv(fac[n - m]) % mod;
}

ll C(ll n, ll m) {
    return fac[n] * inv(fac[m]) % mod * inv(fac[n - m]) % mod;
}

int main() {
    init();
    int n, m; cin >> n >> m;
    ll sum = 0;
    for (int i = 0; i <= n; i++) {
        sum += binpow(-1, i) * C(n, i) * A(m - i, n - i) % mod;
        sum = (sum + mod) % mod;
    }
    cout << A(m, n) * sum % mod << "\n";
}


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

using namespace std;

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

// chmax, chmin
template<class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}

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


long long sol(string S, long long K) {

    long long ans = 0;
    for (int i = 0; i + 1 < S.size() * K; i++) {
        if (S[i % S.size()] == S[(i + 1) % S.size()]) {
            ans++;
            i++;
        }
    }
    return ans;
}

long long rough(string S, long long K) {
    return sol(S, 1) + (sol(S, 2) - sol(S, 1)) * (K - 1);
}


void solve(std::string S, long long K) {
    if (K <= 2) {
        cout << sol(S, K) << endl;
        return;
    }
    if (rough(S, 3) == sol(S, 3)) {
        cout << rough(S, K) << endl;
    } else {
        cout << rough(S, K) - (K-1) / 2 << endl;
    }
}

int main() {
    std::string S;
    std::cin >> S;
    long long K;
    scanf("%lld", &K);
    solve(S, K);
    return 0;
}


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

int main() {
    int A, B, C, X, counter = 0, a = 0, temp1 = 0, b = 0, temp2 = 0, c = 0, ind =0;

    cin >> A >> B >> C >> X;

    // cannot make a payment

    if ((X%100 != 0 && C == 0) || ( X > 500*A+100*B+50*C))
    {
        cout << counter << endl;
    }
    // can make a payment
    else
    {
        a = min(A, X / 500);
        for (int i = 0; i <= a; ++i)
        {
            temp1 = X - 500 * i;
            b = min(B, temp1 / 100);
            for (int j = 0; j <= b; j++)
            {
                if ((temp1-100*j)/50 <= C)
                {
                    ++counter;
                }
            }
        }
        cout << counter << endl;
    }
}


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

int main(void){
	long long N,K;
	int *A,*check;
	int i,p,loop,flag;
	char str[10000000],buf[10000000];
 
	fgets(str, sizeof(str), stdin);
	N=strtoll(strtok(str ," "),buf,10);
	K=strtoll(strtok(NULL," "),buf,10);

	A=(int*)calloc(N,sizeof(int));
	check=(int*)calloc(N,sizeof(int));

	fgets(str, sizeof(str), stdin);
	A[0]=atoi(strtok(str," "));
	for(i=1;i<N;i++){
		A[i]=atoi(strtok(NULL," "));
	}
	
	p=1;
	check[p-1]=1;flag=0;
	for(i=0;i<K;i++){
		p=A[p-1];
		if( (check[p-1]!=0) && (flag==0)){
          	loop=i+2-check[p-1];
			K=(K-(i+1))%loop+(i+1);
			flag=1;
		}else{
			check[p-1]=i+2;
		}
	}

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

	free(A);
	free(check);

	return 0;
}

Measured memory_bytes: 4764
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sc(n) scanf("%d",&n)
#define scl(n) scanf("%lld",&n)
#define pr(n) printf("%d",n)
#define prl(n) printf("%lld",n)
#define nl printf("\n")
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
ll pow1(ll a, ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
		{
			ans=ans*a;
		}
		a=a*a;
		b=b>>1;
	}
	return ans;
}
int main()
{
	int n,m,i,j,k;
	cin>>n>>m;
	map<int,int> ma;
	string s;
	int corr = 0, ans = 0;
	for(i=0;i<m;i++)
	{
		cin>>j>>s;
		if(s == "AC")
		{
			if(ma[j] == 0)
			{
				corr++;
				ma[j] = -1;
			}
			else if(ma[j]>0)
			{
				corr++;
				ans += ma[j];
				ma[j]=-1;
			}
		}
		else
		{
			if(ma[j] == -1)
				continue;
			else
				ma[j]++;
		}
	}
	cout<<corr<<" "<<ans<<endl;
	return 0;
}

Measured memory_bytes: 4992
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
int n,m;
int was[512][512];
int s = 0;
void dfs(int x,int y)
{
    if (was[x][y] == 1)
        return ;
    ++s;
    was[x][y] = 1;
    dfs(n - x + 1,y);
    dfs(x,m - y + 1);
}
int cur[512];
int main(void)
{
    cin>>n>>m;
    vi cnt;
    for (int i = 1;i <= n;++i)
        for (int j = 1;j <= m;++j)
        {
            s = 0;
            dfs(i,j);
            if (s)
                cnt.pb(s);
        }
    sort(all(cnt),greater < int > ());
    for (int i = 1;i <= n;++i)
        for (int j = 1;j <= m;++j)
        {
            char ch;
            cin>>ch;
            ++cur[ch];
        }
    priority_queue < int > q;
    for (int i = 0;i <= 256;++i)
        if (cur[i])
            q.push(cur[i]);
    for (auto it : cnt)
    {
        int node = q.top();
        q.pop();
        if (node >= it)
            node -= it,q.push(node);
        else
            return puts("No") * 0;
    }
    puts("Yes");
    return 0;
}


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

struct Edge {
  int v, w;
};
typedef vector<vector<Edge> > Graph;

const int INF = 1<<28;
const int MAXN = 2020;

int N, M, K;
Graph G;
bool vis[MAXN];
int size;
int cost[MAXN];
int dp[MAXN][MAXN][2];
int C;
int Size[MAXN];
int V[MAXN][MAXN];
int dp2[MAXN][MAXN];

void dfs(int v, int src, int prev) {
  vis[v] = true;
  for(int i = 0; i < G[v].size(); ++i) {
    int nv = G[v][i].v;
    if(nv == prev) continue;
    cost[size++] = G[v][i].w;
    if(nv == src) continue;
    dfs(nv, src, v);
    break;
  }
}

void calc(int r, int v[]) {
  for(int s = 0; s < 2; ++s) {
    fill(dp[0][0], dp[size+1][0], -INF);
    dp[1][s][s] = 0;
    for(int i = 1; i < size; ++i) {
      for(int j = 0; j < size; ++j) {
        for(int k = 0; k < 2; ++k) {
          if(dp[i][j][k] == -INF) continue;
          dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][k]);
          int add = 0;
          if(k) {
            if(!cost[i-1]) continue;
            else add += cost[i-1];
          }
          if(r && i+1 == size && s) {
            if(!cost[i]) continue;
            else add += cost[i];
          }
          dp[i+1][j+1][1] = max(dp[i+1][j+1][1], dp[i][j][k] + add);
        }
      }
    }
    for(int j = 0; j <= size; ++j) {
      v[j] = max(v[j], max(dp[size][j][0], dp[size][j][1]));
    }
  }
}

int main() {
  while(cin >> N >> M >> K) {
    G = Graph(N);
    for(int i = 0; i < M; ++i) {
      int a, b, c;
      cin >> a >> b >> c;
      --a; --b;
      G[a].push_back((Edge){b, c});
      G[b].push_back((Edge){a, c});
    }
    memset(vis, 0, sizeof(vis));
    fill(V[0], V[MAXN], -INF);
    C = 0;
    for(int r = 0; r < 2; ++r) {
      for(int i = 0; i < N; ++i) {
        if(vis[i]) continue;
        if(!r && G[i].size() == 2) continue;
        size = 0;
        dfs(i, i, -1);
        size += !r;
        Size[C] = size;
        calc(r, V[C++]);
      }
    }
    fill(dp2[0], dp2[MAXN], -INF);
    dp2[0][0] = 0;
    for(int i = 0; i < C; ++i) {
      for(int j = 0; j <= K; ++j) {
        for(int k = 0; k <= Size[i] && j+k <= K; ++k) {
          if(dp2[i][j] == -INF) continue;
          dp2[i+1][j+k] = max(dp2[i+1][j+k], dp2[i][j] + V[i][k]);
        }
      }
    }
    if(dp2[C][K] == -INF) cout << "Impossible" << endl;
    else cout << dp2[C][K] << endl;
  }
  return 0;
}

Measured memory_bytes: 64808
#include<bits/stdc++.h>
using namespace std;
#define MIN -11111111
#define MAX 11111111
typedef pair<int,int> P;
int n;
P dat[8*100000-1];
void update(int k,int x);
void init(int n_);
int main(){
  int N,R,L;
  P tim[4*100012];
  cin>>N>>R>>L;
  
  init(N);
  for(int i=0;i<n;i++){
    dat[i+(n-1)]=P(0,i+1);
    tim[i]=P(0,-i-1);
  }
  dat[0] = P(MIN,1);
  int d,t,x,bt=0;
  for(int i=0;i<R;i++){
    cin>>d>>t>>x;
    tim[dat[0].second].first+=t-bt;
    update(d,x);
    bt=t;
  }
  tim[dat[0].second].first+=L-bt;
  sort(tim,tim+n,greater<P>());
  cout<<-tim[0].second-1<<endl;
}
void init(int n_){
  n=1;
  while(n<n_){
    n*=2;
  }
  for(int i=0;i<2*n-1;i++){
    dat[i]=P(MIN,MAX);
  }
}
void update(int k,int a){
  k+=n-2;
  dat[k]=P(dat[k].first+a,dat[k].second);
  while(k>0){
    k=(k-1) /2;
    if(dat[k*2+1].first==dat[k*2+2].first){
      if(dat[k*2+1].second < dat[k*2+2].second){
	dat[k]=dat[k*2+1];
      }else{
	dat[k]=dat[k*2+2];
      }
    }else{
      if(dat[k*2+1].first > dat[k*2+2].first){
	dat[k]=dat[k*2+1];
      }else{
	dat[k]=dat[k*2+2];
      }   
    }
  }
}

  

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

const int MAX_N = 1e5 + 1;

bool is_visited[MAX_N];
vector<int> graph[MAX_N];
vector<int> ans1, ans2;

void dfs(int node, vector<int>& ans) {
    is_visited[node] = true;
    for (int i = 0; i < graph[node].size(); i++) {
        if (is_visited[graph[node][i]]) continue;
        dfs(graph[node][i], ans);
        break;
    }
    ans.push_back(node + 1);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    int u, v;
    for (int i = 0; i < M; i++) {
        cin >> u >> v;
        u--, v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    dfs(0, ans1);
    dfs(0, ans2);
    reverse(ans2.begin(), ans2.end());
    int node_size = ans1.size() + ans2.size() - 1;
    cout << node_size << endl;
    for (int i = 0; i < ans1.size(); i++) cout << ans1[i] << ' ';
    for (int i = 1; i < ans2.size(); i++) cout << ans2[i] << ' ';
    cout << endl;
    return 0;
}

Measured memory_bytes: 11128
#!/usr/bin/env pytho3
import math
# x*1.08 <= s < x*1.08+1 になっている
# x <= 50000なのでs <= 54000
s = int(input())
for i in range(54001):
    if int(i*1.08) == s:
        print(i)
        exit()
print(":(")
"""
x = math.ceil(s*100/108)
if x >= (s+1)*100//108:
    print(":(")
else: print(x)"""

Measured memory_bytes: 38640
#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
#ifdef __LOCAL
#define debug(x) cerr << __LINE__ << ": " << #x << " = " << x << endl
#define debugArray(x, n)                             \
  cerr << __LINE__ << ": " << #x << " = {";          \
  for (long long hoge = 0; (hoge) < (n); ++(hoge)) { \
    cerr << ((hoge) ? "," : "") << x[hoge];          \
  }                                                  \
  cerr << "}" << endl
#else
#define debug(x) (void(0))
#define debugArray(x, n) (void(0))
#endif

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string N;
  cin >> N;
  int sum = 0;
  for (int i = 0; i < N.length(); i++) {
    (sum += N[i] - '0') %= 9;
  }
  cout << (sum ? "No" : "Yes") << endl;
  return 0;
}


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

typedef long long int ll;

int main()
{
    ll n, m;
    cin >> n >> m;
    vector<pair<ll,ll>> ab(n);
    for(ll i = 0;i < n;i++){
        cin >> ab[i].first >> ab[i].second;
    }
    sort(ab.begin(), ab.end());

    ll ans = 0;
    for(ll i = 0;i < n;i++){
        ans += ab[i].first * min(ab[i].second, m);
        m -= ab[i].second;
        if(m <= 0){
            break;
        }
    }

    cout << ans;

    return 0;
}

Measured memory_bytes: 1920
import collections
n=int(input())
l=[]
for _ in range(0, n):
  s=list(input())
  s.sort()
  l.append("".join(s))
cc=collections.Counter(l)
i=0
for k, v in cc.items():
  if v >= 2:
    i+=(v*(v-1))/2
print(int(i))

Measured memory_bytes: 68312
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
typedef long long lng;
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORD(i,b,a) for(int i=(b); i>=(a); --i)
#define REP(i,n) FOR(i,0,n-1)
#define ALL(a) (a).begin(), (a).end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end()) //NOTE: <a> must be sorted in advance

lng power(lng b, lng n) {lng sol=1; while(n>0) {if(n&1) {sol=sol*b;} n>>=1; b*= b;} return sol;} //calculate b^n

const int MOD = 1000000007; //10^9+7


/*********** variables ************/
int A, B;
/**********************************/

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> A >> B;
    if(A==B) cout << "Draw" << endl;
    else if(A==1||A>B&&B!=1) cout << "Alice" << endl;
    else cout << "Bob" << endl;
}


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

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

#define INF 1 << 30
#define REP(i,n) for(ll i=0; i<(int)(n); i++)
#define FOR(i,k,n) for(ll i=(k);i<(int)(n);i++)



vector<bool> gen_sosuu(vector<bool> sosuu){
  int size = sosuu.size();
  REP(i,size){
    sosuu[i] = true;
  }
  sosuu[0] = false;
  sosuu[1] = false;
  sosuu[2] = true;
  FOR(i,2,sqrt(size)+1){
    if(sosuu[i] == false) continue;
    for(int j = 2; i*j<size;j++){
      sosuu[i*j] =false;
    }
  }
  return sosuu;
}

int n;

int main(){
  cin >> n;
  if(n>=1000){
    cout << "ABD" <<endl;
  }else{
    cout <<"ABC"<<endl;
  }
}


Measured memory_bytes: 256
// AtCoderTemplate.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include<cstdio>
#include<iomanip>
#include<cmath>

using namespace std;

typedef long long ll;

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

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

	double p = 0;
	if (n % 2 == 0)
	{
		p = 0.5;
	}
	else
	{
		p = std::ceil((double)n/2) / n;
	}

	cout << setprecision(7) << p << endl;
}


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

int N, M;
vector<vector<int>> G;

int dfs(int d, int cur, int v) {
  if(v + 1 == 1 << N) return 1;
  int ret = 0;
  for(int nx : G[cur]) {
    int bit = 1 << nx;
    if(!(v & bit)) ret += dfs(d + 1, nx, bit | v);
  }
  return ret;
}
int main() {
  cin >> N >> M;
  G.resize(N);
  rep(i, 0, M) {
    int a, b; cin >> a >> b; a--, b--;
    G[a].push_back(b); G[b].push_back(a);
  }
  cout << dfs(0, 0, 1) << endl;
  return 0;
}


Measured memory_bytes: 256
open System
open System.Collections.Generic
open System.Linq
open System

// Following contents are my library. The Main processes are on the bottom of this code.

let puts = Console.WriteLine : 'a -> unit
let put = Console.Write : 'a -> unit
let read() = Console.ReadLine()
let reads () = Console.ReadLine().Split()
let read2 () = reads() |> (fun x -> x.[0], x.[1])
let read3 () = reads() |> (fun x -> x.[0], x.[1], x.[2])
let read4 () = reads() |> (fun x -> x.[0], x.[1], x.[2], x.[3])
let tmap2 f1 f2 (t1, t2) = (f1 t1, f2 t2)
let tmap3 f1 f2 f3 (t1, t2, t3) = (f1 t1, f2 t2, f3 t3)
let tmap4 f1 f2 f3 f4 (t1, t2, t3, t4) = (f1 t1, f2 t2, f3 t3, f4 t4)
let readAs f = read() |> f
let readAs2 f1 f2 = read2 () |> tmap2 f1 f2
let readAs3 f1 f2  f3 = read3 () |> tmap3 f1 f2 f3
let readAs4 f1 f2 f3 f4 = read4 () |> tmap4 f1 f2 f3 f4
let readInt () = readAs int64
let readInt2 () = readAs2 int64 int64
let readInt3 () = readAs3 int64 int64 int64
let readInt4 () = readAs4 int64 int64 int64 int64
let ensmallen l = l % 1000000007L
let manhattan x y = abs (fst x - fst y) + abs (snd x - snd y)
let sayYESNO b = if b then puts "YES" else puts "NO"
let sayYesNo b = if b then puts "Yes" else puts "No"

let toIntArray (s:string) = s.ToCharArray() |> Array.map (fun c -> int c - int '0')


// The main contents of this submission are below this line.

let (a, b, c) = readInt3()
(if (a + b + 1L)>= c then b + c else a + b + 1L + b )|> puts


Measured memory_bytes: 11220
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include<functional>
#include<numeric>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
#include<bitset>
#include<random>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define rep(i,n) FOR(i,0LL,n)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define rrep(i,n) RFOR(i,0LL,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define COUNT(a,y,x) upper_bound(all(a), y) - lower_bound(all(a), x)
#define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end())
#define pb push_back
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef map<ll, ll> MAP;
const ll inf = 2222222222222222222LL;
const ll mod = 1000000007LL;
//const ll mod = 998244353LL;

ll n = 0, m = 0, ans = 0, tmp = 0, ma = -inf, mi = inf;
string s;
bool ok;
ll dx[9] = { 0,1,0,-1,0,1,1,-1,-1 }, dy[9] = { 0,0,1,0,-1,1,-1,1,-1 };
#define endl '\n'
#pragma endregion
#define MAX 222222


ll a[MAX], h[MAX];

struct RMQ {
  vll data;
  ll siz;

  RMQ(ll x = MAX) {
    siz = 1;
    while (siz < x) siz *= 2;
    data.resize(2 * siz - 1, -inf);
  }

  //k番目をaに更新
  void update(ll k, ll a) {
    k += siz - 1;
    data[k] = a;
    while (k > 0) {
      k = (k - 1) / 2;
      data[k] = max(data[k * 2 + 1], data[k * 2 + 2]);
    }
  }

  //区間[a,b)の最大値
  ll query(ll a, ll b, ll k = 0, ll le = 0, ll ri = inf) {
    if (ri == inf) ri = siz;
    if (ri <= a || b <= le) return -inf;
    if (a <= le && ri <= b) return data[k];
    else {
      ll maxl = query(a, b, k * 2 + 1, le, (le + ri) / 2);
      ll maxr = query(a, b, k * 2 + 2, (le + ri) / 2, ri);
      return max(maxl, maxr);
    }
  }
};




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


  cin >> n;
  rep(i, n) cin >> h[i];
  rep(i, n) cin >> a[i];
  RMQ seg(MAX);
  seg.update(1, 0);
  rep(i, n) {
    ma = seg.query(1, h[i] + 1);
    seg.update(h[i], ma + a[i]);
  }
  cout << seg.query(1, n + 1) << endl;


  return 0;
}

Measured memory_bytes: 7552
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    // kagami mochi
    public static void main(String[] args) {
        // 入力処理
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());

        Integer[] mochies = new Integer[n];
        for (int i = 0; i < n; i++) {
            mochies[i] = Integer.valueOf(sc.nextLine());
        }

        Arrays.sort(mochies, Comparator.reverseOrder());

        int cnt = 1;
        for (int i = 0; i < mochies.length - 1; i++) {
            if (!mochies[i].equals(mochies[i + 1])) {
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}


Measured memory_bytes: 23124
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
  int A, B, M;
  cin >> A >> B >> M;
  int a[A], b[B], c[M];
  for (int i = 0; i < A; i++){
    cin >> a[i];
  }

  for (int i = 0; i < B; i++){
    cin >> b[i];
  }

  for (int i = 0; i < M; i++){
    int x, y;
    cin >> x >> y >> c[i];
    c[i] = a[x-1] + b[y-1] - c[i];
  }

  sort(a, a+A);
  sort(b, b+B);
  sort(c, c+M);

  if (a[0] + b[0] > c[0]){
    printf("%d\n", c[0]);
  }else{
    printf("%d\n", a[0] + b[0]);
  }
  
  
  
}


Measured memory_bytes: 4836
void main()
{
    long n, k;
    rdVals(n, k);
    long[] a = rdRow;

    long b = bsr(k << 1);
    long[] cnt = new long[b];
    foreach (x; a)
    {
        foreach (i; 0 .. b)
        {
            if ((x >> i) & 1) ++cnt[i];
        }
    }

    long x;
    foreach_reverse (i, c; cnt)
    {
        if ((x | (1L << i)) > k) continue;
        if (c <= (n >> 1)) x |= (1L << i);
    }

    long f;
    foreach (y; a)
    {
        f += x ^ y;
    }

    f.writeln;
}

enum long mod = 10^^9 + 7;
enum long inf = 1L << 60;

T rdElem(T = long)()
if (!is(T == struct))
{
    return readln.chomp.to!T;
}

alias rdStr = rdElem!string;
alias rdDchar = rdElem!(dchar[]);

T rdElem(T)()
if (is(T == struct))
{
    T result;
    string[] input = rdRow!string;
    assert(T.tupleof.length == input.length);
    foreach (i, ref x; result.tupleof)
    {
        x = input[i].to!(typeof(x));
    }
    return result;
}

T[] rdRow(T = long)()
{
    return readln.split.to!(T[]);
}

T[] rdCol(T = long)(long col)
{
    return iota(col).map!(x => rdElem!T).array;
}

T[][] rdMat(T = long)(long col)
{
    return iota(col).map!(x => rdRow!T).array;
}

void rdVals(T...)(ref T data)
{
    string[] input = rdRow!string;
    assert(data.length == input.length);
    foreach (i, ref x; data)
    {
        x = input[i].to!(typeof(x));
    }
}

void wrMat(T = long)(T[][] mat)
{
    foreach (row; mat)
    {
        foreach (j, compo; row)
        {
            compo.write;
            if (j == row.length - 1) writeln;
            else " ".write;
        }
    }
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.math;
import std.numeric;
import std.mathspecial;
import std.traits;
import std.container;
import std.functional;
import std.typecons;
import std.ascii;
import std.uni;
import core.bitop;

Measured memory_bytes: 4860
#ifdef LOCAL
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#else
#include <bits/stdc++.h>
#endif
using namespace std ;

typedef long long ll ;
#define rep(i , n ) for ( int i =0; i < n ; i++)
#define _sort(arg) sort(begin(arg), end(arg))
#define MOD 1000000007
#define pb push_back
#define DEBUG(x) cout << #x << ": " << x << endl;

/*
__attribute__((constructor))
void initial()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
}
*/

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

	int N;
	
	cin >> N;

	int a[2][N];
	int dp[2][N];

	rep(j, 2)
	{
		rep(i, N)
		{
			cin >> a[j][i];
			if (j > 0)
			{
				if (i > 0)
				{
					dp[j][i] = max(dp[j-1][i], dp[j][i-1]);
				}
				else
				{
					dp[j][i] = dp[j-1][i];
				}
				
			}
			else
			{
				if (i > 0)
				{
					dp[j][i] = dp[j][i-1];
				}
				else
				{
					dp[j][i] = 0;
				}
				
			}

			dp[j][i] += a[j][i];

		}
	}

	cout << dp[1][N-1] << endl;
	

	
	return 0;
}


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

int main()
{
  int n, m;
  cin >> n >> m;
  long a;
  int b;
  vector< pair<long, int> > store(n);
  for (int i = 0; i < n; i++)
  {
    cin >> a >> b;
    store[i] = make_pair(a, b);
  }
  sort(store.begin(), store.end());

  long ans = 0;
  int cnt = 0;
  for (int i = 0; i < n; i++)
  {
    if (cnt + store[i].second < m)
    {
      ans += store[i].first * store[i].second;
      cnt += store[i].second;
    }
    else
    {
      ans += store[i].first * (m - cnt);
      break;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
int main() {
    string s,t;
    cin >> s >> t;
    for(int i = 0;i < s.size();i++) {
        rotate(s.begin(),s.begin() + 1,s.end());
        if(s == t) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>=b;i--)
#define pb(z) push_back(z)
#define ff first
#define ss second
#define pi(a,b) make_pair(a,b)
#define pii pair<ll,ll>
#define T int t;cin>>t;for(int tt=1;tt<=t;tt++)
#define debug(vec) cout<<(#vec)<<" : [ "; for (auto& i: vec) cout<<i<<" "; cout<< "]" << endl
#define input(v,n) vector<int>v;for(int i=0;i<n;i++){int x;cin>>x;v.push_back(x);}
#define debugg(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;


const int inf    = 0x3f3f3f3f;
const ll LL_INF  = 0x3f3f3f3f3f3f3f3f;
const double PI  = acos(-1);
const double eps = 1e-4;
const int mod    = 1e9+7;
const int mx     = 2e5+5;
//vector<int>v;
//for(int i=0; i<n; i++)
//{
//    int x;
//    cin>>x;
//    v.push_back(x);
//}


int main()
{
    IOS
    double w,h,x,y;
    cin>>w>>h>>x>>y;
    double ans=w*h;
    ans/=2.0;
    int tmp=0;
    if(x*2==w && y*2==h)
        tmp=1;
    cout<<setprecision(10)<<fixed;
    cout<<ans<<" "<<tmp<<endl;


}



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

ll mod(ll a)
{
	if(a>0)
		return a;
	return -a;
}

int main()
{
	int n;
	cin>>n;
	ll a[n];
	for(int i=0;i<n;i++)
		cin>>a[i];
	ll dp[n];
	dp[0]=0;
	dp[1]=mod(a[1]-a[0]);
	for(int i=2;i<n;i++)
	{
		dp[i]=min(dp[i-1]+mod(a[i]-a[i-1]),dp[i-2]+mod(a[i]-a[i-2]));
	}
	cout<<dp[n-1]<<endl;
}

Measured memory_bytes: 1792
n = int(input())
a = list(map(int,input().split()))
dic = {}
for i in range(n):
  if a[i] in dic.keys():
    dic[a[i]] += 1
  else:
    dic[a[i]] = 1
total = 0
loss = [0]*(n+1)
for k in dic.keys():
  res = dic[k]*(dic[k]-1)//2
  total += res
  loss[k] = res-(dic[k]-1)*(dic[k]-2)//2
for i in range(n):
  print(total-loss[a[i]])

Measured memory_bytes: 26140
#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 FORR(i, m, n) for (int i = m; i >= n; i--)
#define INF 1e9;
using namespace std;
typedef long long ll;
int main() {
  ll N;
  cin >> N;
  ll A[N];
  REP(i, N) cin >> A[i];

  ll rate[] = {1, 400, 800, 1200, 1600, 2000, 2400, 2800, 3200};

  ll cnt = 0;
  set<ll> color;
  REP(i, N) {
    if (A[i] >= 3200) {
      cnt++;
      continue;
    }

    REP(j, 8) {
      if (rate[j] <= A[i] && A[i] < rate[j + 1]) color.insert(j);
    }
  }

  ll max_c = color.size() + cnt;
  ll min_c = max((ll)(color.size()), 1LL);

  cout << min_c << " " << max_c;

  return 0;
}

Measured memory_bytes: 256
int main(void){
 int x = 0;
 int y = 0;
 int z = 0;
    
 while(1){
  scanf("%d %d",&x,&y);
  if(x==0 && y==0){
   break;
  }
  if(y<x){
   z = x;
   x = y;
   y = z;
  }
  printf("%d %d\n",x,y);
 }
 return 0;
}

Measured memory_bytes: 600
using System;
using System.Linq;

class ALDS1
{
    static void Main()
    {
        int a = int.Parse(Console.ReadLine());
        int[] x = new int[a];
        for (int i = 0; i < a; i++)
        {
            x[i] = int.Parse(Console.ReadLine());
        }
        int m = 1, cnt = 0;
        int[] G = new int[14]; G[0] = 1;
        for (int i = 1; ; i++)
        {
            G[i] = G[i - 1] * 3 + 1;
            if (G[i] > a) break;
            m++;
        }
        Console.WriteLine(m);
        for (int i = m - 1; i >= 0; i--)
        {
            if (i == 0) Console.WriteLine(G[i]);
            else Console.Write(G[i] + " ");
        }
        for (int i = m; i >= 0; i--)
        {
            cnt += insSort(x, a, G[i]);
        }
        Console.WriteLine(cnt);
        for (int i = 0; i < a; i++)
        {
            Console.WriteLine(x[i]);
        }
    }
    static int insSort(int[] A, int n, int g)
    {
        int cnt = 0;
        for (int i = g; i < n; i++)
        {
            int v = A[i];
            int j = i - g;
            while (j >= 0 && A[j] > v)
            {
                A[j + g] = A[j];
                j = j - g;
                cnt++;
            }
            A[j + g] = v;
        }
        return cnt;
    }
}

Measured memory_bytes: 19888
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
	int k;
	cin >> k;
	if (k%2==0) {
		cout << (k/2)*(k/2) << "\n";
		return 0;
	}
	cout << ((k-1)/2)*((k+1)/2) << "\n";
	return 0;
}

Measured memory_bytes: 256
def bubbleSort(A, N):
    flag = 1
    count = 0
    while flag:
        flag = 0
        for j in xrange(N-1,0,-1):
            if A[j] < A[j-1]:
                tmp = A[j]
                A[j] = A[j-1]
                A[j-1] = tmp
                flag += 1
                count += 1
    return A, count

def newbubbleSort(A, N):
    flag = 1
    count = 0
    i = 0
    while flag:
        flag = 0
        for j in xrange(N-1,i,-1):
            if A[j] < A[j-1]:
                tmp = A[j]
                A[j] = A[j-1]
                A[j-1] = tmp
                flag += 1
                count += 1
        i += 1
    return A, count


def main():
    N = int(raw_input())
    A = map(int, raw_input().split())
    new_A, count = newbubbleSort(A, N)
    print ' '.join(map(str,new_A))
    print count

if __name__ == "__main__":
    main()

Measured memory_bytes: 6480
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define vec vector
#define vi vec<int>
#define vvi vec<vec<int>>
#define ALL(a) begin(a), end(a)
#define RALL(a) rbegin(a), rend(a)
#define SORT(a) stable_sort(ALL(a))
#define RSORT(a) stable_sort(RALL(a))
#define REV(a) reverse(ALL(a))
#define UNIQUE(a) a.erase(unique(ALL(a)), end(a))
#define lambda(i) [](auto& i)
#define compare(i, j) [](auto& i, auto& j)
#define min_of(a) *min_element(ALL(a))
#define max_of(a) *max_element(ALL(a))
#define sum(a) accumulate(ALL(a), 0)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define SZ(a) (int)(a).size()
#define REP(i, n) for (decltype(+n) i = 0; i < (n); i++)
#define RREP(i, n) for (auto i = n - 1; i != static_cast<decltype(i)>(-1); i--)
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define RFOR(i, a, b) for (auto i = b - 1; i != a; i--)
#define EACH(i, a) for (auto&& i: (a))
using namespace std;

const int INF = 1e18;
const int MOD = 1e9 + 7;

int ceil_div(int X, int Y) {
  return (X - 1) / Y + 1;
}

struct union_find {
  vi data;
  union_find(int size) : data(size, -1) { }
  bool union_set(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool find_set(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

vi cum(vi V) {
  vi U(SZ(V));
  partial_sum(ALL(V), begin(U));
  return U;
}

void solve() {
  int n;
  int ans = 0;

  string s;
  cin >> s;
  // vi v(n);
  // REP(i, n) {
  //   cin >> v[i];
  // }
  EACH(i, s)if(i == '1')ans++;

  cout << ans << endl;
  // REP(i, n) {
  //   cout << v[i];
  // }
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout << fixed << setprecision(15);
  solve();
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[9]={1,0,-1,0,1,1,-1,-1,0};
const ll dx[9]={0,-1,0,1,1,-1,1,-1,0};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const int mod = 1000000007;
const int max_n = 200005;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


int main(){
    ll n;cin >> n;
    vector<mint> dp(1<<n);dp[0]=1;
    vvl g(n+1);
    rep(i,1<<n)g[__builtin_popcount(i)].pb(i);
    rep(i,n){
        vl v(n);rep(j,n)cin >> v[j];
        for(auto bit:g[i+1]){
            if(__builtin_popcount(bit)!=i+1)continue;
            rep(j,n){
                if(bit&(1<<j)){
                    if(v[j])dp[bit]+=dp[bit-(1<<j)];
                }
            }
        }
    }
    cout << dp[(1<<n)-1] <<endl;
}

Measured memory_bytes: 39120
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
#define REP(i, a, n) for(int i=a; i<n; i++)
#define RREP(i, a, n) for(int i=n-1; i>=a; i--)
#define INF 1000000000
#define ll long long

int n, m;
int flag[200001];
vector<int> d, t;
int main()
{
	cin >> n;
	REP(i, 0, n) {
		int dd;
		cin >> dd;
		d.push_back(dd);
	}
	cin >> m;
	REP(i, 0, m) {
		int tt;
		cin >> tt;
		t.push_back(tt);
	}
	sort(d.begin(), d.end());

	bool pass = true;
	REP(i, 0, m) {
		auto itr = lower_bound(d.begin(), d.end(), t[i]);
		if (*itr != t[i]) {
			pass = false;
			break;
		}
		else {
			d.erase(itr);
		}
	}

	if (pass) cout << "YES" << endl;
	else cout << "NO" << endl;

	return 0;
}

Measured memory_bytes: 2548
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;

const int INF = 1<<30;
int c, n, m, s, d, a, b, f;
int path[101][101];
int dp[101][11] = {};

void solve(){
    // { cost, {source, ticket} }
    priority_queue<pair<int, pair<int,int>>> pq;
    pq.push({0, {s, c}});
    dp[s][c] = 0;

    while(!pq.empty()){
        auto p = pq.top();  pq.pop();
        int cost = -p.first;
        int source = p.second.first;
        int ticket = p.second.second;

        for(int dst = 0; dst < n; dst++){
            if(path[source][dst] == 0)  continue;

            if(dp[dst][ticket] > cost + path[source][dst]){
                dp[dst][ticket] = cost + path[source][dst];
                pq.push({-dp[dst][ticket], {dst, ticket}});
            }

            if(ticket > 0 && dp[dst][ticket-1] > cost + path[source][dst]/2){
                dp[dst][ticket-1] = cost + path[source][dst]/2;
                pq.push({-dp[dst][ticket-1], {dst, ticket-1}});
            }
        }
    }
}

int main(){
    while(cin >> c >> n >> m >> s >> d){
        if(c + n + m + s + d == 0)  break;

        s--; d--;
        // initialize
        memset(path, 0, sizeof(path));
        for(int i = 0; i < 101; i++){
            for(int j = 0; j < 11; j++){
                dp[i][j] = INF;
            }
        }

        for(int i = 0; i < m; i++){
            cin >> a >> b >> f;
            a--; b--;
            path[a][b] = path[b][a] = f;
        }

        solve();

        int ans = INF;
        for(int ticket = 0; ticket <= c; ticket++)  ans = min(ans, dp[d][ticket]);
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 3140
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxV = 90010;
const int maxN = 2e5+10;
const int MOD = 1e9+7;
const ll INF = 1000000000000000010LL;
const int inf = 1e9+10;
#define X first;
#define Y second;

vector<int> v[maxN];
int d[maxN];
double a[maxN];
int n,m;
double ans;
void block(int x)
{
	a[n] = 0;
	for(int i=n-1;i>=1;i--)
	{
		int num = (int)v[i].size();
		double maxv = 0;
		double sum = 0;
		for(auto to:v[i])
		{
			maxv = max(maxv,a[to]);
			sum += a[to];
		}
		if(i==x && num>=2)
		{
			sum -= maxv;
			num -= 1;
		}
		a[i] = sum/num + 1;
	}
	ans = min(ans,a[1]);
}
int main() {

	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
	}
	ans = INF+0.5;
	for(int i=0;i<n;i++)
	{
		block(i);
	}
	printf("%.10f\n",ans);
	return 0;
}

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

using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using pll = pair<ll,ll>;

#define INF (1LL << 60)
#define MOD 1000000007
#define PI 3.14159265358979323846

#define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define PR(x) cout << (x) << endl
#define PS(x) cout << (x) << " "
#define SZ(x) ((ll)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define REV(x) reverse(ALL((x)))
#define ASC(x) sort(ALL((x)))
#define DESC(x) ASC((x)); REV((x))
#define pb push_back
#define eb emplace_back

int main()
{
    ll N;
    cin >> N;
    ll M=0, A=0, R=0, C=0, H=0;
    REP(i,0,N) {
        string s;
        cin >> s;
        if(s[0] == 'M') ++M;
        if(s[0] == 'A') ++A;
        if(s[0] == 'R') ++R;
        if(s[0] == 'C') ++C;
        if(s[0] == 'H') ++H;
    }
    PR(M*(A*R+A*C+A*H+R*C+R*H+C*H)+A*(R*C+R*H+C*H)+R*C*H);



    return 0;
}

/*



*/

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

#define foreach(i, v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
#define BETWEEN(a, x, b) (a<=x&&x<b)

using namespace std;
typedef long long ll;

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

  int a,b,c;cin>>a>>b>>c;
  cout<<min(c,b/a)<<endl;

  return 0;
}


Measured memory_bytes: 3616
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;

int main() {
    int T; cin >> T;
    while (T--) {
        int a = 0, b = 0, succ = 1;
        for (int i = 0; i < 10; i++) {
            int n; scanf("%d", &n);
            if (a > b) {
                if (n > a) a = n;
                else if (n > b) b = n;
                else succ = 0;
            } else {
                if (n > b) b = n;
                else if (n > a) a = n;
                else succ = 0;
            }
        }
        puts(succ ? "YES" : "NO");
    }
    return 0;
}



Measured memory_bytes: 3136