Блог пользователя kevin_debruyne

Автор kevin_debruyne, история, 3 года назад, По-английски

Question 1.

You are given an integer N. Now, you need to find if there exists two prime numbers (X,Y) such that X^2+y^2=N. If (X,Y) exists then output the minimum value of X+Y otherwise print -1.

Input format: The first line contains an integer, N, denoting the value of N described in the problem.

Constraints: 1<=N<=10^9.

Sample Input:

input: 7
output: -1
explanation: for N=7 no such X,Y exists.

input: 34
output: 8
explanation: X=5 and Y=3 satisfy the condition 25+9=34.

input: 13
output: 5
explanation: X=2 and Y=3 satisfy the condition 4+9=13.

Question 2:

Alice has a string S with length N and Bob has a string C with length M. Bob gave Alice an array of integers A of size N representing the cost of deleting each letter in strings S. Find the minimum cost T to delete a number of characters(possibly zero) from S so that C doesn't appear as a sub sequence of S.

Notes: Ai is the cost to delete Si, where 1<=i<=N.

Input format first line: N denoting the no. of elements in A.
second line: M denoting the length of C.
third line: string S, denoting the Alice's string.
fourth line: string C, denoting the Bob's string.
fifth line: contains integers describing A[i].

Sample Input:

5
3
hallo
llo
1 2 3 4 5

output: 5
explanation: if we delete the third character 'l' in string S, we wouldn't have any sub sequence equal to 'llo' in string S, achieving the minimum cost.

sample input: 8
8
muhammad
muhammad
1 2 3 4 5 6 7 8

sample output: 1 explanation: it's enough to delete the first character and this achieves the minimum cost.

sample input: 15
4
hallohallohallo
allo
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

output: 21
explanation: we have four sub sequences equal to 'allo' in string S. If we delete characters numbers 2,7 and 12 in string S, we wouldn't have any sub sequences equal to 'allo' in string S, achieving the minimum cost.

Thanks in advance!!!

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится