akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
int dp[10001] = {0};
int max(int a, int b) {
    return a > b ? a : b;
}
int main() {
    int N, W, weight, value;
    scanf("%d%d", &N, &W);
    for(int i = 0;i < N;i++) {
        scanf("%d%d", &value, &weight);
        for(int j = W; j >= weight; j--)
            dp[j] = max(dp[j], dp[j - weight] + value);
    }
    printf("%d\n", dp[W]);
    return 0;
}

Measured memory_bytes: 2756
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <cstring>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
#define rep(i, n) for(long long i=0; i<n; i++)
#define reps(i, s, e) for(long long i=s; i<e; i++)
#define repr(i, n) for(long long i=n-1; i>=0; i--)
#define reprs(i, s, e) for(long long i=e-1; i>=s; i--)

ll pattylayer(ll n){
    return pow(2, n+1) - 1;
}

ll totallayer(ll n){
    return pow(2, n) + 3*(pow(2, n) - 1);
}

ll rec(ll n, ll x){
    // cout << n << " " << x << endl;
    // cout << " " << totallayer(n) << " " << pattylayer(n) << endl;

    if(x == 0){
        return 0;
    }
    if(n == 0){
        return 1;
    }

    if(2*x - 1 == totallayer(n)){
        // cout << "cond1 " << endl;
        return pattylayer(n-1) + 1;
    }
    else if(2*x - 1 > totallayer(n)){
        // cout << "cond2 " << endl;
        return 1 + pattylayer(n-1) + rec(n-1, x - totallayer(n-1) - 2);
    }
    else{
        // cout << "cond3 " << endl;
        return rec(n-1, x-1);
    }
}

int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n, x; cin >> n >> x;

    cout << rec(n, x);

    return 0;
}

Measured memory_bytes: 384
// vvvvvvvvvvvv TEMPLATE vvvvvvvvvvvv
#include <bits/stdc++.h>
using namespace std; using ll = long long; using P = pair<ll, ll>;
const ll linf = 1e18; const double eps = 1e-12, pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define each(i,a) for (auto&& i : a)
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)
template<typename T> ll min(ll a, const T&& b) { return a < b ? a : b; }
template<typename T> ll min(const T&& a, ll b) { return a < b ? a : b; }
template<typename T> ll max(ll a, const T&& b) { return a > b ? a : b; }
template<typename T> ll max(const T&& a, ll b) { return a > b ? a : b; }
template<typename Head> void out(Head h) { cout << h << endl; } template<typename Head, typename... Tail>void out(Head h, Tail... t) { cout << h << " "; out(t...); }
template<typename T> istream& operator>>(istream& is, vector<T>& v) { each(x,v) is >> x; return is; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) { rep(i,v.size()) { if (i) os << " "; os << v[i]; } return os; }
ostream& operator<<(ostream& os, const vector<string>& v) { rep(i,v.size()) { if (i) os << endl; os << v[i]; } return os; }
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) { rep(i,v.size()) { if (i) os << endl; os << v[i]; } return os; }
template<typename T1, typename T2> ostream& operator<<(ostream& os, const pair<T1, T2>& p) { return os << "(" << p.first << ", " << p.second << ")"; }
struct yes_no : std::numpunct<char> { string_type do_truename() const { return "Yes"; } string_type do_falsename() const { return "No"; } };
void solve(); int main() {
  ios::sync_with_stdio(false); cin.tie(0); locale loc(locale(), new yes_no); cout.imbue(loc); cout << fixed << setprecision(10) << boolalpha;
  solve();
}
// ^^^^^^^^^^^^ TEMPLATE ^^^^^^^^^^^^

void solve() {
  ll n; cin >> n;
  vector<ll> p(4), t(4); cin >> p >> t;
  ll ans = linf;
  rep(a, n+1) rep(b, n-a+1) rep(c, n-a-b+1) rep(d, n-a-b-c+1) {
    if (a * t[0] + b * t[1] + c * t[2] + d * t[3] >= n) {
      chmin(ans, a * p[0] + b * p[1] + c * p[2] + d * p[3]);
    }
  }
  cout << ans << endl;
}



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

using namespace std;

int main(){
    string s, s1;
    cin >> s >> s1;
    if(s.length() > s1.length())cout << "GREATER";
    else if(s1.length() > s.length()) cout << "LESS";
    else{
        for(int i = 0; i < s.length(); ++i){
            if(s[i] > s1[i]){
                cout << "GREATER";
                return 0;
            }else if(s1[i] > s[i]){
                cout << "LESS";
                return 0;
            }
        }
        cout << "EQUAL";
    }
    return 0;

}


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

