akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;

int main() {
        int n;
        scanf("%d", &n);
        vector<int> a(n);
        for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
        sort(a.rbegin(), a.rend());
        int h = 0, w = 0;
        while (true) {
                if (a[w] <= h) break;
                h ++, w ++;
        }
        h --, w --;
        //cerr << "(h, w) = " << "(" << h << ", " << w << ")" << endl;
        int res1 = a[w] - h - 1;
        int k = w;
        while (h < a[k]) k ++;
        int res2 = k - w - 1;
        //cerr << res1 << ' ' << res2 << endl;
        puts((res1 & 1 || res2 & 1) ? "First" : "Second");
        return 0;
}


Measured memory_bytes: 640
n_five_hundred_coin = int(input())
n_hundred_coin = int(input())
n_fifty_coin = int(input())
total_money = int(input())

n_pattern = 0
for five_hundred_coin in range(n_five_hundred_coin+1):
  # この時点で合計を超えていればアウト
  if five_hundred_coin * 500 > total_money:
    break

  for hundred_coin in range(n_hundred_coin+1):
    # この時点で合計を超えていればアウト
    if five_hundred_coin * 500 + hundred_coin * 100 > total_money:
      break

    remain_money = total_money - five_hundred_coin * 500 - hundred_coin * 100
    need_fifty_coin = remain_money / 50

    if need_fifty_coin <= n_fifty_coin:
      n_pattern += 1

print(n_pattern)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n, k; cin >> n >> k;
	string s; cin >> s;
	for(int i=0;i<26;i++){
		if(i==(s[k-1]-'A')){
			s[k-1] = 'a'+i;
		}
	}
	cout << s << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<vector>
#define ll long long
#define ld long double
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
int main(void){
    // Your code here!

  ll a,b;
  ll c,d;
  cin>>a>>b>>c>>d;
  
  ll z= (c)/__gcd(c,d)*d;
  
  ll x1= (a-1)/c;
  ll y1= b/c;
  ll x2= (a-1)/d;
  ll y2= b/d;
  ll x3 =(a-1)/z;
  ll y3= b/z;
  
//  cout<<x1<<y1<<" "<<x2<<y2<<" "<<x3<<y3;
  
  cout<<(b-a+1)-((y1-x1)+ (y2-x2)-(y3-x3));
  
  
}


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

int main(){
    int a , b , c , x ;
    cin >> a >> b >> c >> x ;
    int count = 0 ;
    rep(i,a+1){
        rep(j,b+1){
            rep(k,c+1){
                if(500*i + 100*j + 50*k == x )count++ ;
            }
        }
    }
    cout <<count << endl;
}

Measured memory_bytes: 3584
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>

using namespace std;

long long MOD = 1000000007;

int main(){
    int N;
    cin >> N;
    for(int i=9; i>0; i--){
        if(N%i==0 && N/i<10){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    long long i;
    long long n,k;
    long long m,cnt=0,t;
    while(~scanf("%lld%lld%lld",&n,&m,&k))
    {
        if(n>m)
        {t=m;
        m=n;
        n=t;
        }
        if(m-n+1<=2*k)
            for(i=n;i<=m;i++)
            printf("%lld\n",i);
            else {
                for(i=n;i<=n+k-1;i++)
                    printf("%lld\n",i);
                for(i=m-k+1;i<=m;i++)
                    printf("%lld\n",i);
            }
           cnt=0;


    }
    return 0;
}

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

int main()
{
  int n, ans, tmp = 1000000001, num;
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> num;
    if(i == 1)
      ans = num - tmp;
    if(num >= tmp)
      ans = (num - tmp > ans) ? num - tmp : ans;
    else
      tmp = num;
  }
  cout << ans << endl;
}

Measured memory_bytes: 1164
import java.util.*;
public class Main {

   public static void main(String[] args) {
        
      int a,b,c,sum;
  	Scanner scan=new Scanner(System.in); 
    String s=scan.nextLine(); 
    String[] str=s.split(" ");
    a = Integer.parseInt(str[0]);
    b = Integer.parseInt(str[1]);
    c = Integer.parseInt(str[2]);
     sum = a + b + c;
     if(sum>=22)
     {
       System.out.println("bust");
     }
     else 
     {
       System.out.println("win");
     }
   }
}

Measured memory_bytes: 22484
#[macro_use]
pub mod basic_stdin {
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    use std::io::stdin;
    use std::io::Read;

    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed reading char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed parsing")
}

}

#[macro_export]
macro_rules! test_function {
    (func = $func:expr, $($input:expr => $output:expr),* $(,)*) => {
        $(
            assert_eq!($func(std::io::Cursor::new($input)) , $output);
        )*
    };
}

