akhauriyash/Code-Regression huggingface dataset:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,k=map(int,input().split())
a=list(map(int,input().split()))

# cnt=1
# for i in range(k):
#     cnt*=a[i]

for i in range(k,n):
    # tmp=cnt
    # cnt*=a[i]
    # cnt//=a[i-k]
    # print(tmp,cnt)
    if a[i-k]<a[i]:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 103968
#include <iostream>
using namespace std;
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	long a,b,x;
	cin >> a >> b >> x ;
	if (a<=x && a+b >= x)
	{
		cout << "YES\n";
	}else{
		cout << "NO\n";
	}
	return 0;
}

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

int main(){
  int N, A, B;
  cin >> N >> A >> B;
  int ans=0;
  for(int i=1; i<=N; i++){
    int sum=0;
    int j=i;
    while(j!=0){
      sum+=j%10;
      j=j/10;
    }
    if(sum>=A && sum<=B) ans+=i;
  }
  cout << ans << endl;
}

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

// int main(){
//     int k;
//     cin>>k;
//     if(k<10){
//         cout<<k<<endl;
//         return 0;
//     }
//     ll ans=10;
//     int cnt=9;
//     while(true){
//         string s=to_string(ans);
//         bool f=true;
//         for(int i=0;i<s.size()-1;i++){
//             if(abs(s[i]-s[i+1])>1){
//                 f=false;
//                 break;
//             }
//         }
//         if(f){
//             cnt++;
//             if(cnt==k){
//                 cout<<ans<<endl;
//                 return 0;
//             }
//         }
//         ans++;
//     }
//     return 0;
// }

int main(){
    int k;
    cin>>k;
    vector<ll> a;
    for(int i=1;i<=9;i++)a.push_back(i);
    while(1){
        if(k<=a.size()){
            cout<<a[k-1]<<endl;
            return 0;
        }
        k-=a.size();
        vector<ll> old;
        swap(old,a);
        for(ll x:old){
            for(int i=-1;i<=1;i++){
                int d=x%10+i;
                if(d<0||d>9)continue;
                ll nx=x*10+d;
                a.push_back(nx);
            }
        }
    }
    return 0;
}

Measured memory_bytes: 1712
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int x, a, b;
int main()
{
	scanf("%d %d %d",&x, &a, &b);
	int d = x - a;
	printf("%d\n",d % b);
}

Measured memory_bytes: 888
N,M,X,Y=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
k=str()
if X>=Y:
  k='War'
else:  
  for i in range(X+1,Y+1):
    if max(x)<i<=min(y):
      k='No War'
      break
    elif max(x)>=i or min(y)<i:
      k='War'
      continue
      
print(k)

Measured memory_bytes: 3060
type bs_tree = Nil | Node of node and
     node = {
         key:int;
         mutable parent:bs_tree;
         mutable left:bs_tree;
         mutable right:bs_tree
       };;

let new_node key = {key=key;parent=Nil;left=Nil;right=Nil};;

let insert t z =
  let rec loop y = function
      Nil -> y
    | Node x ->
       if z.key < x.key then
         loop (Node x) (x.left)
       else
         loop (Node x) (x.right)
  in
  let y = loop t t in
  z.parent <- y;
  match y with
    Nil -> (Node z)
  | Node y ->
     if z.key < y.key then
       y.left <- (Node z)
     else
       y.right <- (Node z)
    ;t
;;

let rec print_in = function
    Nil -> ()
  | Node x ->
     print_in (x.left);
     Printf.printf " %d" x.key;
     print_in (x.right)
;;

let rec print_pre = function
    Nil -> ()
  | Node x ->
     Printf.printf " %d" x.key;
     print_pre (x.left);print_pre (x.right)
;;

let () =
  let n = read_int () in
  let rec read t = function
      0 -> ()
    | i ->
       let com = Scanf.scanf "%s" (fun x -> x) in
       if com = "insert" then begin
           let arg = Scanf.scanf " %d\n" (fun x -> x) in
           let z = new_node arg in
           read (insert t z) (i-1)
         end
       else if com = "print" then begin
           let _ = Scanf.scanf "%s\n" (fun x -> x) in
           print_in t;print_newline ();
           print_pre t;print_newline ();
           read t (i-1)
         end
       else ()
  in read Nil n
;;

Measured memory_bytes: 40232
def is_right(i):
  trueA =bin(i)[2:].zfill(N)
  for ii,flag in enumerate(trueA):
    if flag == '1':
      for x,y in A[ii]:
        if trueA[x] != str(y):
          return False
  return True

N = int(input())
A = []
for _ in range(N):
  a = int(input())
  tmpA = []
  for _ in range(a):
    x,y = map(int,input().split())
    tmpA.append([x-1,y])
  A.append(tmpA)

ans = 0
for i in range(2**N):
  if is_right(i):
    ans = max(ans,bin(i).count('1'))
print(ans)

Measured memory_bytes: 44892
def m():
    n, M, Q = map(int, input().split())
    a = [[0 for _ in range(n+1)] for _ in range(n+1)]
    b = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(M):
        l, r = map(int, input().split())
        a[l][r] += 1

    for i in range(1, n+1):
        b[1][i] += a[1][i] + b[1][i-1]
    for i in range(2, n+1):
        b[i][1] += a[i][1] + b[i-1][1]

    for i in range(1, n+1):
        for j in range(1, n+1):
            b[i][j] = a[i][j] + b[i-1][j] + b[i][j-1] - b[i-1][j-1]

    for i in range(Q):
        p, q = map(int, input().split())
        ans = b[q][q] + b[p-1][p-1] - b[q][p-1] - b[p-1][q]
        print(ans)

