akhauriyash/Code-Regression huggingface dataset:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    mod = 10**9 + 7

    n,k = map(int, input().split())
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(n-1):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)

    def dfs(v, par, k):
        if par == -1:
            kk = k-1
        else:
            kk = k-2

        res = 1
        if v == 0:
            res *= k

        for i in range(len(adj[v])):
            nv = adj[v][i]
            if  nv == par:
                continue
            res *= kk * dfs(nv, v, k)
            res %= mod
            kk -= 1
        return res

    res = dfs(0, -1, k)
    print(res)

if __name__ == '__main__':
    main()

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

int main()
{
	int n,i,s=0;
	cin>>n;
	int a[n+1];
	for(i=1; i<=n; i++)  cin>>a[i];
	
	for(i=1; i<=n-1; i++)
	{
		if(a[i]<a[i+1])
		{
			swap(a[i],a[i+1]);
			s++;
		}
	}
	
	cout<<n-s<< endl;
	return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<queue>
#define LL long long
#define _ int mid=(l+r)>>1
#define ___ t1[p]=min(t1[p<<1],t1[p<<1|1]);t2[p]=min(t2[p<<1],t2[p<<1|1])
#define __ push(p)
using namespace std;
inline int read( )
{
  int sum=0;char c=getchar( );bool f=0;
  while(c<'0'||c>'9') {if(c=='-') f=1;c=getchar( );}
  while(c>='0'&&c<='9') {sum=sum*10+c-'0';c=getchar( );}
  if(f) return -sum;
  return sum;
}
const int N=200015;
const LL INF=1000000000000000000LL;
int n,m,at;LL v;
LL t1[N*4],t2[N*4],tag[N*4];
inline int abs(int x) {return x<0?-x:x;}
inline void build(int p,int l,int r)
{
  if(l==r) {l==at?t1[p]=l,t2[p]=-l:t1[p]=t2[p]=INF;return;}
  _;build(p<<1,l,mid);
  build(p<<1|1,mid+1,r);___;
}
inline void lab(int p,LL x) {t1[p]+=x;t2[p]+=x;tag[p]+=x;}
inline void push(int p)
{
  LL u=tag[p];if(!u) return;
  int L=p<<1,R=L|1;lab(L,u);lab(R,u);tag[p]=0;
}
inline LL a1(int p,int l,int r,int L,int R)
{
  if(l==L&&r==R) return t1[p];_;__;
  if(R<=mid) return a1(p<<1,l,mid,L,R);
  else if(L>mid) return a1(p<<1|1,mid+1,r,L,R);
  else return min(a1(p<<1,l,mid,L,mid),a1(p<<1|1,mid+1,r,mid+1,R));
}
inline LL a2(int p,int l,int r,int L,int R)
{
  if(l==L&&r==R) return t2[p];_;__;
  if(R<=mid) return a2(p<<1,l,mid,L,R);
  else if(L>mid) return a2(p<<1|1,mid+1,r,L,R);
  else return min(a2(p<<1,l,mid,L,mid),a2(p<<1|1,mid+1,r,mid+1,R));
}
inline void ch(int p,int l,int r)
{
  if(l==r) {t1[p]=v+l;t2[p]=v-l;return;}_;__;
  if(at<=mid) ch(p<<1,l,mid);else ch(p<<1|1,mid+1,r);___;
}
inline void DFS(int p,int l,int r)
{
  if(l==r) {v=min(v,t1[p]-l);return;}_;__;
  DFS(p<<1,l,mid);DFS(p<<1|1,mid+1,r);
}
int main( )
{
  int i,x,y;LL r1,r2;
  n=read( );m=read( );at=read( );x=read( );build(1,1,n);
  for(i=1;i<=m;i++)
    {
      y=read( );
      r1=a1(1,1,n,y,n)-y;
      r2=y==1?INF:a2(1,1,n,1,y-1)+y;
      lab(1,abs(x-y));      
      at=x;v=min(r1,r2);ch(1,1,n);
      x=y;
    }
  v=INF;DFS(1,1,n);cout<<v;
  return 0;
}

Measured memory_bytes: 18688
const config = {
    input: '/dev/stdin',
    newline: '\n'
};

const line = require('fs').readFileSync(config.input, 'utf-8').split(config.newline);

const isPrime = n => {
    if (n < 2) return false;
    if (n === 2) return true;
    for (let i = 2; i*i <= n; i++) {
        if (n % i === 0) return false;
    }
    return true;
};

const ans = line.slice(1, line.length-1)
                .map(x => parseInt(x))
                .reduce((acc, x) => isPrime(x) ? acc + 1 : acc, 0);
console.log(ans);


Measured memory_bytes: 18188
#include <iostream>

#include <vector>
using namespace std;
int main(){
  int n,p;
  for(;;){
    cin >>n >> p;
    if(n == 0 && p == 0)break;
    int human[n];
    for(int i = 0;i < n;i++){
      human[i]=0;
    }
    int stone = p;
    int turn = 0;
    for(;;){
      if(!stone){
        stone += human[turn];
        human[turn] = 0;

      } else if(stone > 0){
        stone--;
        human[turn]++;
        if(!stone && human[turn] == p){
          cout << turn << endl;
          break;
        }
      }

      turn++;
      if(turn >= n) turn = 0;
    }

  }
}

Measured memory_bytes: 2980
/* 
 * Project: AtCoder Beginners Contest 140 C - Maximal Value
 * Author: toms74209200 <https://github.com/toms74209200>
 *
 * Created on 2020/09/06
 * Copyright (c) 2020 toms74209200
 * 
 * This software is released under the MIT License.
 * http://opensource.org/licenses/mit-license.php
 */
#include <cstdio>
#include <cstdint>
#include <vector>
using namespace std;

uint32_t n;
vector<uint32_t> b;

void solve() {

    uint64_t sum = 0;
    sum += *b.begin();
    sum += *(b.end()-1);
    for (int i=0;i<n-2;i++) {
        sum += min(b[i], b[i+1]);
    }

    printf("%llu\n", sum);

}

int main() {

    scanf("%d", &n);
    b.resize(n-1);
    for (int i=0;i<n-1;i++) {
        scanf("%d", &b[i]);
    }

    solve();

}

Measured memory_bytes: 3264
n,a,b=map(int,input().split())
if b<a:
  print(0)
  exit()
  
if a==b:
  print(1)
  exit()
  

n-=2

if n<0:
  print(0)
  exit()

if n==0:
  print(1)
  exit()

print(b*n-a*n+1)


Measured memory_bytes: 61872
#include <set>
#include <map>
#include <list>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
#define int long long

signed main(void){
  int a,b,c;
  cin >> a >> b >> c;
  if( c >= a && c <= b){
    cout << "Yes\r\n";
  }else{
    cout << "No\r\n";
  }
  return 0;
}


Measured memory_bytes: 256
import sys
def is_anagram(s):
    return s == s[::-1]
S = input()
N = len(S)
if not is_anagram(S):
    print('No')
    sys.exit()
cond1 = int(((N-1)/2))
cond1 = S[0:cond1]
cond2 = int(((N+3)/2)-1)
cond2 = S[cond2:]
if is_anagram(cond1) and is_anagram(cond2):
    print('Yes')
else:
    print('No')


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

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

void insertionSort(int A[],int n){
	int tmp;
	int j;
	for(int i=1;i<n;i++){
		show(A,n);
		tmp=A[i];
		j=(i-1);
		while(j>=0 && A[j]>tmp){
			A[j+1]=A[j];
			j--;
		}
		A[j+1]=tmp;
		
	}
}

int main(){
    int n;
	int *A;

	scanf("%d",&n);
	A=(int*)malloc(sizeof(int)*n);
	for(int i=0;i<n;i++){
		scanf("%d",&A[i]);
	}

	insertionSort(A,n);
	show(A,n);

	return 0;
}


Measured memory_bytes: 2044
A = input()
B = input()
digita = A.__len__()
digitb = B.__len__()
if digita > digitb:
  print("GREATER")
elif digita < digitb:
  print("LESS")
else:
  for i in range(digita):
    if A[i] > B[i]:
      print("GREATER")
      break
    elif A[i] < B[i]:
      print("LESS")
      break
  else:
    print("EQUAL")

Measured memory_bytes: 3060
#include<cstdio>
long long a[100010]={0,1,2,3,4,5,6,7,8,9}; 
int main()
{
	int k,id=1;scanf("%d",&k);
	for(int i=10; i<=k; )
	{
		long long x=a[id]*10,y=a[id++]%10;
		if(y==0) a[i++]=x,a[i++]=x+1;
		else if(y==9) a[i++]=x+8,a[i++]=x+9;
		else a[i++]=x+y-1,a[i++]=x+y,a[i++]=x+y+1;
	}
	printf("%lld\n",a[k]);
	return 0;
}


Measured memory_bytes: 2464
#include <stdio.h>

int main() {
  int n;
  int memo[51] = { 0 };
  for (int a = 0; a <= 9; a++) {
    for (int b = 0; b <= 9; b++) {
      for (int c = 0; c <= 9; c++) {
        for (int d = 0; d <= 9; d++) {
          memo[a + b + c + d]++;
        }
      }
    }
  }
  while (~scanf("%d", &n)) {
    printf("%d\n", memo[n]);
  }
  return 0;
}


Measured memory_bytes: 2080
#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mid ((x + y) / 2)
#define left (ind * 2)
#define right (ind * 2 + 1)
#define mp make_pair
#define timer ((double)clock() / CLOCKS_PER_SEC)
#define endl "\n"
#define spc " "
#define d1(x) cerr<<#x<<":"<<x<<endl
#define d2(x, y) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<endl
#define d3(x, y, z) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<endl
#define fast_io() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

typedef long long int lli;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<double, double> dd;

const int N = (int)(2e3 + 5);
const int LOG = (int)(20);

lli n, cs, ar[N], mini[N][N], tree[N], ans = LONG_LONG_MAX;

void build(int ind, int x, int y) {
	if(x == y) {
		tree[ind] = ar[x];
		return;
	}
	build(left, x, mid);
	build(right, mid + 1, y);
	tree[ind] = min(tree[left], tree[right]);
}

lli get(int ind, int x, int y, int a, int b) {
	if(a > b)
		return min(get(ind, x, y, 1, b), get(ind, x, y, a, n));
	if(y < a || b < x)
		return LONG_LONG_MAX;
	if(a <= x && y <= b)
		return tree[ind];
	return min(get(left, x, mid, a, b), get(right, mid + 1, y, a, b));
}

int main() {
	fast_io();
//	freopen("inp.in", "r", stdin);

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

	build(1, 1, n);

	for(lli k = 0; k <= n - 1; k++) {
		lli t = k * cs;
		for(int i = 1; i <= n; i++) {
			int l = i - k;
			if(l <= 0)
				l += n;
			int r = i;
			t += get(1, 1, n, l, r);
		}
		ans = min(ans, t);
	}
	cout << ans;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1e9)
#define PI (acos(-1))
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl

/*
    // 配列の最大値を取得
    int max = *max_element(vec.begin(), vec.end());
    // 配列の最大値のイテレータを取得
    vector<int>::iterator maxIt = max_element(vec.begin(), vec.end());
    // 配列の最大値までの距離を取得
    int maxIndex = distance(vec.begin(), maxIt);
    // 隣り合う重複要素を削除し、末尾のゴミを削除
    // (uniqueは、重複を取り除いた範囲の末尾の次を指すイテレータを返す)
    vec.erase(unique(vec.begin(), vec.end()), vec.end());
    // pair
    vector<pair<int, int>> v;
    v.push_back(make_pair(a, b));
*/

int main() {
    string S;  cin >> S;
    
    int a = count(S.begin(), S.end(), '0');
    int b = S.size() - a;
    print((a < b ? a : b) * 2);
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    string s;
    cin >>s;
    if(s.length()%2==1){
        char k=s[s.length()/2];
        int i=1;
        while(i<=s.length()/2&&s[i+(s.length()/2)]==k&&s[(s.length()/2)-i]==k)i++;
        cout << i+(s.length()/2);

    }else{
        if(s[s.length()/2]!=s[s.length()/2-1])cout << s.length()/2;
        else{
            char k=s[s.length()/2];
            int i=1;
            while(i<s.length()/2 &&s[i+(s.length()/2)]==k&&s[s.length()/2 -1-i]==k)i++;
        cout << i+ s.length()/2;
        }
    }
    return 0;
}

Measured memory_bytes: 512
#include<stdio.h>
#include<math.h>

typedef struct{
  double x,y;
}Point;

void koch(int,Point,Point);

int main() {

  Point a,b;
  int n;

  scanf("%d",&n);

  a.x = 0;
  a.y = 0;
  b.x = 100;
  b.y = 0;

  printf("%.8f %.8f\n",a.x,a.y);
  koch(n,a,b);
  printf("%.8f %.8f\n",b.x,b.y);

  return 0;

}

void koch(int n, Point a, Point b) {

  if(n == 0) return;

  Point s,t,u;
  double th = M_PI * 60.0 / 180.0;

  s.x = (2.0 * a.x + 1.0 * b.x) / 3.0;
  s.y = (2.0 * a.y + 1.0 * b.y) / 3.0;
  t.x = (1.0 * a.x + 2.0 * b.x) / 3.0;
  t.y = (1.0 * a.y + 2.0 * b.y) / 3.0;
  u.x = (t.x - s.x) * cos(th) - (t.y - s.y) * sin(th) + s.x;
  u.y = (t.x - s.x) * sin(th) + (t.y - s.y) * cos(th) + s.y;

  koch(n-1,a,s);
  printf("%.8f %.8f\n",s.x,s.y);
  koch(n-1,s,u);
  printf("%.8f %.8f\n",u.x,u.y);
  koch(n-1,u,t);
  printf("%.8f %.8f\n",t.x,t.y);
  koch(n-1,t,b);
}


Measured memory_bytes: 2052
#include<bits/stdc++.h>
using namespace std;
int a[100000];
int main()
{

    int i,j;
    int n;
    for(i=2;i<=30000;i+=2)
        a[i]=1;
    cin>>n;
    if(n<=6)
    {

        if(n==3)
        {

            cout<<2<<" "<<5<<" "<<63<<endl;

        }
        if(n==4){

             cout<<2<<" "<<5<<" "<<63<<" "<<20<<endl;
        }

        if(n==5)
        {
             cout<<2<<" "<<5<<" "<<63<<" "<<20<<" "<<30<<endl;
        }
        if(n==6)
        {
             cout<<2<<" "<<5<<" "<<63<<" "<<20<<" "<<30<<" "<<60<<endl;
        }




    }
    else{
            int fl=0;
            vector<int> u;
              u.push_back(2);
              u.push_back(4);
              u.push_back(3);
              u.push_back(9);
              int co=4;
              if(n%2)
                fl=1;
              n=n-n%2;
              for(i=8;i<=30000;i+=2)
              {
                  if(co==n)
                    break;
                  if(i%6==0)
                    continue;
                  u.push_back(i);
                  co++;



              }
               for(i=15;i<=30000;i+=3)
              {
                  if(co==n)
                    break;
                  if(i%6==0)
                    continue;
                  u.push_back(i);
                  co++;



              }
             n=n+fl;
               for(i=6;i<=30000;i+=6)
              {
                  if(co==n)
                    break;

                  u.push_back(i);
                  co++;



              }


        for(auto i:u)
            cout<<i<<" ";
        cout<<endl;



    }






    return 0;
}


Measured memory_bytes: 640
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from heapq import heapify, heappop, heappush
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
def f(x, y, z):
    return x**2 + y**2 + z **2 + x * y + y * z + z * x

L = [0] * (N + 1)
thre =  ceil(sqrt(N)) + 1
# print(thre)
for x in range(1, thre+1):
    for y in range(1, thre + 1):
        for z in range(1, thre + 1):
            if f(x,y,z) <= N:
                L[f(x, y, z)] += 1
print(*L[1:], sep="\n")





Measured memory_bytes: 10272
import java.util.Scanner;
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cardNum = Integer.parseInt(sc.next());
        int gateNum = Integer.parseInt(sc.next());
        int min = 0;
        int max = 0;

        min = Integer.parseInt(sc.next());
        max = Integer.parseInt(sc.next());

        for(int gtn = 1; gtn < gateNum; gtn++){
            int mint = Integer.parseInt(sc.next());
            if(min < mint) min = mint;
            int maxt = Integer.parseInt(sc.next());
            if(max > maxt) max = maxt;
        }

        int counter = 0;
        for(int i = 1; i <= cardNum; i++) {
            if(i >= min && i <= max) counter++;
        }
        System.out.println(counter);
    }
}

