/Benny and Triangle

Benny and Triangle

One day Benny decides to miss lessons. But as she is a very good pig she will do her homework anyway. She doesn't know anything about the content of this lessons. Your task is to help her.

The problem is following: you are given a right triangle with coordinates of vertices (0, 0), (0, a), (b, 0) and integer p. You may choose any value val and draw a vertical line x = val. After that let area(val) be the area of the part of triangle at the right side of this line. Your task is to find such minimal val that area(val) is not more than p% of the area of the given triangle.

Input

The first and the only one line contains three integers a, b and p.

Output

Output in a single line answer to the problem with two signs after decimal point.

It is guaranteed that the answer+10^-6 and answer-10^-6 would produce the same rounded answer.

Constraints

• 1 ≤ a, b ≤ 10⁷
• 1 ≤ p < 100
• 1 ≤ a, b ≤ 10³ holds for test cases worth 20% of the problem's score.

---

Sample Input

(Plaintext Link)

2 2 25

Sample Output

(Plaintext Link)

1.00

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
//typedef long int li;
typedef unsigned long long int ulli;
#define ini(a, v)   memset(a, v, sizeof(a))
#define all(x)      (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define test() int t; cin>>t;while(t--)
 
#define si(x) scanf("%d",&x)
#define slli(x) scanf("%lld",&x)
#define sli(x) scanf("%ld",&x)
#define sd(x) scanf("%d",&x)
 
#define pfi(x) printf("%d\n",x)
#define pfli(x) printf("%ld\n",x)
#define pflli(x) printf("%lld\n",x)
 
#define abs(x) ((x)>0?(x):-(x))
 
 
#define TRI(a,b,c) mp(mp(a,b),c)
 
#define INDEX(arr,ind) (lower_bound(all(arr),ind)-arr.begin())
#define LB(a,x) (lower_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which does not compare less than val.
#define UB(a,x) (upper_bound(all(a),x)-a.begin()) //  first element in the range [first,last) which compares greater than val.
#define all(x) x.begin(),x.end()
#define sz size()
 
#define rep(i,a,b) for(int  i=(a);i<(b);i++)
#define repl(i,a,b) for(lli  i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b);i>=(a);i--)
#define foreach( gg,itit ) for( typeof(gg.begin()) itit=gg.begin();itit!=gg.end();itit++ )
 
typedef pair<lli,lli> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
vector<pair<lli,lli> > v;
vector<pair<pair<lli,lli>,char > > op;
int main()
 {
   double a,b,p;
   cin>>a>>b>>p;
   p=p*.01;
   double l=0; 
    double r=b;    
    double ach=(p*(b*a))/2.0;
    double ans=0.0;
   while(r-l>=0.0000001)
    {
         double mid=(l+r)/2.0;
        // printf("%.5lf\n",mid);
         double pp=(-(a*mid)+a*b)/b;
         double ar=(pp*(b-mid))/2.0;
         if(ach-ar>=0.0000001)
          {
           r=mid;
           ans=mid;
    }
    else 
    { 
       l=mid;
    }
    }
    printf("%.2lf",ans);
    return 0;
 }

**Multiplication Table(div2 D)

 Multiplication Table

Bizon the Champion isn't just charming, he also is very smart.

While some of us were learning the multiplication table, Bizon the Champion had fun in his own manner. Bizon the Champion painted ann × m multiplication table, where the element on the intersection of the i-th row and j-th column equals i·j (the rows and columns of the table are numbered starting from 1). Then he was asked: what number in the table is the k-th largest number? Bizon the Champion always answered correctly and immediately. Can you repeat his success?

Consider the given multiplication table. If you write out all n·m numbers from the table in the non-decreasing order, then the k-th number you write out is called the k-th largest number.

Input

The single line contains integers n, m and k (1 ≤ n, m ≤ 5·105; 1 ≤ k ≤ n·m).

Output

Print the k-th largest number in a n × m multiplication table.

Sample test(s)

input

2 2 2

output

2

input

2 3 4

output

3

input

1 10 5

output

5

Note

A 2 × 3 multiplication table looks like this:

1 2 3
2 4 6

-----------------------------------editorial----------------------------------------

Solution is discreat binary search. We need to find largest x such that amount of numbers from table, least than x, is strictly less than k. 

suppose by descreat b search we set that let answer is X than count no of numbers in each row <=X

this can easily done in o(1) in each row (by just devide )

now value x for which exactly k no of numbers are less than x will be the answer 

main problem is redendency 

---ex suppose input is 3,5,9

soo if create array and sor it it will be like 

1 2 2 3 3 4 4 5 6 6 8 9 1014 15

now  for k=9 ans is 6 

but when we count using  our method no of numbers <=6 than it will give 10, since 6 repeats 2 times (internal repeats will never affact answer ),

so to handle this problem we count no of times 6 can be form in the given array (factorise till sqrt), in this case it is 2(let z)  and count <=6 is 10

soo answer for k=10-z+1 to 10 will be 6 

------------------------------------------------------------------code--------------------------------------------------------------------

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli ans=1e14;
lli calc(lli n,lli m ,lli num)
 {
    lli maxi=sqrt(num);
    
    int re=0;
    for(int i=1;i<=maxi;i++)
     {
      if(num%i==0)
       {
      
        lli se=num/i;
    
        if(i<=n && se<=m)
     {
     
      re++;
     }
        if(i<=m && se<=n)
     {
    
      re++;
      } 
        if(se==i && se<=n && se<=m)
     {
  
      re--;
      } 
    }
  }
 
  return re;
  
 }