m()

Measured memory_bytes: 61928
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
char a[511][511];
int n;
int main(){
	scanf("%d\n",&n);
	for (int i = 0; i < n; i++){
		scanf("%s\n",a[i]);
	}
	int tot = 0, flag = 0;
	for (int i = 0; i < n; i++){
		int cnt = 0;
		for (int j = 0; j < n; j++)
			cnt += a[j][i] == '#';
		if (cnt == n) tot++;
		if (cnt > 0) flag = 1;
	}
	int ans = 1e9;
	if (flag == 0) cout << -1 << endl;
	else {
		for (int i = 0; i < n; i++) {
			int tmp = 0;
			int o = 0;
			if (a[i][i] == '.'){
				for (int k = 0; k < n; k++)
					if (a[k][i] == '#')  o = 1;
				if (!o) tmp += 2;
				else tmp += 1;

			}

			for (int j = 0; j < n; j++)
				if (a[i][j] == '.' && j != i) tmp++;
			ans = min(ans, tmp + n - tot);
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string.h>

#define MAX_LINE 8
#define MAXA_DATA 50

using namespace std;

// プロトタイプ宣言
void searchString(string box);

// main関数
int main() {
    int count = 0;
    int max = MAX_LINE * MAXA_DATA;
    char str[8];
    string box;
    for (int i=0; i<max; i++) {
        cin >> str;
        box.append(str);
        count++;
        // 8行ごとにチェック
        if(count%MAX_LINE == 0){
            searchString(box);
            box = "";
        }
    }
}

// 文字列チェック
void searchString(string box){
    string A("1100000011");
    string B("1000000010000000100000001");
    string C("1111");
    string D("1000000110000001");
    string E("11000000011");
    string F("100000001100000001");
    string G("110000011");
    // find関数は文字列がみつからなかったときにnposを返す
    if (box.find(A) != std::string::npos) {
        cout << "A" << endl;
    }
    else if(box.find(B) != std::string::npos) {
        cout << "B" << endl;
    }
    else if(box.find(C) != std::string::npos) {
        cout << "C" << endl;
    }
    else if(box.find(D) != std::string::npos) {
        cout << "D" << endl;
    }
    else if(box.find(E) != std::string::npos) {
        cout << "E" << endl;
    }
    else if(box.find(F) != std::string::npos) {
        cout << "F" << endl;
    }
    else if(box.find(G) != std::string::npos) {
        cout << "G" << endl;
    }
}


Measured memory_bytes: 3104
import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner scan = new Scanner(System.in);
		String str1 = scan.next();
		scan.close();
		
		String str2 = str1.replaceAll("[a-z]", "x");
		System.out.println(str2);
	}
}

Measured memory_bytes: 22612
#include<iostream>
#include<vector>
#include<sstream>
#include<istream>

using namespace std;

int main(){

    int a[3][3]={{0}};
    string s,buf;
    stringstream ss;
    
    for(int i=0;i<3;i++){
        getline(cin,s);
        ss<<s;     
        
        for(int j=0;j<3;j++){
            getline(ss, buf, ' ');
            a[i][j]=stoi(buf);        
        }
        ss.str("");
        ss.clear(stringstream::goodbit);
    }

    if(a[1][2]-a[1][0]+a[0][0]-a[0][2]== 0 &&
    a[2][2]-a[2][0]+a[0][0]-a[0][2]== 0 &&
    a[1][1]-a[1][0]+a[0][0]-a[0][1]==0 &&
    a[2][1]-a[2][0]+a[0][0]-a[0][1]==0){
        cout<<"Yes"<<endl;
    }else{cout<<"No"<<endl;}
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;

int A[111111];

int main(){
    int N, M;
    cin >> N >> M;
    for(int i=0; i<M; i++){
        int L, R;
        cin >> L >> R;
        A[L]++;
        A[R+1]--;
    }
    for(int i=1; i<=100000; i++)
        A[i] += A[i-1];
    int ans = 0;
    for(int i=0; i<=100000; i++)
        if(A[i] == M)
            ans++;
    cout << ans << endl;
    return 0;
}

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

const int score_win = 3;
const int score_draw = 1;

int main() {
  int turn_num;
  string player1_word, player2_word;
  int player1_score = 0, player2_score = 0;

  cin >> turn_num;

  for(int i = 0; i < turn_num; i++) {
    cin >> player1_word >> player2_word;

    int result = player1_word.compare(player2_word);

    if(result == 0) {
      player1_score += score_draw;
      player2_score += score_draw;
    } else if(result > 0) {
      player1_score += score_win;
    } else {
      player2_score += score_win;
    }
  }

  printf("%d %d\n", player1_score, player2_score);
}



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

int main() {
  int W, H, x, y, r;
  cin >> W >> H >> x >> y >> r;
  
  if (r <= x && x <= W-r &&
     r <= y && y <= H-r) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  
  return 0;
  
}



Measured memory_bytes: 3120
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using static System.Math;
using static System.Array;
using static AtCoderSolve.Tool;

namespace AtCoderSolve
{
    class Solve
    {
        const int mod = 1000000007;
        const int INF = int.MaxValue / 2;
        const long SINF = long.MaxValue / 2;


        static void Main(string[] args)
        {
            //var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            //Console.SetOut(sw);
            var cin = new Scanner();

            var input = cin.SplitReaderL();
            long A = input[0];
            long B = input[1];
            long K = input[2];
            while (K > 0)
            {
                Exchange(ref A, ref B);
                K--;
                if (K > 0)
                {
                    Exchange(ref B, ref A);
                    K--;
                }
            }

            Console.WriteLine($"{A} {B}");


            //Console.Out.Flush();
        }

        public static void Exchange(ref long a, ref long b)
        {
            if (a % 2 == 1)
            {
                a--;
            }
            a /= 2;
            b += a;
        }


    }

    public class Scanner
    {
        public int[] SplitReader()
        {
            int[] array = Console.ReadLine().Split().Select(int.Parse).ToArray();
            return array;
        }
        public long[] SplitReaderL()
        {
            long[] array = Console.ReadLine().Split().Select(long.Parse).ToArray();
            return array;
        }
    }

    public static class Tool
    {
        static public void Initialize<T>(ref T[] array, T initialvalue)
        {
            for(var i = 0; i < array.Length; i++)
            {
                array[i] = initialvalue;
            }
        }
        static public long ModuloP(long value,long mod)
        {
            long r = value % mod;
            
            if (r * mod < 0)
            {
                r += mod;
            }
            return r;
        }

    }

    struct Pair<T> : IComparable<Pair<T>> where T : IComparable<T>
    {
        public T variable;
        public int index;

        public Pair(T val, int i)
        {
            variable = val;
            index = i;
        }

        public int CompareTo(Pair<T> otherPair)
        {
            return variable.CompareTo(otherPair.variable);
        }

        public int CompareIndex(Pair<T> otherPair)
        {
            return index.CompareTo(otherPair.index);
        }
    }



}






Measured memory_bytes: 13396
import java.util.Scanner;

class Main{
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		StringBuilder all = new StringBuilder();
		StringBuilder out = new StringBuilder();
		
		while(true){
			
			int h = sc.nextInt();
			int w = sc.nextInt();
			
			if((h + w) <= 0){break;}
			
			
			for(int t = 0; t < w; t++){
				out = out.append("#");
			}
			out = out.append("\n");
			
			
			
			for(int j = 0; j < (h-2); j++){
				out = out.append("#");
				for(int i = 0; i < (w-2); i++){
						out = out.append(".");
					}
				out = out.append("#");
				out = out.append("\n");
			}
			
		
			for(int b = 0; b < w; b++){
				out = out.append("#");
			}
			
			out = out.append("\n");
		
			all = all.append(out + "\n");
			out.delete(0, out.length());
			
		}
		
		System.out.print(all);
	}
}


Measured memory_bytes: 28216
s = int(input())
 
if s == 1 or s == 2 or s == 4:
  print(4)
else:  
  cnt = 1
  while True:
    if s % 2  == 0:
      s = int(s/2)
    else:
      s = 3*s + 1
    if s == 4:
      break
    else:
      cnt += 1
  print(cnt+4)

Measured memory_bytes: 3316
import math
a, b, h, m = map(int, input().split())
c = h * 30 + m * 0.5
d = m * 6
x = min(abs(c-d), 360-abs(c-d))
if x <= 180:
    e = x
else:
    e = x-180
f = e/180*math.pi
if e == 0:
    print(abs(a-b))
elif e == 180:
    print(a+b)
else:
    print(math.sqrt(a*a + b*b - (2*a*b*math.cos(f))))

Measured memory_bytes: 9404
#include <stdio.h>

class Dice4{
public:
	int number[6];

	void roll(char dst){
		switch(dst){
		case 'E':
			setNumber(number[3],number[1],number[0],number[5],number[4],number[2]);
			break;
		case 'N':
			setNumber(number[1],number[5],number[2],number[3],number[0],number[4]);
			break;
		case 'S':
			setNumber(number[4],number[0],number[2],number[3],number[5],number[1]);
			break;
		case 'W':
			setNumber(number[2],number[1],number[5],number[0],number[4],number[3]);
			break;
		}
	};

	bool isSameDice(int inputed[]){
		char order[25] = "NNNNWNNNWNNNENNNENNNWNNN";
		for(int i = 0; i < 24; i++){
			roll(order[i]);
			for(int j = 0; j < 6; j++){
				if(inputed[j] != number[j])
					break;
				if(j == 5)
					return true;
			}
		}
		return false;
	}

private:
	void setNumber(int n0,int n1,int n2,int n3,int n4,int n5){
		number[0] = n0;
		number[1] = n1;
		number[2] = n2;
		number[3] = n3;
		number[4] = n4;
		number[5] = n5;
	}

};

int main(){
	int n,k,j;
	scanf("%d",&n);
	Dice4 array[n];
	for(int i = 0; i < n; i++){
		scanf("%d %d %d %d %d %d",&array[i].number[0],&array[i].number[1],&array[i].number[2],
				&array[i].number[3],&array[i].number[4],&array[i].number[5]);
	}
	for(k = 0; k < n-1; k++){
		for(j = k+1; j < n; j++){
			if(array[k].isSameDice(array[j].number))
				break;
		}
		if(j < n) break;
	}
	if(k == n-1){
		printf("Yes\n");
	}else{
		printf("No\n");
	}
}

Measured memory_bytes: 1012
#include <bits/stdc++.h>
 
int ri() {
	int n;
	scanf("%d", &n);
	return n;
}
 
int main() {
	int k = ri();
	int cur = 0;
	int res = -1;
	for (int i = 1; i <= k; i++) {
		cur = (cur * 10 + 7) % k;
		if (cur == 0) {
			res = i;
			break;
		}
	}
	printf("%d\n", res);
	return 0;
}

Measured memory_bytes: 3772
#include<bits/stdc++.h>
#define pb push_back
#define PI acos(-1)
#define mp make_pair
#define F first
#define sd(x) scanf("%d",&x)
#define sd2(x,y) scanf("%d%d",&x,&y)
#define sdl(x) scanf("%lld",&x)
#define sd2l(x,y) scanf("%lld%lld",&x,&y)
#define maxn 100100
#define S second
#define ll long long int
#define inf 1000000014
#define infl (ll)(1e18+1)
#define mod 1000000007
#define clrs(x) memset(x,0,sizeof x)
#define sz(x) (int) x.size()
#define pi pair< ll,int >
#define pii pair<pi,int>
#define pu push
#define ld long double
#define trace1(x)  cerr << #x << ": " << x << endl
#define trace2(x, y)  cerr << #x << ": " << x << " | " << #y << ": " << y << endl
using namespace std;
using namespace std;
int p[maxn],q[maxn];
ll modexp(ll a, ll b)
{
  if(b==0)
    return 1ll;
  else
    if(b==1)
      return a;
  else
      if(b%2==1)
      return (a*modexp(a,b-1))%mod;
  else
    return modexp((a*a)%mod,b/2);
}
int main()
{
  //freopen("input.txt","r",stdin);
  int h,w;
  sd2(w,h);ll ans  = 0;
  for(int i=0;i<w;i++)
  {
      sd(p[i]);
  }
  for(int i=0;i<h;i++)
  {
      sd(q[i]); 
  }
  sort(p,p+w);
  sort(q,q+h);
  int c1,c2;
  c1 = h+1;c2 = w+1; 
  int ptr1 = 0;
  int ptr2 = 0 ;
  while(ptr1 < w && ptr2 < h)
  {
      if(p[ptr1]<=q[ptr2])
      {
          ans+= p[ptr1]*1ll*c1;
          c2--;
          ptr1++;
      }
      else
      {
          ans+= q[ptr2]*1ll*c2;
          c1--;
          ptr2++;
      }
    //  cout<<ans<<"\n";
  }
  while(ptr1 < w)
  {
       ans+= p[ptr1]*1ll*c1;
       c2--;
       ptr1++;
  }
   while(ptr2 < h)
  {
       ans+= q[ptr2]*1ll*c2;
       c1--;
       ptr2++;
  }
  cout<<ans<<"\n";
  return 0;
}


Measured memory_bytes: 1024
//chiragjn
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define gibe_de_fast_io_b0ss ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
const ll mod = 1e9 + 7;
const ll INF = 0x7FFFFFFFFFFFFFFF/2;
int main(){
    gibe_de_fast_io_b0ss;
    int n;
    cin>>n;
    vector<int> arr(n, 0), cache(n, INT_MAX / 2);
    
    for(int i = 0; i < n; i++) {
    	cin>>arr[i];
    }
    cache[0] = 0;
    for(int i = 1; i < n; i++) {
    	cache[i] = min(cache[i], cache[i - 1] + abs(arr[i] - arr[i - 1]));
    	if(i > 1) {
    		cache[i] = min(cache[i], cache[i - 2] + abs(arr[i] - arr[i - 2]));	
    	}
    }
    cout<<cache[n - 1];
    return 0;
}


Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
	static BufferedReader input =
			new BufferedReader (new InputStreamReader (System.in));
	static List<Integer> list = new ArrayList<Integer>();
	public static void main(String[] a) throws IOException {
		Integer num = 0;
		for (int i = 0; i < 10; ++i) {
			try {
				num = Integer.parseInt(input.readLine());
			} catch (NumberFormatException e) {
				System.exit(0);
			}
			if (num < 0 || 10000 < num) {
				System.exit(0);
			}
			list.add(num);
		}
		Collections.sort(list);
		System.out.println(list.get(9) + "\n" + list.get(8) + "\n" + list.get(7));
	}
}