#[macro_export]
macro_rules! input_macro {
    (string = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    (reader = $s:expr, $($r:tt)*) => {
        let reader = std::io::BufReader::new($s);
        let mut bytes = std::io::Read::bytes(reader);
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[macro_export]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
    ($iter:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[macro_export]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    let stdin = std::io::stdin();
    let ret = solve(stdin.lock());

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

fn solve<T: std::io::Read>(reader: T) -> i64 {
    input_macro! {
        reader = reader,
        a: i64,
        b: i64,
    }

    let x = a + b;
    let y = a - b;
    let z = a * b;

    let vec = vec![x, y, z];
    vec.into_iter().max().unwrap()
}

#[cfg(test)]
mod tests {

    #[test]
    fn test_solve_function() {
        atcorder::test_function! {
            func = super::solve,
            "3 1" => 4,
        }
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    long h,w,ans;
    cin >> h >> w;
   if (h==1 || w==1) ans= 1;
   else if(h%2==0 && w%2==0) ans=h*w/2;
   else if(h%2 == 1 && w%2 == 1) ans= (h-1)*w/2+w/2+1;
   else   ans= h*w/2 ;
  cout<<ans ;
}


Measured memory_bytes: 384
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;

using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;

template <class T> inline T chmax(T &a, const T b) {return a = (a < b) ? b : a;}
template <class T> inline T chmin(T &a, const T b) {return a = (a > b) ? b : a;}

constexpr int MOD = 1e9 + 7;
constexpr int inf = 1e9;
constexpr long long INF = 1e18;

#define all(a) (a).begin(), (a).end()

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

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

    int n, W; cin>>n>>W;
    vector<int> w(n), v(n);
    for(int i=0; i<n; i++) cin>>w[i]>>v[i];

    vector<vector<ll>> dp(n+1, vector<ll>(W+1, 0));
    for(int i=0; i<n; i++){
        for(int j=0; j<=W; j++){
            chmax(dp[i+1][j], dp[i][j]);
            if(j - w[i] >= 0) chmax(dp[i+1][j], dp[i][j-w[i]] + v[i]);
        }
    }

    cout << dp[n][W] << endl;

    return 0;
}

Measured memory_bytes: 80256
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            //[summary]B - Comparison
            var a = Console.ReadLine();
            var b = Console.ReadLine();

            Console.WriteLine(Compare(a, b));
        }

        static string Compare(string a, string b)
        {
            int digit = GetDigit(a, b);

            a = a.PadLeft(digit, '0');
            b = b.PadLeft(digit, '0');

            switch (a.CompareTo(b))
            {
                case 1:
                    return "GREATER";
                case 0:
                    return "EQUAL";
                default:
                    return "LESS";
            }
        }

        static int GetDigit(string a, string b)
        {
            int len1 = a.Length;
            int len2 = b.Length;

            if (len1 > len2)
            {
                return len1;
            }
            else
            {
                return len2;
            }
        }
    }
}

Measured memory_bytes: 13396
#include <cstdio>
#include <iostream>
#include <string>

using namespace std;

inline void reverse(char* buf, int a, int b) {
  const int mid = (a + b) / 2;
  int j = b;
  int t;
  for (int i = a; i <= mid; ++i) {
    if (i == j) {
      break;
    }
    t = buf[i];
    buf[i] = buf[j];
    buf[j] = t;
    --j;
  }
}

int main() {
  char str[1001] = {'\0'};
  cin >> str;

  int q;
  cin >> q;

  int a, b;
  string o, p;
  for (int i = 0; i < q; ++i) {
    cin >> o >> a >> b;
    if (o == "print") {
      for (int j = a; j <= b; ++j) {
        printf("%c", str[j]);
      }
      printf("\n");
    } else if (o == "reverse") {
      reverse(str, a, b);
    } else if (o == "replace") {
      cin >> p;
      int k = 0;
      for (int j = a; j <= b; ++j) {
        str[j] = p[k];
        ++k;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 1192
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
int main() {
  int n;
  cin>>n;
  cout<<3*n*n<<endl;
}

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

int main(void) {
  int A, B;
  cin >> A >> B;
  if (A >= 13) cout << B << endl;
  else if (A >= 6) cout << B / 2 << endl;
  else cout << 0 << endl;

  return 0;
}

Measured memory_bytes: 256
package main

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

func main() {
	sc := newScanner(os.Stdin)
	a, b, _, k := sc.i(), sc.i(), sc.i(), sc.i()
	if a > k {
		fmt.Println(k)
	} else {
		t := k - a
		if b > t {
			fmt.Println(a)
		} else {
			r := a - (t - b)
			fmt.Println(r)
		}
	}
}

// I/O
type scanner struct {
	sc *bufio.Scanner
}

func newScanner(input io.Reader) *scanner {
	sc := bufio.NewScanner(input)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &scanner{sc}
}

func (s *scanner) s() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *scanner) i() int {
	i, e := strconv.Atoi(s.s())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *scanner) f() float64 {
	f, e := strconv.ParseFloat(s.s(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *scanner) bs() []byte {
	return []byte(s.s())
}

func (s *scanner) is(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.i()
	}
	return res
}

func (s *scanner) fs(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.f()
	}
	return res
}


Measured memory_bytes: 1756
import java.util.*;
import java.math.BigDecimal;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int x = sc.nextInt();
        int y = sc.nextInt();
        int turu = 0, kame = x;
      
        while(kame >= 0){
          if(turu * 2 + kame * 4 == y){
            System.out.println("Yes");
            System.exit(0);
          }
          kame--;
          turu++;
        }

        System.out.println("No");
    }
}

Measured memory_bytes: 35712
#include<stdio.h>
int main(void)
{
  char s[4];
  char t[4];
 
  scanf("%s",&s);
  scanf("%s",&t);
  int i;
  int c=0;
  
  for(i=0;i<3;i++)
  {
    if(s[i]==t[i])
    {
      c++;
    }
  }
  
  printf("%d",c);
  
  return 0;
}
  

Measured memory_bytes: 128
import itertools

def hash_map(l, n):
  l_pairs = []
  for i in range(2, n+1):
    l_pairs += list(itertools.combinations(l, i))

  mapping = l
  for pair in l_pairs:
    mapping.append(sum(pair))

  return mapping

n = int(input())
list_a = list(map(int, input().split()))
q = int(input())
list_m = list(map(int, input().split()))

mapping = hash_map(list_a, n)

for m in list_m:
  if m in mapping: 
    print('yes')
  else:
    print('no')


Measured memory_bytes: 189056
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int	C = sc.nextInt();

		if(A < C && B > C || A > C && B < C) {
			System.out.println("Yes");

		}else {
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 23892
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long ll;
int main() {
  int n,a,sub=0;
  map<int,int> mp;
  cin>>n;
  rep(i,n){
      cin>>a;
      mp[a]++;
  }
  for(auto itr=mp.begin();itr!=mp.end();itr++)
    sub+=itr->second-1;
  if(sub%2)
    sub++;
  printf("%d",n-sub);
  return 0;
}

Measured memory_bytes: 4992
import std.stdio;
import std.range;
import std.array;
import std.string;
import std.conv;
import std.typecons;
import std.algorithm;
import std.container;
import std.typecons;
import std.random;
import std.csv;
import std.regex;
import std.math;
import core.time;
import std.ascii;
import std.digest.sha;
import std.outbuffer;

void main() {
	auto args = readln.chomp.split.map!(to!int);
	int a = args[0];
	int b = args[1];
	int c = args[2];
	int x = args[3];
	int y = args[4];
	int z = x + y;
	int ans = int.max;
	for (int i = 0; i <= z * 2; ++i) {
		int m = i / 2;
		int rx = x - m;
		int ry = y - m;
		int v = i * c + rx.max(0) * a + ry.max(0) * b;
		ans = min(ans, v);
	}
	ans.writeln;
}



Measured memory_bytes: 256
//****author RKN
//DATE 5/2/2020 5.15 AM
 
 
// ***************DREAM IS NOT THAT YOU SEE WHILE SLEEPING BUT IT IS WHAT DONT LET YOU SLEEP************//
 
 
///////////////////////    machayenge......sala hoga apne se bhi ek din    ///////////////////////////////////////////////////////////

#include<bits/stdc++.h>
using namespace std;
 
/////////////////////////////   %   variable  %   //////////////////////////////////////////////////////////////
 
#define ll long long
#define pb push_back 
#define f1 first
#define s2 second
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pr pair<ll,ll>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
int dir1[8]={1,0,0,-1,-1,1,-1,1};
int dir2[8]={0,-1,1,0,-1,1,1,-1};
#define en "\n"

ll MAX=1e9+7;

////////////////////////////////////////////////////////////////////////////////////////////

ll ans[101][100001];

int main()
{
    int n,wt,a,b;
    cin>>n>>wt;
    vector<pair<int,int>>v;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b;
        v.pb({a,b});
    }
    sort(all(v));
    for(int i=0;i<=v.size();i++)
    {
        for(int j=0;j<=wt;j++)
        {
            if(i==0 || j==0)
            ans[i][j]=0;
            else if(v[i-1].f1<=j)
            ans[i][j]=max(ans[i-1][j],v[i-1].s2+ans[i-1][j-v[i-1].f1]);
            else
            ans[i][j]=ans[i-1][j];
        }
    }
    cout<<ans[n][wt];
    return 0;
}


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

#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set
#define l_l pair<ll, ll>
#define vll vector<ll>
#define mll map<ll, ll>

using namespace std;

const ll MOD = 1000000007LL;
const ll INF = (1LL << 60LL);

int main() {
  // std::cout << std::fixed << std::setprecision(10);
  ll N;
  scanf("%lld", &N);

  ll ans = 0;

  vector<ll> list;
  for (ll i = 0; i < N; i++) {
    ll v;
    scanf("%lld", &v);
    list.emplace_back(v);
  }

  ans += list[0];
  ans += list[list.size() - 1];

  for (ll i = 0; i < N - 2; i++) {
    ans += min(list[i], list[i + 1]);
  }

  cout << ans << endl;
}


Measured memory_bytes: 3692
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define ALL(v) (v).begin(), (v).end()
#define LENGTHOF(x) (sizeof(x) / sizeof(*(x)))
#define AFILL(a, b) fill((int*)a, (int*)(a + LENGTHOF(a)), b)
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define INF 1 << 30
#define EPS 1e-10

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

int main(){
  rep(i, 4){
    int t, n, res;
    scanf("%d%d", &t, &n);
    if(t == 1) res = n*6000;
    else if(t == 2) res = n*4000;
    else if(t == 3) res = n*3000;
    else if(t == 4) res = n*2000;
    printf("%d\n", res);
  }
  return 0;
}

Measured memory_bytes: 1188
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a, b;
	cin >> a >> b;
	
	int ans = 0;
	
	
	int calc = 1;
	while(calc < b){
		ans++;
		calc += (a - 1);
	}
	
	cout << ans << endl;
}


Measured memory_bytes: 256
N,M = map(int,input().split(" "))
a = [0] * N
b = [0] * N
for i in range(M):
    aaa,bbb = map(int,input().split(" "))
    if aaa == 1:
        b[bbb-1] = 1
    if bbb == N:
        a[aaa-1] = 1

for i in range(N):
    if a[i] * b[i]:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")

Measured memory_bytes: 6132
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for (int i = a; i <b; i++)
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vl;
typedef pair<int,int> pi;
#define trace(x) cout<<#x<<"="<<x<<"\n";
#define llp 1000000007
#define mod 1000000007

template < typename F, typename S >
ostream& operator << ( ostream& os, const pair< F, S > & p ) {
    return os << "(" << p.first << ", " << p.second << ")";
}

template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
    os << "{";
    typename vector< T > :: const_iterator it;
    for( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "}";
}

template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
    os << "[";
    typename set< T > :: const_iterator it;
    for ( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "]";
}

template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v ) {
    os << "[";
    typename map< F , S >::const_iterator it;
    for( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << it -> first << " = " << it -> second ;
    }
    return os << "]";
}

