SPOJ Problem Set (classical)
24. Small factorials
Problem code: FCTRL2
You are asked to calculate factorials of some small positive integers.
Input
An integer t, 1<=t<=100, denoting the number of testcases, followed by t lines, each containing a single integer n, 1<=n<=100.
Output
For each integer n given at input, display a line with the value of n!
Example
Sample input:
4
1
2
5
3
Sample output:
1
2
120
6
Thursday, February 10, 2011
SPOJ, NSTEPS, Number Steps
SPOJ Problem Set (classical)
1112. Number Steps
Problem code: NSTEPS
Starting from point (0,0) on a plane, we have written all non-negative integers 0, 1, 2,... as shown in the figure. For example, 1, 2, and 3 has been written at points (1,1), (2,0), and (3, 1) respectively and this pattern has continued.
You are to write a program that reads the coordinates of a point (x, y), and writes the number (if any) that has been written at that point. (x, y) coordinates in the input are in the range 0...10000.
Input
The first line of the input is N, the number of test cases for this problem. In each of the N following lines, there is x, and y representing the coordinates (x, y) of a point.
Output
For each point in the input, write the number written at that point or write No Number if there is none.
Example
Input:
3
4 2
6 6
3 4
Output:
6
12
No Number
1112. Number Steps
Problem code: NSTEPS
Starting from point (0,0) on a plane, we have written all non-negative integers 0, 1, 2,... as shown in the figure. For example, 1, 2, and 3 has been written at points (1,1), (2,0), and (3, 1) respectively and this pattern has continued.
You are to write a program that reads the coordinates of a point (x, y), and writes the number (if any) that has been written at that point. (x, y) coordinates in the input are in the range 0...10000.
Input
The first line of the input is N, the number of test cases for this problem. In each of the N following lines, there is x, and y representing the coordinates (x, y) of a point.
Output
For each point in the input, write the number written at that point or write No Number if there is none.
Example
Input:
3
4 2
6 6
3 4
Output:
6
12
No Number
SPOJ TOANDFRO, To and Fro
SPOJ Problem Set (classical)
400. To and Fro
Problem code: TOANDFRO
Mo and Larry have devised a way of encrypting messages. They first decide secretly on the number of columns and write the message (letters only) down the columns, padding with extra random letters so as to make a rectangular array of letters. For example, if the message is “There’s no place like home on a snowy night” and there are five columns, Mo would write down
t o i o y
h p k n n
e l e a i
r a h s g
e c o n h
s e m o t
n l e w x
Note that Mo includes only letters and writes them all in lower case. In this example, Mo used the character ‘x’ to pad the message out to make a rectangle, although he could have used any letter. Mo then sends the message to Larry by writing the letters in each row, alternating left-to-right and right-to-left. So, the above would be encrypted as
toioynnkpheleaigshareconhtomesnlewx
Your job is to recover for Larry the original message (along with any extra padding letters) from the encrypted one.
Input
There will be multiple input sets. Input for each set will consist of two lines. The first line will contain an integer in the range 2...20 indicating the number of columns used. The next line is a string of up to 200 lower case letters. The last input set is followed by a line containing a single 0, indicating end of input.
Output
Each input set should generate one line of output, giving the original plaintext message, with no spaces.
Example
Input:
5
toioynnkpheleaigshareconhtomesnlewx
3
ttyohhieneesiaabss
0
Output:
theresnoplacelikehomeonasnowynightx
thisistheeasyoneab
400. To and Fro
Problem code: TOANDFRO
Mo and Larry have devised a way of encrypting messages. They first decide secretly on the number of columns and write the message (letters only) down the columns, padding with extra random letters so as to make a rectangular array of letters. For example, if the message is “There’s no place like home on a snowy night” and there are five columns, Mo would write down
t o i o y
h p k n n
e l e a i
r a h s g
e c o n h
s e m o t
n l e w x
Note that Mo includes only letters and writes them all in lower case. In this example, Mo used the character ‘x’ to pad the message out to make a rectangle, although he could have used any letter. Mo then sends the message to Larry by writing the letters in each row, alternating left-to-right and right-to-left. So, the above would be encrypted as
toioynnkpheleaigshareconhtomesnlewx
Your job is to recover for Larry the original message (along with any extra padding letters) from the encrypted one.
Input
There will be multiple input sets. Input for each set will consist of two lines. The first line will contain an integer in the range 2...20 indicating the number of columns used. The next line is a string of up to 200 lower case letters. The last input set is followed by a line containing a single 0, indicating end of input.
Output
Each input set should generate one line of output, giving the original plaintext message, with no spaces.
Example
Input:
5
toioynnkpheleaigshareconhtomesnlewx
3
ttyohhieneesiaabss
0
Output:
theresnoplacelikehomeonasnowynightx
thisistheeasyoneab
SPOJ JULKA, Julka
SPOJ Problem Set (classical)
54. Julka
Problem code: JULKA
Julka surprised her teacher at preschool by solving the following riddle:
Klaudia and Natalia have 10 apples together, but Klaudia has two apples more than Natalia. How many apples does each of he girls have?
Julka said without thinking: Klaudia has 6 apples and Natalia 4 apples. The teacher tried to check if Julka's answer wasn't accidental and repeated the riddle every time increasing the numbers. Every time Julka answered correctly. The surprised teacher wanted to continue questioning Julka, but with big numbers she could't solve the riddle fast enough herself. Help the teacher and write a program which will give her the right answers.
Task
Write a program which
reads from standard input the number of apples the girls have together and how many more apples Klaudia has,
counts the number of apples belonging to Klaudia and the number of apples belonging to Natalia,
writes the outcome to standard output
Input
Ten test cases (given one under another, you have to process all!). Every test case consists of two lines. The first line says how many apples both girls have together. The second line says how many more apples Klaudia has. Both numbers are positive integers. It is known that both girls have no more than 10100 (1 and 100 zeros) apples together. As you can see apples can be very small.
Output
For every test case your program should output two lines. The first line should contain the number of apples belonging to Klaudia. The second line should contain the number of apples belonging to Natalia.
Example
Input:
10
2
[and 9 test cases more]
Output:
6
4
[and 9 test cases more]
54. Julka
Problem code: JULKA
Julka surprised her teacher at preschool by solving the following riddle:
Klaudia and Natalia have 10 apples together, but Klaudia has two apples more than Natalia. How many apples does each of he girls have?
Julka said without thinking: Klaudia has 6 apples and Natalia 4 apples. The teacher tried to check if Julka's answer wasn't accidental and repeated the riddle every time increasing the numbers. Every time Julka answered correctly. The surprised teacher wanted to continue questioning Julka, but with big numbers she could't solve the riddle fast enough herself. Help the teacher and write a program which will give her the right answers.
Task
Write a program which
reads from standard input the number of apples the girls have together and how many more apples Klaudia has,
counts the number of apples belonging to Klaudia and the number of apples belonging to Natalia,
writes the outcome to standard output
Input
Ten test cases (given one under another, you have to process all!). Every test case consists of two lines. The first line says how many apples both girls have together. The second line says how many more apples Klaudia has. Both numbers are positive integers. It is known that both girls have no more than 10100 (1 and 100 zeros) apples together. As you can see apples can be very small.
Output
For every test case your program should output two lines. The first line should contain the number of apples belonging to Klaudia. The second line should contain the number of apples belonging to Natalia.
Example
Input:
10
2
[and 9 test cases more]
Output:
6
4
[and 9 test cases more]
SPOJ FCTRL, Factorial
SPOJ Problem Set (classical)
11. Factorial
Problem code: FCTRL
The most important part of a GSM network is so called Base Transceiver Station (BTS). These transceivers form the areas called cells (this term gave the name to the cellular phone) and every phone connects to the BTS with the strongest signal (in a little simplified view). Of course, BTSes need some attention and technicians need to check their function periodically.
ACM technicians faced a very interesting problem recently. Given a set of BTSes to visit, they needed to find the shortest path to visit all of the given points and return back to the central company building. Programmers have spent several months studying this problem but with no results. They were unable to find the solution fast enough. After a long time, one of the programmers found this problem in a conference article. Unfortunately, he found that the problem is so called "Travelling Salesman Problem" and it is very hard to solve. If we have N BTSes to be visited, we can visit them in any order, giving us N! possibilities to examine. The function expressing that number is called factorial and can be computed as a product 1.2.3.4....N. The number is very high even for a relatively small N.
The programmers understood they had no chance to solve the problem. But because they have already received the research grant from the government, they needed to continue with their studies and produce at least some results. So they started to study behaviour of the factorial function.
For example, they defined the function Z. For any positive integer N, Z(N) is the number of zeros at the end of the decimal form of number N!. They noticed that this function never decreases. If we have two numbers N1
Input
There is a single positive integer T on the first line of input (equal to about 100000). It stands for the number of numbers to follow. Then there are T lines, each containing exactly one positive integer number N, 1 <= N <= 1000000000.
Output
For every number N, output a single line containing the single non-negative integer Z(N).
Example
Sample Input:
6
3
60
100
1024
23456
8735373
Sample Output:
0
14
24
253
5861
2183837
11. Factorial
Problem code: FCTRL
The most important part of a GSM network is so called Base Transceiver Station (BTS). These transceivers form the areas called cells (this term gave the name to the cellular phone) and every phone connects to the BTS with the strongest signal (in a little simplified view). Of course, BTSes need some attention and technicians need to check their function periodically.
ACM technicians faced a very interesting problem recently. Given a set of BTSes to visit, they needed to find the shortest path to visit all of the given points and return back to the central company building. Programmers have spent several months studying this problem but with no results. They were unable to find the solution fast enough. After a long time, one of the programmers found this problem in a conference article. Unfortunately, he found that the problem is so called "Travelling Salesman Problem" and it is very hard to solve. If we have N BTSes to be visited, we can visit them in any order, giving us N! possibilities to examine. The function expressing that number is called factorial and can be computed as a product 1.2.3.4....N. The number is very high even for a relatively small N.
The programmers understood they had no chance to solve the problem. But because they have already received the research grant from the government, they needed to continue with their studies and produce at least some results. So they started to study behaviour of the factorial function.
For example, they defined the function Z. For any positive integer N, Z(N) is the number of zeros at the end of the decimal form of number N!. They noticed that this function never decreases. If we have two numbers N1
Input
There is a single positive integer T on the first line of input (equal to about 100000). It stands for the number of numbers to follow. Then there are T lines, each containing exactly one positive integer number N, 1 <= N <= 1000000000.
Output
For every number N, output a single line containing the single non-negative integer Z(N).
Example
Sample Input:
6
3
60
100
1024
23456
8735373
Sample Output:
0
14
24
253
5861
2183837
SPOJ ADDREV, Adding Reversed Numbers
SPOJ Problem Set (classical)
42. Adding Reversed Numbers
Problem code: ADDREV
The Antique Comedians of Malidinesia prefer comedies to tragedies. Unfortunately, most of the ancient plays are tragedies. Therefore the dramatic advisor of ACM has decided to transfigure some tragedies into comedies. Obviously, this work is very hard because the basic sense of the play must be kept intact, although all the things change to their opposites. For example the numbers: if any number appears in the tragedy, it must be converted to its reversed form before being accepted into the comedy play.
Reversed number is a number written in arabic numerals but the order of digits is reversed. The first digit becomes last and vice versa. For example, if the main hero had 1245 strawberries in the tragedy, he has 5421 of them now. Note that all the leading zeros are omitted. That means if the number ends with a zero, the zero is lost by reversing (e.g. 1200 gives 21). Also note that the reversed number never has any trailing zeros.
ACM needs to calculate with reversed numbers. Your task is to add two reversed numbers and output their reversed sum. Of course, the result is not unique because any particular number is a reversed form of several numbers (e.g. 21 could be 12, 120 or 1200 before reversing). Thus we must assume that no zeros were lost by reversing (e.g. assume that the original number was 12).
Input
The input consists of N cases (equal to about 10000). The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly one line with two positive integers separated by space. These are the reversed numbers you are to add.
Output
For each case, print exactly one line containing only one integer - the reversed sum of two reversed numbers. Omit any leading zeros in the output.
Example
Sample input:
3
24 1
4358 754
305 794
Sample output:
34
1998
1
42. Adding Reversed Numbers
Problem code: ADDREV
The Antique Comedians of Malidinesia prefer comedies to tragedies. Unfortunately, most of the ancient plays are tragedies. Therefore the dramatic advisor of ACM has decided to transfigure some tragedies into comedies. Obviously, this work is very hard because the basic sense of the play must be kept intact, although all the things change to their opposites. For example the numbers: if any number appears in the tragedy, it must be converted to its reversed form before being accepted into the comedy play.
Reversed number is a number written in arabic numerals but the order of digits is reversed. The first digit becomes last and vice versa. For example, if the main hero had 1245 strawberries in the tragedy, he has 5421 of them now. Note that all the leading zeros are omitted. That means if the number ends with a zero, the zero is lost by reversing (e.g. 1200 gives 21). Also note that the reversed number never has any trailing zeros.
ACM needs to calculate with reversed numbers. Your task is to add two reversed numbers and output their reversed sum. Of course, the result is not unique because any particular number is a reversed form of several numbers (e.g. 21 could be 12, 120 or 1200 before reversing). Thus we must assume that no zeros were lost by reversing (e.g. assume that the original number was 12).
Input
The input consists of N cases (equal to about 10000). The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly one line with two positive integers separated by space. These are the reversed numbers you are to add.
Output
For each case, print exactly one line containing only one integer - the reversed sum of two reversed numbers. Omit any leading zeros in the output.
Example
Sample input:
3
24 1
4358 754
305 794
Sample output:
34
1998
1
TopCoder SRM 148, DIV II, MNS
Problem Statement
9 numbers need to be arranged in a magic number square. A magic number square is a square of numbers that is arranged such that every row and column has the same sum. For example:
1 2 3
3 2 1
2 2 2
Create a class MNS containing a method combos which takes as an argument a int[] numbers and returns the number of distinct ways those numbers can be arranged in a magic number square. Two magic number squares are distinct if they differ in value at one or more positions. For example, there is only one magic number square that can be made of 9 instances of the same number.
9 numbers need to be arranged in a magic number square. A magic number square is a square of numbers that is arranged such that every row and column has the same sum. For example:
1 2 3
3 2 1
2 2 2
Create a class MNS containing a method combos which takes as an argument a int[] numbers and returns the number of distinct ways those numbers can be arranged in a magic number square. Two magic number squares are distinct if they differ in value at one or more positions. For example, there is only one magic number square that can be made of 9 instances of the same number.
TopCoder SRM 148, DIV II, DivisorDigits
Problem Statement
Create a class DivDigits containing a method howMany which takes as an argument an int number and returns how many digits in number that number itself is divisible by. Count all occurences of such digits in the number, not just the first. See examples for more information.
Create a class DivDigits containing a method howMany which takes as an argument an int number and returns how many digits in number that number itself is divisible by. Count all occurences of such digits in the number, not just the first. See examples for more information.
TopCoder SRM 148, DIV II, CeyKaps
Problem Statement
The keycaps on a keyboard have been switched around, and the user is now trying to remember what he was trying to type.
Create a class CeyKaps containing the method decipher that takes a String typed, representing the visible message on the screen, and a String[] switched, representing the keycap switches. The method should return the original intended message (what keys the user thought he was pressing).
A keycap can be switched around more than once. For example, if someone switched around 'A' and 'S', then switched around 'S' and 'D', then 'D' would be where 'A' originally was, 'S' where 'D' was, and 'A' where 'S' was.
The elements of switches will be formatted as (quotes added for clarity) "*:*", where the *'s represent the keycaps to be switched. The above example would be represented as: {"A:S","S:D","D:A"}, or alternately as {"S:A","D:S","A:D"} or any other such combination. The order of the keycaps doesn't matter, but the order of the switches does.
The keycaps on a keyboard have been switched around, and the user is now trying to remember what he was trying to type.
Create a class CeyKaps containing the method decipher that takes a String typed, representing the visible message on the screen, and a String[] switched, representing the keycap switches. The method should return the original intended message (what keys the user thought he was pressing).
A keycap can be switched around more than once. For example, if someone switched around 'A' and 'S', then switched around 'S' and 'D', then 'D' would be where 'A' originally was, 'S' where 'D' was, and 'A' where 'S' was.
The elements of switches will be formatted as (quotes added for clarity) "*:*", where the *'s represent the keycaps to be switched. The above example would be represented as: {"A:S","S:D","D:A"}, or alternately as {"S:A","D:S","A:D"} or any other such combination. The order of the keycaps doesn't matter, but the order of the switches does.
Wednesday, February 9, 2011
Just Another Hacking Tool #2
In my last post on Just Another Hacking Tool #1, I mentioned a lot about references of basic hacking tool like phishing or penetrating a vulnerable server. And also in that post I mentioned that after reading from the websites (hackpconline, vxchaos, metasploit), I was able to make myself a keylogger. This video will show what I did :D
I made this keylogger with C++, implemented with the usage of openssl, Windows Socket Programming and GUI programming.
Well this is my first self-made keylogger, and I do think that it's 99% FUD (The processing will still be shown in task-manager, and at this point I think all .exe programs cannot run without being scheduled by task manager), but this keylogger is for Windows users only :(
Anyway, this keylogger has the ability to take log characters by characters the victim typed, and by default it will be sent to a defined e-mail in the program. Currently this guy can take around 80 length of characters the victim typed in, but of course It can be easily modified within a second!
The link below shows the video of my keylogger, which I made by using jing, and it's in swf format and I don't know how to insert music in swf file, so, stick with it :D
The video is here
ps: dont spam my email! and if you want me to make one for you, PM me :D
Tuesday, February 8, 2011
TopCoder SRM 147, DIV II, PeopleCircle
Problem Statement
There are numMales males and numFemales females arranged in a circle. Starting from a given point, you count clockwise and remove the K'th person from the circle (where K=1 is the person at the current point, K=2 is the next person in the clockwise direction, etc...). After removing that person, the next person in the clockwise direction becomes the new starting point. After repeating this procedure numFemales times, there are no females left in the circle.
Given numMales, numFemales and K, your task is to return what the initial arrangement of people in the circle must have been, starting from the starting point and in clockwise order.
For example, if there are 5 males and 3 females and you remove every second person, your return String will be "MFMFMFMM".
There are numMales males and numFemales females arranged in a circle. Starting from a given point, you count clockwise and remove the K'th person from the circle (where K=1 is the person at the current point, K=2 is the next person in the clockwise direction, etc...). After removing that person, the next person in the clockwise direction becomes the new starting point. After repeating this procedure numFemales times, there are no females left in the circle.
Given numMales, numFemales and K, your task is to return what the initial arrangement of people in the circle must have been, starting from the starting point and in clockwise order.
For example, if there are 5 males and 3 females and you remove every second person, your return String will be "MFMFMFMM".
TopCoder SRM 147, DIV II, CCipher
Problem Statement
Julius Caesar used a system of cryptography, now known as Caesar Cipher, which shifted each letter 2 places further through the alphabet (e.g. 'A' shifts to 'C', 'R' shifts to 'T', etc.). At the end of the alphabet we wrap around, that is 'Y' shifts to 'A'.
We can, of course, try shifting by any number. Given an encoded text and a number of places to shift, decode it.
For example, "TOPCODER" shifted by 2 places will be encoded as "VQREQFGT". In other words, if given (quotes for clarity) "VQREQFGT" and 2 as input, you will return "TOPCODER". See example 0 below.
Julius Caesar used a system of cryptography, now known as Caesar Cipher, which shifted each letter 2 places further through the alphabet (e.g. 'A' shifts to 'C', 'R' shifts to 'T', etc.). At the end of the alphabet we wrap around, that is 'Y' shifts to 'A'.
We can, of course, try shifting by any number. Given an encoded text and a number of places to shift, decode it.
For example, "TOPCODER" shifted by 2 places will be encoded as "VQREQFGT". In other words, if given (quotes for clarity) "VQREQFGT" and 2 as input, you will return "TOPCODER". See example 0 below.
Monday, February 7, 2011
Just Another Hacking Tool #1
For those of you who want to learn about hacking, like how do you steal passwords from your friend, or penetrate to a vulnerable server, I got several recommendations of website that you can read:
1. hackpconline
2. or compilation of source codes, vxchaos
3. or find a metasploit penetration testing framework
These sites provide anything there is to help you with hacking, like keylogging tools, phishing templates, XSS softwares, etc.
I myself learn a lot from those websites, and now i can make my own keylogger. So what are you waiting for, hackers-wannabe? :)
1. hackpconline
2. or compilation of source codes, vxchaos
3. or find a metasploit penetration testing framework
These sites provide anything there is to help you with hacking, like keylogging tools, phishing templates, XSS softwares, etc.
I myself learn a lot from those websites, and now i can make my own keylogger. So what are you waiting for, hackers-wannabe? :)
TopCoder SRM 192, DIV II, BoxLoader
Problem Statement
Your company has a new box loading robot. It is your job to program it to pack items into the shipping boxes. The robot does not have a very large program memory so you are restricted to placing all the items into the boxes in the same orientation. Each item is a rectangular solid with dimensions itemX by itemY by itemZ. The box is also rectangular with the dimensions boxX by boxY by boxZ. The items can be placed in the box in any orthogonal orientation (ie. the sides of the items must be parallel to the sides of the box), but only whole items can be placed in the box. Your task here is to determine the greatest number of items that can be packed into the box (with all the items in the same orientation).
For example, if the box is 100x98x81 units and the items are 3x5x7 units, then orienting the items so they are 5x7x3, allows them to fit in the box in a 20x14x27 grid, filling the entire box, which is optimal: 7560 items.
Your company has a new box loading robot. It is your job to program it to pack items into the shipping boxes. The robot does not have a very large program memory so you are restricted to placing all the items into the boxes in the same orientation. Each item is a rectangular solid with dimensions itemX by itemY by itemZ. The box is also rectangular with the dimensions boxX by boxY by boxZ. The items can be placed in the box in any orthogonal orientation (ie. the sides of the items must be parallel to the sides of the box), but only whole items can be placed in the box. Your task here is to determine the greatest number of items that can be packed into the box (with all the items in the same orientation).
For example, if the box is 100x98x81 units and the items are 3x5x7 units, then orienting the items so they are 5x7x3, allows them to fit in the box in a 20x14x27 grid, filling the entire box, which is optimal: 7560 items.
TopCoder SRM 293, DIV II, Aquarium
Problem Statement
You have a fish aquarium. You are given a int[] fishSizes, denoting the size of each fish in the aquarium. They've been getting along pretty well so far, but you would now like to add a new fish (called Bob). You know that fish sometimes eat each other. You estimate that a fish might eat another fish if and only if it is at least two times larger, but no more than ten times larger, than that other fish.
Considering this, you would like to choose Bob's size such that:
- Bob is not in danger of being eaten by any other fish (i.e., its size is not between 1/10 and 1/2, inclusive, the size of any other fish).
- Bob is not tempted to eat any other fish (i.e., no other fish in the aquarium has a size between 1/10 and 1/2, inclusive, of Bob's size).
Your task is to return the number of different integer sizes for Bob between minSize and maxSize, inclusive, that won't cause any eating "conflicts" with other fish.
You have a fish aquarium. You are given a int[] fishSizes, denoting the size of each fish in the aquarium. They've been getting along pretty well so far, but you would now like to add a new fish (called Bob). You know that fish sometimes eat each other. You estimate that a fish might eat another fish if and only if it is at least two times larger, but no more than ten times larger, than that other fish.
Considering this, you would like to choose Bob's size such that:
- Bob is not in danger of being eaten by any other fish (i.e., its size is not between 1/10 and 1/2, inclusive, the size of any other fish).
- Bob is not tempted to eat any other fish (i.e., no other fish in the aquarium has a size between 1/10 and 1/2, inclusive, of Bob's size).
Your task is to return the number of different integer sizes for Bob between minSize and maxSize, inclusive, that won't cause any eating "conflicts" with other fish.
TopCoder SRM 337, DIV II, AnagramList
Problem Statement
An anagram of a string is any string that contains the same characters in any order. For example, the anagrams of "tree" are, in alphabetical order: "eert", "eetr", "eret", "erte", "eter", "etre", "reet", "rete", "rtee", "teer", "tere" and "tree".
You will be given a String s and an int i. Return the ith (0-based) anagram of s when listed in alphabetical order. If there is no such anagram, return an empty String.
An anagram of a string is any string that contains the same characters in any order. For example, the anagrams of "tree" are, in alphabetical order: "eert", "eetr", "eret", "erte", "eter", "etre", "reet", "rete", "rtee", "teer", "tere" and "tree".
You will be given a String s and an int i. Return the ith (0-based) anagram of s when listed in alphabetical order. If there is no such anagram, return an empty String.
TopCoder SRM 496, DIV II, Anagram Free
Problem Statement
A string X is an anagram of string Y if X can be obtained by arranging all characters of Y in some order, without removing any characters and without adding new characters. For example, each of the strings "baba", "abab", "aabb" and "abba" is an anagram of "aabb", and strings "aaab", "aab" and "aabc" are not anagrams of "aabb".
A set of strings is anagram-free if it contains no pair of strings which are anagrams of each other. Given a set of strings S, return the size of its largest anagram-free subset. Note that the entire set is considered a subset of itself.
A string X is an anagram of string Y if X can be obtained by arranging all characters of Y in some order, without removing any characters and without adding new characters. For example, each of the strings "baba", "abab", "aabb" and "abba" is an anagram of "aabb", and strings "aaab", "aab" and "aabc" are not anagrams of "aabb".
A set of strings is anagram-free if it contains no pair of strings which are anagrams of each other. Given a set of strings S, return the size of its largest anagram-free subset. Note that the entire set is considered a subset of itself.
Facebook Hacker Cup 2011 Round 1C, N-Factorful
When I opened Facebook Hacker Cup 2011 Round 1C's problems, this is the first problem that I open because I didnt have enough time to do all three.
When I thought I did this problem right because it gave me the right output for the sample problem, It turned out I got something wrong in my code because facebook told so. Then I checked my code, and apparently I forgot to change sieve of eratostheness upper limit (sqrt(n)) to n/2 for this problem, so i didnt pass to the next round :(
N-Factorful
A number is called n-factorful if it has exactly n distinct prime factors. Given positive integers a, b, and n, your task is to find the number of integers between a and b, inclusive, that are n-factorful. We consider 1 to be 0-factorful.
Input
Your input will consist of a single integer T followed by a newline and T test cases. Each test cases consists of a single line containing integers a, b, and n as described above.
Output
Output for each test case one line containing the number of n-factorful integers in [a, b].
Constraints
T = 20
1 ≤ a ≤ b ≤ 107
0 ≤ n ≤ 10
When I thought I did this problem right because it gave me the right output for the sample problem, It turned out I got something wrong in my code because facebook told so. Then I checked my code, and apparently I forgot to change sieve of eratostheness upper limit (sqrt(n)) to n/2 for this problem, so i didnt pass to the next round :(
N-Factorful
A number is called n-factorful if it has exactly n distinct prime factors. Given positive integers a, b, and n, your task is to find the number of integers between a and b, inclusive, that are n-factorful. We consider 1 to be 0-factorful.
Input
Your input will consist of a single integer T followed by a newline and T test cases. Each test cases consists of a single line containing integers a, b, and n as described above.
Output
Output for each test case one line containing the number of n-factorful integers in [a, b].
Constraints
T = 20
1 ≤ a ≤ b ≤ 107
0 ≤ n ≤ 10
Facebook Hacker Cup Test Round, Characters
Characters
You're interested in figuring out the number of case-insensitive unique characters in some string. This sounds simple and easily-automated, so you just decide to just go for it.
Input
Your input will consist of an integer N followed by a newline. N test cases will follow, all separated by newlines. Each test case is a string of letters containing some combination of letters (upper- and lower-case are allowed), the space character, and the characters contained in the string ?!.'$%&*:;,.
Output
Your output should consist of one integer per case, separated by whitespace, indicating the number of case-insensitive unique characters contained in the input string.
Constraints
5 ≤ N ≤ 25
Input strings will not exceed 100 characters in length.
You're interested in figuring out the number of case-insensitive unique characters in some string. This sounds simple and easily-automated, so you just decide to just go for it.
Input
Your input will consist of an integer N followed by a newline. N test cases will follow, all separated by newlines. Each test case is a string of letters containing some combination of letters (upper- and lower-case are allowed), the space character, and the characters contained in the string ?!.'$%&*:;,.
Output
Your output should consist of one integer per case, separated by whitespace, indicating the number of case-insensitive unique characters contained in the input string.
Constraints
5 ≤ N ≤ 25
Input strings will not exceed 100 characters in length.
Facebook Hacker Cup Test Round, Reverser
Reverser
You've intercepted a series of transmissions encrypted using an interesting and stupid method, which you have managed to decipher. The messages contain only spaces and lowercase English characters, and are encrypted as follows: for all words in a sentence, the ith word (1-based) word is replaced with the word generated by applying the following recursive operation f(word, i):
If the length of word is less than or equal to i,
return word.
Otherwise, return f(right half of word, i) +
f(left half of word, i).
If word is of odd length, it is split such that the right side is longer. You've decided to have a little fun with whoever is sending the messages, and to broadcast your own messages encrypted in the same style that they are using.
Input
Your input will begin with an integer N, followed by a newline and then N test cases. Each case consists of an unencrypted sentence containing only spaces and lowercase letters, and cases are newline-separated. There will be no leading or trailing spaces in a sentence and there will be at most 1 space character between any otherwise-adjacent characters
Output
Output, for each case and separated by newlines, the contents of the encrypted sentence after applying the encoding method describe above to it. You may ignore traditional capitalization rules and stick to all lowercase letters.
Constraints
5 ≤ N ≤ 25
Sentences will contain no more than 100 characters.
You've intercepted a series of transmissions encrypted using an interesting and stupid method, which you have managed to decipher. The messages contain only spaces and lowercase English characters, and are encrypted as follows: for all words in a sentence, the ith word (1-based) word is replaced with the word generated by applying the following recursive operation f(word, i):
If the length of word is less than or equal to i,
return word.
Otherwise, return f(right half of word, i) +
f(left half of word, i).
If word is of odd length, it is split such that the right side is longer. You've decided to have a little fun with whoever is sending the messages, and to broadcast your own messages encrypted in the same style that they are using.
Input
Your input will begin with an integer N, followed by a newline and then N test cases. Each case consists of an unencrypted sentence containing only spaces and lowercase letters, and cases are newline-separated. There will be no leading or trailing spaces in a sentence and there will be at most 1 space character between any otherwise-adjacent characters
Output
Output, for each case and separated by newlines, the contents of the encrypted sentence after applying the encoding method describe above to it. You may ignore traditional capitalization rules and stick to all lowercase letters.
Constraints
5 ≤ N ≤ 25
Sentences will contain no more than 100 characters.
Facebook Hacker Cup Test Round, Almost
Almost
For two integers a and c, we define a and a third integer b to be almost factors of c by choosing the minimal b that minimizes |ab-c|. Your task will be to determine b given a and c.
Input
Your input file will consist of a single integer N, the number of test cases in the file, followed by N pairs of integers a and c. All tokens in the input will be separated by some whitespace.
Output
Your output should consist of N newline-separated integers, each one representing b for the corresponding pair (a, c) in the input.
Constraints
5 ≤ N ≤ 20
1 ≤ a, c ≤ 1010
For two integers a and c, we define a and a third integer b to be almost factors of c by choosing the minimal b that minimizes |ab-c|. Your task will be to determine b given a and c.
Input
Your input file will consist of a single integer N, the number of test cases in the file, followed by N pairs of integers a and c. All tokens in the input will be separated by some whitespace.
Output
Your output should consist of N newline-separated integers, each one representing b for the corresponding pair (a, c) in the input.
Constraints
5 ≤ N ≤ 20
1 ≤ a, c ≤ 1010
Facebook HC2011 Qualification Round, Studious Student
Studious Student
You've been given a list of words to study and memorize. Being a diligent student of language and the arts, you've decided to not study them at all and instead make up pointless games based on them. One game you've come up with is to see how you can concatenate the words to generate the lexicographically lowest possible string.
Input
As input for playing this game you will receive a text file containing an integer N, the number of word sets you need to play your game against. This will be followed by N word sets, each starting with an integer M, the number of words in the set, followed by M words. All tokens in the input will be separated by some whitespace and, aside from N and M, will consist entirely of lowercase letters.
Output
Your submission should contain the lexicographically shortest strings for each corresponding word set, one per line and in order.
Constraints
1 <= N <= 100
1 <= M <= 9
1 <= all word lengths <= 10
You've been given a list of words to study and memorize. Being a diligent student of language and the arts, you've decided to not study them at all and instead make up pointless games based on them. One game you've come up with is to see how you can concatenate the words to generate the lexicographically lowest possible string.
Input
As input for playing this game you will receive a text file containing an integer N, the number of word sets you need to play your game against. This will be followed by N word sets, each starting with an integer M, the number of words in the set, followed by M words. All tokens in the input will be separated by some whitespace and, aside from N and M, will consist entirely of lowercase letters.
Output
Your submission should contain the lexicographically shortest strings for each corresponding word set, one per line and in order.
Constraints
1 <= N <= 100
1 <= M <= 9
1 <= all word lengths <= 10
AOJ 0221 FizzBuzz
Problem F: FizzBuzz
「Fizz Buzz」と言われる数字を使ったゲームがあります。このゲームは複数のプレイヤーで数字を 1 から順にひとつずつ数え上げていくもので、各プレイヤーは直前のプレイヤーが発言した次の数字 をひとつだけ発言します。その時、3 で割り切れる場合は 「Fizz」, 5 で割り切れる場合は 「Buzz」、 両者で割り切れる場合は「FizzBuzz」と数の代わりに発言しなければなりません。
このゲームでは、最初の 16 までの発言は以下のようになります。
1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, ・・・
太郎君は友達とこの「Fizz Buzz」をして遊ぶことにしました。太郎君たちはルールを次のようにし ました。 「間違えた人は脱落する。その次の人は間違えた数の次の数から始める。つまり、1, 2, 3 と 発言した場合、3 で間違えたので次は 4 から始めることになる。」このルールに従ってゲームを行うの ですが、このゲームに慣れていないため、間違えたことに気付かないことがあり、公平な判断ができ ません。そこであなたは太郎君たちがこのゲームを楽しめるように、決められた発言回数が終わった 時点で残っていた人を出力するプログラムを作成することになりました。
プレイヤー数 m、ゲーム中に発言された回数 n とそれぞれの発言 s を入力とし、 入力が終わった時点で残っているプレイヤーの番号を小さい順に出力するプログラムを作成してくだ さい。ただし、プレイヤーには 1 から番号が割り振られており、発言順番も 1 番目のプレイヤーから 順に行い、一通り発言が終わると、再度 1 番目のプレイヤーから発言することとします。順番の回っ てきたプレイヤーが既に脱落している場合は、その次のプレイヤーが発言します。また、このプログラムは、プレイヤーが一人になった時点で、その後の発言を無視しなければなりません。
さらに、 m は 2 以上 1000 以下の整数、 n は 1 以上 10000 以下の 整数とし、s は数字、Fizz、Buzz、FizzBuzz、あるいは間違った発言を示すその他の文字列です。
Input
複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。 各データセットは以下のとおりです。
1 行目 プレイヤー数 m 発言回数 n (整数 整数;半角空白区切り)
2 行目 第 1 の発言 s1 (半角英数字)
3 行目 第 2 の発言 s2 (半角英数字)
:
n+1 行目 第 n の発言 sn (半角英数字)
Output
入力データセットごとに、指定された発言回数まで入力されたときに残っているプレイヤーの番号を 小さい順に出力します。
Sample Input
5 7
1
2
Fizz
4
Buzz
6
7
3 5
1
2
3
4
5
0 0
Output for the Sample Input
2 3 4 5
1
「Fizz Buzz」と言われる数字を使ったゲームがあります。このゲームは複数のプレイヤーで数字を 1 から順にひとつずつ数え上げていくもので、各プレイヤーは直前のプレイヤーが発言した次の数字 をひとつだけ発言します。その時、3 で割り切れる場合は 「Fizz」, 5 で割り切れる場合は 「Buzz」、 両者で割り切れる場合は「FizzBuzz」と数の代わりに発言しなければなりません。
このゲームでは、最初の 16 までの発言は以下のようになります。
1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, ・・・
太郎君は友達とこの「Fizz Buzz」をして遊ぶことにしました。太郎君たちはルールを次のようにし ました。 「間違えた人は脱落する。その次の人は間違えた数の次の数から始める。つまり、1, 2, 3 と 発言した場合、3 で間違えたので次は 4 から始めることになる。」このルールに従ってゲームを行うの ですが、このゲームに慣れていないため、間違えたことに気付かないことがあり、公平な判断ができ ません。そこであなたは太郎君たちがこのゲームを楽しめるように、決められた発言回数が終わった 時点で残っていた人を出力するプログラムを作成することになりました。
プレイヤー数 m、ゲーム中に発言された回数 n とそれぞれの発言 s を入力とし、 入力が終わった時点で残っているプレイヤーの番号を小さい順に出力するプログラムを作成してくだ さい。ただし、プレイヤーには 1 から番号が割り振られており、発言順番も 1 番目のプレイヤーから 順に行い、一通り発言が終わると、再度 1 番目のプレイヤーから発言することとします。順番の回っ てきたプレイヤーが既に脱落している場合は、その次のプレイヤーが発言します。また、このプログラムは、プレイヤーが一人になった時点で、その後の発言を無視しなければなりません。
さらに、 m は 2 以上 1000 以下の整数、 n は 1 以上 10000 以下の 整数とし、s は数字、Fizz、Buzz、FizzBuzz、あるいは間違った発言を示すその他の文字列です。
Input
複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。 各データセットは以下のとおりです。
1 行目 プレイヤー数 m 発言回数 n (整数 整数;半角空白区切り)
2 行目 第 1 の発言 s1 (半角英数字)
3 行目 第 2 の発言 s2 (半角英数字)
:
n+1 行目 第 n の発言 sn (半角英数字)
Output
入力データセットごとに、指定された発言回数まで入力されたときに残っているプレイヤーの番号を 小さい順に出力します。
Sample Input
5 7
1
2
Fizz
4
Buzz
6
7
3 5
1
2
3
4
5
0 0
Output for the Sample Input
2 3 4 5
1
AOJ 0109 Smart Calculator
Smart Calculator
Your task is to write a program which reads an expression and evaluates it.
The expression consists of numerical values, operators and parentheses, and the ends with '='.
The operators includes +, - , *, / where respectively represents, addition, subtraction, multiplication and division.
Precedence of the operators is based on usual laws. That is one should perform all multiplication and division first, then addition and subtraction. When two operators have the same precedence, they are applied from left to right.
You may assume that there is no division by zero.
All calculation is performed as integers, and after the decimal point should be truncated
Length of the expression will not exceed 100.
Input
The input is a sequence of datasets. The first line contains an integer n which represents the number of datasets. There will be n lines where each line contains an expression.
Output
For each datasets, prints the result of calculation.
Sample Input
2
4-2*3=
4*(8+4+3)=
Output for the Sample Input
-2
60
Your task is to write a program which reads an expression and evaluates it.
The expression consists of numerical values, operators and parentheses, and the ends with '='.
The operators includes +, - , *, / where respectively represents, addition, subtraction, multiplication and division.
Precedence of the operators is based on usual laws. That is one should perform all multiplication and division first, then addition and subtraction. When two operators have the same precedence, they are applied from left to right.
You may assume that there is no division by zero.
All calculation is performed as integers, and after the decimal point should be truncated
Length of the expression will not exceed 100.
Input
The input is a sequence of datasets. The first line contains an integer n which represents the number of datasets. There will be n lines where each line contains an expression.
Output
For each datasets, prints the result of calculation.
Sample Input
2
4-2*3=
4*(8+4+3)=
Output for the Sample Input
-2
60
AOJ 0030 Sum of Integers
Sum of Integers
Write a program which reads n digits chosen from 0 to 9 and prints the number of combinations where the sum of the digits equals s. You can not use the same digits in a combination. For example, the combinations where n = 3 and s = 6 are as follows:
1 + 2 + 3 = 6
0 + 1 + 5 = 6
0 + 2 + 4 = 6
Input
The input consists of several datasets. Each dataset includes n and s separated by a space.
The input ends with a case where n = 0 and s = 0.
Output
For each dataset, print the number of combination in a line.
Sample Input
3 6
3 1
0 0
Output for the Sample Input
3
0
Write a program which reads n digits chosen from 0 to 9 and prints the number of combinations where the sum of the digits equals s. You can not use the same digits in a combination. For example, the combinations where n = 3 and s = 6 are as follows:
1 + 2 + 3 = 6
0 + 1 + 5 = 6
0 + 2 + 4 = 6
Input
The input consists of several datasets. Each dataset includes n and s separated by a space.
The input ends with a case where n = 0 and s = 0.
Output
For each dataset, print the number of combination in a line.
Sample Input
3 6
3 1
0 0
Output for the Sample Input
3
0
AOJ 0029 English Sentence
English Sentence
Your task is to write a program which reads a text and prints two words. The first one is the word which is arise most frequently in the text. The second one is the word which has the maximum number of letters.
The text includes only alphabetical characters and spaces. A word is a sequence of letters which is separated by the spaces. You can assume the following conditions:
The number of letters in the text is less than or equal to 1000.
The number of letters in a word is less than or equal to 32..
There is only one word which is arise most frequently in given text.
There is only one word which has the maximum number of letters in given text.
Input
A text.
Output
The two words separated by a space.
Sample Input
Thank you for your mail and your lectures
Output for the Sample Input
your lectures
Your task is to write a program which reads a text and prints two words. The first one is the word which is arise most frequently in the text. The second one is the word which has the maximum number of letters.
The text includes only alphabetical characters and spaces. A word is a sequence of letters which is separated by the spaces. You can assume the following conditions:
The number of letters in the text is less than or equal to 1000.
The number of letters in a word is less than or equal to 32..
There is only one word which is arise most frequently in given text.
There is only one word which has the maximum number of letters in given text.
Input
A text.
Output
The two words separated by a space.
Sample Input
Thank you for your mail and your lectures
Output for the Sample Input
your lectures
AOJ 0026 Dropping Ink
Dropping Ink
As shown in the following figure, there is a paper consisting of a grid structure where each cell is indicated by (x, y) coordinate system.
We are going to put drops of ink on the paper. A drop comes in three different sizes: Large, Medium, and Small. From the point of fall, the ink sinks into surrounding cells as shown in the figure depending on its size. In the figure, a star denotes the point of fall and a circle denotes the surrounding cells.
Originally, the paper is white that means for each cell the value of density is 0. The value of density is increased by 1 when the ink sinks into the corresponding cells. For example, if we put a drop of Small ink at (1, 2) and a drop of Medium ink at (3, 2), the ink will sink as shown in the following figure (left side):
In the figure, density values of empty cells are 0. The ink sinking into out of the paper should be ignored as shown in the figure (top side). We can put several drops of ink at the same point.
Your task is to write a program which reads a sequence of points of fall (x, y) with its size (Small = 1, Medium = 2, Large = 3), and prints the number of cells whose density value is 0. The program must also print the maximum value of density.
You may assume that the paper always consists of 10 × 10, and 0 ≤ x < 10, 0 ≤ y < 10.
Input
x1,y1,size
x2,y2,size
.
.
.
Output
Print the number of cells whose density value is 0. (first line)
Print the maximum value of density. (second line)
Sample Input
2,5,3
3,6,1
3,4,2
4,5,2
3,6,3
2,4,1
Output for the Sample Input
77
5
As shown in the following figure, there is a paper consisting of a grid structure where each cell is indicated by (x, y) coordinate system.
We are going to put drops of ink on the paper. A drop comes in three different sizes: Large, Medium, and Small. From the point of fall, the ink sinks into surrounding cells as shown in the figure depending on its size. In the figure, a star denotes the point of fall and a circle denotes the surrounding cells.
Originally, the paper is white that means for each cell the value of density is 0. The value of density is increased by 1 when the ink sinks into the corresponding cells. For example, if we put a drop of Small ink at (1, 2) and a drop of Medium ink at (3, 2), the ink will sink as shown in the following figure (left side):
In the figure, density values of empty cells are 0. The ink sinking into out of the paper should be ignored as shown in the figure (top side). We can put several drops of ink at the same point.
Your task is to write a program which reads a sequence of points of fall (x, y) with its size (Small = 1, Medium = 2, Large = 3), and prints the number of cells whose density value is 0. The program must also print the maximum value of density.
You may assume that the paper always consists of 10 × 10, and 0 ≤ x < 10, 0 ≤ y < 10.
Input
x1,y1,size
x2,y2,size
.
.
.
Output
Print the number of cells whose density value is 0. (first line)
Print the maximum value of density. (second line)
Sample Input
2,5,3
3,6,1
3,4,2
4,5,2
3,6,3
2,4,1
Output for the Sample Input
77
5
AOJ 0005 GCD and LCM
GCD and LCM
Write a program which computes the greatest common divisor (GCD) and the least common multiple (LCM) of given a and b (0 < a, b ≤ 2,000,000,000). You can supporse that LCM(a, b) ≤ 2,000,000,000.
Input
Input consists of several data sets. Each data set contains a and b separated by a single space in a line. The input terminates with EOF.
Output
For each data set, print GCD and LCM separated by a single space in a line.
Sample Input
8 6
50000000 30000000
Output for the Sample Input
2 24
10000000 150000000
Write a program which computes the greatest common divisor (GCD) and the least common multiple (LCM) of given a and b (0 < a, b ≤ 2,000,000,000). You can supporse that LCM(a, b) ≤ 2,000,000,000.
Input
Input consists of several data sets. Each data set contains a and b separated by a single space in a line. The input terminates with EOF.
Output
For each data set, print GCD and LCM separated by a single space in a line.
Sample Input
8 6
50000000 30000000
Output for the Sample Input
2 24
10000000 150000000
AOJ 0004 Simultaneous Equation
Simultaneous Equation
Write a program which solve a simultaneous equation:
ax + by = c
dx + ey = f
The program should print x and y for given a, b, c, d, e and f(-1000 ≤ a, b, c, d, e, f ≤ 1000). You can suppose that given equation has a unique solution.
Input
The input consists of several data sets, 1 line for each data set. In a data set, there will be a, b, c, d, e, f separated by a single space. The input terminates with EOF.
Output
For each data set, print x and y separated by a single space. Print the solution to three places of decimals. Round off the solution to three decimal places.
Sample Input
1 2 3 4 5 6
2 -1 -2 -1 -1 -5
Output for the Sample Input
-1.000 2.000
1.000 4.000
Hint
try it
2 -1 -3 1 -1 -3
2 -1 -3 -9 9 27
output should be
0.000 3.000
0.000 3.000
SPOJ ONP, Transform the Expression
Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation). Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,...,z. Assume that there is only one RPN form (no expressions like a*b*c).
Input
t [the number of expressions <= 100]
expression [length <= 400]
[other expressions]
Text grouped in [ ] does not appear in the input file.
Output
The expressions in RPN form, one per line.
Example
Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))
Output:
abc*+
ab+zx+*
at+bac++cd+^*SPOJ PALIN, The Next Palindrome
A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.
Input
The first line contains integer t, the number of test cases. Integers K are given in the next t lines.
Output
For each K, output the smallest palindrome larger than K.
Example
Input:
2
808
2133
2
808
2133
Output:
818
2222
818
2222
SPOJ prime1
Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!
Input
The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.
Output
For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.
Example
Input:
2
1 10
3 5
Output:
2
3
5
7
3
5
Subscribe to:
Posts (Atom)