Measured memory_bytes: 17012
/*
 * main.c
 *
 *  Created on: 2019/02/16
 *      Author: londo
 */

#include<stdio.h>

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


Measured memory_bytes: 128
N = int(input())
b = list(map(int,input().split()))
tmp = b[:]
ans = []
i = N-1
while i >= 0:
    if tmp[i] == 1:
        tmp[i] = float('inf')
        ans.append(b[i])
        while i < N:
            tmp[i] -= 1
            i += 1
    i -= 1
if len(ans) == N:
    for i in ans:
        print(i)
else:
    print(-1)

Measured memory_bytes: 3064
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

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

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
const ll mod = 1e9 + 7;

double inf = 1.0/0;

int main(void){
  double xs, ys, xt, yt;
  cin >> xs >> ys >> xt >> yt;
  int n;
  cin >> n;
  vector<double> x(n + 2), y(n + 2), r(n + 2);
  REP(i, 0, n) {
    cin >> x[i] >> y[i] >> r[i];
  }
  x[n] = xs;
  y[n] = ys;
  r[n] = 0;
  x[n + 1] = xt;
  y[n + 1] = yt;
  r[n + 1] = 0;
  vector<vector<double> > dist(n + 2, vector<double>(n + 2, inf));
  REP(i, 0, n + 2) {
    dist[i][i] = 0;
  }
  REP(i, 0, n + 2) {
    REP(j, 0, n + 2) {
      double sqdist = pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2);
      double rdist = sqrt(sqdist);
      dist[i][j] = max(0.0, rdist - r[i] - r[j]);
    }
  }
  typedef pair<double, int> PDI;
  priority_queue<PDI, vector<PDI>, greater<PDI> > que;
  que.push(PDI(0.0, n));
  vector<double> d(n + 2, 1.0/0);
  double EPS = 1e-11;
  while (not que.empty()) {
    PDI t = que.top(); que.pop();
    int v = t.second;
    if (d[v] <= t.first + EPS) {
      continue;
    }
    d[v] = t.first;
    REP(i, 0, n + 2) {
      que.push(PDI(d[v] + dist[v][i], i));
    }
  }
  printf("%.15f\n", d[n + 1]);
}