Measured memory_bytes: 48144
n = int(input())
a = list(map(int, input().split()))


def f(p):
    sa = 0
    ans = 0
    for ai in a:
        if p:
            sa += ai
            if sa >= 0:
                ans += sa + 1
                sa = -1
            p = False
        else:
            sa += ai
            if 0 >= sa:
                ans += 1 - sa
                sa = 1
            p = True
    return ans


def main():
    print(min(f(True), f(False)))


main()


Measured memory_bytes: 14332
N = int(input())
mn=100
for A in range(1,int(N**(0.5))+1):
    cnta=0
    cntb=0
    if N%A==0:
        B=N/A
        while A>0:
            A//=10
            cnta+=1
        while B>0:
            B//=10
            cntb+=1
        cnt=max(cnta,cntb)
        mn=min(mn,cnt)
print(mn)

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

int main()
{
	int A, B;
	scanf("%d %d", &A, &B);
	int i,ans=0;
	for (i = 0;i < 2;i++)
	{
		if (A > B) {
			ans += A;
			A--;
		}
		else {
			ans += B;
			B--;
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 128
N=int(input())
A=list(map(int,input().split()))
A=[0]+A
B=[0]*(N+1)
for i in range(N):
  k=N-i 
  c=0
  for j in range(k,N+1,k):
    c+=B[j]
    c%=2
  if A[k]!=c:
    B[k]=1
    
print(sum(B))
for i in range(len(B)):
  if B[i]==1:
    print(i)

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

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

int main(void){
  int x, y, size;
  while(scanf("%d,%d,%d", &x, &y, &size) != EOF){
    if(size == 1){
      map[x][y]++;
      for(int i = 0; i < 4; i++){
        int nx = x + dx[i], ny = y + dy[i];
        if(0 <= nx && nx < 10 && 0 <= ny && ny < 10) map[nx][ny]++;
      }
    }else if(size == 2){
      for(int i = -1 ; i <= 1; i++) for(int j = -1; j <= 1; j++){
        int nx = x + i, ny = y + j;
        if(0 <= nx && nx < 10 && 0 <= ny && ny < 10) map[nx][ny]++;
      }
    }else if(size == 3){
      for(int i = -1 ; i <= 1; i++) for(int j = -1; j <= 1; j++){
        int nx = x + i, ny = y + j;
        if(0 <= nx && nx < 10 && 0 <= ny && ny < 10) map[nx][ny]++;
      }
      if(y + 2 < 10) map[x][y + 2]++;
      if(0 <= y - 2) map[x][y - 2]++;
      if(x + 2 < 10) map[x + 2][y]++;
      if(0 <= x - 2) map[x - 2][y]++;
    }
  }  
  int cnt = 0, maxCard = 0;
  for(int i = 0; i < 10; i++) for(int j = 0; j < 10; j++){
    if(map[i][j] == 0) cnt++;
    if(map[i][j] > maxCard) maxCard = map[i][j]++;
  }
  
  cout << cnt << endl << maxCard << endl;
  return 0;
}

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

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;

int main() {
  string s;
  cin >> s;
  int notOk = 0;
  if (s.size() == 1) {
    cout << "-1 -1" << '\n';
  } else {
    int found = 0;
    for (int i = 0; i < (int)s.size() - 2; i++) {
      set<char> x({s[i], s[i+1], s[i+2]});
      if (x.size() == 2) {
        cout << i+1 << ' ' << i+3 << '\n';
        found = 1;
        break; 
      }
    }
    for (int i = 0; i < (int)s.size() - 1 && !found; i++) {
      set<char> x({s[i], s[i+1]});
      if (x.size() == 1) {
        cout << i+1 << ' ' << i+2 << '\n';
        found = 1;
        break; 
      }
    }
    if (!found) {
      cout << "-1 -1" << '\n';
    }
  }
  return 0;
}

Measured memory_bytes: 512
import math
import fractions
import sys
#入力:N(int:整数)
def input1():
	return str(input())

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(str,input().split()))


a,b,c=input2()

if a+b+c>=22:
	print("bust")
else:
	print("win")






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

using namespace std;
 
int main()
{
    string s;
    cin>>s;
    int n=s.size();
    if(s[n-1]=='s')
    {
        s+="es";
    }
    else
    {
        s+="s";
    }
    cout<<s<<endl;
    return 0;
}

Measured memory_bytes: 3592
#include <cstdio>
#include <iostream>
#include <cstring>

#define MAX 100000

int main()
{
	int N, Q, l[MAX], r[MAX], num[MAX], count=0;
	std::string S;
	scanf("%d %d", &N, &Q);
	std::cin >> S;
	for(int i=0; i<N-1; i++){
		if(S[i] == 'A' && S[i+1] == 'C'){
			S[i] = 'a';
		}
	}
	num[0] = 0;
	for(int i=0; i<N-1; i++){
		if(S[i] == 'a'){
			count+=1;
		}
		num[i+1] = count;
	}
	// for(int i=0; i<N; i++){
	// 	printf("%d", num[i]);
	// }
	for(int i=0; i<Q; i++){
		scanf("%d %d", &l[i], &r[i]);
	}
	for(int i=0; i<Q; i++){
		printf("%d\n", num[r[i]-1]-num[l[i]-1]);
	}
	return 0;
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
using namespace std;
#define ALL(obj) (obj).begin(),(obj).end()
const int INF=100000000;


int main()
{
    string s;
    set<int> st;
    cin >> s;
    for(int i=0;i<s.size();i++) st.insert(s.at(i));
    for(int i=0;i<26;i++){
        set<int>::iterator iti=st.find('a'+i);
        if(iti==st.end()){
            char p='a'+i;
            cout << p << endl;
            return 0;
        }
    }
    cout << "None" << endl;

    return 0;
}

Measured memory_bytes: 512
N = int(input())
flag = True
shiritori_dict = {}
new_word = ""
old_word = input()
shiritori_dict[old_word] = True
for i in range(1, N):
    new_word = input()
    if old_word[-1] != new_word[0]:
        flag = False
    if new_word not in shiritori_dict:
        shiritori_dict[new_word] = True
    else:
        flag = False
    old_word = new_word
if flag:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
local function upper_bound(key,ary)
    local n=#ary
    if n==0 then
        return 1 
    end
    if key<ary[1] then
        return 1
    end
    if key>=ary[n] then
        return n+1
    end
    local min,max=1,n
    while 1<max-min do
        local mid=math.floor((min+max)/2)
        if key>=ary[mid] then
            min=mid
        else
            max=mid
        end
    end
    return max
end

n=io.read("*n","*l")
l={}
for i=1,n do
    l[i]=io.read("*n")
end
table.sort(l)
counter=0
for i=n,3,-1 do
    large=l[i]
    for j=i-1,2,-1 do
        middle=l[j]
        if middle*2<=large then
            break
        end
        local smallmin=upper_bound(large-middle,l)
        if smallmin<j then
            counter=counter+j-smallmin
        end
    end
end
print(counter)

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

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rep(i, n) repd(i, 0, n)

using namespace std;

using ll = long long;
using ul = unsigned long long;
ll mod = 1000000007;

int main() {
source:
    ll a[3];
    rep(i, 3) { cin >> a[i]; }
    sort(a, a + 3);
    ll all = a[0] * a[1] * a[2];
    ll half = a[0] * a[1] * (a[2] / 2);
    cout << all - half * 2 << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MAXN=17;
int n,a[MAXN],ans,x[MAXN][MAXN],y[MAXN][MAXN],jud[MAXN];
int main () {
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		for (int j=1;j<=a[i];j++) {
			scanf("%d%d",&x[i][j],&y[i][j]);
		}
	}
	for (int i=0;i<(1<<n);i++) {
		memset(jud,0,sizeof(jud));
		int flg=0;
		for (int j=0;j<n;j++) {
			if (i&(1<<j)) {jud[j+1]=1,flg++;}
		}
		for (int j=1;j<=n;j++) {
			if (i&(1<<(j-1))) {
				for (int k=1;k<=a[j];k++) {
					if (jud[x[j][k]]^y[j][k]) {flg=0;break;}
				}
			}
		}
		ans=max(ans,flg);
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 256
n = int(input())
ans = [0]*n
ans2 = [0]*n
a=list(map(int, input().split()))
b=list(map(int, input().split()))
amax=0
bmax=0

for i in range(n//2):
  if a[i]>amax:
    amax=a[i]
    ans[i]=1
    ans2[i]=a[i]
  elif a[i]<amax:
    print(0)
    quit()
  else:
    ans[i]=amax
  if b[-(i+1)]>bmax:
    bmax=b[-(i+1)]
    ans[-(i+1)]=1
    ans2[-(i+1)]=b[-(i+1)]
  elif b[-i-1]<bmax:
    print(0)
    quit()
  else:
    ans[-(i+1)]=bmax

if n%2==1:  
  i=n//2
  if a[i]>amax:
    amax=a[i]
    ans[i]=1
    ans2[i]=a[i]
  elif a[i]<amax:
    print(0)
    quit()
  else:
    ans[i]=amax
    
for i in range(n//2, n):
  if a[i]>amax:
    amax=a[i]
    if ans[i]==1 and a[i]!=ans2[i]:
        print(0)
        quit()
    elif ans[i] != 1 and ans[i]<a[i]:
      print(0)
      quit()
    ans[i]=1
  elif a[i]<amax:
    print(0)
    quit()
  else:
    ans[i]=min(amax, ans[i])
  if b[-(i+1)]>bmax:
    bmax=b[-(i+1)]
    if ans[-(i+1)]==1 and b[-(i+1)]!=ans2[-(i+1)]:
        print(0)
        quit()
    elif ans[-i-1]!=1 and ans[-i-1]<b[-i-1]:
      print(0)
      quit()
    ans[-(i+1)]=1
  elif b[-i-1]<bmax:
    print(0)
    quit()
  else:
    ans[-(i+1)]=min(bmax, ans[-(i+1)])
    
kotae=1
for i in range(n):
  kotae*=ans[i]
  kotae%=(10**9+7)
print(kotae)

Measured memory_bytes: 100276
#include <iostream>
#include <string>

int main()
{
	std::string A, B;

	std::cin >> A >> B;

	int count = 0;

	for (size_t index = 0; index < A.size(); ++index)
	{
		if (A.at(index)==B.at(index))
		{
			continue;
		}
		++count;
	}

	std::cout << count << std::endl;
}



Measured memory_bytes: 3440
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <deque>
#include <math.h>
#include <cstring>
#include <string.h>
#include <iomanip>
#include <stdlib.h>
#include <queue>
#include <stack>
#include<cassert>
#include <cfloat>
#include <list>
using namespace std ;
#define ll long long
#define submitStage int TCF = 1 ;
#define testStage int TCF = 1000 ;
#define testMyStupedCode TCF--
void FastInputOutput(){
    ios_base :: sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
}
void ReadFromFile( string name , string extention ){
    string fullPath = name + "." + extention ;
    freopen( fullPath.c_str() , "r" , stdin ) ;
}
inline int D(){
    int t ;
    scanf( "%d" , &t ) ;
    return t ;
}
inline ll LLD(){
    ll t ;
    scanf( "%lld" , &t ) ;
    return t ;
}
inline char C(){
    char c ;
    scanf( "%c" , &c ) ;
    return c ;
}
inline ll power(ll x, ll p, ll m){
    ll res = 1;
    while(p){
        if(p & 1)
            res = (res * x) % m;
        x = (x * x) % m;
        p >>= 1;
    }
    return res;
}
long double ModLog(long double base, long double x) {
    return (logl(x) / logl(base));
}

const int N = 3e3 + 5;
int dp[N][N], n, m;
char a[N], b[N];

void print(int i, int j){
     if(!i || !j)
          return;
     int ret = dp[i][j];
     if(ret == dp[i - 1][j])
          print(i - 1, j);
     else if(ret == dp[i][j - 1])
          print(i, j - 1);
     else{
          print(i - 1, j - 1);
          printf("%c", a[i - 1]);
     }
}
int main(){
     scanf("%s %s", a, b);
     n = strlen(a);
     m = strlen(b);
     for(int i = 1; i <= n; ++i)
          for(int j = 1; j <= m; ++j)
               if(a[i - 1] == b[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
               else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
     print(n, m);
     return 0;
}



Measured memory_bytes: 35584
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;

int main(){
	int L;
	cin >> L;
	int r=(int) log2(L);
	int N=r+1;
	vector<int> v,u,w;
	for(int i=1;i<N;i++){	
		v.push_back(i);
		u.push_back(i+1);
		w.push_back(0);
		v.push_back(i);
		u.push_back(i+1);
		w.push_back(pow(2,i-1));
	}
	for(int i=N-1;i>0;i--){
		if(L-pow(2,i-1)>=pow(2,r)){
			v.push_back(i);
			u.push_back(N);
			w.push_back(L-pow(2,i-1));
			L-=pow(2,i-1);
		}
	}
	cout << N << ' ' << v.size() << endl;
	for(int i=0;i<v.size();i++){
		cout << v[i] << ' ' << u[i] << ' ' << w[i] << endl;
	}
}


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

int main() {
  int a, b;
  cin >> a >> b;
  int r = -1;
  for (int i = 0; i < 20 * b; i++) {
    if (int(0.08 * i) == a && int(0.1 * i) == b) {
      r = i;
      break;
    }
  }
  cout << r << endl;
}


Measured memory_bytes: 384
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
class BinaryIndexedTree:
	def __init__(self, n):
		self.size = n
		self.bit = [0] * (n + 1)
 
	def sum(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= (i & -i)
		return s
 
	def add(self, i, x):
		while i <= self.size:
			self.bit[i] += x
			i += (i & -i)

            
def solve():
  n = int(input())
  for i in range(n+1):
    for j in range(i+1,n):
      x = i^j
      ct = 0
      while (x>0):
        x //= 2
        ct += 1
      print(ct,end=" ")
    print("")
      
solve()

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

int main() {
  int N, M, C;
  cin >> N >> M >> C;
  int X = 0;
  vector<int> vec_b(M);
  for(int i=0; i<M; i++)
    cin >> vec_b.at(i);
  
  for(int i=0; i<N; i++){
    vector<int> vec(M);
    for(int k=0; k<M; k++)
    cin >> vec.at(k);
    
    int sum = 0;
    for(int j=0; j<M ;j++){ 
        sum += vec.at(j) * vec_b.at(j);
    }
    sum += C;
    if(sum>0)
      X++;
    else
      continue;
  }
  cout << X << endl;
}

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

using namespace std;

const int N = 2e5 + 10;

int n, k;
int a[N];

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    int l = 1, r = (int)(1e9);
    while (l <= r) {
        int mid = l + r >> 1, ret = 0;
        for (int i = 1; i <= n; i++)
            ret += (a[i] / mid) + (a[i] % mid ? 1 : 0) - 1;
        if (ret <= k)
            r = mid - 1;
        else
            l = mid + 1;
    }
    printf("%d\n", r + 1);
}


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

ll INF = 1LL << 60;

int 
main() {

  int X; cin >> X;
  int ans = 1;
  for(int i = 1; i * i <= X; i++){
    for(int k = 2; k <= X; k++){
      if(pow(i,k) <= X) ans = max(ans, (int)pow(i, k));
    }
  }

  cout << ans << endl;

}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>

#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = Y-1;(X) >= 0;--(X))
#define repa(X,A,Y) for (int (X) = A;(X) <= (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define mod(n, m) (((n)%(m)+(m))%m)
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
const int INFINT = 1 << 30;                          // 1.07x10^ 9
const ll INFLL = 1LL << 60;                          // 1.15x10^18
const double EPS = 1e-10;
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

const int MAX_AB = 100000, MAX_Q = 100000;
ll A, B, Q;
ll s[MAX_AB], t[MAX_AB];
ll x[MAX_Q];

int main() {

  cin >> A >> B >> Q;
  rep(i, A) cin >> s[i];
  rep(i, B) cin >> t[i];
  rep(i, Q) cin >> x[i];

  for (int q = 0; q < Q; ++q) {
      ll rs_idx = lower_bound(s, s+A, x[q]) - s;
      ll rt_idx = lower_bound(t, t+B, x[q]) - t;
      ll ls_idx = (s[rs_idx] == x[q] ? rs_idx : rs_idx - 1);
      ll lt_idx = (t[rt_idx] == x[q] ? rt_idx : rt_idx - 1);

      ll ans = INFLL;
      // right
      if (rs_idx != A && rt_idx != B) {
          ans = min(ans, max(s[rs_idx]-x[q], t[rt_idx]-x[q]));
      } 
      // left
      if (ls_idx >= 0 && lt_idx >= 0) {
          ans = min(ans, max(x[q]-s[ls_idx], x[q]-t[lt_idx]));
      }

      // right left
      if (rs_idx != A && lt_idx >= 0) {
          ans = min(ans, s[rs_idx]-x[q]+s[rs_idx]-t[lt_idx]);
      }
      if (rt_idx != B && ls_idx >= 0) {
          ans = min(ans, t[rt_idx]-x[q]+t[rt_idx]-s[ls_idx]);
      }

      // left right
      if (ls_idx >= 0 && rt_idx != B) {
          ans = min(ans, x[q]-s[ls_idx]+t[rt_idx]-s[ls_idx]);
      }
      if (lt_idx >= 0 && rs_idx != A) {
          ans = min(ans, x[q]-t[lt_idx]+s[rs_idx]-t[lt_idx]);
      }


      cout << ans << endl;
  }

  return 0;
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define REP1(i,a,b) for(int i=a; i<=(int)(b); i++)
#define ALL(x) begin(x),end(x)
#define PB push_back
using namespace std;
typedef int64_t LL;
typedef vector<int> VI;
typedef pair<int,int> PII;

template<class T> inline bool chmax( T &a, const T &b ) { return b>a ? a=b,true : false; }
template<class T> inline bool chmin( T &a, const T &b ) { return b<a ? a=b,true : false; }
template<class T> using MaxHeap = priority_queue<T>;
template<class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template<class T, class F=less<T>> void sort_uniq( vector<T> &v, F f=F() ) {
    sort(begin(v),end(v),f);
    v.resize(unique(begin(v),end(v))-begin(v));
}

const int INF=2e9+10;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<PII> a;
    REP(i,n) {
        int x,l;
        cin >> x >> l;
        a.emplace_back(x+l,x-l);
    }
    sort(ALL(a));
    int ans=0,t=-INF;
    REP(i,n) {
        if ( t<=a[i].second ) {
            ans++; t=a[i].first;
        }
    }
    cout << ans << '\n';
    return 0;
}










Measured memory_bytes: 1400
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iterator>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <utility>
#include <memory>
#include <functional>
#include <deque>
#include <cctype>
#include <ctime>
#include <numeric>
#include <list>
#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll;
typedef vector<vector<long long> > vvll;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}

#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _rep(i,n) _rep2((i),0,(n))
#define _rep2(i,a,b) for(int i=(a);i<(b);++i)
#define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define fi first
#define se second
#define mkp make_pair
#define DEBUG
#ifdef DEBUG
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#else
#define dump(x) 
#define debug(x) 
#endif

#define MOD 1000000007LL
#define EPS 1e-8
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)

void mainmain(){
	int H,W;
	cin>>H>>W;
	vint cnt(26);
	rep(i,H){
		rep(j,W){
			char t;
			cin>>t;
			cnt[t-'a']++;
		}
	}
	sort(ALL(cnt));
	map<int,int> ma;
	rep(i,26){
		if(cnt[i]==0) continue;
		ma[cnt[i]]++;
	}
	bool ok = false;
	if(H%2==1 && W%2==1){
		int tmp = ((H-1)/2) + ((W-1)/2);
		int c = 0;
		int d = 0;
		ok = true;
		for(auto x: ma){
			if(x.fi%2){
				d += x.se;
				if((x.fi-1)%4) c += x.se;
			}
			// if(x.fi%2) ok=false;
			else if(x.fi%4) c += x.se;
		}
		if(c>tmp) ok=false;
		if(d!=1) ok=false;
	}
	else if(H%2==0 && W%2==0){
		ok = true;
		for(auto x: ma){
			if(x.fi%4){
				ok=false;
			}
		}
	}
	else{
		if(W%2==0) swap(H, W);
		int tmp = H/2;
		int c = 0;
		// cout<<tmp<<endl;
		if(ma[1] == 0){
			ok = true;
			for(auto x: ma){
				if(x.fi==1) continue;
				if(x.fi%2) ok=false;
				if(x.fi%4) c += x.se;
			}
			if(c>tmp) ok=false;
		}
	}
	cout<<(ok?"Yes":"No")<<endl;
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout<<fixed<<setprecision(20);
    mainmain();
}

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

typedef pair<int,int> P;
int N,M;
unordered_map<int,vector<int> > G[500005];
vector<int> V[100005];
int H[500003];
P E[500005];
const int INF = INT_MAX;

int solve(){
  priority_queue<P,vector<P>,greater<P> > q;
  q.push( P(0,0) );
  fill( H, H + N + 2*M, INF );
  H[0] = 0;
  while( !q.empty() ){
    P p = q.top(); q.pop();
    int id = p.second, cost = p.first;
    if( H[id] < cost ) continue;
    if( id < N ) {
      int nc = cost + 1;
      for( int v : V[id] ){
        if( H[v] > nc ){
          H[v] = nc;
          q.push( P( nc, v ) );
        }
      }
    } else {
      P e = E[id];
      int now = e.first, c = e.second;
      //cout << "edge to : " << now << " , " << c << endl;      
      if( H[now] > cost ){
        H[now] = cost;
        q.push( P( cost, now ) );
      }
      
      if( !G[now].count( c ) ) continue;
      for( int to : G[now][c] ){
        if(  H[to] > cost ){
          H[to] = cost;
          q.push( P( cost, to ) );
        }
      }      
    }
  }
  return H[N-1];
}

map<P,int> fc;
void add_node(int p, int c,int &cnt){
  if( !fc.count( P( p,c ) ) ){
    V[ p ].push_back( cnt );
    E[cnt] = P( p, c );
    fc[ P(p,c) ] = cnt++;
  }
}

int main(){
  cin >> N >> M;
  int cnt = N;
  for(int i=0;i<M;i++){
    int p,q,c; cin >> p >> q >> c; --p; --q;
    add_node( p, c, cnt );
    add_node( q, c, cnt );
    G[p][c].push_back( fc[ P( q,c ) ] );
    G[q][c].push_back( fc[ P( p,c ) ] );    
  }
  int res = solve();
  if( res == INF ) cout << -1 << endl;
  else cout << res << endl;
}


Measured memory_bytes: 103412
#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
#include <iomanip>
#include <algorithm>
using namespace std;

typedef long long ll;

const int Maxn = 105;

int n;
int a[Maxn];
int tk[Maxn];
ll res, best;

void Solve(int lvl)
{
	//printf("Solve(%d)\n", lvl);
	for (int i = lvl; i <= n && 3 * i <= n; i++) if (!tk[i]) {
	//	printf("got %d\n", i);
		for (int j = i; j <= n; j += i) 
			if (tk[j]++ == 0) res -= a[j];
	//	printf("tk %d, res = %lld\n", i, res);
		Solve(i + 1);
		for (int j = i; j <= n; j += i)
			if (--tk[j] == 0) res += a[j];
	//	printf("ret %d (%d, %d, %d)\n", i, tk[1], tk[2], tk[3]);
	}
	ll cur = res;
	int i;
	for (i = n; 2 * i > n; i--) if (!tk[i] && a[i] < 0)
		cur -= a[i];
	for (; 3 * i > n; i--) if (!tk[i] && a[i] < 0) {
		ll got = a[i];
		if (!tk[i + i] && a[i + i] >= 0) got += a[i + i];
		if (got < 0) cur -= got;
	}
	best = max(best, cur);
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		res += a[i];
	}
	for (int i = n; i >= 1; i--)
		if (2 * i > n && a[i] < 0) {
			res -= a[i]; tk[i] = true;
		}
	Solve(1);
	cout << best << endl;
	return 0;
}

Measured memory_bytes: 256
package main

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

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	Case := 1
	for {
		scanner.Scan()
		W, _ := strconv.Atoi(scanner.Text())
		if W == 0 {
			break
		}
		scanner.Scan()
		n, _ := strconv.Atoi(scanner.Text())
		w := make([]int, n+1)
		v := make([]int, n+1)
		for i := 1; i <= n; i++ {
			scanner.Scan()
			info := strings.Split(scanner.Text(), ",")
			v[i], _ = strconv.Atoi(info[0])
			w[i], _ = strconv.Atoi(info[1])
		}
		// fmt.Println(v)
		// fmt.Println(w)
		dp := make([][]int, n+1)
		for i := range dp {
			dp[i] = make([]int, W+1)
		}
		maxV := -(1 << 21)
		minW := 1 << 21
		for i := 1; i <= n; i++ {
			for j := 1; j <= W; j++ {
				// fmt.Println(dp)
				if j-w[i] >= 0 {
					dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])
					if maxV < dp[i][j] {
						maxV = dp[i][j]
						minW = j
					} else if maxV == dp[i][j] {
						minW = min(minW, j)
					}
				} else {
					dp[i][j] = dp[i-1][j]
				}
			}
		}
		fmt.Printf("Case %d:\n", Case)
		Case += 1
		fmt.Println(maxV)
		fmt.Println(minW)
	}
}
func max(x, y int) int {
	if x < y {
		return y
	}
	return x
}
func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}


Measured memory_bytes: 9772
h,w=map(int,input().split())
a=[]
for _ in [0]*h:
    ai=list(input())
    #print(ai)
    if "#" in ai:
        a.append(ai)
t=[]
for wi in zip(*a):
    if "#" in wi:
        t.append(wi)
for ans in zip(*t):
    print("".join(ans))


Measured memory_bytes: 38256
/*
ID: arunesh2
TASK: ride
LANG: C++                 
*/
/* LANG can be C++11 or C++14 for those more recent releases */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    set<ll> s;
    for(int i=0;i<3;i++)
    {
        ll p;cin>>p;
        s.insert(p);
    }
    cout<<s.size()<<"\n";
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
const int MAX_N = 1 << 19;
int n;
template<class V, int NV> struct SegTree{
    V comp(V l, V r) {return min(l, r);};
    
    vector<V> dat;

    SegTree() {
        dat = vector<V>(MAX_N, {INF, INF});
        n = 1;
        while(n < NV) n *= 2;
        rep(i, 2 * n - 1) dat[i] = {INF, INF};
    }

    // k番目の値(0-indexed)をaに変更
    void update(int k, V a) {
        k += n - 1;
        dat[k] = a;
        while(k > 0) {
            k = (k - 1) / 2;
            dat[k] = comp(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }
    // [a, b)の最小値を探す．
    V query(int a, int b, int k, int l, int r) {
        if(r <= a || b <= l) return {INF, INF};
        if(a <= l && r <= b) return dat[k];
        else {
            V vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
            V vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return comp(vl, vr);
        }
    }
};
int N, p[200010];
SegTree<pair<int, int>, 1 << 18> st1, st2;

vector<int> E[200010];
int pR[200010];

void dfs(int L, int R, int pa = 0) {
    //cout <<"*"<< L << " " << R << endl;
    pair<int, int> mi1, mi2;
    // 区間が2であれば、ペアが確定
    if (L + 1 == R) {
        E[pa].push_back(p[L]);
        pR[p[L]] = p[R];
        return;
    }

    if (L % 2 == 0) {
        mi1 = st1.query(L, R, 0, 0, n);
        mi2 = st2.query(mi1.second + 1, R + 1, 0, 0, n);
    } else {
        mi1 = st2.query(L, R, 0, 0, n);
        mi2 = st1.query(mi1.second + 1, R + 1, 0, 0, n);
    }
    int i = mi1.second;
    int j = mi2.second;
    //cout << mi1.first << " " << mi2.first << endl;
    //ペアが決まったので、代入
    E[pa].push_back(mi1.first);
    pR[mi1.first] = mi2.first;
    //cout << "OK" << endl;
    if (L != i) dfs(L, i - 1, mi1.first);
    if (i + 1 != j) dfs(i + 1, j - 1, mi1.first);
    if (R != j) dfs(j + 1, R, mi1.first); 

}

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    rep(i, N) cin >> p[i];
    rep(i, N) {
        if (i % 2 == 0) st1.update(i, {p[i], i});
        else st2.update(i, {p[i], i});
    }

    dfs(0, N - 1);

    vector<int> ans;
    priority_queue<int, vector<int>, greater<int>> que;
    que.push(E[0].front());

    while(!que.empty()) {
        int q = que.top(); que.pop();

        ans.push_back(q);
        ans.push_back(pR[q]);

        for(auto x: E[q]) que.push(x);
    }
    rep(i, N) {
        if (i != 0) cout << " ";
        cout << ans[i];
    }
    cout << endl;


    return 0;
}


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

typedef long long ll;

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

    int n,a;
    cin >> n >> a;
    if(n%500<=a) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

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

int main(){
	int n,t,x,y;
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d %d %d",&t,&x,&y);
		if((t%(x+y)!=0 and (t-x-y)%2!=0) or t<x+y){
			cout<<"No"<<endl;
			return 0;
		}
	}
	cout<<"Yes"<<endl;
}


Measured memory_bytes: 256
import sys
input=sys.stdin.readline

def main():
    N = int(input())
    V1 = {}
    V2 = {}
    V = list(map(int, input().split()))
    for i,v in enumerate(V):
        if i%2 == 0:
            V1[v] = V1[v] + 1 if v in V1 else 1
        else:
            V2[v] = V2[v] + 1 if v in V2 else 1

    V1 = sorted(V1.items(), key=lambda x:x[1], reverse=True)
    V2 = sorted(V2.items(), key=lambda x:x[1], reverse=True)

    if V1[0] != V2[0]:
        ans = 0
        for v in V1[1:]:
            ans += v[1]
        for v in V2[1:]:
            ans += v[1]
        print(ans)
    else:
        a1 = 0
        for v in V1[1:]:
            a1 += v[1]
        a1 += V2[0][1]
        for v in V2[2:]:
            a1 += v[1]
        a2 = 0
        a2 += V1[0][1]
        for v in V1[2:]:
            a2 += v[1]
        for v in V2[1:]:
            a2 += v[1]
        print(min(a1,a2))

if __name__ == '__main__':
    main()


Measured memory_bytes: 17752
#include<iostream>
#include<cmath>
#include<vector>
#include<utility>

using namespace std;


int partition(vector<int>& A,int p){
  int x=0;
  int i=0;

  //partition 基準
  int r=A.size()-1;

  x = A[r];
  i =p-1;
   for(int j=0;j<r;j++){
      if(A[j]<=x){
          i++;
          swap(A[i],A[j]);
      }
   }
   swap(A[i+1],A[r]);
   return i+1;
}











int main(){

    int n=0;
    int temp = 0;
    int q=0;
    cin >> n;
    vector<int> A;

    for(int i=0;i<n;i++){
        cin >> temp;
        A.push_back(temp);
    }

    q = partition(A,0);
 
    for(int i=0;i<n;i++){
        if(i!=0)cout << " ";
        if(i==q){cout << "[" << A[i]<< "]";}
         else {cout << A[i];}
    }
    cout << endl;

    return 0;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

int main() {
    int a, p;
    cin >> a >> p;
    p += a * 3;
    cout << p / 2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

#ifdef _DEBUG
#define DMP(x) cerr << #x << ": " << x << "\n"
#else
#define DMP(x) ((void)0)
#endif

const int MOD = 1000000007, INF = 1111111111; 
using namespace std;
typedef long long lint;

int main() {

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

	int H, W;
	cin >> H >> W;

	vector<vector<char>> tile(H, vector<char>(W));
	for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) cin >> tile[i][j];

	vector<int> row(H, 1), col(W, 1);
	for (int i = 0; i < H; i++) {

		bool flag = true;
		for (int j = 1; j < W; j++) {

			if (tile[i][j - 1] != tile[i][j]) {
				flag = false;
				break;
			}
		}

		if (flag && tile[i][0] == '.') row[i] = 0;
	}	

	for (int j = 0; j < W; j++) {

		bool flag = true;
		for (int i = 1; i < H; i++) {

			if (tile[i - 1][j] != tile[i][j]) {
				flag = false;
				break;
			}
		}

		if (flag && tile[0][j] == '.') col[j] = 0;
	}

	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {

			if (row[i] & col[j]) cout << tile[i][j];

		}
		if (row[i]) cout << "\n";
	}

	return 0;
	
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int N,M;cin>>N>>M;
    const int mod=1e9+7;
	int A[M];
	for(int i=0;i<M;i++){
		cin>>A[i];
	}
	int dp[N+1];dp[0]=1;
	int j;
	if(A[0]==1){
		j=1;
		dp[1]=0;
	}else{
		j=0;
		dp[1]=1;
	}for(int i=2;i<=N;i++){
		if(i==A[j]){
			dp[i]=0;
			if(j<M-1) j++;
		}else{
			dp[i]=(dp[i-1]+dp[i-2])%mod;
		}
	}cout<<dp[N]<<endl;
}

Measured memory_bytes: 1024
N, M = [int(i) for i in input().split()]
L, R = 0, N + 10
for l, r in [[int(i) for i in input().split()] for _ in range(M)]:
    L = max(L, l)
    R = min(R, r)
if R < L:
    print(0)
else:
    print(R - L + 1)

Measured memory_bytes: 21156
for i in range(3005):
    input_list = [int(x) for x in input().split()]
    
    if input_list[0] == 0 and input_list[1] == 0: 
        break
    else: 
        input_list.sort()
        input_list = [str(x) for x in input_list]
        print(' '.join(input_list))


Measured memory_bytes: 5624