**Bear and Steady Gene

Bear and Steady Gene

A gene is represented as a string of length n$n$ (where n$n$ is divisible by 4$4$), composed of the letters A$\text{A}$, C$\text{C}$, T$\text{T}$, and G$\text{G}$. It is considered to be steady if each of the four letters occurs exactly n4$\frac{n}{4}$ times. For example, GACT$\text{GACT}$ and AAGTGCCT$\text{AAGTGCCT}$ are both steady genes.

Bear Limak is a famous biotechnology scientist who specializes in modifying bear DNA to make it steady. Right now, he is examining a gene represented as a string s$s$. It is not necessarily steady. Fortunately, Limak can choose one (maybe empty) substring of s$s$ and replace it with any substring of the same length.

Modifying a large substring of bear genes can be dangerous. Given a string s$s$, can you help Limak find the length of the smallest possible substring that he can replace to make s$s$ a steady gene?

Note: A substring of a string S$S$ is a subsequence made up of zero or more consecutivecharacters of S$S$.

Input Format

The first line contains an interger n$n$ divisible by 4$4$, denoting the length of a string s$s$.
The second line contains a string s$s$ of length n$n$. Each character is one of the four: A$\text{A}$, C$\text{C}$, T$\text{T}$, G$\text{G}$.

Constraints

• 4≤n≤500000$4\le n\le 500000$
• n$n$ is divisible by 4$4$

Subtask

• 4≤n≤2000$4\le n\le 2000$ in tests worth 30%$30\mathrm{\%}$ points.

Output Format

On a new line, print the minimum length of the substring replaced to make s$s$ stable.

Sample Input

8  
GAAATAAA

Sample Output

5

Explanation

One optimal solution is to replace a substring AAATA$\text{AAATA}$ with TTCCG$\text{TTCCG}$, resulting in GTTCCGAA$\text{GTTCCGAA}$. The replaced substring has length 5$5$, so we print 5$5$ on a new line.

-------------------------------------------EDITORIAL--------------------------------------

THIS PROBLEM CAN EASILY SOLVE IF WE USE DISCRET BINARY SEARCH , 

MAIN THING IS THAT WHICH SUBSTRING IS VALID TO REPLACE ..

IF A SUB STRING HAVE  EXTRA CHARACTERS WHICH ARE PRESENT IN THE STRING ( IT CAN HAVE SOME NON EXTRA CHARS ALSO ) THAT SUB STRING CAN BE REPLACE..

NOW SUPPOSE WE WANT TO REPLACE A SUB STRING WHICH END AT INDEX  i , 

THAN WE CAN REPLACE MAXIMUM FROM INDEX (0,i) AND MINIMUM AT SOME INDEX (j,i) , WE CAN FIX THIS INTERMEDIATE INDEX USING THE DISRCRET BINARY SEARCH ...

MAIN OBSERVATION IS THAT IF SUB STRING (j,i )  CAN BE A VALID SUBSTRING TO REPLACE  THAN A SUB STRING (k,i) WHERE k<j is also a valid sub string to replace  

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

#include<bits/stdc++.h>

using namespace std;

struct st

{

int g,a,t,c;

} stt[1000000];

int main()

 {

  int n;

   cin>>n;

   string s;

   cin>>s;

   int G=0,A=0,C=0,T=0;

    int len=s.length();

    stt[0].c=0;

    stt[0].a=0;

    stt[0].t=0;

    stt[0].g=0;

   //  cout<<s<<endl;

   

    for(int i=1;i<=len;i++)

     {

      if(s[i-1]=='G') 

 {

  G++;

  stt[i].g=1;

 }

      else if(s[i-1]=='C') 

{

C++;

stt[i].c=1;

}

 

      else if(s[i-1]=='A')

{

A++;

stt[i].a=1;;

 } 

      else 

 {

  // cout<<" wtf"<<endl;

  T++;

  stt[i].t=1;

  //cout<<stt[i].t<<endl;

 }

 

 

  stt[i].a+=stt[i-1].a;

  stt[i].c+=stt[i-1].c;

  stt[i].g+=stt[i-1].g;

  stt[i].t+=stt[i-1].t;

  

     

}

  n=len;

int exa=A-n/4;

int exg=G-n/4;

int exc=C-n/4;

int ext=T-n/4;

         if(A==n/4 && T==n/4 && G==n/4 && C==n/4 )

          {

          cout<<0<<endl;

          return 0;

 }

int ans=1000000;

 

for(int i=1;i<=len;i++)

 {

 

   int l=1,r=i;

   int c=0;

     

   while(c<=70)

    {

   

     c++;

     int mid=(l+r)/2;

       if(  exa<=stt[i].a-stt[mid-1].a && exg<=stt[i].g-stt[mid-1].g && exc<=stt[i].c-stt[mid-1].c && ext<=stt[i].t-stt[mid-1].t  )

         {

            l=mid;

            ans=min(ans,i-mid+1);

  }

 

  else

  {

  r=mid;

  }

}

 }

   if(ans!=1000000)

  cout<<ans<<endl;

  else cout<<0<<endl;

 }

/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;
 }