Measured memory_bytes: 24688
#include <stdio.h>

int main()
{
    int A;
    int B;

    scanf("%d %d", &A, &B);

    if (A >= 13)
    {
        printf("%d", B);
    }
    else if (13 > A && A > 5) //不等式の書き方とは違い活を使うだろ普通
    {
        printf("%d", B / 2);
    }
    else if (5 >= A)
    {
        printf("0");
    }
    return 0;
}


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

#define rep(i,n) for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define NP next_permutation
#define pb push_back
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef multiset<ll> S;
typedef priority_queue<ll> PQ;
typedef priority_queue<P,vector<P>,greater<P>> SPQ;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;

const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;

template<class T> bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T> void decimal(T a){cout<<fixed<<setprecision(a);}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<endl;}
template<class T> void outvp(T v){rep(i,v.size())outp(v[i]);}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> void outvv(T v){rep(i,v.size()){rep(j,v[i].size()){if(j)cout<<' ';cout<<v[i][j];}cout<<endl;}}

void YesNo(bool a){if(a) out("Yes"); else out("No");}
void yesno(bool a){if(a) out("yes"); else out("no");}
void YESNO(bool a){if(a) out("YES"); else out("NO");}
ll GCD(ll a,ll b){if(b==0) return a; return GCD(b,a%b);}
ll LCM(ll a,ll b){return(a/GCD(a,b))*(b/GCD(a,b))*GCD(a,b);}
ll POW(ll a,ll b){ll c=1; while(b>0){if(b&1){c=a*c %mod;}a=a*a %mod;b>>=1;}return c;}
vi calc(ll x){vi res; while(x>0){res.pb(x%10);x/=10;}reverse(all(res)); return res;}

