# Phoenix and Gold solution codeforces – Phoenix has collected nn pieces of gold 2021

## Phoenix and Gold solution codeforces

Phoenix and Gold solution codeforces  Phoenix and Gold solution codeforces  Phoenix and Gold solution codeforces

Phoenix has collected nn pieces of gold, and he wants to weigh them together so he can feel rich. The ii-th piece of gold has weight wiwi. All weights are distinct. He will put his nn pieces of gold on a weight scale, one piece at a time.

The scale has an unusual defect: if the total weight on it is exactly xx, it will explode. Can he put all nn gold pieces onto the scale in some order, without the scale exploding during the process? If so, help him find some possible order.

Formally, rearrange the array ww so that for each ii (1in)(1≤i≤n)j=1iwjx∑j=1iwj≠x.

Input Phoenix and Gold solution codeforces

The input consists of multiple test cases. The first line contains an integer tt (1t10001≤t≤1000) — the number of test cases.

The first line of each test case contains two integers nn and xx (1n1001≤n≤1001x1041≤x≤104) — the number of gold pieces that Phoenix has and the weight to avoid, respectively.

The second line of each test case contains nn space-separated integers (1wi100)(1≤wi≤100) — the weights of the gold pieces. It is guaranteed that the weights are pairwise distinct.

Output Phoenix and Gold solution codeforces

For each test case, if Phoenix cannot place all nn pieces without the scale exploding, print NO. Otherwise, print YES followed by the rearranged array ww. If there are multiple solutions, print any.

Example Phoenix and Gold solution codeforces
Phoenix and Gold solution codeforces  Phoenix and Gold solution codeforces  Phoenix and Gold solution codeforces

input

Copy
3
3 2
3 2 1
5 3
1 2 3 4 8
1 5
5


output

Copy
YES
3 2 1
YES
8 1 2 3 4
NO

Phoenix and Gold solution codeforces  Phoenix and Gold solution codeforces  Phoenix and Gold solution codeforces
Note

In the first test case, Phoenix puts the gold piece with weight 33 on the scale first, then the piece with weight 22, and finally the piece with weight 11. The total weight on the scale is 33, then 55, then 66. The scale does not explode because the total weight on the scale is never 22.

In the second test case, the total weight on the scale is 889911111414, then 1818. It is never 33.

In the third test case, Phoenix must put the gold piece with weight 55 on the scale, and the scale will always explode.

Phoenix and Gold solution codeforces  Phoenix and Gold solution codeforces  Phoenix and Gold solution codeforces

## Python Phoenix and Gold solution codeforces  Phoenix and Gold solution codeforces  Phoenix and Gold solution codeforces

R=lambda:map(int,input().split())
t,=R()
while t:
t-=1;n,x=R();a=[*R()];i=s=0;f=1
while(i<n)&(s<x):s+=a[i];i+=1
if s==x and(f:=i<n):a[i-1],a[i]=a[i],a[i-1]
print(*(['NO'],['YES']+a)[f])

# C++

Phoenix and Gold solution codeforces  Phoenix and Gold solution codeforces  Phoenix and Gold solution codeforces

#include<bits/stdc++.h>
using namespace std;
int T,n,x,w[105];
int main()
{
cin>>T;
while(T--)
{
cin>>n>>x;int cnt=0;
for(int i=1;i<=n;++i)cin>>w[i],cnt+=w[i];
puts(cnt==x?"NO":"YES");
if(cnt==x)continue;
for(int i=1;i<=n;++i)
{
if(x==w[i])swap(w[i],w[i+1]);
cout<<w[i]<<' ';x-=w[i];
}
puts("");
}
}

## RUBY

Phoenix and Gold solution codeforces  Phoenix and Gold solution codeforces  Phoenix and Gold solution codeforces

def read
gets.split.map &:to_i
end
gets.to_i.times do
if w.sum == x
puts "NO"
else
puts "YES"
n.times do |i|
w[i], w[i + 1] = w[i + 1], w[i] if w[i] == x
print w[i], " "
x -= w[i]
end
puts
end
end

## JAVA

Phoenix and Gold solution codeforces  Phoenix and Gold solution codeforces  Phoenix and Gold solution codeforces

import java.io.*;
import java.util.*;

