Monday, 27 April 2015

                                                         . Hexadecimal's Numbers
One beautiful July morning a terrible thing happened in Mainframe: a mean virus Megabyte somehow got access to the memory of his not less mean sister Hexadecimal. He loaded there a huge amount of n different natural numbers from 1 to n to obtain total control over her energy.
But his plan failed. The reason for this was very simple: Hexadecimal didn't perceive any information, apart from numbers written in binary format. This means that if a number in a decimal representation contained characters apart from 0 and 1, it was not stored in the memory. Now Megabyte wants to know, how many numbers were loaded successfully.
Input
Input data contains the only number n (1 ≤ n ≤ 109).
Output
Output the only number — answer to the problem.
Sample test(s)
input
10
output
2
Note
For n = 10 the answer includes numbers 1 and 10.
#####################EDITORIAL#########################################
INITIALLY  PUSH 1 IN THE STACK AND NOW TRY TO ADD 10*TOP OF STACK +1 IF IT IS LESS THAN GIVEN NO  AND ALSO TRY TO PUSH 10*TOP OF STACK IN STACK IF IT IS LESS THAN GIVEN NO   NO TOTAL NO OF PUSH DONE IN THE STACK IS THE ANSWER .....
##################################CODE####################################
#include<iostream>
using namespace std;
#include<bits/stdc++.h>
int find(long long int n)
 {
    stack<long long int > sta;
      sta.push(1);
      int count =1;
         while(!sta.empty())
          {
           long long int val=sta.top();
             sta.pop();
             if(val*10+1<=n)
              {
              count++;
              sta.push(val*10+1);
               
              }
              if(val*10<=n)
               {
                  count++;
              sta.push(val*10);
               }
          }
          return count;
          
 }
int  main()
 {
  long  long int n;
   cin>>n;
    int ans=find(n);
    cout<<ans<<endl;
    return 0;
 }
Posted by at No comments:

Sunday, 26 April 2015

A. Testing Pants for Sadness

The average miner Vaganych took refresher courses. As soon as a miner completes the courses, he should take exams. The hardest one is a computer test called "Testing Pants for Sadness".
The test consists of n questions; the questions are to be answered strictly in the order in which they are given, from question 1 to question n. Question i contains ai answer variants, exactly one of them is correct.
A click is regarded as selecting any answer in any question. The goal is to select the correct answer for each of the n questions. If Vaganych selects a wrong answer for some question, then all selected answers become unselected and the test starts from the very beginning, from question 1 again. But Vaganych remembers everything. The order of answers for each question and the order of questions remain unchanged, as well as the question and answers themselves.
Vaganych is very smart and his memory is superb, yet he is unbelievably unlucky and knows nothing whatsoever about the test's theme. How many clicks will he have to perform in the worst case?
Input
The first line contains a positive integer n (1 ≤ n ≤ 100). It is the number of questions in the test. The second line contains space-separated n positive integers ai (1 ≤ ai ≤ 109), the number of answer variants to question i.
Output
Print a single number — the minimal number of clicks needed to pass the test it the worst-case scenario.
Please do not use the %lld specificator to read or write 64-bit integers in ะก++. It is preferred to use the cin, cout streams or the %I64d specificator.
Sample test(s)
input
2
1 1
output
2
input
2
2 2
output
5
input
1
10
output
10
Note
Note to the second sample. In the worst-case scenario you will need five clicks:
  • the first click selects the first variant to the first question, this answer turns out to be wrong.
  • the second click selects the second variant to the first question, it proves correct and we move on to the second question;
  • the third click selects the first variant to the second question, it is wrong and we go back to question 1;
  • the fourth click selects the second variant to the first question, it proves as correct as it was and we move on to the second question;
  • the fifth click selects the second variant to the second question, it proves correct, the test is finished.


######################EDITORIAL##########################################

IT IS EASY IF WE CHECK THIS PROB FROM BACK   .. AND FOUND A EASY PATTERN
                                            OR
We can't move to the i + 1-th question before clicking all answers at i-th question. We will move to the very beginning clicking atai - 1 answers and only one will move us to the next step. Every way from beginning to i-th question have length equal to i - 1plus one for click. There is a simple formula for i + 1-th question:
ci = (ai - 1)· i + 1, 1-based numeration.
Let's summarize all values of ci for making the answer.
############################CODE#############################################
#include<iostream>
using namespace std;
#include<bits/stdc++.h>
int main()
{
long int n; cin>>n;
long long int arr[n+10];
for(int i=0;i<n;i++) cin>>arr[i];
long long int ans=arr[n-1];
long long  int psum=arr[n-1];
//cout<<ans<<endl;
   for(int i=n-2;i>=0;i--)
    {
    long long int ppsum=ans;
     ans+=arr[i]-1;
    ans+=psum;
     psum=ans-ppsum;
    //   cout<<ans<<endl;
    }
     cout<<ans<<endl;
     return 0;
 
}
Posted by at No comments:
                                                       D. Long Jumps
Valery is a PE teacher at a school in Berland. Soon the students are going to take a test in long jumps, and Valery has lost his favorite ruler!
However, there is no reason for disappointment, as Valery has found another ruler, its length is l centimeters. The ruler already has nmarks, with which he can make measurements. We assume that the marks are numbered from 1 to n in the order they appear from the beginning of the ruler to its end. The first point coincides with the beginning of the ruler and represents the origin. The last mark coincides with the end of the ruler, at distance l from the origin. This ruler can be repesented by an increasing sequence a1, a2, ..., an, where ai denotes the distance of the i-th mark from the origin (a1 = 0, an = l).
Valery believes that with a ruler he can measure the distance of d centimeters, if there is a pair of integers i and j (1 ≤ i ≤ j ≤ n), such that the distance between the i-th and the j-th mark is exactly equal to d (in other words, aj - ai = d).
Under the rules, the girls should be able to jump at least x centimeters, and the boys should be able to jump at least y (x < y) centimeters. To test the children's abilities, Valery needs a ruler to measure each of the distances x and y.
Your task is to determine what is the minimum number of additional marks you need to add on the ruler so that they can be used to measure the distances x and y. Valery can add the marks at any integer non-negative distance from the origin not exceeding the length of the ruler.
Input
The first line contains four positive space-separated integers n, l, x, y (2 ≤ n ≤ 105, 2 ≤ l ≤ 109, 1 ≤ x < y ≤ l) — the number of marks, the length of the ruler and the jump norms for girls and boys, correspondingly.
The second line contains a sequence of n integers a1, a2, ..., an (0 = a1 < a2 < ... < an = l), where ai shows the distance from the i-th mark to the origin.
Output
In the first line print a single non-negative integer v — the minimum number of marks that you need to add on the ruler.
In the second line print v space-separated integers p1, p2, ..., pv (0 ≤ pi ≤ l). Number pi means that the i-th mark should be at the distance of pi centimeters from the origin. Print the marks in any order. If there are multiple solutions, print any of them.
Sample test(s)
input
3 250 185 230
0 185 250
output
1
230
input
4 250 185 230
0 20 185 250
output
0
input
2 300 185 230
0 300
output
2
185 230
Note
In the first sample it is impossible to initially measure the distance of 230 centimeters. For that it is enough to add a 20 centimeter mark or a 230 centimeter mark.
In the second sample you already can use the ruler to measure the distances of 185 and 230 centimeters, so you don't have to add new marks.
In the third sample the ruler only contains the initial and the final marks. We will need to add two marks to be able to test the children's skills.

Posted by at No comments:
Subscribe to: Posts (Atom)