void solve() {
  vi lucas;
  rep(i,100){
    if(i==0) lucas.eb(2);
    else if(i==1) lucas.eb(1);
    else lucas.eb(lucas[i-2]+lucas[i-1]);
  }
  ll n;
  cin>>n;
  out(lucas[n]);
}

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


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <stack>
#include <map>
#include <cmath>
#include <algorithm>
#include <functional>
#include <limits>
#include <array>
#include <queue>

using State = std::array<int, 3>;

int main(int argc, char *argv[]){
    int X,Y,Z,K;
    std::cin>>X>>Y>>Z>>K;
    std::vector<long long>A(X),B(Y),C(Z);
    for(auto &a:A){
        std::cin>>a;
    }
    for(auto &b:B){
        std::cin>>b;
    }
    for(auto &c:C){
        std::cin>>c;
    }

    std::sort(A.begin(),A.end(),std::greater<long long>());
    std::sort(B.begin(),B.end(),std::greater<long long>());
    std::sort(C.begin(),C.end(),std::greater<long long>());

    auto ID = [](State s){
        long long id = 0LL;
        for(int i=0; i<3; ++i){
            id <<= 10;
            id |= s[i];
        } 
        return id;
    };

    auto S = [](long long id){
        State s;
        for(int i=2; i>=0; --i){
            s[i] = id&((1<<10)-1);
            id >>= 10;
        } 
        return s;
    };


    std::vector<bool>isVisited(1<<30,false);

    using qel = std::pair<long long, long long>;
    auto compare = [](const qel &lhs, const qel &rhs){
        return lhs.second < rhs.second;
    };
    std::priority_queue<qel, std::vector<qel>,decltype(compare)> queue(compare);

    queue.emplace(0,A[0]+B[0]+C[0]);
    isVisited[0] = true;
    for(int i=0; i<K; ++i){
        auto top = queue.top();
        std::cout << top.second << std::endl;
        auto s = S(top.first);
        queue.pop();
        if(s[0]<X-1){
            auto newS = State{s[0]+1,s[1],s[2]};
            auto newID = ID(newS);
            if(!isVisited[newID]){
                auto value = A[newS[0]] + B[newS[1]] + C[newS[2]];
                queue.emplace(newID,value);
                isVisited[newID] = true;
            }
        }
        if(s[1]<Y-1){
            auto newS = State{s[0],s[1]+1,s[2]};
            auto newID = ID(newS);
            if(!isVisited[newID]){
                auto value = A[newS[0]] + B[newS[1]] + C[newS[2]];
                queue.emplace(newID,value);
                isVisited[newID] = true;
            }
        }
        if(s[2]<Z-1){
            auto newS = State{s[0],s[1],s[2]+1};
            auto newID = ID(newS);
            if(!isVisited[newID]){
                auto value = A[newS[0]] + B[newS[1]] + C[newS[2]];
                queue.emplace(newID,value);
                isVisited[newID] = true;
            }
        }
    }

    return 0;
}


Measured memory_bytes: 131456
n = int(input())
a = [int(input())for i in range(n)]
cnt = {}
for x in a:
    cnt[x] = 0
for x in a:
    if cnt[x] == 0:cnt[x]+=1
    else:cnt[x] -=1
ans = 0
for key in cnt:
    ans += cnt[key] >0
print(ans)

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

using namespace std;
typedef long long int ll;
typedef long double ld;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for (ll i = (ll)(n) - 1; i >= 0; i--)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF (1LL << 62)

#define PI (acos(-1))
#define print(x) cout << x << endl
 
ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll countDigit(ll n) { return floor(log10(n) + 1); } 
typedef pair <ll,ll> P;
static const ll dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};