#define deb(x) cerr << #x << " = " << x << endl;


int main(){
	ios::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<double> a(n);
    vector<string>s(n);
    double ans=0;
    REP(i,0,n){
        cin>>a[i]>>s[i];
        double add=a[i];
        if(s[i][0]=='B'){
            add=380000.0*add;
        }
        ans+=add;
    }
    printf("%.9f\n",ans);



	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int dp[8][1001] = {0};
int a[7],b[7],m;

void comb() {
  for(int i=0;i<8;i++) {
    for(int j=0;j<1001;j++) {
      dp[i][j] = 0;
    }
  }

  dp[0][0] = 1;

  for(int i=0;i<m;i++) {
    for(int j=0;j<1001;j++) {
      for(int k=0;j-k*a[i]>=0 && k <= b[i];k++) {
        dp[i+1][j] += dp[i][j-k*a[i]];
      }
      //        cout << "dp[" << i+1 << "][" << j << "] = " << dp[i+1][j] << endl;
    }
  }
}

int main() {
  int g,n;
  while(cin >> m) {
    if(m==0) break;
    for(int i=0;i<m;i++) {
      cin >> a[i] >> b[i];
    }
    comb();
    cin >> g;
    for(int i=0;i<g;i++) {
      cin >> n;
      cout << dp[m][n] << endl;
    }
  }
}

Measured memory_bytes: 0
#include <stdio.h>
#define N 100
#define WHITE 1
#define GRAY 2
#define BLACK 3

int d[N],f[N],time,S[N],G[N][N],n;


void DFSvisit(int);
void DFS(void);




int main(){
  int i,j,u,v,k;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      G[i][j]=0;
    }
  }
  
  for(i=0;i<n;i++){
    scanf("%d %d",&u,&k);
    for(j=0;j<k;j++){
      scanf("%d",&v);
      G[u-1][v-1]=1;
    }
  }

  DFS();

  for(i=0;i<n;i++){
    printf("%d %d %d\n",i+1,d[i],f[i]);
  }

  return 0;
}







