C - Hamiltonian Pieces
Source: atcoder
Difficulty: 600

Problem Statement
There is a board with
10^9
rows and
10^9
columns, and
R
red pieces and
B
blue pieces. Here,
R+B
is not less than
2
. The square at the
r
-th row from the top and the
c
-th column from the left is called square
(r,c)
. A red piece can move vertically or horizontally by one square in one move, and a blue piece can move diagonally by one square in one move. More precisely, a red piece on square
(r,c)
can move to
(r+1,c), (r,c+1), (r-1,c), (r,c-1)
in one move if the destination square exists, and a blue piece on square
(r,c)
can move to
(r+1,c+1), (r+1,c-1), (r-1,c+1), (r-1,c-1)
in one move if the destination square exists.
We want to place all
(R+B)
pieces on the board in any order, one by one, subject to the following conditions:
At most one piece is placed on a single square.
For each
i
(1 \leq i \leq R+B-1)
, the
i
-th piece placed can move in one move to the square containing the
(i+1)
-th piece placed.
The
(R+B)
-th piece placed can move in one move to the square containing the
1
-st piece placed.
Determine whether there is a way to place the
(R+B)
pieces satisfying these conditions. If it exists, show one example.
You are given
T
test cases; solve each of them.
Constraints
1\leq T\leq 10^5
0 \leq R, B
2 \leq R + B \leq 2 \times 10^5
The sum of
(R+B)
over all test cases is at most
2\times 10^5
.
All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each case is given in the following format:
R
B
Output
Print the answer for each test case in order, separated by newlines.
If there is no way to place the pieces satisfying the conditions for a test case, print
No
.
Otherwise, print such a placement in the following format:
Yes
p_1
r_1
c_1
\vdots
p_{R+B}
r_{R+B}
c_{R+B}
Here,
p_i
is
R
if the
i
-th piece placed is red, and
B
if it is blue.
r_i
and
c_i
are integers between
1
and
10^9
(inclusive), indicating that the
i
-th piece is placed on square
(r_i,c_i)
.
Sample Input 1
3
2 3
1 1
4 0
Sample Output 1
Yes
B 2 3
R 3 2 
B 2 2
B 3 3
R 2 4
No
Yes
R 1 1
R 1 2
R 2 2
R 2 1
For the 1st test case, if we extract the top-left
4\times 5
squares of the board, the placement of the pieces is as follows:
.....
.BBR.
.RB..
.....
Here,
R
indicates a red piece on that square,
B
indicates a blue piece on that square, and
.
indicates an empty square.
For the 2nd test case, there is no placement of the pieces that satisfies the conditions.

C++ solution:
#include<bits/stdc++.h>
using namespace std;
namespace FastIO {
    constexpr int LEN = 1 << 20;
    char in[LEN + 1], out[LEN + 1];
    char *pin = in, *pout = out, *ein = in, *eout = out + LEN;

    char gc() { return pin == ein && (ein = (pin = in) + fread(in, 1, LEN, stdin), ein == in) ? EOF : *pin ++; }
    void pc(char c) { pout == eout && (fwrite(out, 1, LEN, stdout), pout = out); (*pout ++) = c; return; }
    struct Flush { ~Flush() { fwrite(out, 1, pout - out, stdout); pout = out; return; } } _flush;