template <typename T> 
ostream& operator<<(ostream& os, const vector<T>& v) 
{ 
    for (int i = 0; i < (int)v.size(); ++i) { 
        os << v[i]; 
        if (i != (int)v.size() - 1) 
            os << " "; 
    } 
    return os; 
} 

ll nCrModp(ll n, ll r, ll p)
{
    ll C[r+1];
    memset(C, 0, sizeof(C));

    C[0] = 1;

    for (ll i = 1; i <= n; i++)
    {
        for (ll j = min(i, r); j > 0; j--)
            C[j] = (C[j] + C[j-1])%p;
    }
    return C[r];
}

int main()
{
    ll N;
    cin >> N;
    vector<P> p(N);
    rep(i, N) {
        ll a, b; 
        cin >> a >> b;
        p[i] = P(a+b, a-b);
    }
    sort(all(p));

    ll cur = -MOD;
    ll cnt = 0;
    rep(i, N) {
        if (cur <= p[i].second) {
            cnt++;
            cur = p[i].first;
        }
    }
    print(cnt);
    return 0;
}

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

int main() {
    int N;
    cin >> N;
    bool res = false;
    for (int a = 0; a <= 100; ++a) {
        for (int b = 0; b <= 100; ++b) {
            int total = 4 * a + 7 * b;
            if (total == N) {
                cout << "Yes";
                res = true;
                break;
            }
        }
        if (res) break;
    }
    if (!res) cout << "No";
}


Measured memory_bytes: 256
N,A,B = map(int,input().split())

if A==B :
    if N == 1 :
        ans = "Borys"
    else :
        ans = "Alice"
else :
    if (B-A)% 2 == 0 :
        ans = "Alice"
    else :
        ans = "Borys"
print(ans)


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

int main() {
	int n;
	cin >> n;
	vector<int> V(n);
	for (int i = 0; i < n; i++) {
		cin >> V[i];
	}
	int sum = 0;
	int minj;
	for (int i = 0; i < n - 1; i++) {
		minj = i;
		for (int j = i ; j < n; j++) {
			if (V[j] < V[minj]) {
				minj = j;
			}				
		}
		if (i != minj) {
			swap(V[i], V[minj]);
			sum++;
		}	
	}
	for (int i = 0; i < n; i++) {
		cout << V[i];
		if (i == n - 1)
			cout << endl;
		else
			cout << " ";
	}
	cout << sum << endl;
}


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

int main() {
  int N,M;
  cin>>N>>M;
  vector<int> A(N);
  int sum,cnt;
  sum=0;cnt=0;
  for(int i=0;i<N;i++){
    cin>>A.at(i);
    sum+=A.at(i);
  }
  for(int i=0;i<N;i++){
    if(A.at(i)>=((sum+4*M-1)/4/M))cnt++;
  }
  if(cnt>=M)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <sstream>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cmath>
 
using namespace std;

int matrix[8][8];

int factorial(int n){
	if(n == 0) return 1;
	return n*(factorial(n-1));
}

void init(){
	for(int i = 0 ; i < 8; i++){
		for(int j = 0 ; j < 8; j ++){
			matrix[i][j] = 0;
		}
	}
}

int main()
{
	init();
	int N,M;
	cin>>N>>M;
	vector<int> intVec;
	for(int i = 0; i < M; i++){
		int a,b;
		cin>>a>>b;
		a--;
		b--;
		matrix[a][b] = 1;
		matrix[b][a] = 1;
	}

	int count = 0;
	for(int i = 0; i < N; i++){
		intVec.push_back(i);
	}
	int index = 0;
	do{
		for(int i = 0;i < N-1; i++){
			if( matrix[intVec[i]][intVec[i+1]] != 1){
				break;
			}else if(i == N-2){
				count++;
			}
		}
		index++;
		next_permutation(intVec.begin(),intVec.end());
	}while(index < factorial(N-1));
	cout<<count<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Solver {
    public void Solve() {
        int k = sc.nextInt();
        if (k < 10) {
            System.out.println(k);
            return;
        }
        // i: 桁数, j: 最初の数字
        long dp[][] = new long[50][10];
        for (int i = 0; i < 10; i++) {
            dp[1][i] = 1;
        }
        long cnt = 9;
        for (int i = 2; i < 50; i++) {
            for (int j = 0; j < 10; j++) {
                if (j == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j + 1];
                } else if (j == 9) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + dp[i - 1][j + 1];
                }
                if (j == 0) {
                    continue;
                }
                cnt += dp[i][j];
                if (cnt >= k) {
                    // 桁数i最初がj
                    // System.out.println(i);
                    // System.out.println(j);
                    // System.out.println(cnt);
                    // amsは答え
                    int ans[] = new int[i];
                    ans[0] = j;

                    long anscnt = cnt - dp[i][j];
                    int num = j;
                    for (int l = i - 1; l >= 1; l--) {
                        for (int l2 = Math.max(0, num - 1); l2 < Math.min(10, num + 2); l2++) {
                            if (anscnt + dp[l][l2] < k) {
                                anscnt += dp[l][l2];
                            } else {
                                ans[i - l] = l2;
                                num = l2;
                                // System.out.println(l2);
                                // System.out.println(anscnt);
                                break;
                            }
                        }
                    }
                    for (int l = 0; l < ans.length; l++) {
                        System.out.print(ans[l]);
                    }
                    System.out.println();
                    return;

                }
            }
        }
    }

    Scanner sc;

    Solver(Scanner in) {
        this.sc = in;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Solver s = new Solver(sc);
        s.Solve();
        sc.close();
    }
}


Measured memory_bytes: 21844
public class Main {