public class TimePass {
InputStream is;
PrintWriter out;
String INPUT = "";
//boolean codechef=true;
// String prodKey = "Av#/lL{OyEKiLR+/Ce%(w]^J65;XZe8FVb]]<931_=80E[BVnU^@4xu*J%KG3,CRqIZrUN~JJ+*6QC*CyBd>'\$;>O"onO.bQ%{L}";
boolean codechef=true;

void solve()
{
int t=ni();
while(t-->0) {
int n=ni(),x=ni();
int[] w=na(n);
int sum=0;
int ch=1;
for(int i=0;i<n;i++){
sum += w[i];
if (sum == x) {
int f=0;
for(int j=i+1;j<n;j++) {
if (w[i] != w[j]) {
int temp = w[i];
w[i]=w[j];
w[j]=temp;
f=1;
break;
}
}
ch=f;
break;
}
}
if (ch==0) {
out.println("NO");
continue;
} else {
out.println("YES");
for(int i:w) {
out.print(i+" ");
}
out.println();
}
}
}

static int comp(int a,int b){
return a+1097*b;
}

static long printNcR(int n, int r)
{

// p holds the value of n*(n-1)*(n-2)...,
// k holds the value of r*(r-1)...
long p = 1, k = 1;

// C(n, r) == C(n, n-r),
// choosing the smaller value
if (n - r < r) {
r = n - r;
}

if (r != 0) {
while (r > 0) {
p *= n;
k *= r;

// gcd of p, k
long m = __gcd(p, k);

// dividing by gcd, to simplify
// product division by their gcd
// saves from the overflow
p /= m;
k /= m;

n--;
r--;
}

// k should be simplified to 1
// as C(n, r) is a natural number
// (denominator should be 1 ) .
}
else {
p = 1;
}

// if our approach is correct p = ans and k =1
return p;
}

static long __gcd(long n1, long n2)
{
long gcd = 1;

for (int i = 1; i <= n1 && i <= n2; ++i) {
// Checks if i is factor of both integers
if (n1 % i == 0 && n2 % i == 0) {
gcd = i;
}
}
return gcd;
}
static long[][] dp;

static long desc(int[] a,int l,int r) {
if (l==r) return 0;
if (dp[l][r]!=-1) return dp[l][r];
dp[l][r] = a[r]-a[l] + Math.min(desc(a,l+1,r),desc(a,l,r-1));
return dp[l][r];
}

static int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}

// A function to do counting sort of arr[] according to
// the digit represented by exp.
static void countSort(int arr[], int n, int exp)
{
int output[] = new int[n]; // output array
int i;
int count[] = new int[10];
Arrays.fill(count, 0);

// Store count of occurrences in count[]
for (i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;

// Change count[i] so that count[i] now contains
// actual position of this digit in output[]
for (i = 1; i < 10; i++)
count[i] += count[i - 1];

// Build the output array
for (i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}

// Copy the output array to arr[], so that arr[] now
// contains sorted numbers according to curent digit
for (i = 0; i < n; i++)
arr[i] = output[i];
}

// The main function to that sorts arr[] of size n using
static void radixsort(int arr[], int n)
{
// Find the maximum number to know number of digits
int m = getMax(arr, n);

// Do counting sort for every digit. Note that
// instead of passing digit number, exp is passed.
// exp is 10^i where i is current digit number
for (int exp = 1; m / exp > 0; exp *= 10)
countSort(arr, n, exp);
}

static int MAX=1500;

static int prime[], countdiv[];

static int[] getDivisorsArray() {
int n=20000005;
int[] mind = new int[n];
Arrays.fill(mind, -1);
for(int i=2;i<n;i++){
if (mind[i]==-1){
for(int j=i;j<n;j+=i){
if (mind[j]==-1){
mind[j]=i;
}
}
}
}
// int[] nod = new int[n];
// for(int i=2;i<n;i++){
// int prod = i/mind[i];
// if (mind[i] != mind[prod]) {
// nod[i] = nod[prod] + 1;
// } else {
// nod[i] = nod[prod];
// }
// }
return mind;
}

// Simple sieve to find smallest prime factors of numbers
// smaller than MAX
void SieveOfEratosthenes()
{
for (int i = 2; i * i < MAX; ++i)
{
if (prime[i]==0)
for (int j = i * i; j < MAX; j += i)
prime[j] = i;
}

// Prime number will have same divisor
for (int i = 1; i < MAX; ++i)
if (prime[i]==0)
prime[i] = i;
}

// Returns length of the largest subsequence
// with GCD more than 1.
int largestGCDSubsequence(int arr[], int n)
{
int ans = 0;
for (int i=0; i < n; ++i)
{
int element = arr[i];

// Fetch total unique prime divisor of element
while (element > 1)
{
int div = prime[element];

// Increment count[] of Every unique divisor
// we get till now
++countdiv[div];

// Find maximum frequency of divisor
ans = Math.max(ans, countdiv[div]);

while (element % div==0)
element /= div;
}
}

return ans;
}

static boolean check(int x)
{
char[] a=(""+x).toCharArray();
int s=0;
for(int i=0;i<a.length;i++)
{
s+=a[i]-'0';
s%=3;
}
if(s==0)return true;
return false;
}

static int[][] packD(int n,int[] from,int[] to)
{
int[][] g=new int[n][];
int[] p=new int[n];
for(int f:from)
{
p[f]++;
}
int m=from.length;
for(int i=0;i<n;i++)
{
g[i]=new int[p[i]];
}
for(int i=0;i<m;i++)
{
g[from[i]][--p[from[i]]]=to[i];
}
return g;
}

static class Pair3
{
int a,b,c;
public Pair3(int a,int b,int c)
{
this.a=a;
this.b=b;
this.c=c;
}
}

static class Pair
{
int a,b;
public Pair(int a,int b)
{
this.a=a;
this.b=b;
}
}

static long lcm(long a,long b)
{
long val=a;
val*=b;
return (val/gcd(a,b));
}

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

static int pow(int a, int b, int p)
{
long ans = 1, base = a;
while (b!=0)
{
if ((b & 1)!=0)
{
ans *= base;
ans%= p;
}
base *= base;
base%= p;
b >>= 1;
}
return (int)ans;
}

static int inv(int x, int p)
{
return pow(x, p - 2, p);
}

void run() throws Exception
{
if(codechef)oj=true;
is = oj ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);

long s = System.currentTimeMillis();
solve();
out.flush();
tr(System.currentTimeMillis()-s+"ms");
}