int main(){
    int n;
    cin>>n;
    int dp[3];
    cin>>dp[0];
    cin>>dp[1];
    cin>>dp[2];
    for(int i=1;i<n;i++){
        int temp[3];
        cin>>temp[0];
        cin>>temp[1];
        cin>>temp[2];
        temp[0]= temp[0]+max(dp[1],dp[2]);
        temp[1]=temp[1]+max(dp[0],dp[2]);
        temp[2]=temp[2]+max(dp[1],dp[0]);
        dp[0]=temp[0];
        dp[1]=temp[1];
        dp[2]=temp[2];
    }
    cout<<max(dp[0],max(dp[1],dp[2]));
    return 0;
    
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {

  long n,x,m;
  scanf("%ld %ld %ld", &n, &x, &m);
  long list[m];
  for (long i = 0; i < m; i++) {
    list[i] = 0;
  }
  long cur = x,first,first_sum,set,set_sum;
  list[cur] = 1;
  for (long i = 2; ; i++) {
    cur = (cur*cur)%m;
    if (list[cur] == 0) {
      list[cur] = i;
    } else {
      set = i-list[cur];
      first = i-set;
      break;
    }
  }
  cur = x;
  first_sum = 0;
  for (long i = 0; i < first; i++) {
    first_sum += cur;
    cur = (cur*cur)%m;
  }
  set_sum = 0;
  for (long i = 0; i < set; i++) {
    set_sum += cur;
    cur = (cur*cur)%m;
  }
  long ans = 0;
  if (n >= first) {
    ans += first_sum;
    n -= first;
    ans += set_sum*(n/set);
    n %= set;
  } else {
    cur = x;
  }
  for (long i = 0; i < n; i++) {
    ans += cur;
    cur = (cur*cur)%m;
  }
  printf("%ld\n", ans);

  return 0;
}

Measured memory_bytes: 2472
#include <bits/stdc++.h>
using namespace std;
int main(void) {
  int n, a[100001];

  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];

  int ans = 0;
  for (int i = 1; i <= n; i++) {
    if (a[a[i]] == i) {
      ans++;
      a[i] = 0;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 640
///Bismillahir Rahmanir Rahim
#define ll long long
#define ull unsigned long long
#define scf1(a)  scanf("%lld",&a)
#define scf2(a,b)  scanf("%lld %lld",&a,&b)
#define pf    printf
#define pb    push_back
#define rsrt(v) reverse(v.begin(),v.end())
#define srt(v) sort(v.begin(),v.end())
#define ff first
#define ss second
#define spd ios_base::sync_with_stdio(false)
#include<bits/stdc++.h>
using namespace std;
ll arr[100005][4];
ll dp[100005][4];
ll n;
ll solve(ll day, ll act)
{
    if(day>n)return 0;

    if(dp[day][act]!=-1)return dp[day][act];
    ll res = 0;
    for(ll i=1;i<=3;i++)
    {
         if(act!=i)
         res = max(res,(arr[day][i] + solve(day+1,i)));
    }

    dp[day][act] = res;

    return dp[day][act];
}
int main()
{
    ll i,j,k,a,b;

    cin>>n;

    for(i=1;i<=n;i++)
    {
        for(j=1;j<=3;j++)
        {
            cin>>arr[i][j];
        }
    }
    memset(dp,-1,sizeof(dp));
    cout<<solve(1,0)<<endl;
}


Measured memory_bytes: 14336
def main():
  a, b, x = map(int, input().split())
  vm = a*a*b
  if x>vm/2:
    return math.degrees(math.atan(2*(vm-x)/a**3))
  else:
    return math.degrees(math.atan(a*b*b/(2*x)))
if __name__ == '__main__':
  import math
  print(main())

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin>>n;
	vector<long long int> arr (n);
	long long int su=0;
	unordered_map<long long int,long long int> mp;
	for(int i=0;i<n;i++)
	{
	    cin>>arr[i];
	}
	for(int i=0;i<n;i++)
	{
	    mp[arr[i]]++;
	    su+=arr[i];
	}
	int q;
	cin>>q;
	vector<long long int> res;
	for(int i=0;i<q;i++)
	{
	    long long int a;
	    long long int b;
	    cin>>a>>b;
	    if(mp.find(a)!=mp.end())
	    {
	    long long x=mp[a];
	    su=su-a*x;
	    su=su+b*x;
	    mp[b]+=x;
	    mp.erase(a);
	    }
	    res.push_back(su);
	    
	}
	for(int i=0;i<res.size();i++)
	{
	    cout<<res[i]<<endl;
	}
    return 0;
}


Measured memory_bytes: 8436
while True:
  n, k = map(int, input().split())
  if n == 0:
    break

  s_list = list(map(int, input().split()))
  for _ in range(n):
    b_list = list(map(int, input().split()))
    for i in range(k):
      s_list[i] -= b_list[i]
  for s in s_list:
    if s < 0:
      print("No")
      break
  else:
    print("Yes")


Measured memory_bytes: 5612
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <string>
using namespace std;
int main(void){
  int a, b, c;
  cin>>a>>b>>c;
  if(c>=a&&c<=b){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner in = new java.util.Scanner(System.in);
		int N = in.nextInt();
		int ans = 0;
		
		for(int i=1; i<=N; i=i+2) {
			if(yaku(i) == 8) {
				ans++;
			}
		}
		
		System.out.println(ans);
		in.close();
	}
	
	public static int yaku(int N) {
		int count=0;
		for(int i=1; i<=(int)Math.sqrt(N); i++) {
			if(N%i==0) {
				count += 2;
			}
		}
		return count;
	}
}

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

#define     fast()              ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
#define     ll                  long long int
#define     test()              ll t; cin>>t; while(t--) 
#define     lp0(i,begin,end)    for(ll i=begin;i<end;i++)
#define     lp1(i,begin,end)    for(ll i=begin;i<=end;i++)
#define     rlp(i,begin,end)    for(ll i=end;i>=begin;i--)
#define     prec(n)             fixed<<setprecision(n)
#define     initial(a,i)        memset(a,i,sizeof(a))
#define     pb                  push_back
#define     PI                  3.1415926535897932384626433832795
#define     MOD                 1000000007
#define     F                   first
#define     S                   second
#define     all(a)              (a).begin(),(a).end()
#define     BPC(x)              __builtin_popcountll(x)
#define     gcd(a,b)            __gcd(a,b)

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

ll power(ll x,ll n)
{
    ll result = 1;
    while (n)
    {
        if (n & 1)
            result = result * x;
        n = n / 2;
        x = x * x;
    }
    return result;
}


// Solution Function
void solution(ll compte)
{
    // cout<<compte<<"\n";

    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll p1 = a*c;
    ll p2 =a *d;
    ll p3 = b*c;
    ll p4 = b*d;

    ll ans = max(p1,max(p2,max(p3,p4)));
    cout<<ans<<"\n";
}

// Driver Function
int main()
{
    ll compte = 1;
    //test()
    //{
        solution(compte);
        compte++;
    //}
    return 0;
}


Measured memory_bytes: 3632
n=int(input())
hi=[]
for i in map(int,input().split()):
    hi.append(i)
YesNo="Yes"    
for i in range(n-1,1,-1):
    if hi[i]+2<=hi[i-1]:
        YesNo="No"    
#        print("No")
        break
    elif hi[i]+1==hi[i-1]:
        hi[i-1]=hi[i-1]-1
print(YesNo)

Measured memory_bytes: 14396
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define LINF (ll)INF*INF
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

#define int ll //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;
typedef vector<pii> vp;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b){
    return a/gcd(a,b)*b;
}


signed main(void) {
    int N,M;
    int P[100000],Y[100000];
    vector<int> yd[100001];
    cin>>N>>M;
    rep(i,M){cin>>P[i]>>Y[i];
        yd[P[i]].push_back(Y[i]);}
    rep(i,N)sort(yd[i+1].begin(),yd[i+1].end());
    rep(i,M)printf("%012lld\n",(P[i])*1000000+(lower_bound(yd[P[i]]. begin(),yd[P[i]].end(),Y[i])-yd[P[i]].begin())+1);
    }

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

namespace ITP1 {
	class Program {
		public static void Main() {
			int[] input = Console.ReadLine()
				.Split()
				.Select(int.Parse)
				.ToArray();
			int a = input[0], b = input[1], c = input[2];
			bool b1 = a < b;
			bool b2 = a < c;
			bool b3 = b < c;

			/*
			 *		abc	acb	bac	bca	cab	cba
			 *	b1	T	T	F	F	T	F
			 *	b2	T	T	T	F	F	F
			 *	b3	T	F	T	T	F	F
			 */
			if (b1) {
				if (b2) {
					if (b3) Console.WriteLine(a + " " + b + " " + c);
					else Console.WriteLine(a + " " + c + " " + b);
				} else Console.WriteLine(c + " " + a + " " + b);
			} else {
				if (b2) Console.WriteLine(b + " " + a + " " + c);
				else {
					if (b3) Console.WriteLine(b + " " + c + " " + a);
					else Console.WriteLine(c + " " + b + " " + a);
				}
			}
		}
	}
}



Measured memory_bytes: 9572
# match of  a vs b
def match(a, b):
    """
    :type a: int
    :type b: int
    :rtype: int
    """
    return min(a,b) + N * max(a,b)

N = int(input())
A = []
for i in range(N):
    A.append( [ int(n)-1 for n in input().split() ] )

# NEXT[ match(a,b) ]  must be held after  match(a,b)
NEXT = [ [] for i in range(N*N) ]
# How many matches must be held before  match(a,b)
before = [ 0 for i in range(N*N) ]

for i in range(N):
    for j in range(N-2):
        # i vs A[i][j+1]  must be held after  i vs A[i][j]
        NEXT[ match(i,A[i][j]) ].append( match(i,A[i][j+1]) )
        before[ match(i,A[i][j+1]) ] += 1
        
q  = []
q0 = []

for i in range(N):
    for j in range(i+1,N):
        if before[ match(i,j) ] == 0:
            q.append( match(i,j) )
            
day = 0

while True:
    day += 1
    for M in q:
        for m in NEXT[M]:
            before[m] -= 1
            if before[m] == 0:
                q0.append(m)
        NEXT[M] = []
    q = q0
    q0 = []
    #print(NEXT)
    #print(before)
    if q == []:
        break

if NEXT == [ [] for i in range(N*N) ]:
    print(day)
else:
    print(-1)


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

int main()
{
    string a;
    int b, x[3], res1, res2 = 0;
    stack<int> s, t;

    cin >> a >> b;

    for( int i = 0; i < a.size(); i++ )
    {
        s.push(a[i]-'0');
        if( s.size() == 3 )
        {
            for( int j = 0; j < 3; j++ )
            {
                x[j] = s.top();
                s.pop();
            }
            if( x[1] == '+' - '0' )
                s.push( x[0] + x[2] );
            else
                s.push( x[0] * x[2] );
        }
    }

    res1 = s.top();

    t.push(a[0]-'0');
    for( int i = 2; i < a.size(); i++ )
    {
        if( a[i-1] == '+' )
            t.push(a[i]-'0');
        if( a[i-1] == '*' )
        {
            x[0] = t.top(); t.pop();
            t.push(x[0]*(a[i]-'0'));
        }
    }

    while( !t.empty() )
    {
        res2 += t.top();
        t.pop();
    }

    if( b == res1 && b != res2 )
        cout << 'L';
    else if( b != res1 && b == res2 )
        cout << 'M';
    else if( b == res1 && b == res2 )
        cout << 'U';
    else
        cout << 'I';
    
    cout << endl;

    return 0;
}


Measured memory_bytes: 3224
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import static java.lang.Integer.parseInt;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line = "";

		while ((line = br.readLine()) != null && !line.isEmpty()) {
			int l, a, b, c, d;
			l = parseInt(line);
			a = parseInt(br.readLine());
			b = parseInt(br.readLine());
			c = parseInt(br.readLine());
			d = parseInt(br.readLine());
			int ac, bd;
			ac = (a % c > 0) ? a / c + 1 : a / c;
			bd = (b % d > 0) ? b / d + 1 : b / d;
			System.out.println(ac > bd ? l - ac : l - bd);
		}
	}
}

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