  private static void solve() {
    int n = ni();
    int a = ni();
    int b = ni();
    
    System.out.println(Math.min(n*a, b));

  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}



Measured memory_bytes: 21588
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 300 + 5;
int n;
char s[maxn][maxn];

bool judge(int x){
    for(int i = 0; i <  n; i++)
        for(int j = x + i + 1; j < x + n; j++)
            if(s[i%n][j%n] != s[(j-x)%n][(x+i)%n]) return false;
    return true;
}

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) scanf("%s", s[i]);
    int cnt = 0;
    for(int i = 0; i < n; i++)
        if(judge(i)) cnt += n;
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 384
int main(void){int ans, num[15][15], w, h, i, j, map[15][15];while (1){scanf("%d%d", &w, &h);if (w + h == 0){break;}memset(map, -1, sizeof(map));for (i = 0; i < h; i++){for (j = 0; j < w; j++){scanf("%d", &map[i][j]);}}memset(num, 0, sizeof(num));for (i = 0; i < w; i++){if (map[0][i] != 1){num[0][i] = 1;}}for (i = 1; i < h; i++){for (j = 0; j < w; j++){if (j > 0 && map[i - 1][j - 1] == 0 && map[i][j] != 2){num[i][j] += num[i - 1][j - 1];}if (map[i - 1][j] == 0){num[i][j] += num[i - 1][j];}if (j < w - 1 && map[i - 1][j + 1] == 0 && map[i][j] != 2){num[i][j] += num[i - 1][j + 1];}if (i > 1 && map[i - 2][j] == 2){num[i][j] += num[i - 2][j];}}}ans = 0;for (j = 0; j < w; j++){if (map[h - 1][j] != 1){ans += num[h - 1][j];}if (h > 1 && map[h - 2][j] == 2){ans += num[h - 2][j];}}printf("%d\n", ans);}return (0);}

Measured memory_bytes: 0
import sys
s = input()
t = input()

if (t in s):
    print(0)
    sys.exit()

ans = 1000
for i in range(len(s)-len(t)+1):
    diff = 0
    for j in range(len(t)):
        if (s[i+j] == t[j]):
            pass
        else:
            diff += 1
    
    ans = min(ans, diff)

print(ans)


Measured memory_bytes: 9056
import java.util.*;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc = new Scanner (System.in);


		//トッピングの種類の数・生地の値段・トッピングの値段・生地のカロリーを入力
		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();

		//トッピングのカロリー用配列
		int [] d = new int [n];

		//ループ・ソート用
		int i, j;
		int temp;

		//カロリー計算・カロリーの最大値用
		int calorie;
		int max = 0;

		//トッピングのカロリーを入力
		for (i = 0; i < n; i++) {
			d[i] = sc.nextInt();
		}

		//トッピングのカロリーを降順にソート
		for (i = 0; i < n - 1; i++) {
			for (j = i + 1; j < n; j++) {
				if (d[i] < d[j]) {
					temp = d[i];
					d[i] = d[j];
					d[j] = temp;
				}
			}
		}

		//「最高のピザ」を求めて出力
		if (n == 0) {
			System.out.println(a);
		} else {
			for (i = 0; i < n; i++) {
				int sum = c;
				for (j = 0; j < i; j++) {
					sum += d[j];
					calorie = (int) (sum / (a + i * b));
					if (max < calorie) {
						max = calorie;
					}
				}
			}
			System.out.println(max);
		}

	}

}

