Codeforces ラウンド #257 (ディビジョン 2)_html/css_WEB-ITnose

Orz。。

あたりのメモリ制限テスト

256 メガバイト

入力

標準入力

出力

標準出力

Jzzhu の学校には n 人の子供がいます。 Jzzhu は彼らにキャンディーをあげるつもりです。すべての子に 1 から n までの番号を付けましょう。 i 番目の子供は、少なくとも AI キャンディーを手に入れたいと考えています。

Jzzhu は子供たちに並ぶように指示します。最初は、i 番目の子が列の i 番目の位置に立っています。それからJzzhuはキャンディーの配布を開始します。彼は次のアルゴリズムに従います。

列の最初の子供に m 個のキャンディーを与えます。

この子供がまだ十分なキャンディーを持っていない場合、子供は列の最後に行き、そうでない場合は家に帰ります。

ラインが空でない間に最初の 2 つのステップを繰り返します。

すべての子供たちを家に帰った順に考えます。 Jzzhu は、どの子がこの順序で最後になるかを知りたいと考えています。

入力

最初の行には、2 つの整数 n,?m (1?≤?n?≤?100; 1?≤?m?≤) が含まれています?100）。 2 行目には、n 整数 a1,?a2,?...,?an (1?≤?ai?≤?100) が含まれています。
出力
最後の子の番号を表す単一の整数を出力します。

サンプルテスト

入力

rree

出力

入力

5 21 3 1 4 2

出力

注意

最初のサンプルを考えてみましょう。

最初の子1人はキャンディーを2個もらって家に帰ります。次に、子供 2 はキャンディーを 2 つ受け取り、列の最後尾に行きます。現在、行は [3, 4, 5, 2] のようになります (行の順序で子のインデックス)。次に、子供 3 はキャンディーを 2 つ手に入れて家に帰り、子供 4 はキャンディーを 2 つ手に入れて列の最後尾に行きます。現在、行は [5, 2, 4] のようになります。それから子供5はキャンディーを2個もらって家に帰ります。次に、子供 2 はキャンディーを 2 つ手に入れて家に帰り、最後に子供 4 はキャンディーを 2 つ手に入れて家に帰ります。

Child 4 が最後に家に帰ります。

6 41 1 2 2 3 3

も役に立つ队列の書き込み。

B. Jzzhu とシーケンス

テストごとの制限時間

1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

Jzzhu は一種のシーケンスを発明しました。それらは次の特性を満たします:

x と y が与えられているので、fn 法 1000000007 (109?+?7) を計算してください。

入力

最初の行には 2 つの整数 x と y (|x|,?|y|?≤?109) が含まれています。 ）。 2 行目には単一の整数 n (1?≤?n?≤?2・109) が含まれています。

出力

fn モジュロ 1000000007 (109?+?7) を表す単一の整数を出力します。

サンプルテスト

入力

#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<vector>#include<queue>#define INF 0x3f3f3f3fusing namespace std;int main(){    int n, m;    int ans = 0, t = 0, a;    cin >> n >> m;    for (int i = 0; i < n; i++)    {        cin >> a;        if (i == 0 || (a+m-1)/m >= t)        {            ans = i+1;            t = (a+m-1)/m;        }    }    cout << ans << endl;    return 0;}

出力

入力

#include <bits/stdc++.h>using namespace std;const int maxn = 1000 + 10;int n, m;struct node{    int id, cd;};int main(){    int i, j;    scanf("%d%d", &n, &m);    queue<node> q;    for(i=1; i<=n; ++i)    {        scanf("%d", &j);        node t;        t.id = i; t.cd = j;        q.push(t);    }    node cur;    while(!q.empty())    {        cur = q.front(); q.pop();        if(cur.cd >m)        {            cur.cd -= m;            q.push(cur);        }    }    printf("%d\n", cur.id);    return 0;}

出力

2 33

注

最初のサンプルでは、​​f2?=?f1?+?f3 , 3?=?2?+?f3, f3?=?1.

2 番目のサンプルでは、​​ f2?=??-?1; ?-?1 モジュロ (109?+?7) は (109?+?6) に等しい。

原来没考虑好为-1的情况。。淡淡的忧桑。。。。

#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<vector>#include<queue>#define INF 1000000007using namespace std;int main(){    int x, y;    cin>>x>>y;    int n;    cin>>n;    n %= 6;  //6次一循环    int a[10];    a[1]=(x+INF) % INF;    a[2]=(y+INF) % INF;    a[3]=(a[2]-a[1]+INF) % INF;    a[4]=(-x+INF) % INF;    a[5]=(-y+INF) % INF;    a[0]=(a[1]-a[2]+INF) % INF;    n = n%6;    cout<<a[n]<<endl;    return 0;}

C. Jzzhu and Chocolate

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Jzzhu has a big rectangular chocolate bar that consists of n?×?m unit squares. He wants to cut this bar exactly k times. Each cut must meet the following requirements:

each cut should be straight (horizontal or vertical);

each cut should go along edges of unit squares (it is prohibited to divide any unit chocolate square with cut);

each cut should go inside the whole chocolate bar, and all cuts must be distinct.

The picture below shows a possible way to cut a 5?×?6 chocolate for 5 times.

Imagine Jzzhu have made k cuts and the big chocolate is splitted into several pieces. Consider the smallest (by area) piece of the chocolate, Jzzhu wants this piece to be as large as possible. What is the maximum possible area of smallest piece he can get with exactlyk cuts? The area of a chocolate piece is the number of unit squares in it.

Input

A single line contains three integers n,?m,?k (1?≤?n,?m?≤?109; 1?≤?k?≤?2·109).

Output

Output a single integer representing the answer. If it is impossible to cut the big chocolate k times, print -1.

Sample test(s)

input

3 4 1

output

input

6 4 2

output

input

2 3 4

output

-1

Note

In the first sample, Jzzhu can cut the chocolate following the picture below:

In the second sample the optimal division looks like this:

In the third sample, it's impossible to cut a 2?×?3 chocolate 4 times.

#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<vector>#include<queue>#define INF 0x3f3f3f3fusing namespace std;long long int n, m, k;long long int i;int main(){	cin >> n >> m >>k;	if( k>n+m-2 )	{		cout << "-1"<<endl;		return 0;	}	long long int a=0, b=0;	for(i=0; i<2; swap(n,m))	{		if( k<n-1 )			a = (n/(k+1))*m;		else			a = m/(k-n+2);		if( a>=b )			b = a;		i++;	}	cout << b << endl;	return 0;}