using namespace std;

int INF = INT_MAX;

struct SegmentTree{
private:
    int n; //セグ木のサイズ(=ノード数)
    vector<int> node;

public:
    //コンストラクタ: 元配列vを基にセグメント木を作成
    SegmentTree(){}
    SegmentTree(vector<int> v){
        int sz = v.size();
        int height = ceil(log2(sz)); // sz = 4 -> height = 2, sz = 5 -> height = 3
        n = pow(2, height); //セグ木における葉の数
        node.resize(2*n-1, INF); //RMQの場合,無効なノードはintの最大値で初期化

        //まずは最下段に値を入れる
        for(int i = 0; i < sz; i++) node[i+n-1] = v[i];
        //次に、根に登りつつ値を入れる
        for(int i = n-2; i >= 0; i--) node[i] = min(node[(i << 1) + 1], node[(i << 1) + 2]);
    }
    //値の取得クエリ [l, r)の最小値を取得
    int getmin(int a, int b, int k=0, int l=0, int r=-1){
        //最初の呼び出し時の対象区間は[0, n)
        if(r < 0) r = n;

        //[a, b)と[l, r)が交わらない -> INFを返す
        if(r <= a || b <= l) return INF;

        //[a, b)は[l, r)を完全に含む -> 現在のノードの値を返す
        if(a <= l && r <= b) return node[k];

        //[a, b)は[l, r)を一部含む -> 子について探索を行う
        int vl = getmin(a, b, (k << 1) + 1, l, (l+r)/2);
        int vr = getmin(a, b, (k << 1) + 2, (l+r)/2, r);
        return min(vl, vr);
    }

    //値の1点更新クエリ
    void update(int idx, int val){
        node[idx + (n-1)] = val;
        idx = idx + (n-1);
        while(idx > 0){
            idx = (idx % 2 == 0)? idx/2 - 1 : idx/2;
            node[idx] = min(node[(idx << 1)+1], node[(idx << 1)+2]);
        }
    }

    void show(){
        for(int i = 0; i < n; i++){
            cout << node[i + (n-1)] << " ";
        }
        cout << endl;
    }
};