void DFSvisit(int u){
  int i;

  S[u]=GRAY;
  d[u]=++time;

  for(i=0;i<n;i++){
    if(G[u][i]==1 && S[i]==WHITE){
      DFSvisit(i);
    }
  }

  S[u]=BLACK;
  f[u]=++time;
}





void DFS(void){
  int i;
  
  for(i=0;i<n;i++){
    S[i]=WHITE;
  }
  time=0;
  for(i=0;i<n;i++){
    if(S[i]==WHITE){
      DFSvisit(i);
    }
  }
}

Measured memory_bytes: 636
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline int read()
{
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-'0';c=getchar();}
	return x*f;
}
const int maxn = 1e5 + 10;
int n, s, a[maxn], pos; ll ans, p[maxn];
int dfs(int l, int r)
{
	if (r <= pos)
	{
		ans = abs(s - a[l]);
		return a[l];
	}
	else if (l > pos)
	{
		ans = abs(a[r] - s);
		return a[r];
	}
	int np;
	if (p[l] >= p[r])
	{
		p[l] += p[r], np = dfs(l, r - 1), ans += abs(a[r] - np);
		return a[r];
	}
	else
	{
		p[r] += p[l], np = dfs(l + 1, r), ans += abs(np - a[l]);
		return a[l];
	}
}
int main()
{
	n = read(), s = read();
	for (int i = 1; i <= n; i ++)
		a[i] = read(), p[i] = read();
	pos = upper_bound(a + 1, a + 1 + n, s) - a - 1;
	dfs(1, n);
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 3968
//============================================================================
// Name        : hoba.cpp :)
// Author      : (O_O Diab) (Why_not) (el 3AQ)
// Version     :
// Copyright   : please, Don't touch me :(
// Description : problem (I) in C++
// MAIN IDEA   : max sum of S(X) + S(S(X)) => 100 so brute force
//============================================================================
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define rw freopen("input.txt","r",stdin),freopen("output.txt","w",stdout);
#define pb push_back
#define F first
#define S second
#define pf push_front
#define lp(i,a,b) for (int i=a;i<=(int)b;++i)
#define lp2(i,a,b) for (int i=a;i>=b;--i)
#define f(x) return cout<<x<<"\n",0
#define pii pair<int,int>
#define pll pair<ll,ll>
#define all(c) c.begin(),c.end()
#define allr(c) c.rbegin(),c.rend()
#define p(x) cout<<#x<<" = { "<<x<<" } \n"
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define EPS 1e-6
// to convert string to number use int a = stoi(string);
// to convert number to string use string s = to_string(int);
#define FAST ios::sync_with_stdio(0),ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define clr(c,x) memset(c,x,sizeof(c));
using namespace __gnu_pbds;
using namespace std;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const int dx[] = { 0, 1, 0, -1, 1, -1, 1, -1 };
const int dy[] = { 1, 0, -1, 0, 1, -1, -1, 1 };
const int N = 1e5 + 5, mod = (int) 1e9 + 7, INF = 0x3f3f3f3f;
vii vx, vy;
vector<pair<int, pii>> e;
struct dsu {
	int forests = 0, parent[N], groupsize[N];
	void add(int x) {
		parent[x] = x;
		groupsize[x] = 1;
		forests++;
	}
	int findset(int node) {
		if (parent[node] == node)
			return node;
		return parent[node] = findset(parent[node]);
	}
	bool issameset(int x, int y) {
		return findset(x) == findset(y);
	}
	void link(int i, int j) {
		int x = findset(i), y = findset(j);
		if (x == y)
			return;
		if (groupsize[x] < groupsize[y])
			swap(x, y);
		groupsize[x] += groupsize[y];
		parent[y] = x;
		forests--;
	}
};
int main() {
#ifdef ONLINE_JUDGE
	FAST
#endif
	int n;
	cin >> n;
	lp(i,1,n)
	{
		int x, y;
		cin >> x >> y;
		vx.pb( { x, i });
		vy.pb( { y, i });
	}
	sort(all(vx));
	sort(all(vy));
	lp(i,1,n-1)
	{
		e.pb( { abs(vx[i].F - vx[i - 1].F), { vx[i].S, vx[i - 1].S } });
		e.pb( { abs(vy[i].F - vy[i - 1].F), { vy[i].S, vy[i - 1].S } });
	}
	sort(all(e));
	dsu d;
	lp(i,1,n)
		d.add(i);
	ll cost = 0;
	for (auto u : e) {
		if (d.issameset(u.S.F, u.S.S))
			continue;
		d.link(u.S.F, u.S.S);
		cost += u.F;
	}
	f(cost);
	return 0;
}

Measured memory_bytes: 7144
#include <bits/stdc++.h>
#define int long long
#define rng(i, l, r) for (size_t i = (l); i < (r); ++i)
#define rep(i, n) rng(i, 0, n)
#define gnr(i, l, r) for (size_t i = (r)-1; i >= (l); i--)
#define per(i, b) gnr(i, 0, b)
#define ALL(obj) (obj).begin(), (obj).end()    //1,2,3,...
#define rALL(obj) (obj).rbegin(), (obj).rend() //...,3,2,1
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
using namespace std;
const int INF = 1e18;

void solve()
{

    // remove the bottom 3 lines when you submit this code.
    std::ifstream in("sample.txt");
    std::cin.rdbuf(in.rdbuf());

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

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

    int ans = INF;
    for (int ab = 0; ab <= 200010; ab++)
    {
        int tmp = 0;
        tmp += ab * c;
        int da = max((int)0, x - ab / 2);
        int db = max((int)0, y - ab / 2);
        tmp += da * a + db * b;
        ans = min(ans, tmp);
    }
    cout << ans << endl;
}

signed main()
{
    solve();
    return 0;
}


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

using int64=long long;
using uchar=unsigned char;

constexpr int maxn(1000);
constexpr int p(1000000007);

namespace IOManager{
	constexpr int FILESZ(131072);
	char buf[FILESZ];
	const char*ibuf=buf,*tbuf=buf;

	struct IOManager{
		inline char gc()
			{return(ibuf==tbuf)&&(tbuf=(ibuf=buf)+fread(buf,1,FILESZ,stdin),ibuf==tbuf)?EOF:*ibuf++;}

		template<class _Tp>
			inline operator _Tp(){
				_Tp s=0u;char c=gc();
				for(;c<48;c=gc());
				for(;c>47;c=gc())
					s=(_Tp)(s*10u+c-48u);
				return s;
			}
	};
}IOManager::IOManager io;

int r[maxn*maxn+1],
	c[maxn*maxn+1];

int main(){
	const int n=io,m=io,tot=n*m;
	for(int i=1;i<=n;++i)
		r[(int)io]=i;
	for(int i=1;i<=m;++i)
		c[(int)io]=i;

	int ans=1,lr=0,lc=0,cnt=0;
	for(int i=tot;i;--i){
		if(r[i]&&c[i])
			cnt+=lr+lc,
			++lr,++lc;
		else if(r[i])
			ans=(int64)ans*lc%p,
			++lr,cnt+=lc-1;
		else if(c[i])
			ans=(int64)ans*lr%p,
			++lc,cnt+=lr-1;
		else ans=(int64)ans*cnt%p,--cnt;
	}printf("%d",ans);

	return 0;
}


Measured memory_bytes: 2304
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>

typedef long long ll;
typedef unsigned long long ull;
using namespace std;

#define FALSE printf("false\n");
#define TRUE printf("true\n");
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i = 0;(i) < ((int)(n));++(i))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define test(a) cout<<"line:"<<__LINE__<<"["<<(#a)<<": "<<(a)<<"]"<<endl

const int INF = 1e9+7;
const ll INFL = 9*1e18;

// const int dx[4] = { 1, 0, -1, 0 };
// const int dy[4] = { 0, 1, 0, -1 };

const int dx[8] = {1, 1, 0,-1,-1,-1, 0, 1};
const int dy[8] = {0, 1, 1, 1, 0,-1,-1,-1};

#define SUM(vec) accumulate(all(vec),0LL) // 配列の中身を全部足す
template<typename T>void print(T&& x){cout<<x<<endl;}// 改行付き出力
ll inline digit(ll num){int tmp = 0;while(num){tmp++;num/=10;}return tmp;} // 桁数
template<typename T>inline T digitSum(T num){T sum = 0;while(num){sum+=num%10;num/=10;}return sum;} // 各桁の和
template<typename T>inline T gcd(T a,T b){if(b == 0)return a;return gcd(b,a%b);} // 最大公約数
template<typename T>inline T lcm(T a, T b){T g = gcd(a,b);return a/g*b;} // 最小公倍数
template<typename T>inline T power(T a,T b){T tmp=1;rep(i,b){tmp*=a;}return tmp;} // 累乗
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; }
int ctoi(char c){return c-'0';}

