Ankit
BAN USER- 0of 0 votes
AnswersYou are given a tree with N nodes. Every node in the tree has a given weight. Your goal is to divide the given tree in two trees by removing exactly one edge such that the difference of sum of weights in the new trees is minimum.
- Ankit in India
Input
First line contains integer T, the number of test cases. First line of each test case contains integer N, the number of nodes. Next line contains the N integers, weight of node 0, 1 .. N - 1. The next N - 1 line contain two space separated integers x and y, describing an edge, where x and y are 0 based indices for nodes in the tree.
Constraints
T <= 100, N <= 1000
Output
Output a single line for each test case, which contains the min absolute difference between the sum of the nodes of the two trees.
Example
Input:
2
3
8 7 8
1 0
2 1
9
5 5 4 1 8 8 3 5 2
1 0
2 0
3 1
4 1
5 3
6 0
7 5
8 1
Output:
7
13
Author: xyler
Date Added: 15-07-2012
Time Limit: 10 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Algorithm - 0of 0 votes
AnswersTwo numbers are called friendly if they share a digit. For example 1239 and 9760 are friendly where as 1234 and 9876 are not. You are given N numbers and you have to calculate the count of pairs of numbers that are friendly.
- Ankit in India
Input
First line of input contains an integer T, the number of test cases. For each test case, the first line contains N, the number of integers given. The next N lines contain N integers.
Constraint
T <= 10, N <= 10 ** 4, Each given number is between 1 and 10 ** 18
Output
For each test case, print a line containing the count of pairs of number that are friendly.
Example
Input:
2
5
2837 2818 654 35 931
5
183 665 908 774 362
Output:
6
3
Author: xyler
Date Added: 15-07-2012
Time Limit: 1 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC| Report Duplicate | Flag | PURGE
Directi Software Engineer / Developer Algorithm
#include<stdio.h>
struct node{
int data;
struct node* left;
struct node* right;
};
struct node* consbst(int pre[],int k,int l)
{
struct node* tmp=(struct node*)malloc(sizeof(struct node));
if(l==k)
{
tmp->data=pre[k];
tmp->left=NULL;
tmp->right=NULL;
return tmp;
}
int i=k+1;
while(pre[k]>pre[i]&&i<l)
i++;
i--;
tmp->data=pre[k];
tmp->left=consbst(pre,k+1,i);
tmp->right=consbst(pre,i+1,l);
return tmp;
}
void printinorder(struct node* head)
{
if(head==NULL)
return;
printinorder(head->left);
printf("%d",head->data);
printinorder(head->right);
}
int main()
{
struct node* tree;
int pre[]={6,2,1,4,3,5,8,7,9};
tree=consbst(pre,0,8);
printinorder(tree);
getch();
}
consider n=5, then no. of ways to select nos. from 1 to 5 are
{5},{4,1},{3,2} => no. of ways=3.
similarly for n=10
{10},{9,1},{8,2},{7,3},{7,2,1},{6,4},{6,3,1},{5,3,2},{5,4,1} => no. of ways=9
similarly for n=11,
{11},{10,1},{9,2},{8,3},{8,2,1},{7,4},{7,3,1},{6,5},{6,3,2},{6,4,1},{5,4,2},{5,3,2,1} => no. of ways=12.
Note- no number between 1 to n must be repeated
source code-
#include<stdio.h>
int ways(int n)
{
int wayn=0;
if(n<3)return 1;
int i;
int way[n+1];
way[1]=1;
way[2]=1;
for(i=1;i<=(n+1)/2;i++)
{
wayn+=ways(i);
}
if(n%2&& n>=5)
way[n]=wayn-1;
else
way[n]=wayn;
return way[n];
}
int main()
{
int n;
scanf("%d",&n);
printf("%d\n",ways(n));
getch();
return 0;
}
Repangelafiecke, Blockchain Developer at ASU
I am a Data processor at DGS VolMAX. I will also be a controller for the data I use for ...
Repleancpuryear, Data Scientist at Adjetter Media Network Pvt Ltd.
Hi guys!! My name is Lean C Puryear and I love fashion, I hope to some day get into the ...
Both 7 and 5 are co-prime numbers. So it's not possible to uniformly generate 7 numbers using rand5().
- Ankit October 22, 2019