int main(){
    int n, q; cin >> n >> q;
    vector<int> A(n, INF);
    SegmentTree segtree(A);
    for(int i = 0; i < q; i++){
        int cmd, x, y; cin >> cmd >> x >> y;
        if(cmd == 0){
            segtree.update(x, y);
        }
        else{
            cout << segtree.getmin(x, y+1) << endl;
        }
        //segtree.show();
    }
    return 0;
}


Measured memory_bytes: 4960
use std::io::Read;
use std::cmp::{max, min};

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: usize = iterator.next().unwrap().parse().unwrap();

    let mut ans: usize = 100;
    let mut a: usize = 1;
    while a * a <= n {
        if n % a != 0 {
            a += 1;
            continue;
        }
        let b = n / a;
        ans = min(ans, f(a, b));
        a += 1;
    }
    return ans.to_string();
}

fn f(a: usize, b: usize) -> usize {
    let a_len = format!("{}", a).len();
    let b_len = format!("{}", b).len();
    return max(a_len, b_len);
}


Measured memory_bytes: 4352
#define _CRT_SECURE_NO_WARNINGS

/* include ***********************/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

/* define *************************/
//for
#define REP(i,n) for(int i=0,i##_len=(int)(n);i<i##_len;i++)
#define REPS(i,n) for(int i=1,i##_len=(int)(n);i<=i##_len;i++)
#define RREP(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define RREPS(i,n) for(int i=(int)(n);i>0;i--)
#define FOR(i,s,n) for(int i=(int)(s),i##_len=(int)(n);i<i##_len;i++)
#define RFOR(i,s,n) for(int i=(int)(s)-1,i##_len=(int)(n);i>=i##_len;i--)

//printf
#define PRINTD(d) printf("%d\n",(d))
#define PRINTL(d) printf("%lld\n",(d))

//memset
#define m0(s) memset(s,0,sizeof(s))
#define ml(s) memset(s,63,sizeof(s))
#define fill(s,c) memset(s,c,sizeof(s))

#define INF 1e9
#define MOD 1000000007

typedef long long ll;
typedef unsigned long long ull;

int diff[4][2] = {
	{ 0, -1 },
	{ -1, 0 },
	{ 1, 0 },
	{ 0, 1 },
};

