Edição 34: Treinamento em TI - problemas e desafios atuais das principais empresas

Questões

Um carro tem 4 pneus e 1 pneu sobressalente. Cada pneu pode percorrer uma distância máxima de 20.000 milhas antes de se desgastar. Qual é a distância máxima que o carro pode percorrer antes que você seja forçado a comprar um pneu novo? Você pode trocar os pneus (usando o pneu sobressalente) um número ilimitado de vezes.

Um homem recebe uma tarefa. Ele dobra a tarefa realizada todos os dias. Se o homem realiza a tarefa completamente em 18 dias, quantos dias levou para concluir 25% da tarefa?

Tarefas

Dado um número n, encontre o menor número que tenha o mesmo conjunto de dígitos que n e seja maior que n. Se n for o maior número possível com seu conjunto de dígitos, imprima "não possível".

Entrada:
A primeira linha de entrada contém um número inteiro T, indicando o número de casos de teste.
A primeira linha de cada caso de teste é n, n é o número.

Saída:
imprima o número maior que n com o mesmo conjunto de dígitos e, se não for possível, imprima "não possível" sem aspas duplas.

Restrições: Exemplo: Entrada de Saída
1 ≤ T ≤ 100
1 ≤ n ≤ 100000



2
143
431


314
not possible

Given a value N, find the number of ways to make change for N cents, if we have infinite supply of each of S = { S1, S2,…, Sm} valued coins. The order of coins doesn’t matter. For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

Input:
The first line contains an integer 'T' denoting the total number of test cases. In each test cases, the first line contains an integer 'M' denoting the size of array. The second line contains M space-separated integers A1, A2, ..., AN denoting the elements of the array. The third line contains an integer 'N' denoting the cents.

Output:
Imprima o número de maneiras possíveis de alterar N centavos.

Restrições: Exemplo: Entrada: Saída: Explicação: Caixa de Teste 1: As possibilidades são as seguintes: {1, 1, 1, 1}, {1, 1, 2}, {1, 3}, {2, 2}.
1 ≤ T ≤ 50
1 ≤ N ≤ 300
1 ≤ A[i] ≤ 300



2
3
1 2 3
4
4
2 5 3 6
10


4
5

Dada uma lista de contatos existentes em uma lista telefônica e uma string de consulta str. A tarefa é implementar a consulta de pesquisa para a lista telefônica. Execute uma consulta de pesquisa para cada prefixo p da string de consulta str (ou seja, do índice 1 ao comprimento da string) que imprima todos os contatos recomendados distintos que têm o mesmo prefixo da nossa consulta (p) em ordem lexicográfica. Consulte a parte da explicação para uma melhor compreensão.

NOTA: Se não houver correspondência entre a consulta e os contatos, imprima "0".

Entrada:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains three lines. First line of each test case contains N i.e., number of contacts. Second line contains space separated all the contacts in the form of string. And third line contains query string.

Output:
For each test case, print each query result in new line. If there is no match between query and contacts, print «0».

Constraints:
1<=T<=100
1<=N<=50
1<=|contact[i].length|<=50
1<=|query length|<=6

Example:
Input:
1
3
spiceit spcicecite spiiceti
spicpt

Output:
spiceit spcicecite spiiceti
spiceit spcicecite spiiceti
spiceit spiiceti
spiceit
0
0

Explanation:
By running the query on contact list, we get,
Suggestions based on "s" are:
spiceit spcicecite spiiceti
Suggestions based on "sp" are:
spiceit spcicecite spiiceti
Suggestions based on "spi" are:
spiceit spiiceti
Suggestions based on "spic" are:
spiceit
No Results Found for «spicp», So print «0».
No Results Found for «spicpt», So print «0».

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();
 }
  }
}