public static void main(String[] args) throws Exception {new TimePass().run();}

private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;

{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}

private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }

private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }

private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
}
return sb.toString();
}

private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
}
return n == p ? buf : Arrays.copyOf(buf, p);
}

private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}

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

private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
}
}

private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
}

while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
}
}

private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
private void tr(Object... o) { if(!oj)System.out.println(Arrays.deepToString(o)); }
}

## MONO  C#

Phoenix and Gold solution codeforces  Phoenix and Gold solution codeforces  Phoenix and Gold solution codeforces

using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;

{
static class Program
{
static TextWriter Writer;
private static Queue<string> _currentLineTokens = new Queue<string>();
public static string ReadToken() { while (_currentLineTokens.Count == 0) _currentLineTokens = new Queue<string>(ReadAndSplitLine()); return _currentLineTokens.Dequeue(); }
public static int[][] ReadIntMatrix(int numberOfRows) { int[][] matrix = new int[numberOfRows][]; for (int i = 0; i < numberOfRows; i++) matrix[i] = ReadIntArray(); return matrix; }
{
int[][] matrix = ReadIntMatrix(numberOfRows); int[][] ret = new int[matrix[0].Length][];
for (int i = 0; i < ret.Length; i++) { ret[i] = new int[numberOfRows]; for (int j = 0; j < numberOfRows; j++) ret[i][j] = matrix[j][i]; }
return ret;
}
public static string[] ReadLines(int quantity) { string[] lines = new string[quantity]; for (int i = 0; i < quantity; i++) lines[i] = Reader.ReadLine().Trim(); return lines; }
public static void WriteArray<T>(IEnumerable<T> array) { Writer.WriteLine(string.Join(" ", array)); }
public static void Write(params object[] array) { WriteArray(array); }
public static void WriteLines<T>(IEnumerable<T> array) { foreach (var a in array) Writer.WriteLine(a); }
private class SDictionary<TKey, TValue> : Dictionary<TKey, TValue>
{
public new TValue this[TKey key]
{
get { return ContainsKey(key) ? base[key] : default(TValue); }
set { base[key] = value; }
}
}
private static T[] Init<T>(int size) where T : new() { var ret = new T[size]; for (int i = 0; i < size; i++) ret[i] = new T(); return ret; }
#endregion=

public static bool NextPermutation(List<int> perm)
{
for (int i = perm.Count - 2; i >= 0; i--)
{
if (perm[i] < perm[i + 1])
{
int min = i + 1;
for (int j = min; j < perm.Count; j++)
if (perm[j] > perm[i] && perm[j] < perm[min])
min = j;

var tmp = perm[i];
perm[i] = perm[min];
perm[min] = tmp;
perm.Reverse(i + 1, perm.Count - i - 1);
return true;
}
}

return false;
}

#region SegmentTree

public static long SegmentTreeFunc(long a, long b)
{
return a + b;
}

public static void Build(long[] a, long v, long tl, long tr)
{
if (tl == tr)
t[v] = a[tl];
else
{
long tm = (tl + tr) / 2;
Build(a, v * 2, tl, tm);
Build(a, v * 2 + 1, tm + 1, tr);
t[v] = SegmentTreeFunc(t[v * 2], t[v * 2 + 1]);
}
}

public static long Query(long v, long tl, long tr, long l, long r)
{
if (l > r)
return 0;
if (l == tl && r == tr)
return t[v];

var tm = (tl + tr) / 2;
var res = SegmentTreeFunc(Query(v * 2, tl, tm, l, Math.Min(r, tm)), Query(v * 2 + 1, tm + 1, tr, Math.Max(l, tm + 1), r));
return res;
}

public static long[] t;

#endregion

private static readonly int modulus = 1000000007;
// private static readonly int modulus1 = modulus - 1;

public static long Pow(long a, long b)
{
long y = 1;

while (true)
{
if ((b & 1) != 0)
y = a * y % modulus;
b = b >> 1;
if (b == 0)
return y;
a = a * a % modulus;
}
}

public static long ReversedNumbByPrimeModulo(long a)
{
return Pow(a, modulus - 2);
}

public static long FactByModulo(long a)
{
long ans = 1;

while (a > 0)
{
ans = ans * a % modulus;
a--;
}

return ans;
}

public static long nCkModulo(long n, long k)
{
if (k < n >> 1)
k = n - k;

long ans = 1;
for (long i = n; i > k; i--)
ans = ans * i % modulus;

k = n - k;
var fact = FactByModulo(k);
var revFact = ReversedNumbByPrimeModulo(fact);

ans = ans * revFact % modulus;

return ans;
}

// public static int maxForPrimeCalc = 200000;
// public static List<int> primes = new List<int>(maxForPrimeCalc) {2};
// // public static int[] minPrimeDiv = new int[maxForPrimeCalc + 1];
// public static bool[] isPrime = new bool[maxForPrimeCalc + 1];

// public static void CalcPrimes()
// {
// isPrime[2] = true;
// for (var i = 2; i <= maxForPrimeCalc; i += 2)
// {
// isPrime[i] = false;
// // minPrimeDiv[i] = 2;
// }
// for (var i = 3; i <= maxForPrimeCalc; i += 2)
// {
// isPrime[i] = true;
// }
//
// for (var i = 3; i * i <= maxForPrimeCalc; i += 2)
// {
// if (isPrime[i])
// {
// // minPrimeDiv[i] = i;
// for (var j = i * i; j <= maxForPrimeCalc; j += i)
// {
// if (isPrime[j])
// {
// isPrime[j] = false;
// // minPrimeDiv[j] = i;
// }
// }
// }
// }
// }
//
// public static int[] PrimeDifferentDividersCountHash = new int[maxForPrimeCalc + 1];
//
// private static int PrimeDifferentDividersCount(long numb)
// {
// if (numb == 1)
// return 0;
// if (isPrime[numb])
// return 1;
//
// if (PrimeDifferentDividersCountHash[numb] > 0)
// return PrimeDifferentDividersCountHash[numb];
//
// var divider = minPrimeDiv[numb];
// var prevNumb = numb / divider;
// var ans = PrimeDifferentDividersCount(prevNumb);
//
// if (divider != minPrimeDiv[prevNumb])
// {
// ans += 1;
// }
//
// PrimeDifferentDividersCountHash[numb] = ans;
//
// return ans;
// }

#region Heap

public static void InsertElementInHeap(int value, int[] arr, ref int sizeOfTree)
{
sizeOfTree++;
arr[sizeOfTree] = value;
HeapifyUp(sizeOfTree, arr);
}

public static void HeapifyUp(int cur, int[] arr)
{
while (true)
{
if (cur == 1)
{
return;
}

var parent = cur >> 1;

if (arr[cur] > arr[parent])
{
arr[cur] ^= arr[parent];
arr[parent] ^= arr[cur];
arr[cur] ^= arr[parent];

cur = parent;
continue;
}

break;
}
}

public static int ExtractHeadOfHeap(int[] arr, ref int sizeOfTree)
{
var extractedValue = arr[1];
arr[1] = arr[sizeOfTree];
sizeOfTree--;
HeapifyDown(1, sizeOfTree, arr);
return extractedValue;
}

public static void HeapifyDown(int cur, int sizeOfTree, int[] arr)
{
while (true)
{
var left = cur << 1;
var right = left + 1;
int smallestChild;

if (sizeOfTree < left)
{
return;
}

if (sizeOfTree == left || arr[left] > arr[right])
smallestChild = left;
else
smallestChild = right;

if (arr[cur] < arr[smallestChild])
{
arr[cur] ^= arr[smallestChild];
arr[smallestChild] ^= arr[cur];
arr[cur] ^= arr[smallestChild];

cur = smallestChild;
continue;
}

break;
}
}

#endregion

#region Sorted Set

public class LowerBoundSortedSet<T> : SortedSet<T>
{
private ComparerDecorator<T> _comparerDecorator;
private class ComparerDecorator<T> : IComparer<T>
{
private IComparer<T> _comparer;
public T LowerBound { get; private set; }
public T HigherBound { get; private set; }
private bool _reset = true;
public void Reset()
{
_reset = true;
}
public ComparerDecorator(IComparer<T> comparer)
{
_comparer = comparer;
}
public int Compare(T x, T y)
{
int num = _comparer.Compare(x, y);
if (_reset)
{
LowerBound = y;
}
if (num >= 0)
{
LowerBound = y;
_reset = false;
}
if (num <= 0)
{
HigherBound = y;
_reset = false;
}
return num;
}
}
public LowerBoundSortedSet()
: this(Comparer<T>.Default) {}
public LowerBoundSortedSet(IComparer<T> comparer)
: base(new ComparerDecorator<T>(comparer))
{
_comparerDecorator = (ComparerDecorator<T>) Comparer;
}
public T FindLowerBound(T key)
{
_comparerDecorator.Reset();
this.Contains<T>(key);
return _comparerDecorator.LowerBound;
}
public T FindHigherBound(T key)
{
_comparerDecorator.Reset();
this.Contains<T>(key);
return _comparerDecorator.HigherBound;
}
}

#endregion

static long GCD(long a, long b)
{
while (b > 0) {
a %= b;
a ^= b;
b ^= a;
a ^= b;
}
return a;
}

// private static List<int>[] _divs = new List<int>[100000 + 1];

// private static void CalcDivs()
// {
// for (var i = 0; i < _divs.Length; i++)
// _divs[i] = new List<int>();
//
// for (var i = 1; i < _divs.Length; i++)
// {
// for (var j = i; j < _divs.Length; j += i)
// }
// }

static void Main(string[] args)
{
Writer = new StreamWriter(Console.OpenStandardOutput());

// CalcPrimes();
// CalcDivs();

for (var tmp = 0; tmp < t; tmp++)
{
Solve();
}

Writer.Close();
}

static void Solve()
{

var sum = 0;
for (var i = 0; i < n; i++)
sum += w[i];

if (x > sum)
{
Write("YES");
WriteArray(w);
return;
}

if (x == sum)
{
Write("NO");
return;
}

Array.Sort(w);
var skipped = -1;
var curSum = 0;
for (var i = 0; i < n; i++)
{
if (curSum + w[i] == x)
{
skipped = w[i];
break;
}
else
curSum += w[i];
}

Write("YES");
for (var i = 0; i < n; i++)
{
if (w[i] != skipped)
{
Writer.Write(w[i]);
Writer.Write(" ");
}
}
if (skipped > 0)
Writer.Write(skipped);

Write();
}

public struct MyStruct
{
public int Index;
public int Ans;

public MyStruct(int index, int ans)
{
Index = index;
Ans = ans;
}
}

private static int gcdex (int a, int b, out int x, out int y) {
if (a == 0) {
x = 0; y = 1;
return b;
}
int x1, y1;
int d = gcdex (b%a, a, out x1, out y1);
x = y1 - (b / a) * x1;
y = x1;
return d;
}

private static long GetNumb(Dictionary<char, int> letterDic, List<int> permutation, string s)
{
long res = 0;
long mult = 1;
for (var i = s.Length - 1; i >= 0; i--)
{
res += permutation[letterDic[s[i]]] * mult;

mult *= 10;
}

return res;
}

static void Inc(this Dictionary<long, long> dict, long key, long addedValue)
{
if (dict.ContainsKey(key))
else
}