int Min(int a, int b) {
	return (a)<(b) ? (a) : (b);
}
int Max(int  a, int  b) {
	return (a) > (b) ? (a) : (b);
}
void Swap(int *a, int *b) {
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int main() {
	ll k, a, b;
	scanf("%lld%lld%lld", &k, &a, &b);
	if (b <= a + 2) {
		PRINTL(k+1);
		return 0;
	}
	ll ans = a;
	k -= a - 1;
	if (k % 2) {
		ans++;
		k--;
	}
	ans += (b - a)*(k / 2);
	PRINTL(ans);
}

Measured memory_bytes: 128
#include<cstdio>
int f[4333][4333];
int s[2333];
int main()
{
	int n,m,k,p;
	!scanf("%d%d%d",&n,&m,&k);
	for(int p=k;p<=n+m;p+=k-1)
	{
		for(int i=1;i<=n;i++)
		{
			if(p-i<1)break;
			int r=i-(k-1)>0?i-(k-1):0;
			f[i][p-i]=(s[i+1]-s[r]+1000000008)%1000000007;
		}
		for(int i=0;i<=n;i++)s[i+1]=(s[i]+f[i][p-i])%1000000007;
	}
	printf("%d",f[n][m]);
	return 0;
}

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

using namespace std;

long long x, y, tempp, l, summ, ans, fac;
const long long mod = 1e9 + 7;

long long powermod(long long a, long long b) {
	long long ans = 1;
	a %= mod;
	while (b) {
		if (b & 1) ans = (ans * a) % mod;
		a = (a * a) % mod;
		b >>= 1;
	}
	return ans;
}

long long divi(long long q, long long d) {
	long long temp = 1;
	temp = (q * powermod(d, mod - 2)) % mod;
	return temp;
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> x >> y;
	if ((x + y) % 3) {
		cout << 0 << endl;
		exit(0);
	}
	if (x < y) {
		tempp = y;
		y = x;
		x = tempp;
	}
	if (x > 2 * y) {
		cout << 0 << endl;
		exit(0);
	}
	l = x - y;
	summ = (x + y) / 3;
	l = (summ - l) /2;
	ans = 1;
	for (int i = 0; i<l; i++) {
		ans = (ans * (summ - i)) % mod;
	}
	fac = 1;
	for (int i = 1; i <= l; i++) fac = (fac * i) % mod;
	cout << divi(ans, fac) << endl;
}

Measured memory_bytes: 256
x,i,t;
a(x){
    if(x==2)return 1;
    if(x<2||x%2==0)return 0;
    for(i=3;i<=sqrt(x);i+=2){
        if(x%i==0)return 0;
    }
    return 1;
}
main(){
    for(scanf("%d",&x);~scanf("%d",&x);t+=a(x));
    printf("%d\n",t);
}

Measured memory_bytes: 1788
h,w = map(int,input().split())
a = ["." for i in range(w+2)]
dot_map = [a]
for _ in range(h):
    l = list(input())
    l.insert(0, ".")
    l.append(".")
    dot_map.append(l)
dot_map.append(a)
breaker = 0

for i in range(1, h+1):
    if breaker == 1:
        break
    else:
        for j in range(1,w+1):
            if dot_map[i][j] == "#":
                flag = 0
                if dot_map[i-1][j] == "#":
                    flag += 1
                elif dot_map[i][j-1] == "#":
                    flag += 1
                elif dot_map[i][j+1] == "#":
                    flag += 1
                elif dot_map[i+1][j] == "#":
                    flag += 1
                if flag == 0:
                    breaker += 1
                    break

if breaker == 0:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <stdio.h>
int main(void){
    int i, j, k, t;
    int n, c[501], s[501], f[501];
    
    scanf("%d", &n);
    for(i = 0; i < n; i++){
        scanf("%d %d %d", &c[i], &s[i], &f[i]);
    }
    for(i = 0; i < n; i++){ //start station
        t = 0;
        for(j = i; j < n - 1; j++){ //through station
            for(k = 0; s[j]+f[j]*k < t; k++);
            t = s[j] + f[j]*k + c[j];
        }
        printf("%d\n", t);
    }
    
    return 0;
}


Measured memory_bytes: 128
# -*- coding: utf-8 -*-
#import sys
#sys.setrecursionlimit(1145141919)


N = int(input())
tree = {n:{"parent":-1, "left": -1, "right": -1} for n in range(N)} # left-child right-sibing
parent = set([n for n in range(N)])
for n in range(N):
    inp = [int(n) for n in input().split()]
    tree[inp[0]]["children"] = inp[2:]

    tree[inp[0]]["left"] = inp[2] if len(inp) > 2 else -1
    
    for ip in inp[2:]:
        tree[ip]["parent"] = inp[0]
    
    for i, ip in enumerate(inp[2:-1]):
        tree[inp[2+i]]["right"] = inp[3+i]
    parent = parent.difference(inp[2:])    

def set_depth(n, depth):
    print(depth)
    tree[n]["depth"] = depth
    if tree[n]["left"] != -1:
        set_depth(tree[n]["left"], depth+1)
    if tree[n]["right"] != -1:
        set_depth(tree[n]["right"], depth)

def get_depth(n):
    d = 0
    while tree[n]["parent"] != -1:
        d += 1
        n = tree[n]["parent"]
    return d

#set_depth(parent.pop(), 0)
        
for n in range(N):
    tree[n]["depth"] = get_depth(n)
    if tree[n]["parent"] == -1:
        tree[n]["type"] = "root"
    elif tree[n]["children"] != []:
        tree[n]["type"] = "internal node"
    else:
        tree[n]["type"] = "leaf"
        
    print("node {}: parent = {}, depth = {}, {}, {}"\
          .format(n, tree[n]["parent"], tree[n]["depth"], tree[n]["type"], tree[n]["children"]))

Measured memory_bytes: 77300
#include<bits/stdc++.h>
using namespace std;
signed main() {
	int n, p = -1,i,X,Y; cin >> n;
	int x[105], y[105], h[105];
	for (i=0;i<n;i++) {
		cin >> x[i] >> y[i] >> h[i];
		if (h[i] != 0)p = i;
	}
	for (X = 0; X <= 100; X++) {
		for (Y = 0; Y <= 100; Y++) {
			int H = abs(x[p] - X) + abs(y[p] - Y) + h[p];
			if (H <= 0)continue;
			bool flag = 1;
			for (i = 0; i < n; i++)
				if (h[i] != max(H - abs(X - x[i]) - abs(Y - y[i]), (int)0))flag = 0;
			if (flag) {
				cout << X << ' ' << Y << ' ' << H << endl;
				cin >> n;
				return 0;
			}
		}
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll p,q;
	cin>>p>>q;
	ll ans = 1e16;
	if (q-p>=2019)
		cout<<0;
	else
	{
		for(ll i=p;i<=q;i++)
		{
			for(ll j=i+1;j<=q;j++)
			{
				ans = min(ans , ((i%2019)*(j%2019))%2019);
			}
		}
		cout<<ans;
	}
	
}

Measured memory_bytes: 256
/*
NOTE :
*min_element(.begin(),.end())
*max_element(.begin(),.end())
stack push pop top
queue push pop front
priority_queue<> pq
 push()  pop() size()  top()
map<>
 find() begin() end() insert(map<>::value_type())
pair<>
sort(.begin(), .end())
sort(arr, arr+N)
sort(a, a+N, greater<int>())
binary_search(vc.begin(), vc.end(), x)  //binary_search???true, false?????????
vector<int>::iterator lit = lower_bound(vc.begin(), vc.end(), x);
  lower_bound?????????????????????"??\???"????????????????????????????????????????????¬???????????????
vector<int>::iterator uit = upper_bound(vc.begin(), vc.end(), x);
  upper_bound????????????????????????"?¶???????"?????????????????????????????????????????¬???????????????
*/
#include <iostream>
#include <cstdio>
#include <climits>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <valarray>
#include <utility>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>

#define MAX 100
#define INF 1<<20
#define LLINF 10e12 // 1<<31 // 2^31
#define REP(i,n) for(int i=0;i<n;i++)
#define REP2(i,a,n) for(int i=(a);i<(n);i++)
#define SET(a,c) memset(a,c,sizeof a)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define FOREACH(i,c) for(auto (i) : (c))
#define BIT(i,j) ((i)>>(j))&1
#define ALL(o) (o).begin(), (o).end()
#define ERASE(o) (o).erase(unique(ALL((o))), (o).end());

using namespace std;
typedef long long ll;
typedef valarray<int> array_t;
/////

/////
int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  // FROM HERE
  int n;
  stack<int> T;
  vector<int> V;
  while (cin >> n)
  {
    if(n == 0)
    {
      V.push_back(T.top());
      T.pop();
    }
    else T.push(n);
  }
  FOR(a,V) cout << *a << endl;
  return 0;
}

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

int main() {
    int a, b;
    cin >> a >> b;
    cout << (b % a == 0 ? a + b : b - a) << endl;
}

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

int main(){
  string s;
  rep(i,3){
    cin >> s;
    cout << s[0];
    s = "";
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<string.h>

using namespace std;

typedef pair<int,int> pii;

#define rep(i,j) for(int i=0;i<(j);i++)
#define reps(i,j,k) for(int i=j;i<=k;i++)

class node{
public:
	vector<int> s;
	int f;
};

node t[21];

void setf(int a){
	node *n;
	n = &t[a];
	int l = n->s.size();
	rep(i,l){
		if( (n->f)+1 >= t[n->s[i]].f){
			t[n->s[i]].f=(n->f)+1;
			setf(n->s[i]);
		}
	}
}

int main(){
	int n,m,x,y,cnt=0;
	scanf("%d%d",&m,&n);
	rep(i,21){
		t[i].f=0;
	}
	rep(i,n){
		scanf("%d%d",&x,&y);
		t[x].s.push_back(y);
		setf(x);
	}
	for(int i=0;i<=m&&cnt<m;i++){
		reps(j,1,m){
			if(t[j].f==i)printf("%d\n",j);
		}
	}
	return 0;
}

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

int main(){
  string x,y,z;
  
  cin>>x>>y>>z;
  
  string answer="";
  
  answer+=x.at(0);
  answer+=y.at(1);
  answer+=z.at(2);
  
  
  
  
  cout<<answer<<endl;
  
  
}

  













Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        
        int p8 = Integer.parseInt(sc.next());
        int p10 = Integer.parseInt(sc.next());
        
        int i=0;
        int a=0, b=0;
        for(i=0; i<1100; i++){
            a=i*2/25;
            b=i/10;
            if((a==p8)&&(b==p10)) break;
        }
        if(i>1001) System.out.println(-1);
        else System.out.println(i);
        //String s = sc.next();
        
    }
    
}

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

int main(){
	int n;
	int k;
	int l=1;
	int i=0;
	int sum=1;
	cin>>n>>k;
	for(i=0;i<33;i++){
		l=l*k;
		sum=l-1;
		if(sum>=n){
			break;
		}
	}
	cout<<i+1;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int s[m]; char c[m];
    for (int i = 0; i < m; i++) {
        cin >> s[i] >> c[i];
    }
    for (int i = 0; i < 1000; i++) {
        bool flag = true;
        string a  = to_string(i);
        if (a.size() != n) continue;
        for (int j = 0; j < m; j++) {
            if (a[s[j] - 1] != c[j]) flag = false;
        }
        if (flag) {
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

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

#define LL long long
#define LD long double
#define SC(t,x) static_cast<t>(x)
#define AR(t) vector < t >
#define PII pair < int, int >
#define PLL pair < LL, LL >
#define PIL pair < int, LL >
#define PLI pair < LL, int >
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define PRF first
#define PRS second
#define INIT(ar,val) memset ( ar, val, sizeof ( ar ) )
#define lp(loop,start,end) for ( int loop = start; loop < end; ++loop )
#define lpd(loop,start,end) for ( int loop = start; loop > end; --loop )
#define lpi(loop,start,end) for ( int loop = start; loop <= end; ++loop )
#define lpdi(loop,start,end) for ( int loop = start; loop >= end; --loop )
#define qmax(a,b) (((a)>(b))?(a):(b))
#define qmin(a,b) (((a)<(b))?(a):(b))
#define qabs(a) (((a)>=0)?(a):(-(a)))

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 100007;

struct eT
{
	void setd ( int _u, int _v, int _w, int _l )
	{
		u = _u, v = _v, w = _w, last = _l;
	}

	int u, v, w, last;
}edge[MAXN*2];

int n;
int ke, la[MAXN];
int fw[MAXN], sz[MAXN];
LL ans, mini;

void init ();
void input ();
void work ();

int getsize ( int now, int fa, int nfw );
void dfs ( int now, int fa );



int main ()
{
	init ();
	input ();
	work ();
}



void init ()
{
	// Init Everything Here

	ios::sync_with_stdio ( false );
}

void input ()
{
	// input method

	scanf ( "%d", &n );
	ke = 0;
	INIT ( la, -1 );
	int u, v, w;
	lp ( i, 1, n ) {
		scanf ( "%d%d%d", &u, &v, &w ); 
		edge[ke].setd ( u, v, w, la[u] );
		la[u] = ke++;
		edge[ke].setd ( v, u, w, la[v] );
		la[v] = ke++;
	}
}

void work ()
{
	// main work

	getsize ( 1, -1, 0 );
	mini = INF;
	dfs ( 1, -1 );

	cout << ans * 2 - mini << endl;
}



int getsize ( int now, int fa, int nfw )
{
	fw[now] = nfw;
	sz[now] = 1;
	for ( int i = la[now]; ~i; i = edge[i].last ) if ( edge[i].v ^ fa ) sz[now] += getsize ( edge[i].v, now, edge[i].w );
	ans += SC ( LL, nfw ) * qmin ( sz[now], n - sz[now] );
	return sz[now];
}

void dfs ( int now, int fa )
{
	bool flag = true;
	for ( int i = la[now]; ~i; i = edge[i].last ) {
		if ( ( edge[i].v ^ fa ) && ( sz[edge[i].v] >= n - sz[edge[i].v] ) ) {
			dfs ( edge[i].v, now );
			flag = false;
			break;
		}
	}

	if ( flag ) {
		mini = qmin ( mini, fw[now] );

		if ( sz[now] > n - sz[now] ) {
			for ( int i = la[now]; ~i; i = edge[i].last ) if ( edge[i].v ^ fa ) dfs ( edge[i].v, now );
		}
	}
}

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

using namespace std;


int V[26];
bool flag = true;


int solve(string &s, int b, int e){
    if(flag == false) return -1;

	
    if(e - b == 1) {
		return s[b] - 'a';
	}

    int x;

    for(int i = b, d = 0; i < e; i++){
        if(s[i] == '[') {
            d++;
        } else if(s[i] == ']') {
            d--;
        } else if(s[i] == '-') {
            if(d ==  1) x = i;
        }
    }
	
    int ch1 = solve(s, b+1, x);
    int ch2 = solve(s, x+1, e-1);
	
    if(ch1 == -1 || ch2 == -1) return -1;
	
    if(!!V[ch1] == !!V[ch2]) {
        flag = false;
        return -1;
    } else if(V[ch1]) {
        V[ch1]--;

        return ch1;
    } else {
        V[ch2]--;
        return ch2;
    }

	
    return -1;
}

signed main(){
    string s;

    cin>>s;

    char a;
    int v;

    int N = 0;

    for(int i = 0; i<  s.size(); i++){
        if('a' <= s[i] && s[i] <= 'z') N++;
    }
	
    for(int i = 0; i < N; i++){
		if(!(cin>>a)) break;
		
		cin>>v;
		
        V[a - 'a'] = v;
    }

    solve(s, 0, s.size());
	
	for(int i = 0; i < 26; i++){
		if(V[i]) flag = false;
	}

    if(flag == true) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}




Measured memory_bytes: 3220
import math
def ip():return int(input())
def inp():return map(int,input().split())
def inpstr():return map(str,input().split())
def linp():return list(map(int,input().split()))
def linpstr():return list(map(str,input().split()))

n=ip()
city=[]
score=[]
for i in range(n):
    s,p=inpstr()
    city.append([s,-int(p),i+1])
city.sort()
for i in range(n):print(city[i][2])


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define P pair<int,int>
using ll=int64_t;
using namespace std;
#define ketasuu(n) fixed<<setprecision(n)
#define btoe(p) p.begin(),p.end()
#define etob(p) p.rbegin(),p.rend()


const ll inf=4e18;

int main(){
    ll n; cin>>n;
    vector<ll> p(n);
    rep(i,n) cin>>p[i];
    rep(i,n) p[i]-=(i+1);
    sort(btoe(p));
    ll med,ans=inf, an=0;
    if(n%2==0) med=(p[n/2]+p[n/2-1])/2;
    else med=p[n/2];
    for(ll i=med-10; i<=med+10; ++i){
        an=0;
        rep(j,n) an+=abs(p[j]-i);
        ans=min(ans,an);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 1792
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import static java.lang.Integer.parseInt;

public class Main {

	static int MAX = 999 + 51;
	static char TERM = 'Z';

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;

		while ((line = br.readLine()) != null && !line.isEmpty()) {

			int n = parseInt(line);
			if (n == 0) break;

			//load and pre proc.
			char[][] board = new char[n][MAX];
			int check = 0;
			for (int i = 0; i < n; i++) {
				line = br.readLine();
				for (int j = 0; j < line.length(); j++) {
					char c = line.charAt(j);
					board[i][j] = c;
					if (c == '.') {
						check++;
						if (line.charAt(j + 1) >= 'a') {
							board[i][j] = '+';
							check--;
						}
					}
				}
				board[i][line.length()] = TERM;
			}

			//write off
			//vertical bar.
			for (int j = 0; j < MAX; j++) {
				for (int i = n - 1; i > 0; i--) {
					char c = board[i][j];
					if (c == '+') {
						for (int k = i - 1; k > 0; k--) {
							if (board[k][j] == '.') {
								board[k][j] = '|';
								check--;
							} else break;
						}
					} else if (c == '.') {
						board[i][j] = ' ';
						check--;
					}
				}
				if (check == 0) break;
			}

			//ans.
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < MAX; j++) {
					char c = board[i][j];
					if (c == TERM) break;
					sb.append(board[i][j]);
				}
				sb.append('\n');
			}
			System.out.print(sb.toString());
			
		} //end while
	} //end main
}

Measured memory_bytes: 95108
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <sstream>
#include <math.h>
#include <algorithm>
#include <queue>
using namespace std;
//for (int i = 0; i < N; i++){}
//for (int j = 0; j < M; j++){}

int main() {
    int N;
    cin >> N;
    string w[N];
    map<string, int> mp;

    string x;
    string y;
    bool flag = true;
    for (int i = 0; i < N; i++){
        cin >> x;
        mp[{x}]++;
        if(i==0){
            y = x;
            continue;
        }
        if(mp[{x}]>1){
            flag = false;
            break;
        }
        if((x[0]-0) != y[y.size()-1]-0){
            flag = false;
            break;
        }
        y = x;
    }
    if(flag) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

int digit(int n){
  int ans = 0;
  while (n!=0){
    n /= 10;
    ans++;
  }
  return ans;
}

int main() {
    long long int n;
    cin >> n;
    int n_root = sqrt(n);
    int max1 = 11;
    for(int i=1;i<n_root+1;i++){
        if(n%i==0){
            int b = n/i;
            max1 = min(max1,max(digit(b),digit(i)));
        }
    }
    cout << max1 << endl;
    return 0;
}


Measured memory_bytes: 256
N, T=map(int, input().split())
l=[list(map(int, input().split())) for i in range(N)]
c_min=10**3
t_min=10**3

for i in range(N):
    if l[i][1]<=T:
        if l[i][0]<=c_min:
            c_min=l[i][0]
    
    if l[i][1]<=t_min:
        t_min=l[i][1]
    
if t_min > T:
    print("TLE")
else:
    print(c_min)

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

long long a[10000010];
int main() 
{
    long long n;
    cin>>n;
    long long sum=0;
    for(long long i=1;i<=n;i++)
    {
    	a[i]=i;
    	sum+=i;
    	if(sum>n)
    	{
    		break;
		}
	}
	long long t=sum-n;
	for(long long i=1;i<=n;i++)
	{
		if(a[i]==0)
		{
			continue;
		}
		if(a[i]!=t)
		{
			cout<<a[i]<<endl;
		}
	}
    return 0;
}


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

int main() {
    string s, t;
    cin >> s >> t;
    if(s.size() != t.size()){
        cout << "No" << endl;
        return 0;
    }
    bool j = 0;
    rep(i,s.size()){
        s = s.substr(1,s.size()) + s[0];
        if(s == t) j = 1;
    }
    cout << ((j)? "Yes" :"No") << endl;
}

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

int n, W;
int w[1001], v[1001];
int dp[1001][1001];
int num=1;

void reset_variable(){
	W = 0;
	n = 0;
	for (int i = 0; i < 1001; i++){
		w[i] = 0;
		v[i] = 0;
	}
	memset(dp, 0, sizeof(dp));
}


void solve(void){
	cin >> n;
	for (int i = 0; i<n; i++){
		scanf("%d,%d", &v[i], &w[i]);
	}
	cout << "Case " << num << ":" << endl;
	for (int i = 0; i <= W; i++){
		dp[n][i] = 0;
	}
	for (int i = n - 1; i >= 0; i--){
		for (int j = 0; j <= W; j++){
			if (j < w[i]){
				dp[i][j] = dp[i + 1][j];
			}
			else{
				dp[i][j] = max(dp[i + 1][j], v[i] + dp[i + 1][j - w[i]]);
			}
		}
	}
	for (int i = 0; i < 1001; i++){
		if (dp[0][i] == dp[0][W]){
			cout << dp[0][W] << endl << i << endl;
			return;
		}
	}
}

int main(){
	while (1){
		reset_variable();
		cin >> W;
		if (!W) return 0;
		solve();
		num++;
	}
	return 0;
}

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

using namespace std;

typedef long long ll;
int n;
ll a[222222];

int main(void) {
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%lld", a+i);
    a[i] -= i + 1;
    // printf("%lld ", a[i]);
  }
  /*
  puts("");
  for (int i = -10; i <= 10; i++) {
    ll s = 0;
    for (int j = 0; j < n; j++) {
      s += abs(a[j] - i);
    }
    printf("%3d: %lld\n", i, s);
  }
  */
  sort(a, a+n);
  ll s = n%2 == 0 ? (a[n/2]+a[n/2-1])/2 : a[n/2];
  ll res = 0;
  for (int i = 0; i < n; i++) res += abs(s - a[i]);
  printf("%lld\n", res);
  return 0;
}


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


int main() {
    long long int a,b,c,k;
    cin>>a>>b>>c>>k;
    if(k<=a){
        cout<<k<<endl;
    }else{
        if(k<=a+b){
            cout<<a<<endl;
        }else{
            long long int x=k-a-b;
            cout<<a-x<<endl;
        }
    }

}

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

using namespace std;

int n, p;
string s;

int main() {
    cin >> n >> p;
    cin >> s;
    long long answer = 0;
    if (p == 2 || p == 5) {
        for (int i = 0; i < n; i++) {
            int num = s[i] - '0';
            if (num % p == 0)
                answer += i + 1;
        }
    } else {
        vector <int> c(p, 0);
        int pow = 1, x = 0;
        for (int i = n - 1; i >= 0; i--) {
            c[x] ++;
            int num = s[i] - '0';
            x = (num * pow + x) % p;
            answer += c[x];
            pow = (pow * 10) % p;
        }
    }
    cout << answer << endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
struct SCC{
  int n;
  vector<vector<int> > G,rG,T,C;
  vector<int> vs,used,belong;
  SCC(){}
  SCC(int sz):n(sz),G(sz),rG(sz),used(sz),belong(sz){}
   
  void add_edge(int from,int to){
    G[from].push_back(to);
    rG[to].push_back(from);
  }
   
  void input(int m,int offset=0){
    int a,b;
    for(int i=0;i<m;i++){
      cin>>a>>b;
      add_edge(a+offset,b+offset);
    }
  }
   
  void dfs(int v){
    used[v]=1;
    for(int i=0;i<(int)G[v].size();i++){
      if(!used[G[v][i]]) dfs(G[v][i]);
    }
    vs.push_back(v);
  }
   
  void rdfs(int v,int k){
    used[v]=1;
    belong[v]=k;
    C[k].push_back(v);
    for(int i=0;i<(int)rG[v].size();i++){
      if(!used[rG[v][i]]) rdfs(rG[v][i],k);
    }
  }
   
  int build(){
    fill(used.begin(),used.end(),0);
    vs.clear();
    for(int v=0;v<n;v++){
      if(!used[v]) dfs(v);
    }
    fill(used.begin(),used.end(),0);
    int k=0;
    for(int i=vs.size()-1;i>=0;i--){
      if(!used[vs[i]]){
    T.push_back(vector<int>());
    C.push_back(vector<int>());
    rdfs(vs[i],k++);
      }
    }
    for(int i=0;i<n;i++)
      for(int u:G[i])
    if(belong[i]!=belong[u])
      T[belong[i]].push_back(belong[u]);
    for(int i=0;i<k;i++){
      sort(T[i].begin(),T[i].end());
      T[i].erase(unique(T[i].begin(),T[i].end()),T[i].end());
    }
    return k;
  }
};
signed main(){
  int n,m;
  cin>>n>>m;
  int V = n*2;
  vector<vector<int> > G(V);
   
  int l=0,r=n;
  for(int i=0;i<m;i++){
    int x,y;
    string s,t,u;
    cin>>x>>s>>u>>y>>t;
    x--;y--;
    if(s=="right") x+=n;
    if(t=="right") y+=n;
    G[x].emplace_back((y+n)%V);
    G[y].emplace_back((x+n)%V);
  }
   
  auto check=[&](int x)->int{
    SCC scc(V);
    for(int i=0;i<x;i++)
      for(int v=i;v<V;v+=n)
    for(int u:G[v])
      if(u%n<x) scc.add_edge(v,u);
     
    scc.build();
    for(int i=0;i<x;i++)
      if(scc.belong[i]==scc.belong[i+n]) return 0;
    return 1;
  };
   
  while(l+1<r){
    int m=(l+r)>>1;
    if(check(m)) l=m;
    else r=m;
  }
  cout<<r<<endl;
  return 0;
}



Measured memory_bytes: 8068
#include<iostream>
#include <stdlib.h>
#include <algorithm>
#include <string>
#include <vector>
#include <numeric>
#include <map>

typedef long long int ll;
using namespace std;
int main(){
	int num,s,count=0,diff=100000;
	cin >> num;
	vector<int> weight;
	for(int i=0; i<num;i++){
		cin >> s;
		weight.push_back(s);
	}
	for(int i=0; i<num;i++){
		count+=weight[i];
		weight[i]=0;
		if(abs(accumulate(weight.begin(), weight.end(),0)-count)<=diff){
			diff=abs(accumulate(weight.begin(), weight.end(),0)-count);
		}else{
			cout << diff<<endl;
			return 0;
		}
	}
	cout << diff<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
 int N;
  cin >> N;
  string S;
  cin >> S;
  int s;
  s = S.length();
  int c = 1;
  char C;
  C = S[0];
  for(int i = 0; i < s; i++){
	 if(C != S[i]){
       C = S[i];
       c += 1;
     }
  }
  cout << c << endl;
}

Measured memory_bytes: 512
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
   Scanner scanner = new Scanner(System.in);
    int X = scanner.nextInt();
    int Y = scanner.nextInt();
    int Z = scanner.nextInt();
    
    int d = X;
    X = Y;
    Y = d;
    
    d = Z;
    Z = X;
    X = d;
    
    System.out.println(X + " " + Y + " " + Z + " ");
  }
}

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

typedef long long ll;

int main() {
  int n;
  cin >> n;
  int a[n];
  for (int i = 0; i < n; i++) cin >> a[i];

  // 貪欲法で操作回数の最小値を求める
  // プラスから始まるパターンとマイナスから始まるパターンの2パターン試す
  ll ans1 = 0;
  bool flag = true;
  ll sum = a[0];
  if (sum <= 0) {
    ans1 += -sum + 1;
    sum = 1;
  }
  for (int i = 1; i < n; i++) {
    if (flag) {
      flag = false;
      sum += a[i];
      if (sum < 0) continue;
      ans1 += sum + 1;
      sum = -1;
    } else {
      flag = true;
      sum += a[i];
      if (sum > 0) continue;
      ans1 += -sum + 1;
      sum = 1;
    }
  }
  // マイナスから始まるパターン
  ll ans2 = 0;
  flag = false;
  sum = a[0];
  if (sum >= 0) {
    ans2 += sum + 1;
    sum = -1;
  }
  for (int i = 1; i < n; i++) {
    if (flag) {
      flag = false;
      sum += a[i];
      if (sum < 0) continue;
      ans2 += sum + 1;
      sum = -1;
    } else {
      flag = true;
      sum += a[i];
      if (sum > 0) continue;
      ans2 += -sum + 1;
      sum = 1;
    }
  }

  // 解答
  cout << min(ans1, ans2) << endl;
  return 0;
}


Measured memory_bytes: 640