第34期：IT培训-领先公司的当前问题和挑战

import java.io.*;

class GFG {
	public static void main (String[] args) {
		//code
		GFG gfg = new GFG();
		int testCases, n, i;
		String a;
		char[] c;
		Scanner sc = new Scanner(System.in);
		
		testCases = sc.nextInt();
		
		for(int t = 0; t < testCases; t++)
		{
		    a = sc.next();
		    c = a.toCharArray();
		    i = a.length() - 1;
		    
		    while(i > 0)
		    {
		        if(c[i-1] >= c[i])
		        {
		            i--;
		        }
		        else
		        {
		            break;
		        }
		    }
		    
		    if(i == 0)
		    {
		        System.out.println("not possible");
		    }
		    else
		    {
		        i--;
		        
		    
		        int j = i + 1;
		    
		        for(int k = i + 2; k < a.length(); k++)
		        {
		            if(c[k] > c[i])
		            {
		                j = k;
		            }
		        }
		        
		        char v = c[i];
		        c[i] = c[j];
		        c[j] = v;
		        i++;
		        
		        Arrays.sort(c, i, c.length);
		    
		    
		    
		    for(int k = 0; k < a.length(); k++)
		    {
		        System.out.print(c[k]);
		    }
		    System.out.println();		
		        
		    }
		}
		
	}
}

for _ in range(int(input())):
    n,ar,m=int(input()),list(map(int,input().split())),int(input())
    dp=[0]*(m+1)
    dp[0]=1
    for i in range(n):
        for j in range(ar[i],m+1):
            dp[j]+=dp[j-ar[i]]
    print(dp[m]) 

import java.util.*;
import java.lang.*;
import java.io.*;
class trie
{
  HashMap<Character,trie> child;;
  boolean isEnd;
  trie()
  {
    isEnd=false;
    child=new HashMap<>();
  }
  void add(String a,trie root)
  {
  trie cur=root;
  for (int i=0;i<a.length() ;++i ) {
    if(cur.child.containsKey(a.charAt(i)))
    cur=cur.child.get(a.charAt(i));
    else
    {cur.child.put(a.charAt(i),new trie());
      cur=cur.child.get(a.charAt(i));
    }
  }
  cur.isEnd=true;
  }
   void search(String a,trie root)
   {
     trie cur=root;
     for (int i=0; i<a.length();++i ) {
       char t=a.charAt(i);
       trie node=cur.child.get(t);
       if(node==null)
       {System.out.print("0");
     return;}

     cur=node;
     }
     print(cur,a);
   }
   void print(trie root,String prefix)
   {
       if(root.isEnd)
       {System.out.print(prefix+" ");
       }
     for(char i='a';i<='z';++i)
     {
       trie node=root.child.get(i);
       
       if(node!=null)
       print(node,prefix+i);
     }
   }
}
class phoneDict
 {
  static trie root;
  public static void fn(String a[],int n,String q)
  {
    for (String t :a ) {
      root.add(t,root);
    }
    for(int i=1;i<=q.length();++i)
    {root.search(q.substring(0,i),root);
      System.out.println();
    }
  }
 public static void main (String[] args)
  {
 Scanner ab=new Scanner(System.in);
 int t=ab.nextInt();
 while(t-->0)
 {
     root=new trie();
     int n=ab.nextInt();
     String arr[]=new String[n];
     for(int i=0;i<n;++i)
     arr[i]=ab.next();
      fn(arr,n,ab.next());
     //System.out.println();
 }
  }
}