Выпуск#34: ITренировка — актуальные вопросы и задачи от ведущих компаний

Вопросы

A car has 4 tyres and 1 spare tyre. Each tyre can travel a maximum distance of 20000 miles before wearing off. What is the maximum distance the car can travel before you are forced to buy a new tyre? You are allowed to change tyres (using the spare tyre) an unlimited number of times.

A man is allocated a task. He doubles the task done everyday. If the man completely does the task in 18 days, how many days did it take for the man to complete 25% of the task?

Задачи

Given a number n, find the smallest number that has same set of digits as n and is greater than n. If n is the greatest possible number with its set of digits, then print “not possible”.

Input:
The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is n,n is the number.

Output:
Print the greater number than n with same set of digits and if not possible then print «not possible» without double quote.

Constraints:
1 ≤ T ≤ 100
1 ≤ n ≤ 100000

Example:
Input
2
143
431

Output
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:
Print number of possible ways to make change for N cents.

Constraints:
1 ≤ T ≤ 50
1 ≤ N ≤ 300
1 ≤ A[i] ≤ 300

Example:
Input:
2
3
1 2 3
4
4
2 5 3 6
10

Output:
4
5

Explanation:
Testcase 1: The possiblities are as such: {1, 1, 1, 1}, {1, 1, 2}, {1, 3}, {2, 2}.

Given a list of contacts which exist in a phone directory and a query string str. The task is to implement search query for the phone directory. Run a search query for each prefix p of the query string str(i.e from index 1 to str length) that prints all the distinct recommended contacts which have the same prefix as our query (p) in lexicographical order. Please refer the explanation part for better understanding.

NOTE: If there is no match between query and contacts, print «0».

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