// TODO: write
int main() {
  int a,b,c,d;cin>>a>>b>>c>>d;
  int cnt = 0;
  while(a > 0 && c > 0){
    if(cnt%2 == 0)c -= b;
    else a -= d;
    cnt++;
  }
  if(cnt%2)print("Yes");
  else print("No");
  return 0; 
}


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

 using namespace std;

 int main() {
   string S;
   cin >> S;

   string ans = "Yes";

   for (int i = 0; i < S.length(); i += 2) {
     if (S.at(i) == 'L') {
       ans = "No";
       break;
     }
   }

   if (ans == "Yes") {
     for (int i = 1; i < S.length(); i += 2) {
       if (S.at(i) == 'R') {
         ans = "No";
         break;
       }
     }
   }

   cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define f q.front()
#define SIZE (ll)(1e3)
#define mod (ll)(1e9+7)
using namespace std;
typedef long long int ll;

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

	int a[n+1],i,j;
	for(int i=1;i<=n;i++)cin>>a[i];
     int dp[n+1];
 for(i=1;i<=n;i++)dp[i]=mod;
 	dp[1]=0;dp[2]=abs(a[2]-a[1]);
 for(i=3;i<=n;i++){
   for(j=1;j<3;j++){
   	
   
   	dp[i]=min(dp[i-j]+abs(a[i]-a[i-j]),dp[i]);
 }}
 cout<<dp[n];
return 0;}

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    vector<pair<bool, vector<ll>>> roads(4);
    rep(i, 3) {
        ll a, b;
        cin >> a >> b;
        a--, b--;
        roads[a].second.push_back(b);
        roads[b].second.push_back(a);
    }
    stack<ll> st;
    st.push(0);
    while(!st.empty()) {
        ll current = st.top();
        st.pop();
        roads[current].first = true;
        iter(i, roads[current].second) {
            if(!roads[i].first) {
                st.push(i);
                break;
            }
        }
    }
    iter(i, roads) {
        if(!i.first) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}