    template<typename T> T Read() {
        T x = 0; int f = 1; char ch = gc();
        while (ch < '0' || ch > '9') f = (ch == '-' ? (~f + 1) : f), ch = gc();
        while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
        return x * f;
    }
    void Read(char *s) {
        char ch = gc();
        while (ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t') ch = gc();
        while ((ch != EOF) && !(ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t')) *s = ch, s ++, ch = gc();
        *s = '\0'; return;
    }
    template<typename T> void Read(T &x) { x = Read<T>(); return; }
    template<typename T, typename ...Args>
    void Read(T &x, Args &...args) { Read(x), Read(args...); return; }
    template<typename T> void Write(T x) {
        static char stk[40]; int tp = 0;
        if (x < 0) pc('-'), x = ~x + 1;
        do stk[tp++] = x % 10 + 48, x /= 10; while (x);
        while (tp --) pc(stk[tp]);
        return;
    }
    void Write(char ch) { pc(ch); return; }
    void Write(const char *s) {
        while (*s != '\0') pc(*s), s++;
        return;
    }
    void Puts(const char *s) {
        Write(s), pc('\n'); return;
    }
    template<typename T, typename ...Args>
    void Write(T x, Args ...args) { Write(x), Write(args...); return; }
}

using namespace FastIO;

void solve(int r, int b) {
    int k = (b & 1) > 0 ? 0 : 1;
    int rl = (b+3)>>1;
    for (int i = 1; i < rl; i++) {
        Write("B ", i, " ", i + k, "\n");
    }
    if (r > 0) {
        Write("R ", rl, " ", rl + k, "\n");
        for (int i = 1; i <= (r - 2) / 2; i++) {
            Write("R ", rl + i, " ", rl + k, "\n");
        }
        for (int i = (r - 2) / 2; i > 0; i--) {
            Write("R ", rl + i, " ", rl + k - 1, "\n");
        }
        if (k == 1) {
            Write("R ", rl, " ", rl, "\n");
        }
    }
    for (int row = rl; row >= 3 - k; row--) {
        Write("B ", row, " ", row - 1, "\n");
    }
    if (r > 0 && !k) {
        Write("R ", 2, " ", 1, "\n");
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T = Read<int>();
    int r, b;
    while (T--) {
        r = Read<int>();
        b = Read<int>();
        if ((r & 1) || (!r && (b & 1))) {
            Puts("No");
        } else {
            Puts("Yes");
            solve(r, b);
        }
    }
}

Go solution:
package main

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

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	scanner.Scan()
	T, _ := strconv.Atoi(scanner.Text())

	for t := 0; t < T; t++ {
		scanner.Scan()
		R, _ := strconv.Atoi(scanner.Text())
		scanner.Scan()
		B, _ := strconv.Atoi(scanner.Text())

		if R%2 == 1 {
			fmt.Println("No")
			continue
		}
		if R == 0 && B%2 == 1 {
			fmt.Println("No")
			continue
		}

		fmt.Println("Yes")

		// Handle red pieces
		for i := R / 2; i >= 1; i-- {
			fmt.Printf("R 3 %d\n", i)
		}
		for i := 1; i <= R/2; i++ {
			fmt.Printf("R 2 %d\n", i)
		}

		if B == 0 {
			continue
		}

		if R == 0 {
			// If no red pieces, place blue pieces in a loop
			for i := 1; i <= B; i++ {
				fmt.Printf("B %d %d\n", i, i)
			}
			continue
		}

		// Integrate blue pieces with red pieces
		// Start placing blue pieces from (1, R/2)
		i := 1
		j := R / 2
		for b := 1; b <= B; b++ {
			fmt.Printf("B %d %d\n", i, j)
			if b%2 == 1 {
				i++
				j++
			} else {
				i--
				j--
			}
		}
	}
}

Java solution:
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.HashMap;
import java.util.NoSuchElementException;

public class Main implements Runnable { // Runnableを実装する
	public static void main(String[] args) {
		new Thread(null, new Main(), "", Runtime.getRuntime().maxMemory()).start(); // 16MBスタックを確保して実行
	}
	
	final static long mod=998244353;
	int MAX=10000;
	long[] fac=new long[MAX];
	long[] ifac=new long[MAX];
	long[] inv=new long[MAX];
	{
		Arrays.fill(fac, 1);
		Arrays.fill(ifac, 1);
		Arrays.fill(inv, 1);
		for (int i=2;i<MAX;++i) {
			fac[i]=i*fac[i-1]%mod;
			inv[i]=mod-(mod/i)*inv[(int)(mod%i)]%mod;
			ifac[i]=inv[i]*ifac[i-1]%mod;
		}
	}
	
	static long pow(long a, long n) {
		if (n==0) return 1;
		return pow(a*a%mod,n/2)*(n%2==1?a:1)%mod;
	}
	
	static long inv(long a) {
		return pow(a,mod-2);
	}
	
	long comb(int n, int k) {
		if (k<0||n-k<0)return 0;
		return fac[n]*ifac[n-k]%mod*ifac[k]%mod;
	}
	
	
	public void run() {
		FastScanner sc = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);
		
		int T=sc.nextInt();
		for(int t=0;t<T;++t) {
			int R=sc.nextInt();
			int B=sc.nextInt();
		
		
			if(R%2==1) {
				pw.println("No");
			} else if (R==0) {
				if (B%2==1) {
					pw.println("No");
				} else {
					pw.println("Yes");
					int x=100;
					int y=100;
					for(int i=0;i<B/2-1;++i) {
						pw.println("B "+x+" "+y);
						++x;++y;
					}
					pw.println("B "+x+" "+y);
					--x;
					++y;
					for(int i=0;i<B/2-1;++i) {
						pw.println("B "+x+" "+y);
						--x;--y;
					}
					pw.println("B "+x+" "+y);
					++x;
					--y;					
				}
			} else {
				pw.println("Yes");
				int m=R/2;
				if(B%2==0) {
					int x=1;
					int y=1;
					for(int i=0;i<m-1;++i) {
						pw.println("R " + x + " " + y);
						++x;
					}
					for(int i=0;i<B/2;++i) {
						pw.println("B " + x + " " + y);
						++x;
						++y;
					}
					pw.println("R " + x + " " + y);
					++y;
					for(int i=0;i<m-1;++i) {
						pw.println("R " + x + " " + y);
						--x;
					}
					for(int i=0;i<B/2;++i) {
						pw.println("B " + x + " " + y);
						--x;
						--y;
					}
					pw.println("R " + x + " " + y);
					--y;		
				} else { 
					int x=1;
					int y=1;
					for(int i=0;i<m-1;++i) {
						pw.println("R " + x + " " + y);
						++x;
					}
					for(int i=0;i<(B+1)/2;++i) {
						pw.println("B " + x + " " + y);
						++x;
						++y;
					}
					for(int i=0;i<m;++i) {
						pw.println("R " + x + " " + y);
						--x;
					}
					for(int i=0;i<B/2;++i) {
						pw.println("B " + x + " " + y);
						--x;
						--y;
					}
					pw.println("R " + x + " " + y);
					--y;
				}
				
				
				
				
			}
		
		
		}
		
		
		pw.close();
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}

	private int readByte() {
		if (hasNextByte())
			return buffer[ptr++];
		else
			return -1;
	}

	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}

	private void skipUnprintable() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr]))
			ptr++;
	}

	public boolean hasNext() {
		skipUnprintable();
		return hasNextByte();
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}

	public long nextLong() {
		if (!hasNext())
			throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}

	public int nextInt() {
		return (int) nextLong();
	}
}

