codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1041B.md (2251B)


      1 Source: https://codeforces.com/problemset/problem/1041/B
      2 
      3 B. Buying a TV Set
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Monocarp has decided to buy a new TV set and hang it on the wall in his flat. The wall has enough free space so Monocarp can buy a TV set with screen width not greater than $a$ and screen height not greater than $b$. Monocarp is also used to TV sets with a certain aspect ratio: formally, if the width of the screen is $w$, and the height of the screen is $h$, then the following condition should be met: $\frac{w}{h} = \frac{x}{y}$.
     22 
     23 There are many different TV sets in the shop. Monocarp is sure that for any pair of positive integers $w$ and $h$ there is a TV set with screen width $w$ and height $h$ in the shop.
     24 
     25 Monocarp isn't ready to choose the exact TV set he is going to buy. Firstly he wants to determine the optimal screen resolution. He has decided to try all possible variants of screen size. But he must count the number of pairs of positive integers $w$ and $h$, beforehand, such that $(w \le a)$, $(h \le b)$ and $(\frac{w}{h} = \frac{x}{y})$.
     26 
     27 In other words, Monocarp wants to determine the number of TV sets having aspect ratio $\frac{x}{y}$, screen width not exceeding $a$, and screen height not exceeding $b$. Two TV sets are considered different if they have different screen width or different screen height.
     28 
     29 Input
     30 
     31 The first line contains four integers $a$, $b$, $x$, $y$ ($1 \le a, b, x, y \le 10^{18}$) — the constraints on the screen width and height, and on the aspect ratio.
     32 
     33 Output
     34 
     35 Print one integer — the number of different variants to choose TV screen width and screen height so that they meet the aforementioned constraints.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 17 15 5 3
     43 ```
     44 
     45 Output
     46 
     47 ```
     48 3
     49 ```
     50 
     51 Input
     52 
     53 ```
     54 14 16 7 22
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 0
     61 ```
     62 
     63 Input
     64 
     65 ```
     66 4 2 6 4
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 1
     73 ```
     74 
     75 Input
     76 
     77 ```
     78 1000000000000000000 1000000000000000000 999999866000004473 999999822000007597
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 1000000063
     85 ```
     86 
     87 Note
     88 
     89 In the first example, there are $3$ possible variants: $(5, 3)$, $(10, 6)$, $(15, 9)$.
     90 
     91 In the second example, there is no TV set meeting the constraints.
     92 
     93 In the third example, there is only one variant: $(3, 2)$.