Measured memory_bytes: 18148
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <cstdio>
using namespace std;
int main()
{
	int a,b,c,q=0;
	int x[20];
	int s=1;
	cin>>a>>b;
	if(a<=0&&b>=0)
	cout<<"Zero"<<endl;
	if(a>0&&b>0)
	cout<<"Positive"<<endl;
	if(a<0&&b<0)
	{
		for(int i=a;i<=b;i++)
		{
			if(i<=b) q++;
		}
		if(q%2==0)
		cout<<"Positive"<<endl;
		 else cout<<"Negative"<<endl;
		
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    if (n % 2 != 0) {
        cout << "No";
        return 0;
    }
    char s[n];
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        if (i >= n / 2 && s[i - n / 2] != s[i]) {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
}

Measured memory_bytes: 256
N, K, Q = map(int, input().split())
win_count = [0 for _ in range(N)]
for _ in range(Q):
    win_count[int(input()) - 1] += 1
for i in range(N):
    if K - (Q - win_count[i]) > 0:
        print('Yes')
    else:
        print('No')


Measured memory_bytes: 9896
#include <iostream>
#include <algorithm>
#include <sstream>
#include <cstdio>
#include <vector>
using namespace std;

bool fizzBuzzCheck(int n,string s){
    if(n%15==0)return (s == "FizzBuzz");
    if(n%3==0)return  (s == "Fizz");
    if(n%5==0)return  (s == "Buzz");
    
    for(int i=0;i<s.length();i++) if(s[i]<'0'||s[i]>'9')return false;
    
    return (atoi(s.c_str()) == n);
}

int main(){
    int n,m;
    string s;
    
    while(scanf("%d %d\n",&m,&n), m){
        
        vector<int> rem(m);
        for(int i=0;i<m;i++){
            rem[i] = i+1;
        }
        int c = 0;
        for(int i=1;i<=n;i++){
            getline(cin,s);
            if(rem.size() == 1)continue;
            if( !fizzBuzzCheck(i,s) ){
                rem.erase(remove(rem.begin(),rem.end(),rem[c]),rem.end());
            }else{
                c++;
            }
            c %= rem.size();
        }
        for(int i=0;i<rem.size();i++){
            cout << (i?" ":"") << rem[i];
        }
        cout << endl;
    }
}

Measured memory_bytes: 1256
import os
import heapq
import sys
import math
import operator
from collections import defaultdict
from io import BytesIO, IOBase


"""def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)"""

"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""



def inpt():
    return [int(k) for k in input().split()]


def main():
    n=int(input())
    s=list(input())
    ct=0
    i=0
    j=n-1
    while(i<=j):
        if(s[i]=='W'):
            while(i<j and s[j]=='W'):
                j-=1
            if(i==j):
                break
            ct+=1
            s[i],s[j]=s[j],s[i]
        i+=1
    for i in range(1,n):
        if(s[i-1]=='W' and s[i]=='R'):
            ct+=1
    print(ct)

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()


Measured memory_bytes: 79192
(defun split (string &key (delimiterp #'(lambda (c) (char= c #\Space))))
  (loop :for beg = (position-if-not delimiterp string)
        :then (position-if-not delimiterp string :start (1+ end))
        :for end = (and beg (position-if delimiterp string :start beg))
        :when beg :collect (subseq string beg end)
        :while end))

(destructuring-bind (h w) (mapcar #'parse-integer (split (read-line)))
  (loop :for i :from 1 :to (+ w 2) :do (format t "#"))
  (format t "~%")
  (loop :for i :from 1 :to h
        :for line = (read-line t nil nil)        
        :do (format t "#~a#~%" line))
  (loop :for i :from 1 :to (+ w 2) :do (format t "#"))
  (format t "~%"))


Measured memory_bytes: 15844
import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		int X = sc.nextInt();
		int Y = sc.nextInt();
		
		int[] xmap = new int[N];
		for (int i = 0; i < N; i++) {
			xmap[i] = sc.nextInt();
		}
		
		int[] ymap = new int[M];
		for (int i = 0; i < M; i++) {
			ymap[i] = sc.nextInt();
		}
		
		Arrays.sort(xmap);
		Arrays.sort(ymap);
		
		int xlast = xmap[xmap.length-1];
		int yfrast = ymap[0];
		
		for (int i = xlast+1; i <= yfrast; i++) {
			if (X < i && i <= Y) {
				System.out.println("No War");
				return;
			}
		}
		
		System.out.println("War");
	}
}


Measured memory_bytes: 23252
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)b; i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int n;
    cin >> n;
    set<string> st;
    rep(i, 0, n) {
        string s;
        cin >> s;
        st.insert(s);
    }
    cout << st.size() << endl;
    return 0;
}


Measured memory_bytes: 19268
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

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

    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }

    int k = 0;
    for (;;) {
        int m = 0, l = 0;
        for (int i = 0; i < n; i++) {
            if (m == 0) {
                if (h[i] > 0) m = 1, l = 1, k++;
            }
            if (m == 1) {
                if (h[i] == 0) m = 0; else h[i]--;
            }
        }
        if (l == 0) break;
    }

    cout << k << endl;

    return 0;
}

Measured memory_bytes: 256
n, m = map(int,input().split())
s = [list(map(int,input().split())) for i in range(m)]
nl = [[0,0] for i in range(n+1)]
for a,b in s:
    if a == 1: nl[b][0] = 1
    if b == n: nl[a][1] = 1
ans = "POSSIBLE" if [1,1] in nl else "IMPOSSIBLE"
print(ans)

Measured memory_bytes: 102296
# Stable Sort

length = int(input())
cards = input().rstrip().split()
cards1 = [card for card in cards]
cards2 = [card for card in cards]

def value(n):
    number = n[1:]
    return int(number)

def char(cards):
    charSets = [[] for i in range(10)]
    for i in range(length):
        char = cards[i][:1]
        val = value(cards[i])
        # print('絵柄: ' + char + ', 数字: ' + str(val))
        charSets[val].append(char)
    return charSets

def bubble(cards):
    for i in range(length):
        j = length - 1
        while j > i:
            if value(cards[j]) < value(cards[j - 1]):
                cards[j], cards[j - 1] = cards[j - 1], cards[j]
            j -= 1
    return cards

def selection(cards):
    # count = 0
    for i in range(length):
        minj = i
        for j in range(i, length):
            if value(cards[j]) < value(cards[minj]):
                minj = j
        #if minj != i:
            # count += 1
        cards[i], cards[minj] = cards[minj], cards[i]
    return cards

def stable(cards1, cards2):
    if char(cards1) == char(cards2):
        return 'Stable'
    else:
        return 'Not stable'

c = cards
b = bubble(cards1)
s = selection(cards2)

print(' '.join(b))
print(stable(c, b))
print(' '.join(s))
print(stable(c, s))



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

using namespace std;

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

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

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

int main() {
    int flip = 0;
    string s;
    cin >> s;
    deque<char> Q(s.begin(), s.end());
    int n;
    cin >> n;
    for(int i = 0 ; i < n ; i++){
        int T;
        cin >> T;
        if(T==1){
            flip ^= 1;
        }else{
            int x;
            cin >> x;
            --x;
            char c;
            cin >> c;
            if(flip ^ x ){
                Q.push_back(c);
            }else{
                Q.push_front(c);
            }
        }
    }
    if(flip){
        reverse(Q.begin(), Q.end());
    }
    for( auto i : Q ){
        cout << i;
    }
    cout << endl;

    // Failed to predict input format
    return 0;
}


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


def main():
    K, N = map(int, input().split())
    A = list(map(int, input().split()))

    result = A[-1] - A[0]
    for i in range(1, N):
        result = min(K - A[i] + A[i - 1], result)
    print(result)


if __name__ == "__main__":
    main()


Measured memory_bytes: 25840