JavaScript solution:
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextssort(n,a){return a?cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>b-a):cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>a-b);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}
var streams=[];function print(s){streams.push(s);}

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));
if(streams.length)console.log(streams.join("\n"));

function main(){
  var q = next();
  while(q--)solve();
}

function solve(){
  var [r,b] = nexts(2);
  if(r & 1)return print("No");
  if(r === 0 && b % 2 === 1)return print("No");
  print("Yes");
  var x = 500000, y = 500000;
  for(var i = 0; i < b/2; i++){
    print("B " + y + " " + x);
    y++; x++;
  }
  y -= 2;
  for(var i = 0; i < b >> 1; i++){
    print("B " + y + " " + x);
    y--; x--;
  }
  if(r > 0){
    if(b === 0)x = 500000, y = 500000;
    print("R " + y + " " + x);
    y = 499999, x = 500000;
    print("R " + y + " " + x);
    r -= 2;
  }
  for(var i = 0; i < r/2; i++){
    x--;
    print("R " + y + " " + x);
  }
  y++;
  for(var i = 0; i < r/2; i++){
    print("R " + y + " " + x);
    x++;
  }
}

Python solution:
import os
import sys
from io import BytesIO, IOBase

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")

def solve(r,b):
	x=10**6
	y=10**6
	if r==0:
		if b%2==1:
			print("No")
			return
		print("Yes")
		for i in range(b//2):
			print('B',x,y)
			if i<b//2-1:
				x+=1
				y+=1
			else:
				x+=1
				y-=1
		for i in range(b//2):
			print('B',x,y)
			x-=1
			y-=1
		return
	
	if r%2==1:
		print("No")
		return

	print("Yes")			
	if b==0:
		for i in range(r//2):
			print('R',x,y)
			if i<r//2-1:
				x+=1
			else:
				y+=1
		
		for i in range(r//2):
			print('R',x,y)
			x-=1

		return;

	r-=2
	print('R',x,y)
	y+=1

	for i in range(r//2):
		print('R',x,y)
		x+=1


	for i in range(b//2):
		print('B',x,y)
		if i%2==0:
			x+=1
			y+=1
		else:
			x+=1
			y-=1
	
	if b%2==0:
		print('R',x,y)
		y-=1
	else:
		print('B',x,y)
		x+=1
		y-=1
		print('R',x,y)
		x-=1

	for i in range(b//2-1,-1,-1):
		print('B',x,y)
		if i==(b//2)-1 and y==10**6+1:
			y-=1
			x-=1
		elif i%2==0:
			x-=1
			y+=1
		else:
			x-=1
			y-=1

	for i in range(r//2):
		print('R',x,y)
		x-=1



		

t=int(input())
for _ in range(t):
	r,b=map(int,input().split())
	solve(r,b)

Ruby solution:
t = gets.to_i
ans = []
t.times do
  r,b = gets.split.map(&:to_i)
  i = 10**6
  j = 10**6
  if r%2 == 1
    ans << "No"
  elsif r == 0
    if b%2 == 1
      ans << "No"
    else
      ans << "Yes"
      ans << "B #{i} #{j}"
      ((b/2)-1).times do
        i += 1
        j += 1
        ans << "B #{i} #{j}"
      end
      i += 1
      j -= 1
      ans << "B #{i} #{j}"
      ((b/2)-1).times do
        i -= 1
        j -= 1
        ans << "B #{i} #{j}"
      end
    end
  else
    ans << "Yes"
    ans << "R #{i} #{j}"
    ((r/2)-1).times do
      i -= 1
      ans << "R #{i} #{j}"
    end
    j -= 1
    ans << "R #{i} #{j}"
    ((r/2)-1).times do
      i += 1
      ans << "R #{i} #{j}"
    end
    if b > 1
      if b%2 == 0
        j -= 1
        ans << "B #{i} #{j}"
        (b/2).times do
          i += 1
          j += 1
          ans << "B #{i} #{j}"
        end
        if b > 2
          i -= 1
          j += 1
          ans << "B #{i} #{j}"
          ((b/2)-2).times do
            i -= 1
            j -= 1
            ans << "B #{i} #{j}"
          end
        end
      else
        i += 1
        ans << "B #{i} #{j}"
        (b/2).times do
          i += 1
          j += 1
          ans << "B #{i} #{j}"
        end
        if b > 1
          i -= 1
          j += 1
          ans << "B #{i} #{j}"
          ((b/2)-1).times do
            i -= 1
            j -= 1
            ans << "B #{i} #{j}"
          end
        end
      end
    elsif b == 1
      i += 1
      ans << "B #{i} #{j}"
    end
  end
end
puts ans