poj_3619_Speed_Reading.cpp

Problem Links:

poj3619,

Problem:

Speed Reading

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 6238		Accepted: 2697

Description

All K (1 ≤ K ≤ 1,000) of the cows are participating in Farmer John's annual reading contest. The competition consists of reading a single book with N (1 ≤ N ≤ 100,000) pages as fast as possible while understanding it.

Cow i has a reading speed S_i (1 ≤ S_i ≤ 100) pages per minute, a maximum consecutive reading time T_i (1 ≤ T_i ≤ 100) minutes, and a minimum rest time R_i (1 ≤ R_i ≤ 100) minutes. The cow can read at a rate of S_i pages per minute, but only for T_i minutes at a time. After she stops reading to rest, she must rest for R_i minutes before commencing reading again.

Determine the number of minutes (rounded up to the nearest full minute) that it will take for each cow to read the book.

Input

* Line 1: Two space-separated integers: N and K
* Lines 2..K+1: Line i+1 contains three space-separated integers: S_i , T_i , and R_i

Output

* Lines 1..K: Line i should indicate how many minutes (rounded up to the nearest full minute) are required for cow i to read the whole book.

Sample Input

10 3
2 4 1
6 1 5
3 3 3

Sample Output

6
7
7

Source

USACO 2007 November Bronze

Solution:

1st, get the total reading time for each cow;

2nd, get the up limit of consecutive reading time; (PS: result - 1 = Times needed to rest).

3rd, total = total reading time + MinrestTime * (result from 2nd - 1);

 

Source Code:

[sourcecode language="cpp" collapse="true" padlinenumbers="true"]
//Fri Apr 23 01:56:26 CDT 2010
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int main(int argc, const char* argv[])
{
// freopen("input.in", "r", stdin);
// freopen("output.out", "w", stdout);
int N, K;
while (cin >> N >> K)
{
vector<vector<int> > v(K, vector<int> (3));
for (int i = 0; i < K; i++)
{//The total Reading Time; Max Reading Time; Min Rest time;
cin >> v[i][0] >> v[i][1] >> v[i][2];
v[i][0] = (int) ((N + v[i][0] - 1) / v[i][0]);
// cout << v[i][0] << v[i][1] << v[i][2] << endl;
int times = (int) ((v[i][0] + v[i][1] - 1) / v[i][1]);
int total = v[i][0] + v[i][2]*(times-1);
cout << total << endl;
}
}
// fclose(stdin);
// fclose(stdout);
return 0;
}
[/sourcecode]