当前位置 : 主页 > 编程语言 > python >

Python input/output boilerplate for competitive programming

来源:互联网 收集:自由互联 发布时间:2021-06-25
The following code is my submission for Codeforces 1244C The Football Season. import ioimport sysimport mathdef inverse(a, m): u = 0 v = 1 while a != 0: t = m // a m -= t * a a, m = m, a u -= t * v u, v = v, u assert m == 1 return udef main

The following code is my submission for Codeforces 1244C The Football Season.

import io
import sys
import math

def inverse(a, m):
    u = 0
    v = 1
    while a != 0:
        t = m // a
        m -= t * a
        a, m = m, a
        u -= t * v
        u, v = v, u
    assert m == 1
    return u

def main():
    # It helps to use a input file when testing or debugging your code locally.
    # with open("main.in", "r", encoding='utf-8') as f:
    with sys.stdin as f:
        n, p, w, d = map(int, f.readline().split())
        g = math.gcd(w, d)
        if p % g:
            print(-1)
            return
        W = w // g
        D = d // g
        x = inverse(W, D)
        y = (1 - W * x) // D
        assert W * x + D * y == 1
        m = p // g
        x *= m
        y *= m
        ub = min(x // D, (n - x - y) // (W - D))
        lb = (-y + W - 1) // W
        if lb > ub:
            print(-1)
            return
        X = x - lb * D
        Y = y + lb * W
        assert X >= 0 and Y >= 0 and X * w + Y * d == p and X + Y <= n
        print(X, Y, n - X - Y)
main()

Notes:

  1. // does floor divison in Python.
网友评论