Measured memory_bytes: 3564
#include <bits/stdc++.h>
using namespace std;
/* typedef */
typedef long long ll;
typedef pair<int, int> pii;
/* constant */
const int INF = 1 << 30;
const ll LINF = 1LL << 50;
const int NIL = -1;
const int MAX = 100000;
const int mod = 1000000007;
const double pi = 3.141592653589;
/* global variables */
/* function */
/* main */
int main(){
    int N, K;
    cin >> N >> K;
    vector<bool> D(10);
    for (int i = 0; i < K; i++) {
        int d; cin >> d;
        D[d] = true;
    }
    for (int ans = N; ans <= MAX; ans++) {
        int tmp = ans;
        bool can = true;
        while (tmp > 0) {
            if (D[tmp%10]) {
                can = false;
                break;
            }
            tmp /= 10;
        }
        if (can) {
            cout << ans << '\n';
            return 0;
        }
    }
}


Measured memory_bytes: 3640
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M, X, Y = nl()
Xs = nl()
Ys = nl()
Xs.append(X)
Ys.append(Y)

maxX = max(Xs)
minY = min(Ys)
if maxX < minY:
    print('No War')
else:
    print('War')



Measured memory_bytes: 3060
S_list = list(input())

S_i = S_list[0]
S_i1 = ''
ans = 1

for i in range(1,len(S_list)):
    S_i1 += S_list[i]
    if S_i == S_i1:
        continue
    else:
        S_i = S_i1
        S_i1 = ''
        
        ans += 1
        
print(ans)

Measured memory_bytes: 4840
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
//	入力の読み込み
		Scanner sc = new Scanner(System.in);
		int member = sc.nextInt();  //すぬけの人数
		int sweet = sc.nextInt();  //お菓子の種類数
		int result = 0;  //いたずらされる人数
		int[] brother = new int[member];  //誰が何個持っているかを入れる箱

//	お菓子1種類ずつ、誰にあげるのか、を考えていく
		for(int i=0 ; i<sweet ; i++) {  //お菓子ごとのループ
			int num = sc.nextInt();  //お菓子の種類数
			for(int j=0 ; j<num ; j++) {  //誰にあげるのかのループ
				int sunuke = sc.nextInt();  //お菓子がもらえるすぬけくんの番号
				brother[sunuke-1] += 1;  //あげるすぬけくんの箱に1を足す
			}
		}
//	箱の中身が0のすぬけくんを見つけて、人数をカウントする
		for(int i=0 ; i<member ; i++) {  //最初から最後まで開けて見てみる
			if(brother[i]==0) {
				result++;
			}
		}
//	箱の中身が0だった人数を表示する
		System.out.print(result);
	}
}

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

using namespace std;
typedef long long ll;

#define REP(i, n) for (ll i = 0; i < (n); i++)
#define REPR(i, n) for (ll i = (n); i >= 0; i--)
#define FOR(i, m, n) for (ll i = (m); i < (n); i++)
#define FORR(i, m, n) for (ll i = (m); i >= (n); i--)
#define INF 1e9
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((ll)(x).size())
#define SORT(x) sort((x).begin(), (x).end())
#define dump(x) cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl

