Codeforces problem solution in C programming language
(1) - 4A
A.
Watermelon
Time limit per test 1 second
Memory limit per test 64 megabytes
Input standard input
Output standard output
One
hot summer day Pete and his friend Billy decided to buy a watermelon. They
chose the biggest and the ripest one, in their opinion. After that the
watermelon was weighed, and the scales showed w kilos. They rushed home, dying of
thirst, and decided to divide the berry, however they faced a hard problem.
Pete
and Billy are great fans of even numbers, that's why they want to divide the
watermelon in such a way that each of the two parts weighs even number of
kilos, at the same time it is not obligatory that the parts are equal. The boys
are extremely tired and want to start their meal as soon as possible, that's
why you should help them and find out, if they can divide the watermelon in the
way they want. For sure, each of them should get a part of positive weight.
Input
The first (and the
only) input line contains integer number w (1 ≤ w ≤ 100) — the weight of the watermelon bought by the
boys.
Output
Print YES, if the boys can divide the watermelon into
two parts, each of them weighing even number of kilos; and NO in the opposite case.
Examples
Input
8
Output
YES
Note
For example, the boys
can divide the watermelon into two parts of 2 and 6 kilos respectively (another
variant — two parts of 4 and 4 kilos).
Solution(1)
int main()
{
int w;
scanf("%d",&w);
if(w%2==0 && w!=2)
{
printf("YES");
}
else
{
printf("NO");
}
return 0;
}
(2) - 189A
A.
Cut Ribbon
Time limit per test 1 second
Memory limit per test 256 megabytes
Input standard input
Output standard output
Polycarpus
has a ribbon, its length is n. He wants to cut the ribbon in a way that fulfils the following
two conditions:
·
After the cutting each
ribbon piece should have length a, b or c.
·
After the cutting the
number of ribbon pieces should be maximum.
Help Polycarpus and find the number of ribbon
pieces after the required cutting.
Input
The first line
contains four space-separated integers n, a, b and c (1 ≤ n, a, b, c ≤ 4000) — the length of the original ribbon and
the acceptable lengths of the ribbon pieces after the cutting, correspondingly.
The numbers a, b and c can coincide.
Output
Print a single number
— the maximum possible number of ribbon pieces. It is guaranteed that at least
one correct ribbon cutting exists.
Examples
Input
5 5 3 2
Output
2
Input
7 5 5 2
Output
2
Note
In the first example Polycarpus can cut the
ribbon in such way: the first piece has length 2, the second piece has length
3.
In the second example Polycarpus can cut the
ribbon in such way: the first piece has length 5, the second piece has length
2.
Solution(2)
#include<stdio.h>
int main()
{
int n,a,b,c;
scanf("%d %d %d %d",&n,&a,&b,&c);
int i=0,j=0,temp=0,flag=0;
for(i=0; i<=n; i++)
{
for(j=0; j<=n; j++)
{
if(i*a+j*b<=n)
{
if((n-(i*a+j*b))%c==0)
{
flag=i+j+(n-(i*a+j*b))/c;
if(flag>temp && flag!=0)
{
temp=flag;
}
}
}
}
}
printf("%d",temp);
return 0;
}
(3) - 208A
A.
Dubstep
Time limit per test 2 seconds
Memory limit per test 256 megabytes
Input standard input
Outputstandard output
Vasya
works as a DJ in the best Berland nightclub, and he often uses dubstep music in
his performance. Recently, he has decided to take a couple of old songs and
make dubstep remixes from them.
Let's
assume that a song consists of some number of words. To make the dubstep remix
of this song, Vasya inserts a certain number of words "WUB" before the first word of the song (the
number may be zero), after the last word (the number may be zero), and between
words (at least one between any pair of neighbouring words), and then the boy
glues together all the words, including "WUB", in one string and plays the song at the club.
For
example, a song with words "I AM X" can transform into a dubstep remix as "WUBWUBIWUBAMWUBWUBX" and cannot transform into "WUBWUBIAMWUBX".
Recently, Petya has heard Vasya's new dubstep
track, but since he isn't into modern music, he decided to find out what was
the initial song that Vasya remixed. Help Petya restore the original song.
Input
The input consists of
a single non-empty string, consisting only of uppercase English letters, the
string's length doesn't exceed 200characters. It is guaranteed that before Vasya remixed the song,
no word contained substring "WUB" in it; Vasya didn't change the word order. It is also
guaranteed that initially the song had at least one word.
Output
Print the words of the
initial song that Vasya used to make a dubsteb remix. Separate the words with a
space.
Examples
Input
WUBWUBABCWUB
Output
ABC
Input
WUBWEWUBAREWUBWUBTHEWUBCHAMPIONSWUBMYWUBFRIENDWUB
Output
WE ARE THE CHAMPIONS
MY FRIEND
Note
In the first sample:
"WUBWUBABCWUB" = "WUB" + "WUB" + "ABC" + "WUB". That means that the song originally consisted of a
single word "ABC", and all words "WUB" were added by Vasya.
In the second sample Vasya added a single word
"WUB" between all neighbouring words, in the
beginning and in the end, except for words "ARE" and "THE" — between them Vasya added two "WUB".
Solution(3)
#include <stdio.h>
#include <string.h>
int main()
{
char a[205],ans[200];
int i,j=0,n=0;
scanf("%s",a);
for(i=0;i<strlen(a);i++)
{
if(n==0)
{
if(a[i]=='W')
{
n++;
}
else
{
ans[j]=a[i];
j++;
}
if(i==strlen(a)-1 && a[i]=='W')
{
ans[j]=a[i];
j++;
}
}
else if(n==1)
{
if(a[i]=='U')
{
n++;
}
else if(a[i]=='W')
{
ans[j]='W';
j++;
n=1;
}
else
{
ans[j]='W';
j++;
ans[j]=a[i];
j++;
n=0;
}
if(i==strlen(a)-1 && a[i]=='U')
{
ans[j]='W';
j++;
ans[j]='U';
j++;
}
}
else if(n==2)
{
if(a[i]=='B')
{
n=0;
ans[j]=' ';
j++;
if(j==1)
j--;
}
else
{
ans[j]='W';
j++;
ans[j]='U';
j++;
ans[j]=a[i];
j++;
n=0;
if(a[i]=='W')
{
n=1;
j--;
}
}
}
}
ans[j]='\0';
printf("%s\n",ans);
return 0;
}
(4) - 116A
A.
Tram
Time limit per test 2 seconds
Memory limit per test 256 megabytes
Input standard input
Output standard output
Linear
Kingdom has exactly one tram line. It has n stops, numbered from 1 to n in the order of tram's movement. At
the i-th stop aipassengers exit the tram, while bi passengers enter it. The tram is empty
before it arrives at the first stop. Also, when the tram arrives at the last
stop, all passengers exit so that it becomes empty.
Your task is to calculate the tram's minimum
capacity such that the number of people inside the tram at any time never
exceeds this capacity. Note that at each stop all exiting passengers exit before any entering passenger enters the tram.
Input
The first line
contains a single number n (2 ≤ n ≤ 1000) — the number of the tram's stops.
Then n lines follow, each contains two
integers ai and bi (0 ≤ ai, bi ≤ 1000) — the number of passengers that exits the
tram at the i-th stop, and the
number of passengers that enter the tram at the i-th stop. The stops are given from the first
to the last stop in the order of tram's movement.
·
The number of people
who exit at a given stop does not exceed the total number of people in the tram
immediately before it arrives at the stop. More formally,
This particularly means
that a1 = 0.
·
At the last
stop, all the passengers
exit the tram and it becomes empty. More formally,
·
No passenger will
enter the train at the last stop. That is, bn = 0.
Output
Print a single integer
denoting the minimum possible capacity of the tram (0 is allowed).
Examples
Input
4
0 3
2 5
4 2
4 0
0 3
2 5
4 2
4 0
Output
6
Note
For the first example,
a capacity of 6 is sufficient:
·
At the first stop, the
number of passengers inside the tram before arriving is 0. Then, 3 passengers
enter the tram, and the number of passengers inside the tram becomes 3.
·
At the second stop, 2
passengers exit the tram (1 passenger remains inside). Then, 5 passengers enter
the tram. There are 6 passengers inside the tram now.
·
At the third stop, 4
passengers exit the tram (2 passengers remain inside). Then, 2 passengers enter
the tram. There are 4 passengers inside the tram now.
·
Finally, all the
remaining passengers inside the tram exit the tram at the last stop. There are
no passenger inside the tram now, which is in line with the constraints.
Since the number of passengers inside the tram
never exceeds 6, a capacity of 6 is sufficient. Furthermore it is not possible
for the tram to have a capacity less than 6. Hence, 6 is the correct answer.
Solution(4)
#include<stdio.h>
#include<string.h>
int main(){
int n,a,b,temp=0,i,f=0;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d %d",&a,&b);
temp=temp-a+b;
if(i==1){f=temp;}
if(f<=temp)
f=temp;
}
printf("%d",f);
return 0;
}
(5) - 894A
A.
QAQ
Time
limit per test 1 second
Memory limit per test 256 megabytes
Input standard input
Output standard output
"QAQ"
is a word to denote an expression of crying. Imagine "Q" as eyes with
tears and "A" as a mouth.
Now
Diamond has given Bort a string consisting of only uppercase English letters of
length n. There is a great
number of "QAQ" in the string (Diamond is so cute!).
Bort wants to know how many subsequences
"QAQ" are in the string Diamond has given.
Note that the letters "QAQ" don't have to
be consecutive, but the order of letters should be exact.
Input
The only line contains
a string of length n (1 ≤ n ≤ 100). It's guaranteed that the string only
contains uppercase English letters.
Output
Print a single
integer — the number of subsequences "QAQ" in the string.
Examples
Input
QAQAQYSYIOIWIN
Output
4
Input
QAQQQZZYNOIWIN
Output
3
Note
In the first example
there are 4 subsequences
"QAQ": "QAQAQYSYIOIWIN", "QAQAQYSYIOIWIN", "QAQAQYSYIOIWIN", "QAQAQYSYIOIWIN".
Solution(5)
#include<stdio.h>
int main()
{
char myarray[1000];
scanf("%s",&myarray);
int i,cnt=0,j,k,l,len=0;
len=strlen(myarray);
for(i=0; i<len; i++)
{
if(myarray[i]=='Q')
{
for(j=i+1; j<len; j++)
{
if(myarray[j]=='A')
{
for(l=j+1; l<len; l++)
{
if(myarray[l]=='Q')
{
cnt++;
}
}
}
}
}
}
printf("%d",cnt);
return 0;
}
(6) - 478B
B.
Random Teams
Time limit per test 1 second
Memory limit per test 256 megabytes
Input standard input
Output standard output
n participants of the competition were split into m teams in some manner so that each team
has at least one participant. After the competition each pair of participants
from the same team became friends.
Your
task is to write a program that will find the minimum and the maximum number of
pairs of friends that could have formed by the end of the competition.
Input
The only line of input
contains two integers n and m, separated by a single space (1 ≤ m ≤ n ≤ 109) — the number of participants and the number
of teams respectively.
Output
The only line of the
output should contain two integers kmin and kmax — the minimum possible number of pairs
of friends and the maximum possible number of pairs of friends respectively.
Examples
Input
5 1
Output
10 10
Input
3 2
Output
1 1
Input
6 3
Output
3 6
Note
In the first sample
all the participants get into one team, so there will be exactly ten pairs of
friends.
In the second sample
at any possible arrangement one team will always have two participants and the
other team will always have one participant. Thus, the number of pairs of
friends will always be equal to one.
In the third sample
minimum number of newly formed friendships can be achieved if participants were
split on teams consisting of 2 people, maximum number can be achieved if participants
were split on teams of 1, 1 and 4 people.
Solution(6)
#include <stdio.h>
int main(int argc, char const *argv[])
{
long long int n,m,min,max,s,e,d;
scanf("%I64d %I64d",&n,&m);
max=(n-m)*(n-m+1)/2;
s=n%m;
d=n/m;
e=n/m+1;
min=(m-s)*(d-1)*(d)/2+s*e*(e-1)/2;
printf("%I64d %I64d\n",min,max );
return 0;
}
(7) - 863A
A.
Quasi-palindrome
Time limit per test 1 second
Memory limit per test 256 megabytes
Input standard input
Output standard output
Let quasi-palindromic number be such number that adding some
leading zeros (possible none) to it produces a palindromic string.
String t is called a palindrome, if it reads the
same from left to right and from right to left.
For
example, numbers 131 and 2010200 are quasi-palindromic, they can be transformed to strings "131" and "002010200", respectively, which are palindromes.
You
are given some integer number x. Check if it's a quasi-palindromic number.
Input
The first line
contains one integer number x (1 ≤ x ≤ 109). This number is given without any leading zeroes.
Output
Print "YES" if number x is quasi-palindromic. Otherwise, print "NO" (without quotes).
Examples
Input
131
Output
YES
Input
320
Output
NO
Input
2010200
Output
YES
Solution(7)
#include<stdio.h>
int main()
{
char myarray[1000];
scanf("%s",&myarray);
int i=0,j=0,temp=0,flag=0,len=0;
len=strlen(myarray);
for(j=len-1; j>=0; j--)
{
if(myarray[j]!='0')
{
break;
}
if(myarray[j]=='0')
{
myarray[j]='\0';
temp++;
}
}
len-=temp;
for(i=0,j=len-1; i<=len/2; i++,j--)
{
if(myarray[i]!=myarray[j])
{
flag=1;
break;
}
}
if(!flag)
{
printf("YES");
}
else
{
printf("NO");
}
return 0;
}
(8) - 1A
A.
Theatre Square
Time
limit per test 1 second
Memory limit per test 256 megabytes
Input standard input
Output standard output
Theatre
Square in the capital city of Berland has a rectangular shape with the
size n × m meters.
On the occasion of the city's anniversary, a decision was taken to pave the
Square with square granite flagstones. Each flagstone is of the size a × a.
What is the least number of flagstones needed
to pave the Square? It's allowed to cover the surface larger than the Theatre
Square, but the Square has to be covered. It's not allowed to break the
flagstones. The sides of flagstones should be parallel to the sides of the
Square.
Input
The input contains
three positive integer numbers in the first line: n, m and a (1 ≤ n, m, a ≤ 109).
Output
Write the needed
number of flagstones.
Examples
Input
6 6 4
Output
4
Solution(8)
#include <stdio.h>
int main() {
long long n, m, a;
scanf("%I64d %I64d %I64d", &n, &m, &a);
long long x = (n / a) + (n % a != 0);
long long y = (m / a) + (m % a != 0);
printf("%I64d", x * y);
return 0 (9)
(9) - 71A
A.
Way Too Long Words
Time limit per test 2
seconds
Memory limit per test 256 megabytes
Input standard input
Output standard output
Sometimes
some words like "localization"
or "internationalization" are so long that writing them many
times in one text is quite tiresome.
Let's
consider a word too long,
if its length is strictly more than 10 characters. All
too long words should be replaced with a special abbreviation.
This
abbreviation is made like this: we write down the first and the last letter of
a word and between them we write the number of letters between the first and
the last letters. That number is in decimal system and doesn't contain any
leading zeroes.
Thus,
"localization" will be spelt as "l10n", and "internationalization» will be spelt as "i18n".
You
are suggested to automatize the process of changing the words with abbreviations.
At that all too long words should be replaced by the abbreviation and the words
that are not too long should not undergo any changes.
Input
The first line
contains an integer n (1 ≤ n ≤ 100). Each of the following n lines contains one word. All the words
consist of lowercase Latin letters and possess the lengths of from 1 to 100 characters.
Output
Print n lines. The i-th line should contain the result of
replacing of the i-th word from the
input data.
Examples
Input
4
word
localization
internationalization
pneumonoultramicroscopicsilicovolcanoconiosis
word
localization
internationalization
pneumonoultramicroscopicsilicovolcanoconiosis
Output
word
l10n
i18n
p43s
l10n
i18n
p43s
Solution(9)
#include <stdio.h>
#include <string.h>
int main() {
int n;
scanf("%d", &n);
char x[101];
for (int i = 0; i < n; i++) {
scanf("%s", x);
if (strlen(x) <= 10) {
puts(x);
} else {
printf("%c%d%c\n", x[0], strlen(x) - 2, x[strlen(x) - 1]);
}
}
return 0;
}
(10) - 112A
A.
Petya and Strings
Time limit per test 2 seconds
Memory limit per test 256 megabytes
Input standard input
Output standard output
Little
Petya loves presents. His mum bought him two strings of the same size for his
birthday. The strings consist of uppercase and lowercase Latin letters. Now
Petya wants to compare those two strings lexicographically. The letters' case does not matter, that is
an uppercase letter is considered equivalent to the corresponding lowercase
letter. Help Petya perform the comparison.
Input
Each of the first two
lines contains a bought string. The strings' lengths range from 1 to 100 inclusive. It is guaranteed that the
strings are of the same length and also consist of uppercase and lowercase
Latin letters.
Output
If the first string is
less than the second one, print "-1". If the second string is less
than the first one, print "1". If the strings are equal, print
"0". Note that the letters' case is not taken into consideration when
the strings are compared.
Examples
Input
aaaa
aaaA
aaaA
Output
0
Input
abs
Abz
Abz
Output
-1
Input
abcdefg
AbCdEfF
AbCdEfF
Output
1
Note
If you want more
formal information about the lexicographical order (also known as the "dictionary order" or "alphabetical order")
Solution(10)
#include<stdio.h>
#include<string.h>
int main()
{
int i,n,ans;
char a1[200],a2[200];
scanf("%s",&a1);
scanf("%s",&a2);
n= strlen(a1);
a1[n]="\0";
a2[n]="\0";
if(n>=1 && n<=100)
{
for(i=0;i<n;i++)
{
a1[i]=tolower(a1[i]);
//printf("%d",a1[i]);
a2[i]=tolower(a2[i]);
//printf("%d",a2[i]);
}
for(i=0;i<n;i++)
{
if((int)a1[i]==(int)a2[i])
ans=0;
else if((int)a1[i]>(int)a2[i])
{ans=1;
break;}
else if((int)a1[i]<(int)a2[i])
{ans=-1;
break;}
}
printf("%d",ans);
return 0;
}
else
return 0;}
(11) - 489B
B.
BerSU Ball
Time limit per test 1 second
Memory limit per test 256 megabytes
Input standard input
Output standard output
The
Berland State University is hosting a ballroom dance in celebration of its
100500-th anniversary! n boys and m girls are already busy rehearsing waltz,
minuet, polonaise and quadrille moves.
We know that several boy&girl pairs are
going to be invited to the ball. However, the partners' dancing skill in each
pair must differ by at most one.
For each boy, we know his dancing skills.
Similarly, for each girl we know her dancing skills. Write a code that can
determine the largest possible number of pairs that can be formed from n boys and m girls.
Input
The first line
contains an integer n (1 ≤ n ≤ 100) — the number of boys. The second line
contains sequence a1, a2, ..., an (1 ≤ ai ≤ 100), where ai is the i-th boy's dancing skill.
Similarly, the third
line contains an integer m (1 ≤ m ≤ 100) — the number of girls. The fourth line contains sequence b1, b2, ..., bm(1 ≤ bj ≤ 100), where bj is the j-th girl's dancing skill.
Output
Print a single number
— the required maximum possible number of pairs.
Examples
Input
4
1 4 6 2
5
5 1 5 7 9
1 4 6 2
5
5 1 5 7 9
Output
3
Input
4
1 2 3 4
4
10 11 12 13
1 2 3 4
4
10 11 12 13
Output
0
Input
5
1 1 1 1 1
3
1 2 3
1 1 1 1 1
3
1 2 3
Output
2
Solution(11)
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int arr[101];
int brr[101];
int comparator(const void* p,const void* q)
{
int l=*(int *)p;
int r=*(int *)q;
return l-r;
}
int main()
{
int n,m,i,j,k;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",arr+i);
scanf("%d",&m);
for(i=0;i<m;i++)
scanf("%d",brr+i);
qsort(arr,n,sizeof(int),comparator);
qsort(brr,m,sizeof(int),comparator);
j=0;k=0;
int count=0;
while(j!=n&&k!=m)
{
if(brr[k]>=arr[j]-1&&brr[k]<=arr[j]+1)
{
j++;
k++;
count++;
}
else if(brr[k]>arr[j])
{
j++;
}
else
{
k++;
}
}
printf("%d\n",count);
}
(12) - 903A
A.
Hungry Student Problem
Time limit per test 1 second
Memory limit per test 256 megabytes
Input standard input
Output standard output
Ivan's
classes at the university have just finished, and now he wants to go to the
local CFK cafe and eat some fried chicken.
CFK
sells chicken chunks in small and large portions. A small portion
contains 3 chunks; a large
one — 7 chunks. Ivan
wants to eat exactly x chunks. Now he
wonders whether he can buy exactly this amount of chicken.
Formally,
Ivan wants to know if he can choose two non-negative integers a and b in such a way that a small portions and b large ones contain exactly x chunks.
Help
Ivan to answer this question for several values of x!
Input
The first line
contains one integer n (1 ≤ n ≤ 100) — the number of test cases.
The i-th of the following n lines contains one integer xi (1 ≤ xi ≤ 100) — the number of chicken chunks Ivan wants to
eat.
Output
Print n lines, in i-th line output YES if Ivan can buy exactly xi chunks. Otherwise, print NO.
Example
Input
2
6
5
6
5
Output
YES
NO
NO
Note
In the first example
Ivan can buy two small portions.
In the second example
Ivan cannot buy exactly 5 chunks, since
one small portion is not enough, but two small portions or one large is too
much.
Solution(12)
#include <stdio.h>
#include <stdbool.h>
int main() {
int T; scanf("%d\n", &T);
for(int ti = 0, tn = T ; ti < tn ; ++ti) {
int X; scanf("%d\n", &X); bool found = false;
for(int i = 0 ; 7*i <= X && !found ; ++i)
found = ((X - 7*i) % 3 == 0);
printf("%s\n", found ? "YES" : "NO");
}
return 0;
}
(13) - 518A
A.
Vitaly and Strings
Time limit per test 1 second
Memory limit per test 256 megabytes
Input standard input
Output standard output
Vitaly
is a diligent student who never missed a lesson in his five years of studying
in the university. He always does his homework on time and passes his exams in
time.
During the last lesson the teacher has
provided two strings s and t to Vitaly. The strings have the same
length, they consist of lowercase English letters, string s is lexicographically smaller than
string t. Vitaly wondered if
there is such string that is lexicographically larger than string s and at the same is lexicographically
smaller than string t. This string should
also consist of lowercase English letters and have the length equal to the
lengths of strings s and t.
Let's help Vitaly solve this easy problem!
Input
The first line
contains string s (1 ≤ |s| ≤ 100), consisting of lowercase English letters.
Here, |s| denotes the
length of the string.
The second line
contains string t (|t| = |s|), consisting of lowercase English letters.
It is guaranteed that
the lengths of strings s and t are the same and string s is lexicographically less than
string t.
Output
If the string that
meets the given requirements doesn't exist, print a single string "No such string" (without the quotes).
If such string exists,
print it. If there are multiple valid strings, you may print any of them.
Examples
Input
a
c
c
Output
b
Input
aaa
zzz
zzz
Output
kkk
input
abcdefg
abcdefh
abcdefh
Output
No such string
Note
String s = s1s2... sn is said to be lexicographically smaller
than t = t1t2... tn, if there exists such i, that s1 = t1, s2 = t2, ... si - 1 = ti - 1, si < ti.
Solution(13)
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
long long int factorial(int n)
{
long long int a[n+1];
a[0]=1;
int i;
for(i=1;i<=n;i++)
{
a[i]=a[i-1]*i;
}
return a[n];
}
int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
int cmpi(const void *a,const void *b) {
return ((const int *)a)[0] - ((const int *)b)[0];
}
int min(int a,int b)
{
return (a>b?b:a);
}
int max(int a,int b)
{
return (a<b?b:a);
}
int main()
{
int n,m=0,i,j,a[100007],r[107],k;
char s[101],t[101],f[101];
scanf("%s %s",s,t);
int l=strlen(s);
for(i=l-1;i>=0;i--)
{
if(s[i]!='z')
{
s[i]=s[i]+1;
break;
}
}
for(j=i+1;j<l;j++)
{
s[j]='a';
}
//printf("ikhlj->->%s\n",s);
if( strcmp(s,t)<0 )
printf("%s\n",s);
else
printf("No such string\n");
return 0;
}
(14) - 859A
A.
Declined Finalists
Time limit per test 2 seconds
Memory limit per test 256 megabytes
Input standard input
Output standard output
This
year, as in previous years, MemSQL is inviting the top 25 competitors from the
Start[c]up qualification round to compete onsite for the final round. Not
everyone who is eligible to compete onsite can afford to travel to the office,
though. Initially the top 25 contestants are invited to come onsite. Each
eligible contestant must either accept or decline the invitation. Whenever a
contestant declines, the highest ranked contestant not yet invited is invited
to take the place of the one that declined. This continues until 25 contestants
have accepted invitations.
After the qualifying round completes, you
know K of the onsite
finalists, as well as their qualifying ranks (which start at 1, there are no ties). Determine the minimum
possible number of contestants that declined the invitation to compete onsite
in the final round.
Input
The first line of
input contains K (1 ≤ K ≤ 25), the number of onsite finalists you know.
The second line of input contains r1, r2, ..., rK(1 ≤ ri ≤ 106), the qualifying ranks of the finalists you
know. All these ranks are distinct.
Output
Print the minimum
possible number of contestants that declined the invitation to compete onsite.
Examples
Input
25
2 3 4 5 6 7 8 9 10 11 12 14 15 16 17 18 19 20 21 22 23 24 25 26 28
2 3 4 5 6 7 8 9 10 11 12 14 15 16 17 18 19 20 21 22 23 24 25 26 28
Output
3
Input
5
16 23 8 15 4
16 23 8 15 4
Output
0
Input
3
14 15 92
14 15 92
Output
67
Note
In the first example,
you know all 25 onsite finalists. The contestants who ranked 1-st, 13-th, and 27-th must have
declined, so the answer is 3.
Solution(14)
#include<stdio.h>
int main()
{
int k,c[35],i,r,ck;
while(scanf("%d",&k)==1){
ck=0;
for(i=0;i<k;i++){
scanf("%d",&c[i]);
if(c[i]>ck)
ck=c[i];
}
if(ck>25){
r=ck-25;
printf("%d\n",r);
}
else
printf("%d\n",0);
}
return 0;
}
(15) - 903C
C.
Boxes Packing
Time limit per test 1 second
Memory limit per test 256 megabytes
Input standard input
Output standard output
Mishka
has got n empty boxes. For
every i (1 ≤ i ≤ n), i-th box is a cube with side length ai.
Mishka can put a box i into another box j if the following conditions are met:
·
i-th box is not put
into another box;
·
j-th box doesn't
contain any other boxes;
·
box i is smaller than box j (ai < aj).
Mishka can put boxes into each other an
arbitrary number of times. He wants to minimize the number of visible boxes. A box is called visible iff it is not put into some another box.
Help Mishka to determine the minimum possible
number of visible boxes!
Input
The first line
contains one integer n (1 ≤ n ≤ 5000) — the number of boxes Mishka has got.
The second line
contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109), where ai is the side length of i-th box.
Output
Print the minimum
possible number of visible boxes.
Examples
Input
3
1 2 3
1 2 3
Output
1
Input
4
4 2 4 3
4 2 4 3
Output
2
Note
In the first example
it is possible to put box 1 into box 2, and 2 into 3.
In the second example
Mishka can put box 2 into box 3, and box 4 into box 1.
Solution(15)
#include <stdio.h>
#include<stdlib.h>
int count=0;
void visiblebox(long int a[5000], int n)
{
if(n==0)
return;
int i,j,k=0;
long int b[5000];
for(i=0;i<n;i++)
{
if(a[i]==a[i+1])
b[k++]=a[i];
}
count+=1;
visiblebox(b,k);
return;
}
int comparator(const void *p, const void *q)
{
long int l = *(long int *)p;
long int r = *(long int *)q;
return (l-r);
}
int main()
{
int i,n;
long int a[5000];
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%ld",&a[i]);
qsort(a,n,sizeof(long int),comparator);
visiblebox(a,n);
printf("%d\n",count);
return 0;
}
(16) - 903B
B.
The Modcrab
Time limit per test 1 second
Memory limit per test 256 megabytes
Input standard input
Output standard output
Vova
is again playing some computer game, now an RPG. In the game Vova's character
received a quest: to slay the fearsome monster called Modcrab.
After two hours of playing the game Vova has
tracked the monster and analyzed its tactics. The Modcrab has h2 health points and an attack power
of a2. Knowing that, Vova
has decided to buy a lot of strong healing potions and to prepare for battle.
Vova's character has h1 health points and an attack power
of a1. Also he has a large
supply of healing potions, each of which increases his current amount of health
points by c1 when Vova drinks
a potion. All potions are identical to each other. It is guaranteed that c1 > a2.
The battle consists of multiple phases. In the
beginning of each phase, Vova can either attack the monster (thus reducing its
health by a1) or drink a healing
potion (it increases Vova's health by c1; Vova's health can exceed h1). Then, if the battle is not
over yet, the Modcrab attacks
Vova, reducing his health by a2. The battle ends when Vova's (or Modcrab's) health drops
to 0 or lower. It is
possible that the battle ends in a middle of a phase after Vova's attack.
Of course, Vova wants to win the fight. But
also he wants to do it as fast as possible. So he wants to make up a strategy
that will allow him to win the fight after the minimum possible number of
phases.
Help Vova to make up a strategy! You may
assume that Vova never runs out of healing potions, and that he can always win.
Input
The first line
contains three integers h1, a1, c1 (1 ≤ h1, a1 ≤ 100, 2 ≤ c1 ≤ 100) — Vova's health, Vova's attack power and the
healing power of a potion.
The second line
contains two integers h2, a2 (1 ≤ h2 ≤ 100, 1 ≤ a2 < c1) — the Modcrab's health and his attack power.
Output
In the first line
print one integer n denoting the
minimum number of phases required to win the battle.
Then print n lines. i-th line must be equal to HEAL if Vova drinks a potion in i-th phase, or STRIKE if he attacks the Modcrab.
The strategy must be
valid: Vova's character must not be defeated before slaying the Modcrab, and
the monster's health must be 0 or lower after Vova's last action.
If there are multiple
optimal solutions, print any of them.
Examples
Input
10 6 100
17 5
17 5
Output
4
STRIKE
HEAL
STRIKE
STRIKE
STRIKE
HEAL
STRIKE
STRIKE
Input
11 6 100
12 5
12 5
Output
2
STRIKE
STRIKE
STRIKE
STRIKE
Note
In the first example
Vova's character must heal before or after his first attack. Otherwise his
health will drop to zero in 2 phases while he needs 3 strikes to win.
In the second example
no healing needed, two strikes are enough to get monster to zero health and win
with 6 health left.
Solution(16)
#include <stdio.h>
int main() {
int h1,h2, a1,a2, c1; scanf("%d %d %d\n%d %d\n", &h1, &a1, &c1, &h2, &a2);
const int sc = (h2 + a1 - 1)/ a1; int hc = 0;
for(int dc = h1 - a2*(sc-1) ; dc <= 0 ; dc += (c1-a2)) ++hc;
printf("%d\n", hc+sc);
for(int i = 0 ; i < hc ; ++i) printf("HEAL\n");
for(int i = 0 ; i < sc ; ++i) printf("STRIKE\n");
return 0;
}
(17) - 887A
A.
Div. 64
Time limit per test 1 second
Memory limit per test 256 megabytes
Input standard input
Output standard output
Top-model
Izabella participates in the competition. She wants to impress judges and show
her mathematical skills.
Her
problem is following: for given string, consisting of only 0 and 1, tell if
it's possible to remove some digits in such a way, that remaining number is a
representation of some positive integer, divisible by 64, in the binary
numerical system.
Input
In the only line given
a non-empty binary string s with length up to 100.
Output
Print «yes» (without quotes) if it's possible to remove
digits required way and «no» otherwise.
Examples
Input
100010001
Output
yes
Input
100
Output
no
Note
In the first test
case, you can get string 1 000 000 after removing
two ones which is a representation of number 64 in the binary numerical system.
Solution(17)
#include <stdio.h>
#include <string.h>
int main()
{
char str[106];
scanf("%s", str);
int len = strlen(str);
if(len < 7)
{
printf("no\n");
return 0;
}
int j = 0;
while(str[j] != '1' && str[j] != '\0')
j++;
//printf("%d\n", j);
if(j == len)
{
printf("no\n");
return 0;
}
int i, cnt = 0;
for(i = j + 1; i < len; i++)
if(str[i] == '0')
cnt++;
//printf("%d\n", cnt);
if(cnt > 5)
printf("yes\n");
else
printf("no\n");
return 0;
}
(18) - 854A
A.
Fraction
Time limit per test 1 second
Memory limit per test 512 megabytes
Input standard input
Output standard output
Petya
is a big fan of mathematics, especially its part related to fractions. Recently
he learned that a fraction
During his free time, Petya thinks about
proper irreducible fractions and converts them to decimals using the
calculator. One day he mistakenly pressed addition button ( + ) instead of division button (÷) and got sum of numerator and denominator
that was equal to ninstead of the
expected decimal notation.
Petya wanted to restore the original fraction,
but soon he realized that it might not be done uniquely. That's why he decided
to determine maximum possible proper irreducible fraction 
such that sum of its
numerator and denominator equals n. Help Petya deal with this problem.
such that sum of its
numerator and denominator equals n. Help Petya deal with this problem.
Input
In the only line of
input there is an integer n (3 ≤ n ≤ 1000), the sum of numerator and denominator of the fraction.
Output
Output two
space-separated positive integers a and b, numerator and denominator of the maximum possible proper
irreducible fraction satisfying the given sum.
Examples
Input
3
Output
1 2
Input
4
output
1 3
Input
12
Output
5 7
Solution(18)
#include<stdio.h>
int main()
{
int n;
scanf("%d",&n);
if(n%2==1)
printf("%d %d", n/2, n/2+1);
else if((n/2)%2==1)
printf("%d %d", n/2-2,n/2+2);
else
printf("%d %d", n/2-1,n/2+1);
return 0;
}
(19) - 431C
C.
k-Tree
Time limit per test 1 second
Memory limit per test 256 megabytes
Input standard input
Output standard output
Quite
recently a creative student Lesha had a lecture on trees. After the lecture
Lesha was inspired and came up with the tree of his own which he called a k-tree.
A k-tree is an infinite rooted tree where:
·
each vertex has
exactly k children;
·
each edge has some
weight;
·
if we look at the
edges that goes from some vertex to its children (exactly k edges), then their weights will
equal 1, 2, 3, ..., k.
The picture below shows a part of a 3-tree.
As soon as Dima, a
good friend of Lesha, found out about the tree, he immediately wondered:
"How many paths of total weight n (the sum of all weights of the edges in
the path) are there, starting from the root of a k-tree and also containing at least one edge of
weight at least d?".
Help Dima find an answer to his question. As
the number of ways can be rather large, print it modulo 1000000007 (109 + 7).
Input
A single line contains
three space-separated integers: n, k and d (1 ≤ n, k ≤ 100; 1 ≤ d ≤ k).
Output
Print a single integer
— the answer to the problem modulo 1000000007 (109 + 7).
Examples
Input
3 3 2
Output
3
Input
3 3 3
Output
1
Input
4 3 2
Output
6
Input
4 5 2
Output
7
Solution(19)
#include <stdio.h>
int mod=1000000007;
int dp[102][102];
int ktree(int n,int k,int d) {
if(dp[n][d]!=-1) return dp[n][d]% mod;
int i=1,b=0;
if(k>=n) b=b%mod +1 %mod;
if(n==d) dp[n][d]= 1 %mod;
else if(n<d) dp[n][d]= 0 %mod;
else{
while(i<d && i<=k && (n-i)>0)
{
b= (b%mod +ktree(n-i,k,d)% mod)%mod;
i++;
}
while(i>=d && i<=k && (n-i)>0)
{
b=(b%mod +ktree(n-i,k,1)% mod)%mod;
i++;
}
dp[n][d]= b% mod;
}
return dp[n][d];
}
int main()
{
int i,j;
for(i=0;i<102;i++)
for(j=0;j<102;j++)
dp[i][j]=-1;
// printf("%d",dp[50][3]);
int n,k,d;
scanf("%d%d%d",&n,&k,&d);
printf("%d",ktree(n,k,d)%mod);
return 0;
}
(20) - 263A
A. Beautiful Matrix
Time limit per test 2 seconds
Memory limit per test 256 megabytes
Input standard input
Output standard output
You've
got a 5 × 5 matrix,
consisting of 24 zeroes and a
single number one. Let's index the matrix rows by numbers from 1 to 5 from top to bottom, let's index the
matrix columns by numbers from 1 to 5 from left to
right. In one move, you are allowed to apply one of the two following
transformations to the matrix:
1. Swap two neighboring matrix rows, that is,
rows with indexes i and i + 1 for some integer i (1 ≤ i < 5).
2. Swap two neighboring matrix columns, that is,
columns with indexes j and j + 1 for some integer j (1 ≤ j < 5).
You think that a matrix looks beautiful, if the single number one of the matrix is
located in its middle (in the cell that is on the intersection of the third row
and the third column). Count the minimum number of moves needed to make the
matrix beautiful.
Input
The input consists of
five lines, each line contains five integers: the j-th integer in the i-th line of the input represents the element
of the matrix that is located on the intersection of the i-th row and the j-th column. It is guaranteed that the matrix
consists of 24 zeroes and a
single number one.
Output
Print a single integer
— the minimum number of moves needed to make the matrix beautiful.
Examples
Input
0 0 0 0 0
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
Output
3
Input
0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 0 0
Output
1
Solution(20)
#include<stdio.h>
#include<string.h>
#include<ctype.h>
int main(){
int i,j,m[5][5],p,q;
for(i=0;i<5;i++){
for(j=0;j<5;j++){
scanf("%d",&m[i][j]);
}
}
for(i=0;i<5;i++){
for(j=0;j<5;j++){
if(m[i][j]==1)goto x;
}
}
x:
i++;j++;
//printf("%d %d\n",i,j);
if(i<=3)
p=3-i;
else
p=i-3;
if(j<=3)
q=3-j;
else
q=j-3;
printf("%d",p+q);
return 0;
}
The Gaming Council: Casino & Sports Betting | JTM Hub
ReplyDeleteOur Casino & Sports Betting destination is your destination for 오산 출장샵 the best in gaming, 김천 출장샵 entertainment, dining, hotel and more. 원주 출장마사지 Join 정읍 출장안마 us today for 구미 출장안마