10041: Vito’s family
| Problem C: Vito’s family |
Background
The world-known gangster Vito Deadstone is moving to New York. He has a very big family there, all of them living in Lamafia Avenue. Since he will visit all his relatives very often, he is trying to find a house close to them.
Problem
Vito wants to minimize the total distance to all of them and has blackmailed you to write a program that solves his problem.
Input
The input consists of several test cases. The first line contains the number of test cases.
For each test case you will be given the integer number of relatives r ( 0 < r < 500) and the street numbers (also integers) where they live ( 0 < si < 30000 ). Note that several relatives could live in the same street number.
Output
For each test case your program must write the minimal sum of distances from the optimal Vito’s house to each one of his relatives. The distance between two street numbers si and sj is dij= |si-sj|.
Sample Input
2
2 2 4
3 2 4 6
Sample Output
2
4
Tics:
1. Sort the street number
2. Find median
3. Find summation of distance from median to street number i.e dis+=|median-si|
Code:
| #include <stdio.h>#include<stdlib.h>
#define s 30005 int cmp(const void *a,const void *b){ int *x=(int *)a; int *y=(int *)b; return *x-*y; } int main(){ int a[s]; int i,j,dis,n,m,mid; //freopen(“a.in”,”r”,stdin); scanf(“%d”,&n); for(i=1;i<=n;i++){ scanf(“%d”,&m); for(j=0;j<m;j++) scanf(“%d “,&a[j]); qsort(a,m,sizeof(int),cmp); j=m/2; if(m%2==0) mid=(a[j]+a[j-1])/2; else mid=a[j]; dis=0; |
for(j=0;j<m;j++){if(mid>a[j])
dis=dis+(mid-a[j]); else dis=dis+(a[j]-mid); } printf(“%d\n”,dis); } return 0; |
10137: The Trip
Problem A: The Trip
A number of students are members of a club that travels annually to exotic locations. Their destinations in the past have included Indianapolis, Phoenix, Nashville, Philadelphia, San Jose, and Atlanta. This spring they are planning a trip to Eindhoven.
The group agrees in advance to share expenses equally, but it is not practical to have them share every expense as it occurs. So individuals in the group pay for particular things, like meals, hotels, taxi rides, plane tickets, etc. After the trip, each student’s expenses are tallied and money is exchanged so that the net cost to each is the same, to within one cent. In the past, this money exchange has been tedious and time consuming. Your job is to compute, from a list of expenses, the minimum amount of money that must change hands in order to equalize (within a cent) all the students’ costs.
The Input
Standard input will contain the information for several trips. The information for each trip consists of a line containing a positive integer, n, the number of students on the trip, followed by n lines of input, each containing the amount, in dollars and cents, spent by a student. There are no more than 1000 students and no student spent more than $10,000.00. A single line containing 0 follows the information for the last trip.
The Output
For each trip, output a line stating the total amount of money, in dollars and cents, that must be exchanged to equalize the students’ costs.
| Sample Input
3 10.00 20.00 30.00 4 15.00 15.01 3.00 3.01 0 |
Output for Sample Input
$10.00 $11.99
|
Tips:
1.
If (currentStudentPayment > averagePayment) positiveDifference += currentStudentPayment - averagePayment; Else negativeDifference += averagePayment - currentStudentPayment; if(negativeDifference > positiveDifference) return negativeDifference else return positiveDifference
2. Here negative or positive difference must be int which is the tic of this problem
Code:
#include<stdio.h>
int main(){
double tem[1001];
double sum,neg_dif,pos_dif;
long int n,i;
//freopen(“a.in”,”r”,stdin);
while(1){
scanf(“%ld”,&n);
if(n==0)break;
sum=0.0,neg_dif=0.0,pos_dif=0.0;
for(i=1;i<=n;i++){
scanf(“%lf”,&tem[i]);
tem[i]*=100;
sum=sum+tem[i];
}
double avrg=sum/(double)n;
for(i=1;i<=n;i++){
if(tem[i]>avrg)
neg_dif+=(int)(tem[i]-avrg);
else
pos_dif+=(int)(avrg-tem[i]);
}
if(pos_dif>neg_dif)
printf(“$%.2lf\n”,pos_dif/100);
else
printf(“$%.2lf\n”,neg_dif/100);
}
return 0;
}
10116: Robot Motion
Problem F: Robot Motion
A robot has been programmed to follow the instructions in its path. Instructions for the next direction the robot is to move are laid down in a grid. The possible instructions are
N north (up the page)
S south (down the page)
E east (to the right on the page)
W west (to the left on the page)
For example, suppose the robot starts on the north (top) side of Grid 1 and starts south (down). The path the robot follows is shown. The robot goes through 10 instructions in the grid before leaving the grid.
Compare what happens in Grid 2: the robot goes through 3 instructions only once, and then starts a loop through 8 instructions, and never exits.
You are to write a program that determines how long it takes a robot to get out of the grid or how the robot loops around.
There will be one or more grids for robots to navigate. The data for each is in the following form. On the first line are three integers separated by blanks: the number of rows in the grid, the number of columns in the grid, and the number of the column in which the robot enters from the north. The possible entry columns are numbered starting with one at the left. Then come the rows of the direction instructions. Each grid will have at least one and at most 10 rows and columns of instructions. The lines of instructions contain only the characters N, S, E, or W with no blanks. The end of input is indicated by a row containing 0 0 0.
For each grid in the input there is one line of output. Either the robot follows a certain number of instructions and exits the grid on any one the four sides or else the robot follows the instructions on a certain number of locations once, and then the instructions on some number of locations repeatedly. The sample input below corresponds to the two grids above and illustrates the two forms of output. The word “step” is always immediately followed by “(s)” whether or not the number before it is 1.
Example input:
3 6 5
NEESWE
WWWESS
SNWWWW
4 5 1
SESWE
EESNW
NWEEN
EWSEN
0 0 0
Example output:
10 step(s) to exit
3 step(s) before a loop of 8 step(s)
Tips:
- First you have to input correctly.
- Take two array on is indicate input array other array element represent movement number.
- If out of col or row then only print count step
- Otherwise count -arry count current position value -1
- And count= count-loop count;
- End
|
10062 Tell me the frequencies!
Tell me the frequencies!
Given a line of text you will have to find out the frequencies of the ASCII characters present in it. The given lines will contain none of the first 32 or last 128 ASCII characters. Of course lines may end with ‘\n’ and ‘\r’ but always keep those out of consideration.
Input
Several lines of text are given as input. Each line of text is considered as a single input. Maximum length of each line is 1000.
Output
Print the ASCII value of the ASCII characters which are present and their frequency according to the given format below. A blank line should separate each set of output. Print the ASCII characters in the ascending order of their frequencies. If two characters are present the same time print the information of the ASCII character with higher ASCII value first. Input is terminated by end of file.
Sample Input:
AAABBC
122333
Sample Output:
67 1
66 2
65 3
49 1
50 2
51 3
Tics:
1. Declear a structure like: struct arra{ int ascii,int fre} a[128];
2. Store a[m].ascii=m and a[m].fre++
3. Sort frequency wise and if both fre. Are equal the first large ascii
4. Loop is continue from 32 to 127
5. Print newline exactly. No etra new line at the end of the output.
Code
| #include<stdio.h>
struct array{ int ascii; int fre; } a[128]; int main(){ char ch; int i,f=0,n=0,m; //freopen(“a.in”,”r”,stdin); n=scanf(“%c”,&ch); while(1){ m=(int)ch; while(m!=10){ if(m>31 && m<128){ a[m].ascii=m; a[m].fre+=1; } n=scanf(“%c”,&ch); if(n!=1) break; m=(int)ch; } int tem,j; for(i=32;i<128;i++) { for(j=32;j<127;j++) { if(a[j].fre>a[j+1].fre) { tem=a[j].fre; a[j].fre=a[j+1].fre; a[j+1].fre=tem; tem=a[j].ascii; a[j].ascii=a[j+1].ascii; a[j+1].ascii=tem; } else if(a[j].fre==a[j+1].fre && a[j].ascii<a[j+1].ascii) { tem=a[j].ascii; a[j].ascii=a[j+1].ascii; a[j+1].ascii=tem; } } } for(i=32;i<128;i++){ if(a[i].fre!=0){ printf(“%d %d\n”,a[i].ascii,a[i].fre); a[i].ascii=0; a[i].fre=0; } } n=scanf(“%c”,&ch); if(n!=1) break; printf(“\n”); } return 0; } |
10042: Smith Numbers
| Problem D: Smith Numbers |
Background
While skimming his phone directory in 1982, Albert Wilansky, a mathematician of Lehigh University , noticed that the telephone number of his brother-in-law H. Smith had the following peculiar property: The sum of the digits of that number was equal to the sum of the digits of the prime factors of that number. Got it? Smith’s telephone number was 493-7775. This number can be written as the product of its prime factors in the following way:
The sum of all digits of the telephone number is 4+9+3+7+7+7+5=42, and the sum of the digits of its prime factors is equally 3+5+5+6+5+8+3+7=42. Wilansky was so amazed by his discovery that he named this type of numbers after his brother-in-law: Smith numbers.
As this observation is also true for every prime number, Wilansky decided later that a (simple and unsophisticated) prime number is not worth being a Smith number and he excluded them from the definition.
Problem
Wilansky published an article about Smith numbers in the Two Year College Mathematics Journal and was able to present a whole collection of different Smith numbers: For example, 9985 is a Smith number and so is 6036. However, Wilansky was not able to give a Smith number which was larger than the telephone number of his brother-in-law. It is your task to find Smith numbers which are larger than 4937775.
Input
The input consists of several test cases, the number of which you are given in the first line of the input.
Each test case consists of one line containing a single positive integer smaller than 109.
Output
For every input value n, you are to compute the smallest Smith number which is larger than n and print each number on a single line. You can assume that such a number exists.
Sample Input
1
4937774
Sample Output
4937775
Tips:
- First initialize prime number , in special way
- Then sum each digit
- Find per factor, find sum of digit of that factor, then add it with total sum
- Check it not prime and totals are equal.
Code:
| #include <stdio.h>
#include <math.h> #define max 46400 int p[max+1]; int a[6000]; int prime(){ int k=0,j,i; for(i=1;i<max;i++) p[i]=1;//assume all prime for(i=2;i<=sqrt(max);){ for(j=i+i;j<=max;j+=i) p[j]=0; for(i++;!p[i];i++);//update next one } for(i=1;i<=max;i++) if(p[i]) a[k++]=i; return 0; } int main(){ long int i,j,n,a1,k,sum1,m,fl=0,s; //freopen(“10042.in”,”r”,stdin); prime(); scanf(“%ld”,&n); for(i=0;i<n;i++){ scanf(“%ld”,&a1); for(j=a1+1;;j++){ sum1=0; k=0; /*find the sum of the digit*/ for(m=j;m!=0;m/=10) sum1+=(m%10); /*find the sum of factors of number*/ m=j; s=(long int)sqrt(m); long int o; //if k is larger than sum1 then break for(o=1;a[o]<=s && k<=sum1;o++){ if(m%a[o]==0){ long int ds=0; for(long int dm=a[o];dm!=0;dm/=10) ds+=(dm%10); while(m%a[o]==0){ k+=ds; m=m/a[o]; } } } //prime number is not smith number so k=0 mean it prime if(m!=1 && k!=0){ for (long int dm=m;m!=0;m/=10) k+=(m%10); } /*check condition*/ if(sum1==k) break; } printf(“%ld\n”,j); } return 0; } |
10035: Primary Arithmetic
Problem B: Primary Arithmetic
Children are taught to add multi-digit numbers from right-to-left one digit at a time. Many find the “carry” operation – in which a 1 is carried from one digit position to be added to the next – to be a significant challenge. Your job is to count the number of carry operations for each of a set of addition problems so that educators may assess their difficulty.
Input
Each line of input contains two unsigned integers less than 10 digits. The last line of input contains 0 0.
Output
For each line of input except the last you should compute and print the number of carry operations that would result from adding the two numbers, in the format shown below.
Sample Input
123 456
555 555
123 594
0 0
Sample Output
No carry operation.
3 carry operations.
1 carry operation.
Tics:
1. Number separate 10 time only , this make solution easy.
2. Every loop, a%10+b%10+carry>9 then carry_counter++
Code:
| #include<stdio.h>
int main(){ long int a,b,carry,cc,da,db,add,i; //freopen(“10035.in”,”r”,stdin); while(1){ scanf(“%ld %ld”,&a,&b); if(a==0 && b==0) break; cc=0;carry=0; for(i=1;i<=10;i++){ da=a%10; db=b%10; add=da+db+carry; if(add>9){ cc++; carry=1; } else carry=0; a=a/10; b=b/10; } if(cc==0) printf(“No carry operation.\n”); else if(cc==1) printf(“%ld carry operation.\n”,cc); else printf(“%ld carry operations.\n”,cc); } return 0; } |
10013 – Super long sums
| Super long sums |
The Problem
The creators of a new programming language D++ have found out that whatever limit for SuperLongInt type they make, sometimes programmers need to operate even larger numbers. A limit of 1000 digits is so small… You have to find the sum of two numbers with maximal size of 1.000.000 digits.
The Input
The first line of a input file is an integer N, then a blank line followed by N input blocks. The first line of an each input block contains a single number M (1<=M<=1000000) — the length of the integers (in order to make their lengths equal, some leading zeroes can be added). It is followed by these integers written in columns. That is, the next M lines contain two digits each, divided by a space. Each of the two given integers is not less than 1, and the length of their sum does not exceed M.
There is a blank line between input blocks.
The Output
Each output block should contain exactly M digits in a single line representing the sum of these two integers.
There is a blank line between output blocks.
| Sample Input 2
5 0 0 0 0 0 0 0 0 0 0 10 9 6 2 4 8 6 2 3 1 9 7 5 6 8 3 8 9 6 4 9 |
Sample Output 00000
15746135263 |
Tics:
1. Need a[1000001], b[1000001] to global char type data and take input as integer like %ld;
2. Must print last carry. And must not print last extra newline.
Code:
| #include <stdio.h>#define s 1000001
char a[s],b[s]; int main(){ long n,m,i,add,k; //freopen(“10013.in”,”r”,stdin); scanf(“%ld”,&n); for(k=1;k<=n;k++){ scanf(“%ld”,&m); for(i=1;i<=m;i++) scanf(“%ld %ld”,&a[i],&b[i]); add=0; for(i=m;i>=1;i–) { add = a[i]+b[i]+add;
|
a[i]=add%10;add = add/10;
} if(add!=0) printf(“%ld”,add); for(i=1;i<=m;i++) printf(“%ld”,a[i]);
if(k!=n) printf(“\n\n”); else printf(“\n”); } return 0; } |
Recent Comment