int main()
 {
  lli n,m,k;
  cin>>n>>m>>k;
  lli mini=0;
  lli maxi=n*m+2;
  int s=0;
  //discreat 
  while(mini<maxi)
   {
   lli temp=0;
    lli mid=(mini+maxi)/2;
    
   
       lli re=calc(n,m,mid);// no of times mid can be formed in the given array 
     
    
    for(int i=1;i<=n;i++)
     {
      temp+=min(mid/i,m);
          
     }
     
 
    lli r1=temp-re+1;
    lli r2=temp;
   


    if(k<=r2 && k>=r1)
     {
   
      ans=min(ans,mid);
     }
     if(temp>=k)
      {
       maxi=mid;
   }
   else 
    {
     mini=mid+1;
     
    }
    
   
   }
   cout<<ans<<endl;
 }

**Little Elephant and Cards

 Little Elephant and Cards

The Little Elephant loves to play with color cards.

He has n cards, each has exactly two colors (the color of the front side and the color of the back side). Initially, all the cards lay on the table with the front side up. In one move the Little Elephant can turn any card to the other side. The Little Elephant thinks that a set of cards on the table is funny if at least half of the cards have the same color (for each card the color of the upper side is considered).

Help the Little Elephant to find the minimum number of moves needed to make the set of n cards funny.

Input

The first line contains a single integer n (1 ≤ n ≤ 105) — the number of the cards. The following n lines contain the description of all cards, one card per line. The cards are described by a pair of positive integers not exceeding 109 — colors of both sides. The first number in a line is the color of the front of the card, the second one — of the back. The color of the front of the card may coincide with the color of the back of the card.

The numbers in the lines are separated by single spaces.

Output

On a single line print a single integer — the sought minimum number of moves. If it is impossible to make the set funny, print -1.

Sample test(s)

input

3
4 7
4 7
7 4

output

0

input

5
4 7
7 4
2 11
9 7
1 1

output

2

Note

In the first sample there initially are three cards lying with colors 4, 4, 7. Since two of the three cards are of the same color 4, you do not need to change anything, so the answer is 0.

In the second sample, you can turn the first and the fourth cards. After that three of the five cards will be of color 7.

--------------------------------------------editorial---------------------------------------------------------------------------

It is nice to use the map structure in this problem, but you can solve it without map (using sorting and binary serach). Lets iterate through all possible colors that we have and suppose that this currect color is the one that will make our set funny. The minimal number through all this will be the answer. To find the minimal number of turns to make our set funny using current color we need to know two numbers: the number of cards with current color on the front side and the number of cards with the current color on back side (but not at the same time). Let it be integers a and b. Let m = (n + 1) / 2 — the minimal number of the same cards required to get the funny set. Then if a + b < m it is impossible to make set funny using current color at all. If a ≥ m then the answer is 0, otherwise the answer ism - a.

--------------------------------------------------------code---------------------------------------------------------------------

implementation is easy ..

only tricky thing is that there may  be possibility a card which is not in front side but  , it can made answer. because on opposite side its enough pairs are available ..

------------------------------------------code----------------------------------------------------------------------------------

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

#define test()    int test_case;cin>>test_case;while(test_case--)

#define fr(i,n) for(int i=0;i<n;i++)

#define frr(i,a,n) for(int i=a;i<n;i++)

#define sll(a) scanf("%lld",&a)

#define sl(a) scanf("%ld",&a)

#define si(a) scanf("%i",&a)

#define sd(a)  scanf("%ld",&a)

#define sf(a) scanf("%f",&a)

#define rn(a) return a

#define pai pair<int,int>

#define pal pair<li,li>

#define pall pair<lli,lli>

//#define ff first

//#define second second

#define mod  1000000007

#define mp make_pair

#define pb push_back

#define pll(a) printf("%lld\n",a)

#define pl(a) printf("%lld\n",a)

#define pi(a) printf("%d\n",a)

#define pd(a) printf("%lf\n",a)

#define pf(a) printf("%f\n",a)

#define lc (start+end)/2

#define rc  lc+1

int main()

 {

  int n;

   cin>>n;

   vector<pall> v;

   vector<lli> v1;

   map<lli,int> back;

   set<lli> s;//  will contain all distinct colour which can be give answer 

   

   for(int i=0;i<n;i++)

    {

    lli a,b;

     cin>>a>>b;

     

     s.insert(a);

     s.insert(b);

     

     v.pb(mp(a,b));

     

     v1.pb(a);// it used for applying b'search since not applicable on vector<pair>

     

     

     

    if(a!=b)// means there is some card of different colour on opposoit side

           // which can be used after swap, eliminate a==b sice if both side card are same

           // colour than no meaning of togling

     {

       

      back[b]++;

     

 }

     

}

sort(v.begin(),v.end());

sort(v1.begin(),v1.end());

int mini;

if(n%2==1) mini=n/2+1;

else

mini=n/2;

 

  int ans=INT_MAX;

  set<lli> :: iterator its;

 

  for(its=s.begin();its!=s.end();its++)

  {

  vector<lli> :: iterator it,itv;

    lli clr=*its;

 

    itv=lower_bound(v1.begin(),v1.end(),clr);

    it=upper_bound(v1.begin(),v1.end(),clr);

    int temp=it-v1.begin();

    it--;

    int cov=it-itv+1;

 

    if(cov>mini)

     {

      cout<<"0";

      return 0;

 }

 else

 {

  int req=mini-cov;

  if(req<=back[*its])

  ans=min(ans,req);

 

 }

 

    

 }

 if(ans!=INT_MAX)

 cout<<ans<<endl;

 else

 cout<<"-1"<<endl;

 return 0 ;

 }