int main(int argc, char const *argv[])
{
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    if ((abs(a - c) <= d) || (abs(a - b) <= d && abs(b - c) <= d))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

w, h, x, y, r = map(int, sys.stdin.readline().split())

if x < r or (x+r) > w:
    print('No')
elif y < r or (y+r) > h:
    print('No')
else:
    print('Yes')


Measured memory_bytes: 5604
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define pb push_back
#define fr(i,n) for(int i=0;i<n;i++)
#define Fr(i,n) for(int i=0;i++<n;)
#define ifr(i,n) for(int i=n-1;i>=0;i--)
#define iFr(i,n) for(int i=n;i>0;i--)

int main(){
  int n,v[100010],cnt[2][100010]={},c=0,d=0,e=0,f=0,g,h;
  cin>>n;
  fr(i,n){cin>>v[i];cnt[i%2][v[i]]++;}
  Fr(i,100000){
    if(g<=cnt[0][i]){c=i;g=cnt[0][i];}
    if(h<=cnt[1][i]){e=i;h=cnt[1][i];}
  }
  fr(i,2){sort(cnt[i],cnt[i]+100010);reverse(cnt[i],cnt[i]+100010);}
  cout<<(c==e?n-max(g+cnt[1][1],cnt[0][1]+h):n-g-h)<<endl;
}

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

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

using namespace std;

struct Data {
  int start,end,onAir,recorded;
  bool operator < ( const Data &data ) const {
    if( end != data.end ) return end < data.end;
    if( start != data.start ) return start < data.start;
    return ( onAir != data.onAir ) ? onAir < data.onAir : recorded < data.recorded;
  }
};

const int MAX_N = 1100;
const int IINF = INT_MAX;
int N,s[MAX_N],t[MAX_N],score[MAX_N][2],dp[2000][2000];
vector<int> buf;

int toTime(string s){
  rep(i,(int)s.size()) if( s[i] == ':' ) s[i] = ' ';
  stringstream ss;
  ss << s;
  int h,m;
  ss >> h >> m;
  return h * 60 + m;
}

int main(){
  while( cin >> N, N ){
    vector<Data> vec;
    rep(i,N) {
      string a,b,c;
      cin >> a >> b >> c >> score[i][0] >> score[i][1];
      assert( b != c );
      s[i] = toTime(b), t[i] = toTime(c);
      vec.push_back((Data){s[i],t[i],score[i][0],score[i][1]});
    }
    vec.push_back((Data){0,0,0,0});
    vec.push_back((Data){IINF,IINF,0,0});
    rep(i,N+2) rep(j,N+2) dp[i][j] = 0; 
    sort(vec.begin(),vec.end());
    buf.clear();
    int maxi = 0;
    rep(i,vec.size()) buf.push_back(vec[i].end);
    rep(i,vec.size()){
      rep(j,vec.size()){
        if( i == j ) {
          dp[i][j] = max((i?dp[i-1][j]:0),(j?dp[i][j-1]:0));
        } else if( i < j ) {
          dp[i][j] = dp[i][j-1];
          int prev = upper_bound(buf.begin(),buf.begin()+j,vec[j].start) - buf.begin();
          if( buf[prev] > vec[j].start ) --prev;
          dp[i][j] = max(dp[i][j],((prev!=-1)?dp[i][prev]:0)+vec[j].recorded);
        } else {
          dp[i][j] = dp[i-1][j];
          int prev = upper_bound(buf.begin(),buf.begin()+i,vec[i].start) - buf.begin();
          if( buf[prev] > vec[i].start ) --prev;
          dp[i][j] = max(dp[i][j],((prev!=-1)?dp[prev][j]:0)+vec[i].onAir);
        }
        maxi = max(maxi,dp[i][j]);
      }
    }
    cout << maxi << endl;
  }
  return 0;
}

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

int main() {
    int Q;
    cin >> Q;
    int MAX = 100010;
    vector<pair<int, int>> lr(Q);
    vector<int> is_prime(MAX, 1);
    is_prime[0] = 0; is_prime[1] = 0;
    for(int i = 2; i < MAX; i++) {
        if(!is_prime[i]) {
            continue;
        }
        for(int j = i*2; j < MAX; j += i) {
            is_prime[j] = 0;
        }
    }
    vector<int> a(MAX, 0);
    for(int i = 0; i < MAX; i++) {
        if(i % 2 == 0) {
            continue;
        }
        if(is_prime[i] && is_prime[(i+1)/2]) {
            a[i] = 1;
        }
    }
    vector<int> s(MAX+1, 0);
    for(int i = 0; i < MAX; i++) {
        s[i+1] = s[i] + a[i];
    }
    for(int q = 0; q < Q; q++) {
        int l, r;
        cin >> l >> r;
        r++;
        cout << s[r] - s[l] << endl;
    }
    return 0;
}

Measured memory_bytes: 2560
import java.util.Scanner;
public class Main {
    public static void main(String[] defargs) {
        Scanner scanner = new Scanner(System.in);
        while(true){
		int sum = 0;
		String a= scanner.next();
		if(a.equals("0")){
		    break;
		}
		for(int i = 0; i < a.length(); i++){
			sum += a.charAt(i)-'0';
		    }
		System.out.println(sum);
	    }
    }
}


Measured memory_bytes: 26368
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using TP = tuple<ll,ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(18);
}
const ll MAX = 410;
vector<vector<bool>> used(MAX,vector<bool>(MAX,false));
vector<string> s(MAX);
ll h,w,ans=0;
ll dfs(ll x,ll y,ll &brack){
  ll vx[]={1,0,-1,0},vy[]={0,1,0,-1};
  used[x][y] = true;
  ll res = 0;
  if(s[x][y]=='#') brack++;
  for(int i=0;i<4;i++){
    ll nx = vx[i] + x;
    ll ny = vy[i] + y;
    if(nx>=0&&ny>=0&&nx<h&&ny<w){
      if(!used[nx][ny]&&(s[x][y]!=s[nx][ny])){
        res += dfs(nx,ny,brack);
      }
    }
  }
  return res + 1;
}
signed main(){
  init_io();
  cin >> h >> w;
  for(int i=0;i<h;i++){
    cin >> s[i];
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(!used[i][j]){
        ll brack=0;
        ll area = dfs(i,j,brack);
        ans += brack*(area-brack);
      }
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 30464
#include <bits/stdc++.h>
#define rep(i,a) for(int i=0;i<int(a);++i)
#define REP(i,a,b) for(int i=int(a);i<int(b);++i)
using ll = long long;
using itn = int;
using namespace std;
int GCD(int a, int b){
    return b ? GCD(b, a%b) : a;
}
int main() {
	int n,a,b;
	cin >> n >> a >> b;
	cout << min(n*a,b) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_(i, n, m) for (int i = n; i < (int)(m); i++)
#define all(v) v.begin(), v.end()
#define int long long
#define stoi stoll
//#define _GLIBCXX_DEBUG



signed main() {
  int N, K, S; cin >> N >> K >> S;
  
  rep(i, K) cout << S << " ";
  rep(i, N-K) {
    if(S != 1000000000) cout << 1000000000 << " ";
    else cout << 1 << " ";
  }
  cout << endl;
  

  
}


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

const int DIM = 2e5 + 5;
const int MOD = 1e9 + 7;

int fct[DIM], inv[DIM];

int lgput( int x, int n ) {
    if( n == 0 )
        return 1;
    
    int y = lgput( x, n / 2 );
    y = ( 1LL * y * y ) % MOD;
    
    if( n % 2 == 1 )
        y = ( 1LL * y * x ) % MOD;
    
    return y;
}

inline int comb( int n, int k ) {
    return ( ( ( 1LL * fct[n] * inv[k] ) % MOD ) * inv[n - k] ) % MOD;
}

inline int getans( int l, int c ) {
    return comb( l + c, l );
}

int main( void ) {
    
    fct[0] = inv[0] = 1;
    for( int i = 1; i < DIM; i ++ )
        fct[i] = ( 1LL * fct[i - 1] * i ) % MOD;
    
    inv[DIM - 1] = lgput( fct[DIM - 1], MOD - 2 );
    for( int i = DIM - 2; i >= 1; i -- )
        inv[i] = ( 1LL * inv[i + 1] * (i + 1) ) % MOD;
    
    int h, w, a, b;
    cin >> h >> w >> a >> b;
    
    int ans = getans( h - 1, w - 1 );
    for( int j = 1; j <= b; j ++ ) {
        ans = ( ans - ( 1LL * getans( h - a - 1, j - 1 ) *
                              getans( a - 1, w - j ) ) % MOD + MOD ) % MOD;
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
import java.util.*;

class Main {
	public static void main(String[] arg) {
		Scanner sc = new Scanner(System.in);
		int A = Integer.parseInt(sc.next());
		int B = Integer.parseInt(sc.next());
		int s= 0;
		
		if(B == 1) {
			System.out.println(0);
			return;
		}
		
		for(int i = 1;;i++){
			if((i*(A-1)) + 1 >= B){
				s = i;
				break;
			}
			
		}
		System.out.println(s);
	}
}

Measured memory_bytes: 22868
import math
from math import pi, sqrt, sin, cos

A,B,H,M=map(int, input().split())

theta_H = H / 12 * 2 * pi + M / 12 / 60 * 2 * pi
theta_M = M / 60 * 2 * pi

D = sqrt((A*sin(theta_H)-B*sin(theta_M))**2+(A*cos(theta_H)-B*cos(theta_M))**2)

print(D)

Measured memory_bytes: 9552
import sys
readline = sys.stdin.readline   

def getpar(Edge, p):
    N = len(Edge)
    par = [0]*N
    par[0] = -1
    par[p]  -1
    stack = [p]
    visited = set([p])
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf in visited:
                continue
            visited.add(vf)
            par[vf] = vn
            stack.append(vf)
    return par

def topological_sort_tree(E, r):
    Q = [r]
    L = []
    visited = set([r])
    while Q:
        vn = Q.pop()
        L.append(vn)
        for vf in E[vn]:
            if vf not in visited:
                visited.add(vf)
                Q.append(vf)
    return L

def getcld(p):
    res = [[] for _ in range(len(p))]
    for i, v in enumerate(p[1:], 1):
        res[v].append(i)
    return res


def check(L, Par, wri, even):
    for i in range(len(Par)):
        if wri[i] and (wri[i] % 2 == even[i]):
            return False
    
    inf = 10**9+7
    dpu = [w if w is not None else inf for w in wri]
    dpd = [w if w is not None else -inf for w in wri]
    for l in L[::-1][:-1]:
        if dpu[l] == inf:
            continue
        if dpd[l] > dpu[l]:
            return False
        p = Par[l]
        dpu[p] = min(dpu[p], dpu[l] + 1)
        dpd[p] = max(dpd[p], dpd[l] - 1)
    if dpd[root] > dpu[root]:
        return False
    ans = [None]*N
    ans[root] = wri[root]
    for l in L[1:]:
        p = Par[l]
        if ans[p] - 1 >= dpd[l]:
            ans[l] = ans[p] - 1
        else:
            ans[l] = ans[p] + 1
    return ans
N = int(readline())
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)
K = int(readline())

VP = [tuple(map(lambda x: int(x), readline().split())) for _ in range(K)]
wri = [None]*N
for v, p in VP:
    wri[v-1] = p

root = VP[0][0] - 1
Par = getpar(Edge, root)
L = topological_sort_tree(Edge, root)

even = [True]*N
even[root] = (wri[root] %2 == 0)
for l in L[1:]:
    p = Par[l]
    even[l] = not even[p]
ans = check(L, Par, wri, even)
if ans == False:
    print('No')
else:
    print('Yes')
    print('\n'.join(map(str, ans)))

Measured memory_bytes: 107932
#include<bits/stdc++.h>
#define ll long long
#define vi vector<int>
#define vll vector<ll>
#define F first
#define S second
#define f(i,s,n) for(int i=(int)s;i<=(int)n;++i)
#define Fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
void solve()
{
	int n,d;cin>>n>>d;
	int ans=0;
	while(n--){
		double x,y;cin>>x>>y;
		double a=x*x+y*y;
		a=sqrt(a);
		if(a<=d)
		++ans;
	}
	cout<<ans;
}
int main()
{	Fast;
	//int t;cin>>t;
	//while(t--)
	solve();
}

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

// int/long:		-2147483648 - 2147483648 (-2^31 <= int < 2^31)
// long/long long:	-9223372036854775808 - 9223372036854775807 (-2^63 <= long < 2^63)
#define	INF (1<<29)
//536870912

#define	MOD 1000000007

int	main() {
	string s;
	cin >>s;
	string S;
	for (int i=0; i<s.size(); i++) {
		if ('B'==s.at(i)) {
			if (S.size()>0) {
				S.pop_back();
			}
		} else {
			S.push_back(s.at(i));
		}
	}
	cout <<S <<endl;
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pr pair<ll,ll>
using namespace std;
ll cnt[300005];
bool vis[300005];
int main() {
    int n;
    cin >> n;
    vector<ll> nn;
    for (int i = 0; i < n; i++) {
        ll a;
        cin >> a;
        cnt[a]++;
        if (!vis[a]) {
            vis[a] = 1;
            nn.push_back(a);
        }
    }
    for (int i = 0; i < nn.size(); i++) {
        nn[i] = cnt[nn[i]];
    }
    sort(nn.begin(), nn.end());
    vector<ll> pre;
    pre.push_back(nn[0]);
    for (int i = 1; i < nn.size(); i++) {
        pre.push_back(pre.back() + nn[i]);
    }
    cout << n << '\n';
    for (ll i = 2; i <= n; i++) {
        ll l = 0, r = 1LL*n / i;
        while (l != r) {
            ll m = l + r + 1 >> 1;
            ll p = lower_bound(nn.begin(),nn.end(), m) - nn.begin();
            ll sum=0;
            if (p)sum = pre[p - 1];
            ll x = nn.size() - p;
            if (x + sum / m >= i) {
                if (l == m)break;
                l = m;
            }
            else if (r == m)break;
            else r = m;
        }
        cout << l << '\n';
    }
    return 0;
}

Measured memory_bytes: 13928